Approximate aggregation and HLL sketches in BigQuery

APPROX_COUNT_DISTINCT, APPROX_QUANTILES and APPROX_TOP_COUNT trade a small error for speed on large data. HLL_COUNT sketches go further. You store them per day and merge them later without rereading the rows.

BigQuery has approximate versions of the aggregates that are expensive to compute exactly: distinct counts, quantiles and most-frequent values. They return an estimate in less time and with less memory. A second family, the HLL and KLL functions, returns the intermediate sketch itself as BYTES, so you can store it and merge sketches later, which COUNT(DISTINCT) can never do.

The examples here use GENERATE_ARRAY to make a million rows from nothing, because the error only shows up on data of that size.

APPROX_COUNT_DISTINCT vs COUNT(DISTINCT)

COUNT(DISTINCT x) is exact. APPROX_COUNT_DISTINCT(x) is a statistical estimate. This data has 1,000,000 visits from exactly 250,000 users:

WITH visits AS (
  SELECT MOD(n * 7919, 250000) AS user_id
  FROM UNNEST(GENERATE_ARRAY(1, 1000000)) AS n
)
SELECT
  COUNT(DISTINCT user_id) AS exact,
  APPROX_COUNT_DISTINCT(user_id) AS approx
FROM visits

On this input the estimate is off by 1,512, about 0.6%. For HyperLogLog++ sketches at the default precision, Google’s guide gives an error of about 1% in 95% of cases (±1.15% in its table). APPROX_COUNT_DISTINCT uses a system-defined precision, so expect an error of that order.

The approximate function does not read fewer bytes. A dry run of it over a public table reports exactly what COUNT(DISTINCT) reports for the same column:

SELECT APPROX_COUNT_DISTINCT(corpus) AS approx_corpora
FROM `bigquery-public-data.samples.shakespeare`

COUNT(DISTINCT corpus) on the same table also reports 2,464,625 bytes. So on-demand cost is the same, and the gain is compute time and memory on big inputs. See how queries are billed.

Use the approximate version for dashboards and trends where 1% doesn’t matter. Use the exact one for billing, reconciliation and anything compared against another system’s number.

APPROX_QUANTILES

APPROX_QUANTILES(x, n) returns an array of n + 1 values: the approximate minimum, the n - 1 boundaries between quantiles, and the approximate maximum. Index into it with OFFSET to get one percentile:

WITH latencies AS (
  SELECT MOD(n * 7919, 1000003) AS ms
  FROM UNNEST(GENERATE_ARRAY(1, 1000000)) AS n
)
SELECT
  APPROX_QUANTILES(ms, 4) AS quartiles,
  APPROX_QUANTILES(ms, 100)[OFFSET(95)] AS p95_approx,
  (SELECT PERCENTILE_CONT(ms, 0.95) OVER () FROM latencies LIMIT 1) AS p95_exact
FROM latencies

The data is spread evenly over 0 to 1,000,002, so the true quartiles are about 250,000, 500,000 and 750,000. BigQuery returned 249,975, 500,274 and 750,096. The 95th percentile is 950,014 against an exact 950,000.05, which is PERCENTILE_CONT as a window function (it has no aggregate form).

NULLs are ignored by default. Write RESPECT NULLS to keep them, and they sort first:

SELECT
  APPROX_QUANTILES(x, 2) AS default_nulls,
  FORMAT('%T', APPROX_QUANTILES(x, 2 RESPECT NULLS)) AS respect_nulls
FROM UNNEST([NULL, NULL, 1, 4, 5, 6, 7, 8, 9, 10]) AS x

APPROX_QUANTILES also accepts DISTINCT, which computes quantiles over the distinct values only. The count n must be at least 1 (BigQuery rejects 0).

APPROX_TOP_COUNT and APPROX_TOP_SUM

APPROX_TOP_COUNT(x, n) returns the n most frequent values with their counts, as an array of structs with fields value and count. APPROX_TOP_SUM(x, weight, n) ranks by the sum of a weight instead, with fields value and sum:

WITH hits AS (
  SELECT CASE
    WHEN MOD(n, 10) < 5 THEN '/home'
    WHEN MOD(n, 10) < 8 THEN '/pricing'
    WHEN MOD(n, 10) < 9 THEN '/docs'
    ELSE CONCAT('/blog/', CAST(MOD(n, 997) AS STRING))
  END AS page
  FROM UNNEST(GENERATE_ARRAY(1, 100000)) AS n
)
SELECT APPROX_TOP_COUNT(page, 3) AS top_pages
FROM hits

WITH downloads AS (
  SELECT
    CONCAT('user_', CAST(MOD(n, 5) AS STRING)) AS user_name,
    n AS bytes
  FROM UNNEST(GENERATE_ARRAY(1, 1000)) AS n
)
SELECT APPROX_TOP_SUM(user_name, bytes, 2) AS top_users
FROM downloads

The counts are estimates in general. Here they came out exact. Unlike most aggregates, APPROX_TOP_COUNT does not skip NULLs: a NULL value is counted and can appear in the result.

Sketches: store now, merge later

COUNT(DISTINCT user_id) for a month needs every user_id from that month. If you also want it per day, per week and per country, you read the rows again for each. An HLL sketch is a small summary of a set of values. Build one per day, store it, and answer later questions by merging sketches:

WITH daily AS (
  SELECT 1 AS day, HLL_COUNT.INIT(id) AS sketch FROM UNNEST(GENERATE_ARRAY(1, 100000)) AS id UNION ALL
  SELECT 2, HLL_COUNT.INIT(id) FROM UNNEST(GENERATE_ARRAY(50001, 150000)) AS id UNION ALL
  SELECT 3, HLL_COUNT.INIT(id) FROM UNNEST(GENERATE_ARRAY(100001, 200000)) AS id
)
SELECT
  HLL_COUNT.MERGE(sketch) AS distinct_3_days,
  SUM(HLL_COUNT.EXTRACT(sketch)) AS sum_of_daily_counts
FROM daily

The three days hold ids 1 to 100,000, 50,001 to 150,000 and 100,001 to 200,000, so the true count of distinct ids is 200,000. The merged sketch says 200,142. Adding the three daily counts says 299,198, because ids that appear on two days are counted twice. Distinct counts don’t add up, and that is the case sketches solve.

The functions come in a fixed set:

Use MERGE_PARTIAL when the result is still a sketch, for example rolling days up into weeks while keeping the weekly sketch for later merges. Here DIV(day, 2) puts day 1 in bucket 0 and days 2 and 3 in bucket 1:

WITH daily AS (
  SELECT 1 AS day, HLL_COUNT.INIT(id) AS sketch FROM UNNEST(GENERATE_ARRAY(1, 100000)) AS id UNION ALL
  SELECT 2, HLL_COUNT.INIT(id) FROM UNNEST(GENERATE_ARRAY(50001, 150000)) AS id UNION ALL
  SELECT 3, HLL_COUNT.INIT(id) FROM UNNEST(GENERATE_ARRAY(100001, 200000)) AS id
),
buckets AS (
  SELECT DIV(day, 2) AS bucket, HLL_COUNT.MERGE_PARTIAL(sketch) AS sketch
  FROM daily
  GROUP BY bucket
)
SELECT
  bucket,
  HLL_COUNT.EXTRACT(sketch) AS distinct_ids,
  BYTE_LENGTH(sketch) AS sketch_bytes
FROM buckets
ORDER BY bucket

Bucket 1 holds ids 50,001 to 200,000, so the true count is 150,000 and the sketch says 149,554. Both sketches are 32,791 bytes, though one holds 100,000 ids and the other 150,000.

Precision

HLL_COUNT.INIT takes a precision from 10 to 24, default 15. Anything outside that range is an error. Higher precision means a smaller error and a bigger sketch. We built sketches of the same 100,000 ids at three precisions:

