Vector search APIs with explicit storage and memory behavior.

ELI5 intuition

Think of BORSUK as many sealed boxes of vectors plus a small map. The boxes live on disk or in S3. RAM keeps the map and counters, not every vector. At production scale the map is a tree, not one flat table: root routing index, parent routing pages when needed, L0 routing pages, then bounded vector and graph blobs. A query reads the top map page, drills down to a few promising boxes, opens those boxes, and exact-reranks the candidates before returning ids or vectors.

Writes are fast because new vectors go into fresh L0 boxes. Compaction is the cleanup step after a delivery rush: it groups nearby vectors into read-optimized leaves, rebuilds graph blocks for those leaves, and publishes a new map. Scoped compaction should touch only the boxes being reorganized and the map pages needed to publish them.

BORSUK is not a magic always-perfect shortcut. Exact search can cover the full active index. Approximate search is a budgeted tradeoff: more routing metadata overfetch, segments, bytes, and candidates usually improve recall while reading more data. The report tells you when a query stopped because of a budget, so low I/O is visible instead of pretending the whole index was searched.

API Shape

Records are ids plus vectors. Callers may add only vectors and receive generated string ids, or add vectors with their own string, binary, or integer ids. There are no payload references in the public API. Explicit integer ids are encoded as compact unsigned varint bytes; shorter ids are preferred because storage uses compact binary ids internally.

index.add_vectors(vec![vec![1.0, 0.0], vec![0.0, 1.0]])?;
index.add_vectors_with_ids(vec![vec![0.9, 0.1]], vec!["alpha".into()])?;

let ids = index.search_ids(&[1.0, 0.0], SearchOptions::exact(10))?;
let vectors = index.search_vectors(&[1.0, 0.0], SearchOptions::exact(10))?;
let alpha = index.get_vector("alpha")?;

index.add([[1.0, 0.0], [0.0, 1.0]])
index.add([[0.9, 0.1]], ids=["alpha"])

ids = index.search_ids([1.0, 0.0], k=10)
vectors = index.search_vectors([1.0, 0.0], k=10)
alpha = index.get_vector("alpha")

await index.add([[1, 0], [0, 1]]);
await index.add([[0.9, 0.1]], ["alpha"]);

const ids = await index.searchIds([1, 0], { k: 10 });
const vectors = await index.searchVectors([1, 0], { k: 10 });
const alpha = await index.getVector("alpha");

Beyond dense search

The same bounded-memory engine also does in-place updates, full-text and sparse retrieval, hybrid fusion, and a per-query cost report — all over object storage.

Filtering runs inside the search, not as a post-filter on the top-k. A row is eligible for ranking only if it passes the filter, and BORSUK keeps scanning until it has k matches or the budget is spent — so a selective filter never quietly returns fewer than k results. Values may be null, boolean, integer, float, string, timestamp, list, or nested map, addressed with dotted paths (artist.name).

Native indexes can also accept sparse vector inputs, store mostly-zero vectors compactly, declare named vectors, run BM25 full-text search, and fuse named-vector + text hybrid search; see the API reference. Migration adapters expose the vendor-compatible surfaces they map cleanly; Qdrant named dense vectors map to BORSUK named vectors.

let mut meta = Metadata::new();
meta.insert("genre".into(), MetaValue::Str("rock".into()));
meta.insert("year".into(), MetaValue::Int(1975));
index.add(vec![VectorRecord::new("song-1", vec![0.0, 0.0]).with_metadata(meta)])?;

let filter = Filter::from_json(&serde_json::json!({
    "genre": "rock", "year": { "$gte": 1990 }
}))?;
let report = index.search_with_report(
    &query,
    SearchOptions::exact(10).with_filter(filter).with_include_metadata(true),
)?;

index.add(
    [[0.0, 0.0]], ids=["song-1"],
    metadata=[{"genre": "rock", "year": 1975}],
)
report = index.search_with_report(
    [0.0, 0.0], k=10,
    filter={"genre": "rock", "year": {"$gte": 1990}},
    include_metadata=True,
)
report.hits[0].metadata            # {"genre": "rock", "year": 1975}
report.segments_pruned_by_filter   # segments skipped whole

