Scalable and Adaptive Online Joins

Summary: Adaptive parallel online join for arbitrary predicates, dynamically rerouting data and repartitioning state without blocking or prior workload statistics. Handles skew with eventual local/strong external consistency, amortized-constant tuple cost, and a proven 3.75-competitive distribution bound. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h8b8f773f57af44ab
Venue: VLDB
Year: 2014
Pagerank: 7.8100535e-05
Overall Rank: 2,956 | 80.14%
DOI: 10.14778/2732279.2732281
PDF: Download (CC BY-NC-ND 3.0)

Incoming Non-self Citations Over Time

Authors

1. Mohammed Elseidy (EPFL)
2. Abdallah Elguindy (EPFL)
3. Aleksandar Vitorovic (EPFL)
4. Christoph Koch (EPFL)

BibTeX Citation

@article{elseidy_vldb14,
        title = {{Scalable and Adaptive Online Joins}},
        author = {Elseidy, Mohammed and Elguindy, Abdallah and Vitorovic, Aleksandar and Koch, Christoph},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {6},
        pages = {441--452},
        doi = {10.14778/2732279.2732281},
        url = {https://doi.org/10.14778/2732279.2732281},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011147959
3,370	Frontier: Resilient Edge Processing for the Internet of Things	2018	VLDB	7.3660727e-05
3,603	Scalable Distributed Stream Join Processing	2015	SIGMOD	7.1701004e-05
4,534	AdaptDB: Adaptive Partitioning for Distributed Joins	2017	VLDB	6.5535468e-05
5,061	Change Propagation Without Joins	2023	VLDB	6.2897936e-05
6,543	A Holistic View of Stream Partitioning Costs	2017	VLDB	5.7496377e-05
6,725	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.6954425e-05
6,863	SquirrelJoin: Network-Aware Distributed Join Processing with Lazy Partitioning	2017	VLDB	5.6604842e-05
7,266	Submodularity of Distributed Join Computation	2018	SIGMOD	5.5689674e-05
7,776	Squall: Scalable Real-time Analytics	2016	VLDB	5.4533049e-05
7,968	Parallelizing Intra-Window Join on Multicores: An Experimental Study	2021	SIGMOD	5.4139853e-05
8,778	CLASH: A High-Level Abstraction for Optimized, Multi-Way Stream Joins over Apache Storm	2019	SIGMOD	5.2789044e-05
9,225	Chasing Similarity: Distribution-aware Aggregation Scheduling	2019	VLDB	5.2032183e-05
11,531	Low-Latency Adaptive Distributed Stream Join System Based on a Flexible Join Model	2024	SIGMOD	4.9769913e-05
11,542	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9769913e-05
12,381	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
9	Online Aggregation	1997	SIGMOD	0.00076265429
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.000408505
75	Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters	2007	SIGMOD	0.0003702496
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00034748721
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034099838
127	The Design of the Borealis Stream Processing Engine	2005	CIDR	0.00030414379
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029858107
249	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.0002316492
594	Linear Road: A Stream Data Management Benchmark	2004	VLDB	0.00015816384
799	A Comparison of Join Algorithms for Log Processing in MapReduce	2010	SIGMOD	0.00013882649
866	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00013381756
970	Integrating Scale Out and Fault Tolerance in Stream Processing using Operator State Management	2013	SIGMOD	0.00012776109
2,558	Tuple Routing Strategies for Distributed Eddies	2003	VLDB	8.2968348e-05
2,673	A Latency and Fault-Tolerance Optimizer for Online Parallel Query Plans	2011	SIGMOD	8.1453443e-05
2,845	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB	7.9439702e-05
2,932	Efficient Multi-way Theta-Join Processing Using MapReduce	2012	VLDB	7.8368679e-05
4,046	Adaptive Query Processing in the Looking Glass	2005	CIDR	6.8297725e-05
4,369	Lifting the Burden of History from Adaptive Query Processing	2004	VLDB	6.6302169e-05
6,032	RPJ: Producing Fast Join Results on Streams through Rate-based Optimization	2005	SIGMOD	5.9077446e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,431	Approximate Join Processing Over Data Streams	2003	SIGMOD
2	5,017	Massive Scale-out of Expensive Continuous Queries	2011	VLDB
3	6,725	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD
4	1,034	A Scalable, Predictable Join Operator for Highly Concurrent Data Warehouses	2009	VLDB
5	1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
6	12,389	Let's Rethink Join Optimization in Distributed Systems	2015	CIDR
7	6,543	A Holistic View of Stream Partitioning Costs	2017	VLDB
8	12,304	Runtime Optimization of Join Location in Parallel Data Management Systems	2017	VLDB
9	3,603	Scalable Distributed Stream Join Processing	2015	SIGMOD
10	11,531	Low-Latency Adaptive Distributed Stream Join System Based on a Flexible Join Model	2024	SIGMOD