WITH ids AS (SELECT id FROM UNNEST(GENERATE_ARRAY(1, 100000)) AS id)
SELECT
  HLL_COUNT.EXTRACT(HLL_COUNT.INIT(id, 10)) AS precision_10,
  HLL_COUNT.EXTRACT(HLL_COUNT.INIT(id, 15)) AS precision_15,
  HLL_COUNT.EXTRACT(HLL_COUNT.INIT(id, 24)) AS precision_24,
  COUNT(DISTINCT id) AS exact
FROM ids

WITH ids AS (SELECT id FROM UNNEST(GENERATE_ARRAY(1, 100000)) AS id)
SELECT
  BYTE_LENGTH(HLL_COUNT.INIT(id, 10)) AS bytes_at_10,
  BYTE_LENGTH(HLL_COUNT.INIT(id, 15)) AS bytes_at_15,
  BYTE_LENGTH(HLL_COUNT.INIT(id, 24)) AS bytes_at_24
FROM ids

Google’s guide lists the worst-case storage at each precision, for example 1 KiB at 10, 32 KiB at 15 and 16 MiB at 24. The sketches we built were smaller than that maximum, 214,417 bytes at precision 24, because the sketch format has a sparse representation (the guide mentions it) and the size depends on the data. Treat Google’s numbers as the upper bound.

Precision 10 happened to be closer than precision 15 here (100,071 against 99,651). The error is random around the true value, and a higher precision only narrows the range it can fall in. Don’t read one run as a ranking.

Merging sketches of different precision works and downgrades the result to the lowest precision involved. We merged a precision-12 sketch of 1 to 1,000 with a precision-15 sketch of 500 to 2,000 and got 2,002 for a true count of 2,000.

Sketches must be built from the same type

Sketches of ids as INT64 and of names as STRING can’t be merged, and BigQuery fails the query at run time:

WITH sketches AS (
  SELECT HLL_COUNT.INIT(id) AS sketch FROM UNNEST([1, 2, 3]) AS id
  UNION ALL
  SELECT HLL_COUNT.INIT(name) FROM UNNEST(['a', 'b']) AS name
)
SELECT HLL_COUNT.MERGE(sketch) AS merged
FROM sketches

Google’s reference says each sketch must be initialized on the same type. The message doesn’t say that. If HLL_COUNT.MERGE_PARTIAL failed to compute shows up, look at the types the sketches were built from.

Quantile sketches

KLL sketches are the quantile counterpart. KLL_QUANTILES.INIT_INT64(x) builds a sketch, and MERGE_POINT_INT64(sketch, phi) or MERGE_INT64(sketch, n) merge sketches and return one quantile or an array of n + 1 boundaries. There are INT64 and FLOAT64 variants of each:

WITH daily AS (
  SELECT 1 AS day, KLL_QUANTILES.INIT_INT64(ms) AS sketch FROM UNNEST(GENERATE_ARRAY(1, 1000)) AS ms UNION ALL
  SELECT 2, KLL_QUANTILES.INIT_INT64(ms) FROM UNNEST(GENERATE_ARRAY(1001, 2000)) AS ms
)
SELECT
  KLL_QUANTILES.MERGE_POINT_INT64(sketch, 0.5) AS median_2_days,
  KLL_QUANTILES.MERGE_INT64(sketch, 4) AS quartiles
FROM daily

The median of 1 to 2,000 comes back as 1,000, and the quartile boundaries match the exact values on this small input. In general the result is approximate: the rank of the returned value is within (number of input rows) / precision of the exact rank in 99.999% of cases, with a default precision of 1,000.

Storing sketches

A sketch is an ordinary BYTES value, so a table of daily sketches is just a table with a BYTES column. A typical layout has one row per day and segment (country, plan) with HLL_COUNT.INIT(user_id) as the sketch, loaded once. Any later question, such as “distinct users in the last 7 days in Germany”, runs HLL_COUNT.MERGE(sketch) over a handful of rows instead of rereading the raw events.