Support sketch-based decomposition for percentile metrics

[shangyian]

Problem

APPROX_PERCENTILE is treated as non-decomposable, which has two consequences:

1. At query time, any request mixing a percentile with other metrics drops the whole grain group to the level of the upstream node.
2. When materializing, a cube containing a percentile metric cannot be materialized at cube grain (e.g., no rollups). It falls back to the grain of the underlying fact, so materializing the cube amounts to copying the fact table into the target store, losing most of the benefit of materializing.

Both are avoidable, because percentiles are decomposable via a mergeable sketch. This is the same shape DJ already supports for APPROX_COUNT_DISTINCT with HLL sketches.

Decomposition

The existing HLL entry is the template:

@decomposes(dj_functions.ApproxCountDistinct)
class ApproxCountDistinctDecomposition(AggDecomposition):
    components = [ComponentDef(suffix="_hll",
                               accumulate="hll_sketch_agg",
                               merge="hll_union_agg")]
    def combine(self, components):
        return hll_sketch_estimate(hll_union_agg(components[0].name))

A percentile decomposition is structurally identical: accumulate builds a digest per group, merge unions digests, and combine reads the quantile out of the merged digest.

Choice of Sketch

Several mergeable families exist, but they differ in error model:

sketch	error model	notes
KLL (DataSketches)	bounded rank error, uniform	compact, good general default
Classic quantiles (DoublesSketch)	bounded rank error	KLL's predecessor, larger for equivalent accuracy
REQ (DataSketches)	bounded relative rank error	accuracy concentrates at a chosen tail
t-digest	empirical, strongest at the extremes	no proven bound, notably mid-distribution
q-digest	bounded, integer universe	largely superseded

Uniform rank error is right for medians. For p99-style latency metrics, t-digest or REQ is better. Choosing a sketch purely on availability could make tail metrics worse than computing them directly.

Constraints

A materialized sketch is a serialized blob written by one engine and read by another, so those engines must share an implementation and serialization format, not merely have functions with corresponding names. Two sketches both called "t-digest" from different libraries may not be interchangeable.

This means the registry needs a way to express "this component's serialized form is portable between engines X and Y," which it currently has no notion of.

It also means that a viable sketch is whichever one has a single shared implementation across the engines that must read it. If the materialization target is one engine, this is easy. If materialized sketch columns must also be readable by a second query engine, the set of workable options shrinks considerably and may be empty.

Suggested staging

1. Engine-side sketch at ingest. Where the materialization target can build a sketch during ingestion, DJ emits an ingestion-time sketch aggregation and reads quantiles at query time. This yields correct results at cube grain, at the cost of shipping fact-grain rows to the target.
2. Pre-aggregated sketch. The processing engine builds the sketch before ingest, so only compact sketches are shipped. This is more efficient, but depends on that engine having a sketch aggregate whose output the target can read.
3. Registry entry and dialect portability metadata, generalize the HLL precedent so future sketch-based aggregates don't each need bespoke handling.

Open questions

• Which sketch, given the error-model tradeoff above and whatever is available across engines (Spark, Trino, Druid)?
• Should decompositions be able to declare per-dialect availability, so a decomposition can be used on engines that support it and fall back to single-level elsewhere? Today a decomposition is expressed in one canonical dialect, which makes the least-capable engine the floor.
• Should we enable users to customize which sketch they want to use?