index

package
v0.0.0-...-effd846 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jun 29, 2026 License: Apache-2.0 Imports: 10 Imported by: 0

Documentation

Overview

Package index implements vec's vector index access paths behind one SPI: the flat brute-force baseline and the HNSW graph (spec 07). Every index operates on positions (dense u32 internal ids, spec 02 §3) and returns candidates sorted by distance, so the query planner selects an access path without forking call sites.

The spec layout (spec 07 §8) maps the graph onto off-GC mmap-backed arrays for near-instant recovery. That layout is wired to the pager in the storage-engine slice; this package ships the complete, correct heap-backed graph and a blob serialization seam (Persist/Recover over a PageStore), the same ship-the-correct- path-then-wire-throughput discipline used for the WAL and distance tiers.

Index

Constants

This section is empty.

Variables

View Source 
var (
	// ErrIndexCorrupt is returned when an index detects unrecoverable corruption;
	// the engine surfaces it as a hard error requiring REINDEX.
	ErrIndexCorrupt = errors.New("index: corrupt, REINDEX required")
	// ErrIndexMemoryExceeded is returned by Insert when the configured memory budget
	// is exceeded (spec 07 §13.4).
	ErrIndexMemoryExceeded = errors.New("index: memory budget exceeded")
	// ErrClosed is returned when a method is called after Close.
	ErrClosed = errors.New("index: closed")
	// ErrDimMismatch is returned when a vector's length does not match the index dim.
	ErrDimMismatch = errors.New("index: vector dimension mismatch")
	// ErrBadParams is returned when build/config parameters are invalid.
	ErrBadParams = errors.New("index: invalid parameters")
)

Errors surfaced by the SPI (spec 07 §1.6).

Functions

This section is empty.

Types

type Bitmap 

type Bitmap interface {
	// Contains reports whether pos passes the filter.
	Contains(pos uint32) bool
	// Count returns the number of positions in the set, for selectivity estimation
	// (spec 07 §11.3).
	Count() int
}

Bitmap is a snapshot-visible set of allowed positions for filtered search (spec 07 §11). nil means no predicate.

type BuildParams 

type BuildParams struct {
	M              int     // max neighbors per upper layer (default 16)
	M0             int     // base-layer degree (default 2*M)
	EfConstruction int     // candidate pool size during build (default 200)
	ML             float64 // level multiplier (default 1/ln(M))
	Seed           int64   // reproducible level draws (0 = derive a fixed seed)
	Codec          Codec   // navigation codec (nil = fp32)
	Metric         Metric  // distance metric
	NaiveSelect    bool    // use naive kNN selection instead of the heuristic
}

BuildParams carries construction-time knobs (spec 07 §1.3).

type Candidate 

type Candidate struct {
	Position uint32
	Distance float32
}

Candidate is one result from Search: a position and its distance to the query under the index metric (smaller is closer; Dot/IP and Cosine are oriented so the search heap stays a min-heap, spec 07 §4.2).

type Codec 

type Codec = quant.Quantizer

Codec is the quantization codec an index uses for navigation codes; nil means full-precision fp32 (spec 07 §10, spec 09).

type Flat 

type Flat struct {
	// contains filtered or unexported fields
}

Flat is the brute-force baseline index (spec 07 §1, §11.4). It scans every live position and computes the exact distance, so its results are the recall oracle the HNSW tests measure against. The planner selects it for small collections and for the very-selective-filter fallback where an exact scan beats graph traversal (spec 07 §11.4).

func NewFlat 

func NewFlat(dim int, metric Metric) *Flat

NewFlat returns an empty flat index for the given dimension and metric.

func (*Flat) Build 

func (f *Flat) Build(ctx context.Context, positions []uint32, vectorAt func(uint32) []float32, params BuildParams) error

func (*Flat) Close 

func (f *Flat) Close() error

func (*Flat) Delete 

func (f *Flat) Delete(pos uint32) error

func (*Flat) Insert 

func (f *Flat) Insert(pos uint32, vec []float32) error

func (*Flat) MemoryBytes 

func (f *Flat) MemoryBytes() int64

func (*Flat) Persist 

func (f *Flat) Persist(ps PageStore) error

Persist serializes the flat index to one blob: dim, metric, then each live position and its vector (spec 07 §9.1, simplified to a blob seam).

