Parallelizing Query Optimization on Shared-Nothing Architectures

Summary: Parallels left-deep and bushy query plans by partitioning the plan space across workers on shared-nothing clusters. Masters collect partition-optima with no intra-optimization synchronization; efficiency scales linearly and yields up to 10x speedups on large queries over 100 nodes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11543
Venue: VLDB
Year: 2016
Pagerank: 5.2667452e-05
Overall Rank: 9,446 | 35.20%
DOI: 10.14778/2947618.2947620

Incoming Non-self Citations Over Time

Authors

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

BibTeX Citation

@article{trummer_vldb16,
        title = {{Parallelizing Query Optimization on Shared-Nothing Architectures}},
        author = {Trummer, Immanuel and Koch, Christoph},
        journal = {PVLDB},
        series = {{VLDB} '16},
        volume = {9},
        number = {9},
        pages = {660--671},
        doi = {10.14778/2947618.2947620},
        url = {https://doi.org/10.14778/2947618.2947620},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,158	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.6888079e-05
5,399	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	6.2319315e-05
7,910	Quantum-Inspired Digital Annealing for Join Ordering	2024	VLDB	5.5181056e-05
8,698	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	5.3830073e-05
9,796	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	5.21848e-05
9,969	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	5.1845938e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 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
316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.0002141607
479	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017789732
698	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00014879675
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,470	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB	0.00010676869
1,621	Orca: A Modular Query Optimizer Architecture for Big Data	2014	SIGMOD	0.00010203114
1,645	AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions	2003	VLDB	0.00010129244
2,068	Scheduling Problems in Parallel Query Optimization	1995	PODS	9.2310451e-05
2,540	Multi-Objective Parametric Query Optimization	2015	VLDB	8.45187e-05
3,553	On the Complexity of Approximate Query Optimization	2002	PODS	7.3175599e-05
3,726	Parallelizing Query Optimization	2008	VLDB	7.1697834e-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
6,018	Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs	2009	SIGMOD	6.0060585e-05
6,026	Parallelizing Extensible Query Optimizers	2009	SIGMOD	6.0024042e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,018	Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs	2009	SIGMOD
2	8,064	Progressive Optimization in a Shared-Nothing Parallel Database	2007	SIGMOD
3	246	Automating Physical Database Design in a Parallel Database	2002	SIGMOD
4	2,104	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
5	2,276	Shared Workload Optimization	2014	VLDB
6	6,026	Parallelizing Extensible Query Optimizers	2009	SIGMOD
7	2,337	Multi-dimensional Resource Scheduling for Parallel Queries	1996	SIGMOD
8	3,726	Parallelizing Query Optimization	2008	VLDB
9	434	Query Optimization for Parallel Execution	1992	SIGMOD
10	3,046	Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources	1997	VLDB