Skip noncompetitive rescore heap updates

perfloop/weaviate · INEFFICIENT ALGORITHM

https://perfloop.ai/t/oss/case_va7dqez3c6

Verdict

OPEN · opened 2026-08-12

Hypothesis

I traced `knnSearchByVector` into `rescore`, then inspected the result queue and the regular layer-search admission path. The caller supplies a max queue, and `rescore` empties it before every successful exact-distance result unconditionally executes `Insert` and, once full, `Pop`. The regular layer search instead tests the current worst result before inserting.

After `res` has `k` entries, a strictly worse exact distance cannot remain in the max queue, yet this path still runs the queue’s bubble-up and heapify work before removing an entry. This happens once per successfully rescored candidate on each compressed single-vector request with rescoring enabled. The candidate count is `len(ids)`; under default dynamic EF settings it can range from 100 to 500, while configured rescore caps can change that range. The source check does not establish the rejected-candidate fraction or whether this work outweighs the per-vector LSM lookup and distance calculation.

A case session should differentially test returned IDs and distances, then benchmark `N=20`, `100`, and `500` across `k` values and score distributions while profiling `rescore` and priority-queue CPU. The confirming signal is fewer `Insert` and `Pop` calls and lower CPU only when `N > k` and exact distances fail the current cutoff.

Change to test: Under `mu`, compare each exact distance with the full max queue’s worst entry and skip mutation for strictly noncompetitive candidates. Use the queue’s existing ordering to preserve equal-distance, NaN, and `k == 0` behavior.

Where it lives

perfloop/weaviate · adapters/repos/db/vector/hnsw/search.go

Evidence

No usable result yet.

Timeline