func (*Flat) Recover 

func (f *Flat) Recover(ps PageStore) error

Recover reads a blob written by Persist.

func (*Flat) Search 

func (f *Flat) Search(ctx context.Context, query []float32, k int, filter Bitmap, params SearchParams) ([]Candidate, error)

func (*Flat) Stats 

func (f *Flat) Stats() IndexStats

type HNSW 

type HNSW struct {
	// contains filtered or unexported fields
}

HNSW is vec's default ANN index (spec 07 §17.1). Insert and Delete are serialized by the outer write lock; Search takes the read lock, so concurrent searches run together and exclude only an in-flight mutation. Per-node fine-grained locking (spec 07 §12.1) is a throughput slice over this correct baseline.

func NewHNSW 

func NewHNSW(cfg HNSWConfig) (*HNSW, error)

NewHNSW returns an empty HNSW index ready for Insert or Build (spec 07 §17.2).

func (*HNSW) Build 

func (h *HNSW) Build(ctx context.Context, positions []uint32, vectorAt func(uint32) []float32, params BuildParams) error

Build constructs the graph from scratch by inserting every position in order with deterministic, seeded level draws (spec 07 §5.6, §14.4).

func (*HNSW) Close 

func (h *HNSW) Close() error

Close releases the index (spec 07 §1.4).

func (*HNSW) Delete 

func (h *HNSW) Delete(pos uint32) error

Delete tombstones a point (spec 07 §7.2). The node stays in the graph as a traversal hop; entrypoint loss is repaired here (spec 07 §7.4).

func (*HNSW) Insert 

func (h *HNSW) Insert(pos uint32, vec []float32) error

Insert adds a single point (spec 07 §5.4). It is serialized by the write lock.

func (*HNSW) MemoryBytes 

func (h *HNSW) MemoryBytes() int64

MemoryBytes estimates resident bytes for the graph and stores (spec 07 §13.1).

func (*HNSW) Persist 

func (h *HNSW) Persist(ps PageStore) error

Persist serializes the whole graph to one blob through the PageStore (spec 07 §9.1). The on-disk page layout (§8) is the storage-engine slice; the blob form carries identical state: header, then per node its level, vector, and per-layer neighbor lists. Tombstoned nodes are dropped, matching a rebuild-on-persist.

func (*HNSW) Recover 

func (h *HNSW) Recover(ps PageStore) error

Recover reads a blob written by Persist (spec 07 §9.2). It validates the magic and bounds every read so a truncated blob returns ErrIndexCorrupt rather than panicking.

func (*HNSW) Search 

func (h *HNSW) Search(ctx context.Context, query []float32, k int, filter Bitmap, params SearchParams) ([]Candidate, error)

Search returns the k nearest live candidates passing filter (spec 07 §4.5).

func (*HNSW) Stats 

func (h *HNSW) Stats() IndexStats

Stats returns a counter snapshot (spec 07 §1.3).

type HNSWConfig 

type HNSWConfig struct {
	Dim            int
	Metric         Metric
	M              int
	M0             int
	EfConstruction int
	ML             float64
	Seed           int64
	Codec          Codec
	NaiveSelect    bool
}

HNSWConfig configures a new index (spec 07 §17.3).

type IVF 

type IVF struct {
	// contains filtered or unexported fields
}

IVF is the inverted-file index (spec 08 §2). It implements the Index SPI by partitioning the space into nlist Voronoi cells and scanning only the nprobe cells nearest a query. Like the HNSW index it holds full-precision vectors so it is self-contained ahead of the vector store; the spec's on-disk posting-list layout (spec 08 §2.7) is the storage-engine slice and Persist/Recover ship the whole index as one PageStore blob.

func NewIVF 

func NewIVF(cfg IVFConfig) (*IVF, error)

NewIVF constructs an empty IVF index from a config (spec 08 §2).

func (*IVF) Build 

func (idx *IVF) Build(ctx context.Context, positions []uint32, vectorAt func(uint32) []float32, params BuildParams) error

Build trains the coarse quantizer and assigns every position (spec 08 §2.4).

func (*IVF) Close 

func (idx *IVF) Close() error

Close releases index memory.

func (*IVF) Delete 

func (idx *IVF) Delete(pos uint32) error

