Implementation of magic-sets in a relational database system
- 24 May 1994
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 23 (2) , 103-114
- https://doi.org/10.1145/191843.191860
Abstract
We describe the implementation of the magic-sets transformation in the Starburst extensible relational database system. To our knowledge this is the first implementation of the magic-sets transformation in a relational database system. The Starburst implementation has many novel features that make our implementation especially interesting to database practitioners (in addition to database researchers). (1) We use a cost-based heuristic for determining join orders (sips) before applying magic. (2) We push all equality and non-equality predicates using magic, replacing traditional predicate pushdown optimizations. (3) We apply magic to full SQL with duplicates, aggregation, null values, and subqueries. (4) We integrate magic with other relational optimization techniques. (5) The implementation is extensible.Our implementation demonstrates the feasibility of the magic-sets transformation for commercial relational systems, and provides a mechanism to implement magic as an integral part of a new database system, or as an add-on to an existing database system.Keywords
This publication has 12 references indexed in Scilit:
- Design and implementation of the glue-nail database systemPublished by Association for Computing Machinery (ACM) ,1993
- Magic-sets transformation in nonrecursive systemsPublished by Association for Computing Machinery (ACM) ,1992
- On the power of magicThe Journal of Logic Programming, 1991
- Magic is relevantPublished by Association for Computing Machinery (ACM) ,1990
- Magic conditionsPublished by Association for Computing Machinery (ACM) ,1990
- Starburst mid-flight: as the dust clears (database project)IEEE Transactions on Knowledge and Data Engineering, 1990
- Grammar-like functional rules for representing query optimization alternativesPublished by Association for Computing Machinery (ACM) ,1988
- Optimization of nested SQL queries revisitedPublished by Association for Computing Machinery (ACM) ,1987
- Magic sets and other strange ways to implement logic programs (extended abstract)Published by Association for Computing Machinery (ACM) ,1985
- On optimizing an SQL-like nested queryACM Transactions on Database Systems, 1982