Indexes & metrics

Each collection has one index and one metric, chosen when it is created. The index decides how a search finds candidates; the metric decides what "near" means.

Metrics

Distances are always lower = closer, whatever the metric, so results always sort the same way.

The same point and query under each metric:

for m in cosine euclidean dot_product manhattan hamming; do
  curl -s -X POST localhost:6900/collections -H 'content-type: application/json' \
    -d "{\"name\": \"m-$m\", \"dimension\": 2, \"metric\": \"$m\", \"index\": {\"type\": \"flat\"}}" > /dev/null
  curl -s -X POST localhost:6900/collections/m-$m/points -H 'content-type: application/json' \
    -d '{"points": [{"id": "a", "vector": [1, 0]}]}' > /dev/null
  curl -s -X POST localhost:6900/collections/m-$m/search -H 'content-type: application/json' \
    -d '{"vector": [3, 4], "k": 1}'; echo
done

{"results":[{"distance":0.3999999761581421,"id":"a"}]}
{"results":[{"distance":4.4721360206604,"id":"a"}]}
{"results":[{"distance":-3.0,"id":"a"}]}
{"results":[{"distance":6.0,"id":"a"}]}
{"results":[{"distance":2.0,"id":"a"}]}

Indexes

All three apply filters while they search, not afterwards: points that fail the filter are skipped as results, so a filtered search returns up to k matching points rather than k points minus the ones that failed.

HNSW

A layered proximity graph (Hierarchical Navigable Small World). Searches walk the graph from the top layer down, keeping a beam of the best candidates; a wider beam finds more of the true neighbours and costs more time.

{"type": "hnsw", "m": 16, "ef_construction": 128, "ef_search": 64}

Every search can override the beam with ef. The beam is never narrower than k and never wider than the collection. Exact indexes ignore ef.

curl -X POST localhost:6900/collections -H 'content-type: application/json' \
  -d '{"name": "docs", "dimension": 3, "index": {"type": "hnsw", "m": 32, "ef_search": 128}}'

{"name":"docs","dimension":3,"metric":"cosine","index":{"type":"hnsw","m":32,"ef_construction":128,"ef_search":128,"seed":6512614579346866177},"count":0,"tombstones":0}

Flat

{"type": "flat"}

Compares the query with every point. It has no parameters and no build cost, and its results are exact. Above 16,384 points the scan is split across threads.

k-d tree

{"type": "kd_tree", "balance_factor": 3}

A binary space-partitioning tree that prunes branches that cannot hold a closer point, so results are exact. It shines in a few dimensions and degrades towards a flat scan as dimensions grow.

Inserts can unbalance the tree. Once its depth exceeds balance_factor × log2(n) (balance_factor is 2–64, default 3), it is rebuilt around per-axis medians, at most once every 32 inserts.

Scalar quantization

By default each vector component is a 32-bit float. With "quantization": "scalar", set when the collection is created or later, each component is stored in one byte instead, plus 8 bytes per vector. That is about a quarter of the memory: 768 dimensions take 776 bytes instead of 3,072.

curl -X POST localhost:6900/collections -H 'content-type: application/json' \
  -d '{"name": "docs", "dimension": 768, "quantization": "scalar"}'

client.create_collection("docs", 768, quantization="scalar")

Each vector is mapped onto 256 evenly spaced values between its own smallest and largest component. This needs no training, so points can be added at any time. It is lossy: searches use the decoded values, and points read back carry them too, each component within (max - min) / 510 of what was written. Expect recall to drop slightly (in our tests on random 64-dimensional data, recall@10 stayed above 0.9 against unquantized exact search).

Quantization works with the HNSW and flat indexes and every metric except hamming, which compares exact values. Turning it off later keeps the decoded values: the originals are gone.

Only memory shrinks. The write-ahead log, checkpoints and snapshots hold 32-bit floats (the decoded values once a point is stored), so disk use and the file formats stay the same, and opening a collection briefly needs the full-size vectors before quantizing them.

Binary quantization

With "quantization": "binary", searches score one bit per component (whether it is positive) plus 4 bytes per vector (its mean magnitude) instead of the vectors: 768 dimensions take 100 bytes instead of 3,072. Unlike scalar quantization, it loses nothing: the exact vectors are kept, and every search re-ranks its candidates by their exact distances, so returned distances and vectors are exact.

