Database Paper Browser

Back to papers

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
8034
Venue
VLDB
Year
1991
Pagerank
0.00041010211
Overall Rank
151 | 98.96%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank Citing Paper Year Venue Pagerank
67 The Merge/Purge Problem for Large Databases 1995 SIGMOD 0.00061419648
125 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00044946098
143 TelegraphCQ: Continuous Dataflow Processing for an Uncertain World 2003 CIDR 0.00041688468
239 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00031581944
244 Continuously Adaptive Continuous Queries over Streams 2002 SIGMOD 0.00031037999
248 Efficient set joins on similarity predicates 2004 SIGMOD 0.00030888982
442 Efficient Parallel Set-Similarity Joins Using MapReduce 2010 SIGMOD 0.00023095823
1,073 Processing Theta-Joins using MapReduce* 2011 SIGMOD 0.00014255717
1,559 Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates 1997 VLDB 0.00011368746
1,780 Reducing the Braking Distance of an SQL Query Engine 1998 VLDB 0.00010558417
2,372 Predictable Performance for Unpredictable Workloads 2009 VLDB 8.940791e-05
2,768 Executing Stream Joins on the Cell Processor 2007 VLDB 8.1518597e-05
2,849 Coalescing in Temporal Databases 1996 VLDB 8.0197594e-05
3,000 BigDansing: A System for Big Data Cleansing 2015 SIGMOD 7.7447724e-05
3,575 Lightning Fast and Space Efficient Inequality Joins 2015 VLDB 6.9509846e-05
5,049 High-Performance Row Pattern Recognition Using Joins 2023 VLDB 5.7275467e-05
5,087 Accelerating Queries with Group-By and Join by Groupjoin 2011 VLDB 5.7032118e-05
5,136 Temporal Query Processing and Optimization in Multiprocessor Database Machines 1992 VLDB 5.6666995e-05
5,582 Conjunctive Queries with Inequalities Under Updates 2018 VLDB 5.4211286e-05
5,963 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 5.2485815e-05
6,170 Spatial Join Selectivity Using Power Laws 2000 SIGMOD 5.1708554e-05
6,212 Skew Handling Techniques in Sort-Merge Join 2002 SIGMOD 5.1499439e-05
6,452 On Spatially Partitioned Temporal Join 1994 VLDB 5.0519322e-05
6,618 Near-Optimal Distributed Band-Joins through Recursive Partitioning 2020 SIGMOD 4.9864636e-05
7,247 A Scalable and Generic Approach to Range Joins 2022 VLDB 4.7846107e-05
7,358 Algebraic Optimization of Computations over Scientific Databases 1993 VLDB 4.7478752e-05
12,036 D-Hive: Data Bees Pollinating RDF, Text, and Time 2013 CIDR 4.1905499e-05
12,528 Scalable Continuous Query Processing by Tracking Hotspots 2006 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

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
9 Implementation Techniques For Main Memory Database Systems 1984 SIGMOD 0.001426258
10 Benchmarking Database Systems: A Systematic Approach 1983 VLDB 0.0012093675
37 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00075597514
77 Multiprocessor Hash-Based Join Algorithms 1985 VLDB 0.00056488357
230 A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment 1989 SIGMOD 0.00032145125
352 Random Sampling from B+ trees 1989 VLDB 0.00026276293
764 Random Sampling from Hash Files 1990 SIGMOD 0.00016958917
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,384 Scalable and Adaptive Online Joins 2014 VLDB 7.153329e-05
5,329 Generalized Hash Teams for Join and Group-by 1999 VLDB 5.5652298e-05
549 Hash-Partitioned Join Method Using Dynamic Destaging Strategy 1988 VLDB 0.00020348047
5,523 On Producing Join Results Early 2003 PODS 5.4648346e-05
6,212 Skew Handling Techniques in Sort-Merge Join 2002 SIGMOD 5.1499439e-05
1,800 An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory 2016 SIGMOD 0.00010494121
548 Practical Skew Handling in Parallel Joins 1992 VLDB 0.00020369531
2,599 Design and Evaluation of Parallel Pipelined Join Algorithms 1987 SIGMOD 8.4655075e-05
230 A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment 1989 SIGMOD 0.00032145125
6,618 Near-Optimal Distributed Band-Joins through Recursive Partitioning 2020 SIGMOD 4.9864636e-05