Documentation
¶
Overview ¶
Package vindex implements a btree-resident HNSW vector index for any-store.
Unlike the experimental top-level vector package (which keeps an in-memory arena), this index owns NO graph state: the HNSW graph lives entirely in btree namespaces and every operation runs against a transaction. That is what makes it correct across processes — a reader sees a consistent MVCC snapshot of the graph, a writer's mutations commit atomically with the document, and there is no per-process in-memory layer to invalidate or sync.
Index ¶
- func BuildOf(rtx *btree.ReadTx, vmeta *btree.Namespace) (uint64, error)
- func SetBuildConcurrency(n int)
- type Candidate
- type DistanceFunc
- type Hit
- type Index
- func BulkBuild(wtx *btree.WriteTx, prefix string, p Params, seed int64, ids [][]byte, ...) (*Index, error)
- func BulkBuildParallel(wtx *btree.WriteTx, prefix string, p Params, seed int64, ids [][]byte, ...) (*Index, error)
- func Compact(wtx *btree.WriteTx, prefix string, seed int64) (*Index, error)
- func Create(wtx *btree.WriteTx, prefix string, p Params, seed int64) (*Index, error)
- func Open(db *btree.DB, prefix string, seed int64) (*Index, error)
- func OpenTx(rtx *btree.ReadTx, prefix string, seed int64) (*Index, error)
- func (ix *Index) Build() uint64
- func (ix *Index) Counts(rtx *btree.ReadTx) (live, deleted, total int, err error)
- func (ix *Index) Delete(wtx *btree.WriteTx, docID []byte) (bool, error)
- func (ix *Index) Dim() int
- func (ix *Index) EfSearch() int
- func (ix *Index) Insert(wtx *btree.WriteTx, docID []byte, vec []float32) error
- func (ix *Index) MetaRoot() uint32
- func (ix *Index) Roots() map[string]uint32
- func (ix *Index) Search(rtx *btree.ReadTx, query []float32, k, efSearch int) ([]Hit, error)
- func (ix *Index) SearchCandidates(rtx *btree.ReadTx, query []float32, ef int) ([]Candidate, error)
- func (ix *Index) SetHybrid(h bool)
- func (ix *Index) SetInsertCacheSize(n int)
- func (ix *Index) SetVectorCache(v bool)
- func (ix *Index) Stats(rtx *btree.ReadTx) (Stats, error)
- type Metric
- type Params
- type Quantization
- type Stats
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BuildOf ¶ added in v2.3.0
BuildOf returns the build the index's meta record in rtx's view names (meta.build); 0 for a record written before builds were identified.
func SetBuildConcurrency ¶
func SetBuildConcurrency(n int)
SetBuildConcurrency sets the process-wide budget of concurrent build/compaction workers. n < 1 is treated as 1. In-flight builds keep the budget they captured.
Types ¶
type DistanceFunc ¶
DistanceFunc returns the distance between two equal-length vectors.
func DistanceFor ¶
func DistanceFor(m Metric) DistanceFunc
DistanceFor returns the best distance function for the metric on this CPU — the same kernel the index uses, so brute-force search ranks identically to ANN.
type Index ¶
type Index struct {
// contains filtered or unexported fields
}
Index is a btree-resident HNSW. It holds no graph state — only the namespace handles, the (immutable) parameters, the distance function, and an RNG for level generation. Every operation reads/writes through the passed transaction.
func BulkBuild ¶
func BulkBuild(wtx *btree.WriteTx, prefix string, p Params, seed int64, ids [][]byte, vecs [][]float32) (*Index, error)
BulkBuild creates a fresh index over (ids, vecs) by constructing the HNSW graph in RAM and serializing every record to the namespaces in ONE bulk pass, in label (insertion) order. This is the "build in memory, flush once" pattern every other engine uses (pgvector/Lance/DiskANN/usearch); it avoids the per-edge copy-on-write B-tree churn of Insert-per-document, the dominant cost of an Insert-built graph.
The in-RAM build mirrors Insert's algorithm exactly — same level RNG draw order, same beam search, same neighbour-selection heuristic, same back-link pruning — so for a given (seed, order, vectors) it produces a graph byte-identical to the per-insert path. The serialized records use the same encoders (encodeVec / encodeAdj / meta), so search, incremental Insert, Delete and Compact all work against a bulk-built index unchanged.
ids must be unique and len(ids)==len(vecs); each vec must have length p.Dim. It runs entirely inside wtx (atomic: on error the tx rolls back).
func BulkBuildParallel ¶
func BulkBuildParallel(wtx *btree.WriteTx, prefix string, p Params, seed int64, ids [][]byte, vecs [][]float32, threads int) (*Index, error)
BulkBuildParallel is BulkBuild with a concurrent in-RAM graph construction phase, then the same single-threaded bulk flush. This is the technique hnswlib and Lance use: many workers insert into one shared in-RAM graph guarded by per-node locks. It trades the byte-identical determinism of BulkBuild for near-linear build speedup (the graph-construction CPU, not the btree writes, is the dominant build cost). The resulting graph is a valid HNSW of equivalent recall, not byte-identical (it depends on insertion interleaving).
threads <= 0 uses GOMAXPROCS. Levels are drawn sequentially from the index RNG (deterministic), so only the connection order is nondeterministic.
func Compact ¶
Compact rebuilds the index from its live vectors, dropping every tombstone and re-densifying labels to [0, live). It runs entirely inside wtx: the index's namespaces are deleted and recreated, then the surviving vectors are re-inserted into a fresh HNSW graph. Because it is one transaction it is atomic — on commit the clean graph replaces the old one; on any error the tx rolls back with the original graph intact.
It reclaims the storage that Delete/replace only tombstoned: dead :adj nodes, superseded :vec records, and stale :lbl entries. The rebuilt graph is also of higher quality than a tombstone-laden one (deleted nodes no longer route or dilute neighbour lists), so recall improves or holds.
Returns a NEW *Index bound to the rebuilt namespaces; the caller must publish it in place of the old one and re-apply SetHybrid/SetVectorCache (the returned index defaults to plain btree mode). When there is nothing to reclaim (no tombstones and labels already dense) it is a no-op and returns an index over the existing graph unchanged.
Relabeling safety: live nodes get fresh labels, so any label-keyed RAM cache (the layer-0 mirror, the vector tier) built before the compaction would be invalid. Recreating the namespaces moves their btree root pages, so the collection's reconcile reopens the Index with fresh handles and empty caches (the same root-moved path that handles a range index's drop+recreate). The old Index object is only ever read at the pre-compaction MVCC snapshot, where its caches are still correct, so no in-place cache versioning is needed.
func Create ¶
Create initialises a new index: creates the namespaces and writes the initial meta record. Idempotent only if the namespaces don't already hold an index.
func OpenTx ¶
OpenTx resolves an existing index using a caller-provided read transaction (no nested BeginRead) — used when opening/reconciling inside another tx.
func (*Index) Build ¶ added in v2.3.0
Build returns the identity of the build this object serves (meta.build).
func (*Index) Counts ¶
Counts returns the live, tombstoned, and total-ever node counts from the meta record alone — one btree read, no namespace walk. Cheap enough for a per-write compaction-threshold check (deleted/live ratio). total is the physical label high-water mark (live + tombstones).
func (*Index) Insert ¶
Insert adds (or replaces) the vector for docID. If docID is already present its old node is tombstoned and a fresh node inserted (HNSW-standard update).
func (*Index) MetaRoot ¶
MetaRoot returns the btree root page of the index's meta namespace. The collection compares it against the on-disk namespace to detect that a peer compaction recreated the index (root moved) and the Index must be reopened.
func (*Index) Roots ¶ added in v2.3.0
Roots returns the root page of every namespace of the index, by the namespace's suffix: what a view must have for this object to serve it.
func (*Index) Search ¶
Search returns the k nearest live documents to query, ranked closest-first. efSearch <= 0 uses the index default. It is a thin ranking wrapper over SearchCandidates (which yields the beam in closest-first order); the live query pipeline uses SearchCandidates directly and owns its own sort+limit.
func (*Index) SearchCandidates ¶
SearchCandidates runs the ANN beam search and returns up to ef live candidates with their distances, in (distance, docId) ascending order — a TOTAL order, so identical queries on identical snapshots return identical sequences (query verb coherence). Membership of the ef-cut is likewise deterministic: the beam admits at the boundary by (dist, label), so the result is the unique (dist,label)-smallest ef of the visited set. Unlike Search it does NOT rank/truncate to k — the query pipeline's k-cut/sort/limit own the final windowing.
func (*Index) SetHybrid ¶
SetHybrid enables (or disables) the RAM layer-0 mirror on the read path. Call once right after Create/Open, before concurrent use. The btree stays the source of truth; the mirror is a derived, snapshot-aligned read cache.
func (*Index) SetInsertCacheSize ¶
SetInsertCacheSize configures the per-batch insert vector cache (lever 1): during a write batch, repeatedly-read node vectors (entry point and hubs) are served from a capped RAM arena instead of the btree. n is the max cached vectors (RAM ≈ n*dim*4 bytes per active write searcher); n <= 0 disables it. Call once right after Create/Open, before concurrent use.
func (*Index) SetVectorCache ¶
SetVectorCache enables (or disables) the RAM vector tier (hybrid only): layer-0 vector reads come from a RAM slab instead of the btree, making a hop pure-RAM. It caches the btree's exact :vec bytes (int8 if the index is int8), so results are unchanged. RAM cost ≈ nextLabel × vecRecordSize, where nextLabel is the label high-water mark — every delete/replace allocates a fresh label, so this grows with write churn (NOT just the live set) until a Compact resets it. Use int8 to keep it down. Call once right after Create/Open, before concurrent use.
type Metric ¶
type Metric uint8
Metric selects the distance measure. Smaller is closer for all of them.
type Params ¶
type Params struct {
Dim int
M int // max neighbours on layers >= 1 (default 16)
EfConstruction int // candidate list at insert (default 200)
EfSearch int // candidate list at query (default 64)
Ml float64 // level factor (default 0.25)
Metric Metric
Quantization Quantization
}
Params configure a freshly created index. Zero fields take defaults.
type Quantization ¶
type Quantization uint8
Quantization selects how vectors are stored in the :vec namespace. It is a pure storage choice: vectors are quantized on write and dequantized to float32 on read, so the graph, distance functions, and cross-process consistency are all unchanged — only the bytes on disk (and thus the page cache footprint) shrink.
const ( // QuantNone stores raw float32 vectors (dim*4 bytes), read zero-copy. QuantNone Quantization = iota // QuantInt8 stores a per-vector scale + int8 components (4+dim bytes), ~4x // smaller, at a small recall cost. Symmetric scalar quantization. QuantInt8 )
func (Quantization) String ¶
func (q Quantization) String() string
type Stats ¶
type Stats struct {
Dim int
Metric Metric
Quantization Quantization
M int
M0 int
EfSearch int
NodeCount int // physical nodes ever allocated (incl. tombstones)
LiveCount int // non-deleted nodes
DeletedCount int // tombstones (compaction reclaims these)
TopLayer int
Vec btree.NamespaceSize // vectors (immutable)
Adj btree.NamespaceSize // graph adjacency
Doc btree.NamespaceSize // docId -> label
Lbl btree.NamespaceSize // label -> docId
Meta btree.NamespaceSize // params + entry point
}
Stats summarises a vector index: graph parameters, node counts (live vs tombstoned), and the physical size of each backing namespace.
Source Files