Anurag’s Read

Larger than RAM Vector Indexes for Relational Databases.

A deep design of a transactional vector index that does not fit in memory, with reasons for each choice. The LSM-style appends, versioning and WAL recovery apply well beyond vectors.
Score
8.8
Verdict
Must read
Blog and date
PlanetScale,
Original length and level
25 min, advanced
Topics
vector search, mysql, indexes, storage
Read the original

Context

Most nearest-neighbor research assumes the index fits in RAM, is static and ignores transactions. Relational tables have constant writes, datasets larger than RAM and ACID needs. PlanetScale wanted a native MySQL index so sharded clusters could use it.

A SELECT after commit must see committed vectors, and aborted ones must never appear.

Architecture

The index has two layers. The head index is an in-memory HNSW graph over sampled heads. Each head owns a posting list of nearby vectors, stored as InnoDB rows.

A query searches the head graph, then reads the matching posting lists. An insert searches the head graph and appends to one or more lists, copying boundary vectors for recall. Background jobs keep list sizes bounded.

Mechanisms

M1

Append-only postings

Rewriting a blob to add a vector copies it, leaves garbage and needs a row lock. Instead each posting list is many rows with key (head id, sequence). An insert adds a row with a new increasing sequence. A read becomes a prefix range scan, and the rows are joined.

M2

Splits

A list that grows too large is split by background job after commit. K-means groups its vectors, and the paper's two clusters can become more under heavy inserts. New centroids go into the head graph. Splits lower recall, because local clustering differs from global nearest assignment.

M3

Reassignment with versions

After a split some vectors sit under a head that is no longer nearest. If a vector is farther from its new head than from the old one, it is queued for a move. A move appends the vector to the new list with a bumped version byte. An in-memory version table marks older copies stale, so queries skip them.

M4

Merges and deletes

Stale entries inflate lists, so merges gather neighbor heads, drop stale vectors and recompute the centroid. A delete only sets a flag in the version table. An update becomes a delete plus an insert in the user table.

M5

Crash recovery

Posting changes ride InnoDB transactions. Head graph changes go to a WAL tied to the same job transaction. Recovery loads the last serialized graph and replays the WAL. A compaction job serializes the graph and truncates the WAL, and only background jobs change the graph.

Design decisions

No.ChoseInstead ofWhy
D1Hybrid head graph plus InnoDB postingsGraph stored in tables, or the whole graph in memoryTable graphs need serial B-tree lookups and are slow. In-memory graphs need RAM for every vector.
D2Emulate LSM merges on InnoDBMyRocksMySQL requires one engine per table and index, and MyRocks has slow range scans.
D3Random sampling of headsSPANN's BK-tree clusteringIt is simpler and works well at scale.

Key numbers

  • Heads default to 20% of vectors.
  • Build needs up to 30% of dataset size in memory.
  • Steady state reserves about 20% or less.
  • Claimed recall is 99.9%.
  • Version counter is 1 byte.
  • OpenAI embeddings have 1536 or 3072 dimensions.

Failures and limits

  • No independent benchmarks are given, and the recall and memory figures are the authors' claims.
  • Stale data and recall loss build up between maintenance jobs.
  • Small datasets may get an unbalanced head graph.

Lessons you can use

  • Turn read-modify-write updates into appends with a composite key.
  • Use version counters to retire data without rewriting it.
  • Run repair work in the background and keep the commit path short.
  • Pair an in-memory structure with a WAL and snapshots for durability.

Glossary

HNSWA layered graph used for approximate nearest neighbor search.
Posting listThe set of vectors stored for one head.
LSM treeA write-optimized structure that merges sorted files in the background.
CentroidThe center vector of a cluster.