vector

package
v2.0.0-alpha.16 Latest Latest
Warning

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

 Go to latest Published: Jul 3, 2026 License: MIT Imports: 12 Imported by: 0

README

Experimental: vector (ANN) search for any-store

Status: experimental spike on branch btree-vector-search. Not wired into the public anystore API yet — this package is a self-contained exploration of how to land approximate-nearest-neighbour (ANN) search on top of the embedded btree engine, using github.com/coder/hnsw as the algorithmic reference.

Note: the SIMD distance kernels moved off viterin/vek (amd64-only) to the vendored internal/simd package — AVX2/AVX512 on amd64, NEON/SVE on arm64, int8 byte kernel, pure-Go fallback. So vector.SIMD() is now true on Apple Silicon too. References to "vek" below are historical (the answer to Q1 is now "yes, on every arch, no CGO"). The production index is internal/vindex.

The goal was to answer three questions:

  1. Can we keep SIMD (vector CPU instructions) for the distance kernels, like the reference, without breaking any-store's "pure Go, no CGO" rule?
  2. How much do any-store's memory practices (arenas / struct-of-arrays / pooled scratch) buy us over an idiomatic map-and-pointers HNSW?
  3. What does it cost to make the index durable by persisting it into the btree, versus keeping it purely in memory?

What's here

File Approach
distance.go L2 / Cosine / Dot distance. SIMD via internal/simd (vendored weaviate asm: AVX2/AVX512 on amd64, NEON/SVE on arm64, pure-Go fallback; no CGO) plus scalar & hand-unrolled fallbacks kept only for the benchmark.
brute.go Exact flat scan. Ground truth for recall, O(n·dim) per query.
hnsw.go Map-based in-memory HNSW — a faithful adaptation of coder/hnsw (map[id]*node adjacency, per-node pointers). The "idiomatic Go" baseline.
hnsw_flat.go Arena / SoA HNSW — every vector in one contiguous []float32 slab, every adjacency list in one flat []uint32 arena, dense uint32 ids, pooled per-query heaps + epoch-stamped visited set. Allocation-free steady-state search.
heap.go Two-heap search frontier + epoch-stamped visitedList (arena trick: bump a generation counter instead of clearing N bytes per query).
hnsw_btree.go btree-backed persistent HNSW — wraps the flat index, persists each node (vector + per-layer adjacency) into btree namespaces, and rebuilds the arenas on reopen straight from the persisted records (no re-construction).
hnsw_flat_delete.go deletes/updates — tombstone delete, update (delete+reinsert), Compact, Rebuild, and a hard-delete-with-repair variant for cost comparison. See DELETE_UPDATE.md.
idmap.go + docindex.go doc-id mapping — IDDict turns any-store's []byte document ids into dense uint32 labels via a flat arena; DocFlatHNSW shows the composed []byte-keyed index.
Design notes & comparisons
  • DELETE_UPDATE.md — deletes/updates research + measurements (tombstones, compaction, write amplification, RAM, doc-id mapping).
  • COMPARISON_pgvector.md — vs pgvector (disk-resident buffer-cache-paged graph vs in-memory arena; the "real fork" for any-store).
  • COMPARISON_mongodb.md — vs MongoDB Atlas Vector Search (closest external/API analog; Lucene segment model; quantization; read-your-writes advantage).
  • OPTION_B.md — prototype + measurements of paging vectors through the btree page cache (disk-resident graph): pure paging is ~6–10× slower, but a quantized-routing + paged-rerank hybrid lands at ~1.7× with a fraction of the RAM (paged.go). Includes a realistic 75k markdown-doc / dim-768 capstone where paging holds 94% less RAM.

