# gizdb:core/vector Nearest-neighbour search over a vector column: a HNSW graph per segment (Malkov and Yashunin; the layout of hnswlib and USearch: a flat neighbour array for layer 0, the few upper-layer nodes in their own arrays), and an exact scan where it is cheaper or the filter is selective. A filter is a set of allowed rows; the graph is walked through every row but only allowed ones are returned, and when the allowed rows are few the exact scan answers instead, so recall does not collapse under a 1% filter. One walk (walk) serves a graph in memory and a graph whose level 0 links and values stay in its segment file (Graph.onDisk): it estimates distances on the codes of the index's quantizer (Spec: RaBitQ, SQ8 or none), takes the nearest nodes not taken (one at a time in memory, a beam of reads on disk, as DiskANN), and offers each node it takes to the answer at its exact distance. So the answer is exact over the nodes taken, which hold the walk's final pool. Distances: l2 (squared Euclidean), cosine (1 - cosine similarity) and ip (negative inner product), so smaller is always nearer. Ties go to the lower row, as in BM25 top-k. ```gizlang import * as Vector from "gizdb:core/vector"; ``` ## Types ### `Spec` ```gizlang type Spec = { metric: i64; quant: i64; depth: i64; ef: i64; graph: i64; } ``` How an index builds and walks its graph: the metric, the codes (BITS, SQ8 or RAW), RaBitQ's bits a dimension (0: depthOf) and the build's search breadth. - `metric`: `i64` - `quant`: `i64` - `depth`: `i64` - `ef`: `i64` - `graph`: `i64` ### `Graph` ```gizlang type Graph = { dim: i64; metric: i64; rows: i64; entry: i64; top: i64; levels: Vec; base: Vec; baseCount: Vec; stride: i64; slots: Map; upper: Vec; upperCount: Vec; norms: Vec; quant: i64; lo: Vec; step: Vec; codes: bytes; coded: Vec; padded: i64; depth: i64; center: Vec; bits: bytes; linksAt: i64; } ``` An HNSW graph of vectors: its dimensions, metric, levels, links and codes. - `dim`: `i64` - `metric`: `i64` - `rows`: `i64` - `entry`: `i64` - `top`: `i64` - `levels`: `Vec` - `base`: `Vec` — The level 0 links, `stride` a node; empty when they stay in the segment file (linksAt). - `baseCount`: `Vec` - `stride`: `i64` — Room for links a node has in `base`: 2M in a finished graph; BUILD_ROOM while a build appends to full lists. - `slots`: `_gizlang_sdk_collections.Map` — (node * 64 + level) to its slot in `upper`, for levels above 0. - `upper`: `Vec` - `upperCount`: `Vec` - `norms`: `Vec` — Each row's norm (Graph.resident): cosine distances in memory read it. - `quant`: `i64` — The codes walks estimate on: BITS, SQ8 or RAW (Spec.quant). Graph.withCodes makes them from the values. - `lo`: `Vec` — SQ8 codes of the rows, one byte a dimension: a value is lo + step × code (Graph.encode). - `step`: `Vec` - `codes`: `bytes` - `coded`: `Vec` — Each row's sum of (step × code)² over its dimensions: an L2 walk takes a code distance as a dot product (distancesOf). - `padded`: `i64` — RaBitQ codes of the rows (Gao and Long, SIGMOD 2024, and its extension to more bits; Graph.withBits): after a rotation (rotateInto) of the values padded to `padded` dimensions, a row's residual r = x - center is coded in `depth` bits a dimension as x̄ (quantize), its direction to those bits. The estimate of r · y is scale × (x̄ · y), scale = |r|² / (x̄ · r). `add` is |r|² + 2 scale (x̄ · center) for l2 (the distance is add + |y - center|² - 2 scale (x̄ · y)), the row's norm for cosine (whose rows and query are coded as directions, norm 1, so the estimate is the cosine), and 0 for ip. A row of `bits` is its codes (padded × depth / 8 bytes), then its scale and add as f32: one fetch brings what its estimate reads (Graph.rowBytes). - `depth`: `i64` - `center`: `Vec` - `bits`: `bytes` - `linksAt`: `i64` — Where the level 0 links are in the segment file's block, from its start, when they stay there (base empty; ColdHome.diskGraph); -1 when they are in memory. ### `Marks` ```gizlang type Marks = { bits: Vec; set: Vec; count: i64; pool: Vec; taken: Vec; fresh: Vec; dist: Vec; } ``` What a walk reuses across searches: the visited rows (a bit a row, so the bits of a walk stay in the core's cache, and the rows set, so a new walk clears only their words), the pool, the nodes taken in a step, and the links and distances of the nodes they link to. - `bits`: `Vec` - `set`: `Vec` - `count`: `i64` - `pool`: `Vec` - `taken`: `Vec` - `fresh`: `Vec` - `dist`: `Vec` ### `Near` ```gizlang type Near = { row: i64; distance: f64; } ``` One answer: a row and its distance. - `row`: `i64` - `distance`: `f64` ### `Fetched` ```gizlang type Fetched = { links: Vec; values: Vec; } ``` What a walk on disk read for the rows it asked for, in their order: each row's 2M level 0 links (Graph.baseCount of them used; none when the links were not asked for) and its values. - `links`: `Vec` - `values`: `Vec` ### `Found` ```gizlang type Found = { near: Vec; values: Vec; reads: i64; } ``` What a search found: the k nearest, nearest first, their values (dim a row, in the same order; none in memory), and the rows it read from the segment file. - `near`: `Vec` - `values`: `Vec` - `reads`: `i64` ## Functions ### `specOf` ```gizlang function specOf(options: string): Spec ``` The Spec of a vector index's options (Schema.indexOptions): the metric of its operator class (l2, cosine, ip), then its storage parameters, "{name=value,...}" (relOptions): quantizer (rabitq, the default; sq8; none), bits (4 or 8, rabitq's), ef_construction, and graph (auto, the default, memory or disk; Spec.linksInMemory: a cold segment keeps the graph's links in memory and reads only the vectors it ranks; disk: it reads the links of each beam from the file too). Effects: fail. ### `emptyGraph` ```gizlang function emptyGraph(): Graph ``` A graph with no rows. Effects: fail. ### `distancesTo` ```gizlang function distancesTo(metric: i64, values: Vec, nulls: bytes, dim: i64, q: Vec): Vec ``` The distance of every row of a column (`dim` values each) to `q`; null rows give 0. Effects: fail. ### `distance` ```gizlang function distance(metric: i64, a: Vec, b: Vec): f64 ``` The distance between two whole vectors (SQL's distance functions). Effects: fail. ### `vectorNorm` ```gizlang function vectorNorm(q: Vec): f64 ``` The Euclidean norm of q. Effects: fail. ### `rowDistance` ```gizlang function rowDistance(metric: i64, values: Vec, row: i64, q: Vec, qn: f64): f64 ``` distance(metric, row `row` of values, q) with q's norm `qn` given: the same arithmetic, without a copy of the row. Effects: fail. ### `marks` ```gizlang function marks(): Marks ``` An empty set of marks, for a walk to record the nodes that it visited. Effects: fail. ### `buildGraph` ```gizlang function buildGraph(values: Vec, nulls: bytes, dim: i64, spec: Spec): Graph ``` A graph over the non-null rows of a flat vector column. Nodes join in batches (prefix doubling, as ParlayANN builds): each node of a batch searches the graph as it was before the batch and picks its links on the threads, then the links are written, and every node a batch links to re-picks its own links on the threads. The graph depends only on the rows, not on the threads. Effects: fail. ### `nearest` ```gizlang function nearest(g: Graph, values: Vec, nulls: bytes, q: Vec, k: i64, ef: i64, allowed: bytes, seen: mut Marks): Vec ``` The k nearest non-null rows to `q` of a graph in memory, nearest first. `allowed` (empty: every row) is one byte per row, 1 when the row may be returned. `ef` is the search breadth (at least k). Effects: fail. ### `searchDisk` ```gizlang function searchDisk(g: Graph, fetch: (rows: Vec, links: bool) => Result, q: Vec, k: i64, ef: i64, allowed: bytes, seen: mut Marks): Result ``` The k nearest non-null rows to `q` that `allowed` lets through, of a graph whose level 0 links and values stay in its segment file (Graph.onDisk), with their values: `fetch` reads rows' links and values. Effects: fail, read, write, console, io. ### `exact` ```gizlang function exact(values: Vec, nulls: bytes, dim: i64, metric: i64, q: Vec, k: i64, allowed: bytes): Vec ``` Every allowed non-null row's distance, the k nearest kept. Effects: fail. ### `writeGraphWithin` ```gizlang function writeGraphWithin(out: mut bytes, g: Graph, maxBytes: i64): Result ``` A graph as writeGraphWithin writes it: the dimension, metric word (QUANT), rows, entry and top; each row's level and level 0 link count (a byte each); the level 0 links (2M u32 a row); the upper levels (a u32 count, then for each row and level its count byte and M u32 links); then for RaBitQ the codes: the padded dimension and the bits a dimension (u32 each), the center (padded f32), the codes (padded × depth / 8 bytes a row) and the scale and add factors (f32 a row). SQ8 codes are made from the values when the graph is read (Graph.resident). The level 0 links come first among the large parts, so a cold open reads around them (ColdHome.diskGraph). Effects: fail. ## Methods ### `Spec.linksInMemory` ```gizlang function Spec.linksInMemory(self: Spec, rows: i64, budget: i64): bool ``` Whether a cold segment of `rows` rows keeps its level 0 links in memory under a budget of `budget` bytes (0: none). AUTO keeps them while they take at most a quarter of the budget: the walk then reads only the vectors it ranks; past that they stay in the file and each beam reads them. Effects: fail. ### `Graph.withBits` ```gizlang function Graph.withBits(self: Graph, values: Vec, nulls: bytes): Graph ``` The graph with RaBitQ codes of the rows (Graph.bits), Graph.depth bits a dimension (0: depthOf). One task codes a part of the rows. Effects: fail. ### `Graph.hasCodes` ```gizlang function Graph.hasCodes(self: Graph): bool ``` Whether the graph has the codes of its quantizer (none are needed on the values). ### `Graph.withCodes` ```gizlang function Graph.withCodes(self: Graph, values: Vec, nulls: bytes): Graph ``` The graph with the codes of its quantizer, made from the rows when it has none (Reader.graph gives SQ8 codes never, RaBitQ codes when it wrote them). Effects: fail. ### `Graph.resident` ```gizlang function Graph.resident(self: Graph, values: Vec, nulls: bytes): Graph ``` The graph as a walk in memory reads it: the norms and the codes of the rows. Effects: fail. ### `Graph.onDisk` ```gizlang function Graph.onDisk(self: Graph, values: Vec, nulls: bytes, linksAt: i64, links: bool): Graph ``` The graph with its level 0 links left in the segment file at `linksAt` of its block unless `links` keeps them, and in memory only what a walk on disk reads: the upper levels, the link counts and the codes (and the norms an SQ8 cosine estimate reads). Effects: fail. ### `Reader.graph` ```gizlang function Reader.graph(self: mut Reader, rows: i64, dim: i64, linksAt: i64): Graph ``` The graph writeGraphWithin wrote for a column of `rows` rows of `dim` values, with its level 0 links when `linksAt` is -1, else read without them (they stay in the file at `linksAt` of the block; ColdHome.diskGraph reads the parts around them). It has no norms or SQ8 codes (Graph.resident). A malformed one sets `bad`. Effects: fail, read, write, console, io. ## Constants ### `L2` ```gizlang const L2 = 0 ``` The metric of a graph: squared Euclidean distance. ### `COSINE` ```gizlang const COSINE = 1 ``` The metric of a graph: cosine distance, 1 minus the cosine of the angle. ### `IP` ```gizlang const IP = 2 ``` The metric of a graph: negative inner product. ### `BITS` ```gizlang const BITS = 1 ``` The codes a walk estimates distances on (Graph.quant; Spec): RaBitQ (Graph.withBits), SQ8 (Graph.encode) or none (the values). The numbers are the ones a written graph keeps in its metric word (writeGraphWithin). ### `SQ8` ```gizlang const SQ8 = 2 ``` The codes of a walk: SQ8, one byte a dimension. ### `RAW` ```gizlang const RAW = 3 ``` The codes of a walk: none, the values themselves. ### `LINK_BYTES` ```gizlang const LINK_BYTES = 128 ``` Bytes of a row's level 0 links in a written graph: 2M u32.