APPROX_DISTINCT (HyperLogLog)

Concepts covered: Approximate Aggregates

COUNT(DISTINCT user_id) over a year of streams has to remember every user id it has seen, so that the next occurrence of the same id adds nothing. The structure that remembers is a set of the ids themselves, and its size grows with the number of distinct ids: 500 million ids at 8 bytes each is 4 GB before any overhead, held in memory for the duration of the query. Group by artist and there's a set per artist. Spread the work over many machines and every set has to be shipped to one place and merged. That set is why the first Wrapped query was still going at lunch.

Counting without remembering

APPROX_DISTINCT(user_id) replaces the set with a sketch whose size is fixed before the first row arrives, using the HyperLogLog method. Hash each value to a string of bits. Look at how many zeros the hash starts with. A hash that begins with 3 zeros shows up about once in every 8 values, and one that begins with 10 zeros about once in 1,024, because each extra leading zero halves the odds. So the longest run of leading zeros you have seen is a clue to how many distinct values have passed: see a run of 10 and about a thousand distinct values have gone by. A duplicate hashes to the identical bits, so it can never extend the run, which is how repeats are ignored without being stored.

Hashes shortened to 8 bits for the page. The longest run is 3, and the repeat of u2 changes nothing.

A single longest run is a noisy clue: 1 lucky hash with 20 leading zeros would suggest a million values. HyperLogLog spreads the values across thousands of buckets, chosen by the first bits of the hash, keeps the longest run in each bucket as 1 small number, and combines the buckets with an average that damps the lucky ones. The buckets are the whole sketch. They cost a few kilobytes whether a thousand or a billion values pass through, 2 sketches from 2 machines merge by taking the larger run per bucket, and the error is predictable from the bucket count alone.

• 2.3%
• 0.4%
• 26%

A standard error is a band, and around 2 estimates in 3 land inside it; almost all land within 3 bands. With the default on a true count of 50 million listeners, 2 runs in 3 return a figure within about 1.15 million of the truth, and a result off by more than 3.5 million would be rare. An optional second argument sets the band you will accept, and a smaller band costs a sketch with more buckets, still kilobytes, so tightening is cheap down to the lowest value the engine allows.

Exact

COUNT(DISTINCT) builds a set of user ids per artist and returns 4 listeners for Bolt, 3 for Aria and 2 for Cove.

SELECT
  artist,
  COUNT(DISTINCT user_id) AS listeners
FROM streams
GROUP BY artist
ORDER BY listeners DESC

Approximate

APPROX_DISTINCT builds a sketch per artist instead; on 12 rows it lands on the same 4, 3 and 2.

SELECT
  artist,
  APPROX_DISTINCT(user_id) AS listeners
FROM streams
GROUP BY artist
ORDER BY listeners DESC

Tighter

A second argument of 0.01 asks for a 1% standard error, which buys a larger sketch and the same answer here.

SELECT
  artist,
  APPROX_DISTINCT(user_id, 0.01) AS listeners
FROM streams
GROUP BY artist
ORDER BY listeners DESC

Do

• Use APPROX_DISTINCT for any count you would round anyway, such as a dashboard trend line
• Keep the error argument constant across the queries you compare
• Report approximate figures as approximate: 48.9M, not 48,912,377

Avoid

• Reach for it on billing counts, or on any figure an audit or legal filing depends on
• Compare an approximate count against an exact one and read the gap as a change
• Expect a tighter error to come free: more buckets mean a bigger sketch per group

A daily dashboard reports monthly active users from about 2 billion events a day, and the figure moves by a few percent from day to day. Which count fits?

• APPROX_DISTINCT(user_id) with the default error, since its band is narrower than the daily movement and the sketch keeps the query fast
• COUNT(DISTINCT user_id), since an approximate figure is never acceptable on a dashboard that leadership reads every morning
• APPROX_DISTINCT(user_id, 0.5), since a wide band makes the sketch as small as it can be and the query as fast as it can be
• COUNT(user_id), since it needs no set and no sketch and therefore runs fastest of all the options

One query can carry both kinds of count side by side. COUNT(*) per group counts events and keeps only a running total; APPROX_DISTINCT(user_id, e) in the same SELECT list counts the people behind those events, with e written as a fraction, so 0.01 asks for a 1% standard error. Dividing the first by the second gives events per user.

About this lesson

This section is part of the Aggregating: Intermediate lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.