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

Summary: PMJ makes sort-based joins non-blocking by emitting matches as external mergesort produces initial runs, avoiding the usual full-sort delay. Its generic framework covers join variants and probabilistic online selectivity estimation, with early output and modest runtime overhead. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9044
Venue: VLDB
Year: 2002
Pagerank: 8.1205738e-05
Overall Rank: 2,787 | 80.89%
DOI: 10.1016/B978-155860869-6/50034-2

Incoming Non-self Citations Over Time

Authors

1. Jens-Peter Dittrich (University of Marburg)
2. Bernhard Seeger (University of Marburg)
3. David Scot Taylor (ETH Zurich)
4. Peter Widmayer (ETH Zurich)

BibTeX Citation

@article{dittrich_vldb02,
        title = {{Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm}},
        author = {Dittrich, Jens-Peter and Seeger, Bernhard and Taylor, David Scot and Widmayer, Peter},
        journal = {PVLDB},
        series = {{VLDB} '02},
        doi = {10.1016/B978-155860869-6/50034-2},
        url = {https://doi.org/10.1016/B978-155860869-6/50034-2},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
670	SharedDB: Killing One Thousand Queries With One Stone	2012	VLDB	0.00015157572
1,064	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012336248
1,508	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00010540965
2,892	Scalable and Adaptive Online Joins	2014	VLDB	7.9852178e-05
4,138	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.8779166e-05
5,310	Low-Latency Handshake Join	2014	VLDB	6.2702891e-05
5,467	On Producing Join Results Early	2003	PODS	6.2074577e-05
5,663	Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results	2005	VLDB	6.1298345e-05
5,911	RPJ: Producing Fast Join Results on Streams through Rate-based Optimization	2005	SIGMOD	6.0443263e-05
7,156	The Case for Deep Query Optimisation	2020	CIDR	5.686096e-05
7,820	Parallelizing Intra-Window Join on Multicores: An Experimental Study	2021	SIGMOD	5.5373345e-05
9,017	PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees	2010	SIGMOD	5.3311284e-05
9,392	A Step Toward Deep Online Aggregation	2023	SIGMOD	5.2755515e-05
10,291	SmartRabbit: An Interactive Query Processor	2026	SIGMOD	5.093636e-05
11,194	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	5.093636e-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
1	5,640	Proximity Rank Join	2010	VLDB
2	3,011	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD
3	12,386	Efficient Rank Join with Aggregation Constraints	2011	VLDB
4	499	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB
5	3,134	Efficient Join Algorithms For Large Database Tables in a Multi-GPU Environment	2021	VLDB
6	5,911	RPJ: Producing Fast Join Results on Streams through Rate-based Optimization	2005	SIGMOD
7	5,364	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD
8	9,017	PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees	2010	SIGMOD
9	8,024	Progressive Join Algorithms Considering User Preference	2021	CIDR
10	5,467	On Producing Join Results Early	2003	PODS