Delete tombstones a position (spec 08 §6.2). The posting-list entry is removed at rebuild; search skips tombstoned positions in the interim.

func (*IVF) Insert 

func (idx *IVF) Insert(pos uint32, vec []float32) error

Insert appends a point to its nearest cell without retraining (spec 08 §6.1).

func (*IVF) MemoryBytes 

func (idx *IVF) MemoryBytes() int64

MemoryBytes estimates resident bytes (spec 08 §14.2).

func (*IVF) Persist 

func (idx *IVF) Persist(ps PageStore) error

Persist serializes the whole IVF index to one PageStore blob (spec 08 §13.2, §18.3). The spec's per-list page layout (spec 08 §2.7) is the storage-engine slice; the blob carries the same state the pager will eventually hold as a page run. Tombstoned positions are dropped, matching a rebuild-on-persist.

func (*IVF) Recover 

func (idx *IVF) Recover(ps PageStore) error

Recover rebuilds an IVF index from a blob written by Persist (spec 08 §13.2).

func (*IVF) Search 

func (idx *IVF) Search(ctx context.Context, query []float32, k int, filter Bitmap, params SearchParams) ([]Candidate, error)

Search probes the nprobe nearest cells and returns the top-k (spec 08 §2.5). For IVFADC it scans by ADC distance, then reranks the top candidates with the full-precision vectors (spec 08 §4.5).

func (*IVF) Stats 

func (idx *IVF) Stats() IndexStats

Stats returns a snapshot of index counters (spec 08 §19.1).

type IVFConfig 

type IVFConfig struct {
	Dim      int
	Metric   Metric
	NList    int   // coarse cells; 0 derives sqrt(n) at build (spec 08 §5.2)
	NProbe   int   // default probe count; 0 uses defaultNProbe
	PQM      int   // PQ subspaces for residual codes; 0 = plain IVF
	PQNbits  int   // bits per subspace (default 8)
	UseOPQ   bool  // rotate residuals before PQ (spec 08 §7)
	Seed     int64 // reproducible centroid training
	KMeansIt int   // Lloyd cap; 0 uses defaultKMeansIter
}

IVFConfig configures an inverted-file index (spec 08 §2, §4). A zero PQM builds plain full-precision IVF; a positive PQM builds IVFADC with PQ-encoded residuals (spec 08 §4). OPQ adds a learned rotation before residual PQ (spec 08 §7). PQ residual encoding is defined for the L2 family; for cosine/dot the index keeps full-precision entries and ignores PQM (spec 08 §17.3).

type Index 

type Index interface {
	Build(ctx context.Context, positions []uint32, vectorAt func(uint32) []float32, params BuildParams) error
	Close() error
	Insert(pos uint32, vec []float32) error
	Delete(pos uint32) error
	Search(ctx context.Context, query []float32, k int, filter Bitmap, params SearchParams) ([]Candidate, error)
	Persist(ps PageStore) error
	Recover(ps PageStore) error
	Stats() IndexStats
	MemoryBytes() int64
}

Index is the normative SPI every ANN (and flat) index implements (spec 07 §1.2).

type IndexStats 

type IndexStats struct {
	NodeCount        int64
	TombstoneCount   int64
	LayerHistogram   []int64
	EntrypointPos    uint32
	DistComputations int64
	SearchCount      int64
	MemoryBytes      int64
}

IndexStats is a snapshot of index counters (spec 07 §1.3).

type Metric 

type Metric = distance.Metric

Metric is the distance metric an index ranks by (spec 07 §1.3).

type PageStore 

type PageStore interface {
	PutBlob(b []byte) error
	GetBlob() ([]byte, error)
}

PageStore is the persistence seam (spec 07 §9). The pager implements it; an index serializes its whole state to one blob through PutBlob and reads it back through GetBlob. Page-granular dirty tracking is a later storage-engine slice.

type SPANN 

type SPANN struct {
	// contains filtered or unexported fields
}

SPANN is the SPANN index (spec 08 §10). The centroid index is an in-memory HNSW (spec 08 §10.3) whose positions are centroid ids; posting lists hold member positions. The spec's on-disk posting lists with async reads (spec 08 §10.5) are the storage-engine slice; this build keeps lists and vectors in memory and ships the same boundary-replicated search, with Persist/Recover over a PageStore blob.

