PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees

Summary: PR-Join: non-blocking online-aggregation using hash-partitioned ripple-like ops with expanding width to boost early results. Analytical results show >10x higher early-result rates vs prior non-blocking joins; SSDs push end-to-end toward near-optimal. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h25e5fb9c8e19a45d
Venue: SIGMOD
Year: 2010
Pagerank: 5.1918495e-05
Overall Rank: 9,218 | 38.22%
DOI: 10.1145/1807167.1807186

Incoming Non-self Citations Over Time

Authors

1. Shimin Chen (Intel)
2. Phillip B. Gibbons (Intel)
3. Suman Nath (Microsoft)

BibTeX Citation

@inproceedings{chen_sigmod10,
        title = {{PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees}},
        author = {Chen, Shimin and Gibbons, Phillip B. and Nath, Suman},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807186},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807186},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,610	Scalable Distributed Stream Join Processing	2015	SIGMOD	7.1463915e-05
8,071	Progressive Join Algorithms Considering User Preference	2021	CIDR	5.3800399e-05
9,608	A Step Toward Deep Online Aggregation	2023	SIGMOD	5.1376962e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00081781676
9	Online Aggregation	1997	SIGMOD	0.00076079812
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029805026
571	A Case for Flash Memory SSD in Enterprise Database Applications	2008	SIGMOD	0.00016168887
984	Lazy-Adaptive Tree: An Optimized Index Structure for Flash Devices	2009	VLDB	0.00012672529
1,016	Flashing Up the Storage Layer	2008	VLDB	0.00012461604
1,095	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012036913
1,127	FlashLogging: Exploiting Flash Devices for Synchronous Logging Performance	2009	SIGMOD	0.00011887959
1,465	Online Maintenance of Very Large Random Samples on Flash Storage	2008	VLDB	0.00010546726
1,485	Query Processing Techniques for Solid State Drives	2009	SIGMOD	0.00010498393
1,832	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD	9.5365548e-05
2,853	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB	7.9179824e-05
3,114	An Object Placement Advisor for DB2 Using Solid State Storage	2009	VLDB	7.6194936e-05
3,220	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	7.5077984e-05
5,473	Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results	2005	VLDB	6.1015044e-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	12,432	Let's Rethink Join Optimization in Distributed Systems	2015	CIDR
2	505	Supporting Top-k Join Queries in Relational Databases	2003	VLDB
3	3,072	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD
4	2,853	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB
5	3,236	Partially Preemptible Hash Joins	1993	SIGMOD
6	2,972	Scalable and Adaptive Online Joins	2014	VLDB
7	135	Ripple Joins for Online Aggregation	1999	SIGMOD
8	5,473	Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results	2005	VLDB
9	1,832	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD
10	6,045	RPJ: Producing Fast Join Results on Streams through Rate-based Optimization	2005	SIGMOD