Database Paper Browser

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
2904
Venue
SIGMOD
Year
1996
Pagerank
0.0001263831
Overall Rank
1,313 | 90.87%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank Citing Paper Year Venue Pagerank
14 Online Aggregation 1997 SIGMOD 0.0010801504
454 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022734812
703 Query Execution Techniques for Caching Expensive Methods 1996 SIGMOD 0.00017916705
870 Query Optimization in the Presence of Limited Access Patterns 1999 SIGMOD 0.00015771912
1,057 Cosette: An Automated Prover for SQL 2017 CIDR 0.0001439886
2,099 Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries 2018 VLDB 9.5479391e-05
2,410 Scalable Join Processing on Very Large RDF Graphs 2009 SIGMOD 8.8773796e-05
2,596 WeTune: Automatic Discovery and Verification of Query Rewrite Rules 2022 SIGMOD 8.4729982e-05
2,869 The Complexity of Transformation-Based Join Enumeration 1997 VLDB 7.9808408e-05
3,432 Demonstration of the Cosette Automated SQL Prover 2017 SIGMOD 7.1008151e-05
3,779 Instance-Optimized Data Layouts for Cloud Analytics Workloads 2021 SIGMOD 6.7747205e-05
3,922 Pushing Data-Induced Predicates Through Joins in Big-Data Clusters 2020 VLDB 6.6291079e-05
4,276 Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads 2017 VLDB 6.2976602e-05
4,407 Filtering with Approximate Predicates 1998 VLDB 6.2133426e-05
4,408 Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database 1999 VLDB 6.2109612e-05
5,023 GenRewrite: Query Rewriting via Large Language Models 2026 SIGMOD 5.75363e-05
5,194 Bitvector-aware Query Optimization for Decision Support Queries 2020 SIGMOD 5.6368209e-05
6,957 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 4.8859842e-05
7,015 Changing the Rules: Transformations for Rule-Based Optimizers* 1998 SIGMOD 4.8609507e-05
7,283 Sia: Optimizing Queries using Learned Predicates 2021 SIGMOD 4.7764688e-05
7,805 Scaling a Declarative Cluster Manager Architecture with Query Optimization Techniques 2023 VLDB 4.6462265e-05
8,066 Optimizing Iceberg Queries with Complex Joins 2017 SIGMOD 4.5937212e-05
8,502 Conditional Cuckoo Filters 2021 SIGMOD 4.4972336e-05
8,680 A Practical Approach to Groupjoin and Nested Aggregates 2021 VLDB 4.4694927e-05
8,834 ByteCard: Enhancing ByteDance’s Data Warehouse with Learned Cardinality Estimation 2024 SIGMOD 4.4394021e-05
10,404 Dynamic Pruning for Recursive Joins 2025 SIGMOD 4.1945683e-05
10,475 Cracking SQL Barriers: An LLM-based Dialect Translation System 2025 SIGMOD 4.1945683e-05
11,023 Window Function Expression: Let the Self-join Enter 2024 VLDB 4.1945683e-05
11,267 Anser: Adaptive Information Sharing Framework of AnalyticDB 2023 VLDB 4.1945683e-05
12,384 Optimization of Multi-Domain Queries on the Web 2008 VLDB 4.1945683e-05
12,534 A Nested Relational Approach to Processing SQL Subqueries 2005 SIGMOD 4.1945683e-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.0040449103
16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.0010066783
143 Optimization of Nonrecursive Queries 1986 VLDB 0.00041510555
438 Query Optimization for Parallel Execution 1992 SIGMOD 0.00023199245
837 An Extended Relational Algebra with Control Over Duplicate Elimination 1982 PODS 0.00016097758
876 Parametric Query Optimization 1992 VLDB 0.00015716096
1,423 Magic is Relevant 1990 SIGMOD 0.00012054867
4,199 Implementation of Magic-sets in a Relational Database System 1994 SIGMOD 6.3662839e-05
8,010 Compiling Query Constraints 1994 PODS 4.6065603e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
594 A Rule-Based View of Query Optimization 1987 SIGMOD 0.00019534507
143 Optimization of Nonrecursive Queries 1986 VLDB 0.00041510555
3,283 Magic Conditions 1990 PODS 7.280826e-05
2,042 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.699257e-05
445 The Magic of Duplicates and Aggregates 1990 VLDB 0.0002294367
16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.0010066783
6,957 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 4.8859842e-05
7,075 Magic-sets Transformation in Nonrecursive Systems 1992 PODS 4.842703e-05
4,199 Implementation of Magic-sets in a Relational Database System 1994 SIGMOD 6.3662839e-05
1,423 Magic is Relevant 1990 SIGMOD 0.00012054867