await index.add([[0, 0]], {
  ids: ["song-1"],
  metadata: [{ genre: "rock", year: 1975 }]
});
const report = await index.searchWithReport([0, 0], {
  k: 10,
  filter: { genre: "rock", year: { $gte: 1990 } },
  includeMetadata: true
});
report.hits[0].metadata;           // { genre: "rock", year: 1975 }
report.segmentsPrunedByFilter;     // segments skipped whole

The CLI takes the same dialect: borsuk search --uri "$URI" --query '[0,0]' --k 10 --filter '{"genre":"rock","year":{"$gte":1990}}' --include-metadata, and borsuk add reads metadata from plain-JSON records.

Filter operators

A bare value is an equality test; nested objects use $-prefixed operators. Multiple operators on a field, and multiple fields, combine with logical AND.

Evaluation is total — a filter never errors on a record, it matches or does not. A missing path fails positive operators and satisfies negative ones ($ne, $nin), mirroring Pinecone and MongoDB; use $exists to test presence. Cross-type comparisons are false, and $eq on a list is equality, not element matching (use $contains).

Why it saves money

Each segment summary carries compact statistics over its metadata — numeric min/max per path plus a presence bloom for strings and value kinds. Before fetching a segment, BORSUK asks could any row here match? If the statistics prove not, it skips the segment entirely: no object-storage GET, no bytes, no scan. A filter like tenant = "acme" over a multi-tenant index reads only the segments that hold that tenant. The search_with_report counters rows_evaluated, rows_passed_filter, and segments_pruned_by_filter quantify it per query; the measured selectivity sweep is in Research & Analysis.

Those resident stats are deliberately coarse so they cost almost no RAM. For exact pruning, each segment also has a small filter index — an exact inverted index over its string/boolean metadata — persisted as a separate sidecar object and fetched only when a query carries a filter, then dropped. It never sits in RAM, so it doesn't grow the footprint at any scale, and it catches what the coarse stats can't: a composite filter like {genre: rock, city: paris} can hit a segment whose bloom holds both values even though no single row has both — the exact index intersects them, sees zero matches, and skips the payload. The sidecar is self-validating, so a missing or corrupt one just falls back to reading the segment: it can only save I/O, never change results.

# before: from pinecone import Pinecone; pc = Pinecone(api_key="…")
from borsuk.compat.pinecone import Pinecone
pc = Pinecone(base_uri="file:///data/vectors", dimension=768, metric="cosine")

index = pc.Index("products")
index.upsert([("a", embedding, {"genre": "rock"})], namespace="store-1")
index.query(vector=embedding, top_k=10,
            filter={"genre": {"$eq": "rock"}},
            include_metadata=True, namespace="store-1")

# before: import boto3; s3v = boto3.client("s3vectors")
from borsuk.compat.s3vectors import client
s3v = client("s3vectors", base_uri="file:///data/vectors")

s3v.create_index(vectorBucketName="media", indexName="movies",
                 dimension=768, distanceMetric="cosine")
s3v.put_vectors(vectorBucketName="media", indexName="movies",
                vectors=[{"key": "star-wars", "data": {"float32": emb},
                          "metadata": {"genre": "scifi"}}])
s3v.query_vectors(vectorBucketName="media", indexName="movies",
                  queryVector={"float32": emb}, topK=3,
                  filter={"genre": "scifi"}, returnMetadata=True)

// before: import { Turbopuffer } from "@turbopuffer/turbopuffer";
import { Turbopuffer } from "borsuk/compat/turbopuffer";
const tpuf = new Turbopuffer({ baseUri: "file:///data/vectors", dimension: 768 });

const ns = tpuf.namespace("products");
await ns.write({ upsertRows: [{ id: "1", vector: emb, category: "animal" }],
                 distanceMetric: "cosine_distance" });
await ns.query({ rankBy: ["vector", "ANN", emb], topK: 10,
                 filters: ["And", [["category", "Eq", "animal"]]],
                 includeAttributes: ["category"] });

