Skip to content

MILP: Raqe lacks a keyed sketch's key labels (topk-of-sum heap pricing and sharing) #854

Open

Description

@milindsrivastava1997

Problem

rqe_optimizer::Raqe has no field for the labels a keyed sketch is keyed by. For a top-k-of-sum query, topk(k, sum by (l) (f(m[w]))), the heap holds one key per l value, but the Raqe's grouping is the top-k bucket grouping ([] for a global top-k). This causes two problems:

  1. Pricing. require_shapes and the accuracy curves read data_shape[[]], the per-series shape. The heap's key count is bounded by the series count, so sizing errs large, but accuracy curves measured on per-series values may not match summed values. The chosen depth, width and heap size are therefore not grounded in the actual key set.
  2. Sharing. Two top-k Raqes on one metric whose heaps need different keys (sum by (job) vs sum by (instance)) look identical to the solver. feat(planner): collapse topk(sum by (l) (sum_over_time)) into one CMS heap #849 makes plan_to_planner_output refuse such a plan (DeploymentLabelsDisagree) instead of writing a wrongly keyed heap, but the solver should never propose it.

Fix direction

Add key labels to sketch-bench's Raqe, as part of its stream/deployment identity, and price keyed sketches from data_shape[key labels]. Then populate the field in build_raqe (asap-planner-rs/src/optimizer/milp.rs) and remove the ponytail: note there.

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