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.7844791e-05
Overall Rank: 2,972 | 80.08%
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,296	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011119184
3,379	Frontier: Resilient Edge Processing for the Internet of Things	2018	VLDB	7.3417159e-05
3,610	Scalable Distributed Stream Join Processing	2015	SIGMOD	7.1463915e-05
4,550	AdaptDB: Adaptive Partitioning for Distributed Joins	2017	VLDB	6.5327021e-05
5,080	Change Propagation Without Joins	2023	VLDB	6.2689958e-05
6,553	A Holistic View of Stream Partitioning Costs	2017	VLDB	5.7306258e-05
6,743	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.6766099e-05
6,880	SquirrelJoin: Network-Aware Distributed Join Processing with Lazy Partitioning	2017	VLDB	5.6423904e-05
7,284	Submodularity of Distributed Join Computation	2018	SIGMOD	5.5505534e-05
7,792	Squall: Scalable Real-time Analytics	2016	VLDB	5.4352729e-05
7,985	Parallelizing Intra-Window Join on Multicores: An Experimental Study	2021	SIGMOD	5.3960833e-05
8,797	CLASH: A High-Level Abstraction for Optimized, Multi-Way Stream Joins over Apache Storm	2019	SIGMOD	5.261449e-05
9,249	Chasing Similarity: Distribution-aware Aggregation Scheduling	2019	VLDB	5.1860134e-05
11,580	Low-Latency Adaptive Distributed Stream Join System Based on a Flexible Join Model	2024	SIGMOD	4.9605343e-05
11,591	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9605343e-05
12,424	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB	4.9605343e-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.00076079812
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00040739114
76	Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters	2007	SIGMOD	0.00036932687
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00034691614
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034050614
128	The Design of the Borealis Stream Processing Engine	2005	CIDR	0.00030317705
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029805026
249	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023099455
596	Linear Road: A Stream Data Management Benchmark	2004	VLDB	0.00015766455
799	A Comparison of Join Algorithms for Log Processing in MapReduce	2010	SIGMOD	0.00013839554
867	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00013342302
973	Integrating Scale Out and Fault Tolerance in Stream Processing using Operator State Management	2013	SIGMOD	0.00012734154
2,563	Tuple Routing Strategies for Distributed Eddies	2003	VLDB	8.2699925e-05
2,684	A Latency and Fault-Tolerance Optimizer for Online Parallel Query Plans	2011	SIGMOD	8.1185673e-05
2,853	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB	7.9179824e-05
2,944	Efficient Multi-way Theta-Join Processing Using MapReduce	2012	VLDB	7.8126906e-05
4,069	Adaptive Query Processing in the Looking Glass	2005	CIDR	6.8080574e-05
4,394	Lifting the Burden of History from Adaptive Query Processing	2004	VLDB	6.6084598e-05
6,045	RPJ: Producing Fast Join Results on Streams through Rate-based Optimization	2005	SIGMOD	5.8882414e-05

Semantically Similar Papers

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