DBScholar

Back to papers

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)

Paper ID
2966
Venue
SIGMOD
Year
1996
Pagerank
0.00012494928
Overall Rank
1,037 | 92.89%
DOI
10.1145/233269.233360

Incoming Non-self Citations Over Time

Authors

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.

Rank Citing Paper Year Venue Pagerank
9 Online Aggregation 1997 SIGMOD 0.00077458002
290 An Overview of Query Optimization in Relational Systems 1998 PODS 0.0002227038
801 Query Execution Techniques for Caching Expensive Methods 1996 SIGMOD 0.00013909408
851 Query Optimization in the Presence of Limited Access Patterns 1999 SIGMOD 0.00013611183
910 Cosette: An Automated Prover for SQL 2017 CIDR 0.00013285905
1,829 Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries 2018 VLDB 9.6671311e-05
1,979 Scalable Join Processing on Very Large RDF Graphs 2009 SIGMOD 9.3621296e-05
1,982 WeTune: Automatic Discovery and Verification of Query Rewrite Rules 2022 SIGMOD 9.3573897e-05
2,627 The Complexity of Transformation-Based Join Enumeration 1997 VLDB 8.3284491e-05
3,035 Instance-Optimized Data Layouts for Cloud Analytics Workloads 2021 SIGMOD 7.8297746e-05
3,137 Pushing Data-Induced Predicates Through Joins in Big-Data Clusters 2020 VLDB 7.7204167e-05
3,172 Demonstration of the Cosette Automated SQL Prover 2017 SIGMOD 7.6679093e-05
3,571 Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads 2017 VLDB 7.2991953e-05
3,928 Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database 1999 VLDB 7.0115196e-05
4,363 GenRewrite: Query Rewriting via Large Language Models 2026 SIGMOD 6.7423909e-05
4,435 Filtering with Approximate Predicates 1998 VLDB 6.7078883e-05
4,849 Bitvector-aware Query Optimization for Decision Support Queries 2020 SIGMOD 6.4803828e-05
6,031 Sia: Optimizing Queries using Learned Predicates 2021 SIGMOD 6.0007422e-05
7,079 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 5.7090732e-05
7,117 Changing the Rules: Transformations for Rule-Based Optimizers* 1998 SIGMOD 5.6976091e-05
7,787 A Practical Approach to Groupjoin and Nested Aggregates 2021 VLDB 5.5449593e-05
7,870 Optimizing Iceberg Queries with Complex Joins 2017 SIGMOD 5.5272726e-05
8,115 Scaling a Declarative Cluster Manager Architecture with Query Optimization Techniques 2023 VLDB 5.4842672e-05
8,413 Conditional Cuckoo Filters 2021 SIGMOD 5.4306049e-05
8,423 Cracking SQL Barriers: An LLM-based Dialect Translation System 2025 SIGMOD 5.4275169e-05
8,849 ByteCard: Enhancing ByteDance’s Data Warehouse with Learned Cardinality Estimation 2024 SIGMOD 5.3577504e-05
10,690 Dynamic Pruning for Recursive Joins 2025 SIGMOD 5.093636e-05
11,234 Window Function Expression: Let the Self-join Enter 2024 VLDB 5.093636e-05
11,466 Anser: Adaptive Information Sharing Framework of AnalyticDB 2023 VLDB 5.093636e-05
12,577 Optimization of Multi-Domain Queries on the Web 2008 VLDB 5.093636e-05
12,727 A Nested Relational Approach to Processing SQL Subqueries 2005 SIGMOD 5.093636e-05
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.0024089429
16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.00060089598
143 Optimization of Nonrecursive Queries 1986 VLDB 0.0002959213
434 Query Optimization for Parallel Execution 1992 SIGMOD 0.00018531826
770 Parametric Query Optimization 1992 VLDB 0.00014166811
1,095 An Extended Relational Algebra with Control Over Duplicate Elimination 1982 PODS 0.00012207515
1,410 Magic is Relevant 1990 SIGMOD 0.00010853223
3,650 Implementation of Magic-sets in a Relational Database System 1994 SIGMOD 7.2249961e-05
8,827 Compiling Query Constraints 1994 PODS 5.3615981e-05
Previous Page 1 / 1 Next

Semantically Similar Papers