Granules and the sparse primary index

Rows are grouped into 8192-row blocks called granules, and the primary index keeps one entry per granule — small enough to fit the whole table's index in RAM — so binary search picks the granule range in microseconds.

Previously

If rows inside a part are sorted, the engine doesn't need an index entry per row — it can keep one entry per group of 8192 rows and still find a range fast. That gives us an index small enough to keep entirely in memory.

Scene 09

Granules and the sparse primary index

Watch
Try it
Predict
Capture

What to watch for

A WHERE service='api' AND ts > T query enters. The primary.idx (in RAM) is binary-searched in O(log G) ≈ 7 hops; granules 42..47 survive and the rest stay dim. Watch the four stages.

Implementation

Highlighted lines are the ones running in the diagram right now.

Part.build_primary_index()

one entry per granule of N rows — that's the whole trick

1def build_primary_index(part):
2    g = cfg.index_granularity  # rows per granule
3    primary_idx = []
4    for start in range(0, part.rows, g):
5        granule = part.rows_sorted[start : start + g]
6        primary_idx.append(granule[0].sort_key)
7    write_file('primary.idx', primary_idx)
8    # finer g → more entries, fatter index in RAM
9    # coarser g → fewer entries, but fatter granule reads

Planner.plan_with_index(query)

binary-search primary.idx for overlapping granules; load only those

1def plan_with_index(query):
2    lo, hi = bisect_range(
3        primary_idx, query.predicate_range,
4    )
5    surviving = list(range(lo, hi + 1))
6    for gid in surviving:
7        block = mark_file.locate(gid)
8        rows  = decompress_and_read(block)
9        emit(vectorized_filter(rows, query))
10    # other granules: not a byte of .bin is read

index_size_math

why a billion-row primary.idx is ~1 MB and lives in RAM

1def primary_idx_bytes(part):
2    g = cfg.index_granularity
3    entries = part.rows // g            # N_rows / granule_size
4    return entries * sizeof(sort_key_tuple)
5 
6def rows_pulled_per_match(part):
7    # one surviving granule still loads g rows;
8    # vectorized filter discards the non-matches.
9    return cfg.index_granularity

Sources

Where this sits in Build a columnar OLAP store (ClickHouse / Druid style)

Scene 09 of 13, in the Read side act — Sort key, sparse primary index, skip indexes — narrowing what to scan.. Rows are grouped into 8192-row granules; one index entry per granule keeps the whole table's index in RAM, binary-searched in microseconds.

Up next. The sparse index narrows a query to a granule range using the sort-key prefix. For predicates on OTHER columns — not in the sort key — we need a second kind of index that can prove 'this granule definitely doesn't contain X'.

All 13 scenes in Build a columnar OLAP store (ClickHouse / Druid style) · Every curriculum

Built with Arqly

Every scene in Build a columnar OLAP store (ClickHouse / Druid style) builds on the one before it.All 13 Build a columnar OLAP store (ClickHouse / Druid style) scenes