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.00030395767
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.00047373961
112 TelegraphCQ: Continuous Dataflow Processing for an Uncertain World 2003 CIDR 0.00032445088
200 Continuously Adaptive Continuous Queries over Streams 2002 SIGMOD 0.00025444144
390 QPipe: A Simultaneously Pipelined Relational Query Engine 2005 SIGMOD 0.00019265472
568 Extending Query Rewriting Techniques for Fine-Grained Access Control 2004 SIGMOD 0.00016254878
762 Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS 2007 VLDB 0.00014134432
831 Pipelining in Multi-Query Optimization 2001 PODS 0.00013583882
923 Materialized View Selection and Maintenance Using Multi-Query Optimization 2001 SIGMOD 0.00013059066
1,132 Efficient Exploitation of Similar Subexpressions for Query Processing 2007 SIGMOD 0.00011893781
1,273 Discovering Queries based on Example Tuples 2014 SIGMOD 0.00011243661
1,286 Resource Sharing in Continuous Sliding-Window Aggregates 2004 VLDB 0.00011188038
1,370 Towards Scalable Dataframe Systems 2020 VLDB 0.00010895207
1,383 On-the-Fly Sharing for Streamed Aggregation 2006 SIGMOD 0.00010842596
1,501 Keyword Search in Databases: The Power of RDBMS 2009 SIGMOD 0.00010456517
1,747 Selecting Subexpressions to Materialize at Datacenter Scale 2018 VLDB 9.7303647e-05
1,788 Plan Selection based on Query Clustering 2002 VLDB 9.6275306e-05
2,086 An Architecture for Recycling Intermediates in a Column-store 2009 SIGMOD 9.0677901e-05
2,225 Shared Workload Optimization 2014 VLDB 8.8062552e-05
2,383 Query Processing for High-Volume XML Message Brokering 2003 VLDB 8.5421855e-05
2,413 S4: Top-k Spreadsheet-Style Search for Query Discovery 2015 SIGMOD 8.5063082e-05
2,441 A Case for Staged Database Systems 2003 CIDR 8.4611767e-05
2,558 Tuple Routing Strategies for Distributed Eddies 2003 VLDB 8.2968348e-05
2,697 On Improving User Response Times in Tableau 2015 SIGMOD 8.1166572e-05
2,772 Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer 2016 VLDB 8.033132e-05
2,787 EVA: A Symbolic Approach to Accelerating Exploratory Video Analytics with Materialized Views 2022 SIGMOD 8.0121053e-05
2,850 Nested Mappings: Schema Mapping Reloaded 2006 VLDB 7.9384121e-05
3,034 Chi: A Scalable and Programmable Control Plane for Distributed Stream Processing Systems 2018 VLDB 7.7301387e-05
3,085 Continuous Sampling for Online Aggregation Over Multiple Queries 2010 SIGMOD 7.6607519e-05
3,215 Efficient and Provable Multi-Query Optimization 2017 PODS 7.5233633e-05
3,362 Exact Cardinality Query Optimization for Optimizer Testing 2009 VLDB 7.3719912e-05
3,410 Scalable Pattern Sharing on Event Streams 2016 SIGMOD 7.322416e-05
3,505 Fast Queries Over Heterogeneous Data Through Engine Customization 2016 VLDB 7.2474175e-05
3,544 Computation Reuse in Analytics Job Service at Microsoft 2018 SIGMOD 7.2108612e-05
3,590 Scalable Multi-Query Optimization for Exploratory Queries over Federated Scientific Databases 2008 VLDB 7.1833385e-05
3,597 Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? 2017 SIGMOD 7.1759026e-05
3,996 An Approach to Optimize Data Processing in Business Processes 2007 VLDB 6.8633275e-05
4,007 Automated Generation of Materialized Views in Oracle 2020 VLDB 6.8561069e-05
4,024 Real-Time Multi-Pattern Detection over Event Streams 2019 SIGMOD 6.8444194e-05
4,109 Smurf: Self-Service String Matching Using Random Forests 2019 VLDB 6.7994518e-05
4,214 Optimizing I/O for Big Array Analytics 2012 VLDB 6.7268411e-05
4,334 LIMA: Fine-grained Lineage Tracing and Reuse in Machine Learning Systems 2021 SIGMOD 6.6537801e-05
4,393 Sharing Data and Work Across Concurrent Analytical Queries 2013 VLDB 6.618354e-05
4,579 To Share or Not to Share? 2007 VLDB 6.5205268e-05
4,834 ReCache: Reactive Caching for Fast Analytics over Heterogeneous Data 2018 VLDB 6.3865472e-05
5,340 Supporting Our AI Overlords: Redesigning Data Systems to be Agent-First 2026 CIDR 6.1719029e-05
5,583 Efficient Computation of Multiple Group By Queries 2005 SIGMOD 6.0739524e-05
5,663 Enabling Incremental Query Re-Optimization 2016 SIGMOD 6.0448133e-05
5,776 Lemo: A Cache-Enhanced Learned Optimizer for Concurrent Queries 2023 SIGMOD 5.9957692e-05
5,837 PolicyReplay: Misconfiguration-Response Queries for Data Breach Reporting 2010 VLDB 5.973056e-05
5,847 Graph-Aware, Workload-Adaptive SPARQL Query Caching 2015 SIGMOD 5.9701747e-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.0002928095
155 Common Expression Analysis in Database Applications 1982 SIGMOD 0.0002851688
167 Query Transformation for PSJ-queries 1987 VLDB 0.00027190577
745 Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time 1996 SIGMOD 0.0001430357
1,127 Simultaneous Optimization and Evaluation of Multiple Dimensional Queries 1998 SIGMOD 0.00011913557
2,115 Reusing Invariants: A New Strategy for Correlated Queries 1998 SIGMOD 9.0119103e-05
2,620 Cost-Based Optimization of Decision Support Queries using Transient-Views 1998 SIGMOD 8.2178624e-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,982 An Incremental Anytime Algorithm for Multi-Objective Query Optimization 2015 SIGMOD
3 5,227 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 995 Analyzing Plan Diagrams of Database Query Optimizers 2005 VLDB
7 1,132 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,215 Efficient and Provable Multi-Query Optimization 2017 PODS