Five adapters ship today: Pinecone, Amazon S3 Vectors, and turbopuffer (Python + TypeScript), plus Chroma and Qdrant (Python). Pinecone, S3 Vectors, and Chroma reuse BORSUK's native $-operator filter dialect; turbopuffer's tuple filters and Qdrant's must/should/must_not filters are translated automatically. Qdrant named dense vectors map to BORSUK named vectors; unsupported operations fail explicitly. Each namespace (or collection, or S3 index) becomes its own BORSUK index under a shared base URI. These are local, embedded backends over object storage — not network services — so they carry BORSUK's own publish semantics and distances rather than each vendor's auth, replication, or similarity score. Full reference and limits: docs/drop-in.md.

• Small resident routing state. Open prepares the global product codebook, the second-level coarse product codebook, and compact chunk references. Corpus-sized product codes and vectors remain immutable objects.
• The index lives in object storage, not RAM. Global-PQ code cells and fixed-width lossless vector pages are fetched on demand. There is no resident vector arena; CURRENT is one tiny pointer.
• Fixed product-code waves. At most 32 selected chunks are retained for one scan wave. Its top candidates are merged into a bounded global heap and all chunk payloads are released before the next wave. This produces the same PQ top-k as retaining every selected chunk.
• Index-free global exact pages. Cell-aligned lossless vectors are fixed-width, so row ranges are computed arithmetically with no offset table, dictionary, or decompression state. The 128 MiB LRU is reserved for physical record-sidecar indexes used by late top-k ID reads and fallback paths.
• Bloom fast-paths avoid fetches. Resident id, vector-signature, and tombstone blooms answer “not present / not deleted” with zero object-store I/O, so the common case pays nothing.
• Concurrency doesn't multiply memory. Active and waiting query caps bound admission; leaf-wave and in-flight read caps separately bound S3 fan-out and retained buffers.
• Overlapping cell reads are single-flight. Concurrent users selecting the same immutable checksum share one active fetch/decode. The allocation is released afterward, so this does not silently create an unbounded memory cache.
• Shared decoded-segment cache, on demand. segment_cache_max_bytes lets concurrent queries share one decoded Arc<Segment>, so peak memory tracks a fixed byte budget rather than the reader count.
• Bounded prefetch & content-addressed reuse. Query waves default to 32 leaf reads under a shared 48-read handle gate, while compaction reuses unchanged routing pages by checksum to bound write amplification and transient memory.
• Disk-backed global partitioning. Finalization externally partitions PQ-code/location/lossless-vector rows under BORSUK_BUILD_SCRATCH_DIR (default .borsuk-scratch in the working directory). Scratch may scale with the corpus, while build RAM remains bounded by training, one segment, a 32 MiB code chunk, and a 16 MiB exact page.

These mechanisms are observable: SearchReport exposes bytes_read, routing resident_bytes_estimate, cache hits/misses, records considered vs scored, and the requests breakdown. Benchmark resource traces separately record total process RSS, CPU, disk/cache use, and S3 I/O because routing metadata alone is not a complete memory measurement.

Distance metrics

You choose the metric when you create an index — metric="cosine", "euclidean", "inner-product", "minkowski:3", and so on. Over thirty are built in. Every one returns a distance (smaller = more similar), so a search always keeps the k smallest, no matter whether the underlying formula is a distance or a similarity.

Full equations, input constraints, and per-metric notes are in the API reference.

Leaf Modes

Approximate search first chooses segments, then each selected segment chooses candidate rows. Every approximate mode exact-reranks the selected rows before returning ids or vectors. pq-scan is the production mode — graph-free, compressed, and the lowest, most predictable memory footprint. The graph-backed modes (graph, vamana-pq, hybrid) are experimental: they can lift recall on some datasets but read extra graph objects and cost more memory. Graph-backed modes read graph Parquet only when k < min(max_candidates_per_segment, segment_len) < segment_len.

How each mode actually works

