Skip to content

planner/engine: deploy top-k CMSHeap on FastPath to match what sketch-bench prices #810

Closed as not planned

Description

@milindsrivastava1997

Part of #790.

Problem

The MILP prices top-k with a different sketch from the one ASAPQuery deploys:

Hash path Counters Where
sketch-bench prices (cms-heap-topk-fastpath-vector2d) FastPath i32 sketch-bench/src/wrappers/cms_heap/sketchlib.rs
ASAPQuery deploys (CountMinSketchWithHeap) RegularPath i64 asap_sketchlib portable/countminsketch_topk.rs:21 (SketchlibCMSHeap), wrapped by count_min_sketch_with_heap_accumulator.rs

sketch-bench's own doc comment on Capability::families notes that fastpath and regularpath have different cost profiles, so the planned CPU cost doesn't match what's deployed. The i32 vs i64 counters also mean the plan undercounts matrix memory by 2×.

Decision

Deploy FastPath in ASAPQuery, so it matches what sketch-bench measures. We are not switching sketch-bench to regularpath.

What the change touches

  • The accumulator. asap_sketchlib::sketches::CMSHeap<_, FastPath> is public, so ASAPQuery could build it directly rather than through the portable CountMinSketchWithHeap facade, which hardcodes RegularPath. That needs its own serde, because the facade's MessagePackCodec is what the precompute engine and query engine exchange.
  • The Go collector. ASAPCollector/asap-precompute-go emits CountMinSketchWithHeap payloads that ASAPQuery decodes with from_msgpack (see asapedgeprocessor/emit_heap_test.go). A sketch built with one hash path and queried with the other puts keys in the wrong buckets, so the Go producer has to move to FastPath hashing too, or Go-built sketches need to be refused or kept apart.
  • asap_sketchlib. The unmerged branches asapv1-only/cmsheap and asapv1-only/cleanup contain 458d02e ("drop the portable MessagePack format"). If that lands, the facade goes away and ASAPQuery has to construct sketches::CMSHeap itself anyway. That is the natural place to make this change, so coordinate with that branch.
  • Counter width. Pick one of i32 or i64 and make sketch-bench's wrapper and ASAPQuery agree. With i32, value-weighted top-k (insert_many(round(value))) needs an overflow check.
  • Planner. milp_output.rs already maps cms-heap-topk-fastpath-vector2d to CountMinSketchWithHeap. Once the engine runs FastPath, no planner change is needed.

Done when

  • The engine's CountMinSketchWithHeap uses FastPath with the agreed counter width.
  • Go-produced heap sketches are either hashed the same way or rejected.
  • A test checks that a sketch built by the engine and the sketch sketch-bench benchmarks produce the same bucket indices for the same keys.

Activity

  1. milindsrivastava1997 commented on Oct 27, 2026

    @milindsrivastava1997
    ContributorAuthor

    Duplicate of #811, which has the agreed ASAPQuery-only scope. The Go collector, asap_sketchlib and parity-test items from this issue are carried over in a comment on #811.

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