Cost-Based Optimization for Magic: Algebra and Implementation
Summary: Cost-based optimization treats magic sets rewriting as a join-like method, with cost formulas to select the best variant and a bounded search space; implemented in IBM DB2 V2 with practical performance gains. An algebraic model extends multiset relational algebra with a multiset theta-semi-join operator, defining search space and equivalence rules to enable a rule-based optimizer for non-recursive SQL. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Praveen Seshadri (University of Wisconsin)
- 2. Joseph M. Hellerstein (University of California Berkeley)
- 3. Hamid Pirahesh (IBM)
- 4. T. Y. Cliff Leung (IBM)
- 5. Raghu Ramakrishnan (University of Wisconsin)
- 6. Divesh Srivastava (AT&T)
- 7. Peter J. Stuckey (University of Melbourne)
- 8. S. Sudarshan (Indian Institute of Technology Mumbai)
BibTeX Citation
@inproceedings{seshadri_sigmod96,
title = {{Cost-Based Optimization for Magic: Algebra and Implementation}},
author = {Seshadri, Praveen and Hellerstein, Joseph M. and Pirahesh, Hamid and Leung, T. Y. Cliff and Ramakrishnan, Raghu and Srivastava, Divesh and Stuckey, Peter J. and Sudarshan, S.},
series = {{SIGMOD} '96},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/233269.233360},
url = {https://dl.acm.org/doi/10.1145/233269.233360},
year = {1996}
}
Incoming Citations (Sorted by Pagerank)
Showing 31 of 31 citing papers.
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1 | Access Path Selection in a Relational Database Management System | 1979 | SIGMOD | 0.0023947656 |
| 18 | MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) | 1986 | PODS | 0.00059023577 |
| 143 | Optimization of Nonrecursive Queries | 1986 | VLDB | 0.00029179719 |
| 446 | Query Optimization for Parallel Execution | 1992 | SIGMOD | 0.00018174972 |
| 792 | Parametric Query Optimization | 1992 | VLDB | 0.00013942753 |
| 1,113 | An Extended Relational Algebra with Control Over Duplicate Elimination | 1982 | PODS | 0.00011971883 |
| 1,438 | Magic is Relevant | 1990 | SIGMOD | 0.00010648031 |
| 3,707 | Implementation of Magic-sets in a Relational Database System | 1994 | SIGMOD | 7.0820673e-05 |
| 8,995 | Compiling Query Constraints | 1994 | PODS | 5.2414297e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 143 | Optimization of Nonrecursive Queries | 1986 | VLDB |
| 2 | 10,508 | Succinct Structure Representations for Efficient Query Optimization | 2026 | SIGMOD |
| 3 | 3,364 | Magic Conditions | 1990 | PODS |
| 4 | 1,979 | Efficient Evaluation of Right-, Left-, and Multi-Linear Rules | 1989 | SIGMOD |
| 5 | 531 | The Magic of Duplicates and Aggregates | 1990 | VLDB |
| 6 | 18 | MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) | 1986 | PODS |
| 7 | 7,225 | Adding Magic to an Optimising Datalog Compiler | 2008 | SIGMOD |
| 8 | 7,278 | Magic-sets Transformation in Nonrecursive Systems | 1992 | PODS |
| 9 | 3,707 | Implementation of Magic-sets in a Relational Database System | 1994 | SIGMOD |
| 10 | 1,438 | Magic is Relevant | 1990 | SIGMOD |