Moving HyperLogLog sketches from BigQuery to ClickHouse without the raw data

An enterprise customer kept its audience analytics in BigQuery the way BigQuery recommends: not as raw user IDs but as HyperLogLog sketches, the BYTES values that HLL_COUNT.INIT produces. One sketch per campaign per day, rolled up at query time with HLL_COUNT.MERGE to answer questions like “how many distinct people saw this campaign last quarter?”

Those numbers needed to move to ClickHouse. That meant a column of uniqCombined64 states that could be merged across days, campaigns and arbitrary groupings, exactly like the BigQuery column it replaced.

The obvious migration is to re-read the raw events and rebuild every sketch in ClickHouse. It’s also the one you often can’t do. The raw data is huge, expensive to re-scan, sometimes past its retention window, and sometimes something you’d rather not copy at all. The sketches are the durable artifact. So the question became: can a BigQuery sketch become a ClickHouse sketch directly?

It can. Here’s how, and the handful of places where the details decide whether you get correct numbers or a column of silent zeros.

A sketch is an array, not a set

HyperLogLog doesn’t store values. It hashes each value, uses the first p bits of the hash to pick one of 2^p buckets, and in that bucket keeps the maximum rank it has ever seen. The rank is the number of leading zeros in the rest of the hash, plus one. Long runs of zeros are rare, so the maximum rank across buckets says something about how many distinct values went in. The estimate is a bias-corrected harmonic mean over those ranks, with a switch to linear counting when many buckets are still empty.

Everything the estimator needs is in that array of 2^p small integers. BigQuery’s implementation (Google’s open-source ZetaSketch, an HLL++ variant) and ClickHouse’s uniqCombined64 both maintain exactly this structure. They just write it down differently:

Aspect	ZetaSketch (BigQuery)	ClickHouse uniqCombined64
Envelope	protobuf message	one marker byte, then a fixed layout
Small cardinalities	sparse list of (bucket, rank) pairs	the raw hash values themselves
Large cardinalities	one byte per bucket	6 bits per bucket, bit-packed
Bookkeeping	none stored	rank histogram and a zeros counter

So the conversion isn’t a recomputation. It’s a transcode: read the register array out of one encoding and write it into the other. Nothing is hashed, and the original values are never needed.

Why different hash functions don’t matter

This was the first objection I had to answer, including to myself. BigQuery takes the bucket index from the high bits of Google’s hash, and ClickHouse takes it from the low bits of its own, completely different, hash. Feed the same user IDs into both systems and you get two unrelated arrays. How can copying bucket i to bucket i possibly be valid?

Because we’re not inserting values, we’re moving an array that has already been built. A bucket index is an opaque label. Bucket 7 is just “the slot holding the maximum rank for one 1/2^p slice of hash space”. The estimator never asks which slice produced which rank. It reads:

• the multiset of ranks, which drives the harmonic mean,
• the number of empty buckets, which drives linear counting,

and merging two sketches is a per-bucket max.

A direct index-to-index copy is a consistent relabelling of slices. It changes none of those quantities, and because every converted sketch is relabelled the same way, merges between converted sketches stay correct.

What the relabelling does not preserve is compatibility with sketches ClickHouse builds itself from the same underlying values. A native sketch and a converted sketch are two independent samplings of one population, with the same user in unrelated buckets in each. Merge them and you double-count. That turns into the single most important operational rule, covered further down.

Reading ZetaSketch

A BigQuery sketch is a serialized proto2 AggregatorStateProto. The HLL++ payload lives in extension field 112, and it can take one of two representations.

Dense. Once enough distinct values have arrived, the payload holds exactly 2^p bytes, one per bucket, with 0 meaning “never set”. This maps straight onto the register array.

Sparse. At low cardinality, most buckets are empty, so ZetaSketch stores a sorted list of integers encoded as varint differences. Each integer packs a bucket and a rank, but it does so at a finer sparse precision sp (up to 25 bits) than the normal precision p. A flag bit distinguishes two layouts:

 flag = 0 │ padding             │ sparse index (sp bits)
 flag = 1 │ padding │ normal index (p bits) │ rank (6 bits)

 flag position = max(sp, p + 6)

When the flag is 0, the normal bucket is the top p bits of the sparse index, and the rank is recovered from the leading zeros of the sp − p bits below it. When those bits are all zero, the rank can’t be recovered from them, so ZetaSketch switches to the flag-1 form and stores the rank explicitly. Several sparse entries can land in the same normal bucket, and the maximum wins, which is exactly what ZetaSketch does itself when it upgrades from sparse to dense.

Two further details matter for correctness:

• Only encoding_version = 2 is accepted. Version 1 used a different sparse scheme, and misreading it would produce counts that look plausible and are wrong. Nothing BigQuery emits today is v1, so the decoder rejects it with a clear error instead of guessing.
• Bounds are enforced before any bit shifting. A corrupt sketch claiming sp = 200 would otherwise shift past the width of a 32-bit word.

Precision folding, never invention

If BigQuery built a sketch at a higher precision than the ClickHouse column uses, it can be folded down. Bucket i maps to i >> (p − p′), and each rank is adjusted for the index bits being dropped. If a dropped bit was set, the highest one determines the new rank. If they were all zero, the run of leading zeros just got longer, so the rank grows by p − p′. Each target bucket takes the maximum over its group. This is the standard HLL++ downgrade, and it matches ZetaSketch’s own downgradeRhoW.

Folding up is refused outright. A coarse sketch contains no information to reconstruct a finer one, and quietly padding it would produce confidently wrong numbers.

Writing ClickHouse’s uniqCombined64

uniqCombined64(K) isn’t a single structure. It’s a combined estimator that picks one of three containers depending on cardinality, and writes a marker byte saying which one follows:

Marker	Container	Holds	Used up to
1	SMALL	the hash values, flat array	16 values
2	MEDIUM	the hash values, hash set	2^(K−5), i.e. 1,024 at K = 15
3	LARGE	dense HyperLogLog registers	unbounded

SMALL and MEDIUM store hash values, and a sketch threw those away when it was built. So every converted state is written as LARGE, even one representing a single user. ClickHouse reads a LARGE state correctly at any cardinality, and merging a converted LARGE with anything else works, because a merge promotes to the widest container. The cost is size: a converted state is always 24,783 bytes at K = 15. That’s worth budgeting for if you have millions of tiny sketches.

The LARGE body has three parts, with no header:

1. The registers, 6 bits each, packed LSB-first. Bucket i occupies bits [6i, 6i + 6) of one little-endian bitstream, so buckets straddle byte boundaries:

 byte 0      byte 1      byte 2
 11111100    22222211    33333322     bucket 0 = bits 0–5 of byte 0
                                      bucket 1 = bits 6–7 of byte 0 + bits 0–3 of byte 1

At K = 15 that’s exactly 24,576 bytes. ClickHouse keeps a trailing padding byte in memory for branchless access, but it doesn’t serialize it. Get that detail wrong and every state is off by one byte.

2. A rank histogram. ClickHouse doesn’t rescan the registers to estimate. It maintains a UInt32 count of how many buckets hold each rank: 51 entries, 204 bytes at K = 15. A converter has to rebuild it from the registers. Start with every bucket at rank 0, then move one bucket per non-zero register into its rank.

3. A zeros counter. This is the number of untouched buckets, stored in the narrowest unsigned type that fits: 2 bytes at K = 15.

That makes 1 + 24,576 + 204 + 2 = 24,783 bytes, every time.

Running it inside ClickHouse

A standalone converter would mean exporting sketches, converting them outside the database, and loading them back. I wanted the conversion to happen inside an ordinary INSERT … SELECT, so it could run partition by partition, in a materialized view, or from Airflow, with nothing new to operate.

ClickHouse supports this through executable UDFs. The server spawns a pool of long-lived child processes and streams rows to them over stdin and stdout. The converter is a small Rust library plus a single statically linked binary (built against musl, so it doesn’t care which glibc the server image ships), registered as zetasketch_to_uniq_combined64_p15. From SQL, a migration looks like any other insert:

INSERT INTO audience_daily
SELECT dte, campaign_id, zetasketch_to_uniq_combined64_p15(unhex(sketch_hex))
FROM audience_daily_raw
WHERE dte = {day:Date};

Getting there meant learning three things the documentation leaves you to discover:

