
Counting a Billion Uniques in Kilobytes: The APPROX_COUNT_DISTINCT Payoff
One line of SQL was quietly costing me more than the rest of my data warehouse combined. It was COUNT(DISTINCT). Here's how HyperLogLog fixed it, and the trick most people miss once they've made the swap.
TL;DR
COUNT(DISTINCT user_id) is one of the most expensive things you can ask a data warehouse to do, because it has to remember every unique value and shuffle them across the cluster. Swapping it for an approximate distinct count powered by an algorithm called HyperLogLog, trades ~1–2% accuracy for a dramatic drop in time and memory. But the real prize most engineers miss is that HyperLogLog produces a tiny reusable sketch: compute it once per day, then merge sketches to get weekly and monthly uniques without ever re-reading the raw data. Here's how it works, where it actually saves money, and when you should keep the exact count.Press enter or click to view image in full size
Why the exact count hurts
Most aggregations are decomposable. To
SUM a column across a cluster, each node sums its slice and you add the partial sums. COUNT , MIN , MAX functions same deal. Cheap, parallel, done.COUNT(DISTINCT) is the exception. To guarantee it counts each value exactly once, the engine can't just add partials, it has to make sure the same user_id on node A and node B isn't double-counted. So it shuffles the values across the network to gather each distinct key in one place, and holds a growing set of every unique value in memory while it does. On a billion-row table with hundreds of millions of uniques, that's tens of gigabytes of shuffle, memory pinned until it spills to disk, and minutes of cluster time you pay for by the second.Now multiply that by reality: your dashboard wants daily, weekly, and monthly active users. Three queries, three full scans, three shuffles and the same brutal work, three times a night, forever.
HyperLogLog
HLL rests on one idea: rare events tell you how many times you’ve tried.
1. Hash each value into random bits. The same
user_id always hashes the same way, so duplicates change nothing, that's why they're free.2. Watch for rare patterns. A long run of leading zeros is unlikely: a hash starting with ten zeros is like flipping ten heads, which you won’t hit until you’ve seen ~1,000 distinct values. The rarest pattern seen is a fingerprint for how many distinct things went by.
3. Estimate from the rarest run. Longest zero-run
R → roughly 2^R distinct values. You never stored the values, only the record of that pattern.4. Average away the noise. Drop each hash into one of thousands of buckets, track the longest zero-run per bucket, combine with a harmonic mean. Thousands of guesses averaged get you within a percent or two.
5. Fixed, tiny memory. Each bucket ~6 bits, a few thousand buckets is a few kilobytes whether you counted a thousand uniques or a billion.
Two things fall out of this:
- Accuracy is a dial. More buckets → tighter → more memory. It’s relative error, so it doesn’t blow up as data grows.
- Sketches merge by taking the max. Combine two sketches by keeping the larger zero-run per bucket, no raw data, no re-scan. That’s the whole second half of the article.
Where it actually saves money (and where it doesn’t)
This is the part most “just use APPROX_COUNT_DISTINCT” posts get wrong. Approximate counting is always faster and lighter on memory. Whether it cuts your bill depends on how you’re billed:
- Compute-billed engines (Redshift, EMR/Spark): you pay for cluster time. A distinct-count job dropping from 15 minutes to 30 seconds is a real ~30× cut on that job, plus you stop paying for spill-to-disk and OOM (out-of-memory) restarts. Direct savings.
- Bytes-scanned engines (Athena, BigQuery on-demand): you pay per terabyte read. The approximate function still reads the whole column, so your scan bill barely moves, this is not where you cut cost. But it’s still a trade worth making: the query gets dramatically faster and, just as important, it finishes. Jobs that used to die on shuffle or run out of memory now complete in seconds. You’re trading ~1–2% accuracy for speed and reliability at no extra spend, which is a genuinely good deal.
Knowing this distinction is what separates a cargo-cult optimization from an informed one.
The real payoff: store the sketch, not the number
Here’s the trick that turns a one-query win into a permanent one. Because an HLL sketch is just a few kilobytes of bucket values and sketches merge by taking the max, you can persist a sketch per day and then union days on demand daily, weekly, monthly, all-time without ever touching the raw events again.
-- Build one small sketch per day (run once daily), BigQueryINSERT INTO dau_sketchSELECT date, HLL_COUNT.INIT(user_id) AS sketchFROM eventsWHERE date = CURRENT_DATE()GROUP BY date;-- Monthly actives = merge 30 KB-sized sketches. Zero raw scans:SELECT HLL_COUNT.MERGE(sketch) AS mauFROM dau_sketchWHERE date BETWEEN '2026-06-01' AND '2026-06-30';Every major warehouse exposes this:
- Redshift: the
HLLSKETCHcolumn type; store daily sketches, combine for MAU (monthly active users).
- Snowflake:
HLL_EXPORT/HLL_IMPORT/HLL_COMBINE/HLL_ESTIMATE.
- BigQuery:
HLL_COUNT.INIT→HLL_COUNT.MERGE→HLL_COUNT.EXTRACT.
- Athena / Trino:
approx_set()produces aHyperLogLogblob you can store andmerge()on read.
That “recompute active users over billions of rows every night” job becomes “union some kilobyte-sized sketches.” On bytes-scanned billing this is also where the money finally shows up: you scan the raw events once to build each day’s sketch, then read only the tiny sketches forever after.
The function is named differently everywhere
A quick reference, because copy-pasting
APPROX_COUNT_DISTINCT across engines will bite you:Engine Syntax Default error Note Athena / Trino / Presto
approx_distinct(x) ~2.3% std error not APPROX_COUNT_DISTINCT ; second arg tightens it Amazon Redshift APPROXIMATE COUNT(DISTINCT x) ~2% a keyword on COUNT(DISTINCT) Spark (EMR/Glue)
approx_count_distinct(x[, rsd]) 5% default pass a smaller rsd for tighter bounds BigQuery APPROX_COUNT_DISTINCT(x) ~1–2% HLL_COUNT.* for sketches Snowflake
APPROX_COUNT_DISTINCT(x) / HLL(x) ~1.6% avg HLL_* for sketchesThe one that surprises people: Spark’s default error is 5%, not 1–2%. If you need it tighter on EMR/Glue, pass a smaller relative standard deviation (at the cost of more memory).
How to start
- Find your most expensive
COUNT(DISTINCT), usually the active-users or unique-visitors job.
- Swap in the approximate function for your engine (mind the name and default error) and compare runtime and cost.
- If you compute the same metric over multiple time windows, build a daily sketch table and merge for the rest.
- On Athena/BigQuery, remember the saving comes from the sketch table (scan once), not the function alone.
- Leave the exact count wherever the number has to be exact.
The bottom line
COUNT(DISTINCT) is expensive for a real, structural reason, it can't be aggregated in pieces. HyperLogLog sidesteps that with a beautiful trick: hash to random bits, watch for rare patterns, and estimate the count from a few kilobytes of state. The one-line swap is nice; the durable win is treating the sketch as a first-class asset you compute once and reuse forever. Know where it saves money, know its ~1–2% cost, and know when to keep it exact and you've made exactly the kind of trade-off that separates code that works from a platform that scales.Written by Matheus Sabaudo, AWS Data Engineer. Function names and error figures verified against Trino, Apache Spark, Amazon Redshift, Snowflake, and BigQuery documentation (July 2026).
Enjoyed reading this content? Let the author know!
Your likes, comments, shares, and saves help creators reach more builders.
Loading recommendations
Loading article