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: hf4443deb1e97b2e8
Venue: PODS
Year: 2003
Pagerank: 6.0466546e-05
Overall Rank: 5,620 | 62.33%
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,095	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012036913
4,236	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.7028998e-05
6,045	RPJ: Producing Fast Join Results on Streams through Rate-based Optimization	2005	SIGMOD	5.8882414e-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.0023948467
57	On Random Sampling over Joins	1999	SIGMOD	0.0003999751
102	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00033850505
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029805026
336	An Adaptive Query Execution System for Data Integration*	1999	SIGMOD	0.00020619345
760	Partition Based Spatial-Merge Join	1996	SIGMOD	0.0001419395
1,930	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.3453623e-05
2,007	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.182637e-05
2,853	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB	7.9179824e-05
5,701	A Parallel Processing Strategy for Evaluating Recursive Queries	1986	VLDB	6.0127868e-05
6,036	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD	5.8905221e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	249	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD
2	3,662	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
3	1,603	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	212	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB
6	250	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB
7	3,072	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD
8	6,036	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD
9	2,853	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB
10	5,473	Early Hash Join: A Configurable Algorithm for the Efficient and Early Production of Join Results	2005	VLDB