DBScholar

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
hb0c63f7ed81b7bce
Venue
SIGMOD
Year
2000
Pagerank
0.0003040756
Overall Rank
129 | 99.14%
DOI
10.1145/342009.335419

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{roy_sigmod00,
        title = {{Efficient and Extensible Algorithms for Multi Query Optimization}},
        author = {Roy, Prasan and Seshadri, S. and Sudarshan, S. and Bhobe, Siddhesh},
        series = {{SIGMOD} '00},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/342009.335419},
        url = {https://dl.acm.org/doi/10.1145/342009.335419},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 88 citing papers.

Rank Citing Paper Year Venue Pagerank
38 DISCOVER: Keyword Search in Relational Databases 2002 VLDB 0.00047394041
112 TelegraphCQ: Continuous Dataflow Processing for an Uncertain World 2003 CIDR 0.00032459277
200 Continuously Adaptive Continuous Queries over Streams 2002 SIGMOD 0.000254553
389 QPipe: A Simultaneously Pipelined Relational Query Engine 2005 SIGMOD 0.00019269777
568 Extending Query Rewriting Techniques for Fine-Grained Access Control 2004 SIGMOD 0.00016262553
762 Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS 2007 VLDB 0.00014140446
831 Pipelining in Multi-Query Optimization 2001 PODS 0.00013589597
923 Materialized View Selection and Maintenance Using Multi-Query Optimization 2001 SIGMOD 0.00013064753
1,131 Efficient Exploitation of Similar Subexpressions for Query Processing 2007 SIGMOD 0.0001189909
1,272 Discovering Queries based on Example Tuples 2014 SIGMOD 0.00011248674
1,286 Resource Sharing in Continuous Sliding-Window Aggregates 2004 VLDB 0.0001119284
1,369 Towards Scalable Dataframe Systems 2020 VLDB 0.00010899832
1,383 On-the-Fly Sharing for Streamed Aggregation 2006 SIGMOD 0.00010847646
1,501 Keyword Search in Databases: The Power of RDBMS 2009 SIGMOD 0.00010461358
1,745 Selecting Subexpressions to Materialize at Datacenter Scale 2018 VLDB 9.7343818e-05
1,789 Plan Selection based on Query Clustering 2002 VLDB 9.6293635e-05
2,084 An Architecture for Recycling Intermediates in a Column-store 2009 SIGMOD 9.0716512e-05
2,225 Shared Workload Optimization 2014 VLDB 8.8081001e-05
2,381 Query Processing for High-Volume XML Message Brokering 2003 VLDB 8.5462254e-05
2,412 S4: Top-k Spreadsheet-Style Search for Query Discovery 2015 SIGMOD 8.5101348e-05
2,440 A Case for Staged Database Systems 2003 CIDR 8.46509e-05
2,558 Tuple Routing Strategies for Distributed Eddies 2003 VLDB 8.3007355e-05
2,700 On Improving User Response Times in Tableau 2015 SIGMOD 8.1188166e-05
2,771 Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer 2016 VLDB 8.0369366e-05
2,787 EVA: A Symbolic Approach to Accelerating Exploratory Video Analytics with Materialized Views 2022 SIGMOD 8.0158999e-05
2,849 Nested Mappings: Schema Mapping Reloaded 2006 VLDB 7.942171e-05
3,033 Chi: A Scalable and Programmable Control Plane for Distributed Stream Processing Systems 2018 VLDB 7.7337998e-05
3,087 Continuous Sampling for Online Aggregation Over Multiple Queries 2010 SIGMOD 7.6624333e-05
3,214 Efficient and Provable Multi-Query Optimization 2017 PODS 7.5269127e-05
3,367 Exact Cardinality Query Optimization for Optimizer Testing 2009 VLDB 7.3719456e-05
3,410 Scalable Pattern Sharing on Event Streams 2016 SIGMOD 7.3258817e-05
3,505 Fast Queries Over Heterogeneous Data Through Engine Customization 2016 VLDB 7.2508161e-05
3,545 Computation Reuse in Analytics Job Service at Microsoft 2018 SIGMOD 7.2134803e-05
3,589 Scalable Multi-Query Optimization for Exploratory Queries over Federated Scientific Databases 2008 VLDB 7.1867376e-05
3,599 Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? 2017 SIGMOD 7.1773938e-05
3,995 An Approach to Optimize Data Processing in Business Processes 2007 VLDB 6.86657e-05
4,007 Automated Generation of Materialized Views in Oracle 2020 VLDB 6.8592987e-05
4,023 Real-Time Multi-Pattern Detection over Event Streams 2019 SIGMOD 6.8476587e-05
4,107 Smurf: Self-Service String Matching Using Random Forests 2019 VLDB 6.8026037e-05
4,212 Optimizing I/O for Big Array Analytics 2012 VLDB 6.7298655e-05
4,334 LIMA: Fine-grained Lineage Tracing and Reuse in Machine Learning Systems 2021 SIGMOD 6.6569314e-05
4,392 Sharing Data and Work Across Concurrent Analytical Queries 2013 VLDB 6.6213651e-05
4,577 To Share or Not to Share? 2007 VLDB 6.523408e-05
4,832 ReCache: Reactive Caching for Fast Analytics over Heterogeneous Data 2018 VLDB 6.3895407e-05
5,391 Supporting Our AI Overlords: Redesigning Data Systems to be Agent-First 2026 CIDR 6.1504174e-05
5,582 Efficient Computation of Multiple Group By Queries 2005 SIGMOD 6.0768264e-05
5,667 Enabling Incremental Query Re-Optimization 2016 SIGMOD 6.0458446e-05
5,788 Lemo: A Cache-Enhanced Learned Optimizer for Concurrent Queries 2023 SIGMOD 5.9947442e-05
5,835 PolicyReplay: Misconfiguration-Response Queries for Data Breach Reporting 2010 VLDB 5.9758831e-05
5,844 Graph-Aware, Workload-Adaptive SPARQL Query Caching 2015 SIGMOD 5.9730023e-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
141 Relational Databases for Querying XML Documents: Limitations and Opportunities 1999 VLDB 0.00029294114
155 Common Expression Analysis in Database Applications 1982 SIGMOD 0.00028527932
167 Query Transformation for PSJ-queries 1987 VLDB 0.00027190004
744 Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time 1996 SIGMOD 0.00014309622
1,127 Simultaneous Optimization and Evaluation of Multiple Dimensional Queries 1998 SIGMOD 0.00011918964
2,114 Reusing Invariants: A New Strategy for Correlated Queries 1998 SIGMOD 9.0158191e-05
2,619 Cost-Based Optimization of Decision Support Queries using Transient-Views 1998 SIGMOD 8.2215744e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,612 AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions 2003 VLDB
2 4,980 An Incremental Anytime Algorithm for Multi-Objective Query Optimization 2015 SIGMOD
3 5,223 Approximation Schemes for Many-Objective Query Optimization 2014 SIGMOD
4 592 Global Query Optimization 1986 SIGMOD
5 831 Pipelining in Multi-Query Optimization 2001 PODS
6 996 Analyzing Plan Diagrams of Database Query Optimizers 2005 VLDB
7 1,131 Efficient Exploitation of Similar Subexpressions for Query Processing 2007 SIGMOD
8 1,551 Multiple Query Processing in Deductive Databases using Query Graphs 1986 VLDB
9 2,524 Multi-Objective Parametric Query Optimization 2015 VLDB
10 3,214 Efficient and Provable Multi-Query Optimization 2017 PODS