Database Paper Browser

Back to papers

Efficient and Extensible Algorithms for Multi Query Optimization

Summary: Proposes practical multi-query optimization through three cost-based heuristics (Volcano-SH, Volcano-RU, greedy) to exploit shared subexpressions across queries. Demonstrates significant plan-cost reductions with modest optimizer overhead and easy integration, validated on TPC-D workloads. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
3190
Venue
SIGMOD
Year
2000
Pagerank
0.00037637319
Overall Rank
179 | 98.76%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 87 citing papers.

Rank Citing Paper Year Venue Pagerank
53 DISCOVER: Keyword Search in Relational Databases 2002 VLDB 0.00065993143
143 TelegraphCQ: Continuous Dataflow Processing for an Uncertain World 2003 CIDR 0.00041688468
244 Continuously Adaptive Continuous Queries over Streams 2002 SIGMOD 0.00031037999
515 QPipe: A Simultaneously Pipelined Relational Query Engine 2005 SIGMOD 0.00021209491
607 Extending Query Rewriting Techniques for Fine-Grained Access Control 2004 SIGMOD 0.00019248482
977 Pipelining in Multi-Query Optimization 2001 PODS 0.000148774
1,027 Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS 2007 VLDB 0.0001458537
1,110 Materialized View Selection and Maintenance Using Multi-Query Optimization 2001 SIGMOD 0.00013902997
1,427 Towards Scalable Dataframe Systems 2020 VLDB 0.00012033503
1,475 Efficient Exploitation of Similar Subexpressions for Query Processing 2007 SIGMOD 0.00011765071
1,502 Discovering Queries based on Example Tuples 2014 SIGMOD 0.00011614522
1,557 Resource Sharing in Continuous Sliding-Window Aggregates 2004 VLDB 0.00011381807
1,564 Keyword Search in Databases: The Power of RDBMS 2009 SIGMOD 0.00011340407
1,791 On-the-Fly Sharing for Streamed Aggregation 2006 SIGMOD 0.0001052731
1,921 Selecting Subexpressions to Materialize at Datacenter Scale 2018 VLDB 0.00010085899
1,961 Plan Selection based on Query Clustering 2002 VLDB 9.9464221e-05
2,318 On Improving User Response Times in Tableau 2015 SIGMOD 9.04679e-05
2,329 A Case for Staged Database Systems 2003 CIDR 9.0237899e-05
2,514 Query Processing for High-Volume XML Message Brokering 2003 VLDB 8.6121924e-05
2,577 S4: Top-k Spreadsheet-Style Search for Query Discovery 2015 SIGMOD 8.5066436e-05
2,695 An Architecture for Recycling Intermediates in a Column-store 2009 SIGMOD 8.2827669e-05
2,818 Tuple Routing Strategies for Distributed Eddies 2003 VLDB 8.0673424e-05
2,909 Nested Mappings: Schema Mapping Reloaded 2006 VLDB 7.9282234e-05
2,928 Shared Workload Optimization 2014 VLDB 7.881485e-05
3,314 Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer 2016 VLDB 7.2318547e-05
3,505 Efficient and Provable Multi-Query Optimization 2017 PODS 7.0304901e-05
3,551 Chi: A Scalable and Programmable Control Plane for Distributed Stream Processing Systems 2018 VLDB 6.9776252e-05
3,596 Continuous Sampling for Online Aggregation Over Multiple Queries 2010 SIGMOD 6.9342283e-05
3,610 EVA: A Symbolic Approach to Accelerating Exploratory Video Analytics with Materialized Views 2022 SIGMOD 6.919859e-05
3,677 An Approach to Optimize Data Processing in Business Processes 2007 VLDB 6.8494152e-05
3,943 Exact Cardinality Query Optimization for Optimizer Testing 2009 VLDB 6.6067351e-05
4,012 Scalable Pattern Sharing on Event Streams 2016 SIGMOD 6.5338454e-05
4,160 Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? 2017 SIGMOD 6.3886736e-05
4,171 Computation Reuse in Analytics Job Service at Microsoft 2018 SIGMOD 6.3800823e-05
4,254 Optimizing I/O for Big Array Analytics 2012 VLDB 6.3084831e-05
4,319 Fast Queries Over Heterogeneous Data Through Engine Customization 2016 VLDB 6.2823814e-05
4,397 Smurf: Self-Service String Matching Using Random Forests 2019 VLDB 6.2142485e-05
4,456 Real-Time Multi-Pattern Detection over Event Streams 2019 SIGMOD 6.1644341e-05
4,621 Automated Generation of Materialized Views in Oracle 2020 VLDB 6.036749e-05
4,674 Scalable Multi-Query Optimization for Exploratory Queries over Federated Scientific Databases 2008 VLDB 6.0000019e-05
4,677 To Share or Not to Share? 2007 VLDB 5.9988869e-05
4,779 LIMA: Fine-grained Lineage Tracing and Reuse in Machine Learning Systems 2021 SIGMOD 5.9259373e-05
4,964 Sharing Data and Work Across Concurrent Analytical Queries 2013 VLDB 5.7974073e-05
5,304 ReCache: Reactive Caching for Fast Analytics over Heterogeneous Data 2018 VLDB 5.5738777e-05
5,652 PolicyReplay: Misconfiguration-Response Queries for Data Breach Reporting 2010 VLDB 5.3885559e-05
5,737 Enabling Incremental Query Re-Optimization 2016 SIGMOD 5.3459609e-05
5,742 Efficient Computation of Multiple Group By Queries 2005 SIGMOD 5.3432178e-05
5,778 Graph-Aware, Workload-Adaptive SPARQL Query Caching 2015 SIGMOD 5.3274776e-05
5,846 Efficient Detection of Empty-Result Queries 2006 VLDB 5.3052255e-05
6,106 QoX-Driven ETL Design: Reducing the Cost of ETL Consulting Engagements 2009 SIGMOD 5.2040193e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
89 Common Expression Analysis in Database Applications 1982 SIGMOD 0.00052299473
138 Query Transformation for PSJ-queries 1987 VLDB 0.00042322097
153 Relational Databases for Querying XML Documents: Limitations and Opportunities 1999 VLDB 0.00040759404
775 Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time 1996 SIGMOD 0.00016775051
825 Simultaneous Optimization and Evaluation of Multiple Dimensional Queries 1998 SIGMOD 0.00016171735
1,930 Reusing Invariants: A New Strategy for Correlated Queries 1998 SIGMOD 0.00010052743
2,290 Cost-Based Optimization of Decision Support Queries using Transient-Views 1998 SIGMOD 9.0918901e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,990 AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions 2003 VLDB 9.8491124e-05
5,073 An Incremental Anytime Algorithm for Multi-Objective Query Optimization 2015 SIGMOD 5.7118738e-05
4,876 Approximation Schemes for Many-Objective Query Optimization 2014 SIGMOD 5.8544467e-05
406 Global Query Optimization 1986 SIGMOD 0.00023989944
977 Pipelining in Multi-Query Optimization 2001 PODS 0.000148774
1,064 Analyzing Plan Diagrams of Database Query Optimizers 2005 VLDB 0.00014348262
1,475 Efficient Exploitation of Similar Subexpressions for Query Processing 2007 SIGMOD 0.00011765071
1,287 Multiple Query Processing in Deductive Databases using Query Graphs 1986 VLDB 0.00012798692
2,652 Multi-Objective Parametric Query Optimization 2015 VLDB 8.3662031e-05
3,505 Efficient and Provable Multi-Query Optimization 2017 PODS 7.0304901e-05