A Fast Randomized Algorithm for Multi-Objective Query Optimization

Summary: First polynomial-time, randomized algorithm for multi-objective query optimization. Iterative, multi-objective hill climbing with multiple transformations and a Pareto-cache of intermediate results enables scalable search over join orders and outperforms NSGA-II on large queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5119
Venue: SIGMOD
Year: 2016
Pagerank: 4.4563359e-05
Overall Rank: 8,720 | 39.40%
DOI: 10.1145/2882903.2882927

Incoming Non-self Citations Over Time

Authors

1. Immanuel Trummer
2. Christoph Koch

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,080	Towards a Learning Optimizer for Shared Clouds	2019	VLDB	9.5954034e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040465394
388	Optimization of Large Join Queries	1988	SIGMOD	0.00024654816
400	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00024308369
439	Query Optimization for Parallel Execution	1992	SIGMOD	0.00023183237
811	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00016385568
979	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014871114
1,151	Blink and It's Done: Interactive Queries on Very Large Data	2012	VLDB	0.00013634671
1,618	Multiobjective Query Optimization	2001	PODS	0.00011125239
2,652	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3662031e-05
4,698	Schedule Optimization for Data Processing Flows on the Cloud	2011	SIGMOD	5.9835195e-05
4,876	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	5.8544467e-05
5,073	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD	5.7118738e-05
5,590	PET: Reducing Database Energy Cost via Query Optimization	2012	VLDB	5.4182957e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,255	Parallelizing Query Optimization	2008	VLDB	6.3080082e-05
2,051	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB	9.6871984e-05
2,351	Multi-objective Query Processing for Database Systems	2004	VLDB	8.9836468e-05
870	Parametric Query Optimization	1992	VLDB	0.00015709369
3,053	Fast, Randomized Join-Order Selection — Why Use Transformations?	1994	VLDB	7.6482987e-05
3,505	Efficient and Provable Multi-Query Optimization	2017	PODS	7.0304901e-05
5,073	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD	5.7118738e-05
1,725	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB	0.0001073575
400	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00024308369
2,652	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3662031e-05