In v8, pq-scan means a two-level rotated product-quantization path: an adaptive full-dimensional router assigns vectors to global cells (flat for measured ordinary angular corpora, hierarchical for large angular and Euclidean corpora), then asymmetric-distance lookup tables scan the selected paged product codes. The independently tested product router is a rejected ablation. The older cell-local TurboQuant-4b sketch remains a fallback for filtered, WAL, and non-finalized paths. Publication results name both layers explicitly. vamana-pq remains an experimental graph label, not a claim to implement DiskANN's Vamana construction. Every returned row is exact-scored on its full float32 vector; approximation changes only the shortlist.

flat-scan · production

No sketch at all. Every row in a fetched segment is scored on its full vector, so within a searched segment it is exact. It is the ground truth the other modes approximate and the simplest path to reason about — useful as a baseline and for graph-free testing.

sq-scan · production

Each row stores one scalar routing_code: a cheap signed projection of its vector (an alternating-sign sum of coordinates). Candidate rows are the ones whose code is nearest the query's code by absolute difference, then exact-reranked. It is the cheapest graph-free way to shrink the candidate set, at the cost of a coarse one-dimensional filter.

pq-scan · production (recommended)

A finalized v8 index stores one byte per rotated product-PQ subspace in immutable code chunks. The adaptive full-dimensional coarse router assigns each vector to a global semantic cell, independent of its bounded ingest checkpoint. Search loads only chunks in selected cells, computes ADC distances from the resident codebook, keeps a bounded global shortlist, and exact-reranks lossless rows. Chunks are processed in fixed waves, so 100M vectors do not imply 100M resident codes. Code width is also adaptive: measured defaults use 64 bytes for 96–128D standard corpora, 128 bytes for the 256D NYTimes regime, and 256 bytes for 768+D corpora with at least 100,000 rows. On GIST-960, the code256 / 24-probe / 96-candidate point reaches 0.995 empirical recall and adds only 1.5% to the complete index; exact search remains the separate formal-1.0 path. The older cell-local TurboQuant-4b SRHT sketch is retained for filtered, WAL, and non-finalized fallback searches. Both paths are graph-free; the paged global-PQ path is the production default.

graph · experimental

Alongside the segment, a small proximity graph is stored as numeric row-reference edges in a separate Parquet block. For segments up to 256 rows the graph is an exact k-nearest all-pairs build; above that it uses a bounded, windowed construction (candidates drawn from vector-locality and routing-code orderings inside a fixed window) rather than a full Vamana robust-prune, which keeps write cost from growing quadratically. At query time it seeds entry rows by routing_code and performs a deterministic score-once best-first traversal: a binary heap orders distance then record id, and a dense state table prevents duplicate scoring. Decoded, validated immutable graphs share the byte-accounted segment cache; warm() prepares them before the first graph query. Fresh L0 insert segments are written in this mode. Experimental: graph-enabled indexes store extra objects and the large-segment construction is still being tuned.

vamana-pq · experimental

The same segment-local graph and greedy traversal as graph, but entry rows are seeded by pq_code distance instead of the scalar code. Despite the name it is not the DiskANN/Vamana robust-prune algorithm — it is that greedy graph over PQ-seeded entries. Compaction writes L1+ leaves in this mode. Experimental.

hybrid · experimental

Per-segment dispatch. Every segment records the mode it was written with (L0 as graph, L1+ as vamana-pq), and a hybrid query uses each segment's own mode, reading graph blocks only for the graph-backed segments that have budget to expand. Reach for it when fresh L0 inserts and compacted L1+ leaves coexist, so callers don't have to track the active mix. Experimental.

Vector / record

The unit you store and search: an id plus a float32 vector. Ids can be strings, integers, or raw bytes; there are no payload references in the public API.

Segment

An immutable Parquet object holding a batch of vectors — BORSUK's unit of storage and I/O, also called a leaf. Segments are never mutated in place; new data is appended as new segments and reorganized later by compaction.

Bubble

The informal name for a segment's spatial summary — its centroid and radius together. A query prunes the bubbles it cannot possibly beat and reads only the rest.

Centroid

The mean of a segment's member vectors (each dimension averaged over the members). It is recomputed as vectors are added and is what a query measures distance to when choosing which segments to read.

Radius

The distance from a segment's centroid to its farthest member. It bounds the bubble, so a query can form the lower bound lb(q, s) = max(0, d(q, c_s) − r_s) and skip any segment whose closest possible point is still too far.

