DBScholar

Back to papers

Efficient and Provable Multi-Query Optimization

Summary: Recasts MQO as maximizing a linear transform of cost to exploit common subexpressions, yielding a greedy algorithm with provable approximation. Proves optimality of the factor unless P=NP and offers an easy-to-integrate optimizer extension with practical speedups. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
hd7be2a30be588f8c
Venue
PODS
Year
2017
Pagerank
7.5269127e-05
Overall Rank
3,214 | 78.40%
DOI
10.1145/3034786.3034792

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{kathuria_pods17,
        address = {New York, NY, USA},
        series = {{PODS} '17},
        title = {{Efficient and Provable Multi-Query Optimization}},
        url = {https://dl.acm.org/doi/10.1145/3034786.3034792},
        doi = {10.1145/3034786.3034792},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kathuria, Tarun and Sudarshan, S.},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank Citing Paper Year Venue Pagerank
1,745 Selecting Subexpressions to Materialize at Datacenter Scale 2018 VLDB 9.7343818e-05
3,101 On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML 2018 VLDB 7.649219e-05
4,007 Automated Generation of Materialized Views in Oracle 2020 VLDB 6.8592987e-05
6,706 Tempura: A General Cost-Based Optimizer Framework for Incremental Data Processing 2021 VLDB 5.7049776e-05
8,665 Applicability of Quantum Computing on Database Query Optimization 2022 SIGMOD 5.2922465e-05
8,696 View Selection over Knowledge Graphs in Triple Stores 2021 VLDB 5.2905577e-05
10,131 Optimizing Time Series Queries with Versions 2024 SIGMOD 5.0751052e-05
10,883 QDBO: A Real-time Quantum-augmented Database System Optimizer 2026 VLDB 4.9793485e-05
11,157 Mosaic: An Architecture for Linking Databases and Scalable Interactive Visualizations 2025 SIGMOD 4.9793485e-05
11,186 Rule-Based Graph Cleaning with GPUs on a Single Machine 2025 SIGMOD 4.9793485e-05
11,535 Atom: An Efficient Query Serving System for Embedding-based Knowledge Graph Reasoning with Operator-level Batching 2024 SIGMOD 4.9793485e-05
11,923 SAFE: A Share-and-Aggregate Bandwidth Exploration Framework for Kernel Density Visualization 2022 VLDB 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank Cited Paper Year Venue Pagerank
129 Efficient and Extensible Algorithms for Multi Query Optimization 2000 SIGMOD 0.0003040756
831 Pipelining in Multi-Query Optimization 2001 PODS 0.00013589597
1,131 Efficient Exploitation of Similar Subexpressions for Query Processing 2007 SIGMOD 0.0001189909
1,403 Anatomy of a Modular Multiple Query Optimizer 1988 VLDB 0.0001077088
2,619 Cost-Based Optimization of Decision Support Queries using Transient-Views 1998 SIGMOD 8.2215744e-05
2,660 The Complexity of Transformation-Based Join Enumeration 1997 VLDB 8.1611913e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 143 Optimization of Nonrecursive Queries 1986 VLDB
2 10,508 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD
3 1,403 Anatomy of a Modular Multiple Query Optimizer 1988 VLDB
4 4,486 Optimization of Continuous Queries with Shared Expensive Filters 2007 PODS
5 1,449 Design and Analysis of Parametric Query Optimization Algorithms 1998 VLDB
6 5,223 Approximation Schemes for Many-Objective Query Optimization 2014 SIGMOD
7 4,980 An Incremental Anytime Algorithm for Multi-Objective Query Optimization 2015 SIGMOD
8 1,298 Parametric Query Optimization for Linear and Piecewise Linear Cost Functions 2002 VLDB
9 129 Efficient and Extensible Algorithms for Multi Query Optimization 2000 SIGMOD
10 2,524 Multi-Objective Parametric Query Optimization 2015 VLDB