Skip to content

feat(theta): serialize union results directly #320

Open

Description

@tisonkun

Problem

A Theta union currently produces bytes through union.to_sketch(ordered).serialize(). Result extraction collects retained entries into an owned vector, applies the final theta and nominal-capacity rules, and optionally sorts it before the compact sketch writes another buffer. Callers that only need serialized results should not have to construct an independent compact sketch first.

Suggested approach

  • Add direct union-result serialization with explicit ordered/unordered output semantics.
  • Share result preparation and encoding with compact-sketch serialization. Retain only the scratch storage needed for selection or sorting rather than requiring an owned intermediate sketch.
  • Preserve final-theta filtering, trimming to nominal capacity, canonical empty/singleton handling, and seed metadata. Serializing the internal hash table as-is is not correct.
  • Start with uncompressed union results. Also evaluate how the same internal encoding support can serve ThetaIntersection and ThetaSketch::compact(...).serialize(); these can be follow-up contributions. Intersection has an uninitialized result distinct from an empty sketch, which must remain explicit.

Start with datasketches/src/thetafamily/theta/union.rs, theta/sketch.rs, and common/union.rs. PR #317 provides the HLL motivation. Keep any shared implementation internal; a new cross-sketch public serialization trait is not required.

Validation

Use the existing compact-result path as the reference. Cover ordered/unordered output, exact and estimation modes, empty and singleton results, mixed input precisions, and unions whose internal retained count exceeds nominal capacity. Verify compatibility fixtures and benchmark elapsed time and allocations. Establish any claimed performance improvement with measurements.

Follow CONTRIBUTING.md for changelog entries, integration-test placement, serialization fixtures, and the required checks.

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

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