Context
Every SummaryKind this crate ships today (Kll/Cms/Hll/DDSketch/CmsWithHeap/Kmv/Theta/CountSketch/CountSketchWithHeap, plus the exact accumulators) answers a single scalar-valued query over a single dimension: one column's quantile, one column's cardinality, one column's frequency. There's no summary kind in the catalog today whose own state is itself structured over a value range (as opposed to a single running value), and no summary kind that natively spans more than one dimension.
Two references make the gap concrete:
- Algebird's
QTree[A: Monoid] (datatypes/approx/q_tree.html) is a mergeable structure that stores non-overlapping value ranges, each paired with a monoid-valued aggregate and a count, implicitly forming a binary tree over the value space. Ranges merge (combining both the interval and the underlying Monoid[A] value) once the tree exceeds its capacity. That gives it two things none of our current kinds have: (1) a queryable value-range structure (quantileBounds, rangeCountBounds, rangeSumBounds — bounds over an arbitrary sub-range, not just a single point/quantile), and (2) genericity over an arbitrary inner Monoid[A], so the value carried per range doesn't have to be a plain count — it can itself be another mergeable aggregate.
- Hydra (VLDB '22) (paper) tackles multi-dimensional sketching directly: rather than one monolithic sketch over a full attribute cross-product, it builds per-dimension (or per-attribute-subset) sketches and composes/summarizes across them — a "sketch of sketches" — so a query can get a fast coarse answer and selectively refine specific dimensions, without every dimension combination needing its own dedicated structure.
Both point at the same missing primitive class for asap-sketch/asap-plan: a summary kind whose state is structured (a tree of ranges, or a composition of per-dimension sketches) rather than a single flat accumulator, and whose readout is a query into that structure (a sub-range, a dimension slice) rather than a single point estimate.
Request
Is there room in SummaryKind/SummaryParams/SketchQuery for this class of summary, and if so, what's the right shape?
Concretely, this raises questions this crate hasn't had to answer for any existing kind:
SketchQuery today is a flat enum (Quantile { q }, Cardinality, TopK { k }, PointCount { key, value }) — one query shape per kind, all producing a single value. A QTree-like kind needs a range-shaped query (RangeQuantile { lo, hi }, RangeSum { lo, hi }) returning a bound (two values), not a point estimate. Does that fit as more SketchQuery variants, or does a genuinely range-queryable kind need its own richer query type?- Genericity over an inner monoid (QTree's
A: Monoid type parameter) has no analogue in SummaryParams today — every existing kind's parameters are fixed scalars (k, width, depth, precision, alpha). Should a "tree of ranges, each carrying another summary" shape be modeled as a new SummaryKind whose params reference another SummaryKind (nesting the catalog on itself), or is that a different extension point entirely (e.g. something closer to the Extension/CostModel::realize_extension escape hatch already in place for deployment-specific shapes, rather than a first-class core kind)?
- Multi-dimensional composition (Hydra's angle) is a different axis from QTree's single-dimension range structure: it's about a summary of summaries across dimensions/columns, not within one column's value range. Does that belong at this layer at all (a new
SummaryExpr shape combining several per-column SummaryAgg nodes), or is it purely a CostModel/deployment-side concern (choosing which per-dimension sketches to build and how to combine their readouts), with core only needing to not get in the way?
No concrete failing query or deployment need drives this yet — flagging it as a forward-looking extensibility question, same spirit as #171/#172's "flagging the gap for discussion rather than proposing a specific API."
References
Context
Every
SummaryKindthis crate ships today (Kll/Cms/Hll/DDSketch/CmsWithHeap/Kmv/Theta/CountSketch/CountSketchWithHeap, plus the exact accumulators) answers a single scalar-valued query over a single dimension: one column's quantile, one column's cardinality, one column's frequency. There's no summary kind in the catalog today whose own state is itself structured over a value range (as opposed to a single running value), and no summary kind that natively spans more than one dimension.Two references make the gap concrete:
QTree[A: Monoid](datatypes/approx/q_tree.html) is a mergeable structure that stores non-overlapping value ranges, each paired with a monoid-valued aggregate and a count, implicitly forming a binary tree over the value space. Ranges merge (combining both the interval and the underlyingMonoid[A]value) once the tree exceeds its capacity. That gives it two things none of our current kinds have: (1) a queryable value-range structure (quantileBounds,rangeCountBounds,rangeSumBounds— bounds over an arbitrary sub-range, not just a single point/quantile), and (2) genericity over an arbitrary innerMonoid[A], so the value carried per range doesn't have to be a plain count — it can itself be another mergeable aggregate.Both point at the same missing primitive class for
asap-sketch/asap-plan: a summary kind whose state is structured (a tree of ranges, or a composition of per-dimension sketches) rather than a single flat accumulator, and whose readout is a query into that structure (a sub-range, a dimension slice) rather than a single point estimate.Request
Is there room in
SummaryKind/SummaryParams/SketchQueryfor this class of summary, and if so, what's the right shape?Concretely, this raises questions this crate hasn't had to answer for any existing kind:
SketchQuerytoday is a flat enum (Quantile { q },Cardinality,TopK { k },PointCount { key, value }) — one query shape per kind, all producing a single value. A QTree-like kind needs a range-shaped query (RangeQuantile { lo, hi },RangeSum { lo, hi }) returning a bound (two values), not a point estimate. Does that fit as moreSketchQueryvariants, or does a genuinely range-queryable kind need its own richer query type?A: Monoidtype parameter) has no analogue inSummaryParamstoday — every existing kind's parameters are fixed scalars (k,width,depth,precision,alpha). Should a "tree of ranges, each carrying another summary" shape be modeled as a newSummaryKindwhose params reference anotherSummaryKind(nesting the catalog on itself), or is that a different extension point entirely (e.g. something closer to theExtension/CostModel::realize_extensionescape hatch already in place for deployment-specific shapes, rather than a first-class core kind)?SummaryExprshape combining several per-columnSummaryAggnodes), or is it purely aCostModel/deployment-side concern (choosing which per-dimension sketches to build and how to combine their readouts), with core only needing to not get in the way?No concrete failing query or deployment need drives this yet — flagging it as a forward-looking extensibility question, same spirit as #171/#172's "flagging the gap for discussion rather than proposing a specific API."
References
QTree— https://twitter.github.io/algebird/datatypes/approx/q_tree.htmlcrates/sketch/src/sketch.rs—SummaryKind/SummaryParams(the catalog this would extend) andSketchQuery(the readout-query vocabulary a range-queryable kind would need to extend)