An Evaluation of Non-Equijoin Algorithms

Summary: Proposes a partitioned band join for non-equijoins; analyzes it against an optimized sort-merge baseline with analytical models and a WiSS implementation. Partitioned band join outperforms sort-merge unless memory is tight or inputs are equal size; a parallel Gamma DB version demonstrates scalable speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hf911a1d5f286804d
Venue: VLDB
Year: 1991
Pagerank: 0.00024275691
Overall Rank: 220 | 98.53%
DOI: -

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{dewitt_vldb91,
        title = {{An Evaluation of Non-Equijoin Algorithms}},
        author = {DeWitt, David J. and Naughton, Jeffrey F. and Schneider, Donovan A.},
        journal = {PVLDB},
        series = {{VLDB} '91},
        pages = {443--452},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
60	The Merge/Purge Problem for Large Databases	1995	SIGMOD	0.00039343755
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00032945275
112	TelegraphCQ: Continuous Dataflow Processing for an Uncertain World	2003	CIDR	0.00032341214
180	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026534482
201	Continuously Adaptive Continuous Queries over Streams	2002	SIGMOD	0.00025363666
202	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025244506
359	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00019963275
867	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00013342302
1,569	Reducing the Braking Distance of an SQL Query Engine	1998	VLDB	0.00010177494
1,598	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00010096339
1,926	Predictable Performance for Unpredictable Workloads	2009	VLDB	9.3500398e-05
2,429	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	8.4657925e-05
2,704	Executing Stream Joins on the Cell Processor	2007	VLDB	8.0950719e-05
3,307	Lightning Fast and Space Efficient Inequality Joins	2015	VLDB	7.4203464e-05
3,517	Coalescing in Temporal Databases	1996	VLDB	7.220733e-05
4,227	Accelerating Queries with Group-By and Join by Groupjoin	2011	VLDB	6.7087461e-05
5,170	Conjunctive Queries with Inequalities Under Updates	2018	VLDB	6.2330027e-05
5,469	High-Performance Row Pattern Recognition Using Joins	2023	VLDB	6.1022571e-05
5,506	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.0883761e-05
5,523	Temporal Query Processing and Optimization in Multiprocessor Database Machines	1992	VLDB	6.0818572e-05
6,036	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD	5.8905221e-05
6,068	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.8805774e-05
6,286	On Spatially Partitioned Temporal Join	1994	VLDB	5.8064375e-05
6,743	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.6766099e-05
7,373	A Scalable and Generic Approach to Range Joins	2022	VLDB	5.5245298e-05
7,549	Algebraic Optimization of Computations over Scientific Databases	1993	VLDB	5.4809567e-05
12,565	D-Hive: Data Bees Pollinating RDF, Text, and Time	2013	CIDR	4.9605343e-05
13,050	Scalable Continuous Query Processing by Tracking Hotspots	2006	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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.00081781676
46	Benchmarking Database Systems: A Systematic Approach	1983	VLDB	0.00044656322
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00039922419
156	Multiprocessor Hash-Based Join Algorithms	1985	VLDB	0.00028431734
249	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023099455
480	Random Sampling from B+ trees	1989	VLDB	0.00017573936
1,237	Random Sampling from Hash Files	1990	SIGMOD	0.00011381076

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,972	Scalable and Adaptive Online Joins	2014	VLDB
2	5,553	Generalized Hash Teams for Join and Group-by	1999	VLDB
3	855	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB
4	5,620	On Producing Join Results Early	2003	PODS
5	6,036	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD
6	1,269	An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory	2016	SIGMOD
7	491	Practical Skew Handling in Parallel Joins	1992	VLDB
8	3,072	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD
9	249	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD
10	6,743	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD