Grammar-like functional rules for representing query optimization alternatives

Abstract

Extensible query optimization requires that the “repertoire” of alternative strategies for executing queries be represented as data, not embedded in the optimizer code. Recognizing that query optimizers are essentially expert systems, several researchers have suggested using strategy rules to transform query execution plans into alternative or better plans. Though extremely flexible, these systems can be very inefficient at any step in the processing, many rules may be eligible for application and complicated conditions must be tested to determine that eligibility during unification. We present a constructive, “building blocks” approach to defining alternative plans, in which the rules defining alternatives are an extension of the productions of a grammar to resemble the definition of a function in mathematics. The extensions permit each token of the grammar to be parametrized and each of its alternative definitions to have a complex condition. The terminals of the grammar are base-level database operations on tables that are interpreted at run-time. The non-terminals are defined declaratively by production rules that combine those operations into meaningful plans for execution. Each production produces a set of alternative plans, each having a vector of properties, including the estimated cost of producing that plan. Productions can require certain properties of their inputs, such as tuple order and location, and we describe a “glue” mechanism for augmenting plans to achieve the required properties. We give detailed examples to illustrate the power and robustness of our rules and to contrast them with related ideas.

References

1. BABB 79 E Babb, Implementing a Relational Database by Means of Speclahzed Hardware, A CM Trans on Database Systems 4,1 (1979) pp 1-29
2. BATO 86 D S Batorv et al, GENESIS An Extenslble Database Management System, Tech Report TR-86-07 (Dept of Comp Scl, Umv of Texas at To appear m IEEE Trans on Software Engmeermg
3. BATO 87a D S Batory, A Molecular Database Systems Technology, Tech Report TR-87-23 (Dept of Comp Sol, Unlv of Texas at
4. BATO 87b D Batory, Extenslble Cost Models and Query Op- Umlzatlon m GENESIS, IEEE Database Engineering 10,4 (Nov 1987)
5. BACK 78 J Backus, Can programming be liberated from the yon Neumann style9 A functional style and Rs algebra of programs", Comm ACM 21,8 (Aug 1978)
6. BERN 81 P Bernstem and D-H Chiu, Using Semi-Joins to Solve Relational Quenes, Journal ACM 28,1 (Jan 1981) pp 25-40
7. BRAT 84 K Bratbergsengen, Hashing Methods and Relational Algebra Operations, Procs of the Tenth Internatwnal Conf on Very Large Data Bases (Singapore), Morgan Kaufmann Pubhshers (Los Altos, CA, 1984) pp 323-333
8. CARE 86 M J Carey, D J DeWltt, D Frank, G Graefe, J E Rachardson, E j Shekata, and M Murahknshna, The Architecture of the EXODUS Extenslble DBMS a Prehmmary Report, Procs of the Internatzonal Workshop on Object-Oriented Database Systems (Astlomar, CA, Sept 1986)
9. CHU 82 W W Chu and P Hurley, Optmtal Query Processing for Dlstnbuted Database Systems, IEEE Trans on Computers C-31,9 (Sept 1982) pp 835-850
10. CLEA 77 J C Cleaveland and R C Uzgahs, Grammars for Programming Languages, Elsewer North-Holland (New York, 1977)
11. DANI 82 D Darnels, P G Sehnger, L M Haas, B G Lmdsay, C Mohan, A Walker, and P Wtlms, An Introduction to Dtstnbuted Query Compilation in R*, Procs Second lnternatlonal Conj" on Distributed Databases (Berhn, September 1982) Also avadable as IBM Research Report RJ3497, San Jose, CA, June 1982
12. DEWI 85 D J DeWttt and R Gerber, Multtprocessor Hash- Based Join Algonthms, Procs of the Eleventh Internarwhal Conf on Very Large Data Bases (Stockholm, Sweden), Morgan Kaufmann Publishers (Los Altos, CA, September 1985) pp 151-164
13. EPST 78 R Epstein, M Stonebraker, and E Wong, Distributed Query Processing In a Relataonal Data Base System, Procs of ACM-SIGMOD (Austin, TX, May 1978) pp 169-180
14. FREY 87 J C Freytag, A Rule-Based View of Query Optmuzatton, Procs of ACM-SIGMOD (San Francisco, CA, May 1987) pp 173-180
15. GRAE 87a G Graefe and D J DeWRt, The EXODUS Optttmzer Generator, Procs of ACM-SIGMOD (San Francisco, CA, May 1987) pp 160-172
16. GRAE 87b G Graefe, Software Modulanzauon wath the EXO- DUS OpUrmzer Generator, IEEE Database Engineermg 10,4 (Nov 1987)
17. HAER 78 T Haerder, Implementing a Generahzed Access Path Structure for a Relational Database System, A CM Trans on Database Systems 3,3 (Sept 1978) pp 258-298
18. KOST 71 C H A Koster, Affix Grammars, ALGOL 68 lmplementatwn Elsener North-Holland (J E L Peck (ed), Amsterdam, 1971) pp 95-109
19. LEE 88 M K Lee, J C Freytag, and G M Lohman, Implementing an Interpreter for FuncUonal Rules m a Query Opttm~er, IBM Research Report RJ6125 IBM Almaden Research Center (San Jose, CA, March 1988)
20. LIND 87 B Lmdsay, J McPherson, and H Plrahesh, A Data Management Extension Axcbatecture, Procs of A CM- SIGMOD (San Franclsco, CA, May 1987) pp 220-226 Also available as IBM Res Report RJ5436, San Jose, CA, Dee 1986
21. LOHM 83 G M Lohman, J C Stoltzfus, A N Benson, M D Martin, and A F Cardenas, Remotely-Sensed Geophysical Databases Experience and Imphcauons for Generahzed DBMS, Procs of ACM-SIGMOD (San Jose, CA, May 1983) pp 146-160
22. LOHM 84 G M Lohman, D Darnels, L M Haas, R Ktstler, P G Sehnger, OpttmlTatton of Nested Queries m a Dmtnbuted Relauonal Database, Procs of the Tenth lntematzonal Conf on Very Large Data Bases (Singapore), Morgan Kaufmann Publishers (Los Altos, CA, 1984) pp 403-415 Also available as IBM Research Report RJ4260, San Jose, CA, Aprd 1984
23. LOHM 85 G M Lohman, C Mohan, L M Haas, B G Lmdsay, P G Sehnger, P F Wdms, and D Darnels, Query Processing in R*, Query Processing m Database Systems, Sprmger-Verlag (Kam, Batory, & Remer (eds), 1985) pp 31-47 Also available as IBM Research Report RJ4272, San Jose, CA, April 1984
24. MACK 86 L F Mackert and G M Lohman, R* Optun~er Valldat~on and Performance Evaluauon for Distributed Queries, Procs of the Ts~lfth Internatronal Conference on Very Large Data Bases (Kyoto) Morgan Kaufmmm Publishers (Los Altos, CA, August 1986) pp 149-159 Also avadable as IBM Research Report RJS050, San Jose, CA, Aprd 1986
25. MORR 86 K Morns, J D Ullman, and A Van Gelder, Design Overvaew of the NAIL) System, Report No STAN- CS-86-1108 Stanford Umversaty (Stanford, CA, May 1986)
26. ROSE 87 A Rosenthal and P Helman, Understanding and Extending Transformation-Based OpDm~Ters, IEEE Database Engineering 10,4 (Nov 1987)
27. SCHW 86 P M Sehwarz, W Challg, J C Freytag, G M Lohman, J McPherson, C Mohan, and H Ptrahesh, Extenslbthty m the Starburst Database System, Procs of the Internatwnal Workshop on ObJect-Oriented Database Systems (Asdomar, CA), IEEE (Sept 1986)
28. SELI 79 P G Selmger, M M Astrahan, D D Chamberhn, R A Lone, and T G Pnce, Access Path Selection m a Relatmnal Database Management System Procs of ACM-SIGMOD (May 1979) pp 23-34
29. STON 86 M Stonebraker and L Rowe, The Design of Postgres Procs of ACM-SIGMOD (May 1986) pp 340-~'~
30. ULLM 85 J D Ullman, Implementation of Logical Quer~ Languages for Databases, A CM Trans on Databa.~e S) tents 10,3 (September 1985) pp 289-321
31. VALD 87 P Valdunez, Join Inchces, ACM Trans on Datat~zse Systems 12,2 (June 1987) pp 219-246
32. WONG 76 E Wong and K Yousseh, Decomposaton ~ l Strategy for Query Processing, A CM Trans on Database Systems 1,3 (Sept 1976) pp 223-241
33. WONG 83 E Wong and R Katz, Distributing a Database for Parallehsm, Procs of ACM-SIGMOD (San Jose CA May 1983) pp 23-29

Index Terms

• Information systems

  • Data management systems

    • Database management system engines

      • Database query processing

  • Information retrieval

    • Retrieval tasks and goals

      • Clustering and classification

  • Information systems applications

    • Data mining

      • Clustering

• Theory of computation

  • Formal languages and automata theory

    • Grammars and context-free languages

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)