Overlapping segments

Bubbles are allowed to overlap in space — BORSUK never forces the segments to partition the vector space. A vector still belongs to exactly one segment (the one it was routed to at insert time), but the region two bubbles cover can intersect. This is fine and expected: a query simply reads every bubble whose lower bound qualifies, so a point sitting in an overlap is found regardless of which segment owns it, and correctness holds because the read candidates are always exact-reranked on full vectors. The only cost of heavy overlap is extra reads — more bubbles pass the pruning test — which compaction and the incremental split/merge keep in check by tightening bubbles over time. This is also why BORSUK does not need to reassign a vector to its strictly-nearest segment: the lower-bound test already spans all candidates.

Pivot

A routing representative vector derived from segment centroids. Paged readers keep only the top-level routing state resident and fetch lower routing pages as needed; resident-routing mode loads the complete pivot table.

Routing page / routing tree

The paged, hierarchical index over segment summaries. A query walks it from the top layer down to candidate segments, fetching only the pages it needs so routing memory does not grow as a fully resident table.

Segment summary

The routing record for one segment: its id, level, object path, record count, centroid, radius, and bloom filters. In paged mode it is loaded through routing pages; in resident-routing mode the full set is kept in memory.

Manifest

The object that lists the active segments, the tombstone, the pivots, and index metadata for one published version of the index.

CURRENT

A single small pointer object naming the active manifest version. It is the only non-Parquet persistent object, and the compare-and-swap on it is what makes concurrent publishes safe.

Level (L0 / L1+)

LSM-style levels. L0 holds freshly appended insert segments; compaction rewrites them into read-optimized L1+ leaves that pack nearby vectors together.

Compaction

Rewriting segments from a source level into new target-level leaves — sorting nearby vectors together for better locality and physically dropping tombstoned rows in the same pass.

Tombstone

A soft-delete marker. Deleted ids are recorded once and filtered out at query time; the underlying rows are physically reclaimed later by compaction or an explicit purge.

Split / merge

Incremental maintenance operations. An oversized bubble splits into tighter children; a bubble left sparse by deletes merges into its nearest neighbour. Both touch only the affected segments and can run in parallel across nodes.

Leaf mode

The per-segment strategy for choosing which rows to exact-score: flat-scan, sq-scan, pq-scan (production) or graph, vamana-pq, hybrid (experimental). See Leaf modes.

pq_code / routing_code

The compact per-row sketches a leaf mode ranks by before exact scoring — a per-dimension byte code (pq_code) and a scalar projection (routing_code).

Rerank

The always-final step of scoring the selected candidate rows on their full float32 vectors under the index metric. Because rerank is exact, a leaf mode only changes which rows are scored, never the scores.

Resident metadata (resident bytes)

The routing metadata BORSUK estimates as resident: manifest fields, top-level routing state, and — only in resident-routing mode — all segment summaries. Reported as resident_bytes_estimate; it is not total process RSS and does not include decoded cells, runtime allocations, or cache contents.

Recall

The fraction of a query's true nearest neighbours that were actually returned. Exact mode returns all of them; approximate mode reports whether coverage was complete or budget-limited.

Metadata

A schemaless, JSON-like object stored next to each vector — string keys mapping to null, boolean, integer, float, string, timestamp, list, or nested-map values. Kept in a compact binary column, returned only when a search opts in with include_metadata. See Metadata filtering.

Filter

A predicate over metadata that constrains a search to matching rows, written as a Pinecone-style operator dictionary ({"genre": "rock", "year": {"$gte": 1990}}). Applied before ranking, so results are exact rather than a post-filter over an unfiltered top-k.

Prefilter (filter-first search)

The strategy of deciding which rows match the filter first, then ranking only those, instead of ranking the vector-nearest rows and dropping the non-matches afterward. It matters when a filter is selective: filtering first means the query never wastes work scoring rows it will discard, and it cannot miss a matching neighbour just because it fell outside the vector-nearest window. See the filtered-query visualization.

Metadata statistics / segment pruning

