The sparse primary index

A granule is the smallest unit ClickHouse's data processing mechanics work with.

Why sparse rather than dense#

A B-tree index in a transactional database points at individual rows, because rows are looked up individually. ClickHouse instead sorts the data physically by the key, so it does not need row-level precision — it needs to know which regions of the sorted data can be skipped.

So it divides each column into granules of 8,192 rows and stores the primary key values from just one row per granule: the first. One entry per 8,192 rows makes the index small enough to fit entirely in memory, which removes index I/O from the query path.

Each data part has its own primary index, used independently. There is no global index across the table.

How a query uses it#

When a query filters on primary key columns, ClickHouse:

1. Reads the predicate on the primary key columns.
2. Loads the part's index into memory.
3. Scans index entries to determine which granules cannot match and can be skipped.
4. Loads only the surviving granules, together with the matching granules of any other columns the query needs.

Verify the skipping yourself#

EXPLAIN indexes = 1 reports exactly how many parts and granules survived pruning:

EXPLAIN indexes = 1
SELECT
    max(price)
FROM
    uk.uk_price_paid_simple
WHERE
    town = 'LONDON' AND street = 'OXFORD STREET';

         ReadFromMergeTree (uk.uk_price_paid_simple)
         Indexes:
           PrimaryKey
             Keys:
               town
               street
             Condition: and((street in ['OXFORD STREET', 'OXFORD STREET']), (town in ['LONDON', 'LONDON']))
             Parts: 3/3
             Granules: 3/3609

Granules: 3/3609 is the number to read. Out of 3,609 granules in the table, three were loaded:

1 row in set. Elapsed: 0.010 sec. Processed 24.58 thousand rows, 159.04 KB (2.53 million rows/s., 16.35 MB/s.)
Peak memory usage: 13.00 MiB.

The table holds 29,556,244 rows. The query processed about 24,580 of them.

Count index entries per part#

One index entry corresponds to one granule, so counting marks tells you how many granules a part contains:

SELECT
    part_name,
    max(mark_number) AS entries
FROM mergeTreeIndex('uk', 'uk_price_paid_simple')
GROUP BY part_name;

   ┌─part_name─┬─entries─┐
1. │ all_2_2_0 │     914 │
2. │ all_1_1_0 │    1343 │
3. │ all_0_0_0 │    1349 │
   └───────────┴─────────┘

The same count appears as marks in system.parts.

When the index does nothing#

The index only prunes when the filter matches the key, in key order. Three cases where it does not help:

• The filter names a non-key column. All granules are read. Use a data-skipping index or projection instead.
• The filter skips the first key column. A key of (town, street) filtered only by street prunes little, because rows for one street are scattered across every town's range.
• ORDER BY on a non-key column. Sorting the result set requires reading every row first.

A GROUP BY over a non-key column on a 30-million-row table reads all 30,033,199 rows. That is expected behaviour, not a misconfiguration — it means the key does not serve that query.

Related#

• Choose a primary key — which columns to put in the key and in what order
• MergeTree and data parts — where the index physically lives
• Optimize query performance — tools for queries the primary index cannot serve