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: 5118
Venue: SIGMOD
Year: 2016
Pagerank: 4.4600243e-05
Overall Rank: 8,725 | 39.31%
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,083	Towards a Learning Optimizer for Shared Clouds	2019	VLDB	9.5834572e-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.0040449103
387	Optimization of Large Join Queries	1988	SIGMOD	0.0002471967
399	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00024315433
438	Query Optimization for Parallel Execution	1992	SIGMOD	0.00023199245
813	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.0001639584
978	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014881073
1,152	Blink and It's Done: Interactive Queries on Very Large Data	2012	VLDB	0.00013645792
1,614	Multiobjective Query Optimization	2001	PODS	0.00011135193
2,659	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3604734e-05
4,700	Schedule Optimization for Data Processing Flows on the Cloud	2011	SIGMOD	5.9882572e-05
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
5,585	PET: Reducing Database Energy Cost via Query Optimization	2012	VLDB	5.4231214e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,261	Parallelizing Query Optimization	2008	VLDB	6.31244e-05
2,044	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB	9.6953608e-05
2,346	Multi-objective Query Processing for Database Systems	2004	VLDB	8.9919258e-05
876	Parametric Query Optimization	1992	VLDB	0.00015716096
3,048	Fast, Randomized Join-Order Selection — Why Use Transformations?	1994	VLDB	7.6543116e-05
3,462	Efficient and Provable Multi-Query Optimization	2017	PODS	7.0703696e-05
5,075	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD	5.7172118e-05
1,726	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB	0.00010741411
399	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00024315433
2,659	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3604734e-05