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: 5180
Venue: SIGMOD
Year: 2016
Pagerank: 5.3607984e-05
Overall Rank: 8,831 | 39.42%
DOI: 10.1145/2882903.2882927

Incoming Non-self Citations Over Time

Authors

1. Immanuel Trummer (EPFL)
2. Christoph Koch (EPFL)

BibTeX Citation

@inproceedings{trummer_sigmod16,
        title = {{A Fast Randomized Algorithm for Multi-Objective Query Optimization}},
        author = {Trummer, Immanuel and Koch, Christoph},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2882927},
        url = {https://dl.acm.org/doi/10.1145/2882903.2882927},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,468	Towards a Learning Optimizer for Shared Clouds	2019	VLDB	0.00010686496

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.0024089429
434	Query Optimization for Parallel Execution	1992	SIGMOD	0.00018531826
463	Optimization of Large Join Queries	1988	SIGMOD	0.00018064961
479	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017789732
708	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00014727576
774	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014123979
1,227	Blink and It's Done: Interactive Queries on Very Large Data	2012	VLDB	0.00011582387
1,762	Multiobjective Query Optimization	2001	PODS	9.812504e-05
2,540	Multi-Objective Parametric Query Optimization	2015	VLDB	8.45187e-05
4,117	Schedule Optimization for Data Processing Flows on the Cloud	2011	SIGMOD	6.8919486e-05
4,880	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD	6.4656221e-05
5,124	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	6.3567981e-05
5,339	PET: Reducing Database Energy Cost via Query Optimization	2012	VLDB	6.2609069e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,726	Parallelizing Query Optimization	2008	VLDB
2	2,104	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
3	2,932	Multi-objective Query Processing for Database Systems	2004	VLDB
4	770	Parametric Query Optimization	1992	VLDB
5	2,996	Fast, Randomized Join-Order Selection—Why Use Transformations?	1994	VLDB
6	3,268	Efficient and Provable Multi-Query Optimization	2017	PODS
7	4,880	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD
8	1,470	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB
9	479	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD
10	2,540	Multi-Objective Parametric Query Optimization	2015	VLDB