func NewSPANN 

func NewSPANN(cfg SPANNConfig) (*SPANN, error)

NewSPANN constructs an empty SPANN index from a config (spec 08 §10).

func (*SPANN) Build 

func (s *SPANN) Build(ctx context.Context, positions []uint32, vectorAt func(uint32) []float32, params BuildParams) error

Build trains centroids, builds the in-RAM centroid index over them, then assigns every point to its nearest list plus any boundary list within the replication factor (spec 08 §10.4, §15.4).

func (*SPANN) Close 

func (s *SPANN) Close() error

Close releases index memory.

func (*SPANN) Delete 

func (s *SPANN) Delete(pos uint32) error

Delete tombstones a position (spec 08 §11.5). Search skips tombstoned members; physical removal from posting lists happens at consolidation.

func (*SPANN) Insert 

func (s *SPANN) Insert(pos uint32, vec []float32) error

Insert assigns a new point to its lists immediately (spec 08 §11.3). The spec's delta buffer with background consolidation (spec 08 §11.2) is the streaming slice over this correct foreground path.

func (*SPANN) MemoryBytes 

func (s *SPANN) MemoryBytes() int64

MemoryBytes estimates resident bytes (spec 08 §14.2).

func (*SPANN) Persist 

func (s *SPANN) Persist(ps PageStore) error

Persist serializes the whole index to one PageStore blob (spec 08 §13.2, §18.3). The centroid index is not serialized: it is a deterministic HNSW over the centroids and is rebuilt on Recover, so the blob carries only centroids, vectors, and posting lists. Tombstoned positions are dropped, matching rebuild-on-persist.

func (*SPANN) Recover 

func (s *SPANN) Recover(ps PageStore) error

Recover rebuilds a SPANN index from a blob written by Persist, reconstructing the centroid index from the centroids (spec 08 §13.2). Bounds-checked throughout.

func (*SPANN) Search 

func (s *SPANN) Search(ctx context.Context, query []float32, k int, filter Bitmap, params SearchParams) ([]Candidate, error)

Search probes the nprobe nearest centroids via the centroid index, scans their posting lists, dedups replicated members, and returns the k nearest by exact distance (spec 08 §10.5, §10.6).

func (*SPANN) Stats 

func (s *SPANN) Stats() IndexStats

Stats returns a snapshot of index counters (spec 08 §19.1).

type SPANNConfig 

type SPANNConfig struct {
	Dim          int
	Metric       Metric
	NList        int     // number of posting lists (centroids); 0 derives sqrt(n)
	NProbe       int     // posting lists scanned per query; 0 uses defaultNProbe
	ReplicaCount int     // max lists a boundary point joins; 0 uses defaultSpannReplicas
	BoundaryEps  float64 // replication factor; 0 uses defaultBoundaryEps
	Seed         int64
	KMeansIt     int
}

SPANNConfig configures a SPANN index (spec 08 §10): an in-RAM centroid index over disk-resident posting lists, with boundary replication so a query that lands near a cell edge still finds neighbors that fell into the neighboring cell.

type SearchParams 

type SearchParams struct {
	EfSearch      int  // HNSW candidate pool size (default 50)
	MaxCandidates int  // hard cap before rerank (default 2*k)
	UseRerank     bool // rerank top candidates with full-precision vectors
	RerankFactor  int  // rerank this many * k candidates (default 3)
	NProbe        int  // IVF/SPANN: lists to probe (default 16, spec 08 §5.3)
	BeamWidth     int  // DiskANN: beam width (default 64, spec 08 §9.5)
}

SearchParams carries query-time knobs (spec 07 §1.3, spec 08 §5.5, §9.5).

type SliceBitmap 

type SliceBitmap struct {
	// contains filtered or unexported fields
}

SliceBitmap is a simple Bitmap over a set of positions, sufficient for the query layer and tests (spec 07 §11). The storage layer supplies roaring-style bitmaps later; the SPI only needs Contains and Count.

func NewSliceBitmap 

func NewSliceBitmap(positions []uint32) *SliceBitmap

NewSliceBitmap builds a bitmap from the given positions.

func (*SliceBitmap) Contains 

func (b *SliceBitmap) Contains(pos uint32) bool

