HCIJ: Hardware-Conscious Interval Joins for Modern CPUs

Interval join is a widely used operation in temporal and spatial databases. While many algorithms have been proposed for efficiently evaluating interval joins, limited attention has been given to understanding their microarchitectural characteristics, or their ability to effectively exploit various aspects of modern CPUs, like SIMD vectorization, NUMA awareness, and thread scheduling, to enhance performance. In this work, we bridge this gap by making the following contributions: (i) We present the first microarchitectural analysis of a state-of-the-art interval join algorithm to show that it significantly underutilizes modern CPUs. We perform an in-depth root cause analysis to identify various bottlenecks that lead to such underutilization. (ii) We present HCIJ–Hardware-Conscious Interval Join, an interval join algorithm for modern, multisocket, multicore CPUs that overcomes various bottlenecks by being hardware conscious in its design for data partitioning (to balance utilization across cores), SIMD vectorization (to avoid data dependencies), handling NUMA topologies (explicit memory management), and data caching. (iii) We perform a thorough experimental evaluation to demonstrate that HCIJ is portable across multiple CPU architectures, and can outperform the state-of-the-art solutions 1.2×– 3.2× times while maintaining a smaller memory footprint.