mddata_test.go (TestMDDataset) is the realistic-scale dataset: 75k synthetic topic-clustered markdown documents embedded with the feature-hashing trick (dim 768, cosine) — representative geometry, not uniform-random. Run with go test ./vector -run TestMDDataset -v (skipped in -short).

  • CROSS_HARDWARE.md — cmd/vectorbench run on three linux/amd64 machines (disk-backed, twice each). Headline: a no-AVX2 box makes distance ~25× slower (vek's fallback is even slower than the unrolled loop) — SIMD presence dominates everything; the hybrid stays the sweet spot (1.3–2.4×) and cold reload-from-disk is 8–37 ms loading only topology.
  • ARM.md — how it runs on modern ARM (Apple Silicon / Graviton / mobile). Now updated: the NEON kernel landed (internal/simd), so vector.SIMD() is true on arm64 and the old scalar penalty is recovered, int8 included.
  • PLAN_INTEGRATION.md — plan to land this in any-store as a btree-resident vector index (full-btree/Option B): where it plugs into the existing index/write-tx machinery, on-disk namespaces, write/read paths, the cross-process MVCC reliability argument, API, and phasing.

A self-contained, static, no-CGO benchmark binary lives at cmd/vectorbench — build once, copy to any linux/amd64 box (no Go needed on the target), and run -db <path> twice for build-then-cold-reload measurements.

Three ways to land it — and the one that wins

The arena/flat layout (FlatHNSW) is the centrepiece. It differs from the map-based port in exactly the ways any-store already optimises elsewhere:

  • Vectors in an arena. One []float32, vector i at [i*dim:(i+1)*dim]. No per-vector slice header, no N pointers for the GC to scan, sequential reads feeding the SIMD kernels.
  • Adjacency in an arena. One flat []uint32 grown append-only as dense ids are assigned — no map[id]*node per node. A node with top layer L occupies M0 + L*M slots; the dense+monotonic id stream is exactly the access pattern an arena is good at.
  • Pooled scratch. The two search heaps and the visited set are pooled and reused, so a steady-state query allocates nothing.

BtreeHNSW reuses that same arena layout as its on-disk format: a forward cursor over the (big-endian-keyed) nodes namespace yields nodes in id order, which is precisely the order appendRaw needs to rebuild the arenas.

Benchmarks

Machine: 32-core x86-64, Go 1.26, vek reporting AVX acceleration active. Reproduce with:

go test ./vector -run TestMemoryFootprint -v          # memory
go test ./vector -bench BenchmarkDistance -benchmem    # SIMD vs scalar
go test ./vector -bench 'BenchmarkSearch' -benchmem     # query latency
go test ./vector -bench 'BenchmarkBuild' -benchmem -benchtime=1x   # build
1. SIMD distance — keeping vector CPU instructions pays off

L2 distance, ns/op, 0 allocs:

dim scalar 4-way unrolled SIMD (vek/AVX) SIMD vs scalar
128 35.96 24.86 5.56 6.5×
768 271.3 148.9 20.32 13.4×
1536 549.2 288.4 38.28 14.3×

For typical embedding sizes (768/1536) SIMD is 13–14× faster than naive scalar and ~7× faster than what the compiler manages from unrolled Go. Distance dominates ANN work, so this is the single biggest lever — and it stays CGO-free.

2. Search latency — 20 000 × 128-dim, k=10, efSearch=64
index ns/op B/op allocs/op vs brute
brute (exact) 2 217 256 327 768 4 1×
map HNSW 446 836 240 777 518 5.0×
flat HNSW 43 942 160 1 50×

The arena index is ~10× faster than the map HNSW and ~50× faster than brute, while doing essentially zero allocation per query (the one alloc is the returned result slice). The map version pays 518 allocs/query chasing pointers and building temporary neighbour-key slices.

3. Build — 20 000 × 128-dim
index time alloc bytes allocs
map HNSW (ef=64) 6.63 s 3.73 GB 9.0 M
flat HNSW (efConstruction=200) 2.88 s 930 MB 20 441
btree HNSW (efConstruction=200 + durable persist) 3.08 s 2.15 GB 2.74 M

The flat index builds 2.3× faster than the map index and allocates 440× fewer times — despite using a heavier construction (efConstruction=200 vs 64). Cache locality and the absence of per-node maps more than pay for the larger candidate list.

Persisting to the btree adds only ~7 % wall-time over the pure in-memory build (writes are batched into one transaction via Flush). The extra allocations are serialization buffers + btree page writes.

4. Memory footprint — 20 000 × 128-dim (raw vectors = 9.8 MiB)
index resident × raw vectors
map HNSW 28.6 MiB 2.93×
flat HNSW 14.5 MiB 1.48×

The arena index is ~2× smaller. Both own a private copy of every vector, so the difference is pure structural overhead: maps + node structs + per-node slice headers vs. two flat arenas. FlatHNSW.MemBytes() (13.9 MiB, cap-based) corroborates the measured 14.5 MiB.

5. Recall (quality is not sacrificed)

Recall@10 vs exact brute force (random vectors):

index L2 Cosine
map HNSW (ef=64) 0.90 0.89
flat HNSW (ef=64, efC=200) 0.98 0.99
btree HNSW, after close + reload from disk 0.99 —

The btree variant returns byte-identical results before and after a reload (deterministic graph reconstruction), confirming the persistence format is lossless.

Takeaways / recommendation

  • Keep SIMD for distance (the dominant speedup, no-CGO). Update: this now uses the vendored internal/simd asm kernels (AVX2/AVX512 + NEON/SVE + fallback) instead of vek, so the SIMD win extends to arm64, not just amd64.
  • Land the arena/SoA layout, not the map port. ~10× faster search, ~2× faster build, ~2× less memory, ~zero query allocations, same recall.
  • Persist with the arena layout as the on-disk format. Durability via the btree costs only ~7 % build time and reloads losslessly. The natural next step for real integration is to drive BtreeHNSW from collection write transactions and expose it as a vector index type.

Known simplifications (this is a spike)

  • Neighbour pruning uses coder/hnsw's simple "drop the farthest" rule; it does not remove the reverse backlink on prune (slightly asymmetric graph, standard in lightweight HNSWs, negligible recall impact at these sizes).
  • FlatHNSW.Add is append-only (no per-key update/delete yet); deletes would need tombstones or a compaction pass.
  • BtreeHNSW serialises whole node records on change; a production version would split the rarely-changing vector blob from the frequently-changing adjacency list to cut write amplification.
  • Search over the working set is in-memory; for datasets that exceed RAM the vectors could stay in the btree and be paged in, trading latency for footprint (not explored here).

Documentation

Overview

Package vector is an experimental vector-search PROTOTYPE for any-store.

Deprecated: this package is NOT the live vector engine and is not imported by any-store itself (only by cmd/vectorbench). The production vector index is internal/vindex (a btree-resident HNSW). This package is retained only as a benchmarking/recall reference and may be removed.

It explores a few ways to land approximate nearest-neighbour (ANN) search on top of the embedded btree engine, using github.com/coder/hnsw as the algorithmic reference. Three index families are provided:

  • Brute: exact flat scan (ground truth / recall baseline).
  • HNSW: map-based in-memory graph, a faithful port of coder/hnsw.
  • FlatHNSW: an arena/SoA (struct-of-arrays) HNSW that keeps every vector in one contiguous []float32 slab and every adjacency list in flat []uint32 slices — no per-node maps, no per-vector allocations. This is the variant wired into the btree for persistence (see BtreeHNSW).

Distance is computed with SIMD (AVX2/AVX-512 via github.com/viterin/vek, pure-Go assembly, no CGO — the same library coder/hnsw uses) with scalar and hand-unrolled fallbacks kept around purely so the benchmarks can quantify the SIMD win.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func CosineDistanceSIMD 

func CosineDistanceSIMD(a, b []float32) float32

CosineDistanceSIMD mirrors coder/hnsw's CosineDistance: 1 - cosineSimilarity.

func CosineDistanceScalar 

func CosineDistanceScalar(a, b []float32) float32

CosineDistanceScalar is a naive cosine distance.

func DotDistanceSIMD 

func DotDistanceSIMD(a, b []float32) float32

DotDistanceSIMD returns the negated inner product (smaller = closer).

func DotDistanceScalar 

func DotDistanceScalar(a, b []float32) float32

DotDistanceScalar is a naive negated inner product.

func GenMDDataset 

func GenMDDataset(n, dim int, seed int64) (vecs [][]float32, ids []uint64, topics []int, avgBytes float64)

GenMDDataset builds n synthetic markdown documents, returning their embeddings, sequential doc ids, topic labels, and the average rendered markdown size in bytes.

func L2DistanceSIMD 

func L2DistanceSIMD(a, b []float32) float32

L2DistanceSIMD returns the Euclidean distance using vectorised kernels.

func L2DistanceScalar 

func L2DistanceScalar(a, b []float32) float32

L2DistanceScalar is a naive Euclidean distance.

func L2DistanceUnrolled 

func L2DistanceUnrolled(a, b []float32) float32

L2DistanceUnrolled is a 4-way unrolled Euclidean distance. The compiler can auto-vectorise the independent accumulators on some targets; this sits between the naive scalar and the explicit-SIMD kernels.

func PagedExists 

func PagedExists(db *btree.DB, name string) bool

PagedExists reports whether a persisted paged index named name is present.

func PersistPaged 

func PersistPaged(g *FlatHNSW, db *btree.DB, name string, metric Metric) error

PersistPaged writes g to db under name in the split on-disk form (:topo, :vec, :pmeta) in a single write transaction.

func SIMD 

func SIMD() bool

SIMD reports whether a hand-written SIMD kernel was selected for this CPU. When false, the simd package transparently uses a pure-Go fallback.

Types

type Brute 

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

Brute is an exact k-NN index: it keeps every vector in one contiguous slab and scans all of them per query. It is O(n·dim) per search but always returns the true nearest neighbours, so it doubles as the ground truth for measuring the recall of the approximate (HNSW) indexes.

The contiguous slab (vectors stored back-to-back in a single []float32) is the same arena layout used by FlatHNSW — it keeps distance kernels reading sequential memory and avoids one allocation per vector.

func NewBrute 

func NewBrute(dim int, m Metric) *Brute

NewBrute creates an exact index for dim-dimensional vectors under metric m.

func (*Brute) Add 

func (b *Brute) Add(key uint64, vec []float32)

Add appends a vector. It does not deduplicate keys (the brute index is a benchmark/ground-truth tool, not a primary store).

func (*Brute) Len 

func (b *Brute) Len() int

Len returns the number of indexed vectors.

func (*Brute) Search 

func (b *Brute) Search(query []float32, k int) []SearchResult

Search returns the k nearest neighbours to query, ordered closest-first.

type BtreeHNSW 

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

BtreeHNSW lands the arena HNSW on top of any-store's embedded btree engine. It keeps the working graph in memory as a FlatHNSW (so search runs at in-memory speed) while durably persisting every node — vector + per-layer adjacency — into two btree namespaces: 

<name>:meta   one record with the index parameters + entry point
<name>:nodes  one record per node, keyed by the dense id (8-byte big-endian)

Because ids are dense and big-endian-keyed, a forward cursor over the nodes namespace yields them in id order, which is exactly the order FlatHNSW needs to rebuild its arenas on reload (no re-construction, no re-randomised levels).

Writes are buffered: Add mutates the in-memory graph and records which nodes changed; Flush persists the dirty set + meta in a single write transaction. This batches the (relatively expensive) durable writes the same way a bulk import would.

BtreeHNSW is not safe for concurrent Add/Flush; serialise those externally. Concurrent Search is safe (it only reads the in-memory FlatHNSW).

func OpenBtreeHNSW 

func OpenBtreeHNSW(db *btree.DB, name string, dim int, m Metric) (*BtreeHNSW, error)

OpenBtreeHNSW opens (or creates) a persistent index named name inside db. If the namespaces already hold an index its parameters and dim are taken from the stored meta and the dim/metric arguments are only used when creating a fresh index.

func (*BtreeHNSW) Add 

func (b *BtreeHNSW) Add(key uint64, vec []float32)

Add inserts a vector into the in-memory graph and records the touched nodes for the next Flush. It does not write to disk.

func (*BtreeHNSW) Delete 

func (b *BtreeHNSW) Delete(key uint64) bool

Delete tombstones key. Persistence is a single tiny record on the next Flush — the node's own record is retained because it still routes searches.

func (*BtreeHNSW) Flush 

func (b *BtreeHNSW) Flush() error

Flush durably writes all nodes and tombstones touched since the last Flush, plus the index meta, in a single btree write transaction.

func (*BtreeHNSW) Len 

func (b *BtreeHNSW) Len() int

Len returns the number of indexed vectors.

func (*BtreeHNSW) Search 

func (b *BtreeHNSW) Search(query []float32, k int) []SearchResult

Search runs an in-memory ANN search over the working graph.

func (*BtreeHNSW) SetEf 

func (b *BtreeHNSW) SetEf(ef int)

SetEf adjusts the query-time candidate list size.

func (*BtreeHNSW) Stats 

func (b *BtreeHNSW) Stats() WriteStats

Stats returns accumulated write-amplification telemetry.

func (*BtreeHNSW) Update 

func (b *BtreeHNSW) Update(key uint64, vec []float32) bool

Update changes key's vector (delete-old + reinsert-new). On Flush this costs one tombstone plus the new node and its touched neighbours.

type DistanceFunc 

type DistanceFunc func(a, b []float32) float32

DistanceFunc returns the distance between two equal-length vectors. Smaller means closer for every metric exposed here.

type DocFlatHNSW 

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

DocFlatHNSW shows how a real any-store vector index composes the two pieces: an IDDict that turns document ids ([]byte) into dense uint32 labels, and a FlatHNSW arena graph keyed by those labels. It is the shape the collection layer would drive from its write transactions.

Labels are stable for the life of a document id (they survive graph Compact, because Compact only reshuffles the graph's *internal* arena ids, never the labels it is keyed by). That stability is what lets the on-disk node records key by label without rewriting them on every compaction.

func NewDocFlatHNSW 

func NewDocFlatHNSW(dim int, m Metric, seed int64, capHint int) *DocFlatHNSW

NewDocFlatHNSW creates an empty document-keyed index.

func (*DocFlatHNSW) Add 

func (x *DocFlatHNSW) Add(docID []byte, vec []float32)

Add inserts a vector for docID. Re-adding an existing id is a no-op (use Update to change its vector).

func (*DocFlatHNSW) Compact 

func (x *DocFlatHNSW) Compact()

Compact reclaims the graph's tombstoned arena space. Dictionary tombstones (just the orphaned id bytes) are left in place — they are tiny next to the vector/adjacency arenas — and labels stay stable across the call.

func (*DocFlatHNSW) Delete 

func (x *DocFlatHNSW) Delete(docID []byte) bool

Delete tombstones docID in both the dictionary and the graph.

func (*DocFlatHNSW) DictMemBytes 

func (x *DocFlatHNSW) DictMemBytes() int

DictMemBytes isolates the id-dictionary footprint (for the RAM breakdown).

func (*DocFlatHNSW) Len 

func (x *DocFlatHNSW) Len() int

Len returns the number of live documents.

func (*DocFlatHNSW) MemBytes 

func (x *DocFlatHNSW) MemBytes() int

MemBytes returns the combined footprint of the graph arenas and the id dictionary.

func (*DocFlatHNSW) Search 

func (x *DocFlatHNSW) Search(query []float32, k int) []DocResult

Search returns the k nearest document ids to query.

func (*DocFlatHNSW) Update 

func (x *DocFlatHNSW) Update(docID []byte, vec []float32) bool

Update changes docID's vector (delete-old + reinsert-new in the graph; the label, and therefore the document's identity, is unchanged).

type DocResult 

type DocResult struct {
	ID       []byte
	Distance float32
}

DocResult is a search hit carrying the document id bytes (as any-store keys documents) instead of an internal label.

type FlatHNSW 

type FlatHNSW struct {
	M              int     // max neighbours per node on layers >= 1
	M0             int     // max neighbours per node on layer 0 (commonly 2*M)
	Ml             float64 // level generation factor
	EfSearch       int     // candidate-list size at query time
	EfConstruction int     // candidate-list size at insert time
	// contains filtered or unexported fields
}

FlatHNSW is a struct-of-arrays / arena implementation of HNSW. Compared to the map-based HNSW it differs in three memory-conscious ways:

  1. Vectors live in one contiguous []float32 slab (vectors), indexed by a dense uint32 id. No per-vector slice header, no N pointers for the GC to scan, sequential reads for the SIMD distance kernels.

  2. Adjacency lists live in one flat []uint32 arena (links) plus a flat []int32 count arena. Each node's links are appended once at insert time (ids are dense and monotonic, so the arena grows append-only — exactly the access pattern an arena is good at). No map[K]*node per node.

  3. The per-query visited set and the two search heaps are pooled and reused (see flatScratch / visitedList), so a steady-state search allocates nothing.

The same arena layout is what BtreeHNSW serialises to / from disk.

func NewFlatHNSW 

func NewFlatHNSW(dim int, m Metric, seed int64) *FlatHNSW

NewFlatHNSW creates an empty arena-backed HNSW. seed makes level generation deterministic; pass 0 for a fixed default.

func (*FlatHNSW) Add 

func (h *FlatHNSW) Add(key uint64, vec []float32)

Add inserts a vector. If the key already exists the call is ignored; use Update to change an existing key's vector.

func (*FlatHNSW) Compact 

func (h *FlatHNSW) Compact()

Compact rebuilds the arenas keeping only live nodes, assigning fresh dense ids and remapping every neighbour id. Edges that pointed at tombstoned nodes are dropped (leaving slightly thinner neighbourhoods — cheap, and usually a negligible recall hit until the deleted fraction is large). This reclaims all tombstone memory and removes tombstones from query navigation, restoring search speed. O(physical_nodes + total_links). Does NOT re-run construction; use Rebuild for that.

func (*FlatHNSW) Delete 

func (h *FlatHNSW) Delete(key uint64) bool

Delete tombstones the vector for key. It returns false if the key is absent or already deleted. O(1); reclaim the space later with Compact.

func (*FlatHNSW) DeleteHardRepair 

func (h *FlatHNSW) DeleteHardRepair(key uint64, replenish bool) bool

DeleteHardRepair is the locked wrapper around deleteHardRepairLocked.

func (*FlatHNSW) DeletedFraction 

func (h *FlatHNSW) DeletedFraction() float64

DeletedFraction returns tombstones / physical size — the signal for when to Compact. Production systems compact somewhere around 0.1–0.2.

func (*FlatHNSW) Len 

func (h *FlatHNSW) Len() int

Len returns the number of live (non-deleted) vectors.

func (*FlatHNSW) MemBytes 

func (h *FlatHNSW) MemBytes() int

MemBytes returns an approximate resident size of the index's backing arenas (vectors + adjacency + bookkeeping), excluding the keyToID map.

func (*FlatHNSW) PhysicalLen 

func (h *FlatHNSW) PhysicalLen() int

PhysicalLen returns the number of slots in the arenas, including tombstones. PhysicalLen-Len is the reclaimable space waiting for Compact.

func (*FlatHNSW) Rebuild 

func (h *FlatHNSW) Rebuild()

Rebuild reconstructs the graph from scratch by re-inserting every live vector. Highest quality (full HNSW construction) and most expensive; use when many updates/deletes have degraded the graph beyond what Compact restores.

func (*FlatHNSW) Search 

func (h *FlatHNSW) Search(query []float32, k int) []SearchResult

Search returns the k nearest neighbours, closest-first.

func (*FlatHNSW) Update 

func (h *FlatHNSW) Update(key uint64, vec []float32) bool

Update changes the vector stored for key. It is implemented as tombstone-old + insert-new: the old node keeps acting as a waypoint until Compact reclaims it, while the new node is linked into the graph at a fresh id using the new vector. This is the standard HNSW update because an in-place vector swap would leave both the node's own edges and every incoming edge computed against the stale vector (see UpdateInPlace for that variant and its caveats). Returns false if key does not exist.

func (*FlatHNSW) UpdateInPlace 

func (h *FlatHNSW) UpdateInPlace(key uint64, vec []float32) bool

UpdateInPlace overwrites a node's vector without changing its id or re-running construction. It is cheap (no new node, no re-link of the whole graph) but lower quality: the node's outgoing edges and every incoming edge were chosen for the OLD vector and are not recomputed, so the node can end up poorly placed. Offered for benchmarking against Update; not recommended when the vector moves significantly. Returns false if key is absent or deleted.

type HNSW 

type HNSW struct {
	// M is the maximum number of neighbours kept per node per layer.
	M int
	// Ml is the level-generation factor (layer i is ~Ml× the size of i-1).
	Ml float64
	// EfSearch is the size of the dynamic candidate list during search.
	EfSearch int
	// contains filtered or unexported fields
}

HNSW is a map-based, fully in-memory Hierarchical Navigable Small World graph. It is a close adaptation of github.com/coder/hnsw with the generic key fixed to uint64 and the distance function pluggable. Adjacency is stored as a map[uint64]*hnswNode per node, which makes deletes cheap but costs an allocation per node and chases pointers during search.

This is the "pure in-memory, idiomatic Go" baseline that FlatHNSW is measured against.

func NewHNSW 

func NewHNSW(dim int, m Metric, seed int64) *HNSW

NewHNSW builds an empty graph. seed makes level generation deterministic for reproducible benchmarks; pass 0 for a fixed default seed.

func (*HNSW) Add 

func (h *HNSW) Add(key uint64, vec []float32)

Add inserts (or replaces) a vector.

func (*HNSW) Len 

func (h *HNSW) Len() int

Len returns the number of vectors in the base layer.

func (*HNSW) Search 

func (h *HNSW) Search(query []float32, k int) []SearchResult

Search returns the k nearest neighbours, closest-first.

type IDDict 

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

idmap.go answers the "how do we link graph nodes to real any-store documents" question.

any-store keys every document by the marshaled bytes of its `id` field (`idVal.MarshalTo`) — an arbitrary, variable-length []byte (a string, int, objectid, …). There is no numeric rowid. An HNSW arena, on the other hand, wants a dense, fixed-width uint32 to index its vector/adjacency slabs.

IDDict bridges the two with **dictionary encoding**: each distinct document id is assigned a dense uint32 *label* (a monotonic counter). The label is what the graph stores; the document id is recovered from the label only when results are returned.

Two ways to keep the label -> id-bytes reverse mapping: 

[][]byte            one slice header (24 B on 64-bit) + one backing array
                    PER id  ->  24 B/id of pure overhead, N heap objects for
                    the GC to scan, ids scattered across the heap.

flat arena (this)   all id bytes concatenated in one []byte, plus one
                    []uint32 of end-offsets  ->  4 B/id of overhead, exactly
                    two heap objects total, ids contiguous.

The arena form is the one any-store should use; the benchmark (BenchmarkIDMapMem) quantifies the gap.

func NewIDDict 

func NewIDDict(capHint int) *IDDict

NewIDDict returns an empty dictionary. capHint pre-sizes the arenas.

func (*IDDict) Delete 

func (d *IDDict) Delete(id []byte) (label uint32, ok bool)

Delete tombstones the label for id (the arena bytes stay until Compact). The forward entry is removed so the id can be re-Interned to a fresh label.

func (*IDDict) ID 

func (d *IDDict) ID(label uint32) []byte

ID returns the document-id bytes for a label. The returned slice aliases the arena; copy it if you need to retain it past the next mutation.

func (*IDDict) Intern 

func (d *IDDict) Intern(id []byte) (label uint32, isNew bool)

Intern returns the label for id, assigning a fresh one if unseen. isNew reports whether a new label was allocated. The id bytes are copied into the arena, so the caller may reuse its buffer.

func (*IDDict) Label 

func (d *IDDict) Label(id []byte) (uint32, bool)

Label returns the label for id if present and live.

func (*IDDict) Len 

func (d *IDDict) Len() int

Len returns the number of live ids.

func (*IDDict) MemBytes 

func (d *IDDict) MemBytes() int

MemBytes approximates the dictionary's resident size. The forward map is estimated (Go does not expose its true footprint); the arenas are exact.

type Metric 

type Metric uint8

Metric selects how the distance between two vectors is measured. 

const (
	// L2 is the (squared-free) Euclidean distance. Smaller is closer.
	L2 Metric = iota
	// Cosine is 1 - cosine-similarity. Smaller is closer. Inputs need not be
	// normalised; the metric normalises internally.
	Cosine
	// Dot is the negated inner product (so that "smaller is closer" holds for
	// all metrics). Use with pre-normalised vectors for cosine-equivalent
	// ranking at lower cost.
	Dot
)

func (Metric) DistanceFor 

func (m Metric) DistanceFor() DistanceFunc

DistanceFor returns the best available distance function for the metric on this CPU. The simd package selects a SIMD or pure-Go kernel internally (the pure-Go L2 is the hand-unrolled loop that beats vek's old fallback on no-AVX2 x86), so there is nothing CPU-specific to branch on here.

func (Metric) String 

func (m Metric) String() string

type PagedHNSW 

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

PagedHNSW is a prototype of "Option B" from COMPARISON_pgvector.md: instead of holding every vector in a contiguous RAM arena, it keeps only the graph *topology* (adjacency + levels + entry point) resident and reads each node's vector from the btree on demand during traversal — paging it through the same page cache (pcache) the btree already maintains. This is the DiskANN-lite / pgvector residency model: RAM scales with the graph, not the vectors.

Memory math (per node): the topology is ~M0*4 = 128 B; a vector is dim*4 B (512 B at dim=128, 6 KB at dim=1536). So paging the vectors keeps ~80% (dim 128) to ~98% (dim 1536) of the data on disk while the navigable graph stays in RAM. The cost is one btree point-lookup per visited node instead of one array index — that overhead is exactly what TestPagedVsMemory measures.

This prototype borrows an existing FlatHNSW purely for its in-RAM topology (neighbors/level/entry/deleted); the vectors it reads come from the btree, not from the FlatHNSW slab. Search is single-threaded (one reusable scratch).

func AttachPaged 

func AttachPaged(g *FlatHNSW, db *btree.DB, name string, metric Metric) (*PagedHNSW, error)

AttachPaged wraps an in-RAM FlatHNSW with an existing on-disk :vec namespace (already populated, e.g. by PersistPaged) without writing anything. The returned index can do pure paged Search AND the route-in-RAM SearchHybrid, because its topology source g still holds the full vectors in RAM.

func BuildPagedFromFlat 

func BuildPagedFromFlat(g *FlatHNSW, db *btree.DB, name string, metric Metric) (*PagedHNSW, error)

BuildPagedFromFlat persists g's vectors into a <name>:vec btree namespace and returns a PagedHNSW that traverses g's topology while reading vectors from the btree. g's own vector slab can be released afterwards (the paged index does not use it).

func OpenPaged 

func OpenPaged(db *btree.DB, name string) (*PagedHNSW, error)

OpenPaged reopens a persisted paged index, loading only its topology into RAM.

func (*PagedHNSW) Gets 

func (p *PagedHNSW) Gets() int

Gets returns the cumulative number of btree vector lookups (telemetry).

func (*PagedHNSW) PhysLen 

func (p *PagedHNSW) PhysLen() int

PhysLen returns the number of nodes (live + tombstoned) in the loaded graph.

func (*PagedHNSW) Search 

func (p *PagedHNSW) Search(query []float32, k int) ([]SearchResult, error)

Search runs the HNSW query reading vectors from the btree. It opens one read transaction for the query (the realistic unit) so the traversal sees a consistent snapshot and benefits from the reader's page cache.

func (*PagedHNSW) SearchHybrid 

func (p *PagedHNSW) SearchHybrid(query []float32, k int) ([]SearchResult, error)

SearchHybrid models the production answer (DiskANN / pgvector-with-rescore): ROUTE the graph using an in-RAM vector copy (here g's slab; in a real build a quantized int8/binary slab a quarter/thirtieth the size), then page only the final ef candidates' full vectors from the btree to RERANK. This collapses the ~1900 btree reads/query of pure paging down to ef reads/query, so latency returns to near in-memory while RAM stays at (routing-slab + topology).

Because the prototype reuses the same float32 vectors for routing and rerank, the *results* are identical to Search; what it isolates is the latency/Get profile of the hybrid (in-RAM routing + ef paged rerank reads).

func (*PagedHNSW) TopologyBytes 

func (p *PagedHNSW) TopologyBytes() int

TopologyBytes approximates the resident RAM of the paged index: the graph arenas WITHOUT the vector slab (the whole point — vectors live on disk).

type SearchResult 

type SearchResult struct {
	Key      uint64
	Distance float32
}

SearchResult is one hit returned by a search: the caller's key and its distance to the query (smaller = closer).

type WriteStats 

type WriteStats struct {
	Flushes        int
	RecordsWritten int // total btree Put calls (nodes + tombstones + meta)
	NodeRecords    int // node Puts only
	Tombstones     int // tombstone Puts
	BytesWritten   int // total payload bytes
	VectorBytes    int // of node payloads, the vector portion
	AdjacencyBytes int // of node payloads, the adjacency portion
}

WriteStats accumulates write-amplification telemetry. RecordsWritten counts btree Put calls; the byte counters split node-record payload into the (large, rarely-changing) vector part and the (small, churning) adjacency part — the split that motivates storing them in separate namespaces.

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.