Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Quantile sketches: t-digest, q-digest, KLL

Which error does each quantile sketch bound, and why can you never average p99 values?

A quantile is a position in sorted order: the median is the 0.5 quantile, is the 0.99 quantile. Parcelo wants delay percentiles per depot.

Why this is hard. Quantiles are holistic: they are neither invertible (you cannot subtract a departing element) nor decomposable (you cannot combine partial answers), the classification from the sliding-window section in Ordering structures. Exact quantiles provably require Ω(n) space, and even an ε-approximate requires Ω(1/ε). There is no bounded-state exact answer, and there never will be.

Three designs, three different definitions of error. The difference in the error definition matters more than the difference in structure.

  • q-digest imposes a fixed hierarchical binary partition on the value domain and stores counts at nodes, compressing upward. It needs a bounded integer universe, which is its main limitation. Its error is on rank, relative to N.
  • KLL (with the older GK and MRL as ancestors) uses a hierarchy of . Each buffer, when full, sorts itself and keeps every other element, choosing odd or even positions at random, at double weight. Space is O((1/ε) · log log(1/δ)) for ε-approximate rank. It is fully mergeable, makes no assumption about the input distribution, and comes with proofs.
  • t-digest clusters points with a scale function that keeps clusters tiny near quantile 0 and quantile 1 and lets them grow in the middle. This gives relative accuracy in the tails: p99 and p999 are estimated far more precisely than p50. For monitoring, where nobody has ever cared about the median, that is the right bias. It is exactly the opposite of KLL's uniform rank guarantee.

Be honest about t-digest, because it is the most deployed and the least guaranteed. Its accuracy claims are empirical, not proved. Adversarial inputs and heavily duplicated values have been shown to degrade it, and there is no bound you can quote to a reviewer. KLL has theorems; has good behavior on data that looks like real data. Pick by which of those you need, and know which one you picked.

The connection to something every monitoring team learns. The rule "you cannot average p99 values across shards or time windows" is a statement that the quantile function is not a homomorphism (it does not merge from partial results). Mergeable digests are the correct resolution: store the digest per shard per window, merge the digests, then read the quantile. Storing the quantile and averaging it is the error the rule warns about, and dashboards commit it constantly.

One structure most people actually run: the fixed-bucket histogram (for example the classic Prometheus histogram). It is mergeable, trivially cheap, and accurate only to the extent that someone chose the bucket boundaries well, which they did before they knew the latency distribution. Exponential (native) histograms fix this by making the relative error constant across the whole range. That is the same insight as t-digest's scale function, reached by a different route.