HarperFast / HarperFast/harper

HNSW: graph-size resolution is a lifetime id high-water mark — churn-heavy tables permanently over-provision build/search ef

Open
#2,182 0 comments 0 reactions 0 assignees View on GitHub
area:performance area:search enhancement
Dominant language
JavaScript
Stars
89
Forks
10
Avg merge
2d 6h
Merged PRs (30d)
200

Description

Follow-up to #2180 / #2181, from the pre-push review's main finding.

Both HNSW auto-scales (search `ef`, and construction `ef` as of #2181) resolve graph size from the shared id counter — a **lifetime high-water mark of allocated node ids**. Deletes never decrement it, so a churn-heavy table (TTL eviction, delete-and-reinsert ingest) reads permanently high. On the search side that means a generous-but-capped `ef`. On the build side it means a table holding, say, 30K live vectors that has allocated 5M ids over its life resolves 5M → `efConstruction` pinned at the cap → every insert runs a 512-candidate connection search on a 30K-node graph, ~5x the base build CPU, inside the write transaction, forever — with zero recall benefit. Documented as an accepted caveat in DESIGN.md (bounded at `AUTO_EFC_MAX`, wastes CPU, never hurts recall), but the right fix is a count that tracks live nodes.

Sketch: a second slot in the shared `next-id` buffer maintained as a live count (increment on insert, decrement on remove). The hard parts are (a) re-seeding it O(1) after restart — the largest-id reverse seek that re-seeds the id counter has no live-count analogue, and an exact count is a full key scan; (b) mixed-version workers sharing the buffer during a rolling upgrade. A persisted periodically-checkpointed count (exact-on-rebuild, drift-bounded between checkpoints) may be the pragmatic middle.

Also worth considering alongside (from the same review): a "pinned build, auto search" configuration does not currently exist — setting `efConstruction` pins the search-side default too, so the escape hatch for the churn cost trades away search-ef auto-scaling.

Generated by Claude Fable 5.

Contributor guide

Open the contributing guide

Research direction

Start with DESIGN.md and the shared next-id buffer, then trace the restart re-seeding path and the insert/remove updates for HNSW auto-scaling. Resolve how a live-node count should be persisted, rebuilt, and shared with mixed-version workers; done means churn-heavy tables scale ef values from live nodes without breaking restart or rolling-upgrade behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
javascript, node.js
Domain
databases, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.