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
3251
Venue
SIGMOD
Year
2000
Pagerank
0.0003072825
Overall Rank
128 | 99.13%
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 87 citing papers.

Rank Citing Paper Year Venue Pagerank
37 DISCOVER: Keyword Search in Relational Databases 2002 VLDB 0.00048017193
111 TelegraphCQ: Continuous Dataflow Processing for an Uncertain World 2003 CIDR 0.00032990214
193 Continuously Adaptive Continuous Queries over Streams 2002 SIGMOD 0.00025964286
383 QPipe: A Simultaneously Pipelined Relational Query Engine 2005 SIGMOD 0.00019520728
552 Extending Query Rewriting Techniques for Fine-Grained Access Control 2004 SIGMOD 0.00016630306
761 Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS 2007 VLDB 0.00014254351
822 Pipelining in Multi-Query Optimization 2001 PODS 0.00013807229
929 Materialized View Selection and Maintenance Using Multi-Query Optimization 2001 SIGMOD 0.00013152103
1,154 Efficient Exploitation of Similar Subexpressions for Query Processing 2007 SIGMOD 0.00011934202
1,262 Discovering Queries based on Example Tuples 2014 SIGMOD 0.00011427456
1,263 Resource Sharing in Continuous Sliding-Window Aggregates 2004 VLDB 0.00011425419
1,354 On-the-Fly Sharing for Streamed Aggregation 2006 SIGMOD 0.00011057534
1,431 Towards Scalable Dataframe Systems 2020 VLDB 0.00010807221
1,555 Keyword Search in Databases: The Power of RDBMS 2009 SIGMOD 0.00010370683
1,765 Selecting Subexpressions to Materialize at Datacenter Scale 2018 VLDB 9.8079546e-05
1,771 Plan Selection based on Query Clustering 2002 VLDB 9.7942089e-05
2,151 An Architecture for Recycling Intermediates in a Column-store 2009 SIGMOD 9.0784444e-05
2,276 Shared Workload Optimization 2014 VLDB 8.8196376e-05
2,333 Query Processing for High-Volume XML Message Brokering 2003 VLDB 8.7376556e-05
2,387 S4: Top-k Spreadsheet-Style Search for Query Discovery 2015 SIGMOD 8.6482009e-05
2,394 A Case for Staged Database Systems 2003 CIDR 8.6362653e-05
2,513 Tuple Routing Strategies for Distributed Eddies 2003 VLDB 8.48462e-05
2,686 On Improving User Response Times in Tableau 2015 SIGMOD 8.25822e-05
2,785 Nested Mappings: Schema Mapping Reloaded 2006 VLDB 8.1236628e-05
2,933 EVA: A Symbolic Approach to Accelerating Exploratory Video Analytics with Materialized Views 2022 SIGMOD 7.9474026e-05
3,042 Continuous Sampling for Online Aggregation Over Multiple Queries 2010 SIGMOD 7.8231049e-05
3,117 Chi: A Scalable and Programmable Control Plane for Distributed Stream Processing Systems 2018 VLDB 7.7382559e-05
3,268 Efficient and Provable Multi-Query Optimization 2017 PODS 7.5810998e-05
3,319 Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer 2016 VLDB 7.5236413e-05
3,352 Scalable Pattern Sharing on Event Streams 2016 SIGMOD 7.4932699e-05
3,426 Exact Cardinality Query Optimization for Optimizer Testing 2009 VLDB 7.4218997e-05
3,598 Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? 2017 SIGMOD 7.2718988e-05
3,605 Computation Reuse in Analytics Job Service at Microsoft 2018 SIGMOD 7.2640711e-05
3,638 Fast Queries Over Heterogeneous Data Through Engine Customization 2016 VLDB 7.2338361e-05
3,913 An Approach to Optimize Data Processing in Business Processes 2007 VLDB 7.0230514e-05
3,946 Real-Time Multi-Pattern Detection over Event Streams 2019 SIGMOD 7.0046969e-05
4,023 Smurf: Self-Service String Matching Using Random Forests 2019 VLDB 6.949387e-05
4,101 Automated Generation of Materialized Views in Oracle 2020 VLDB 6.9009734e-05
4,137 Optimizing I/O for Big Array Analytics 2012 VLDB 6.8783832e-05
4,240 LIMA: Fine-grained Lineage Tracing and Reuse in Machine Learning Systems 2021 SIGMOD 6.809685e-05
4,330 Sharing Data and Work Across Concurrent Analytical Queries 2013 VLDB 6.7563122e-05
4,507 Scalable Multi-Query Optimization for Exploratory Queries over Federated Scientific Databases 2008 VLDB 6.6563628e-05
4,508 To Share or Not to Share? 2007 VLDB 6.6561159e-05
4,764 ReCache: Reactive Caching for Fast Analytics over Heterogeneous Data 2018 VLDB 6.51896e-05
5,470 Efficient Computation of Multiple Group By Queries 2005 SIGMOD 6.2070458e-05
5,552 Enabling Incremental Query Re-Optimization 2016 SIGMOD 6.1778488e-05
5,701 Lemo: A Cache-Enhanced Learned Optimizer for Concurrent Queries 2023 SIGMOD 6.1167049e-05
5,711 PolicyReplay: Misconfiguration-Response Queries for Data Breach Reporting 2010 VLDB 6.1128939e-05
5,716 Graph-Aware, Workload-Adaptive SPARQL Query Caching 2015 SIGMOD 6.1100964e-05
5,979 QoX-Driven ETL Design: Reducing the Cost of ETL Consulting Engagements 2009 SIGMOD 6.0212043e-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
137 Relational Databases for Querying XML Documents: Limitations and Opportunities 1999 VLDB 0.00029877792
153 Common Expression Analysis in Database Applications 1982 SIGMOD 0.00029032276
166 Query Transformation for PSJ-queries 1987 VLDB 0.00027676268
736 Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time 1996 SIGMOD 0.00014508563
1,107 Simultaneous Optimization and Evaluation of Multiple Dimensional Queries 1998 SIGMOD 0.00012145695
2,093 Reusing Invariants: A New Strategy for Correlated Queries 1998 SIGMOD 9.1831198e-05
2,593 Cost-Based Optimization of Decision Support Queries using Transient-Views 1998 SIGMOD 8.3649196e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,645 AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions 2003 VLDB
2 4,880 An Incremental Anytime Algorithm for Multi-Objective Query Optimization 2015 SIGMOD
3 5,124 Approximation Schemes for Many-Objective Query Optimization 2014 SIGMOD
4 583 Global Query Optimization 1986 SIGMOD
5 822 Pipelining in Multi-Query Optimization 2001 PODS
6 984 Analyzing Plan Diagrams of Database Query Optimizers 2005 VLDB
7 1,154 Efficient Exploitation of Similar Subexpressions for Query Processing 2007 SIGMOD
8 1,530 Multiple Query Processing in Deductive Databases using Query Graphs 1986 VLDB
9 2,540 Multi-Objective Parametric Query Optimization 2015 VLDB
10 3,268 Efficient and Provable Multi-Query Optimization 2017 PODS