A Scalable Hash Ripple Join Algorithm

Summary: Parallel hash ripple join with sampling to speed convergence for join-aggregate workloads; extends Haas and Hellerstein by combining parallelism with sampling. Memory-overflow tolerant; prototype shows convergence scales with processors and remains competitive with parallel hybrid hash join when run to completion. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h0c17a9a2cfcb9722
Venue: SIGMOD
Year: 2002
Pagerank: 9.5690887e-05
Overall Rank: 1,820 | 87.77%
DOI: 10.1145/564691.564721

Incoming Non-self Citations Over Time

Authors

1. Gang Luo (University of Wisconsin)
2. Curt J. Ellmann (NCR Corporation)
3. Peter J. Haas (IBM)
4. Jeffrey F. Naughton (University of Wisconsin)

BibTeX Citation

@inproceedings{luo_sigmod02,
        title = {{A Scalable Hash Ripple Join Algorithm}},
        author = {Luo, Gang and Ellmann, Curt J. and Haas, Peter J. and Naughton, Jeffrey F.},
        series = {{SIGMOD} '02},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/564691.564721},
        url = {https://dl.acm.org/doi/10.1145/564691.564721},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
596	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015785583
795	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013938779
1,090	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012077577
1,111	A Transducer-Based XML Query Processor	2002	VLDB	0.00011984202
3,087	Continuous Sampling for Online Aggregation Over Multiple Queries	2010	SIGMOD	7.6624333e-05
3,213	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	7.5328015e-05
3,603	Scalable Distributed Stream Join Processing	2015	SIGMOD	7.173496e-05
4,217	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.7271293e-05
5,452	Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results	2005	VLDB	6.1242445e-05
5,609	Responsible Data Integration: Next-generation Challenges	2022	SIGMOD	6.0689501e-05
5,831	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.9782109e-05
8,216	Wander Join: Online Aggregation for Joins	2016	SIGMOD	5.3764262e-05
8,744	ProgressiveDB – Progressive Data Analytics as a Middleware	2019	VLDB	5.2881174e-05
9,184	PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees	2010	SIGMOD	5.211541e-05
9,575	A Step Toward Deep Online Aggregation	2023	SIGMOD	5.1571823e-05
10,314	DeepOLA: Online Aggregation for Deeply Nested Queries	2022	SIGMOD	5.0377739e-05
12,317	Toward High-Performance Distributed Stream Processing via Approximate Fault Tolerance	2017	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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.00076195956
46	Benchmarking Database Systems: A Systematic Approach	1983	VLDB	0.00044784799
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029866033
249	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023175253
334	An Adaptive Query Execution System for Data Integration*	1999	SIGMOD	0.00020691326
1,628	Adaptive Parallel Aggregation Algorithms	1995	SIGMOD	0.00010037937
5,254	Online Feedback for Nested Aggregate Queries with Multi-Threading	1999	VLDB	6.2079513e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,144	Memory-Contention Responsive Hash Joins	1994	VLDB
2	5,452	Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results	2005	VLDB
3	3,248	Partially Preemptible Hash Joins	1993	SIGMOD
4	210	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB
5	2,507	Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory	1990	VLDB
6	135	Ripple Joins for Online Aggregation	1999	SIGMOD
7	361	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD
8	9,184	PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees	2010	SIGMOD
9	3,059	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD
10	1,799	An Adaptive Hash Join Algorithm for Multiuser Environments	1990	VLDB