Your COUNT(DISTINCT) Is Too Slow: Approximations and Sampling in Postgres

I'm very impatient. I don't always care about the exact right answer. When I'm checking how many unique visitors hit a page, I don't need 497,536 — "about 497,000" is fine. If getting that answer takes 3 milliseconds instead of a second, I'll take the trade every time.

Postgres has several features for approximation and sampling that are worth knowing about, especially if you're working with huge data sets. Approximation options in Postgres range from built-in table sampling to algorithms for probabilistic data structures. This post walks through all of them using the same test data so you can compare and see when each one makes sense.

Follow along with a sample web analytics table

Everything in this post uses the same 10 million row test table. You can generate it yourself on Postgres 17 or 18+ with the hll and datasketches extensions installed. The benchmarks here were run on Postgres 18, and an Apple M-series machine with shared_buffers = 256MB, work_mem = 64MB, and max_parallel_workers_per_gather = 2 (the Postgres default) — a pretty standard laptop setup. Parallel scans are enabled for all queries equally. I also made a companion SQL gist with additional details. I think "too much SQL" wins me some kind of Snowflake employee award.

We're simulating a web analytics table, the kind of data you'd have from a product analytics tracker, or really any event-driven application. Each row here is a single page view with information about who visited, where they came from, and how fast the page loaded.

I built this test data set specifically so it has properties that exercise each approximation technique.

• There are lots of distinct users for testing distinct counting
• A few categorical columns like traffic channel for set operations (that is, comparing overlapping groups)
• A numeric response time column with a skewed distribution for testing percentile calculations

Generating 10 million rows

This INSERT uses generate_series and random functions to fill the table which takes about 90 seconds on my laptop.

The table ends up at about 1.4 GB on disk with 500,000 distinct users. The distribution should be somewhat realistic — a few power users generate way more traffic than everyone else, a handful of pages get most of the views, and response times have a long tail where most pages load fast but some are much slower. This makes it a good test for everything we'll cover.

The problem: Exact is expensive

Exact aggregates on big tables are slow in two different ways, and knowing which kind of slow you're dealing with determines which tool to reach for.

Aggregate stats — averages, sums, percentiles — are expensive because they have to read every row:

percentile_cont needs to sort all 10 million response time values to find the 99th percentile. Even with 64MB of work_mem and parallel workers, that's 2.6 seconds. Drop work_mem to 4MB (a common default) and it gets much worse — the sort spills to disk with over 200 MB of temp file I/O just to answer one question.

These queries are fine when you're doing a one-off analysis. They're probably not fine for dashboards that refresh every few seconds, or for tables that are 10 or 100 times larger than our test set. The rest of this post covers the tools that fix each case — starting with the simplest.

TABLESAMPLE: zero-setup sampling

For aggregate stats like averages and percentiles, you have a super simple option: just read less data. Postgres has a built-in TABLESAMPLE clause that returns a random subset of your table without needing any extensions or setup.

In our example, a 10% sample gives you a nearly identical average in about a third the time. Percentiles work too:

The p99 estimate is within 0.3% of exact, and it ran 10x faster because Postgres only sorted ~1 million values instead of 10 million. You put TABLESAMPLE right after the table name and give it a percentage.

TABLESAMPLE has two sampling methods you can choose from.

SYSTEM samples at the page level. Postgres data is stored in 8KB pages on disk, and SYSTEM randomly includes or excludes entire pages. This is fast because it can skip whole chunks of the table without reading them. The downside is that if your data is physically clustered, you will get a biased sample, and there's no way to ensure it is correctly distributed.

BERNOULLI evaluates each row individually with a random number generator. This gives you a more evenly distributed sample but it's slower because it can't skip pages. The method is named after Jacob Bernoulli, the 17th-century Swiss mathematician who developed some of the math for probability.

Where TABLESAMPLE falls down

Sampling can be a good fix for quicker aggregates. But what about distinct counts? We all know how slow full distinct counts are on huge tables.

You might think "I sampled 10%, so multiply by 10 to get the full number." But this massively overcounts. Here's why: if a user appears in 20 rows across the full table, even a 10% sample is almost certain to catch at least one of those rows. So nearly all 500K users show up in your 10% sample. Multiplying by 10 gives you a number that's eight times too high.

TABLESAMPLE is best for: averages, sums, ballpark histograms, spot-checking your data during development, or as a quick smoke test. It may have some clustered data bias. If you need accurate distinct counts, you need a different approach.

HyperLogLog: streaming distinct counts

HyperLogLog (HLL) is a probabilistic algorithm that's been around since 2007. The core idea is simple: instead of storing every unique value, it observes patterns in the binary representation of hashed values to estimate how many distinct values it's seen.

