Interval trees and stabbing queries
Why is pruning a stabbing query over intervals, and how do distributed engines join on ranges?
The constraint changes shape. Every structure above indexes points on a totally ordered domain. An interval is not a point, and intervals are not totally ordered: [1, 10] and [5, 6] are neither before nor after each other. So one descent through a 1-D sorted structure cannot answer "which stored intervals contain x?" (a stabbing query) or "which overlap [a, b]?" You need either:
- augmentation: store, in each subtree, the maximum end point, so you can skip a branch that cannot reach into the query; this is the interval tree; or
- a different decomposition: a segment tree, an R-tree, or a space-filling curve that maps a multi-dimensional problem back to one dimension at the cost of some distortion of locality. (Multi-dimensional spatial indexing is a specialization; the one-dimensional interval and range case stays here because it is universal: temporal validity, pruning and as-of joins.)
Why this matters far beyond its niche reputation
A min-max zone map (for each file, the minimum and maximum value of a column) is a set of intervals. "Which files could contain key k?" is a stabbing query. Every pruning decision in a modern data lake is an interval problem. So the effectiveness of pruning is governed entirely by interval overlap, not by the existence of statistics.
Example. If files are written in arrival order, and the pruning column (say, tracking_id) is not correlated with arrival order, then every file's [min, max] spans nearly the whole domain. Every stabbing query returns every file. Your statistics are perfectly maintained and completely useless.
This is the mechanism behind all clustering advice. Sorting, or Z-ordering (interleaving the bits of several columns to sort by several at once) on the pruning column is an operation to reduce interval overlap. Z-ordering in particular accepts more overlap in each single dimension in exchange for less overlap across several. There is no way to have low overlap in every dimension at once; that is the multi-dimensional version of "you can only sort a table by one thing."
The distributed form is always binning
Augmented interval trees are elegant and essentially undistributable. A distributed range or as-of join instead cuts the domain into fixed bins and replicates each interval into every bin it touches, about (mean interval length ÷ bin width) + 1 times. The operator, its optimal bin width and its heavy-tail failure are on range and interval joins.
Where you meet intervals in data engineering: SCD2 validity ranges (a slowly changing dimension table where each row is valid from one date to another), as-of and temporal joins, time-series chunk selection, file pruning, and any "which version was live at time t" question.