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: 11355
Venue: VLDB
Year: 2016
Pagerank: 4.3577129e-05
Overall Rank: 9,305 | 35.27%
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,474	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.0625972e-05
6,056	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	5.2321475e-05
7,486	Quantum-Inspired Digital Annealing for Join Ordering	2024	VLDB	4.7180617e-05
8,775	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	4.4553047e-05
9,693	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	4.3027391e-05
10,283	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	4.1945683e-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.0040449103
399	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00024315433
423	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023669348
784	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00016675823
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,672	Scheduling Problems in Parallel Query Optimization	1995	PODS	0.00010949448
1,726	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB	0.00010741411
1,986	AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions	2003	VLDB	9.8536784e-05
2,249	Orca: A Modular Query Optimizer Architecture for Big Data	2014	SIGMOD	9.2034693e-05
2,659	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3604734e-05
4,194	On the Complexity of Approximate Query Optimization	2002	PODS	6.3697822e-05
4,261	Parallelizing Query Optimization	2008	VLDB	6.31244e-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
6,334	Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs	2009	SIGMOD	5.1058462e-05
6,337	Parallelizing Extensible Query Optimizers	2009	SIGMOD	5.1053757e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,334	Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs	2009	SIGMOD	5.1058462e-05
8,165	Progressive Optimization in a Shared-Nothing Parallel Database	2007	SIGMOD	4.5717277e-05
285	Automating Physical Database Design in a Parallel Database	2002	SIGMOD	0.0002899128
2,044	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB	9.6953608e-05
2,925	Shared Workload Optimization	2014	VLDB	7.888494e-05
6,337	Parallelizing Extensible Query Optimizers	2009	SIGMOD	5.1053757e-05
2,459	Multi-dimensional Resource Scheduling for Parallel Queries	1996	SIGMOD	8.7676516e-05
4,261	Parallelizing Query Optimization	2008	VLDB	6.31244e-05
438	Query Optimization for Parallel Execution	1992	SIGMOD	0.00023199245
3,124	Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources	1997	VLDB	7.5201555e-05