The Postgres hll extension managed by Citus Data implements HLL as a native data type. When you use it, you'd typically store it as a column in a rollup table alongside your regular columns. It's a compact binary blob, so pretty space efficient. You can install it with:

Basic distinct count

Here's the simplest use — getting an approximate distinct count:

That's 320 milliseconds vs 671 ms for exact COUNT(DISTINCT) which is about twice as fast on a single scan. Also HLL isn't just about raw speed on one query. The function names are a bit verbose but the pattern is always the same: hash the value, aggregate the hashes into an HLL, then ask for the cardinality.

Preaggregate for instant queries

The real power of HLL is that sketches are mergeable. This is the key concept that makes them different from just "a faster COUNT(DISTINCT)." You can build a separate HLL sketch for each day, store those sketches in a table, and then union them together at query time to get distinct counts across any date range.

The daily_hll table has one row per day. Each row is tiny — the HLL column in this example is about 1.3 KB per row regardless of how many users it represents. And querying this small rollup table instead of scanning millions of raw rows is what gets you from hundreds of milliseconds to sub-millisecond.

HLL sketches work as window functions too, making rolling unique counts trivial:

Try computing a rolling 7-day unique user count with exact SQL — you'd need a correlated subquery that re-scans raw data for every output row. That took 7 seconds for just 5 days in our test — at that rate it would be over 2 minutes for all 91 days. With HLL, it's just a window function over a tiny column, done in 4 milliseconds.

Apache DataSketches: the full toolkit for probability

Apache DataSketches is a library of streaming algorithms originally developed at Yahoo for analytics at web scale. "Sketch" is a general term for any compact probabilistic data structure that summarizes a stream of data. Think of it like a compressed fingerprint of your dataset that you can still ask questions about.

The Postgres extension brings several sketch types, each designed for a different kind of question:

CPC: compact distinct counting

CPC is the DataSketches answer to "how many distinct values?" — the same question HLL answers, but CPC sketches can be more compact when stored and are thought to have slightly better accuracy at the same memory budgets.

The cpc_sketch_build function is an aggregate — it works like count() or sum(), collapsing all the rows into a single sketch value. That sketch is an opaque binary blob, and you use cpc_sketch_get_estimate to extract the cardinality from it.

Theta sketches: set operations on distinct counts

Here's where things get interesting and where DataSketches really separates itself from plain HLL. Theta sketches let you do set operations — intersection, union, difference — on distinct count sketches.

Here's a question you simply cannot answer with HLL or COUNT(DISTINCT): "How many users visited via both Google and Facebook?"

With pre-aggregated COUNT(DISTINCT) rollups, answering overlap questions like this is impossible — you'd have to go back to the raw event table and do a self-join. With Theta sketches, you just intersect two pre-built sketches directly.

There's also theta_sketch_a_not_b for exclusive reach ("Google users who did NOT visit via Facebook") and you can compute a full pairwise overlap matrix across all channels.

KLL sketches: quantiles without sorting

"What's the p99 response time?" is a question that normally requires Postgres to sort your entire dataset. KLL sketches (named after their inventors Karnin, Lang, and Liberty, who published the algorithm in 2016) maintain a compact summary that can answer quantile, rank, and histogram questions without ever sorting.

Compared to the exact values in this example (p50: 121.55, p90: 385.23, p99: 986.39), KLL is within about 7% on the tails. For monitoring and dashboards where you're looking at trends and alerting on big changes, this is more than accurate enough. And it ran four times faster.

You can also get full histograms with KLL using the probability mass function:

Like all the other sketch types, KLL is additive. Build one sketch per time bucket in your pipeline, then merge them at query time to get percentiles across any date range without resorting the original data.

Frequent Strings: most common values

The last sketch type finds the most common values in a column:

On a single full-table scan, the sketch is actually slightly slower than a plain GROUP BY. The value shows up when you preaggregate — build one sketch per day, then merge across any date range without re-scanning millions of rows:

That's 1,000x faster in our testing. The rollup table has 92 rows — one tiny sketch per day. The standard Postgres query has to scan 3+ million rows, hash them by page_path, sort, and return the top 76.

The preaggregate-then-merge pattern

This is the architectural pattern that ties everything together. The idea is:

1. Build sketches once during your ETL or data pipeline, grouping by the dimensions you care about (date, channel, region, and so on)
2. Store those sketches in a rollup table alongside regular aggregates like count(*) and sum(revenue)
3. Query the rollup table at dashboard time: Filter to the dimensions you need, merge the sketches, get instant answers

Here's what the rollup table looks like:

This produces 3,680 rows (90 days x 5 channels x 8 regions). The table is 88 MB because it stores the full binary sketches. Compare that to the 1.4 GB raw table.

Now every analytics query hits the rollup instead of scanning the raw data:

