Skip to content

Flat-buffer state columns for fixed-size sketches need slice kernels in asap_sketchlib #764

Open

Description

@zzylol

Problem, by example

A 10-second pane of count(distinct ...)-style HLL states, one per series, over 2,000 series at precision 10. #762 makes the executor columnar. Its state column (values::StateColumn) still holds these states as 2,000 separate HllSketchAccumulator objects (StateStorage::Objects), and each object owns its own 1,024-byte register Vec<u8>:

Today Wanted (#762, "fixed-size sketches in flat buffers")
Memory 2,000 heap allocations of 1 KiB, plus 2,000 Arcs one 2,000 × 1,024-byte buffer
Merging two panes 2,000 merge_with calls, each allocating a new sketch one element-wise max over two buffers
Building a pane one allocation per group none per group

The same applies to Count-Min (rows × cols f64 counters per group) and plain Count Sketch.

Why it isn't done today

The update, merge and estimate logic of these sketches lives in asap_sketchlib, and the executor must use it rather than reimplement it (hashing, register update rules):

  • asap_sketchlib::CountMinSketch keeps its counters in a crate-private backend (backend: SketchlibCms). There is no constructor over, or view of, an external counter slice.
  • asap_sketchlib::HllSketch exposes registers: Vec<u8>, but its update (hash, leading-zero count, register max) has no function that takes a caller's register slice.

So the executor keeps one sketchlib object per group, which #762 allows as the fallback ("otherwise one object per group").

Proposal

asap_sketchlib exposes, per fixed-size sketch (HLL, Count-Min, Count Sketch), kernels over a caller-owned slice:

  • update(slice, item)
  • merge(dst_slice, src_slice)
  • estimate(slice, ...)
  • a slice length for the sketch's parameters

StateColumn then gains a StateStorage::Flat { buffer: Vec<T>, stride } variant. StateColumnUpdater, SummaryMerge and SummaryEstimate call the slice kernels, with no per-group object.

Scope and acceptance

  • In scope: HLL, Count-Min and Count Sketch state columns as flat buffers, with the same states (byte for byte) as the per-object path, checked by tests/state_column_updater.rs.
  • Out of scope: variable-size sketches (KLL, DDSketch, KMV, UnivMon, the top-k heaps), which stay one object per group.

Status and related work

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions