APPROX_PERCENTILE at Scale

Concepts covered: Approximate Aggregates

An average answers the question of what a typical request costs in total, and it answers it badly for anything with a long tail. Take 7 searches whose times climb from 95 ms through 120, 150, 160 and 180 to 210 before jumping to 2,400 ms. Their average is about 474 ms, a figure no search actually took, because 6 of the 7 finished under 211 ms and 1 took 2.4 seconds and dragged the mean up. A percentile answers a different question: p50 is the value that half the rows are at or below, p95 the value that 95% are at or below. Sorted, the 7 searches have a p50 of 160 ms, which is the 4th value. The slow one shows up where it belongs, at the top of the distribution.

The exact way to get a percentile is to sort every value in the group and walk to the rank, which means holding every value. For a billion requests a day grouped by endpoint, that's a full sort of a billion numbers, with the memory to match. APPROX_PERCENTILE(latency_ms, 0.5) keeps a quantile sketch instead: a bounded summary of where values fall by rank, with the same rank-error bound at every percentile, that merges across machines and reads out any percentile at the end. The group can be 7 rows or 7 billion and the sketch stays the same size.

SELECT
  endpoint,
  AVG(latency_ms) AS avg_ms,
  APPROX_PERCENTILE(latency_ms, 0.5) AS p50_ms,
  APPROX_PERCENTILE(latency_ms, 0.99) AS p99_ms
FROM requests
GROUP BY endpoint
ORDER BY p99_ms DESC

Run it and read /search against /checkout. The 5 /checkout latencies sit between 290 and 320 ms. Its average and p50 agree at 305, and its p99 is 320, the top of a tight range. The /search average of about 474 ms sits above 6 of its 7 requests, its p50 is 160 ms, and its p99 lands on the 2,400 ms outlier. The averages said the 2 endpoints perform within a factor of 2 of each other. The percentiles say /checkout is steady and /search has a tail problem.

What the accuracy argument promises

A third argument, APPROX_PERCENTILE(latency_ms, 0.99, 0.01), sets the accuracy, and the promise is about rank rather than milliseconds. With 0.01, the returned value's true position is within 1% of the rank you asked for: somewhere between the 98th and the 100th percentile. If latencies climb steeply in that last 2%, the millisecond gap can be large; if they are flat there, it's small. The default is 0.01, and lowering it, to 0.001 say, buys a finer sketch at the cost of memory per group. For p50 on a smooth distribution the default is more than enough. A spiky distribution read at p99.9 needs a lower value, checked against an exact sort on a sample.

Average hides

• 1 outlier moves it for everyone
• Says nothing about how many users were slow
• Cheap: 1 sum and 1 count per group

Percentile shows

• p50 is a typical experience, p99 the worst 1%
• Tails stay visible however small they are
• Exact needs a full sort, approximate needs a fixed sketch

A p99 latency over 10 million requests uses APPROX_PERCENTILE(latency_ms, 0.99) with the default accuracy. What does the result guarantee?

• The value is within 1% of the true p99 when measured in milliseconds
• The value's true rank lies between the 98th and the 100th percentile
• The result is exact because the group is large enough to fill the sketch
• The result is the average latency of the slowest 1% of the requests

Several percentiles can come out of one pass over the rows. Each APPROX_PERCENTILE call takes the rank it reads as a fraction, 0.5 for the median and 0.95 for p95, and an optional accuracy as its third argument. Dashboards usually set p50 and p95 next to each other, because the gap between them shows how long the tail is.

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.