Use sketchlib-rust sketches #124

Activity

1. milindsrivastava1997

   assigned

   GnaneshGnani

   and

   zzylol

   on Mar 4, 2026
2. milindsrivastava1997 commented on Mar 4, 2026

   

   milindsrivastava1997

   on Mar 4, 2026

   ContributorAuthor

   More actions

   Originally by @linear[bot] on 2026-02-17:

   PRO-415
3. milindsrivastava1997

   added

   asap-query-engine

   on Mar 4, 2026
4. milindsrivastava1997 commented on Mar 4, 2026

   

   milindsrivastava1997

   on Mar 4, 2026

   ContributorAuthor

   More actions

   Originally by @GnaneshGnani on 2026-02-27:

   CountMin

   Type / shape

   • sketch-core: CountMinSketch is a plain struct:
     • sketch: Vec<Vec<f64>>
     • row_num: usize
     • col_num: usize
   • sketchlib-rust: CountMin<S, Mode> is generic:
     • usually used as CountMin<Vector2D<i32>, RegularPath>
     • stores counts in a MatrixStorage instead of a raw Vec<Vec<f64>>.

   Key argument

   • sketch-core:
     • update(&str, f64)
     • query_key(&str) -> f64
     • The key is always a &str (caller can pre-join labels with ";" if needed).
   • sketchlib-rust:
     • insert(&SketchInput)
     • estimate(&SketchInput) -> S::Counter
     • To use a string key, the caller passes SketchInput::Str("key") or SketchInput::String("key".into()).

   Value argument

   • sketch-core:
     • value: f64 is added directly into the matrix cell (+ value).
     • This supports both count (+1) and sum semantics.
   • sketchlib-rust:
     • Each insert increments an integer counter (i32 / i64 / i128) by 1 (or by many for insert_many).

   Hashing

   • sketch-core:
     • Uses xxhash_rust::xxh32(key_bytes, i as u32) per row.
     • 32‑bit hash, different seed per row.
   • sketchlib-rust:
     • Uses hash64_seeded(row_idx, &SketchInput) (TwoX-based 64‑bit hash).
     • Different hash family and width.

   Merge

   • sketch-core:
     • merge(Vec<CountMinSketch>) -> Result<CountMinSketch, _>
     • merge_refs(&[&CountMinSketch]) -> Result<CountMinSketch, _>
     • Returns a new sketch by adding matrices element‑wise.
   • sketchlib-rust:
     • merge(&mut self, &Self)
     • Modifies self in place.

   Serialization

   • sketch-core:
     • serialize_msgpack() -> Vec<u8>
     • deserialize_msgpack(&[u8]) -> Result<Self, _>
     • Serializes the explicit struct fields { row_num, col_num, sketch } via MessagePack.
   • sketchlib-rust:
     • serialize_to_bytes() -> Result<Vec<u8>, _>
     • deserialize_from_bytes(&[u8]) -> Result<Self, _>
     • Serializes the generic struct via derived serde; layout is different from CountMinSketch.

   UDAF helpers

   • sketch-core:
     • aggregate_count(depth, width, keys, values) -> Option<Vec<u8>>
     • aggregate_sum(depth, width, keys, values) -> Option<Vec<u8>>
     • These are one‑shot helpers tailored to Arroyo UDFs.
   • sketchlib-rust:
     • No built‑in one‑shot aggregation helpers; caller builds the sketch manually.

   ---

   KLL

   Type / name

   • sketch-core:
     • KllSketchData { k: u16, sketch_bytes: Vec<u8> } (wire wrapper).
     • KllSketch { k: u16, sketch: KllDoubleSketch }.
   • sketchlib-rust:
     • KLL { items, levels, k, m, num_levels, ... }.

   Construction

   • sketch-core:
     • KllSketch::new(k: u16).
   • sketchlib-rust:
     • KLL::init_kll(k: i32) (and init(k: usize, m: usize)).

   Update input

   • sketch-core:
     • update(value: f64) accepts a plain f64.
   • sketchlib-rust:
     • update(&SketchInput) -> Result<(), &'static str> expects a SketchInput that can be converted to f64 (e.g., SketchInput::F64(value)).

   Query

   • sketch-core:
     • get_quantile(q: f64) -> f64.
   • sketchlib-rust:
     • quantile(q: f64) -> f64.
     • Also cdf() for CDF operations.

   Merge

   • sketch-core:
     • merge(Vec<KllSketch>) -> Result<KllSketch, _>
     • merge_refs(&[&KllSketch]) -> Result<KllSketch, _>
   • sketchlib-rust:
     • merge(&mut self, &KLL)
     • In‑place merge.

   Serialization

   • sketch-core:
     • serialize_msgpack() -> Vec<u8> and deserialize_msgpack(&[u8]) -> Result<Self, _>
     • Uses KllSketchData { k, sketch_bytes } around the inner dsrs sketch serialization.
     • Also from_dsrs_bytes(&[u8], k) for legacy formats.
   • sketchlib-rust:
     • serialize_to_bytes() -> Result<Vec<u8>, _>
     • deserialize_from_bytes(&[u8]) -> Result<Self, _>
     • Serializes the Rust KLL struct directly; wire layout differs from KllSketchData.

   UDAF helper

   • sketch-core:
     • aggregate_kll(k, values: &[f64]) -> Option<Vec<u8>>.
   • sketchlib-rust:
     • No built‑in UDAF helper; caller would need to construct and serialize manually.

   ---

   Hydra KLL

   Dedicated vs generic type

   • sketch-core:
     • Dedicated HydraKllSketch type:
       • HydraKllSketch { sketch: Vec<Vec<KllSketch>>, row_num, col_num }.
   • sketchlib-rust:
     • Generic Hydra { row_num, col_num, sketches: Vector2D<HydraCounter>, type_to_clone }.
     • KLL appears as HydraCounter::KLL(KLL).

   Update key/value

   • sketch-core:
     • update(&str, value: f64):
       • Hashes the string key for each row and updates the corresponding KllSketch.
   • sketchlib-rust:
     • update(&str, &SketchInput, Option<i32>):
       • Same string key, but value is a SketchInput (e.g. SketchInput::F64(value)).
       • Splits the key into parts on ';' and updates multiple combinations (multi-dimensional behavior).

   Query

   • sketch-core:
     • query(&str, quantile: f64) -> f64:
       • For a key, finds the appropriate cell in each row, computes KllSketch::get_quantile, and returns the median across rows.
   • sketchlib-rust:
     • query_key(Vec<&str>, &HydraQuery) -> f64:
       • For KLL, uses HydraQuery::Quantile(f64) (and can also use HydraQuery::Cdf(f64)).
     • There is also:
       • query_frequency(Vec<&str>, &SketchInput) -> f64
       • query_quantile(Vec<&str>, threshold: f64) -> f64 (CDF-based).
   • Relationship:
     • A call like HydraKllSketch::query("key", q) in sketch-core corresponds to:
       • Hydra::query_key(vec!["key"], &HydraQuery::Quantile(q)) in sketchlib-rust.

   Construction

   • sketch-core:
     • HydraKllSketch::new(row_num, col_num, k).
   • sketchlib-rust:
     • Hydra::with_dimensions(row_num, col_num, HydraCounter::KLL(KLL::init_kll(k))).

   Serialization

   • sketch-core:
     • serialize_msgpack() and deserialize_msgpack() on HydraKllSketchData.
   • sketchlib-rust:
     • serialize_to_bytes() / deserialize_from_bytes() on Hydra.
     • Both use MessagePack but with different wrapper types.

   UDAF helper

   • sketch-core:
     • aggregate_hydrakll(...) -> Option<Vec<u8>>.
   • sketchlib-rust:
     • No one‑shot UDAF helper for Hydra; caller must construct and serialize explicitly.

   ---

   HLL (HyperLogLog)

   Type / name

   • current implementation (not yet in sketch-core):
     • HllSketch in datafusion_summary_library, wrapping hyperloglogplus::HyperLogLogPlus.
   • sketchlib-rust:
     • HyperLogLog<Regular> and HyperLogLog<DataFusion>, using a custom HllBucketList storage.

   Construction

   • current:
     • HllSketch::new() (with fixed precision).
   • sketchlib-rust:
     • HyperLogLog::<Regular>::new()
     • HyperLogLog::<DataFusion>::new().

   Insert input

   • current:
     • insert<T: Hash>(&T) – accepts any hashable type directly.
     • insert_bytes(&[u8]).
   • sketchlib-rust:
     • insert(&SketchInput) – expects a SketchInput (e.g. U64, Str, String, Bytes).
     • Caller must wrap the underlying data into SketchInput.

   Query (cardinality)

   • current:
     • count() -> u64.
   • sketchlib-rust:
     • estimate() -> usize.
     • No count() alias by default; semantic is the same (returns a cardinality estimate).

   Merge

   • current:
     • merge(&mut self, &mut other) (for the hyperloglogplus type).
   • sketchlib-rust:
     • merge(&mut self, &Self) for HyperLogLog<Variant>.

   Serialization

   • current:
     • to_bytes() -> Vec<u8> and from_bytes(&[u8]) -> Option<Self> using hyperloglogplus’s internal format.
   • sketchlib-rust:
     • serialize_to_bytes() -> Result<Vec<u8>, _> and deserialize_from_bytes(&[u8]) -> Result<Self, _> using its own MessagePack-based format.
5. milindsrivastava1997

   linked a pull request that will close this issueSketchlib rust migration #161on Mar 6, 2026
6. GnaneshGnani

   linked a pull request that will close this issueAdd backend abstraction for sketch implementations #207on Mar 20, 2026
7. milindsrivastava1997

   closed this as completedin #207on Mar 20, 2026