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
2905
Venue
SIGMOD
Year
1996
Pagerank
0.00012629432
Overall Rank
1,313 | 90.88%
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.0010813443
454 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022796106
699 Query Execution Techniques for Caching Expensive Methods 1996 SIGMOD 0.0001794078
867 Query Optimization in the Presence of Limited Access Patterns 1999 SIGMOD 0.00015757737
1,056 Cosette: An Automated Prover for SQL 2017 CIDR 0.00014391317
2,097 Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries 2018 VLDB 9.5439744e-05
2,407 Scalable Join Processing on Very Large RDF Graphs 2009 SIGMOD 8.8702781e-05
2,595 WeTune: Automatic Discovery and Verification of Query Rewrite Rules 2022 SIGMOD 8.4725961e-05
2,878 The Complexity of Transformation-Based Join Enumeration 1997 VLDB 7.9694937e-05
3,430 Demonstration of the Cosette Automated SQL Prover 2017 SIGMOD 7.0985442e-05
3,777 Instance-Optimized Data Layouts for Cloud Analytics Workloads 2021 SIGMOD 6.7713324e-05
3,923 Pushing Data-Induced Predicates Through Joins in Big-Data Clusters 2020 VLDB 6.6232068e-05
4,272 Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads 2017 VLDB 6.2933353e-05
4,403 Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database 1999 VLDB 6.2054188e-05
4,405 Filtering with Approximate Predicates 1998 VLDB 6.2048285e-05
5,001 GenRewrite: Query Rewriting via Large Language Models 2026 SIGMOD 5.7634197e-05
5,195 Bitvector-aware Query Optimization for Decision Support Queries 2020 SIGMOD 5.6314278e-05
6,955 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 4.8812945e-05
7,015 Changing the Rules: Transformations for Rule-Based Optimizers* 1998 SIGMOD 4.8563411e-05
7,278 Sia: Optimizing Queries using Learned Predicates 2021 SIGMOD 4.7720613e-05
7,807 Scaling a Declarative Cluster Manager Architecture with Query Optimization Techniques 2023 VLDB 4.6417687e-05
8,070 Optimizing Iceberg Queries with Complex Joins 2017 SIGMOD 4.5893281e-05
8,499 Conditional Cuckoo Filters 2021 SIGMOD 4.4929219e-05
8,676 A Practical Approach to Groupjoin and Nested Aggregates 2021 VLDB 4.4652082e-05
8,834 ByteCard: Enhancing ByteDance’s Data Warehouse with Learned Cardinality Estimation 2024 SIGMOD 4.4351469e-05
10,415 Dynamic Pruning for Recursive Joins 2025 SIGMOD 4.1905499e-05
10,485 Cracking SQL Barriers: An LLM-based Dialect Translation System 2025 SIGMOD 4.1905499e-05
11,026 Window Function Expression: Let the Self-join Enter 2024 VLDB 4.1905499e-05
11,269 Anser: Adaptive Information Sharing Framework of AnalyticDB 2023 VLDB 4.1905499e-05
12,392 Optimization of Multi-Domain Queries on the Web 2008 VLDB 4.1905499e-05
12,543 A Nested Relational Approach to Processing SQL Subqueries 2005 SIGMOD 4.1905499e-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.0040465394
16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.00099936325
144 Optimization of Nonrecursive Queries 1986 VLDB 0.00041430126
439 Query Optimization for Parallel Execution 1992 SIGMOD 0.00023183237
835 An Extended Relational Algebra with Control Over Duplicate Elimination 1982 PODS 0.00016081611
870 Parametric Query Optimization 1992 VLDB 0.00015709369
1,423 Magic is Relevant 1990 SIGMOD 0.00012047765
4,198 Implementation of Magic-sets in a Relational Database System 1994 SIGMOD 6.361961e-05
8,012 Compiling Query Constraints 1994 PODS 4.6021663e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
592 A Rule-Based View of Query Optimization 1987 SIGMOD 0.0001953183
144 Optimization of Nonrecursive Queries 1986 VLDB 0.00041430126
3,284 Magic Conditions 1990 PODS 7.2738706e-05
2,048 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.689916e-05
448 The Magic of Duplicates and Aggregates 1990 VLDB 0.00022922417
16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.00099936325
6,955 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 4.8812945e-05
7,069 Magic-sets Transformation in Nonrecursive Systems 1992 PODS 4.8380576e-05
4,198 Implementation of Magic-sets in a Relational Database System 1994 SIGMOD 6.361961e-05
1,423 Magic is Relevant 1990 SIGMOD 0.00012047765