Skip to content

Evaluate smaller sorts for unique query metadata #795

Closed

Description

@adityamukho

Follow-up to #772. The audit found small stable-sort specializations for metadata whose keys are intended to be unique:

  • query/datalog/prepared.rs::collect_slot_names: sort names collected from a HashSet.
  • query/engine/plan.rs::Builder::or: sort branch variable names collected from a map.
  • query/engine/plan.rs::Builder::sub: sort imported (name, slot) pairs by slot.

At baseline 3d19abbce5dd8d5244641ff0d7ba8bad5424d07f, Rust 1.99.1 with the audit lock and unchanged release profile, the first two changes together independently reduced the CLI from 1,263,592 to 1,263,240 bytes (352 saved). The import-sort prototype independently produced 1,262,936 bytes (656 saved). These savings are not additive; measure any combination.

The standalone string-sort probe at 100K elements was 24.2% faster for random unique names and within 2.3% for ascending/descending input across four paired socket-swapped rounds. It removes stable-sort scratch space, but this is not an end-to-end query-planning benchmark. Small query-sized lists and complete prepare/plan costs need measurement.

Scope:

  • Confirm every equal-key tie is indistinguishable. In particular, prove the import-slot invariant (including duplicate join-variable inputs and aliases) before changing the import sort; omit that change if stable ties matter.
  • Keep optimizer selectivity/cost sorts and legacy transaction replay sorts stable.
  • Preserve prepared slot order, branch variable order, plan behavior and errors using existing differential tests plus any missing tie case.
  • Remeasure independently and combined on native, browser and WASI; run relevant plan/prepared/disjunction tests, MSRV and normal coverage gates on the bench.
  • Keep public API, format, size cap and coverage floors unchanged.

Activity

  1. added this to the v3.0.0 milestone on Oct 29, 2026
  2. added a commit that references this issue on Oct 30, 2026
  3. adityamukho commented on Oct 30, 2026

    @adityamukho
    CollaboratorAuthor

    Done in #799 (merged into v3): all three sorts are unstable; import-slot invariant proved and tested. Sizes: native −1,008, WASI −1,752, browser −1,886 bytes; planning time unchanged within noise.

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

    enhancementNew feature or requestperformanceBenchmark performance regressions

    Type

    No type

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions