Diag-Join: An Opportunistic Join Algorithm for 1:N Relationships

Summary: Diag-Join exploits time-of-creation clustering to enable an opportunistic join for 1:N relations. It outperforms block-wise nested-loop join, GRACE hash join, and index nested-loop join on clustered data and provides an analytical cost model. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h71727dfb2b7303d9
Venue: VLDB
Year: 1998
Pagerank: 5.7073875e-05
Overall Rank: 6,690 | 55.03%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Sven Helmer (University of Mannheim)
2. Till Westmann (University of Mannheim)
3. Guido Moerkotte (University of Mannheim)

BibTeX Citation

@article{helmer_vldb98,
        title = {{Diag-Join: An Opportunistic Join Algorithm for 1:N Relationships}},
        author = {Helmer, Sven and Westmann, Till and Moerkotte, Guido},
        journal = {PVLDB},
        series = {{VLDB} '98},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,387	How Soccer Players Would do Stream Joins	2011	SIGMOD	0.00010825457
5,530	Generalized Hash Teams for Join and Group-by	1999	VLDB	6.0935245e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00081992507
82	Hashing Methods and Relational Algebra Operations	1984	VLDB	0.00036053776
156	Multiprocessor Hash-Based Join Algorithms	1985	VLDB	0.00028522117
656	An Overview of The System Software of A Parallel Relational Database Machine GRACE	1986	VLDB	0.00015069885
853	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB	0.00013444911
920	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB	0.00013081835
1,314	A Low Communication Sort Algorithm for a Parallel Database Machine	1989	VLDB	0.00011058431
2,267	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB	8.7222779e-05
3,672	FastSort: A Distributed Single-Input Single-Output External Sort	1990	SIGMOD	7.1098491e-05
4,136	Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases	1994	VLDB	6.7872141e-05
6,582	Indexing Multiple Sets	1994	VLDB	5.7441203e-05
7,854	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB	5.4401441e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,287	On Spatially Partitioned Temporal Join	1994	VLDB
2	1,034	A Scalable, Predictable Join Operator for Highly Concurrent Data Warehouses	2009	VLDB
3	1,514	Computing Joins Of Relations	1975	SIGMOD
4	853	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB
5	7,609	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD
6	3,494	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS
7	4,642	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD
8	3,660	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
9	4,063	Event-Join Optimization in Temporal Relational Databases	1989	VLDB
10	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB