Implementation of magic-sets in a relational database system

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 1994. (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. © 1994, ACM. All rights reserved.