Learning Objectives
- Explain why ClickHouse's primary index can be a flat, sorted array searched with binary search, rather than a self-balancing tree structure like a B-tree
- Describe what a single index entry (a "mark") actually stores, and how binary search over those marks narrows a scan to a contiguous range of granules
- Predict how changing index_granularity affects the size of the primary index, the amount of over-read per matched query, and the cost of searching the index itself
- Explain why making granules smaller isn't a free way to improve query performance
Why This Matters
The the-wrong-index-is-fine lesson told you what the primary index does — it skips whole granules, not rows — and why a filter that misses it is forgiving rather than catastrophic. What it left as a black box is the mechanism: what that index actually looks like, and how ClickHouse turns "this table has thousands of index entries" into "we read exactly 40 granules" without checking every entry one at a time. That mechanism turns out to be almost embarrassingly simple — a sorted array and a binary search — and seeing it plainly is what lets you reason about a setting you'll actually encounter, index_granularity, instead of just leaving it alone because it looks scary.
Why the index gets to be a plain array
You already know, from loading-data in Module 2, that every INSERT sorts its block by the table's ORDER BY expression before writing a part. That fact does almost all the work here. If a part's rows are physically sorted by the primary key, then "the primary key value of granule 0's first row," "granule 1's first row," "granule 2's first row," and so on form a sequence that never decreases — each entry is greater than or equal to the one before it.
A sequence that's guaranteed to be monotonic is exactly the condition a binary search needs: repeatedly check the middle of a range, and use the fact that everything on one side is guaranteed smaller (or larger) to throw away half the remaining candidates, without ever looking at them. A general-purpose index that has to support arbitrary inserts and deletes at any position — the situation a B-tree is built for — needs a self-balancing tree to keep that kind of guarantee cheap to maintain as data changes. ClickHouse's primary index doesn't have that problem: a part, once written, never changes. There's nothing to rebalance. So instead of a tree, the index for a part can be exactly what it needs to be and nothing more: an uncompressed, flat, sorted array.
What one entry actually holds
Each entry in that array is called a mark, and a mark holds exactly one thing: the primary key column values of the first row of the granule it corresponds to. Not a hash. Not a count. Not a pointer into every row of the granule. Just the key values that row happens to have — because, in a sorted part, that value alone is enough to say "no row before this point in the file can be smaller than this."
events is ORDER BY (event_type, event_time), 50,000,000 rows, ~6,100 granules
mark event_type event_time (first row of the granule)
──── ────────── ─────────────────────────────────────
0 click 2024-01-01 00:00:03
1 click 2024-01-04 11:42:17
... ... ...
2100 click 2024-05-30 22:58:04
2101 page_view 2024-01-01 00:00:11
... ... ...
3800 page_view 2024-06-12 09:03:51
3801 purchase 2024-01-01 00:01:47
... ... ...
5200 purchase 2024-08-19 14:20:00
5201 refund 2024-01-02 07:15:33
... ... ...
6099 refund 2024-12-31 23:59:41
Reading that table top to bottom, event_type never decreases — every click mark sits before every page_view mark, which sits before every purchase mark, exactly because the underlying data is sorted by (event_type, event_time) before it's ever written. That's the whole structure. No branching, no child pointers, no rebalancing logic — just ~6,100 small rows sitting in order, small enough as a whole to live comfortably in memory even though the table behind it has 50 million rows.
Binary search is what "Granules: 40/5000" actually costs
When a query filters on the first column of ORDER BY — the case the previous lesson called "matches the prefix" — ClickHouse runs exactly this binary search over the mark array to find the contiguous run of marks whose granule could contain a match. That's the mechanism behind the EXPLAIN indexes = 1 output from the previous lesson:
"Indexes": [
{
"Type": "PrimaryKey",
"Keys": ["event_type", "event_time"],
"Condition": "and((event_type in ['purchase', 'purchase']), (event_time in (2024-06-01, +inf)))",
"Parts": "3/12",
"Granules": "40/6100"
}
]
"Granules": "40/6100" doesn't come from ClickHouse checking all 6,100 marks and keeping the 40 that match. It comes from a binary search — roughly $\log_2(6100) \approx 13$ comparisons — that lands directly on the boundary marks for 'purchase', then narrows the result further using event_time (the mechanics of narrowing on a second key column are the next lesson's subject). Doubling the table to 12,200 granules doesn't double that search cost; it adds exactly one more comparison. That's the property that makes the whole scheme scale: the index can grow into the millions of marks for a huge table, and finding the matching range still costs a small, roughly constant number of comparisons.
Common Misconception
"Lowering index_granularity (say, from the default 8,192 down to a few hundred) is a free way to make queries faster — smaller granules mean less over-read, so there's no downside."
The over-read half of that reasoning is correct: a smaller granule means the sparse index can point closer to the exact row, so a matched range pulls in less extra data — the index_granularity * 2 extra-rows cost from the previous lesson shrinks right along with the granule size. What the reasoning misses is that granule count and mark count are the same number. Cut index_granularity by 16x and you don't just get finer boundaries — you get roughly 16x more marks in the index array, which is 16x more memory the array occupies, in every process holding that table's parts. The search itself barely notices — binary search grows logarithmically, so 16x more marks costs a few extra comparisons, not 16x more work — but the index has to be held in memory in full before any of those cheap comparisons can happen at all. "Smaller granules, less over-read" is real. "Free," it isn't: the bill shows up as RAM, not as search time.
Predict, Then Verify
Two versions of the same 50,000,000-row events table exist, both ORDER BY (event_type, event_time). Table A uses the default index_granularity of 8,192 (~6,100 marks). Table B is created with index_granularity = 512 — 16x smaller granules.
For a query with WHERE event_type = 'purchase' AND event_time > '2024-06-01' that matches the ORDER BY prefix on both tables, predict, for Table B relative to Table A:
- Roughly how many marks does Table B's primary index array hold?
- Does the amount of extra, non-matching data read within the matched range go up, down, or stay the same?
- Does the number of binary-search comparisons needed to find the matching range go up by roughly the same factor as the mark count?
Reveal the answer →
-
About 16x more marks — roughly 97,700, since granule count scales inversely with granule size at a fixed row count (50,000,000 ÷ 512 ≈ 97,656).
-
Down, and by roughly the same 16x factor. The best-case over-read bound is
index_granularity * 2extra rows per matched range: about 16,384 rows for Table A's 8,192-row granules, versus about 1,024 rows for Table B's 512-row granules. Smaller granules really do mean less wasted reading. -
No — nowhere close to 16x. Binary search cost is logarithmic in the number of marks: $\log_2(6100) \approx 13$ comparisons for Table A, $\log_2(97700) \approx 17$ comparisons for Table B. Going from 6,100 to 97,700 marks — a 16x increase — costs about 4 extra comparisons, not 16x more. The real cost of Table B's smaller granularity isn't a slower search; it's a primary index array that's roughly 16x larger and has to be held fully in memory before that fast search can even run.
Summary
ClickHouse's primary index can be a plain, flat, sorted array — not a self-balancing tree — because MergeTree parts are immutable and physically sorted by ORDER BY at write time, which guarantees the array's values never decrease as you move through it. Each entry, called a mark, stores nothing but the primary key column values of its granule's first row. Because the array is sorted, ClickHouse finds the contiguous range of marks a query's filter could match using binary search, at a cost that grows logarithmically with the number of marks — roughly 13 comparisons for a 6,100-mark index, and still only around 17 for one sixteen times larger. That's the mechanism behind an EXPLAIN line like "Granules": "40/5000": a small number of cheap comparisons, not a linear check of every mark. index_granularity is the dial controlling how many marks exist in the first place: shrinking it reduces the over-read a matched query pays for, but grows the mark count — and the memory the fully-loaded index array occupies — by roughly the same factor, while barely touching how expensive the search itself is.
Quiz
1. Why can ClickHouse's primary index be a plain sorted array instead of a self-balancing tree structure like a B-tree?
2. What does a single mark in the primary index actually store?
3. A table's primary index has 6,100 marks. A query filters on the leading ORDER BY column and EXPLAIN reports "Granules": "40/6100". Roughly how did ClickHouse arrive at that number?
4. A table's index_granularity is lowered from 8,192 to 512 (16x smaller granules), with the row count unchanged. What happens to the number of binary-search comparisons needed to find a matching range?
5. A team lowers index_granularity table-wide to shrink over-read on their largest table, reasoning that finer granules can only help. What real cost does that reasoning overlook?