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.4699346e-05
Overall Rank: 5,511 | 61.67%
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.00012051353
4,245	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.3272687e-05
6,338	RPJ: Producing Fast Join Results on Streams through Rate-based Optimization	2005	SIGMOD	5.105321e-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.0040449103
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
76	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057303551
217	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00033536712
394	An Adaptive Query Execution System for Data Integration*	1999	SIGMOD	0.00024460855
925	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015264328
2,094	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5547223e-05
2,281	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.1077704e-05
3,204	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB	7.3889212e-05
5,743	A Parallel Processing Strategy for Evaluating Recursive Queries	1986	VLDB	5.3442345e-05
6,214	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD	5.1546943e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,647	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	4.9772122e-05
3,515	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.0220813e-05
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
540	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.0002063443
351	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.0002636504
404	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00024143076
2,640	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD	8.3924401e-05
6,214	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD	5.1546943e-05
3,204	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB	7.3889212e-05
5,906	Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results	2005	VLDB	5.2787348e-05