curl -X POST localhost:6900/collections -H 'content-type: application/json' \
  -d '{"name": "docs", "dimension": 1536, "quantization": "binary", "on_disk": true}'

client.create_collection("docs", 1536, quantization="binary", on_disk=True)

The exact vectors stay in memory unless the collection keeps them on disk, so the memory saving comes with on_disk: then only the bits are in memory, about a thirty-second of the vectors. In memory, the bits make searches read far less memory, but take a little more of it.

Signs alone are a coarse summary of a vector, so searches fetch 20 × k candidates from the bits before re-ranking them. In our tests on random 256-dimensional data, the hardest case for it, recall@10 stayed above 0.95 against exact search with every metric, through both HNSW and flat indexes. It suits high-dimensional embeddings (several hundred dimensions or more) whose components are centred around zero, such as those of most embedding models; for low-dimensional data, prefer scalar quantization. HNSW graphs are built from the exact vectors, so inserting into an on-disk collection reads vectors from disk.

The same rules as for scalar quantization apply: HNSW and flat indexes only, no hamming, and it can be switched on, off or to scalar later.

Datatypes

"datatype" sets how a vector's components are stored, in memory and in on-disk vector files. It is set per vector when the collection is created and cannot change later:

curl -X POST localhost:6900/collections -H 'content-type: application/json' \
  -d '{"name": "docs", "dimension": 1024, "datatype": "float16"}'
curl -X POST localhost:6900/collections -H 'content-type: application/json' \
  -d '{"name": "codes", "dimension": 1024, "metric": "dot_product", "datatype": "uint8"}'

client.create_collection("docs", 1024, datatype="float16")
client.create_collection("codes", 1024, metric="dot_product", datatype="uint8")

Points read back carry the stored values, so a float16 vector reads back rounded (after cosine normalisation). Searches compute exact distances to the stored values. Queries are always 32-bit floats, in every datatype, so a uint8 collection can be searched with any vector. Unlike quantization, a datatype loses nothing more than its rounding, so there is nothing to re-rank: float16 suits embeddings, whose components rarely need more than three digits, and uint8 suits models that output byte embeddings. Cosine vectors are normalised to fractions, which bytes cannot hold, so uint8 needs another metric (dot_product for byte embeddings meant for cosine similarity).

Datatypes work with every index and with binary quantization, which then keeps its exact vectors in the smaller datatype. Scalar quantization needs float32. The write-ahead log, checkpoints and snapshots hold 32-bit floats, as with quantization, so the file formats are unchanged.

Distance kernels

On x86-64 CPUs with AVX2 and FMA (Intel since Haswell, AMD since Excavator), distances are computed with 256-bit SIMD instructions, and float16 vectors are widened in hardware (F16C). The CPU is checked at run time, so the same binary runs everywhere: on other CPUs it uses portable code, which compilers vectorize for the baseline instruction set (SSE2, or NEON on ARM). The two add in a different order, so distances may differ in their last bits between machines, never within one process.

Persistence

The file engine saves the index with each checkpoint, so a restart loads the HNSW graph instead of rebuilding it. The RocksDB engine stores only the points and rebuilds the index when it opens a collection. Snapshots carry the index too. See storage & durability.

Benchmark

make bench runs crates/db/examples/benchmark.rs: it inserts clustered random points into in-memory collections with the Euclidean metric, then runs the same queries against each index and measures recall@10 against the exact (flat) results.

cargo run --release -p quiver-db --example benchmark -- 100000 128 1000

Measured on an Intel Core i7-9700K (8 cores, 3.6 GHz) under WSL 2. Queries run one after another on one thread, except the flat index, which splits each scan across all cores above 16,384 points.

100,000 points, 128 dimensions, 1,000 queries. HNSW build: 47.5 s (2,106 inserts/s).

100,000 points, 8 dimensions, 1,000 queries (-- 100000 8 1000). HNSW build: 14.2 s (7,020 inserts/s).

The k-d tree only runs at 32 dimensions or fewer. Your numbers will differ with hardware and data; the benchmark's uniform argument draws points from the unit hypercube instead, a much harder case for every graph index.