Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Sorted runs and the sparse index

Why does sorted data need only a sparse index, and what pins the size of its granule?

This is the "no structure at all" option, and it is the dominant one in analytics, so it deserves more respect than its position in the list suggests.

The constraint. If data is sorted, position is already a function of the key, so no extra structure is needed. The problem: plain binary search is log₂(n) dependent probes (30 misses for a billion keys). That is optimal in comparisons and, in practice, the worst option in this article. Everything built on a is an attempt to reduce the number of dependent probes.

There are two escapes.

  1. Block it. Group keys into blocks of one transfer unit. This turns binary search into a B-tree and is the same derivation as before.
  2. Predict the position. If you can approximate the distribution of the keys (its CDF, the fraction of keys below each value), jump straight to an estimated offset and correct locally. does this with a straight-line model and reaches O(log log n) on uniform data, but O(n) on adversarial data (the in another costume). (RMI, PGM) generalize it to a hierarchy of fitted models. Be clear about the claim: the idea is sound and important (replace a general-purpose structure with a model of the actual data), but the production case is unsettled. Updates are hard, the wins depend on the workload, and reported speedups often compare against unrepresentative baselines. Treat learned indexes as an active research direction, not a settled technique.

The sparse index is what actually runs your industry

Parquet row-group statistics, ClickHouse's primary index with index_granularity = 8192, and Iceberg manifests with per-file column bounds are all the same design: keep one index entry per granule (a group of rows) instead of one per row, so the index is small enough to live in memory, and accept scanning one granule to find the row.

# Sparse index over a sorted file: one entry per granule of G rows.
import bisect
G = 8192
sparse_keys = [rows[i][0] for i in range(0, len(rows), G)]   # first key of each granule

def lookup(key):
    g = bisect.bisect_right(sparse_keys, key) - 1             # which granule?
    if g < 0: return None
    for row in rows[g * G:(g + 1) * G]:                       # scan one granule only
        if row[0] == key: return row
    return None

The granule size is pinned by two inequalities

This derivation is worth internalizing.

  • The granule must be at least the minimum efficient I/O of the medium. Below it you pay a full request for a partial read.
  • The index must be at most the memory budget. Above it you have moved the problem rather than solved it.

The number of index entries is n / granule, so the index size is (n / granule) × entry_size, and the memory limit gives .