Skip indexes — prove a granule has no match, then skip it

A skip index stores per-granule summary metadata (minmax / set / bloom) that lets the engine prove 'this granule definitely does not contain a match' and skip reading it entirely — useful only when values are clustered, not random.

Previously

The sparse index narrows queries by the sort-key prefix. For predicates on OTHER columns, a second kind of index proves 'this granule definitely doesn't contain X' so the engine can skip it without reading the data.

Scene 10

Skip indexes — prove a granule lacks X

Watch
Try it
Predict
Capture

skip index badge → proves 'definitely not here'

bloom filter — 'definitely not' or 'maybe', never 'yes'

What to watch for

100 granules, each topped with a bloom_filter skip index on user_id. The query WHERE user_id = 12345 probes every badge: ~94 say 'definitely no' and grey out, 5 stay 'maybe' (one true hit + a few false positives), 1 is the actual row. The GRANULES READ counter shows 6 instead of 100.

Implementation

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

Skip-index DDL

negative, secondary, per-column

1ALTER TABLE events
2  ADD INDEX user_id_bf user_id
3  TYPE bloom_filter(0.01)
4  GRANULARITY 4;
5-- 0.01 = target false-positive rate
6-- GRANULARITY 4 = one entry per 4 * 8192 = 32768 rows

Read-path pruning

probe the badge, skip the granule

1def scan(predicate, candidate_granules, skip_index):
2    for g in candidate_granules:
3        if skip_index is None or \
4           skip_index.maybe_contains(g, predicate):
5            read_columns(g, predicate)   # 'maybe' → load + filter
6        else:
7            skip(g)                      # proven absent, no IO

BloomFilter.maybe_contains(value)

k hashes, one absent bit proves 'definitely not'

1def maybe_contains(value):
2    for h in hash_fns:                  # k independent hashes
3        if bits[h(value) % size] == 0:
4            return False                # definitely-not — skip
5    return True                         # maybe — must read

Sources

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

Scene 10 of 13, in the Read side act — Sort key, sparse primary index, skip indexes — narrowing what to scan.. Per-granule sketches (minmax / set / bloom) prove 'this granule cannot contain a match' and skip reading it — only useful when values are clustered.

Up next. Skip indexes prune at read time. The bigger lever is to PRE-COMPUTE the answer at write time — turn a billion-row scan into a two-hundred-row scan by materializing the aggregation as data lands.

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