An Efficient Framework for Order Optimization

Neumann, Thomas ; Moerkotte, Guido

TR-03-011.pdf - Veröffentlichte Version

Download (206kB)

URN: urn:nbn:de:bsz:180-madoc-7362
Dokumenttyp: Arbeitspapier
Erscheinungsjahr: 2003
Sprache der Veröffentlichung: Englisch
Einrichtung: Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Sonstige - Fakultät für Mathematik und Informatik
MADOC-Schriftenreihe: Veröffentlichungen der Fakultät für Mathematik und Informatik > Institut für Informatik > Technical Reports
Fachgebiet: 004 Informatik
Normierte Schlagwörter (SWD): relationale Datenbank , Abfrageverarbeitung
Freie Schlagwörter (Englisch): databases , order optimization , plan generation
Abstract: Since the introduction of cost-based query optimization, the performance-critical role of interesting orders has been recognized. Some algebraic operators change interesting orders (e.g. sort and select), while others exploit interesting orders (e.g. merge join). The two operations performed by any query optimizer during plan generation are 1) computing the resulting order given an input order and an algebraic operator and 2) determining the compatibility between a given input order and the required order a given algebraic operator can beneficially exploit. Since these two operations are called millions of times during plan generation, they are highly performance-critical. The third crucial parameter is the space requirement for annotating every plan node with its output order. Lately, a powerful framework for reasoning about orders has been developed, which is based on functional dependencies. Within this framework, the current state-of-the-art algorithms for implementing the above operations both have a lower bound time requirement of Omega(n), where n is the number of functional dependencies involved. Further, the lower bound for the space requirement for every plan node is Omega(n). We improve these bounds by new algorithms with upper time bounds O(1). That is, our algorithms for both operations work in constant time during plan generation, after a one-time preparation step. Further, the upper bound for the space requirement for plan nodes is O(1) for our approach. Besides, our algorithm reduces the search space by detecting and ignoring irrelevant orderings. Experimental results with a full fledged query optimizer show that our approach significantly reduces the total time needed for plan generation. As a corollary of our experiments, it follows that the time spent for order processing is a non-neglectable part of plan generation.
Zusätzliche Informationen:

Das Dokument wird vom Publikationsserver der Universitätsibliothek Mannheim bereitgestellt.

+ Zitationsbeispiel und Export

Neumann, Thomas und Moerkotte, Guido (2003) An Efficient Framework for Order Optimization. [Arbeitspapier]

+ Suche Autoren in

+ Download-Statistik

Downloads im letzten Jahr

Detailierte Angaben

Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail

Actions (login required)

Eintrag anzeigen Eintrag anzeigen