How does ClickHouse's sparse primary index use granules to skip data in a query?

## Granules: the unit of reading A `MergeTree` part stores each column in its own compressed file, with rows in sorting-key order. Those rows are logically cut into **granules**, controlled by the table setting `index_granularity`, whose default is 8192 rows. A granule is the smallest amount of data ClickHouse will read from a column file — you cannot fetch one row, only the granule containing it. Two structures per part make this work: - The **primary index** (`primary.idx`): one entry per granule, containing the primary-key column values of the granule's *first* row. It is small — a table with a billion rows and 8192-row granules has roughly 122,000 entries per full part — and is held in memory. - The **mark files** (one per column): for each granule, the offset of the compressed block and the offset inside it. This is what converts "I want granules 40–52" into actual byte ranges in every column file the query touches. ## How a query narrows down For `WHERE tenant_id = 7 AND event_date = '2025-03-01'` on a table with `ORDER BY (tenant_id, event_date, user_id)`, execution narrows in stages: 1. **Partition pruning.** If a partition key is declared, whole partitions whose min/max cannot satisfy the predicate are dropped before any part is opened. Each part also stores min/max values for the partition-key columns, so a filter on the underlying column prunes even when the partition expression is a function of it. 2. **Primary index analysis, per part.** The condition is turned into a range over the key. Because index entries are sorted, ClickHouse binary-searches for the first and last granule whose range can intersect the condition, producing a set of granule ranges. 3. **Skipping index analysis.** Any declared data-skipping indexes then remove further granules from that set. 4. **Reading.** Marks convert surviving granules to byte ranges; only those blocks of only the referenced columns are read and decompressed, then filtered row by row — the granule almost always contains non-matching rows too, and the filter step removes them. ## Sparse, not dense — and why that matters A B-tree in an OLTP engine stores one entry per row and can fetch exactly the row you asked for. ClickHouse deliberately does not: an entry per row over billions of rows would be larger than the data it indexes and would defeat the compression that makes the columnar layout cheap. The consequence is a hard floor on read amplification. A query for a single user id, when `user_id` is the leading key column, still reads at least 8192 rows' worth of every column it selects. ClickHouse is not a key-value store, and "we'll use it for point lookups" is the classic misuse. The corollary is that the index only helps on a **leading run** of key columns. With `ORDER BY (tenant_id, event_date, user_id)`, a query filtering only on `user_id` cannot use the index at all: `user_id` is sorted only within equal `(tenant_id, event_date)`, so every granule's range covers the whole domain of `user_id`. The plan will select every granule of every part. Filtering on `tenant_id` alone prunes well; filtering on `tenant_id` and `event_date` prunes better. ## Reading the effect `EXPLAIN indexes = 1` in front of the query prints the index-analysis steps and how many parts and granules survive each of them — that is the direct evidence that pruning happened, rather than guessing from wall-clock time. Comparing the granules selected against the table's total is the diagnosis: if the number is essentially everything, the predicate does not touch a key prefix. ```sql EXPLAIN indexes = 1 SELECT count() FROM events WHERE tenant_id = 7 AND event_date = '2025-03-01'; ``` ## Practical consequences - **Sort order is the index.** There is no way to add a second primary index to a table; if a second access path is genuinely needed, the standard answers are a data-skipping index, or a second copy of the data sorted the other way. - **Cardinality of the leading column decides everything.** A leading column with two distinct values splits the table into two ranges — pruning is nearly useless. A leading column that is already the natural filter (tenant, customer, date) is what makes the pattern work. - **Many small parts weaken it.** Index analysis runs per part, and each part contributes at least one granule of reading if it cannot be excluded outright, so the same logical data spread over thousands of parts is read far less selectively than over a handful of large ones. - **The granule floor is tunable but rarely tuned.** `index_granularity` can be lowered per table to reduce read amplification for very selective lookups, at the cost of a bigger in-memory index and more marks. ## Interview traps Calling it "like a B-tree", claiming the index locates rows, or asserting that any indexed column prunes regardless of position are the three answers that end the topic. The strong answer walks parts → granules → marks and states the 8192-row floor explicitly.