Use sketchlib-rust sketches

[milindsrivastava1997]

[milindsrivastava1997]

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

PRO-415

[milindsrivastava1997]

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.