CONCEPT Cited by 1 source

HNSW index¶

Definition¶

An HNSW (Hierarchical Navigable Small World) index is a multi-layer proximity-graph ANN index with state-of-the-art recall / latency for in-memory vector search. It is the dominant in-memory vector index in practice — used by Lucene, FAISS, Vespa, Qdrant, and most mainstream vector DBs.

See systems/hnsw for the full system page.

Two structural properties¶

RAM-bound. HNSW needs the full graph in memory for good performance; random-access edge traversal is the inner loop.
No incremental reorganisation. Inserts extend the graph but full rebuilds are required periodically to maintain recall as the graph evolves — not compatible with OLTP write cadence.

Why these matter for databases¶

PlanetScale's 2024-10-22 vector-beta announcement names these exact two properties as the reason HNSW was rejected for a relational-database-hosted vector index:

"HNSW has very good query performance, but struggles to scale because it needs to fit its whole dataset in RAM. Most importantly, HNSW indexes cannot be updated incrementally, so they require periodically re-building the index with the underlying vector data. This is just not a good fit for a relational database."

— sources/2024-10-22-planetscale-planetscale-vectors-public-beta

Canonical wiki statement that "RAM-bound + no incremental updates" together disqualify HNSW for use inside a relational engine.

When it's the right choice¶

HNSW dominates when: corpus fits in RAM; writes are bulk / episodic; query latency at high recall is the performance target; the vector index can be an independent sidecar without transactional coupling to relational data.

Seen in¶

sources/2024-10-22-planetscale-planetscale-vectors-public-beta — canonical wiki statement of HNSW's structural limitations as rejection criteria for a database-hosted vector index.