Correcting execution of distributed queries

ABSTRACT

Algorithms for processing distributed queries require a priori estimates of the size of intermediate relations. Most such algorithms take a “static” approach in which the algorithm is completely determined before processing begins. If size estimates are found to be inaccurate at some intermediate stage, there is no opportunity to re-schedule, and the result may be far from optimal. Adaptive query execution may be used to alleviate the problem. Care is necessary, though, to ensure that the delay associated with re-scheduling does not exceed the time saved through the use of a more efficient strategy. This paper presents a low overhead delay method to decide when to correct a strategy. Sampling is used to estimate the size of relations, and alternative heuristic strategies prepared in a background mode are used to decide when to correct. Correction is made only if lower overall delay is achieved, including correction time. Evaluation using a model of a distributed data base indicates that the heuristic strategies are near optimal. Moreover, it also suggests that it is usually correct to abort creation of an intermediate relation which is much larger than predicted.

REFERENCES

• 1: Apers P., Hevner A., Yao S.B., 1983; "Algorithms for Distributed Queries", IEEE TOSE, Vol. SE-9, No. 1, Jan. 1983, 57-68.
• 2: David A. Bell , D. H. O. Ling , Sally I. McClean, Pragmatic Estimation of Join Sizes and Attribute Correlations, Proceedings of the Fifth International Conference on Data Engineering, p.76-84, February 06-10, 1989
• 3: Philip A. Bernstein , Nathan Goodman , Eugene Wong , Christopher L. Reeve , James B. Rothnie, Jr., Query processing in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.6 n.4, p.602-625, Dec. 1981 [doi>10.1145/319628.319650]
• 4: Peter Bodorik , J. Spruce Riordon, Distributed Query Processing Optimization Objectives, Proceedings of the Fourth International Conference on Data Engineering, p.320-329, February 01-05, 1988
• 5: P. Bodorik , J. S. Riordon, A threshold mechanism for distributed query processing, Proceedings of the 1988 ACM sixteenth annual conference on Computer science, p.616-625, February 1988, Atlanta, Georgia, United States [doi>10.1145/322609.323136]
• 6: Bodorik P. and Riordon J.S., 1988c; "Evaluating Dynamic Processing of Distributed Queries", Proc. of the IEEE Int. Conference on Distributed Computing Systems, San Jose, California, June 13-17. 1988, 510-519.
• 7: P. Bodorik , J. S. Riordon, Heuristic algorithms for distributed query processing, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.144-155, December 05-07, 1988, Austin, Texas, United States
• 8: P. Bodorik , J. S. Riordon , C. Jacob, Dynamic distributed query processing techniques, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.348-357, February 21-23, 1989, Louisville, Kentucky [doi>10.1145/75427.75474]
• 9: Carey M., Livny M., Lu Hongjun, 1985; "Dynamic Task Allocation in a Distributed Database System", Proc. of the 1985 IEEE Conf. on Distributed Comp. Systems, 282-291.
• 10: Cellary W., Meyer D., 1980; "A Multi-query approach to Distributed Processing in a Relational Distributed Database Management System", Distributed Data Bases: Proc. Inter. Symp. on Distributed Data Bases, Edited by Delobel C., Litwin W., North Holland Publ. Co. March 1980.
• 11: Stefano Ceri , Giuseppe Pelagatti, Distributed databases principles and systems, McGraw-Hill, Inc., New York, NY, 1984
• 12: S Ceri , G Gottlob, Optimizing joins between two partitioned relations in distributed databases, Journal of Parallel and Distributed Computing, v.3 n.2, p.183-205, June 1986 [doi>10.1006/jpdc.1996.0054]
• 13: Tian-Jy Chao , Csaba J. Egyhazy, Estimating Temporary Files Sizes in Distributed Relational Database Systems, Proceedings of the Second International Conference on Data Engineering, p.4-12, February 05-07, 1986
• 14: S. Christodoulakis, Implications of certain assumptions in database performance evauation, ACM Transactions on Database Systems (TODS), v.9 n.2, p.163-186, June 1984 [doi>10.1145/329.318578]
• 15: Chu y., Hurley P., 1982; "Ophmal Query Processing for Distributed DB Systems", IEEE TOC, Vol. C-31, No. 9, Sept. 1982, 835-850.
• 16: Daniels et al., 1982; "An Introduction to Distributed Ouerv Comvilation in Svstem R", In mData Sihnkider G.J., editor, korth Holland, 1982, 247-290.
• 17: C. Egyhazy , K. Triantis, A query processing algorithm for distributed relational database systems, The Computer Journal, v.31 n.1, p.34-40, Feb., 1988 [doi>10.1093/comjnl/31.1.34]
• 18: Robert Epstein , Michael Stonebraker , Eugene Wong, Distributed query processing in a relational data base system, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509292]
• 19: Epstein R., Stonebraker M., 1980; "Analysis of Distributed DB Processing Strategies", 6th VLDB Conf., Montreal, QUE, Canada, 1980,92-101.
• 20: Robert Epstein , Michael Stonebraker , Eugene Wong, Distributed query processing in a relational database system, The INGRES papers: anatomy of a relational database system, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 21: Bezalel Gavish , Arie Segev, Set query optimization in distributed database systems, ACM Transactions on Database Systems (TODS), v.11 n.3, p.265-293, Sept. 1986 [doi>10.1145/6314.6488]
• 22: Hevner A., Yao S.B., 1979; "Query Processing in Distributed Data Base Systems", IEEE TOSE, Vol. SE-5, No. 3, May 1979, 177-187.
• 23: Hevner A., 1980, "Query Processing in Distr. Data Base Systems", Ph.D. thesis, Univ. of Minnesota, 1980.
• 24: Hai-Yann Hwang , Yao-Tin Yu, An Analytical Method for Estimating and Interpreting Query Time, Proceedings of the 13th International Conference on Very Large Data Bases, p.347-358, September 01-04, 1987
• 25: Toshihide Ibaraki , Tiko Kameda, On the optimal nesting order for computing N-relational joins, ACM Transactions on Database Systems (TODS), v.9 n.3, p.482-502, Sept. 1984 [doi>10.1145/1270.1498]
• 26: Alle IJbema , Henk M. Blanken, Estimating Bucket Accesses: A Practical Approach, Proceedings of the Second International Conference on Data Engineering, p.30-37, February 05-07, 1986
• 27: Anant Jhingran, A Performance Study of Query Optimization Algorithms on a Database System Supporting Procedures, Proceedings of the 14th International Conference on Very Large Data Bases, p.88-99, August 29-September 01, 1988
• 28: Kambayashi Y., 1985; "Processing Cyclic Queries:, in Query Processing in Distributed Data Base Systems, Edited by Kim, Reiner and Batory, Springer-Verlag, 1985, pp. 62-78.
• 29: Larry Kerschberg , Peter D. Ting , S. Bing Yao, Query optimization in star computer networks, ACM Transactions on Database Systems (TODS), v.7 n.4, p.678-711, Dec. 1982 [doi>10.1145/319758.319778]
• 30: Kim W., 1985; "Global Optimization of Relational Queries: A First Step", in Query Processing in Distributed Data Base Systems. Edited by Kim, Reiner and Batoxy. Springer-Verlag, 1985, pp. 207- 216.
• 31: Akhil Kumar , Michael Stonebraker, The effect of join selectives on optimal nesting order, ACM SIGMOD Record, v.16 n.1, p.28-41, March 1987 [doi>10.1145/24820.24822]
• 32: Stéphane Lafortune , Eugene Wong, A state transition model for distributed query processing, ACM Transactions on Database Systems (TODS), v.11 n.3, p.294-322, Sept. 1986 [doi>10.1145/6314.6460]
• 33: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 34: Lohman G.M., et. al., 1985; in "Query Processing in R*", in Query Processing in Database M, Edited by Kim W., Reiner D., Batory D., Springer Verlag, 1985, pp. 31-47.
• 35: Lothar F. Mackert , Guy M. Lohman, R* Optimizer Validation and Performance Evaluation for Distributed Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.149-159, August 25-28, 1986
• 36: Lothar F. Mackert , Guy M. Lohman, R* optimizer validation and performance evaluation for local queries, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.84-95, May 28-30, 1986, Washington, D.C., United States
• 37: Mahmoud S.A., Riordon J.S., Toth K.C., 1979; "Distributed Database Partitioning and Query Processing", Proc. IFIP-TC-2, Venice, Italy, 1979,32-51.
• 38: S. Masuyama , T. Ibaraki , S. Nishio , T. Hasegawa, Shortest semijoin schedule for a local area distributed database system, IEEE Transactions on Software Engineering, v.13 n.5, p.602-606, May 1987 [doi>10.1109/TSE.1987.233465]
• 39: Nguyen, N.G., 1981; "Distributed Query Management for a Local Network", Proc. 2nd hit. Conf. on Distributed Computing Systems, Paris, France, April 1981, 188-196.
• 40: Frank Olken , Doron Rotem, Simple Random Sampling from Relational Databases, Proceedings of the 12th International Conference on Very Large Data Bases, p.160-169, August 25-28, 1986
• 41: Otoo E.J., et al., 1987; "Improving Semi-Join Evaluation in Distributed Query Processing", Proc. of the IEEE Conf. on Distr. Comp. Systems, 1987, 554-561.
• 42: Ounegbe E., Rahimi S., Hevner A., 1983; "Local Query Translation and Optimization in a Distributed System", Proc. NCC, July 1983, pp. 229-239.
• 43: Perizzo W., 1984; "A Method for Processing Distr. Database Queries", IEEE TOSE, Vol. SE-IO, No. 4, July 1984,466-471.
• 44: Pyra J.. 1988; "Dynamic Query Processing in Distributed DB Systems", M.ComD.Sci. Thesis. Technical Universitv of Nova Scotia. Halifax: Nova Scotia, Canada, December 1988.
• 45: Andreas Reuter, Load Control and Load Balancing in a Shared Database Management System, Proceedings of the Second International Conference on Data Engineering, p.188-197, February 05-07, 1986
• 46: Giovanni Maria Sacco, Distributed Query Evaluation in Local Area Networks, Proceedings of the First International Conference on Data Engineering, p.510-516, April 24-27, 1984
• 47: Segev A., 1984; "Optimizing Fragmented 2-Way Joins", Proc. of the Int. Conf. on Distributed Computing Systems, 1984, 378-388.
• 48: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 49: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 50: Stanley Y. W. Su , Krishna P. Mikkilineni , Raymond A. Liuzzi , Y. C. Chow, A Distributed Query Processing Strategy Using Decomposition, Pipelining and Intermediate Result Sharing Techniques, Proceedings of the Second International Conference on Data Engineering, p.94-102, February 05-07, 1986
• 51: Brad T. Vander Zanden , Howard M. Taylor , Dina Bitton, Estimating Block Accessses when Attributes are Correlated, Proceedings of the 12th International Conference on Very Large Data Bases, p.119-127, August 25-28, 1986
• 52: Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985 [doi>10.1145/3147.3165]
• 53: Eugene Wong, A statistical approach to incomplete information in database systems, ACM Transactions on Database Systems (TODS), v.7 n.3, p.470-488, Sept. 1982 [doi>10.1145/319732.319747]
• 54: H. Z. Yang , Per-Åke Larson, Query Transformation for PSJ-Queries, Proceedings of the 13th International Conference on Very Large Data Bases, p.245-254, September 01-04, 1987
• 55: Yu C., Lin Y.C., 1982; "Some Estimation Problems in Distributed Query Processing", Proc. IEEE Data Eng. Conf., 1982, 13-19.
• 56: Yu C., et. al., 1983; "On the design of a Distr. Query Processing Strategy", Proc. ACM SIGMOD Conf., May 1983, pp. 30-39.
• 57: Yu C.T., 1985; 'Distributed Database Query Processing", in Query Processing in Database Svstems, Edited by Kim W., Reiner D., Batory D., Springer Verlag, 1985, pp. 48-61.
• 58: Clement T. Yu , Leszek Lilien , Keh-Chang Guh , Marjorie Templeton , David Brill , Arbee L. P. Chen, Adaptive Techniques for Distributed Query Optimization, Proceedings of the Second International Conference on Data Engineering, p.86-93, February 05-07, 1986
• 59: C. T. Yu , K.-C. Guh , W. Zhang , M. Templeton , D. Brill , A.L.P. Chen, Algorithms to process distributed queries in fast local networks, IEEE Transactions on Computers, v.36 n.10, p.1153-1164, Oct. 1987 [doi>10.1109/TC.1987.1676856]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Algorithms, Design, Theory