Pipelining in Multi-Query Optimization

Summary: Introduce a general model for pipelined multi-query optimization and a necessary and sufficient condition to decide schedule validity under finite buffer constraints. Prove NP-hardness of finding minimum-cost valid schedules, propose a greedy heuristic, and show TPC-D performance gains. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h2def42a55ead9ef3
Venue: PODS
Year: 2001
Pagerank: 0.00013589597
Overall Rank: 831 | 94.42%
DOI: 10.1145/375551.375561

Incoming Non-self Citations Over Time

Authors

1. Nilesh N. Dalvi (Indian Institute of Technology Mumbai)
2. Sumit K Sanghai (Indian Institute of Technology Mumbai)
3. Prasan Roy (AT&T)
4. S. Sudarshan (Indian Institute of Technology Mumbai)

BibTeX Citation

@inproceedings{dalvi_pods01,
        address = {New York, NY, USA},
        series = {{PODS} '01},
        title = {{Pipelining in Multi-Query Optimization}},
        url = {https://dl.acm.org/doi/10.1145/375551.375561},
        doi = {10.1145/375551.375561},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Dalvi, Nilesh N. and Sanghai, Sumit K and Roy, Prasan and Sudarshan, S.},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
112	TelegraphCQ: Continuous Dataflow Processing for an Uncertain World	2003	CIDR	0.00032459277
389	QPipe: A Simultaneously Pipelined Relational Query Engine	2005	SIGMOD	0.00019269777
667	SharedDB: Killing One Thousand Queries With One Stone	2012	VLDB	0.00014978213
762	Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS	2007	VLDB	0.00014140446
2,225	Shared Workload Optimization	2014	VLDB	8.8081001e-05
2,700	On Improving User Response Times in Tableau	2015	SIGMOD	8.1188166e-05
2,771	Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer	2016	VLDB	8.0369366e-05
3,214	Efficient and Provable Multi-Query Optimization	2017	PODS	7.5269127e-05
3,367	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB	7.3719456e-05
3,995	An Approach to Optimize Data Processing in Business Processes	2007	VLDB	6.86657e-05
4,056	The Case for Precision Sharing	2004	VLDB	6.8261065e-05
4,392	Sharing Data and Work Across Concurrent Analytical Queries	2013	VLDB	6.6213651e-05
4,486	Optimization of Continuous Queries with Shared Expensive Filters	2007	PODS	6.5788984e-05
4,577	To Share or Not to Share?	2007	VLDB	6.523408e-05
5,582	Efficient Computation of Multiple Group By Queries	2005	SIGMOD	6.0768264e-05
5,788	Lemo: A Cache-Enhanced Learned Optimizer for Concurrent Queries	2023	SIGMOD	5.9947442e-05
6,075	QoX-Driven ETL Design: Reducing the Cost of ETL Consulting Engagements	2009	SIGMOD	5.8944111e-05
6,217	Materialization and Reuse Optimizations for Production Data Science Pipelines	2022	SIGMOD	5.8474357e-05
7,027	Near-Optimal Algorithms for Shared Filter Evaluation in Data Stream Systems	2008	SIGMOD	5.6179837e-05
7,341	Scalable Multi-Query Execution using Reinforcement Learning	2021	SIGMOD	5.5481233e-05
7,809	Nautilus: An Optimized System for Deep Transfer Learning over Evolving Training Datasets	2022	SIGMOD	5.4490255e-05
8,042	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	5.4014499e-05
8,968	Pipemizer: An Optimizer for Analytics Data Pipelines	2022	VLDB	5.2471751e-05
9,463	Optimizing Complex Queries with Multiple Relation Instances	2008	SIGMOD	5.1728359e-05
10,289	Request Window: an Approach to Improve Throughput of RDBMS-based Data Integration System by Utilizing Data Sharing Across Concurrent Distributed Queries	2007	VLDB	5.0446125e-05
11,548	Pasta: A Cost-Based Optimizer for Generating Pipelining Schedules for Dataflow DAGs	2024	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 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
844	Exploiting Inter-Operation Parallelism in XPRS	1992	SIGMOD	0.00013533208
957	Materialized View Selection for Multidimensional Datasets	1998	VLDB	0.00012861484
1,403	Anatomy of a Modular Multiple Query Optimizer	1988	VLDB	0.0001077088
2,103	Scheduling Problems in Parallel Query Optimization	1995	PODS	9.0414685e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,136	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
2	6,049	Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs	2009	SIGMOD
3	3,299	On Optimal Processor Allocation To Support Pipelined Hash Joins	1993	SIGMOD
4	3,214	Efficient and Provable Multi-Query Optimization	2017	PODS
5	2,305	Multi-dimensional Resource Scheduling for Parallel Queries	1996	SIGMOD
6	1,796	Dynamic Pipeline Scheduling for Improving Interactive Query Performance	2001	VLDB
7	6,288	Elastic Pipelining in an In-Memory Database Cluster	2016	SIGMOD
8	2,103	Scheduling Problems in Parallel Query Optimization	1995	PODS
9	2,168	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB
10	9,784	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR