A Scalable and Generic Approach to Range Joins

Summary: Introduces a fully parallel, kd-tree-based multidimensional range join supporting broad non-equi predicates alongside equality constraints. Integrated in Umbra, it delivers scalable, low-memory execution and outperforms competing systems on real and synthetic workloads. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12972
Venue: VLDB
Year: 2022
Pagerank: 5.6727648e-05
Overall Rank: 7,207 | 50.56%
DOI: 10.14778/3551793.3551849

Incoming Non-self Citations Over Time

Authors

1. Maximilian Reif (Technical University of Munich)
2. Thomas Neumann (Technical University of Munich)

BibTeX Citation

@article{reif_vldb22,
        title = {{A Scalable and Generic Approach to Range Joins}},
        author = {Reif, Maximilian and Neumann, Thomas},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {11},
        pages = {3018--3030},
        doi = {10.14778/3551793.3551849},
        url = {https://doi.org/10.14778/3551793.3551849},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,622	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	7.2465862e-05
5,321	High-Performance Row Pattern Recognition Using Joins	2023	VLDB	6.2659937e-05
6,957	Design and Analysis of a Processing-in-DIMM Join Algorithm: A Case Study with UPMEM DIMMs	2023	SIGMOD	5.7303405e-05
10,674	Parallel kd-tree with Batch Updates	2025	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00082404462
23	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.00054886415
34	The Design Of Postgres	1986	SIGMOD	0.00049302774
103	DuckDB: an Embeddable Analytical Database	2019	SIGMOD	0.00034161428
210	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00024797689
241	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD	0.00023654664
422	Umbra: A Disk-Based System with In-Memory Performance	2020	CIDR	0.00018732744
6,596	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.828647e-05
7,787	A Practical Approach to Groupjoin and Nested Aggregates	2021	VLDB	5.5449593e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,235	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD
2	11,556	Scaling Equi-Joins	2022	SIGMOD
3	3,617	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
4	9,497	Rank Join Queries in NoSQL Databases	2014	VLDB
5	3,295	Lightning Fast and Space Efficient Inequality Joins	2015	VLDB
6	2,962	To Partition, or Not to Partition, That is the Join Question in a Real System	2021	SIGMOD
7	12,386	Efficient Rank Join with Aggregation Constraints	2011	VLDB
8	7,326	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB
9	7,286	Efficient Computation of Quantiles over Joins	2023	PODS
10	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB