Sketches versus sampling for COUNT DISTINCT

Measure your machineNeeds Python with DuckDB

Problem

A sample scales additive measures well: the sum of a 1% sample times 100 estimates the total sum. Distinct counts do not scale that way, because duplicates are not spread evenly: a 1% sample sees almost every distinct value at most once, so it finds about as many distinct values as it has rows, and multiplying by 100 counts each of them a hundred times. A HyperLogLog sketch reads every row in a few kilobytes and estimates distinct counts within a percent or two.

Use DuckDB with 20 million events over 5 million possible users. Compute the exact distinct count, approx_count_distinct, and COUNT(DISTINCT user_id) * 100 over a 1% sample. Repeat with SUM(user_id) to see the sample estimate work.

The question. How far off is each distinct-count estimate, and does the sample work for a SUM?

Predict

Estimating COUNT DISTINCT users by sampling 1% of rows and multiplying by 100: how far off is it?

Within 5%5 to 50% offAbout 2× too highAbout 4× too high

Run it

1Install uv once. It fetches Python and the lab's packages for you.
Terminal
```
curl -LsSf https://astral.sh/uv/install.sh | sh
```

2Get the script. It is the whole lab: read it, then download it.

sketches-versus-sampling-for-count-distinct.py40 linesDownload

View the code

sketches-versus-sampling-for-count-distinct.py

# /// script
# requires-python = ">=3.10"
# dependencies = ["duckdb"]
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""Sketches against sampling for COUNT DISTINCT.

DuckDB, 20 million events over 5 million possible users. The exact distinct
count, approx_count_distinct (HyperLogLog), and "count distinct in a 1% sample
and multiply by 100". Then the same three for SUM(user_id), where scaling a
sample does work.
"""
import argparse, json
import duckdb

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--rows", type=int, default=20_000_000, help="Events.")
p.add_argument("--users", type=int, default=5_000_000, help="Possible users.")
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()

con = duckdb.connect(); con.execute("SELECT setseed(0.5)")
con.execute(f"CREATE TABLE ev AS SELECT (random() * 1000)::INT AS page, (random() * {args.users})::INT AS user_id FROM range({args.rows})")
q = lambda s: con.execute(s).fetchone()[0]
exact = q("SELECT COUNT(DISTINCT user_id) FROM ev")
approx = q("SELECT approx_count_distinct(user_id) FROM ev")
samp = q("SELECT COUNT(DISTINCT user_id) * 100 FROM ev USING SAMPLE 1% (bernoulli, 7)")
s_exact = q("SELECT SUM(user_id) FROM ev"); s_samp = q("SELECT SUM(user_id) * 100 FROM ev USING SAMPLE 1% (bernoulli, 7)")
rows = [{"measure": "COUNT DISTINCT user_id", "method": "exact", "value": exact, "error_pct": 0.0},
        {"measure": "COUNT DISTINCT user_id", "method": "approx_count_distinct (HLL)", "value": approx, "error_pct": (approx / exact - 1) * 100},
        {"measure": "COUNT DISTINCT user_id", "method": "1% sample × 100", "value": samp, "error_pct": (samp / exact - 1) * 100},
        {"measure": "SUM(user_id)", "method": "exact", "value": s_exact, "error_pct": 0.0},
        {"measure": "SUM(user_id)", "method": "1% sample × 100", "value": s_samp, "error_pct": (s_samp / s_exact - 1) * 100}]
for r in rows: print(f"{r['measure']:<24} {r['method']:<30} {r['value']:>18,}  ({r['error_pct']:+.2f}%)")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"tables": {"estimates": rows}}, f)

3Run it in the folder you saved it to, with the defaults first. Then change a knob from the table below and run it again.

Terminal

uv run sketches-versus-sampling-for-count-distinct.py
uv run sketches-versus-sampling-for-count-distinct.py --help     # every knob

Knobs
Knob · default	What it changes
--rows20,000,000	Events.
--users5,000,000	Possible users.

Our run

Estimates

Estimates
Measure	Method	Value	Error
COUNT DISTINCT user_id	exact	4.91M	0%
COUNT DISTINCT user_id	approx_count_distinct (HLL)	4.89M	-0.391%
COUNT DISTINCT user_id	1% sample × 100	19.6M	299%
SUM(user_id)	exact	50,000B	0%
SUM(user_id)	1% sample × 100	50,000B	0.059%

Reference runApple M2 · 8 cores · 8 GB

Output · uv run sketches-versus-sampling-for-count-distinct.py

COUNT DISTINCT user_id   exact                                   4,908,651  (+0.00%)
COUNT DISTINCT user_id   approx_count_distinct (HLL)             4,889,466  (-0.39%)
COUNT DISTINCT user_id   1% sample × 100                        19,591,300  (+299.12%)
SUM(user_id)             exact                          50,010,572,328,677  (+0.00%)
SUM(user_id)             1% sample × 100                50,040,262,870,300  (+0.06%)

macOS 26.6.2 · Python 3.13.3 · duckdb 1.5.6 · run 2026-10-20

What we found

The exact count was 4.91M users. HyperLogLog said 4.89M (-0.391%); the scaled sample said 19.6M (299%). For the SUM, the same sample was off by only 0.059%.

Read it

Sampling works for measures that add up across rows and fails for those that depend on duplicates across rows. For distinct counts use a sketch, which is mergeable and cheap; never scale a sampled distinct count.