That's an 80x speedup — from over 300 milliseconds down to 4 milliseconds. And it works for all the sketch types:

Don't overlook the hardware payoff here

Another thing worth pointing out is that sketches don't just make queries faster, they also make your hardware requirements smaller.

Think about what exact queries are doing under the hood. COUNT(DISTINCT) builds a hash table in memory that grows with the number of unique values. percentile_cont() sorts the entire column in memory. When these structures exceed your work_mem setting, Postgres writes temp files to disk — and that's when things really slow down.

Here's what we saw with work_mem = 4MB:

The key insight: A CPC sketch uses 2-4 KB of memory whether you feed it 500 thousand or 500 million distinct values. A KLL sketch uses 4-8 KB whether you're computing percentiles over 10 million or 10 billion values. The memory footprint is bounded by the sketch's precision parameter, not by the size of your data.

What this means in practice:

• You don't need to tune work_mem up to 256MB to avoid disk spills
• You don't need fast NVMe storage for temp file I/O
• Your analytics queries can run comfortably on a modest cloud instance
• Dashboards stay responsive even on constrained hardware

The rollup query reads 576 buffers — that's 4.5 MB of data total. You could serve that from basically anything.

Keeping rollups fresh

Once you've got a rollup table, the next question is how to keep it up to date as new events arrive. There are a few good options depending on how much infrastructure you want.

Materialized views

The simplest approach is a materialized view — same SQL as the rollup table, but with a built-in refresh mechanism:

Now REFRESH MATERIALIZED VIEW CONCURRENTLY analytics_rollup; rebuilds it without blocking reads. You can put that in a cron job or call it from your pipeline after loading new data.

The tradeoff: Every refresh does a full recompute — it rescans all 10M rows and rebuilds every sketch from scratch. For our test table that takes about 10-15 seconds, which is fine for a nightly job. At hundreds of millions of rows it starts to hurt. For more on making matviews query-friendly, see Indexing Materialized Views in Postgres.

pg_incremental: process only new data

If full-table rescans become too expensive, pg_incremental gives you incremental processing. Instead of rebuilding the entire rollup, you define a pipeline that only processes rows that arrived since the last run:

This is a natural fit for sketches because they're additive — you build a sketch for today's data and union it with yesterday's at query time. You don't have to re-scan historical rows. See pg_incremental: Incremental Data Processing in Postgres for the full details.

Sketches on remote data with pg_lake

Your event data doesn't have to live in a Postgres heap table for any of this to work. If your data already lives in object storage — synced from a warehouse, landed by a pipeline, or written directly by an application, pg_lake lets you query it from Postgres as an Apache Iceberg™ table. Under the hood, pg_lake uses a DuckDB columnar engine for the scan, so analytical queries on remote data are often dramatically faster than on a local heap table:

The speedup depends on the query. For aggregates that scan a single column (avg, sum, filtered counts), Iceberg's columnar format is dramatically faster because it only reads the bytes it needs. For hash-heavy operations like COUNT(DISTINCT), both engines are doing similar work and performance converges.

But sketches may still matter — you can't query object storage in under a millisecond, no matter how fast the engine is. The rollup pattern we saw before can work on remote object stores. Scan Iceberg once, store sketches locally, and you'll have single-digit millisecond dashboard queries over data that lives remotely:

The source data stays in object storage (cheap, shared with other tools). The sketch rollup lives in local Postgres (fast, tiny — 2.3 MB for 90 days of rollups vs 1.4 GB of raw data in our example). You can get sub-millisecond dashboard queries without copying terabytes of raw events into your database.

When NOT to approximate

Not everything should be approximated. Before the pitchforks come out in the comments section I'll add this warning. Here are cases where you should stick with exact:

Financial reporting, billing, compliance: If a number goes on an invoice or in a regulatory filing, you need exact. No debate.

Small tables: If you have under about 1 million rows, exact aggregates are fast enough — they'll come back in under 200ms. Don't add complexity to a problem that doesn't exist.

When you need individual rows: Sketches are aggregates. They can tell you "about 500K unique users" but they can't tell you which users. If you need WHERE user_id = X, you need the raw data.

Joins on approximate results: You can't JOIN on a sketch. You can TABLESAMPLE a table and then join it to something else, but be aware that sampling happens before the join — a 10% sample of two joined tables gives you ~1% of the matching rows.

"Close only counts in horseshoes and hand grenades."

Benchmark summary

All numbers from our 10M-row page_views table on Postgres 18 in Docker (Apple M-series, 256MB shared_buffers, 64MB work_mem, max_parallel_workers_per_gather = 2 unless noted). Parallel query is enabled for all benchmarks equally — both exact and sketch-based queries benefit from parallel table scans:

Comparison at a glance