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: h116eb349c323a04e
Venue: VLDB
Year: 2016
Pagerank: 5.1497631e-05
Overall Rank: 9,621 | 35.32%
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,139	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.6046928e-05
5,425	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	6.1349269e-05
5,908	Quantum-Inspired Digital Annealing for Join Ordering	2024	VLDB	5.9506986e-05
8,524	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	5.3231221e-05
8,651	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	5.2945994e-05
8,850	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	5.2645282e-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.0023947656
321	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00021088704
487	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017462723
708	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00014629998
796	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00013938011
1,243	Blink and It's Done: Interactive Queries on Very Large Data	2012	VLDB	0.0001135375
1,276	Orca: A Modular Query Optimizer Architecture for Big Data	2014	SIGMOD	0.00011239266
1,449	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB	0.00010620564
1,612	AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions	2003	VLDB	0.00010072731
2,103	Scheduling Problems in Parallel Query Optimization	1995	PODS	9.0414685e-05
2,524	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3439125e-05
3,567	On the Complexity of Approximate Query Optimization	2002	PODS	7.2010667e-05
3,775	Parallelizing Query Optimization	2008	VLDB	7.0272615e-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
6,049	Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs	2009	SIGMOD	5.9047797e-05
6,136	Parallelizing Extensible Query Optimizers	2009	SIGMOD	5.8759799e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,049	Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs	2009	SIGMOD
2	8,185	Progressive Optimization in a Shared-Nothing Parallel Database	2007	SIGMOD
3	243	Automating Physical Database Design in a Parallel Database	2002	SIGMOD
4	2,136	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
5	2,225	Shared Workload Optimization	2014	VLDB
6	6,136	Parallelizing Extensible Query Optimizers	2009	SIGMOD
7	2,305	Multi-dimensional Resource Scheduling for Parallel Queries	1996	SIGMOD
8	3,775	Parallelizing Query Optimization	2008	VLDB
9	446	Query Optimization for Parallel Execution	1992	SIGMOD
10	3,091	Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources	1997	VLDB