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: 3189
Venue: SIGMOD
Year: 2000
Pagerank: 0.00037672155
Overall Rank: 179 | 98.76%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 37 of 87 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,443	Optimizing Join Enumeration in Transformation-based Query Optimizers	2014	VLDB	5.0599139e-05
6,469	Materialization and Reuse Optimizations for Production Data Science Pipelines	2022	SIGMOD	5.0519488e-05
6,650	Efficient Identification of Implicit Facts in Incomplete OWL2-EL Knowledge Bases	2014	VLDB	4.9763184e-05
6,753	State-Slice: New Paradigm of Multi-query Optimization of Window-based Stream Queries	2006	VLDB	4.9387235e-05
6,875	E-Cube: Multi-Dimensional Event Sequence Analysis Using Hierarchical Pattern Query Sharing	2011	SIGMOD	4.8978754e-05
6,963	Query Translation from XPath to SQL in the Presence of Recursive DTDs	2005	VLDB	4.8828629e-05
7,087	Increasing Buffer-Locality for Multiple Index Based Scans through Intelligent Placement and Index Scan Speed Control	2007	VLDB	4.8379358e-05
7,128	Jigsaw: A Data Storage and Query Processing Engine for Irregular Table Partitioning	2021	SIGMOD	4.8230171e-05
7,330	Lemo: A Cache-Enhanced Learned Optimizer for Concurrent Queries	2023	SIGMOD	4.7609373e-05
7,374	Sharing Work in Keyword Search over Databases	2011	SIGMOD	4.7494134e-05
7,461	Scalable Multi-Query Execution using Reinforcement Learning	2021	SIGMOD	4.723898e-05
7,701	Resource-efficient Shared Query Execution via Exploiting Time Slackness	2021	SIGMOD	4.6741329e-05
7,776	Plan Stitch: Harnessing the Best of Many Plans	2018	VLDB	4.6537231e-05
7,863	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	4.6328993e-05
8,257	Automating and Optimizing Data-Centric What-If Analyses on Native Machine Learning Pipelines	2023	SIGMOD	4.5487511e-05
8,295	View Selection over Knowledge Graphs in Triple Stores	2021	VLDB	4.5435639e-05
8,442	SageDB: An Instance-Optimized Data Analytics System	2022	VLDB	4.5120602e-05
8,795	Graphsurge: Graph Analytics on View Collections Using Differential Computation	2021	SIGMOD	4.4499973e-05
8,859	Pipemizer: An Optimizer for Analytics Data Pipelines	2022	VLDB	4.4344107e-05
9,092	Optimizing Complex Queries with Multiple Relation Instances	2008	SIGMOD	4.3981563e-05
9,378	CHEX: Multiversion Replay with Ordered Checkpoints	2022	VLDB	4.3463396e-05
9,556	Materialized View Selection & View-Based Query Planning for Regular Path Queries	2024	SIGMOD	4.3254416e-05
9,604	GeaFlow: A Graph Extended and Accelerated Dataflow System	2023	SIGMOD	4.3177432e-05
9,792	Optimizing Time Series Queries with Versions	2024	SIGMOD	4.2818172e-05
9,846	HyperBlocker: Accelerating Rule-based Blocking in Entity Resolution using GPUs	2025	VLDB	4.2721228e-05
9,922	Request Window: an Approach to Improve Throughput of RDBMS-based Data Integration System by Utilizing Data Sharing Across Concurrent Distributed Queries	2007	VLDB	4.2549509e-05
9,992	Supporting Our AI Overlords: Redesigning Data Systems to be Agent-First	2026	CIDR	4.1945683e-05
10,503	Self-Enhancing Video Data Management System for Compositional Events with Large Language Models	2025	SIGMOD	4.1945683e-05
10,726	Improving DBMS Scheduling Decisions with Accurate Performance Prediction on Concurrent Queries	2025	VLDB	4.1945683e-05
10,890	Oligolithic Cross-task Optimizations across Isolated Workloads*	2024	CIDR	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,053	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	4.1945683e-05
11,220	Lightweight Materialization for Fast Dashboards Over Joins	2023	SIGMOD	4.1945683e-05
11,483	Shahin: Faster Algorithms for Generating Explanations for Multiple Predictions	2021	SIGMOD	4.1945683e-05
11,624	Towards Multi-way Join Aware Optimizer in SAP HANA	2020	VLDB	4.1945683e-05
11,958	Shared Execution of Recurring Workloads in MapReduce	2015	VLDB	4.1945683e-05
12,266	Ten Thousand SQLs: Parallel Keyword Queries Computing	2010	VLDB	4.1945683e-05

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
88	Common Expression Analysis in Database Applications	1982	SIGMOD	0.00052316625
138	Query Transformation for PSJ-queries	1987	VLDB	0.00042334092
153	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00040784455
779	Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time	1996	SIGMOD	0.00016786961
829	Simultaneous Optimization and Evaluation of Multiple Dimensional Queries	1998	SIGMOD	0.0001618536
1,927	Reusing Invariants: A New Strategy for Correlated Queries	1998	SIGMOD	0.00010062716
2,284	Cost-Based Optimization of Decision Support Queries using Transient-Views	1998	SIGMOD	9.1053836e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,986	AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions	2003	VLDB	9.8536784e-05
5,075	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD	5.7172118e-05
4,874	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	5.8594632e-05
410	Global Query Optimization	1986	SIGMOD	0.00023934971
977	Pipelining in Multi-Query Optimization	2001	PODS	0.0001488881
1,476	Efficient Exploitation of Similar Subexpressions for Query Processing	2007	SIGMOD	0.00011779092
1,070	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB	0.00014316791
1,291	Multiple Query Processing in Deductive Databases using Query Graphs	1986	VLDB	0.00012794369
2,659	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3604734e-05
3,462	Efficient and Provable Multi-Query Optimization	2017	PODS	7.0703696e-05