Multiobjective Query Optimization

Summary: Shows Mariposa’s stride-based greedy optimizer for delay–cost trade-offs can be arbitrarily bad. Adapts multiobjective-optimization techniques to compute Pareto cost–delay curves to any accuracy, and gives a polynomial algorithm for the general problem without stride restrictions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h3b7a2333a7d6eb92
Venue: PODS
Year: 2001
Pagerank: 9.5976083e-05
Overall Rank: 1,806 | 87.86%
DOI: 10.1145/375551.375560

Incoming Non-self Citations Over Time

Authors

1. Christos H. Papadimitriou (University of California Berkeley)
2. Mihalis Yannakakis (AT&T)

BibTeX Citation

@inproceedings{papadimitriou_pods01,
        address = {New York, NY, USA},
        series = {{PODS} '01},
        title = {{Multiobjective Query Optimization}},
        url = {https://dl.acm.org/doi/10.1145/375551.375560},
        doi = {10.1145/375551.375560},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Papadimitriou, Christos H. and Yannakakis, Mihalis},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
313	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021311041
2,524	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3439125e-05
2,566	Stratified Computation of Skylines with Partially-Ordered Domains	2005	SIGMOD	8.288424e-05
2,996	Multi-objective Query Processing for Database Systems	2004	VLDB	7.7697801e-05
4,188	Schedule Optimization for Data Processing Flows on the Cloud	2011	SIGMOD	6.7464862e-05
4,980	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD	6.3293674e-05
5,223	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	6.2212838e-05
5,269	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB	6.2014805e-05
8,971	A Fast Randomized Algorithm for Multi-Objective Query Optimization	2016	SIGMOD	5.2462912e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2,103	Scheduling Problems in Parallel Query Optimization	1995	PODS	9.0414685e-05
2,168	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB	8.9275427e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,449	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB
2	5,735	Efficient and Accurate Cost Models for Parallel Query Optimization	1996	PODS
3	5,223	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD
4	7,909	Optimizing Star Queries in a Distributed Database System	1984	VLDB
5	8,635	An Iterative Method for Distributed Database Design	1991	VLDB
6	446	Query Optimization for Parallel Execution	1992	SIGMOD
7	8,971	A Fast Randomized Algorithm for Multi-Objective Query Optimization	2016	SIGMOD
8	3,214	Efficient and Provable Multi-Query Optimization	2017	PODS
9	2,524	Multi-Objective Parametric Query Optimization	2015	VLDB
10	2,996	Multi-objective Query Processing for Database Systems	2004	VLDB