On Producing Join Results Early

Summary: Introduces a modified sort-merge join that interleaves join steps with selected merge phases to produce early (progressive) join results while preserving overall I/O-efficiency. Provides the first analytical tradeoff bounds and applies to many sort-based joins (equi, spatial, temporal, band, similarity). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1286
Venue: PODS
Year: 2003
Pagerank: 5.4648346e-05
Overall Rank: 5,523 | 61.62%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,425	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012044433
4,244	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.3228453e-05
6,349	RPJ: Producing Fast Join Results on Streams through Rate-based Optimization	2005	SIGMOD	5.0957869e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040465394
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
75	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057450043
216	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00033560137
396	An Adaptive Query Execution System for Data Integration*	1999	SIGMOD	0.00024439334
923	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015254021
2,119	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5036401e-05
2,285	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.1097273e-05
3,211	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB	7.3780807e-05
5,754	A Parallel Processing Strategy for Evaluating Recursive Queries	1986	VLDB	5.3391931e-05
6,212	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD	5.1499439e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
230	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00032145125
3,519	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.0181381e-05
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
538	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00020632609
350	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00026368305
403	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00024176677
2,599	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD	8.4655075e-05
6,212	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD	5.1499439e-05
3,211	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB	7.3780807e-05
5,916	Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results	2005	VLDB	5.269117e-05