The EXODUS optimizer generator

ABSTRACT

This paper presents the design and an initial performance evaluation of the query optimizer generator designed for the EXODUS extensible database system. Algebraic transformation rules are translated into an executable query optimizer, which transforms query trees and selects methods for executing operations according to cost functions associated with the methods. The search strategy avoids exhaustive search and it modifies itself to take advantage of past experience. Computational results show that an optimizer generated for a relational system produces access plans almost as good as those produced by exhaustive search, with the search time cut to a small fraction.

References

1. ASTR76.M M Astrahan, et al, "System R Relauonal Approach to Database Management," ACM Transacuons on Database Systems, Vol 1(2), pp 97-137, (June 1976)
2. BARR81.A Ban- and E A Felgenbaum, The Handbook of Artificial Intelhgence, Wflham Kaufman, Inc, Los Altos, CA (1981)
3. BOBR83.D G Bobrow and M Stefik, "The LOOPS Manual," m LOOPS Release Notes, XEROX, Palo Alto, CA (1983)
4. CARE85.M J Carey and D J DeWltt, "Extenslble Database Systems," Proceechngs of the Islamorada Workshop, (Feb 1985)
5. CARE86a.M J Carey, D J DeWxtt, J E Rachardson, and E J Shelota, "Object and Fie Management m the EXODUS Extenslble Database System," Proceechngs of 1986 VLDB Conference, pp 91-100 (Aug 1986)
6. CARE86b.M J Carey, D J DeW#tt, D Frank, G Graefe, J E Richardson, E J Shekata, and M Mural#shna, "The ArchRecture of the EXODUS Extens#ble DBMS A Prehmlnary Report," Proceedings of the International Workshop on Object-Oriented Database Systems, (Sep 1986)
7. CLOC81.W Clocksm and C Melllsh, Progranmalng m Prolog, Spnnger-Vedag, New York (1981)
8. COPE84.G Copeland and D Maler, "Makang Smalltalk a Database System," Proceedings of ACM SIGMOD Conference, pp 316-325, (June 1984)
9. DAYA85.U Dayal and J M Srmth, "PROBE A Knowledge-Oriented Database Management System," Proceexhngs of the Islamorada Workshop, (Feb 1985)
10. DEWI86.D J DeWltt, R H Gerber, G Grade, M L Heytens, K B Kumar, and M Mural#shna, "GAMMA - A I-hgh Performance Datattow Database Machine," Proceedings of 1986 VLDB Conference, pp 228-237, (Aug 1986)
11. FORG81.C L Forgy, "OPS5 Reference Manual," Computer Science Techmcal Report 135, Carnegie- Mellon Umverslty, (1981 )
12. FREY85.C F Freytag, "Translating Relauonal Queries into Iteralave Programs," Ph D Thes#s, Harvard UmversRy, (Sep 1985)
13. FREY86a.C F Freytag and N Goodman, "Translaung Relauonal Quenes into Iterattve Programs Using a Program Transformalaon Approach," Proceexhngs of ACM SIGMOD Conference, (June 1986)
14. FREY86b.C F Freytag, "A Rule-Based View of Query Optttmzataon", subtmtted for pubhcauon, (Oct 1986)
15. HANA77.M Z Hananl, "An Opnmal Evaluauon of Boolean Expressions m an Onhne Query System," Commumcatlons of the ACM, Vol 20(5) pp 344- 347, (May 1977)
16. HART68.P E Hart, N J Nflsson, and B Raphael, "A Formal Bas#s for Heunsuc Deterrmnatmn of Mmmmm Path Cost," IEEE Transacuons on SSC, Vol 4, pp 100-107 (1968)
17. JARK84.M Jarke and J Koch, "Query Opnrmzalaon m Database Systems," ACM Computing Surveys, Vol 16(2) pp 111-152, (June 1984)
18. KLUG82.A Klug, "Access Paths m the ABE Stattsttcal Query Faclhty," Procee&ngs of ACM 1982 SIG- MOD Conference, pp 161-173, (June 1982)
19. KLUG82a.A Klug, "Equwalence of Relalaonal Algebra and Relataonal Calculus Query Languages Having Aggregate Funcaons," Journal of the ACM, Vol 29(3), pp 699-717, (July 1982)
20. KOOI80.R P Kool, "The Opmmzataon of Queries m Relauonal Databases," PhD Thes#s, Case Western Reserve UmversRy, (Sept 1980)
21. LYNG86., P Lyngback and W Kent, "A Data Modehng Methodology for the Design and Implementataon of Informataon Systems," Proceedings of the lntematmnal Workshop on Object-Oriented Database Systems, (Sep 1986)
22. MANO86.F Manola and U Dayal, "PDM An Object- Oriented Data Model," Proceedings of the Intemauonal Workshop on ObJect-Oriented Database Systems, (Sep 1986)
23. NGUY82.G T Nguyen, L Ferrat, and H Galy, "A I-hgh- Level User Interface for a Local Network Database System," Prr#eedangs of IEEE Infocom, pp 96-105, (1982)
24. RICH87.J E Rachardson and M J Carey, "Programn-nng Constructs for Database System lmplementauon m EXODUS," Proeeechng of ACM SIGMOD Conference, (1987)
25. ROSE86.A Rosenthal, U Dayal, and D Remer, "Fast Query Opurmzauon over a Large Strategy Space The Pdot Pass Approach," unpubhshed manuscript
26. SELI79.P Cmffiths Sehnger, M M Astrahan, D D Chamberhn, R A Lone, and T G Price, "Access Path Selecuon m a Rclauonal Database Management System," Procee.Atngs of 1979 ACM SIGMOD Conference, (June 1979)
27. SHIP81.D W Slupman, "The Funclaonal Data Model and the Data Language DAPLEX," ACM Transacuons on Database Systems, Vol 6(1), pp 140-173, (Mar 1981)
28. SMIT75.J M Srmth and P Y,T Chang, "OpUmlzmg the Performance of a Relauonal Algebra Database Interface," Communlcauons of the ACM, Vol 18(10), pp 568-579, (1975)
29. STON76.M Stonebraker, E Wrong, P Kreps, and G D Held, "The Design and Implementauon of INGRES," ACM Transacttons on Database Systems, Vol 1(3), pp 189-222, (Sept 1976)
30. STON86.M Stonebraker and L A Rowe, "The Design of POSTGRES," Procer.#ngs of 1986 SIGMOD Conference, pp 340-355, (May 1986)
31. TSUR86.S Tsur and C Zarnolo, "LDL A Logic-Based Data-Language," MCC Techmcal Report, (DB-026- 86)MCC, (Feb 1986)
32. WARR77.D H D Warren, L M Peretra, and F Perelra, "PROLOG - The language and its n'nplementat#on compared with Lisp," Prigs of ACM SIGART-SIGPLAN Symp on AI and Programming Languages, (1977)
33. WONG76.E Wong and K Youssefi, "De#omposmon - A Strategy for Query Processing," ACM Transacuons on Database Systems, Vol 1(3), pp 223-241, (Sept 1976)
34. YOUS79.K Youssefi and E Wong, "Query processing m a relauonal database management system," Proceedrags of 1979 VLDB Conference, pp 409-417, (Oct 1979)
35. ZANI83.C Zamolo, "The Database Language GEM," Proceedings of 1983 ACM SIGMOD Conference, (May 1983)

Index Terms

• Information systems

  • Data management systems

    • Database design and models

  • Information retrieval

    • Information retrieval query processing

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language types