Per-segment summaries of the metadata it holds — numeric min/max per dotted path plus a presence bloom over string values and value kinds. A filtered query uses them to prove a segment holds no matching row and skip it before any payload fetch, so selective filters read only the segments that can match. Negated and existence predicates never prune.

Namespace

In the migration adapters, the partition unit inherited from Pinecone/turbopuffer (a namespace) or S3 Vectors (an index within a bucket). Each maps to its own BORSUK index under a shared base URI, so tenants and collections stay physically isolated.

Functionality

The Rust crate, Python package, and TypeScript package support create/open, generated or explicit ids, dense or sparse vector inputs, named vectors, exact and approximate id/vector search, BM25 text search, named-vector + text hybrid search, batch search, Float32 buffer inputs, get-by-id vector loading, stats, scoped compaction, full-level rebuild, obsolete segment garbage collection, metric catalogs, leaf-mode catalogs, vector distance helpers, strict id recall helpers, and tie-aware distance recall helpers.

How your data is stored

Manifests, segment summaries, pivots, routing rows, physical record rows, sparse columns, BM25, and optional graph blocks are Parquet-backed binary data. BM25 and named-sparse search load small field roots during open, route query terms to bounded term pages, then range-read only selected posting and row-metadata row groups; they never download a complete postings file to find one term. Exact block-max bounds avoid later reads without changing recall, while one shared byte gate bounds decoded work across users. The production pq-scan artifact uses a standard Parquet adaptive-IVF/product-PQ descriptor plus standard Arrow IPC ANN bundles. Each cell chunk is one record batch with an independently range-addressable fixed-size scan payload and typed exact-vector values buffer. The descriptor stores their checked byte ranges, so a query fetches only selected scan slices and bounded exact-rerank rows; final IDs come from the physical record sidecar. CURRENT is a fixed binary pointer to the active immutable version and the only custom durable object.

Testing and performance

Correctness gates, release-scale workloads, raw latency distributions, recall curves, and CPU/RAM/NVMe timelines are kept with the reproducible benchmark artifacts and research documentation.

Research

• DiskANN — billion-point nearest-neighbour search on a single node (NeurIPS 2019); the Vamana graph on SSD.
• FreshDiskANN — streaming inserts/deletes without full rebuild (2021).
• SPFresh — incremental in-place update for billion-scale vector search (SOSP 2023); centroid posting-lists with lightweight rebalancing.
• SPANN — the disk-resident centroid/posting-list index SPFresh builds on.
• HNSW — hierarchical navigable small worlds (Malkov & Yashunin, TPAMI 2018), the in-RAM graph most engines use.
• ScaNN — anisotropic vector quantization (ICML 2020).
• TurboQuant — random rotations and coordinate quantization evaluated for vector search.
• DSANN — disaggregated-storage approximate nearest-neighbour search.
• Puffin-backed vector indexes — vector indexing in open table formats over object storage.

Systems compared

• turbopuffer architecture — object-storage-first, SPFresh-based index.
• Pinecone serverless architecture and slab architecture — LSM slabs on object storage with a freshness layer.
• Amazon S3 Vectors — purpose-built object-storage vectors.
• Qdrant filtering — filter-aware HNSW traversal.
• Weaviate filtering (ACORN) and vector index (HFresh = SPFresh).
• Milvus on object storage — decoupled storage/compute.
• pgvector and its 0.8.0 filtering improvements.
• FAISS — index-type library reference.
• awesome-vector-databases — a broad landscape catalog.

Full markdown docs

The source repository keeps the long-form documentation beside the implementation:

• docs/architecture.md explains segment layout, routing, cache behavior, and compaction.
• docs/api.md covers Rust, Python, TypeScript, and CLI usage.
• docs/drop-in.md documents migration adapters and their compatibility limits.
• docs/storage-format.md documents the Parquet tables, binary CURRENT pointer, and compatibility rules.
• docs/benchmarks.md lists performance benchmarks, smoke checks, and tracked measurements.
• docs/production-readiness.md defines the correctness, package, storage, performance, memory, API, and object-store gates for a production-ready release.

License

BORSUK uses the Business Source License 1.1. Production use is free unless your company, organization, and affiliates make over US $100,000/year.