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: 1285
Venue: PODS
Year: 2003
Pagerank: 6.2074577e-05
Overall Rank: 5,467 | 62.50%
DOI: 10.1145/773153.773167

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; San Jose State University)
4. Peter Widmayer (ETH Zurich)

BibTeX Citation

@inproceedings{dittrich_pods03,
        address = {New York, NY, USA},
        series = {{PODS} '03},
        title = {{On Producing Join Results Early}},
        url = {https://dl.acm.org/doi/10.1145/773153.773167},
        doi = {10.1145/773153.773167},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Dittrich, Jens-Peter and Seeger, Bernhard and Taylor, David Scot and Widmayer, Peter},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,064	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012336248
4,138	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.8779166e-05
5,911	RPJ: Producing Fast Join Results on Streams through Rate-based Optimization	2005	SIGMOD	6.0443263e-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.0024089429
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00034590762
131	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00030424509
328	An Adaptive Query Execution System for Data Integration*	1999	SIGMOD	0.00021081317
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
1,880	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5562066e-05
1,993	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.3421788e-05
2,787	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB	8.1205738e-05
5,563	A Parallel Processing Strategy for Evaluating Recursive Queries	1986	VLDB	6.1716947e-05
5,897	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD	6.0472244e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,364	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD
2	3,617	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
3	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
4	360	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD
5	209	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB
6	252	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB
7	3,011	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD
8	5,897	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD
9	2,787	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB
10	5,663	Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results	2005	VLDB