From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System

Summary: Unifies communication-optimal distributed join evaluation with worst-case optimal sequential algorithms for cyclic joins on parallel architectures. Demonstrates practical optimizations and a unified evaluation of both approaches, enabling efficient, scalable join processing in DBMS. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5078
Venue: SIGMOD
Year: 2015
Pagerank: 0.00010025547
Overall Rank: 1,938 | 86.54%
DOI: 10.1145/2723372.2750545

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 30 of 30 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
341	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026850764
1,322	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012595941
1,334	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00012543633
1,372	Random Sampling over Joins Revisited	2018	SIGMOD	0.0001233325
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1871115e-05
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
3,526	Distributed Data Deduplication	2016	VLDB	7.0056559e-05
3,733	Sortledton: a Universal, Transactional Graph Data Structure	2022	VLDB	6.8067988e-05
3,923	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	6.6232068e-05
3,983	The Myria Big Data Management and Analytics System and Cloud Service	2017	CIDR	6.5588011e-05
4,554	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	6.0839934e-05
6,618	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	4.9864636e-05
6,822	Computing Join Queries with Functional Dependencies	2016	PODS	4.9101655e-05
7,122	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	4.8199209e-05
7,154	Submodularity of Distributed Join Computation	2018	SIGMOD	4.8107765e-05
7,600	Quill: Efficient, Transferable, and Rich Analytics at Scale	2016	VLDB	4.697054e-05
7,759	G-SQL: Fast Query Processing via Graph Exploration	2016	VLDB	4.6549638e-05
8,423	SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries	2020	SIGMOD	4.5112315e-05
8,530	HYPERSONIC: A Hybrid Parallelization Approach for Scalable Complex Event Processing	2022	SIGMOD	4.4893996e-05
9,079	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD	4.3956812e-05
9,332	SODA: A Set of Fast Oblivious Algorithms in Distributed Secure Data Analytics	2023	VLDB	4.351469e-05
9,335	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	4.351469e-05
10,238	TurboLynx: Schemaless Graph Engine Strikes Back for General-Purpose Analytics	2026	VLDB	4.1905499e-05
10,498	HoneyComb: A Parallel Worst-Case Optimal Join on Multicores	2025	SIGMOD	4.1905499e-05
10,523	cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns	2025	SIGMOD	4.1905499e-05
11,360	Scaling Equi-Joins	2022	SIGMOD	4.1905499e-05
11,839	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.1905499e-05
11,843	An Efficient MapReduce Cube Algorithm for Varied Data Distributions	2016	SIGMOD	4.1905499e-05
11,890	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB	4.1905499e-05
11,957	Big Data Research: Will Industry Solve all the Problems?	2015	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
100	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050033475
109	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.00048217028
116	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00046191288
158	HadoopDB: An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads	2009	VLDB	0.00040401371
285	Automating Physical Database Design in a Parallel Database	2002	SIGMOD	0.00028978423
503	Worst-case Optimal Join Algorithms	2012	PODS	0.00021517145
539	Shark: SQL and Rich Analytics at Scale	2013	SIGMOD	0.00020615453
769	Multi-Dimensional Database Allocation for Parallel Data Warehouses	2000	VLDB	0.00016862794
900	F1: A Distributed SQL Database That Scales	2013	VLDB	0.00015466804
1,063	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB	0.00014352292
1,114	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013871948
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.00012118832
1,556	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	0.00011383141
2,051	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB	9.6871984e-05
2,216	Skew in Parallel Query Processing	2014	PODS	9.2693784e-05
2,410	Automated Partitioning Design in Parallel Database Systems	2011	SIGMOD	8.8643562e-05
2,518	Track Join: Distributed Joins with Minimal Network Traffic	2014	SIGMOD	8.6052941e-05
3,068	Efficient Multi-way Theta-Join Processing Using MapReduce	2012	VLDB	7.6241861e-05
3,371	Demonstration of the Myria Big Data Management Service	2014	SIGMOD	7.1634294e-05
3,384	Scalable and Adaptive Online Joins	2014	VLDB	7.153329e-05
4,128	Advanced Join Strategies for Large-Scale Distributed Computation	2014	VLDB	6.4214449e-05
8,110	Execution Primitives for Scalable Joins and Aggregations in Map Reduce	2014	VLDB	4.5805849e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,128	Advanced Join Strategies for Large-Scale Distributed Computation	2014	VLDB	6.4214449e-05
7,832	Effective Resource Utilization for Multiprocessor Join Execution	1989	VLDB	4.636825e-05
4,255	Parallelizing Query Optimization	2008	VLDB	6.3080082e-05
1,114	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013871948
8,213	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	4.5533861e-05
6,060	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	5.2271244e-05
11,898	Let's Rethink Join Optimization in Distributed Systems	2015	CIDR	4.1905499e-05
3,899	Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment	2021	VLDB	6.6513982e-05
2,311	Parallel evaluation of multi-join queries	1995	SIGMOD	9.0610521e-05
2,051	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB	9.6871984e-05