The turbovec Index Access Method (design doc)

Status (v1.3.0): the turbovec index AM is default-on and the relfile-resident page format is the only storage strategy. The experimental_index_am and relfile_storage Cargo features were retired in Phase Q; the historical bits below are preserved for context but the build instructions have been brought up to date.

TL;DR

# Default build includes the AM:
cargo build

# Test it (requires cargo-pgrx):
cargo pgrx test pg<N>

# Stripped-down build without the AM (no .so footprint for AM
# scan/insert/build code):
cargo build --no-default-features --features pg<N>

Historical note: why a Cargo feature gate (and why it’s gone)

The IndexAmRoutine implementation is several hundred lines of unsafe extern "C-unwind" FFI. It interacts with the Postgres lock manager, snapshot machinery, and memory contexts. v0.3..v0.8 shipped it behind a Cargo feature so users couldn’t accidentally CREATE INDEX ... USING turbovec and trip an unfinished code path. - The code is still in tree, reviewable, and ready to enable as soon as it is validated against a real cluster.

Module map (src/index/)

src/index/
├── mod.rs         # IndexAmRoutine builder + handler entry point + opclass DDL
├── options.rs     # bit_width / dim / lists / assign_dups / graph reloptions
├── page.rs        # meta page + wire format (MetaPageData, VERSION = 8, KIND_*)
├── relfile.rs     # relfile-resident page read/write (the storage strategy)
├── build.rs       # ambuild + ambuildempty (out-of-core spill + per-tuple ctx)
├── build_pool.rs  # bounded rayon pool for the parallel build phases
├── insert.rs      # aminsert (deferred-commit)
├── scan.rs        # ambeginscan / amrescan / amgettuple / amendscan
├── vacuum.rs      # ambulkdelete + amvacuumcleanup
├── cost.rs        # amcostestimate
├── validate.rs    # amvalidate
├── ivf.rs         # IVF coarse quantizer (k-means, cell directory)
├── onebit.rs      # 1-bit centered sign-BQ codec
└── graph.rs       # Vamana graph kind (DEPRECATED v2.5.0)

The opclass.rs / persist.rs files and the turbovec.am_storage side table below no longer exist. They were the v0.4–v1.2 experimental design. Since v1.3.0 (Phase Q) storage is relfile-resident via PostgreSQL’s buffer manager — ambuild/aminsert/ambulkdelete read and write the index relation’s own pages through src/index/relfile.rs, there is no SPI side table, and the opclass DDL lives in src/index/mod.rs. The section below is kept only as historical context for the retired design; read src/index/relfile.rs and src/index/page.rs for how storage actually works today.

Storage strategy (historical: retired side table)

CREATE TABLE turbovec.am_storage (
    indexrelid  oid PRIMARY KEY,
    bit_width   int4 NOT NULL,
    dim         int4 NOT NULL,
    n_vectors   int8 NOT NULL,
    payload     bytea NOT NULL,
    version     int4 NOT NULL,
    updated_at  timestamptz NOT NULL DEFAULT now()
);
  • payload is the bytes produced by IdMapIndex::write (TVIM format).
  • We do not store the index in the index relation’s main fork. Phase 5 will move to relfile-resident pages.
  • Each aminsert reads the current payload, deserialises, inserts via IdMapIndex::add_with_ids, serialises, writes back. Slow but safe. Phase 5 will introduce per-indexrelid mutex + lazy flush.

Callback responsibilities (Phase 4 minimum)

Callback Phase 4 implementation
ambuild IndexBuildHeapScan on the heap relation; for each row produce a u64 from the heap TID and a Vec
ambuildempty INSERT empty payload.
aminsert Load index from am_storage, add_with_ids, serialise, UPDATE.
ambeginscan palloc an IndexScanDesc; attach Rust-side ScanOpaque via pg_sys::palloc0 cast.
amrescan Reset cursor; capture orderby key into ScanOpaque.query.
amgettuple On first call: load index, run IdMapIndex::search; cache results. On subsequent calls: pop next result, set scan->xs_heaptid, return true. Return false when results are drained.
amendscan pfree the ScanOpaque.
ambulkdelete For each dead heap TID, IdMapIndex::remove(tid_to_u64); persist.
amvacuumcleanup No-op (Phase 4 has no incremental compaction).
amcostestimate Heuristic: n_vectors * dim * bit_width / 64.0 for total cost; 0 startup.
amoptions Parse bit_width and dim reloptions; reject bit_width ∉ {2,3,4} and dim % 8 != 0.
amvalidate Return true. Phase 5 will validate operator class support.

Operator class plumbing

CREATE OPERATOR CLASS vec_ip_ops
  DEFAULT FOR TYPE vector USING turbovec AS
    OPERATOR 1 <#> (vector, vector) FOR ORDER BY float_ops,
    FUNCTION 1 negative_inner_product(vector, vector);

CREATE OPERATOR CLASS vec_cosine_ops
  FOR TYPE vector USING turbovec AS
    OPERATOR 1 <=> (vector, vector) FOR ORDER BY float_ops,
    FUNCTION 1 cosine_distance(vector, vector);

Strategy 1 = “the order-by operator”. amcanorderbyop = true, amcanorder = false (we don’t provide a total order, only nearest- to-query ranking).

Test plan (Phase 5)

Once the scaffold compiles and cargo pgrx test pg17 --features experimental_index_am boots a cluster, the minimum acceptance suite is:

  1. CREATE INDEX docs_emb_idx ON docs USING turbovec (embedding vec_cosine_ops) WITH (bit_width = 4); succeeds.
  2. EXPLAIN (ANALYZE) SELECT id FROM docs ORDER BY embedding <=> $1 LIMIT 10; shows Index Scan using docs_emb_idx.
  3. The same query without the index returns the same top-1 result (allow recall slip on top-2..10).
  4. INSERT INTO docs ... followed by re-running the query reflects the new row.
  5. DELETE FROM docs WHERE id = ... followed by VACUUM removes the row from the index.
  6. DROP INDEX docs_emb_idx succeeds and removes the am_storage row.

Known risks (read before enabling)

  • Memory-context lifetime. Pgrx-allocated boxes inside callbacks must be transferred into Postgres’s CurrentMemoryContext or explicitly leaked into a longer-lived context (PortalContext for scan opaque). Getting this wrong looks like SEGV during scan.
  • Lock interleaving. aminsert runs under an exclusive lock on the heap row but only a RowExclusiveLock on the index. Two concurrent inserts can race on the side table. Phase 5 needs a per-indexrelid advisory lock, or moves to relfile pages.
  • Crash safety. Side-table writes are WAL-logged. A crash mid- aminsert rolls back; the index then has fewer rows than the heap until the next ambuild. Phase 5 fixes this with bgworker reconciliation.
  • swap_remove index renumbering. IdMapIndex::remove returns the slot vacated; the upstream crate’s id→slot map is updated automatically, so external consumers (us) only ever see u64 ids. We rely on this — do not switch to TurboQuantIndex::swap_remove.

References

  • pgvecto.rs — production-grade pgrx index AM. Read its src/index/algorithms/ and src/index/am.rs for working patterns.
  • Postgres docs, Index Access Method Interface.
  • pgrx-pg-sys pg17.rs — search for IndexAmRoutine and the am*_function typedefs to see the exact ABI.

Phase 18: forced-index-scan crash, fixed

For the entire v0.4..v1.0.0-rc.1 run, the index_am_forced_index_scan test case (SET enable_seqscan = off; SELECT ... ORDER BY emb <=> q LIMIT k) reliably aborted the backend with:

munmap_chunk(): invalid pointer
... server process (PID …) was terminated by signal 6: Aborted

We chased a long list of red herrings — xs_orderbyvals allocation, Box::leak lifetime tweaks, xs_recheckorderby = true/false, allocator mismatches, etc. The actual bug was a one-liner in src/index/scan.rs::amrescan:

// BUG (v0.4 .. v1.0.0-rc.1):
std::ptr::copy_nonoverlapping(
    orderbys,
    (*scan).orderByData,
    (norderbys as usize) * std::mem::size_of::<pg_sys::ScanKeyData>(), // wrong unit
);

std::ptr::copy_nonoverlapping::<T>(src, dst, count) takes count in elements of T, not bytes. We were therefore copying norderbys * sizeof(ScanKeyData) ScanKeyData elements into a slot sized for norderbys — a buffer overrun of roughly sizeof(ScanKeyData) × the requested size. That smashed the IndexScanDesc and adjacent heap chunks; the actual free() that tripped glibc’s munmap_chunk() happened much later, when the scan context was torn down and an unrelated chunk’s metadata got walked.

