Documentation
¶
Overview ¶
Package vector implements stroma's pure-Go vector backend.
The canonical implementation of the dot product is the scalar left-to-right reduction in this file. Any alternate implementation that becomes the default path MUST produce results byte-identical to this one on the project's golden test corpus. Approximate acceleration paths must be explicit opt-ins. See docs/vector-backend-v4-spec.txt.
Index ¶
- Constants
- Variables
- func NormalizeF32(v []float32)
- type Hit
- type Matrix
- func (m *Matrix) ChunkID(i int) int64
- func (m *Matrix) RowOf(chunkID int64) (int, bool)
- func (m *Matrix) Rows() int
- func (m *Matrix) Search(ctx context.Context, query []float32, opts SearchOptions) ([]Hit, error)
- func (m *Matrix) SearchParallel(ctx context.Context, query []float32, opts SearchOptions, workers int) ([]Hit, error)
- func (m *Matrix) SearchParallelWithPool(ctx context.Context, query []float32, opts SearchOptions, pool *WorkerPool) ([]Hit, error)
- type MatrixLoadOptions
- type RowBitset
- type SearchMode
- type SearchOptions
- type TieKey
- type WorkerPool
Constants ¶
const BinaryFanoutThreshold = 8192
BinaryFanoutThreshold is the ModeBinary equivalent. The Hamming scoring kernel is roughly an order of magnitude cheaper per row than the float32 dot-product, so the break-even where parallelism beats the goroutine-startup + heap-merge fixed cost shifts up. Empirically (M3 Ultra, dim=768, 8 workers) parallel Hamming regresses serial at ~5k rows by ~25% but wins at ~57k rows by ~17%; setting the threshold at 8192 keeps SciFact-class corpora on the serial path while still engaging fan-out at FiQA-class scale and above.
const FanoutThreshold = 4096
FanoutThreshold is the minimum candidate count below which SearchParallel falls through to the single-threaded Search for ModeFloat32 / ModeInt8. Below this the goroutine startup cost and per-worker heap allocation dominate the scoring loop. The spec fixes this at 4096 based on initial scalar benchmarks; tune together with the SearchParallel benchmark when scoring kernels change.
Variables ¶
var ErrWorkerPoolClosed = errors.New("vector: worker pool closed")
ErrWorkerPoolClosed is returned by SearchParallelWithPool when the supplied pool was already closed before or during job submission. Callers normally see this only when Snapshot.Close races a concurrent SearchVector call — a misuse that the database/sql concurrency contract also leaves undefined; the error is provided so the runaway is reported, not deadlocked.
Functions ¶
func NormalizeF32 ¶
func NormalizeF32(v []float32)
NormalizeF32 is the exported entry point for in-place L2 normalization. It exists so the snapshot dispatcher in package index can normalize the query at the search entry point without reaching into unexported helpers; the body delegates to the canonical normalizeF32.
Types ¶
type Hit ¶
Hit is a single scored result returned by Matrix.Search. Ref and ChunkIndex are copied from the matrix's row-aligned tieKeys at the time the heap is materialized, so callers see stable identity even if the matrix is later replaced.
type Matrix ¶
type Matrix struct {
Dim int
Data []float32
Int8 []int8
Bits []byte
// contains filtered or unexported fields
}
Matrix is the in-memory full-precision corpus the Go-native backend scores against. Rows are stored row-major in Data with stride Dim; row i is Data[i*Dim:(i+1)*Dim]. chunkIDs and tieKeys are row-aligned (len == rows). chunkRows maps chunk_id to row index for filter pushdown lookups; it is built once at load time and never mutated by search.
Int8 and Bits are populated only when the corresponding runtime search mode is enabled. They share the same row alignment as Data (Int8 stride is Dim; Bits stride is Dim/8 — Dim must be a multiple of 8 for ModeBinary).
func NewMatrixFromSnapshot ¶
NewMatrixFromSnapshot loads the full corpus from a v4 snapshot DB into an in-memory Matrix sized for dim and the given runtime search mode. It is exactly NewMatrixFromSnapshotWithOptions(ctx, db, dim, quant, MatrixLoadOptions{}); see that function for the full contract.
func NewMatrixFromSnapshotWithOptions ¶
func NewMatrixFromSnapshotWithOptions(ctx context.Context, db *sql.DB, dim int, quant string, opts MatrixLoadOptions) (*Matrix, error)
NewMatrixFromSnapshotWithOptions loads the full corpus from a v4 snapshot DB into an in-memory Matrix.
v4 storage keeps full-precision float32 bytes in chunk_vectors for every runtime mode:
- float32: raw rows are normalized into m.Data. When opts.BinaryPrefilter is true and dim%8 == 0 each row is also sign-packed into m.Bits so the snapshot dispatcher can route ModeFloat32 searches through searchBinary's Hamming prefilter + full-precision cosine rescore. Default (opts zero value) leaves m.Bits nil, preserving the exact-cosine semantics float32 snapshots have always had.
- int8: raw rows are normalized and quantized with the same f64 normalize/round path used for queries, then dequantized into m.Data, with raw int8 bytes retained in m.Int8.
- binary: raw rows are normalized into m.Data and sign-packed into m.Bits for the hamming prefilter. BinaryPrefilter is ignored — binary quantization always populates m.Bits by definition.
The query pins ORDER BY v.chunk_id so the row indices are stable across runs; tieKeys (ref, chunk_index) are populated from the JOIN before any top-K limiting can happen, which is the load-bearing invariant for the integration tie-break order.
func (*Matrix) ChunkID ¶
ChunkID returns the chunk_id stored at row i. It panics if i is out of range; callers in this package never produce out-of-range row indices.
func (*Matrix) RowOf ¶
RowOf returns the row index for chunk_id and whether it exists in this matrix. Used by filter pushdown to translate a SQL-resolved candidate set into row indices.
func (*Matrix) Search ¶
Search returns the top opts.Limit hits scored against the matrix.
Validation contract: this layer assumes its caller (the snapshot dispatcher) has already enforced public-API invariants:
- query is L2-normalized at length m.Dim
- SearchDimension is zero or in (0, m.Dim) and only set in ModeFloat32
- opts.Mode matches the runtime representation populated on m (ModeInt8 needs m.Int8 for parity probes but is not strictly required for scoring; ModeBinary needs m.Bits)
Anything that violates the contract returns (nil, nil) rather than partial results, mirroring "no matches" — surfacing detailed errors is the dispatcher's responsibility. ctx errors are propagated so a caller's deadline interrupts the O(N) scan instead of letting it burn CPU and memory until natural completion.
Results are returned in the integration tie-break order: distance ASC, ref ASC, chunk_index ASC. Ties at the candidate cutoff are resolved by the row-aligned tieKeys held in m, so they cannot be silently dropped before hydration.
func (*Matrix) SearchParallel ¶
func (m *Matrix) SearchParallel(ctx context.Context, query []float32, opts SearchOptions, workers int) ([]Hit, error)
SearchParallel runs Matrix scoring across `workers` goroutines and merges the per-worker top-K heaps into one global top-K heap.
Algorithm (spec STAGE_5_SPEC):
- Partition the candidate row enumeration into N contiguous chunks (N = workers). Each worker scores rows from its chunk only.
- Each worker fills its own bounded topKHeap of size opts.Limit using the same scoring kernel as serial Search.
- Final merge: drain each per-worker heap, feed all kept entries into one final topKHeap of size opts.Limit. Result is the global top-K under the integration tie-break order (distance ASC, ref ASC, chunk_index ASC).
Determinism: each per-worker heap is bounded by entryLess, and the final merge re-applies entryLess to the union of survivors, so the returned ordering is independent of worker completion order.
Worker count semantics:
- workers <= 0 selects runtime.GOMAXPROCS(0). The snapshot dispatcher resolves this earlier and passes a concrete count; callers driving Matrix directly inherit the same default.
- workers == 1 short-circuits to serial Search
- workers > candidate count is clamped to the candidate count
Mode dispatch: the dotF32 path (ModeFloat32 without SearchDimension, and ModeInt8 — which is also a dotF32 score against m.Data after the dispatcher pre-quantizes the query) is fan-out parallelized via parallelDotTopK. ModeBinary parallelizes its Hamming prefilter via parallelBinarySearch; the cosine rescore over limit*BinaryRescore survivors stays serial because its budget is too small to amortize fan-out overhead. ModeFloat32 with SearchDimension > 0 (Matryoshka) keeps the serial pipeline because its prefilter renormalizes a shared scratch buffer per row. SearchParallel always returns the same hits Search would have returned for any mode.
func (*Matrix) SearchParallelWithPool ¶
func (m *Matrix) SearchParallelWithPool(ctx context.Context, query []float32, opts SearchOptions, pool *WorkerPool) ([]Hit, error)
SearchParallelWithPool is the shared-budget variant of SearchParallel: scoring partitions are submitted to the supplied WorkerPool rather than running in goroutines spawned per call. Concurrent SearchParallelWithPool calls against the same pool share its budget — total active scoring goroutines across all in-flight searches is bounded at pool.Workers().
The Snapshot dispatcher uses this method when the snapshot has a pool (the production default). Direct Matrix users that don't need the budget bound continue to call SearchParallel.
Behavior matches SearchParallel for thresholds, mode dispatch, determinism, and ctx cancellation. The only difference is the goroutine source.
pool == nil is tolerated as a defensive fallback: pool.Workers() returns 0, the workers count clamps to 1, and the call falls through to serial Search via the workers <= 1 short-circuit below. Callers that intend per-call goroutine fan-out without a pool should use SearchParallel instead. The Snapshot dispatcher only ever calls this method through ensureSearchPool, which guarantees a non-nil pool when fan-out is eligible.
type MatrixLoadOptions ¶
type MatrixLoadOptions struct {
// BinaryPrefilter, when true, sign-packs each float32 row into
// m.Bits during loadFloat32Matrix (when dim%8 == 0). Loaders for
// int8/binary quantization ignore this field — int8 has its own
// m.Int8 representation and binary always sign-packs.
//
// The downstream search dispatcher decides whether to USE the bits;
// this option only controls whether they are PRESENT. Memory cost
// is dim/8 bytes per row (~5.5 MiB on a 57 600-row corpus at
// dim=768) when enabled.
BinaryPrefilter bool
}
MatrixLoadOptions tunes the matrix loader without changing its signature for the common case. Unknown fields default to the zero value; NewMatrixFromSnapshot is exactly NewMatrixFromSnapshotWithOptions with all zeros.
type RowBitset ¶
type RowBitset struct {
// contains filtered or unexported fields
}
RowBitset is a compact bitset over matrix row indices. It lets the snapshot dispatcher communicate filter-pushdown candidate sets to Matrix.Search without materializing an O(filter_match_count) slice.
Memory is bounded at len(matrix.Rows())/8 bytes regardless of how many rows match the filter — for a 100k-row matrix that's ~12.5 KB, versus 800 KB for a slice of int64 chunk_ids when every row matches. This bounds per-query allocations under broad filters on large corpora (the post-review medium finding from the Stage 1 codex adversarial review).
func NewRowBitset ¶
NewRowBitset returns an empty bitset sized for n rows.
func (*RowBitset) Each ¶
Each invokes fn for each set row index in ascending order. Implemented via TrailingZeros64 word-walking so iteration is O(set_bits) rather than O(matrix_rows).
func (*RowBitset) EachUntil ¶
EachUntil is the early-stop variant of Each: iteration stops as soon as fn returns false. This lets callers (notably the scoring loops in search.go) abort on context cancellation without first materializing the row index slice.
func (*RowBitset) Len ¶
Len returns the number of rows the bitset addresses (the matrix row count it was built for, not the popcount).
type SearchMode ¶
type SearchMode int
SearchMode selects which stored representation the matrix is scored against. Float32 is the canonical reference; Int8 and Binary preserve the existing public quantization modes as runtime search modes.
const ( // ModeFloat32 scores the query against L2-normalized full-precision // rows in m.Data. This is the baseline mode and the only mode that // supports SearchDimension (Matryoshka prefiltering). ModeFloat32 SearchMode = iota // ModeInt8 scores against runtime-quantized int8 rows in m.Int8, // dequantized as float32(int8)/127 to preserve the int8 contract // while accumulating in float32. Stored bytes remain full precision // in v4 storage. ModeInt8 // ModeBinary uses sign-packed bits in m.Bits for a Hamming // prefilter then rescores survivors against full-precision rows in // m.Data with cosine. The binaryRescoreMultiplier slack is applied // before rescore. ModeBinary )
func SearchModeForQuantization ¶
func SearchModeForQuantization(quant string) (SearchMode, bool)
SearchModeForQuantization maps the store-package quantization name (the same string carried on Snapshot.quantization) to the matching SearchMode. This is the bridge the snapshot dispatcher uses; it is exported so the index package does not need to reproduce the mapping in two places.
type SearchOptions ¶
type SearchOptions struct {
// Limit is the number of hits to return.
Limit int
// Candidates restricts scoring to rows whose chunk_id is in this
// slice. nil means "see CandidateBitset; if both nil, scan all
// rows". The matrix resolves chunk_ids to row indices via its
// internal chunkRows map. Use Candidates for narrow filters
// where the match count is small; use CandidateBitset for broad
// filters where the match count approaches the matrix size.
Candidates []int64
// CandidateBitset is the row-level bitset alternative to
// Candidates. When non-nil it takes precedence over Candidates
// and bounds per-query memory at matrix.Rows()/8 bytes regardless
// of how many rows the filter matches. The snapshot dispatcher
// builds a bitset directly from the SQL filter pre-fetch so a
// broad filter on a large snapshot never materializes an
// O(filter_match_count) chunk_id slice.
CandidateBitset *RowBitset
// SearchDimension is the Matryoshka prefix length for ModeFloat32.
// 0 means "use Dim" (no prefix prefiltering). Non-zero values are
// rejected for ModeInt8 and ModeBinary; this matches the v3 public
// behavior (search_matryoshka_test.go).
SearchDimension int
// Mode selects the stored representation to score against.
Mode SearchMode
// MatryoshkaPrefilter scales the candidate pool size for the
// Matryoshka prefix prefilter before the full-dim rescore. Values
// <= 1 mean "no slack" (prefilter pool == Limit). The wired-up
// dispatcher passes index.matryoshkaPrefilterMultiplier (3 in v3)
// to match the v3 public behavior.
MatryoshkaPrefilter int
// BinaryRescore scales the candidate pool size for the Hamming
// prefilter before the full-precision cosine rescore. Values <= 1
// mean "no slack". The wired-up dispatcher passes
// index.binaryRescoreMultiplier (3 in v3).
BinaryRescore int
}
SearchOptions controls a single Matrix.Search invocation.
type TieKey ¶
TieKey carries the row-aligned ordering metadata that the bounded top-K heap uses to break ties on distance. Matrix holds a row-aligned []TieKey loaded with the matrix so that ties at the candidate cutoff cannot be silently dropped before hydration.
The integration tie-break order, fixed by the spec, is:
distance ASC, ref ASC, chunk_index ASC
type WorkerPool ¶
type WorkerPool struct {
// contains filtered or unexported fields
}
WorkerPool is the shared worker pool that backs the spec WORKER_POOL_LIFECYCLE: per-Snapshot, lazy-created on first parallel vector search after the matrix has loaded, released on Snapshot.Close. Concurrent SearchParallelWithPool calls on the same snapshot share the pool budget — the pool's worker count is the total scoring parallelism across all in-flight searches, not a per-search multiplier. This is the resource bound multi-tenant callers expect: SearchWorkers caps the snapshot's CPU footprint, it does not multiply per request.
Lifecycle:
- NewWorkerPool starts `workers` long-lived goroutines that pull jobs from a shared channel.
- Submit places one task on the channel; under contention the submitter blocks until a worker picks it up. There is no unbounded queue, so high QPS naturally throttles to pool throughput rather than expanding heap.
- Close is idempotent. It signals workers to exit and waits for them. Pending tasks return ErrWorkerPoolClosed via Submit.
A WorkerPool is safe for concurrent Submit calls but not for concurrent Close calls (Close is idempotent via sync.Once but callers should not race Close with Submit on the user-facing API — the Snapshot owns Close and runs it only after no more SearchVector calls can begin).
func NewWorkerPool ¶
func NewWorkerPool(workers int) *WorkerPool
NewWorkerPool starts a pool with `workers` long-lived goroutines. workers <= 0 selects 1 (degenerate but safe). Callers normally derive the count from runtime.GOMAXPROCS(0) — see index.resolveSearchWorkers for the canonical resolution.
func (*WorkerPool) Close ¶
func (p *WorkerPool) Close()
Close signals all worker goroutines to exit and waits for them. Idempotent: a subsequent Close is a no-op. After Close, submit returns ErrWorkerPoolClosed, and any in-flight SearchParallelWithPool calls surface the same error for the partitions whose jobs the workers had not yet claimed.
Workers running a job at Close time finish that job (this is usually a partition scoring loop that itself observes ctx cancellation), then exit. Close therefore returns only after all in-flight scoring is quiescent.
func (*WorkerPool) Workers ¶
func (p *WorkerPool) Workers() int
Workers returns the parallelism degree the pool was constructed with. Used by SearchParallelWithPool to decide partition count.
Source Files