fin1te

Writing/·4 min read

Sub-20 ms lookups on trillion-row tables: ClickHouse sort keys in practice

Subscriber lookups went from full-partition scans in the hundreds of milliseconds to under 20 ms reading three granules. The fix was one line of DDL, and the reasons it works are worth knowing properly.

ClickHouseDatabasesPerformance

The largest tables on the telecom IPDR platform I work on are well past two trillion rows. The query that matters most is the simplest one: give me every record for this subscriber in this time range. For a long time it took somewhere between 260 and 400 ms.

That sounds fine until you remember it is a point lookup. A point lookup on a well-designed ClickHouse table should barely care whether the table holds five million rows or five trillion.

After changing the sort key and partitioning, the same lookup came back in 18 ms and read 24,573 rows. I benchmarked on a single table of about six billion rows so every run was repeatable, but the result holds at full size, and the rest of this post explains why.

How ClickHouse finds rows

ClickHouse does not have a B-tree. A MergeTree table stores each part’s rows sorted by the table’s ORDER BY key, one file per column, compressed in blocks.

Alongside the data it keeps a sparse primary index, primary.idx: one entry for the first row of every granule. A granule is 8,192 rows by default (index_granularity), or fewer if those rows add up to more than 10 MB (index_granularity_bytes, the adaptive granularity setting). The index is small enough to live in memory permanently, even for enormous tables, because it stores one key per eight thousand rows rather than one per row.

Each column also has a mark file that maps granule number to an offset inside the compressed column file. So a lookup is:

  1. Binary-search primary.idx for the range of granules whose keys could match.
  2. Use the marks to jump straight to those blocks in each column you asked for.
  3. Decompress and filter only those.

That only works when the filter is on the leading columns of the sort key. Filter on anything else and step 1 can’t narrow anything down, so ClickHouse reads every granule in every partition that survives partition pruning.

Why it was slow

The old table was not sorted by subscriber first. A subscriber lookup was therefore a scan of every granule in the matching partitions. ClickHouse is extremely good at scans, which is why it still came back in a few hundred milliseconds, but it was doing orders of magnitude more work than it needed to, and that work grows with the table.

The change

The access pattern is “one subscriber, one time range”, so the sort key should lead with the subscriber, then time:

CREATE TABLE ipdr_local
(
    msisdn          String,
    start_datetime  DateTime,
    -- ...
)
ENGINE = MergeTree
PARTITION BY toStartOfHour(start_datetime)
ORDER BY (msisdn, start_datetime);

Two things work together:

  • Hourly partitions mean the time range in the query drops whole partitions before the index is even consulted.
  • Subscriber first in the sort key means that inside each surviving part, all rows for one subscriber sit next to each other, and the sparse index points straight at them.

Reading the result

24,573 is not a random number. It is three granules of 8,192, minus three rows. The whole query touched about three blocks of data.

You can see this directly with EXPLAIN:

EXPLAIN indexes = 1
SELECT *
FROM ipdr_local
WHERE msisdn = '…' AND start_datetime BETWEEN '…' AND '…';

The output lists each index that was applied (MinMax, Partition, PrimaryKey) with a Granules: X/Y line. On a table sorted the wrong way for the query, the primary key line shows X equal or close to Y: the index is not helping. With the right key, X drops to a handful. Here it was three.

That is the whole trick. Not faster scanning, but not scanning. It is also why the gain holds as the table grows into the trillions: more data means more partitions and more granules, but a lookup still lands on a handful of them.

Things that are easy to get wrong

  • Partition granularity. Partitions that are too fine produce too many parts, and past a threshold ClickHouse starts delaying and then rejecting inserts with Too many parts. Hourly suits this data volume; for a smaller table it would be far too fine. Watch system.parts after a day of inserts.
  • Low cardinality first. The usual advice is to put low-cardinality columns first in the sort key because it compresses better. That is right for analytical scans and wrong for point lookups. Decide which access pattern the table exists for.
  • The second access pattern. A table can only be sorted one way. If you also need fast lookups by IP address, you need something else: a bloom_filter data-skipping index, a projection with its own ORDER BY, or a second table fed by a materialized view. Each costs storage or insert throughput; pick knowingly.
  • Changing it later. You cannot rewrite a table’s ORDER BY in place beyond appending newly added columns. Changing the leading column means a new table and a backfill, which at trillions of rows is a planned operation, not a hotfix.

The broader point

Most of what makes a large ClickHouse estate cheap is this kind of unglamorous detail: the right sort key, sensible partition sizes, and inserts large enough that the table does not drown in tiny parts. Together they are a big part of why the platform runs on under 180 servers when the original plan called for 1,700.