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: 1710
Venue: PODS
Year: 2017
Pagerank: 7.0703696e-05
Overall Rank: 3,462 | 75.92%
DOI: 10.1145/3034786.3034792

Incoming Non-self Citations Over Time

Authors

1. Tarun Kathuria
2. S. Sudarshan

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,922	Selecting Subexpressions to Materialize at Datacenter Scale	2018	VLDB	0.00010082599
3,918	On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML	2018	VLDB	6.6315176e-05
4,623	Automated Generation of Materialized Views in Oracle	2020	VLDB	6.0411909e-05
7,305	Tempura: A General Cost-Based Optimizer Framework for Incremental Data Processing	2021	VLDB	4.7678776e-05
8,176	Applicability of Quantum Computing on Database Query Optimization	2022	SIGMOD	4.5674639e-05
8,295	View Selection over Knowledge Graphs in Triple Stores	2021	VLDB	4.5435639e-05
9,792	Optimizing Time Series Queries with Versions	2024	SIGMOD	4.2818172e-05
10,447	Mosaic: An Architecture for Linking Databases and Scalable Interactive Visualizations	2025	SIGMOD	4.1945683e-05
10,486	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	4.1945683e-05
10,979	Atom: An Efficient Query Serving System for Embedding-based Knowledge Graph Reasoning with Operator-level Batching	2024	SIGMOD	4.1945683e-05
11,417	SAFE: A Share-and-Aggregate Bandwidth Exploration Framework for Kernel Density Visualization	2022	VLDB	4.1945683e-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
179	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD	0.00037672155
977	Pipelining in Multi-Query Optimization	2001	PODS	0.0001488881
1,237	Anatomy of a Modular Multiple Query Optimizer	1988	VLDB	0.00013115863
1,476	Efficient Exploitation of Similar Subexpressions for Query Processing	2007	SIGMOD	0.00011779092
2,284	Cost-Based Optimization of Decision Support Queries using Transient-Views	1998	SIGMOD	9.1053836e-05
2,869	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	7.9808408e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,725	A Fast Randomized Algorithm for Multi-Objective Query Optimization	2016	SIGMOD	4.4600243e-05
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00041510555
4,384	Optimization of Continuous Queries with Shared Expensive Filters	2007	PODS	6.2371282e-05
1,237	Anatomy of a Modular Multiple Query Optimizer	1988	VLDB	0.00013115863
1,726	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB	0.00010741411
4,874	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	5.8594632e-05
5,075	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD	5.7172118e-05
1,647	Parametric Query Optimization for Linear and Piecewise Linear Cost Functions	2002	VLDB	0.00011033757
179	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD	0.00037672155
2,659	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3604734e-05