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: 11356
Venue: VLDB
Year: 2016
Pagerank: 4.353536e-05
Overall Rank: 9,312 | 35.29%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Immanuel Trummer
2. Christoph Koch

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,476	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.0560383e-05
6,060	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	5.2271244e-05
7,486	Quantum-Inspired Digital Annealing for Join Ordering	2024	VLDB	4.7135369e-05
8,772	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	4.451034e-05
9,692	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	4.2986161e-05
10,295	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	4.1905499e-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.0040465394
400	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00024308369
422	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023654556
782	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00016665859
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,674	Scheduling Problems in Parallel Query Optimization	1995	PODS	0.00010939926
1,725	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB	0.0001073575
1,990	AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions	2003	VLDB	9.8491124e-05
2,247	Orca: A Modular Query Optimizer Architecture for Big Data	2014	SIGMOD	9.201975e-05
2,652	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3662031e-05
4,189	On the Complexity of Approximate Query Optimization	2002	PODS	6.3681294e-05
4,255	Parallelizing Query Optimization	2008	VLDB	6.3080082e-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
6,333	Parallelizing Extensible Query Optimizers	2009	SIGMOD	5.1013149e-05
6,336	Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs	2009	SIGMOD	5.1009488e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,336	Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs	2009	SIGMOD	5.1009488e-05
8,168	Progressive Optimization in a Shared-Nothing Parallel Database	2007	SIGMOD	4.5674166e-05
285	Automating Physical Database Design in a Parallel Database	2002	SIGMOD	0.00028978423
2,051	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB	9.6871984e-05
2,928	Shared Workload Optimization	2014	VLDB	7.881485e-05
6,333	Parallelizing Extensible Query Optimizers	2009	SIGMOD	5.1013149e-05
2,458	Multi-dimensional Resource Scheduling for Parallel Queries	1996	SIGMOD	8.7601979e-05
4,255	Parallelizing Query Optimization	2008	VLDB	6.3080082e-05
439	Query Optimization for Parallel Execution	1992	SIGMOD	0.00023183237
3,129	Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources	1997	VLDB	7.5132501e-05