func (*SliceBitmap) Count 

func (b *SliceBitmap) Count() int

type Vamana 

type Vamana struct {
	// contains filtered or unexported fields
}

Vamana is the DiskANN graph index (spec 08 §8). It implements the Index SPI as a single flat graph of fixed max degree, the structure that maps one node to one SSD page. This build holds the adjacency and the colocated vectors in memory; the spec's on-disk adjacency-block layout and async beam reads (spec 08 §8.7, §9.2) are the storage-engine slice, and Persist/Recover ship the graph as one blob.

func NewVamana 

func NewVamana(cfg VamanaConfig) (*Vamana, error)

NewVamana constructs an empty Vamana graph from a config (spec 08 §8).

func (*Vamana) Build 

func (g *Vamana) Build(ctx context.Context, positions []uint32, vectorAt func(uint32) []float32, params BuildParams) error

Build runs the two-pass Vamana construction (spec 08 §8.3, §15.3): a pass at alpha=1 then a pass at the configured alpha, each greedy-searching for every point's candidates and pruning with RobustPrune, then linking backward edges.

func (*Vamana) Close 

func (g *Vamana) Close() error

Close releases graph memory.

func (*Vamana) Delete 

func (g *Vamana) Delete(pos uint32) error

Delete tombstones a position (spec 08 §11.5). Physical removal from adjacency blocks happens at delete consolidation; search skips tombstoned results meanwhile.

func (*Vamana) Insert 

func (g *Vamana) Insert(pos uint32, vec []float32) error

Insert adds a point by searching for its neighbors and linking it in immediately (spec 08 §11.3, consolidate-on-insert). The spec's in-memory delta buffer with background consolidation (spec 08 §11.2) is the streaming-throughput slice over this correct foreground path.

func (*Vamana) MemoryBytes 

func (g *Vamana) MemoryBytes() int64

MemoryBytes estimates resident bytes (spec 08 §14.2).

func (*Vamana) Persist 

func (g *Vamana) Persist(ps PageStore) error

Persist serializes the whole graph to one PageStore blob (spec 08 §13.2, §18.3). The spec's on-disk adjacency-block layout (spec 08 §8.7) is the storage-engine slice; the blob carries the same state: header, optional codec page, then per node its colocated vector and adjacency. Tombstoned nodes are dropped, matching a rebuild-on-persist, and surviving edges into them are filtered out.

func (*Vamana) Recover 

func (g *Vamana) Recover(ps PageStore) error

Recover rebuilds a Vamana graph from a blob written by Persist (spec 08 §13.2). Every read is bounds-checked so a truncated blob returns ErrIndexCorrupt.

func (*Vamana) Search 

func (g *Vamana) Search(ctx context.Context, query []float32, k int, filter Bitmap, params SearchParams) ([]Candidate, error)

Search runs beam search from the medoid (spec 08 §9.1). Navigation uses the PQ approximation when a codec is configured and full precision otherwise; the colocated full-precision vector always decides the result (spec 08 §9.1).

func (*Vamana) Stats 

func (g *Vamana) Stats() IndexStats

Stats returns a snapshot of graph counters (spec 08 §19.1).

type VamanaConfig 

type VamanaConfig struct {
	Dim       int
	Metric    Metric
	R         int     // max out-degree; 0 uses defaultVamanaR
	L         int     // build candidate pool; 0 uses defaultVamanaL
	Alpha     float64 // pass-2 prune bias; 0 uses defaultVamanaAlpha
	BeamWidth int     // default search beam; 0 uses defaultBeamWidth
	Seed      int64   // reproducible build order
	Codec     Codec   // PQ navigation copy; nil = full precision
}

VamanaConfig configures a DiskANN/Vamana graph (spec 08 §8). A non-nil Codec is the PQ navigation copy used for distance estimation during traversal (spec 08 §8.8); nil navigates with full precision. Either way the colocated full-precision vector decides the result (spec 08 §9.1).

type VectorStore 

type VectorStore interface {
	// Vector returns the fp32 vector at pos. The slice is read-only to the caller.
	Vector(pos uint32) []float32
}

VectorStore fetches full-precision vectors by position for rerank and graph navigation (spec 07 §10.4). The storage engine implements it; tests use an in-memory store.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.