Skip to content

Allow updating theta, tuple and CPC sketches with a pre-computed hash #807

Open

Description

@davecromberge

Use case

We build audience statistics by unrolling event data: each row's ID is added to many sketches at once, one per tag the end user belongs to (often hundreds per row), and to both a theta and a CPC sketch. Every update(id) computes the same seeded MurmurHash3 x64-128 again, so a row hashes one ID hundreds of times.

What I measured

Hashing each ID once per row and passing that hash to every sketch gives byte-identical sketches. It cut 16–26% of total compute in our production workloads, which are dominated by sketch updates. To get there we had to call the package-private methods by name through MethodHandles, which is fragile across releases.

Current state

The hash entry points already exist, but aren't public:

  • UpdatableThetaSketch.hashUpdate(long hash) (package-private, abstract), fed hash(datum, seed)[0] >>> 1;
  • CpcSketch.hashUpdate(long hash0, long hash1) (package-private).

Proposal

Make these public, or add public equivalents, with the contract that the caller computed MurmurHash3 x64-128 using the sketch's seed. Pairing them with a public helper that computes that hash for a given seed would make the contract hard to get wrong. For example:

long[] h = UpdatableThetaSketch.hashOf(id, seed);   // or a shared hashing utility
thetaSketch.hashUpdate(h[0] >>> 1);                          // or take the raw pair and shift internally
cpcSketch.hashUpdate(h[0], h[1]);

Sketches built this way stay compatible with ones built from items, as long as the seed matches.

Questions

  • Is exposing this acceptable, given that responsibility for the seed moves to the caller?
  • Should the theta method take the raw 128-bit pair and apply >>> 1 itself, so theta and CPC share one input?
  • Should the same API go to datasketches-cpp and datasketches-rust, so the languages stay consistent? We also need it in Rust.

If this is acceptable, I'm able to contribute PRs with tests showing parity between update(item) and hashUpdate(hash).

Activity

  1. leerho commented on Nov 19, 2026

    @leerho
    Member

    Hello @davecromberge, it is good to hear from you!

    When we did the original work on sketches back in 2012-2014, few engineers had even heard of sketches, so we felt it was important to try to protect sketch users from themselves. Thus, the fixed hash function, default hash seed, the short seed hash, etc.

    Now, sketching is more widespread, and I think it is appropriate to open up more access into the fundamental hashing operations of these sketches.

    Your idea makes sense, but I think the implementation will need to be thought out carefully.

    • We don't want any code duplication. If we set up a "HashUtility" somewhere it should also be leveraged by the update(*) methods currently in the sketches that use hashing: Theta, Tuple, CPC, etc. This would minimize API disruption for users that don't have your use case.
    • There is other "hash conditioning" that goes on in the update(*) functions other than the (h >>> 1) operation: floating-point, strings, and arrays all have special canonicalization operations and checks. It would be nice if all of this special handling could also be centralized into this "HashUtility". This will make it trivial to add additional update types that the current sketches don't handle, e.g., 'update(MemorySegment), update(short[]), etc.".
    • The fact that some sketches use 128 bits and others only use 64 bits is a wrinkle we will have to think through.
    • The result, I think, would mean a rewrite of the whole "update(item, seed?)" section of a number of sketches.
    • If you are willing to propose an initial design for this, we can discuss it here.
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

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions