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
h603ee9ee12d092fc
Venue
SIGMOD
Year
1996
Pagerank
0.00012401489
Overall Rank
1,032 | 93.07%
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.00076195956
272 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022509573
790 Cosette: An Automated Prover for SQL 2017 CIDR 0.00013976438
821 Query Execution Techniques for Caching Expensive Methods 1996 SIGMOD 0.00013660347
869 Query Optimization in the Presence of Limited Access Patterns 1999 SIGMOD 0.00013348278
1,680 Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries 2018 VLDB 9.9031411e-05
1,893 WeTune: Automatic Discovery and Verification of Query Rewrite Rules 2022 SIGMOD 9.4126198e-05
2,026 Scalable Join Processing on Very Large RDF Graphs 2009 SIGMOD 9.1624074e-05
2,660 The Complexity of Transformation-Based Join Enumeration 1997 VLDB 8.1611913e-05
2,765 Instance-Optimized Data Layouts for Cloud Analytics Workloads 2021 SIGMOD 8.0439015e-05
3,073 Pushing Data-Induced Predicates Through Joins in Big-Data Clusters 2020 VLDB 7.6777283e-05
3,202 Demonstration of the Cosette Automated SQL Prover 2017 SIGMOD 7.5411821e-05
3,336 GenRewrite: Query Rewriting via Large Language Models 2026 SIGMOD 7.4137763e-05
3,592 Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads 2017 VLDB 7.1835842e-05
3,957 Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database 1999 VLDB 6.8991437e-05
4,229 Cracking SQL Barriers: An LLM-based Dialect Translation System 2025 SIGMOD 6.7165534e-05
4,391 Bitvector-aware Query Optimization for Decision Support Queries 2020 SIGMOD 6.6214093e-05
4,481 Filtering with Approximate Predicates 1998 VLDB 6.5807146e-05
6,147 Sia: Optimizing Queries using Learned Predicates 2021 SIGMOD 5.8710365e-05
7,225 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 5.5810777e-05
7,233 Changing the Rules: Transformations for Rule-Based Optimizers* 1998 SIGMOD 5.5792253e-05
7,907 A Practical Approach to Groupjoin and Nested Aggregates 2021 VLDB 5.4287568e-05
8,023 Optimizing Iceberg Queries with Complex Joins 2017 SIGMOD 5.4054487e-05
8,213 Scaling a Declarative Cluster Manager Architecture with Query Optimization Techniques 2023 VLDB 5.3770961e-05
8,580 Conditional Cuckoo Filters 2021 SIGMOD 5.3100462e-05
9,012 ByteCard: Enhancing ByteDance’s Data Warehouse with Learned Cardinality Estimation 2024 SIGMOD 5.2375369e-05
9,652 Window Function Expression: Let the Self-join Enter 2024 VLDB 5.1453267e-05
11,126 Dynamic Pruning for Recursive Joins 2025 SIGMOD 4.9793485e-05
11,777 Anser: Adaptive Information Sharing Framework of AnalyticDB 2023 VLDB 4.9793485e-05
12,867 Optimization of Multi-Domain Queries on the Web 2008 VLDB 4.9793485e-05
13,017 A Nested Relational Approach to Processing SQL Subqueries 2005 SIGMOD 4.9793485e-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.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