Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm

Summary: PMJ emits results during external mergesort, removing blocking waits for sort-based joins. PMJ framework, with a probabilistic selectivity estimator, enables early results for joins (incl. similarity); implemented in an object-relational cursor algebra. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8853
Venue: VLDB
Year: 2002
Pagerank: 7.3889212e-05
Overall Rank: 3,204 | 77.72%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
940	SharedDB: Killing One Thousand Queries With One Stone	2012	VLDB	0.00015173166
1,425	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012051353
1,524	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00011516282
3,382	Scalable and Adaptive Online Joins	2014	VLDB	7.1597145e-05
4,245	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.3272687e-05
5,511	On Producing Join Results Early	2003	PODS	5.4699346e-05
5,866	Low-Latency Handshake Join	2014	VLDB	5.2968632e-05
5,906	Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results	2005	VLDB	5.2787348e-05
6,338	RPJ: Producing Fast Join Results on Streams through Rate-based Optimization	2005	SIGMOD	5.105321e-05
7,470	The Case for Deep Query Optimisation	2020	CIDR	4.7201897e-05
8,018	Parallelizing Intra-Window Join on Multicores: An Experimental Study	2021	SIGMOD	4.6046381e-05
8,205	PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees	2010	SIGMOD	4.5593375e-05
10,981	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.1945683e-05
11,194	A Step Toward Deep Online Aggregation	2023	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,069	Proximity Rank Join	2010	VLDB	6.4789031e-05
2,640	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD	8.3924401e-05
12,191	Efficient Rank Join with Aggregation Constraints	2011	VLDB	4.1945683e-05
552	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00020310903
3,898	Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment	2021	VLDB	6.6551268e-05
6,338	RPJ: Producing Fast Join Results on Streams through Rate-based Optimization	2005	SIGMOD	5.105321e-05
6,647	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	4.9772122e-05
8,205	PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees	2010	SIGMOD	4.5593375e-05
7,840	Progressive Join Algorithms Considering User Preference	2021	CIDR	4.6371736e-05
5,511	On Producing Join Results Early	2003	PODS	5.4699346e-05