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: 1709
Venue: PODS
Year: 2017
Pagerank: 7.5810998e-05
Overall Rank: 3,268 | 77.58%
DOI: 10.1145/3034786.3034792

Incoming Non-self Citations Over Time

Authors

1. Tarun Kathuria (Microsoft)
2. S. Sudarshan (Indian Institute of Technology Mumbai)

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 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,765	Selecting Subexpressions to Materialize at Datacenter Scale	2018	VLDB	9.8079546e-05
3,205	On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML	2018	VLDB	7.6386536e-05
4,101	Automated Generation of Materialized Views in Oracle	2020	VLDB	6.9009734e-05
6,626	Tempura: A General Cost-Based Optimizer Framework for Incremental Data Processing	2021	VLDB	5.8198723e-05
8,527	View Selection over Knowledge Graphs in Triple Stores	2021	VLDB	5.4119882e-05
8,695	Applicability of Quantum Computing on Database Query Optimization	2022	SIGMOD	5.3835466e-05
9,947	Optimizing Time Series Queries with Versions	2024	SIGMOD	5.1915905e-05
10,728	Mosaic: An Architecture for Linking Databases and Scalable Interactive Visualizations	2025	SIGMOD	5.093636e-05
10,763	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	5.093636e-05
11,192	Atom: An Efficient Query Serving System for Embedding-based Knowledge Graph Reasoning with Operator-level Batching	2024	SIGMOD	5.093636e-05
11,615	SAFE: A Share-and-Aggregate Bandwidth Exploration Framework for Kernel Density Visualization	2022	VLDB	5.093636e-05

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
128	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD	0.0003072825
822	Pipelining in Multi-Query Optimization	2001	PODS	0.00013807229
1,154	Efficient Exploitation of Similar Subexpressions for Query Processing	2007	SIGMOD	0.00011934202
1,375	Anatomy of a Modular Multiple Query Optimizer	1988	VLDB	0.00010977145
2,593	Cost-Based Optimization of Decision Support Queries using Transient-Views	1998	SIGMOD	8.3649196e-05
2,627	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.3284491e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	143	Optimization of Nonrecursive Queries	1986	VLDB
2	1,375	Anatomy of a Modular Multiple Query Optimizer	1988	VLDB
3	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
4	4,441	Optimization of Continuous Queries with Shared Expensive Filters	2007	PODS
5	1,470	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB
6	5,124	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD
7	4,880	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD
8	1,321	Parametric Query Optimization for Linear and Piecewise Linear Cost Functions	2002	VLDB
9	128	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD
10	2,540	Multi-Objective Parametric Query Optimization	2015	VLDB