AWS Builder Center
Counting a Billion Uniques in Kilobytes: The APPROX_COUNT_DISTINCT Payoff

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.

AWS Data Engineer | ☁️ AWS Certified Solutions Architect | 🧱 ETL & ELT Pipeline Design

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), BigQuery
INSERT INTO dau_sketch
SELECT date, HLL_COUNT.INIT(user_id) AS sketch
FROM events
WHERE date = CURRENT_DATE()
GROUP BY date;
-- Monthly actives = merge 30 KB-sized sketches. Zero raw scans:
SELECT HLL_COUNT.MERGE(sketch) AS mau
FROM dau_sketch
WHERE date BETWEEN '2026-06-01' AND '2026-06-30';
Every major warehouse exposes this:
  • Redshift: the  HLLSKETCH  column 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 a  HyperLogLog  blob you can store and  merge()  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 sketches
The 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

  1. Find your most expensive  COUNT(DISTINCT) , usually the active-users or unique-visitors job.
  1. Swap in the approximate function for your engine (mind the name and default error) and compare runtime and cost.
  1. If you compute the same metric over multiple time windows, build a daily sketch table and merge for the rest.
  1. On Athena/BigQuery, remember the saving comes from the sketch table (scan once), not the function alone.
  1. 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).
Any opinions in this article are those of the individual author and may not reflect the opinions of AWS.
Enjoyed reading this content? Let the author know!

Your likes, comments, shares, and saves help creators reach more builders.

Loading recommendations

Loading article