Read ClickHouse - Lightning Fast Analytics for Everyone, Schulze, Schreiber, Yatsishin,
Dahimene and Milovidov, PVLDB 17(12):3731-3744, 2024.
doi:10.14778/3685800.3685802
Recording what is worth exploring, ranked, with what we already have next to it. Working
from the paper, which is a description of the design. Anything we build is ours.
Two of these I would break out into their own issues if wanted. The rest are recorded here
rather than filed, because filing a reading list as tickets is how a tracker rots.
1. Preimage rewriting for monotonic functions on the sort key
The strongest item, and it lands on a shape we measured today.
Monotonicity traits allow to infer if a function produces sorted results on sorted input
key value ranges. Second, some functions can compute the preimage of a given function
result. This is used to replace comparisons of constants with function calls on the key
columns by comparing the key column value with the preimage. For example,
toYear(k) = 2024 can be replaced by k >= 2024-01-01 && k < 2025-01-01.
We have no equivalent. grep -riE 'monoton|preimage' src/ finds two comments and no code.
Why it matters here: a predicate on date_trunc('minute', time) cannot use the zone map on
time today, because the zone map holds time and the predicate is about a function of it.
Rewritten to a range on time it prunes with the machinery we already have. This is the
q1 to q3 shape, and #391 showed time pruning is doing the real work on those queries.
It is also principled rather than a special case, which is the objection I raised against
myself on #369. The technique is a function property plus a rewrite, not a hardcoded rule
about date_trunc.
2. A sparse sort-key index over chunk groups
ClickHouse additionally stores, for every part, a mapping from the primary key column
values of each granule's first row to the granule's id, i.e. the index is sparse. The
resulting data structure is typically small enough to remain fully in-memory, e.g. only
1000 entries are required to index 8.1 million rows.
We evaluate zone maps to decide which chunk groups survive. That is linear in the number of
chunk groups. On today's bench table that is 667, which is nothing. At a hundred times the
size it is 66,700 min/max comparisons before a single row is read.
This pairs directly with today's clustering measurement. Clustering is what makes pruning
possible; a sparse index is what makes locating the surviving groups cheap. It only
works on sorted data, which is exactly what pgcolumnar.cluster and sort_by produce, so
we would already have the precondition.
Their index is per part and in memory. Ours would be per storage and would need a home.
3. Set skipping indices
- Set indices, storing a configurable number of unique values per index block. These
indexes are best used with data with small local cardinality, i.e. "clumped together"
values.
We have min/max and bloom. A set index sits between them: exact rather than probabilistic,
cheaper than bloom for low-cardinality clumped columns, and it can answer negative and IN
predicates that bloom cannot.
Our benchmark table is full of exactly this shape. region, datacenter, rack, os,
arch, team, service are all low cardinality, and after clustering they are clumped.
4. Filters ordered by descending selectivity, evaluated column by column
filters on different columns are evaluated sequentially in order of descending estimated
selectivity based on heuristics and (optional) column statistics. Only data chunks that
contain at least one matching row are passed to the next predicate.
with an explicit caveat worth keeping:
The optimization is only applied when at least one highly selective predicate is present;
otherwise the latency would deteriorate compared to an evaluation of all predicates in
parallel.
The paper attributes a visible step change in their own version-over-version benchmark to
this technique. I found no evidence we order pushed-down quals by selectivity.
5. Merge-time data transformation, including tiered storage
Their merges do work beyond compaction: replacing merges for deduplication, aggregating
merges that maintain incremental materialized views, and TTL merges that act on whole parts.
The TTL case is the one that connects to open work:
CREATE TABLE tab(ts DateTime, msg String)
ENGINE MergeTree PRIMARY KEY ts
TTL (ts + INTERVAL 1 WEEK) TO VOLUME 's3'
Aging cold data to object storage is a tiering feature, and it needs #393 and #394 first.
Our compact, recluster and vacuum rewrites are the natural place for it, since they
already rewrite.
6. Hash tables sized from runtime statistics
creation of hash tables based on predicted sizes from runtime statistics to avoid
unnecessary resizes
They select among 30-plus hash table implementations per operator and size them from
runtime statistics. #369 is a plan-time group estimate being 25 to 42 times wrong, and I
measured today that no statistics object fixes it. Sizing from what the partial aggregate
actually produced is a different answer to the same problem, and worth knowing about even
if it does not fit our node.
7. Idempotent inserts
the server maintains hashes of the last N inserted parts (e.g. N=100) and ignores
re-inserts of parts with a known hash
A retried bulk load is deduplicated by the server rather than by the client. Relevant to
pgcolumnar.parallel_copy and to the write path generally.
Two things the paper says about benchmarks that we should take
ClickBench is the denormalized benchmark and TPC-H is the normalized one. Their
ClickBench workload is 43 queries over a single 100 million row table, which is the same
single-table shape as our TSBS suite. Their TPC-H numbers are where joins appear.
That is exactly the gap #401 and #402 are about, and it suggests TPC-H rather than
something invented as the join-heavy fixture.
Even ClickHouse did not have join predicate pushdown, as of the version measured:
Queries Q7-Q9 and Q19 depend on extended plan-level optimizations for joins such as join
reordering and join predicate pushdown (both missing as of ClickHouse v24.6) to achieve
viable runtimes.
Useful calibration for #401. A team whose entire product is this saw those queries suffer
without it. It supports treating join work as a large lift with a measurement in front of
it, rather than something to reach for casually.
What I would break out
Items 1 and 2. Item 1 because it is small, principled, and aims at a shape we have measured.
Item 2 because it compounds with the clustering result and has no design risk beyond where
to put the index.
The rest I would leave recorded here until something makes one of them urgent.
Read ClickHouse - Lightning Fast Analytics for Everyone, Schulze, Schreiber, Yatsishin,
Dahimene and Milovidov, PVLDB 17(12):3731-3744, 2024.
doi:10.14778/3685800.3685802
Recording what is worth exploring, ranked, with what we already have next to it. Working
from the paper, which is a description of the design. Anything we build is ours.
Two of these I would break out into their own issues if wanted. The rest are recorded here
rather than filed, because filing a reading list as tickets is how a tracker rots.
1. Preimage rewriting for monotonic functions on the sort key
The strongest item, and it lands on a shape we measured today.
We have no equivalent.
grep -riE 'monoton|preimage' src/finds two comments and no code.Why it matters here: a predicate on
date_trunc('minute', time)cannot use the zone map ontimetoday, because the zone map holdstimeand the predicate is about a function of it.Rewritten to a range on
timeit prunes with the machinery we already have. This is theq1 to q3 shape, and #391 showed time pruning is doing the real work on those queries.
It is also principled rather than a special case, which is the objection I raised against
myself on #369. The technique is a function property plus a rewrite, not a hardcoded rule
about
date_trunc.2. A sparse sort-key index over chunk groups
We evaluate zone maps to decide which chunk groups survive. That is linear in the number of
chunk groups. On today's bench table that is 667, which is nothing. At a hundred times the
size it is 66,700 min/max comparisons before a single row is read.
This pairs directly with today's clustering measurement. Clustering is what makes pruning
possible; a sparse index is what makes locating the surviving groups cheap. It only
works on sorted data, which is exactly what
pgcolumnar.clusterandsort_byproduce, sowe would already have the precondition.
Their index is per part and in memory. Ours would be per storage and would need a home.
3. Set skipping indices
We have min/max and bloom. A set index sits between them: exact rather than probabilistic,
cheaper than bloom for low-cardinality clumped columns, and it can answer negative and
INpredicates that bloom cannot.
Our benchmark table is full of exactly this shape.
region,datacenter,rack,os,arch,team,serviceare all low cardinality, and after clustering they are clumped.4. Filters ordered by descending selectivity, evaluated column by column
with an explicit caveat worth keeping:
The paper attributes a visible step change in their own version-over-version benchmark to
this technique. I found no evidence we order pushed-down quals by selectivity.
5. Merge-time data transformation, including tiered storage
Their merges do work beyond compaction: replacing merges for deduplication, aggregating
merges that maintain incremental materialized views, and TTL merges that act on whole parts.
The TTL case is the one that connects to open work:
Aging cold data to object storage is a tiering feature, and it needs #393 and #394 first.
Our
compact,reclusterandvacuumrewrites are the natural place for it, since theyalready rewrite.
6. Hash tables sized from runtime statistics
They select among 30-plus hash table implementations per operator and size them from
runtime statistics. #369 is a plan-time group estimate being 25 to 42 times wrong, and I
measured today that no statistics object fixes it. Sizing from what the partial aggregate
actually produced is a different answer to the same problem, and worth knowing about even
if it does not fit our node.
7. Idempotent inserts
A retried bulk load is deduplicated by the server rather than by the client. Relevant to
pgcolumnar.parallel_copyand to the write path generally.Two things the paper says about benchmarks that we should take
ClickBench is the denormalized benchmark and TPC-H is the normalized one. Their
ClickBench workload is 43 queries over a single 100 million row table, which is the same
single-table shape as our TSBS suite. Their TPC-H numbers are where joins appear.
That is exactly the gap #401 and #402 are about, and it suggests TPC-H rather than
something invented as the join-heavy fixture.
Even ClickHouse did not have join predicate pushdown, as of the version measured:
Useful calibration for #401. A team whose entire product is this saw those queries suffer
without it. It supports treating join work as a large lift with a measurement in front of
it, rather than something to reach for casually.
What I would break out
Items 1 and 2. Item 1 because it is small, principled, and aims at a shape we have measured.
Item 2 because it compounds with the clustering result and has no design risk beyond where
to put the index.
The rest I would leave recorded here until something makes one of them urgent.