1. The chunk header is text. With send_chunk_header on, each block starts with its row count, written as ASCII digits followed by a newline, not as a binary integer. Reading it as a UInt64 desyncs the stream on the first row.
2. The output has no length prefixes. The input argument is a String, which RowBinary length-prefixes. The return value is an AggregateFunction, which it doesn’t: ClickHouse relies on the state being self-terminating. Add a prefix anyway and nothing errors. ClickHouse reads the prefix’s first byte as a container marker, matches nothing, and silently leaves the state empty. Every row comes back as 0.
3. Where the files go is strict. The registration XML must sit in the config root and match a *_function.*ml glob. It must not be in config.d/, where it gets merged into server config and never loaded as a function. The binary must live in the user-scripts directory, referenced by a bare name. And a -- inside an XML comment, the most natural thing to write when documenting a command line, invalidates the whole file.

The process lifecycle needed care too. One pooled process serves many queries, so a single malformed row must never crash it and take unrelated queries down with it. A bad row becomes ClickHouse’s empty state and contributes nothing, just like a NULL. That leniency has an obvious failure mode: a systematically unconvertible column looks like a column of zeros. Two things push back on that. The configured precision is validated at startup, so the most likely misconfiguration fails loudly before any row is read. And the first failure plus a final tally go to stderr, capped at three lines per process, because ClickHouse doesn’t reliably drain a UDF’s stderr, and an unbounded log would eventually block the process mid-write.

Proving it’s correct

Sketch conversion is exactly the kind of code that can look right and be wrong, because a subtly broken sketch still produces a believable number. So the rule for validation was that both ends of every check are bytes produced by the real systems, never fixtures written by hand to match my own assumptions.

Byte-exact against ClickHouse’s own serializer. This is the check that can’t pass by coincidence. I took a real uniqCombined64State(15) blob that ClickHouse 24.8 wrote for 100,000 values, parsed out its registers with an independent reader, re-encoded from the registers alone, and compared. All 24,783 bytes were identical. A second test confirms ClickHouse’s own histogram and zeros counter are exactly what the register array implies, which pins down my reading of those trailing fields instead of assuming it.

Real BigQuery sketches, both representations. Fixtures come straight from HLL_COUNT.INIT over synthetic inputs, sized to cross the sparse-to-dense boundary, so both decode paths run against Google’s actual bytes.

End-to-end agreement. Each fixture was converted and finalized in ClickHouse, then compared with BigQuery’s own HLL_COUNT.EXTRACT:

Distinct values	BigQuery	ClickHouse after conversion	Drift
1	1	1	0%
25	25	25	0%
5,000	5,004	5,001	0.06%
50,000	49,886	49,706	0.36%

The drift isn’t a conversion error. The registers are identical, but each engine applies its own bias-correction tables on top of the same raw harmonic mean. At 1 and 25 values both fall back to linear counting over a nearly empty array, which is effectively exact. At higher cardinality they differ by a fraction of HyperLogLog’s own standard error (about 0.6% at precision 15).

Real production sketches. Finally, a sample of genuine production sketches from the customer’s table: every row converted, with zero failures. Those were pulled read-only for the check and never stored alongside the code.

Operating it without surprises

A few rules for running this on a sharded, replicated cluster:

• Install on every node, first. The function is evaluated wherever the data lives, so every shard and every replica needs the binary and the registration before the first query that uses it. Skipped replicas show up as intermittent failures weeks later.
• Keep the raw export. Land the hex-encoded sketches in a staging table and convert from there. Conversion becomes a pure transformation you can re-run without going back to BigQuery.
• Backfill a partition at a time. A failure then costs one day, not a month, and memory stays flat. After each partition, count rows that finalize to zero. A non-zero count that the source data doesn’t explain means rows failed to convert.
• Never mix lineages. Converted sketches and ClickHouse-native sketches over the same population go in separate columns. This is the only way to get a badly wrong number out of an otherwise correct system.

What I’d take to the next problem

The most useful move was refusing the framing of the problem. “Migrate distinct counts” sounded like “re-process the raw data”. Asking what the data actually is, an array of ranks with two different envelopes, turned a large, slow, expensive backfill into a byte-level transcode.

The rest was discipline around failure modes that don’t announce themselves. Sketches fail silently, and executable UDFs fail silently. The work that made this trustworthy was reading both engines’ source until every byte had a citation, then validating against bytes the real systems produced, so “it looks right” was never the evidence.