Implementation of magic-sets in a relational database system
Authors:
Open Access
- 24 May 1994
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 23 (2) , 103-114
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 system1993
- Magic-sets transformation in nonrecursive systems1992
- On the power of magicThe Journal of Logic Programming, 1991
- Magic is relevant1990
- Magic conditions1990
- 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 alternatives1988
- Optimization of nested SQL queries revisited1987
- Magic sets and other strange ways to implement logic programs (extended abstract)1985
- On optimizing an SQL-like nested queryACM Transactions on Database Systems, 1982