The other 39 tests never tripped it because the planner kept small-table ORDER BY queries on a sequential scan and amrescan was never called with norderbys > 0. Forcing the index via enable_seqscan = off was the only way to reach the buggy codepath.

Fix

std::ptr::copy_nonoverlapping(orderbys, (*scan).orderByData, norderbys as usize);
std::ptr::copy_nonoverlapping(keys,     (*scan).keyData,     nkeys     as usize);

Once the corruption was gone, the next layer of the executor turned out to need real values in xs_orderbyvals[0]. The reorder-queue path in IndexNextWithReorder (PG 16 nodeIndexscan.c) compares the AM’s claimed distance against the recomputed exact distance and elog(ERROR, "index returned tuples in wrong order") if the recompute is less than what the AM claimed. Setting xs_orderbynulls[0] = true makes the comparator return -1 and trips that error.

We therefore write f64::NEG_INFINITY into xs_orderbyvals[0] on every amgettuple — a universal lower bound that’s safe for cosine, inner-product and any future distance metric. Every tuple goes through the reorder queue and is drained in exact order at end-of-scan; we cap at k = 1024 results per scan, so the queue overhead is negligible.

Lessons

  1. Buffer overruns in copy_nonoverlapping are silent until they’re loud. The crash was nowhere near the actual write; it was wherever glibc next touched the smashed arena chunk.
  2. amcanorderbyop = true requires monotone-or-lower-bound xs_orderbyvals. NULLs are not safe under cmp_orderbyvals.
  3. Default-plan queries hide forced-plan bugs. Always include one enable_seqscan = off test case per orderby AM.

Workarounds (no longer needed; kept for the historical record)

  • v0.4..v1.0.0-rc.1 users who hit the crash were advised to use the function-driven turbovec.knn() API instead. That still works identically; the index AM is now also safe.

    SELECT k.id, k.score
FROM   turbovec.knn('docs'::regclass, 'id', 'embedding', $1, 10) k;

Phase 14+ roadmap

CREATE INDEX CONCURRENTLY support (Phase 14)

Postgres lets users build indexes without blocking writes via CREATE INDEX CONCURRENTLY. The AM contract is that ambuild is called twice:

  1. First pass with a snapshot taken at the start, while writers continue. The result must include every row visible at that snapshot.
  2. Second pass under a stricter snapshot, validating that no row inserted by writers between the two passes was missed. (PG’s built-in machinery does the diff via validate_index.)

For our side-table-persisted AM, the requirements are:

  • ambuild must be idempotent: running it twice over the same heap state must produce the same am_storage row. Our current implementation uses INSERT ... ON CONFLICT (indexrelid) DO UPDATE, so this is already true.
  • ambuild must respect the snapshot it is given. We currently walk the heap via index_build_range_scan, which uses the scan’s snapshot — already correct.
  • We need amcanorderbyop = true (we have it) and we should not set ampredlocks (we don’t).
  • aminsert for in-flight inserts during the build window must arrive at the right indexrelid. PG drives this; nothing for us to add.

Status: untested. Phase 14 deliverable is

#[pg_test]
fn cic_concurrent_with_writes() {
    // Spawn a bgworker / background INSERT loop, kick off
    // CREATE INDEX CONCURRENTLY in the test, verify the final
    // index reflects every row including those inserted during
    // the build.
}

Also need to advertise CIC support in IndexAmRoutine — PG automatically allows CIC when amcanorder = false and amclusterable = false, both of which we have. So the SQL surface should Just Work; the test is the deliverable.

Other Phase 14+ items

  • Binary-compatible vector varlena layout — replace the v0.x CBOR-derived storage with the pgvector-compatible [i32 vl_len_, i16 dim, i16 unused, f32[dim]] layout. Adds zero-copy casts to/from pgvector.vector when both extensions are installed and reduces storage overhead by ~10–15%. Pure data-layout change; does not need pgrx index AM expertise.
  • Parallel ambuild via index_build_range_scan(parallel = true) and a shared BuildState. Material wins on multi-million-row builds.
  • Recall benchmark harness — benches/recall.rs driving a pgrx cluster: load glove-200, openai-1536, openai-3072; build both pg_turbovec and pgvector hnsw indexes; compare R@k and p99 latency at matched bit budgets. Output JSON to benches/results/.
  • HNSW-on-TurboQuant — research: replace the flat IVF-like IdMapIndex with an HNSW graph whose nodes hold TurboQuant codes. Hierarchical structure for sub-millisecond k-NN at the cost of build time.