Skip to content

query-engine: semicolon-joined group keys collide #912

Open

Description

@milindsrivastava1997

Problem

Group keys are turned into strings by joining label values with ; and turned back by splitting on ;. The encoding is not injective, so distinct groups can collide:

labels encoded
["a;b"] a;b
["a", "b"] a;b
[] ``
[""] ``

A label value containing ; therefore merges two groups in a sketch, and decoding splits it into the wrong label list.

Where

  • Encode:
    • KeyByLabelValues::to_semicolon_str (data_model/key_by_label_values.rs)
    • extract_group_key (precompute_engine/ingest_source.rs)
    • CMS, HydraKLL and CMS-with-heap accumulators (sketch keys)
    • accumulator_factory.rs (CMS / CMS-with-heap updaters)
    • DeltaSetAggregatorAccumulator::serialize_to_bytes
  • Decode:
    • KeyByLabelValues::from_semicolon_str
    • build_group_key_label_values (precompute_engine/worker.rs)
    • CountMinSketchWithHeapAccumulator::get_topk_keys

extract_group_key maps a missing label to "". That matches Prometheus semantics (missing == empty) and is not part of this issue.

Fix

One lossless encoding, defined once on KeyByLabelValues and used by every site above in place of ; join/split. Proposed: a JSON array of the label values (["a;b"] vs ["a","b"]), via serde_json, which is already a dependency.

Tests

  • Regression: ["a;b"] / ["a","b"] and [] / [""] encode differently and round-trip exactly.
  • Sketch accumulators: two groups that collide today get separate estimates (CMS, HydraKLL, CMS-with-heap top-k keys).
  • Precompute engine end to end: a label value containing ; comes back as one label, not two.

Ordering

After #911. #911 keeps the ; encoding so its baselines isolate the sketchlib upgrade; this change moves sketch hashes on its own.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions