MergeTree: brute force, organized

ClickHouse’s storage engine is topic 4’s LSM shapes at analytics scale: immutable sorted parts, background merges, and — because the workload is scans, not point reads — an index that is deliberately SPARSE. This chapter walks the slices of src/Storages/MergeTree/ that carry the design: parts / granules / sparse index / merges. The codebase is huge; read ONLY what’s anchored below.

1. The mental model

 table = set of immutable sorted PARTS (sorted by ORDER BY key)
 part  = one directory: one file per column + primary.idx + marks
 granule = 8192 rows (index_granularity, MergeTreeSettings.cpp:70)
 mark  = (offset_in_compressed_file, offset_in_decompressed_block)
         one mark per granule per column
 INSERT -> writes a NEW part (no in-place anything; topic 4's
           immutability), background MERGES combine parts

An LSM tree where: memtable ≈ the insert block, SSTable ≈ part, compaction ≈ merge — but no WAL-per-row, no point-read path, and the index is SPARSE because the workload is scans.

2. The sparse primary index

• primary.idx = the ORDER BY key of the FIRST row of each granule — 8192× smaller than the data; always in memory (IMergeTreeDataPart.h:424 getIndex / :425 loadIndexToCache).
• Query on the key → binary search granule RANGES: MergeTreeDataSelectExecutor::markRangesFromPKRange (:1725, used at :189) — turns a predicate into a list of MarkRanges to read.
• Marks (src/Formats/MarkInCompressedFile.h:17): two offsets, because granules live inside compressed blocks — seek to compressed offset, decompress, skip to row.

 WHERE user_id = 42 (ORDER BY user_id):
 primary.idx: [1, 800, 1600, ...]  -> binary search -> granules 3..4
 read marks[3..4] per needed column -> decompress ~16K rows, scan them

Sparse = you always over-read up to a granule; the bet is that decompress+scan of 8192 rows is cheap (vectorized) and the index stays resident. A B-tree answers “which row”; this answers “which 8192 rows”.

The pruning core is two binary searches:

#![allow(unused)]
fn main() {
// primary_idx[g] = ORDER BY key of granule g's FIRST row — 8192x
// smaller than the data, always in memory
fn mark_range(primary_idx: &[Key], lo: &Key, hi: &Key) -> Range<usize> {
    let first = primary_idx.partition_point(|k| k < lo).saturating_sub(1);
    let last = primary_idx.partition_point(|k| k <= hi);
    first..last   // for each granule: seek marks[g].compressed_offset,
}                 // decompress the block, skip to row — then just scan
}

3. Merges (topic 4 redux)

MergeTreeDataMergerMutator::selectPartsToMerge (:272) + MergeTask.h:84 — background merge selection with heuristics balancing write amplification vs part count (too many parts = slow scans, the read-amp/write-amp dial again). Specialized engines (ReplacingMergeTree, AggregatingMergeTree, SummingMergeTree) do WORK during merges — dedup, pre-aggregation — compaction-as-computation, the trick FalkorDB could steal for graph statistics.

4. Codecs (src/Compression/)

Per-column codec CHAINS (CompressionCodecMultiple.cpp): CODEC(Delta, LZ4) composes. The menu includes the time-series specials: DoubleDelta, Gorilla (XOR floats), FPC, GCD, ALP — topic 30 material. Contrast DuckDB: ClickHouse makes YOU declare the chain (or takes the default LZ4); no analyze-and-score pass.

5. What to take from the VLDB ’24 paper framing

Materialized views (AggregatingMergeTree targets) as the answer to “scans are still too slow”: precompute during ingest/merge. The architecture triangle: brute-force scan speed (ClickHouse) vs precomputation (Pinot/Druid star-tree) vs embedded convenience (DuckDB).

Questions for notes.md

1. Sparse index over-read: worst case rows decompressed for a point query with granularity 8192 and a 3-column read? Why is that fine here and fatal for OLTP?
2. Two offsets per mark: why can’t it be one? (Compression block boundaries ≠ granule boundaries.)
3. ORDER BY choice: (user_id, ts) vs (ts, user_id) — which queries does each serve, and what happens to zone maps on the second column? (Same clustering lesson as DuckDB zone maps, but declared upfront.)
4. Merge heuristics: what goes wrong with too-eager merging (write amp) vs too-lazy (read amp)? Topic 4’s leveled-vs-tiered, at part granularity.
5. M12/M22: FalkorDB stores matrices per relationship type. What’s the “part” equivalent if property columns become mergeable segments — and could a merge pre-aggregate degree stats the way SummingMergeTree does?

Done when

You can draw part → granule → mark → compressed block, walk a point query through the sparse index, and name what ClickHouse traded away (point reads, in-place updates) for scan throughput.

References

Papers

• The VLDB ’24 system paper gets its own chapter: reading-clickhouse-paper.md — read it after this code walk

Code

• ClickHouse — src/Storages/MergeTree/ (the anchors above: MergeTreeSettings.cpp, IMergeTreeDataPart.h, MergeTreeDataSelectExecutor.cpp, MergeTreeDataMergerMutator.cpp, MergeTask.h), src/Formats/MarkInCompressedFile.h, and src/Compression/ for the codec chains; a fresh shallow clone is enough