README.md

# Learn Vector Databases 🧭

<div align="center">

[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
[![pgvector Version](https://img.shields.io/badge/pgvector-0.8+-4169E1.svg?logo=postgresql)](https://github.com/pgvector/pgvector)
[![CI](https://github.com/TheLearningHubOrg/learn-vector-databases/actions/workflows/ci.yml/badge.svg)](https://github.com/TheLearningHubOrg/learn-vector-databases/actions/workflows/ci.yml)
[![Release](https://img.shields.io/github/v/release/TheLearningHubOrg/learn-vector-databases)](https://github.com/TheLearningHubOrg/learn-vector-databases/releases)
[![Qdrant](https://img.shields.io/badge/Qdrant-1.x-DC244C.svg?logo=qdrant)](https://qdrant.tech/documentation/)
[![Python](https://img.shields.io/badge/Python-3.12%20%7C%203.13-3776AB.svg?logo=python)](https://docs.python.org/3/)

**From your first cosine distance to staff-level vector search architecture: metrics, ANN indexes, quantization, filtering, multi-tenancy and distributed operations.**  
HNSW, IVF, DiskANN, SQ8, PQ and binary quantization, pgvector, Qdrant, Milvus, Weaviate and Pinecone, hybrid search with RRF, sharding, WAL and compaction.

[Getting Started](#1-stage-1-vector-foundations-metrics--first-queries) • [ANN Indexing](#2-stage-2-approximate-nearest-neighbor-indexing) • [Quantization](#3-stage-3-quantization--memory-compression) • [Engines](#4-stage-4-database-landscape--architecture) • [Filtering & Hybrid](#5-stage-5-filtering-multi-tenancy--hybrid-search) • [Distributed Ops](#6-stage-6-distributed-scaling--production-operations) • [Interview Prep](#7-stage-7-staff-vector-database-engineer-interview-handbook--cheatsheet)

<br/>

<a href="https://www.buymeacoffee.com/manthanank">
  <img src="public/bmc-button.svg" alt="Buy Me A Coffee" width="180">
</a>

</div>

---

## 🗺️ 7-Stage Pedagogical Roadmap

```mermaid
flowchart LR
    S1["Stage 1: Vectors & Metrics"] --> S2["Stage 2: ANN Indexing"]
    S2 --> S3["Stage 3: Quantization"]
    S3 --> S4["Stage 4: Engines"]
    S4 --> S5["Stage 5: Filtering & Hybrid"]
    S5 --> S6["Stage 6: Distributed Ops"]
    S6 --> M["Masterclasses M1-M6"]
    M --> S7["Stage 7: Staff Interview Handbook"]
```

| Stage | Focus Domain | Core Concepts & Engineering Outcomes |
| :--- | :--- | :--- |
| **Stage 1** | **Vector Foundations, Metrics & First Queries** | Embeddings and dimensions, L2 / cosine / inner product / L1 / Hamming, `l2_normalize`, the curse of dimensionality, dense vs sparse vectors. Run pgvector's `<->`, `<=>`, `<#>`, `<+>` operators and the starter FastAPI service; reason about which metric an embedding model expects. |
| **Stage 2** | **Approximate Nearest Neighbor Indexing** | Exact kNN as ground truth, `recall_at_k`, IVF (`nlist`, `nprobe`, `ivfflat.probes`), HNSW (`m`, `ef_construction`, `hnsw.ef_search`, layer assignment, the neighbour heuristic), deletes and tombstones, LSH and Annoy, DiskANN/Vamana, ScaNN. Pick and tune an index and prove its recall. |
| **Stage 3** | **Quantization & Memory Compression** | RAM sizing for vectors and graphs, SQ8 with quantile clipping, `halfvec` FP16, PQ codebooks and ADC lookup tables, 1-bit `binary_quantize` with `<~>` Hamming, oversampling and rescoring. Cut memory 4-32x and measure what it costs in recall. |
| **Stage 4** | **Database Landscape & Architecture** | Purpose-built engines vs extensions; Qdrant segments and `GET /collections` fields, Milvus growing/sealed segments and consistency levels, pgvector, Redis `FT.CREATE`, Elasticsearch `knn`; the same query in six APIs; capacity estimates with `estimate_memory`. Pick an engine from numbers. |
| **Stage 5** | **Filtering, Multi-Tenancy & Hybrid Search** | Post-filter vs pre-filter vs in-graph filtering measured in the starter, cardinality-based planning, `hnsw.iterative_scan`, partial indexes, roaring bitmaps, Qdrant `is_tenant` and `payload_m`, Milvus partition keys, Weaviate tenant states, BM25, RRF / relative score / DBSF fusion, hybrid SQL with `tsvector`. |
| **Stage 6** | **Distributed Scaling & Production Operations** | Consistent hashing and shard keys, scatter-gather, `R + W > N` quorums, WAL and segments with tombstones and compaction (runnable), bulk loads with `indexing_threshold: 0`, SIMD, page cache, snapshots, alias and view swaps, recall canaries, capacity planning. |
| **Masterclasses** | **M1 Benchmarking, M2 Hybrid & Reranking, M3 Multi-Vector, M4 Matryoshka Funnels, M5 Model Migration, M6 Blueprint** | Recall/QPS Pareto sweeps; fusion plus cross-encoder rerank; ColBERT-style MaxSim with Qdrant multivectors; prefix shortlists with full-vector rescoring; dual-write, backfill, shadow-read and alias cut-over; a multi-tenant hybrid service, runnable in-process and as a Qdrant service class. |
| **Stage 7** | **Staff Interview Handbook** | 53 interview Q&As across concepts, internals, architecture and scenarios, plus a one-page cheatsheet. |

### Which languages this guide uses, and why

Vector databases are language-neutral servers, so each topic is shown in the tool's own interface first: **SQL** for pgvector (the scripts in [`sql/`](sql/)), the **REST API** with `curl` for Qdrant, and engine config files where they exist. Client code is **Python**, because the embedding and RAG ecosystem and the official clients for Qdrant, Milvus, Weaviate and Chroma all lead with Python, and every embedding model ships a Python SDK first. The starter project is a small FastAPI service over a pure-Python index ([`src/learn_vector_databases/`](src/learn_vector_databases/)), written to be read side by side with Stages 1-3 rather than to compete with FAISS or hnswlib.

---

## 🆕 Vector Database Versions, What's New & Migration

There is no single "vector database" release train. This guide tracks the engines it uses: **pgvector** (the SQL examples and CI), **Qdrant** (the REST and Python examples), and **Milvus** and **Weaviate** where Stages 4-5 compare them. Where a version number is not certain, the guide says "current stable".

### V.1 Release Timeline

```mermaid
timeline
    title Releases that changed how vector search is built
    section 2023
      pgvector 0.5.0 : HNSW index type next to IVFFlat
    section 2024
      pgvector 0.6.0 : parallel HNSW builds
      pgvector 0.7.0 : halfvec, sparsevec, bit types, binary_quantize, L1 and Hamming operators
      Qdrant 1.10 : universal Query API with prefetch and RRF fusion, multivectors
      Qdrant 1.11 : tenant-optimised keyword index (is_tenant), DBSF fusion
      Milvus 2.4 : sparse vectors, multi-vector hybrid search, GPU CAGRA index
      pgvector 0.8.0 : iterative index scans for filtered queries
      Milvus 2.5 : built-in BM25 full-text search
    section 2025
      Qdrant 1.13 : GPU-accelerated HNSW indexing
      Milvus 2.6 : RaBitQ 1-bit quantization, Woodpecker WAL, tiered storage
    section Current stable
      pgvector 0.8.x : the version the SQL scripts and CI target
      Qdrant 1.x : Query API is the main search entry point
```

### V.2 Compatibility Matrix

| Engine | Version this guide targets | Runs on | Client used here | Notes |
| --- | --- | --- | --- | --- |
| pgvector | 0.8.x (current stable) | PostgreSQL 13 or newer | `psql`, any Postgres driver | CI uses the `pgvector/pgvector:pg17` image. HNSW needs 0.5.0+, `halfvec`/`bit`/`binary_quantize` need 0.7.0+, iterative scans need 0.8.0+. |
| Qdrant | 1.10 or newer (current stable 1.x) | Linux container, Qdrant Cloud | REST, `qdrant-client` for Python | `query_points` replaces the older `search`, `search_batch` and `recommend` calls. |
| Milvus | 2.5 or newer | Kubernetes, Docker, Milvus Lite for local tests | `pymilvus` (`MilvusClient`) | 2.5 adds BM25 full-text search; 2.6 adds RaBitQ and a new WAL. |
| Weaviate | 1.x, client v4 | Container, Weaviate Cloud | `weaviate-client` v4 | v4 Python client talks gRPC; the v3 client is deprecated. |
| Starter project | 1.0.0 | Python 3.12 or 3.13 | FastAPI, uvicorn | Pure Python index, no NumPy needed. |

### V.3 What's New in Current Stable

#### pgvector 0.7: smaller types and binary quantization in SQL

Before 0.7 every vector was `vector` (4 bytes per dimension) and the HNSW index was capped at 2,000 dimensions. 0.7 added `halfvec` (2 bytes per dimension, indexable up to 4,000 dimensions), `bit` with `binary_quantize`, and `sparsevec`, so quantization can live in an expression index while the table keeps full precision.

```sql
-- Before: full-precision index only
CREATE INDEX ON docs USING hnsw (embedding vector_cosine_ops);

-- After: FP16 index over a full-precision column
CREATE INDEX ON docs USING hnsw ((embedding::halfvec(16)) halfvec_cosine_ops);
-- queries must use the same expression to hit the index
SELECT id FROM docs ORDER BY embedding::halfvec(16) <=> $1::halfvec(16) LIMIT 10;
```

#### pgvector 0.8: iterative index scans

An HNSW scan returns at most `hnsw.ef_search` candidates. With a selective `WHERE` clause most of them are filtered out and the query can return fewer rows than `LIMIT`. 0.8 lets the scan keep walking the graph until enough rows pass the filter.

```sql
-- Before: a 2% filter could return 1 row for LIMIT 10
SELECT id FROM docs WHERE tenant = 7 ORDER BY embedding <=> $1 LIMIT 10;

-- After: keep scanning until LIMIT is met (or max_scan_tuples is reached)
SET hnsw.iterative_scan = relaxed_order;
SELECT id FROM docs WHERE tenant = 7 ORDER BY embedding <=> $1 LIMIT 10;
```

`relaxed_order` may return rows slightly out of distance order; `strict_order` keeps exact order at a higher cost. Wrap the query in a subquery and re-sort if order matters.

#### Qdrant 1.10: the Query API

`query_points` replaces separate `search`, `recommend` and `discover` calls and adds server-side multi-stage queries: prefetch candidates with one vector (or a quantized one), then fuse or rescore.

```python
from qdrant_client import QdrantClient, models

client = QdrantClient(url="http://localhost:6333")

# Before (deprecated): client.search(collection_name="docs", query_vector=vec, limit=5)
# After:
hits = client.query_points(collection_name="docs", query=[0.1, 0.9, 0.2, 0.0], limit=5).points
```

### V.4 Migration Guide (pgvector 0.6 to 0.8, Qdrant client to the Query API)

```bash
# 1. pgvector: upgrade the extension package (image tag or OS package), then in each database:
psql "$DATABASE_URL" -c "ALTER EXTENSION vector UPDATE;"
psql "$DATABASE_URL" -c "SELECT extversion FROM pg_extension WHERE extname = 'vector';"

# 2. Rebuild IVFFlat indexes after large data changes (lists are trained at build time):
psql "$DATABASE_URL" -c "REINDEX INDEX CONCURRENTLY docs_ivf;"

# 3. Qdrant Python client: upgrade, then replace search() with query_points()
pip install --upgrade qdrant-client
grep -rn "\.search(" --include="*.py" .
```

### V.5 Deprecations & Breaking Changes

| Version | Deprecated / removed | Replacement | What breaks and how to fix it |
| --- | --- | --- | --- |
| pgvector 0.7.0 | HNSW limited to 2,000-dim `vector` | `halfvec` index (up to 4,000 dims) or `binary_quantize` expression index | 3,072-dim models (for example `text-embedding-3-large`) could not be indexed. Index `embedding::halfvec(3072)` instead. |
| pgvector 0.8.0 | Relying on `hnsw.ef_search` alone for filtered queries | `hnsw.iterative_scan` | Filtered queries silently returned fewer rows than `LIMIT`. Turn on iterative scans and set `hnsw.max_scan_tuples`. |
| Qdrant client 1.10+ | `search`, `search_batch`, `recommend`, `discover` | `query_points`, `query_batch_points` | Old methods emit deprecation warnings and are dropped in newer clients. Results move to `.points`. |
| Weaviate client v4 | v3 Python client (`weaviate.Client`) | `weaviate.connect_to_local()` / `connect_to_weaviate_cloud()` | Different object model and gRPC port 50051 must be reachable. |
| Weaviate (current stable 1.x) | Tenant states `HOT` / `COLD` | `ACTIVE` / `INACTIVE` / `OFFLOADED` | Old names still map, but new code should use the new enum values. |

---

## 📋 Table of Contents

- [🆕 Versions, What's New & Migration](#-vector-database-versions-whats-new--migration)
- [1. Stage 1: Vector Foundations, Metrics & First Queries](#1-stage-1-vector-foundations-metrics--first-queries)
  - [1.1 What a Vector Database Is and the Problem It Solves](#11-what-a-vector-database-is-and-the-problem-it-solves)
  - [1.2 Embeddings: Where Vectors Come From](#12-embeddings-where-vectors-come-from)
  - [1.3 Installation & First Run](#13-installation--first-run)
  - [1.4 First Queries with pgvector](#14-first-queries-with-pgvector)
  - [1.5 Distance Metrics: Euclidean, Squared L2, Inner Product, Cosine, Manhattan, Hamming](#15-distance-metrics-euclidean-squared-l2-inner-product-cosine-manhattan-hamming)
  - [1.6 Metric Equivalence & Why L2 Normalisation Matters](#16-metric-equivalence--why-l2-normalisation-matters)
  - [1.7 The Curse of Dimensionality & Why B-Trees and k-d Trees Fail](#17-the-curse-of-dimensionality--why-b-trees-and-k-d-trees-fail)
  - [1.8 Dense, Sparse & Hybrid Representations](#18-dense-sparse--hybrid-representations)
  - [1.9 Line-by-Line Breakdown of the Starter API](#19-line-by-line-breakdown-of-the-starter-api)
  - [1.10 Pitfalls](#110-pitfalls)
  - [1.11 Best Practices](#111-best-practices)
  - [1.12 Hands-on Exercise](#112-hands-on-exercise)
- [2. Stage 2: Approximate Nearest Neighbor Indexing](#2-stage-2-approximate-nearest-neighbor-indexing)
  - [2.1 Exact kNN vs Approximate Nearest Neighbor & Recall@K](#21-exact-knn-vs-approximate-nearest-neighbor--recallk)
  - [2.2 Inverted File (IVF) Indexes & Voronoi Cell Partitioning](#22-inverted-file-ivf-indexes--voronoi-cell-partitioning)
  - [2.3 Hierarchical Navigable Small World (HNSW) Graphs](#23-hierarchical-navigable-small-world-hnsw-graphs)
  - [2.4 HNSW Insert & Search, Step by Step in Code](#24-hnsw-insert--search-step-by-step-in-code)
  - [2.5 HNSW Hyperparameters: `M`, `ef_construction` and `ef_search`](#25-hnsw-hyperparameters-m-ef_construction-and-ef_search)
  - [2.6 Deletes, Updates & Graph Maintenance](#26-deletes-updates--graph-maintenance)
  - [2.7 Tree-Based Indexes (Annoy) & Locality-Sensitive Hashing (LSH)](#27-tree-based-indexes-annoy--locality-sensitive-hashing-lsh)
  - [2.8 DiskANN & the Vamana Graph](#28-diskann--the-vamana-graph)
  - [2.9 Google ScaNN & Anisotropic Vector Quantization](#29-google-scann--anisotropic-vector-quantization)
  - [2.10 Choosing an Index](#210-choosing-an-index)
  - [2.11 Pitfalls](#211-pitfalls)
  - [2.12 Best Practices](#212-best-practices)
  - [2.13 Hands-on Exercise](#213-hands-on-exercise)
- [3. Stage 3: Quantization & Memory Compression](#3-stage-3-quantization--memory-compression)
  - [3.1 Sizing Memory: Vectors, Graph and Overhead](#31-sizing-memory-vectors-graph-and-overhead)
  - [3.2 Scalar Quantization (SQ8): float32 to int8](#32-scalar-quantization-sq8-float32-to-int8)
  - [3.3 Half Precision: float16, bfloat16 and pgvector `halfvec`](#33-half-precision-float16-bfloat16-and-pgvector-halfvec)
  - [3.4 Product Quantization (PQ): Sub-Vector Codebooks](#34-product-quantization-pq-sub-vector-codebooks)
  - [3.5 Asymmetric vs Symmetric Distance Computation (ADC vs SDC)](#35-asymmetric-vs-symmetric-distance-computation-adc-vs-sdc)
  - [3.6 Production Product Quantizer with NumPy](#36-production-product-quantizer-with-numpy)
  - [3.7 Binary Quantization (BQ): One Bit per Dimension](#37-binary-quantization-bq-one-bit-per-dimension)
  - [3.8 Oversampling & Rescoring](#38-oversampling--rescoring)
  - [3.9 Quantization Trade-off Matrix](#39-quantization-trade-off-matrix)
  - [3.10 Pitfalls](#310-pitfalls)
  - [3.11 Best Practices](#311-best-practices)
  - [3.12 Hands-on Exercise](#312-hands-on-exercise)
- [4. Stage 4: Database Landscape & Architecture](#4-stage-4-database-landscape--architecture)
  - [4.1 Dedicated Specialized Vector DBs vs Vector-Extended Databases](#41-dedicated-specialized-vector-dbs-vs-vector-extended-databases)
  - [4.2 Architectural Breakdown: Qdrant, Pinecone, Milvus, Weaviate, ChromaDB](#42-architectural-breakdown-qdrant-pinecone-milvus-weaviate-chromadb)
  - [4.3 Relational & Document Extensions: PostgreSQL `pgvector`, Redis, OpenSearch](#43-relational--document-extensions-postgresql-pgvector-redis-opensearch)
  - [4.4 Storage Engine Layouts: In-Memory vs MMAP Disk-Backed vs Quantized RAM plus SSD](#44-storage-engine-layouts-in-memory-vs-mmap-disk-backed-vs-quantized-ram-plus-ssd)
  - [4.5 Deep Dive into Pinecone Serverless Architecture](#45-deep-dive-into-pinecone-serverless-architecture)
  - [4.6 Exhaustive Head-to-Head Engine Comparison](#46-exhaustive-head-to-head-engine-comparison)
  - [4.7 Inside a Qdrant Collection: Points, Segments and Payload](#47-inside-a-qdrant-collection-points-segments-and-payload)
  - [4.8 Inside Milvus: Growing and Sealed Segments, Consistency Levels](#48-inside-milvus-growing-and-sealed-segments-consistency-levels)
  - [4.9 The Same Query in Six APIs](#49-the-same-query-in-six-apis)
  - [4.10 Consistency, Durability & Transactions Compared](#410-consistency-durability--transactions-compared)
  - [4.11 Choosing an Engine with a Capacity Estimate](#411-choosing-an-engine-with-a-capacity-estimate)
  - [4.12 Pitfalls](#412-pitfalls)
  - [4.13 Best Practices](#413-best-practices)
  - [4.14 Hands-on Exercise](#414-hands-on-exercise)
- [5. Stage 5: Filtering, Multi-Tenancy & Hybrid Search](#5-stage-5-filtering-multi-tenancy--hybrid-search)
  - [5.1 The Filtering Dilemma: Post-Filtering vs Pre-Filtering Recall Collapse](#51-the-filtering-dilemma-post-filtering-vs-pre-filtering-recall-collapse)
  - [5.2 Single-Stage Payload-Filtered HNSW Graph Traversal](#52-single-stage-payload-filtered-hnsw-graph-traversal)
  - [5.3 Measuring the Three Strategies in the Starter](#53-measuring-the-three-strategies-in-the-starter)
  - [5.4 Query Planning by Cardinality](#54-query-planning-by-cardinality)
  - [5.5 Filtering in pgvector: Iterative Scans, Partial Indexes and B-trees](#55-filtering-in-pgvector-iterative-scans-partial-indexes-and-b-trees)
  - [5.6 Filter Optimization with Roaring Bitmaps](#56-filter-optimization-with-roaring-bitmaps)
  - [5.7 Multi-Tenancy Isolation Patterns: Namespaces vs Collections vs Partition Keys](#57-multi-tenancy-isolation-patterns-namespaces-vs-collections-vs-partition-keys)
  - [5.8 Enterprise Multi-Tenancy in Milvus & Weaviate](#58-enterprise-multi-tenancy-in-milvus--weaviate)
  - [5.9 Dynamic Tenant Rebalancing & Mitigating "Noisy Neighbors"](#59-dynamic-tenant-rebalancing--mitigating-noisy-neighbors)
  - [5.10 Hybrid Search: Fusing Vector Proximity with Inverted Text Indexes](#510-hybrid-search-fusing-vector-proximity-with-inverted-text-indexes)
  - [5.11 Fusion Methods: RRF, Relative Score Fusion and DBSF](#511-fusion-methods-rrf-relative-score-fusion-and-dbsf)
  - [5.12 Hybrid Search in SQL with pgvector and `tsvector`](#512-hybrid-search-in-sql-with-pgvector-and-tsvector)
  - [5.13 Pitfalls](#513-pitfalls)
  - [5.14 Best Practices](#514-best-practices)
  - [5.15 Hands-on Exercise](#515-hands-on-exercise)
- [6. Stage 6: Distributed Scaling & Production Operations](#6-stage-6-distributed-scaling--production-operations)
  - [6.1 Distributed Topologies: Coordinators, Shard Replicas & Raft Consensus](#61-distributed-topologies-coordinators-shard-replicas--raft-consensus)
  - [6.2 Sharding: Hash Routing, Consistent Hashing and Shard Keys](#62-sharding-hash-routing-consistent-hashing-and-shard-keys)
  - [6.3 Replication and Consistency: Quorums in Practice](#63-replication-and-consistency-quorums-in-practice)
  - [6.4 High-Throughput Write Pipelines: WAL, Segment Immutability & Compaction](#64-high-throughput-write-pipelines-wal-segment-immutability--compaction)
  - [6.5 The Write Path in Code](#65-the-write-path-in-code)
  - [6.6 High-Throughput Ingestion: Batching, Bulk Loads and Kafka](#66-high-throughput-ingestion-batching-bulk-loads-and-kafka)
  - [6.7 Hardware Acceleration: SIMD, AVX-512, and ARM Neon Vectorization](#67-hardware-acceleration-simd-avx-512-and-arm-neon-vectorization)
  - [6.8 Linux OS Page Cache Tuning for On-Disk Vector Storage](#68-linux-os-page-cache-tuning-for-on-disk-vector-storage)
  - [6.9 Snapshot Backups, Recovery & Zero-Downtime Index Rebuilding](#69-snapshot-backups-recovery--zero-downtime-index-rebuilding)
  - [6.10 Observability: What to Measure and Alert On](#610-observability-what-to-measure-and-alert-on)
  - [6.11 Capacity Planning and Cost](#611-capacity-planning-and-cost)
  - [6.12 Pitfalls](#612-pitfalls)
  - [6.13 Best Practices](#613-best-practices)
  - [6.14 Hands-on Exercise](#614-hands-on-exercise)
- [M1. Masterclass: Benchmarking Vector Search](#m1-masterclass-benchmarking-vector-search)
  - [M1.1 The ANN-Benchmarks Methodology: Recall@K vs QPS vs Build Cost](#m11-the-ann-benchmarks-methodology-recallk-vs-qps-vs-build-cost)
  - [M1.2 Worked Example: A Recall/Latency Sweep](#m12-worked-example-a-recalllatency-sweep)
  - [M1.3 Benchmark Tools and What Each Answers](#m13-benchmark-tools-and-what-each-answers)
  - [M1.4 Production Checklist](#m14-production-checklist)
- [M2. Masterclass: Hybrid Retrieval and Reranking Pipelines](#m2-masterclass-hybrid-retrieval-and-reranking-pipelines)
  - [M2.1 How a Multi-Stage Retrieval Pipeline Works](#m21-how-a-multi-stage-retrieval-pipeline-works)
  - [M2.2 Worked Example: Fusion in the Starter and in Qdrant](#m22-worked-example-fusion-in-the-starter-and-in-qdrant)
  - [M2.3 Cross-Encoder Reranking](#m23-cross-encoder-reranking)
  - [M2.4 Trade-offs: Which Pipeline to Run](#m24-trade-offs-which-pipeline-to-run)
  - [M2.5 Production Checklist](#m25-production-checklist)
- [M3. Masterclass: Multi-Vector Retrieval and Late Interaction](#m3-masterclass-multi-vector-retrieval-and-late-interaction)
  - [M3.1 How MaxSim Scoring Works](#m31-how-maxsim-scoring-works)
  - [M3.2 Worked Example: Candidate Generation Decides Recall](#m32-worked-example-candidate-generation-decides-recall)
  - [M3.3 Multi-Vectors in Qdrant: Funnel with a Cheap First Stage](#m33-multi-vectors-in-qdrant-funnel-with-a-cheap-first-stage)
  - [M3.4 Trade-offs: Single Vector, Multi-Vector, Cross-Encoder](#m34-trade-offs-single-vector-multi-vector-cross-encoder)
  - [M3.5 Production Checklist](#m35-production-checklist)
- [M4. Masterclass: Matryoshka Embeddings and Funnel Search](#m4-masterclass-matryoshka-embeddings-and-funnel-search)
  - [M4.1 How Truncation and Funnel Search Work](#m41-how-truncation-and-funnel-search-work)
  - [M4.2 Worked Example: Prefix Size vs Shortlist](#m42-worked-example-prefix-size-vs-shortlist)
  - [M4.3 Funnels in Qdrant and pgvector](#m43-funnels-in-qdrant-and-pgvector)
  - [M4.4 Trade-offs: Ways to Shrink the First Stage](#m44-trade-offs-ways-to-shrink-the-first-stage)
  - [M4.5 Production Checklist](#m45-production-checklist)
- [M5. Masterclass: Zero-Downtime Embedding Model Migration](#m5-masterclass-zero-downtime-embedding-model-migration)
  - [M5.1 The Migration State Machine](#m51-the-migration-state-machine)
  - [M5.2 Worked Example: The Pieces in Code](#m52-worked-example-the-pieces-in-code)
  - [M5.3 Engine Commands for Each Step](#m53-engine-commands-for-each-step)
  - [M5.4 Trade-offs: Migration Strategies](#m54-trade-offs-migration-strategies)
  - [M5.5 Production Checklist](#m55-production-checklist)
- [M6. Masterclass: Production Blueprint, a Multi-Tenant Hybrid Retrieval Service](#m6-masterclass-production-blueprint-a-multi-tenant-hybrid-retrieval-service)
  - [M6.1 Architecture](#m61-architecture)
  - [M6.2 The Runnable Blueprint in the Starter](#m62-the-runnable-blueprint-in-the-starter)
  - [M6.3 The Qdrant Service Class](#m63-the-qdrant-service-class)
  - [M6.4 Collection Definition for the Hybrid Version](#m64-collection-definition-for-the-hybrid-version)
  - [M6.5 Trade-offs in the Blueprint](#m65-trade-offs-in-the-blueprint)
  - [M6.6 Production Checklist](#m66-production-checklist)
- [7. Stage 7: Staff Vector Database Engineer Interview Handbook & Cheatsheet](#7-stage-7-staff-vector-database-engineer-interview-handbook--cheatsheet)
  - [7.1 Core Concepts (Q1-Q10)](#71-core-concepts-q1-q10)
  - [7.2 Internals & Performance (Q11-Q30)](#72-internals--performance-q11-q30)
  - [7.3 Architecture & Design (Q31-Q50)](#73-architecture--design-q31-q50)
  - [7.4 Scenario & Debugging Questions (Q51-Q53)](#74-scenario--debugging-questions-q51-q53)
  - [7.5 Staff Cheatsheet](#75-staff-cheatsheet)
- [🧪 Example Projects](#-example-projects)
- [📝 Cheat Sheets](#-cheat-sheets)
- [📚 Resources](#-resources)
- [🤝 Contributing](#-contributing)
- [📄 License](#-license)
- [🙏 Acknowledgments](#-acknowledgments)
- [🌐 Connect with me](#-connect-with-me)
- [☕ Support](#-support)

---

## 1. Stage 1: Vector Foundations, Metrics & First Queries

This stage covers what a vector database stores, where the vectors come from, and how "similar" is measured. You need basic Python and SQL, and Docker if you want to run pgvector or Qdrant locally. At the end you can load embeddings into pgvector and the starter API, choose the right distance metric for a model, and explain why ordinary B-tree indexes cannot answer nearest-neighbour queries.

```mermaid
flowchart LR
    A["Raw content: text, images, code"] --> B["Embedding model"]
    B --> C["Dense vector, e.g. 768 floats"]
    C --> D["Normalise, choose a metric"]
    D --> E[("Vector store: pgvector, Qdrant, starter API")]
    Q["User query"] --> B
    E --> F["Top-k nearest items + payload"]
```

### 1.1 What a Vector Database Is and the Problem It Solves

Relational databases (PostgreSQL, MySQL) and NoSQL stores (MongoDB, Cassandra) are built to query structured scalar data with exact equality (`WHERE id = 101`) or range comparisons (`WHERE age BETWEEN 21 AND 65`). Full-text engines add token matching. None of them can answer "which of these 10 million paragraphs means roughly the same as this question?", because two paragraphs with the same meaning can share no words at all, and two photos of the same dog share no bytes.

A **vector database** stores high-dimensional vectors produced by embedding models, together with an id and a payload (metadata), and answers **k-nearest-neighbour (kNN) queries**: return the `k` stored vectors closest to a query vector under a distance function. Because exact kNN over millions of vectors is too slow, it builds **approximate nearest neighbour (ANN)** indexes that trade a little recall for orders of magnitude less work (Stage 2), and compresses vectors so they fit in memory (Stage 3).

```mermaid
graph TD
    RawData["Unstructured data: text, image, audio, code"] --> Model["Embedding model, e.g. CLIP or text-embedding-3-small"]
    Model --> Vector["Float vector in R^1536"]
    Vector --> VDB[("Vector database: HNSW graph or IVF index")]
    Query["Query: 'golden retriever in snow'"] --> Model
    Model --> QueryVector["Query vector"]
    QueryVector --> VDB
    VDB --> TopK["Top-k semantically nearest items"]
```

| Question you ask | Best tool | Index it uses | Why a vector index does not replace it |
| --- | --- | --- | --- |
| "Order 1042, please" | Relational DB | B-tree on the key | Exact lookups are O(log N) and never approximate. |
| "Docs containing `CVE-2024-3094`" | Full-text engine | Inverted index (BM25) | Rare tokens, ids and codes are matched exactly; embeddings blur them. |
| "Docs that mean the same as this question" | Vector DB | HNSW, IVF, DiskANN | No tokens need to overlap; similarity lives in embedding space. |
| "Both, restricted to tenant 7" | Vector DB with payload filters and sparse vectors | HNSW + payload index + inverted index | Stage 5 combines all three. |

A vector database is therefore three things glued together: a **vector index** for similarity, a **payload store and index** for filters, and the **usual database machinery** (WAL, snapshots, replication, access control) that makes the first two safe to run in production.

### 1.2 Embeddings: Where Vectors Come From

A vector $\mathbf{v} \in \mathbb{R}^D$ is an ordered list of $D$ real numbers. An **embedding model** is a neural network trained (usually with a contrastive objective) so that inputs with related meaning land close together in that space. Individual dimensions have no human meaning; only distances between vectors do.

$$\mathbf{v} = [v_1, v_2, \dots, v_D] \in \mathbb{R}^D$$

| Model family (examples) | Dimensions | Output normalised? | Metric the model expects | Notes |
| --- | --- | --- | --- | --- |
| `all-MiniLM-L6-v2` (sentence-transformers) | 384 | Yes, with the default pipeline | Cosine | Small and fast; good for prototypes. |
| `bge-base-en-v1.5` | 768 | Yes when `normalize_embeddings=True` | Cosine / inner product | Wants an instruction prefix on queries for retrieval. |
| `text-embedding-3-small` (OpenAI) | 1536, shortenable | Yes | Cosine (= inner product on unit vectors) | Supports a `dimensions` parameter (Matryoshka-style truncation). |
| `text-embedding-3-large` (OpenAI) | 3072, shortenable | Yes | Cosine | Above pgvector's 2,000-dim `vector` index limit; index as `halfvec`. |
| CLIP ViT-B/32 | 512 | No (normalise yourself) | Cosine | Text and images share one space. |
| SPLADE, BM25 | vocabulary size (30k+) | n/a | Sparse dot product | Sparse vectors, see 1.8. |

Three rules follow from how embeddings are produced:

1. **One model per vector field.** Vectors from different models (or different versions of one model) live in unrelated spaces. Comparing them returns numbers, not errors, and the results are meaningless.
2. **Use the metric the model was trained with.** A model trained with cosine similarity encodes meaning in angle, not length.
3. **Some models are asymmetric.** E5 and BGE expect a prefix such as `query: ` or an instruction on the query side and none (or `passage: `) on the document side. Forgetting it lowers recall without any visible error.

Truncating a Matryoshka-style embedding (for example keeping the first 512 of 1536 dimensions) keeps most of its quality, but the shortened vector is no longer unit length. Re-normalise it before storing it in a cosine or dot-product collection.

### 1.3 Installation & First Run

You can follow every stage with the starter project alone (pure Python, no database). pgvector and Qdrant are optional and run in Docker.

```bash
# 1. Starter project (Python 3.12 or 3.13)
git clone https://github.com/TheLearningHubOrg/learn-vector-databases.git
cd learn-vector-databases
python -m venv .venv
source .venv/bin/activate            # Windows: .venv\Scripts\activate
pip install -r requirements.txt -r requirements-dev.txt
pytest -q                            # all tests should pass
python -m src.learn_vector_databases.main   # prints a demo for each stage
uvicorn app.main:app --port 8000     # starter API on http://localhost:8000

# 2. PostgreSQL with pgvector
docker run -d --name pgvector -e POSTGRES_PASSWORD=postgres -p 5432:5432 pgvector/pgvector:pg17
export DATABASE_URL=postgresql://postgres:postgres@localhost:5432/postgres
bash sql/run-all.sh                  # runs sql/01..03 and asserts their results

# 3. Qdrant (REST on 6333, gRPC on 6334)
docker run -d --name qdrant -p 6333:6333 -p 6334:6334 \
  -v qdrant_storage:/qdrant/storage qdrant/qdrant
curl -s http://localhost:6333/healthz
```

The starter image is the same service, built by the multi-stage [`Dockerfile`](Dockerfile):

```bash
docker build -t learn-vector-databases .
docker run --rm -p 8000:8000 learn-vector-databases
curl -s http://localhost:8000/health     # {"status":"ok"}
```

| Piece | Where | What it teaches |
| --- | --- | --- |
| `src/learn_vector_databases/vectordb.py` | Pure-Python engine | Metrics, exact kNN, IVF, HNSW, SQ8, PQ, BQ, rescoring. |
| `src/learn_vector_databases/geometry.py` | Exercise helpers | Curse of dimensionality, LSH, memory estimates. |
| `app/main.py` | FastAPI service | Collections, inserts, filtered search over the engine. |
| `sql/01_quickstart.sql` … `03_quantization.sql` | pgvector scripts | The same ideas in SQL, self-checking with `RAISE EXCEPTION`. |
| `tests/` | pytest | Executable claims from the README (recall, degree limits, compression). |

### 1.4 First Queries with pgvector

pgvector adds a `vector(n)` column type, distance operators, and two index types (`hnsw`, `ivfflat`) to PostgreSQL. The first script, [`sql/01_quickstart.sql`](sql/01_quickstart.sql), creates a five-row table of 3-dimensional toy embeddings and queries it.

```sql
CREATE EXTENSION IF NOT EXISTS vector;

CREATE TABLE items (
    id        bigint PRIMARY KEY,
    title     text   NOT NULL,
    category  text   NOT NULL,
    embedding vector(3) NOT NULL
);

INSERT INTO items (id, title, category, embedding) VALUES
    (1, 'cat',    'animal',  '[0.90, 0.10, 0.00]'),
    (2, 'kitten', 'animal',  '[0.85, 0.20, 0.05]'),
    (3, 'tiger',  'animal',  '[0.70, 0.05, 0.30]'),
    (4, 'car',    'vehicle', '[0.05, 0.10, 0.95]'),
    (5, 'truck',  'vehicle', '[0.10, 0.05, 0.90]');

SELECT title,
       round((embedding <-> '[1, 0.1, 0]')::numeric, 4) AS l2,
       round((embedding <=> '[1, 0.1, 0]')::numeric, 4) AS cosine,
       round((embedding <#> '[1, 0.1, 0]')::numeric, 4) AS neg_ip,
       round((embedding <+> '[1, 0.1, 0]')::numeric, 4) AS l1
FROM items
ORDER BY embedding <=> '[1, 0.1, 0]'
LIMIT 3;
```

| Line / API | Role | What happens at runtime |
| :--- | :--- | :--- |
| `CREATE EXTENSION vector` | Loads pgvector into this database | Registers the `vector`, `halfvec`, `sparsevec` types, operators and index access methods. Needed once per database, not per server. |
| `vector(3)` | Fixed-dimension column | Every insert is checked; `[1, 2]` fails with `expected 3 dimensions, not 2`. Storage is `4 * dims + 8` bytes per value. |
| `'[0.90, 0.10, 0.00]'` | Text literal cast to `vector` | Parsed as float4. Drivers can also send arrays or the binary format. |
| `<->` | Euclidean (L2) distance | Lower is closer. Index opclass `vector_l2_ops`. |
| `<=>` | Cosine distance, `1 - cos` | Range 0 to 2. Opclass `vector_cosine_ops`. |
| `<#>` | **Negative** inner product | Negated so that `ORDER BY ... ASC` still means "most similar first". Multiply by -1 to display the real dot product. Opclass `vector_ip_ops`. |
| `<+>` | L1 (Manhattan) distance | Added in 0.7.0. Opclass `vector_l1_ops`. |
| `ORDER BY embedding <=> q LIMIT k` | The kNN query shape | With an index and this exact shape the planner can use an index scan; without `LIMIT` it cannot. |

The same script then proves two behaviours with `DO` blocks: a `WHERE category = 'vehicle'` filter combined with vector ordering returns `car` first, and inserting a 2-dimensional vector raises `data_exception`. Filters and vector ordering compose in plain SQL, which is pgvector's main advantage over a separate vector service (Stage 4).

The equivalent first steps in Qdrant use its REST API. Collections fix the vector size and distance at creation time:

```bash
curl -X PUT http://localhost:6333/collections/items \
  -H 'Content-Type: application/json' \
  -d '{"vectors": {"size": 3, "distance": "Cosine"}}'

curl -X PUT 'http://localhost:6333/collections/items/points?wait=true' \
  -H 'Content-Type: application/json' \
  -d '{"points": [
        {"id": 1, "vector": [0.90, 0.10, 0.00], "payload": {"title": "cat",   "category": "animal"}},
        {"id": 4, "vector": [0.05, 0.10, 0.95], "payload": {"title": "car",   "category": "vehicle"}},
        {"id": 5, "vector": [0.10, 0.05, 0.90], "payload": {"title": "truck", "category": "vehicle"}}
      ]}'

curl -X POST http://localhost:6333/collections/items/points/query \
  -H 'Content-Type: application/json' \
  -d '{"query": [0, 0, 1], "limit": 2, "with_payload": true,
       "filter": {"must": [{"key": "category", "match": {"value": "vehicle"}}]}}'
```

Qdrant returns a **score**, not a distance: for `Cosine` and `Dot` higher is better, for `Euclid` and `Manhattan` lower is better. pgvector always returns a distance where lower is better. Mixing the two conventions is a common bug when code moves between engines.

### 1.5 Distance Metrics: Euclidean, Squared L2, Inner Product, Cosine, Manhattan, Hamming

```mermaid
graph TD
    Metrics["Which metric?"]
    L2["Euclidean L2: straight-line distance"]
    IP["Inner product: angle and length"]
    COS["Cosine: angle only"]
    L1["Manhattan L1: sum of absolute differences"]
    HAM["Hamming: differing bits"]
    Metrics --> L2
    Metrics --> IP
    Metrics --> COS
    Metrics --> L1
    Metrics --> HAM
    COS -->|"vectors are unit length"| IP
    IP -->|"vectors are unit length"| L2
```

| Distance Metric | Formula | Value Range | Properties & Primary Use Cases |
| :--- | :--- | :--- | :--- |
| **Euclidean ($L_2$)** | $d(\mathbf{u}, \mathbf{v}) = \sqrt{\sum_{i=1}^D (u_i - v_i)^2}$ | $[0, \infty)$ | Straight-line distance. Lower is closer. Sensitive to magnitude. Image features, clustering. |
| **Squared Euclidean** | $d^2(\mathbf{u}, \mathbf{v}) = \sum_{i=1}^D (u_i - v_i)^2$ | $[0, \infty)$ | Skips the square root. Same ranking as $L_2$ because $\sqrt{x}$ is monotonic, so engines use it internally. |
| **Inner / Dot Product (IP)** | $\mathbf{u} \cdot \mathbf{v} = \sum_{i=1}^D u_i v_i$ | $(-\infty, \infty)$ | Higher is closer. Mixes angle and length. Recommendation models (matrix factorisation) often rely on length meaning "popularity". |
| **Cosine Distance** | $1 - \frac{\mathbf{u} \cdot \mathbf{v}}{\|\mathbf{u}\|_2 \|\mathbf{v}\|_2}$ | $[0, 2]$ | Pure angle. Scale-invariant. The default for text embeddings. Undefined for the zero vector. |
| **Manhattan ($L_1$)** | $\sum_{i=1}^D \|u_i - v_i\|$ | $[0, \infty)$ | Sum of absolute differences. Less dominated by one large coordinate than $L_2$. |
| **Hamming** | $\sum_{i=1}^D (u_i \oplus v_i)$ | $[0, D]$ | Counts differing bits of binary vectors. Computed as XOR plus population count, a handful of instructions per 64 dimensions. |

The starter implements all of them in one function. Every metric is expressed as a distance where **lower is closer**, so indexes never need to know which direction to sort:

```python
from src.learn_vector_databases.vectordb import DistanceMetric, calculate_distance

a, b = [1.0, 0.0, 1.0], [0.5, 0.5, 1.0]
for metric in DistanceMetric:
    print(f"{metric.value:18} {calculate_distance(a, b, metric):.4f}")
```

```text
EUCLIDEAN          0.7071
SQUARED_EUCLIDEAN  0.5000
COSINE             0.1340
DOT_PRODUCT        -1.5000
MANHATTAN          1.0000
HAMMING            1.0000
```

| Line / API | Role | What happens at runtime |
| :--- | :--- | :--- |
| `DistanceMetric` | `str` enum | Values double as API strings (`"COSINE"`), so FastAPI validates them for free. |
| `len(a) != len(b)` check | Guard | Raises `ValueError("Dimension mismatch: 3 != 2")`, the same class of error pgvector raises. |
| `COSINE` branch | `1 - dot / (norm_a * norm_b)` | Clamps the similarity to `[-1, 1]` to absorb float rounding; returns `1.0` for a zero vector instead of NaN. |
| `DOT_PRODUCT` branch | `-dot(a, b)` | Negated, exactly like pgvector's `<#>`. |
| `HAMMING` branch | Threshold at 0.5, count mismatches | Treats inputs as 0/1 vectors; Stage 3's `BinaryQuantizer` does the packed-bits version. |

How the metric names map across engines:

| Metric | Starter | pgvector operator / opclass | Qdrant | Milvus `metric_type` | Weaviate `distance` |
| --- | --- | --- | --- | --- | --- |
| L2 | `EUCLIDEAN` | `<->` / `vector_l2_ops` | `Euclid` | `L2` | `l2-squared` |
| Inner product | `DOT_PRODUCT` | `<#>` / `vector_ip_ops` | `Dot` | `IP` | `dot` |
| Cosine | `COSINE` | `<=>` / `vector_cosine_ops` | `Cosine` (normalises on insert) | `COSINE` | `cosine` |
| L1 | `MANHATTAN` | `<+>` / `vector_l1_ops` | `Manhattan` | n/a | `manhattan` |
| Hamming | `HAMMING` | `<~>` / `bit_hamming_ops` | via binary quantization | `HAMMING` | `hamming` |

### 1.6 Metric Equivalence & Why L2 Normalisation Matters

A vector is **unit normalised** when its Euclidean norm is 1:

$$\|\mathbf{v}\|_2 = \sqrt{\sum_{i=1}^D v_i^2} = 1 \quad\Longrightarrow\quad \mathbf{v}_{\text{norm}} = \frac{\mathbf{v}}{\|\mathbf{v}\|_2}$$

For two unit vectors the squared L2 distance expands to:

$$\|\mathbf{u} - \mathbf{v}\|^2 = \|\mathbf{u}\|^2 + \|\mathbf{v}\|^2 - 2(\mathbf{u} \cdot \mathbf{v}) = 2 - 2(\mathbf{u} \cdot \mathbf{v}) = 2 \cdot d_{\cos}(\mathbf{u}, \mathbf{v})$$

So on normalised data **cosine distance, inner product and L2 produce the same ranking**. This has three practical consequences:

1. Normalise once at write time and the engine can use the cheapest kernel (an inner product) instead of computing two norms and a division for every candidate. Qdrant does this automatically for `Cosine` collections; the starter API does it in `Collection.prepare`.
2. You can move a cosine workload to an index that only supports L2 (some IVF and PQ implementations) without changing results.
3. If your vectors are **not** normalised, these metrics disagree, and choosing the wrong one changes the results (see 1.10).

The starter test suite checks the identity numerically ([`tests/test_stages.py`](tests/test_stages.py)):

```python
import math, random
from src.learn_vector_databases.vectordb import DistanceMetric, calculate_distance, l2_normalize

rng = random.Random(0)
u = l2_normalize([rng.gauss(0, 1) for _ in range(64)])
v = l2_normalize([rng.gauss(0, 1) for _ in range(64)])

sq_l2 = calculate_distance(u, v, DistanceMetric.SQUARED_EUCLIDEAN)
cos = calculate_distance(u, v, DistanceMetric.COSINE)
assert math.isclose(sq_l2, 2 * cos, rel_tol=1e-9)
print(round(sq_l2, 6), round(2 * cos, 6))
```

And the effect of skipping normalisation, in two dimensions:

```python
from src.learn_vector_databases.vectordb import DistanceMetric, calculate_distance

query = [1.0, 0.0]
short_on_topic = [0.9, 0.1]     # nearly the same direction
long_off_topic = [5.0, 5.0]     # 45 degrees away, but long

for name, doc in [("short_on_topic", short_on_topic), ("long_off_topic", long_off_topic)]:
    print(name,
          "cos", round(calculate_distance(query, doc, DistanceMetric.COSINE), 3),
          "dot", round(calculate_distance(query, doc, DistanceMetric.DOT_PRODUCT), 3))
```

```text
short_on_topic cos 0.006 dot -0.9
long_off_topic cos 0.293 dot -5.0
```

Cosine ranks the on-topic document first; inner product ranks the long one first because its length dominates. For text search that is a bug; for a recommender where length encodes popularity it may be the intent.

In SQL, pgvector 0.7+ has `l2_normalize()`, which you can apply on insert:

```sql
INSERT INTO items (id, title, category, embedding)
VALUES (6, 'lion', 'animal', l2_normalize('[3, 0.4, 1.2]'::vector));
```

### 1.7 The Curse of Dimensionality & Why B-Trees and k-d Trees Fail

Engineers often ask why vector coordinates cannot be indexed with B-trees, k-d trees or R-trees. In two or three dimensions they can: a k-d tree splits space into boxes and a nearest-neighbour query prunes every box that is farther away than the best match so far, giving roughly $O(\log N)$ work.

As $D$ grows, high-dimensional geometry stops cooperating:

1. **Volume concentrates in the shell.** Almost all of the volume of a high-dimensional ball lies in a thin shell near its surface, so random points are almost all "far" from the centre and from each other.
2. **Distances concentrate.** The gap between the nearest and the farthest neighbour shrinks relative to the nearest distance:
   $$\lim_{D \rightarrow \infty} \frac{\text{dist}_{\max} - \text{dist}_{\min}}{\text{dist}_{\min}} \rightarrow 0$$
3. **Pruning stops working.** When every box is about as close as every other, a k-d tree or R-tree query must open nearly all branches and degrades to an $O(N)$ scan with extra pointer chasing on top.

`geometry.distance_contrast` measures point 2 on uniform random data (500 points, one query):

```python
from src.learn_vector_databases.geometry import distance_contrast

for d in (2, 8, 32, 128, 512, 1536):
    print(f"D={d:5}  (max - min) / min = {distance_contrast(d):.3f}")
```

```text
D=    2  (max - min) / min = 20.134
D=    8  (max - min) / min = 2.571
D=   32  (max - min) / min = 0.805
D=  128  (max - min) / min = 0.467
D=  512  (max - min) / min = 0.154
D= 1536  (max - min) / min = 0.082
```

At 1,536 dimensions the farthest random point is only about 8% farther than the nearest. Real embeddings are not uniform noise (they lie near a much lower-dimensional manifold, which is why ANN works at all), but tree pruning still collapses. Vector databases therefore use **proximity graphs (HNSW, Vamana)**, **clustering (IVF)** and **compression (PQ, BQ)** instead of space-partitioning trees.

```mermaid
flowchart TD
    Low["D = 2 or 3"] --> KD["k-d tree prunes most boxes"]
    KD --> Fast["About log N node visits"]
    High["D = 768 or more"] --> Conc["Distances concentrate"]
    Conc --> Overlap["Every box overlaps the search ball"]
    Overlap --> Scan["Tree visits almost every leaf: O(N)"]
    Scan --> ANN["Use graphs, clusters, quantization instead"]
```

### 1.8 Dense, Sparse & Hybrid Representations

Vector engines handle two complementary formats:

| Property | Dense vectors (e.g. OpenAI, BGE) | Sparse vectors (e.g. BM25, SPLADE) |
| :--- | :--- | :--- |
| **Dimensionality** | Fixed, typically 256 to 3,072 | Vocabulary-sized, 30,000 to 100,000+ |
| **Non-zero values** | Essentially all of them | Typically 50 to 200 per document |
| **What it captures** | Meaning, paraphrase, synonyms | Exact tokens, ids, acronyms, rare terms |
| **Storage** | Contiguous float arrays | Posting lists: `term_id -> [(doc_id, weight)]` |
| **Index** | HNSW, IVF, PQ | Inverted index, WAND / block-max pruning |
| **pgvector type** | `vector`, `halfvec` | `sparsevec` (0.7+) |

A sparse vector is stored as `{dimension: weight}`. Its dot product only touches dimensions present in both vectors, so cost depends on the number of non-zeros, not the vocabulary size:

```python
from src.learn_vector_databases.vectordb import sparse_dot

doc = {1042: 0.8, 77: 0.3, 9001: 1.2}      # token ids -> weights
query = {9001: 1.0, 5: 0.4}
print(sparse_dot(query, doc))               # 1.2: only token 9001 overlaps
```

```sql
-- pgvector sparse literal: {index:value,...}/dimensions (indices start at 1)
SELECT '{1:0.8,3:1.2}/5'::sparsevec <#> '{3:1.0,5:0.4}/5'::sparsevec AS neg_ip;   -- -1.2
```

Hybrid search keeps both representations for each document and fuses their result lists, usually with Reciprocal Rank Fusion. Stage 5 builds it; for now the point is that dense vectors miss exact identifiers (`CVE-2024-3094`, SKU numbers, function names) and sparse vectors miss paraphrases, so production retrieval often needs both.

### 1.9 Line-by-Line Breakdown of the Starter API

[`app/main.py`](app/main.py) exposes the pure-Python engine over HTTP. It is deliberately close to the shape of a real vector database API: collections with a fixed dimension and metric, batch inserts with payloads, and top-k search with a filter.

```python
class CollectionConfig(BaseModel):
    dimensions: int = Field(gt=0, le=4096)
    metric: DistanceMetric = DistanceMetric.COSINE
    index: Literal["flat", "hnsw"] = "hnsw"
    m: int = Field(default=16, ge=2, le=64)
    ef_construction: int = Field(default=64, ge=8, le=512)

class Collection:
    def __init__(self, config: CollectionConfig) -> None:
        self.config = config
        self.lock = threading.Lock()
        if config.index == "flat":
            self.index = ExactKNNIndex(metric=config.metric)
        else:
            self.index = HNSWIndex(dimensions=config.dimensions, metric=config.metric,
                                   M=config.m, ef_construction=config.ef_construction)

    def prepare(self, vector: List[float]) -> List[float]:
        if len(vector) != self.config.dimensions:
            raise HTTPException(422, f"expected {self.config.dimensions} dimensions, got {len(vector)}")
        return l2_normalize(vector) if self.config.metric == DistanceMetric.COSINE else vector
```

| Line / API | Role | What happens at runtime |
| :--- | :--- | :--- |
| `dimensions: int = Field(gt=0, le=4096)` | Schema validation | A collection's dimension is fixed forever, like `vector(n)` or Qdrant's `size`. |
| `index: Literal["flat", "hnsw"]` | Index choice | `flat` is exact kNN (Stage 2.1); `hnsw` is the graph from Stage 2.3. |
| `threading.Lock()` | Write serialisation | HNSW inserts mutate shared neighbour lists; real engines use finer-grained locks or immutable segments (Stage 6). |
| `prepare()` | Write-time check and normalisation | Wrong dimensions return HTTP 422; cosine collections store unit vectors so ranking matches 1.6. |
| `PUT /collections/{name}/points` | Batch insert | Validates the whole batch (duplicate ids, existing ids, dimensions) before inserting anything, so a bad point cannot leave half a batch behind. |
| `POST /collections/{name}/search` | Top-k query | Passes a payload predicate into the index, so filtering happens during traversal, not after (Stage 5). |
| `GET /collections/{name}` | Introspection | Reports a memory estimate: `points * dims * 4` bytes for vectors and `points * 2 * m * 4` for the layer-0 graph (Stage 3.1). |

Try it:

```bash
uvicorn app.main:app --port 8000 &

curl -s -X PUT localhost:8000/collections/docs -H 'Content-Type: application/json' \
  -d '{"dimensions": 3, "metric": "COSINE", "index": "hnsw"}'

curl -s -X PUT localhost:8000/collections/docs/points -H 'Content-Type: application/json' \
  -d '{"points": [
        {"id": "cat",    "vector": [1.0, 0.1, 0.0], "payload": {"lang": "en"}},
        {"id": "kitten", "vector": [0.9, 0.2, 0.0], "payload": {"lang": "fr"}},
        {"id": "car",    "vector": [0.0, 0.1, 1.0], "payload": {"lang": "en"}}]}'

curl -s -X POST localhost:8000/collections/docs/search -H 'Content-Type: application/json' \
  -d '{"vector": [1.0, 0.15, 0.0], "k": 2, "filter": {"lang": "en"}}'
# [{"id":"cat",...},{"id":"car",...}]  the filter skips "kitten" even though it is closer
```

```mermaid
sequenceDiagram
    participant C as Client
    participant API as FastAPI app
    participant Col as Collection
    participant Idx as HNSWIndex
    C->>API: POST /collections/docs/search
    API->>Col: prepare(vector)
    Col-->>API: unit vector or 422
    API->>Idx: search(query, k, ef_search, filter_predicate)
    Idx-->>API: list of (VectorItem, distance)
    API-->>C: JSON hits with id, distance, payload
```

### 1.10 Pitfalls

| Pitfall | Symptom | Fix |
| --- | --- | --- |
| Forgetting `CREATE EXTENSION vector` in a new database | `ERROR: type "vector" does not exist` | Run `CREATE EXTENSION IF NOT EXISTS vector;` in every database (migrations, test databases too). |
| Inserting a vector with the wrong length | pgvector: `ERROR: expected 3 dimensions, not 2`; Qdrant: `Wrong input: Vector dimension error: expected dim: 3, got 2`; starter API: HTTP 422 | Pin the model and dimension in config; validate at the edge; truncate Matryoshka vectors on purpose, not by accident. |
| Comparing vectors from two different models | No error, results look random | One model per vector field; store `model` and `model_version` in the payload; re-embed everything when the model changes. |
| Reading `<#>` as a similarity | Scores are negative and "bigger is worse" | `<#>` is the negative inner product; display `-(a <#> b)` or `1 - (a <=> b)` for cosine similarity. |
| Using inner product on unnormalised text embeddings | Long documents win every query (see 1.6) | Normalise on write, or use cosine. |
| Zero vectors in a cosine collection | pgvector returns `NaN` distance; rows sort unpredictably | Reject empty or zero embeddings at ingestion (an empty string often embeds to a near-constant vector). |
| Missing query prefix on asymmetric models (E5, BGE) | Recall drops by several points with no error | Apply the model's documented query and passage prefixes in one shared embedding function. |
| Sorting Qdrant scores ascending | Worst matches first for `Cosine`/`Dot` | Qdrant returns scores (higher is better for Cosine/Dot); pgvector returns distances (lower is better). |
| Re-normalising after truncation is skipped | Cosine collection works, dot collection ranks wrongly | Call `l2_normalize` after cutting dimensions. |

### 1.11 Best Practices

- **Record the embedding model with the data**: a `model` field in the payload lets you find and re-embed stale vectors after an upgrade.
- **Normalise at write time when the model expects cosine**: it lets the engine use the cheaper inner-product kernel and makes L2, IP and cosine agree.
- **Fix the dimension in the schema**: `vector(768)` or a collection `size` catches pipeline bugs at insert time rather than at query time.
- **Keep the embedding call in one function used by both ingestion and queries**: prefixes, truncation and normalisation then cannot drift apart.
- **Test with tiny, hand-checkable vectors first**: three-dimensional examples like `sql/01_quickstart.sql` make metric and sort-order bugs obvious.
- **Treat distances as relative, not absolute**: a cosine distance of 0.3 means different things for different models; tune thresholds per model with labelled examples.

### 1.12 Hands-on Exercise

1. Run `python -c "from src.learn_vector_databases.geometry import distance_contrast; print([round(distance_contrast(d), 3) for d in (2, 32, 512)])"`. **Expected:** a strictly decreasing list, roughly `[20.134, 0.805, 0.154]`.
2. In psql, add a sixth row `'lion'` with an unnormalised vector `[3, 0.4, 1.2]`, then run the `ORDER BY embedding <#> '[1, 0.1, 0]'` and `ORDER BY embedding <=> '[1, 0.1, 0]'` queries. **Expected:** `lion` ranks first by inner product (its length is about 3.3) but only third by cosine. Then run `UPDATE items SET embedding = l2_normalize(embedding);` and repeat both queries. **Expected:** the two orders are now identical.
3. Through the starter API, create a `DOT_PRODUCT` collection and a `COSINE` collection, insert the 2-D vectors from 1.6 into both, and query `[1, 0]`. **Expected:** `long_off_topic` wins in the dot collection, `short_on_topic` in the cosine one.

Solutions: `distance_contrast` in [`src/learn_vector_databases/geometry.py`](src/learn_vector_databases/geometry.py) with its test in [`tests/test_geometry.py`](tests/test_geometry.py); the normalisation identity in [`tests/test_stages.py`](tests/test_stages.py); the SQL patterns in [`sql/01_quickstart.sql`](sql/01_quickstart.sql).

[Back to top ⤴️](#-table-of-contents)

---

## 2. Stage 2: Approximate Nearest Neighbor Indexing

This stage explains how vector indexes avoid scanning every vector: clustering (IVF), proximity graphs (HNSW, Vamana), hashing (LSH) and trees (Annoy). It assumes Stage 1's metrics. Afterwards you can choose an index for a workload, set `m`, `ef_construction`, `ef_search`, `lists` and `probes` from evidence, and prove the result with a recall measurement instead of trusting defaults.

```mermaid
flowchart TD
    Q["Query vector"] --> Choice{"Index type"}
    Choice -->|"flat"| Flat["Scan all N vectors: exact"]
    Choice -->|"IVF"| IVF["Score nlist centroids, scan nprobe lists"]
    Choice -->|"HNSW"| HNSW["Greedy descent, beam search on layer 0"]
    Choice -->|"DiskANN"| Disk["Compressed routing in RAM, full vectors on SSD"]
    Flat --> R["Top-k"]
    IVF --> R
    HNSW --> R
    Disk --> R
    R --> Rec["Compare with exact top-k: recall@k"]
```

### 2.1 Exact kNN vs Approximate Nearest Neighbor & Recall@K

Exact (flat, brute-force) kNN computes the distance from the query to every stored vector and keeps the `k` smallest. It costs $O(N \cdot D)$ per query, needs no build step and always returns the true answer. ANN indexes do much less work per query but may miss some true neighbours. The standard way to express that loss is **recall@k**: the fraction of the true top-k that the ANN search returned.

$$\text{Recall@K} = \frac{1}{|Q|} \sum_{q \in Q} \frac{|A_q \cap G_q|}{K}$$

```mermaid
graph LR
    subgraph ExactPros["Exact kNN (flat)"]
        E1["100% recall by definition"]
        E2["No build or training step"]
        E3["O(N x D) work per query"]
    end
    subgraph ANNPros["ANN (HNSW / IVF)"]
        A1["Typically 95-99% recall when tuned"]
        A2["Build or training step required"]
        A3["Visits a small fraction of N"]
    end
    ExactPros -->|"N grows past ~100k"| ANNPros
```

The starter's flat index and recall function are short enough to read in full:

```python
import heapq
from src.learn_vector_databases.vectordb import calculate_distance

class ExactKNNIndex:
    def __init__(self, metric):
        self.metric = metric
        self.items = {}

    def add(self, item):
        self.items[item.id] = item

    def search(self, query, k=5, filter_predicate=None):
        scored = (
            (item, calculate_distance(query, item.vector, self.metric))
            for item in self.items.values()
            if filter_predicate is None or filter_predicate(item.payload)
        )
        return heapq.nsmallest(k, scored, key=lambda pair: pair[1])

def recall_at_k(approximate, exact, k):
    truth = {item.id for item, _ in exact[:k]}
    found = {item.id for item, _ in approximate[:k]}
    return len(truth & found) / len(truth) if truth else 1.0
```

| Line / API | Role | What happens at runtime |
| :--- | :--- | :--- |
| generator `scored` | Lazy scoring | Distances are computed one at a time; nothing is materialised for all N. |
| `heapq.nsmallest(k, ...)` | Bounded heap | Keeps a heap of size k: $O(N \log k)$ instead of sorting all N. Engines do the same with SIMD distance kernels. |
| `filter_predicate` | Pre-filter | For flat search, filtering first is always correct and cheap. Stage 5 shows why graphs are harder. |
| `recall_at_k` | Quality metric | Set intersection of ids. It ignores order inside the top-k; use nDCG or MRR when order matters. |

When exact search is the right choice:

- The collection is small. A flat scan of 50,000 768-dimensional float32 vectors reads about 150 MB of memory; with SIMD that is low tens of milliseconds on one core, often fine for internal tools.
- Each query only touches a small subset, for example one tenant's 2,000 documents behind a filter. Qdrant switches to a full scan automatically when the filtered set is below `full_scan_threshold`; pgvector does the same when the planner estimates a sequential scan is cheaper.
- You need ground truth to measure an ANN index (always).
- Recall errors are unacceptable (deduplication audits, legal discovery) and latency budgets allow it.

### 2.2 Inverted File (IVF) Indexes & Voronoi Cell Partitioning

An **IVF** index runs k-means over the data to find `nlist` centroids, then stores each vector in the posting list of its nearest centroid. Each list is a Voronoi cell. A query scores all centroids, picks the `nprobe` nearest, and scans only their lists.

```mermaid
flowchart TD
    Build["Build: run k-means on a sample"] --> Centroids["nlist centroids, e.g. 1024"]
    Centroids --> Lists["Assign every vector to its nearest centroid list"]
    Query["Query q"] --> Probe["Distance from q to all nlist centroids"]
    Probe --> Top["Keep nprobe closest centroids, e.g. 16"]
    Top --> Scan["Scan only those posting lists"]
    Lists --> Scan
    Scan --> Result["Top-k"]
```

The starter's `IVFIndex.search` is the whole algorithm:

```python
def search(self, query, k=5, nprobe=None, filter_predicate=None):
    probes = max(1, min(nprobe or self.nprobe, len(self.centroids)))
    ranked = sorted(range(len(self.centroids)),
                    key=lambda c: calculate_distance(query, self.centroids[c], self.metric))
    scored = (
        (item, calculate_distance(query, item.vector, self.metric))
        for c in ranked[:probes]
        for item in self.inverted_lists.get(c, [])
        if filter_predicate is None or filter_predicate(item.payload)
    )
    return heapq.nsmallest(k, scored, key=lambda pair: pair[1])
```

Work per query is roughly $nlist + nprobe \cdot N / nlist$ distance computations. With $N = 10^6$, $nlist = 1000$ and $nprobe = 10$ that is about 11,000 distances instead of a million.

| Parameter | Rule of thumb | Effect of raising it |
| --- | --- | --- |
| `nlist` (FAISS), `lists` (pgvector) | pgvector docs suggest `rows / 1000` up to 1M rows and `sqrt(rows)` above; FAISS users often pick $4\sqrt{N}$ to $16\sqrt{N}$ | Smaller lists, faster scans per probe, but more centroids to score and more boundary misses at a fixed `nprobe`. |
| `nprobe` (FAISS), `ivfflat.probes` (pgvector) | Start near `sqrt(lists)`; typical range 8 to 64 | Higher recall, linearly more work. `nprobe = nlist` is an exact search. |

Measured on the starter (3,000 clustered 32-dimensional vectors, `nlist = 55`, recall@10 over 50 queries):

| `nprobe` | 1 | 2 | 4 | 8 | 16 |
| --- | --- | --- | --- | --- | --- |
| recall@10 | 0.626 | 0.886 | 0.998 | 1.000 | 1.000 |

The cliff between `nprobe = 1` and `2` is the **boundary effect**: a query near the edge of a Voronoi cell has true neighbours in the next cell, which a single probe never opens.

In pgvector, IVFFlat is trained from the rows present when the index is built, so build it **after** loading data:

```sql
CREATE INDEX docs_ivf ON docs USING ivfflat (embedding vector_cosine_ops) WITH (lists = 70);
SET ivfflat.probes = 7;          -- per session or per transaction (SET LOCAL)
SELECT id FROM docs ORDER BY embedding <=> $1 LIMIT 5;
```

Creating it on an empty or tiny table prints `NOTICE: ivfflat index created with little data` and later queries have poor recall, because the centroids came from almost nothing. If the data distribution drifts (new topics, a new tenant), rebuild with `REINDEX INDEX CONCURRENTLY`.

### 2.3 Hierarchical Navigable Small World (HNSW) Graphs

**HNSW** (Malkov and Yashunin, 2016) is the default in-memory index of almost every vector database: pgvector, Qdrant, Weaviate, Milvus, Elasticsearch/OpenSearch, Redis and Chroma all ship it. It combines two ideas:

- A **navigable small-world graph**: each vector is a node linked to a few near neighbours plus some longer links, so greedy "move to the neighbour closest to the query" reaches the target region in few hops.
- A **skip-list hierarchy**: every node lives on layer 0, and a geometrically shrinking random subset is promoted to layers 1, 2, 3… Upper layers are sparse express lanes; lower layers refine.

```mermaid
graph TD
    subgraph Layer2["Layer 2: a few nodes, long links"]
        L2_A["A"] === L2_F["F"]
    end
    subgraph Layer1["Layer 1: more nodes"]
        L1_A["A"] --- L1_C["C"]
        L1_C --- L1_F["F"]
        L1_F --- L1_I["I"]
    end
    subgraph Layer0["Layer 0: every node, short links"]
        L0_A["A"] --- L0_B["B"]
        L0_B --- L0_C["C"]
        L0_C --- L0_D["D"]
        L0_D --- L0_E["E"]
        L0_E --- L0_F["F"]
        L0_F --- L0_G["G"]
        L0_G --- L0_H["H"]
        L0_H --- L0_I["I"]
    end
    Query["Query q"] -.->|"enter at the top"| L2_A
    L2_A ==>|"greedy step"| L2_F
    L2_F -.->|"drop down"| L1_F
    L1_F ==>|"greedy step"| L1_I
    L1_I -.->|"drop down"| L0_I
    L0_I ==>|"beam search with ef candidates"| L0_H
```

**Layer assignment.** Each new node draws its top layer as

$$\ell = \lfloor -\ln(U) \cdot m_L \rfloor, \quad U \sim \text{Uniform}(0, 1], \quad m_L = \frac{1}{\ln M}$$

so $P(\ell \ge l) = M^{-l}$. With $M = 16$, about 1 in 16 nodes reaches layer 1, 1 in 256 reaches layer 2, and a million-node graph has around five layers. The starter's `_random_level` is exactly this formula, capped at 16 layers.

**Search, layer by layer:**

1. Start at the global entry point (the node with the highest layer).
2. On each upper layer, walk greedily: move to any neighbour closer to the query, stop at a local minimum. This is a beam of width 1.
3. Drop to the next layer, starting from that local minimum.
4. On layer 0, run a **beam search** that keeps the best `ef_search` candidates, expanding the closest unexpanded candidate until none can improve the result set. Return the best `k`.

Search cost grows roughly logarithmically with N in practice, and linearly with `ef_search` and `M`.

### 2.4 HNSW Insert & Search, Step by Step in Code

Insertion uses the same search to find neighbours for the new node, layer by layer, then connects it. The core routine is the layer-0 beam search, `_search_layer` in [`vectordb.py`](src/learn_vector_databases/vectordb.py):

```python
def _search_layer(self, query, entry_points, ef, level, accept=None):
    visited = set(entry_points)
    candidates = []            # min-heap: (distance, node) still to expand
    results = []               # max-heap via negation: best ef accepted nodes
    for ep in entry_points:
        d = self._distance(query, ep)
        heapq.heappush(candidates, (d, ep))
        if accept is None or accept(ep):
            heapq.heappush(results, (-d, ep))

    while candidates:
        dist, node = heapq.heappop(candidates)
        if len(results) >= ef and dist > -results[0][0]:
            break                                  # nothing left can improve the results
        for neighbour in self.graph.get(level, {}).get(node, []):
            if neighbour in visited:
                continue
            visited.add(neighbour)
            d = self._distance(query, neighbour)
            if len(results) < ef or d < -results[0][0]:
                heapq.heappush(candidates, (d, neighbour))
                if accept is None or accept(neighbour):
                    heapq.heappush(results, (-d, neighbour))
                    if len(results) > ef:
                        heapq.heappop(results)     # drop the current worst
    return sorted((-neg, n) for neg, n in results)
```

| Line / API | Role | What happens at runtime |
| :--- | :--- | :--- |
| `visited` set | Avoid revisits | Each node's distance is computed at most once per query. Engines use a reusable bitset or generation-counter array instead of a hash set. |
| `candidates` min-heap | Frontier | Always expands the closest unexpanded node next (best-first search). |
| `results` max-heap of size `ef` | Current best | `-results[0][0]` is the worst distance still kept; it is the stopping bound. |
| `break` condition | Termination | Once the closest frontier node is worse than the worst result, no expansion can help. Larger `ef` delays this, exploring more. |
| `accept(neighbour)` | Filter hook | A node that fails the filter is still pushed to `candidates`, so it acts as a bridge but never takes a result slot (Stage 5.2). |

Choosing which neighbours to link uses the **diversity heuristic** from the paper. A naive index links the M closest candidates; if they are all in one tight cluster, the new node has M edges pointing the same way. The heuristic keeps a candidate only if it is closer to the new node than to every neighbour already kept:

```python
def _select_neighbours(self, candidates, m):
    selected, skipped = [], []
    for dist, cand in candidates:                     # sorted by distance to the new node
        if len(selected) >= m:
            break
        cand_vec = self.items[cand].vector
        if all(dist < self._distance(cand_vec, kept) for kept in selected):
            selected.append(cand)                     # covers a new direction
        else:
            skipped.append(cand)                      # redundant with a kept neighbour
    for cand in skipped:                              # fill up so sparse regions get m edges
        if len(selected) >= m:
            break
        selected.append(cand)
    return selected
```

```mermaid
sequenceDiagram
    participant New as New node x
    participant Up as Upper layers
    participant L as Current layer
    participant Nb as Chosen neighbours
    New->>New: level = floor(-ln(U) * mL)
    New->>Up: greedy descent from entry point to layer level+1
    Up-->>New: closest node found so far
    loop each layer from min(level, top) down to 0
        New->>L: beam search with ef_construction
        L-->>New: ef closest candidates
        New->>New: diversity heuristic keeps M
        New->>Nb: add edges both ways
        Nb->>Nb: prune to M (2M on layer 0) with the same heuristic
    end
    New->>New: becomes entry point if level > top
```

The starter's tests check the invariants that real engines also maintain: no node exceeds `M` links on upper layers or `M0 = 2M` on layer 0 (`test_hnsw_degree_never_exceeds_limits`), and recall on random data stays high (`test_hnsw_recall_is_high_on_random_data`).

### 2.5 HNSW Hyperparameters: `M`, `ef_construction` and `ef_search`

| Hyperparameter | Scope | Typical default | Effect and trade-off |
| :--- | :--- | :---: | :--- |
| **`M`** (`m` in pgvector and Qdrant) | Build | 16 | Max links per node on upper layers; layer 0 allows `2M`. Higher `M` (32, 48, 64) helps high-dimensional or hard datasets reach high recall, but graph memory and build time grow linearly. |
| **`ef_construction`** (`ef_construct` in Qdrant) | Build | 64 (pgvector), 100 (Qdrant) | Beam width while inserting. Higher builds a better-connected graph (higher recall ceiling) at slower ingestion. Must be at least `2 * m` in pgvector. |
| **`ef_search`** (`hnsw.ef_search`, `hnsw_ef`, `ef`) | Query | 40 (pgvector) | Beam width at query time. Must be at least `k`. Tunable per query: raise it for recall, lower it for throughput. |

Measured on the starter (3,000 clustered 32-dim vectors, `M = 16`, `ef_construction = 64`, recall@10 over 50 queries; pure Python, so only the relative latencies matter):

| `ef_search` | 10 | 20 | 40 | 80 | 160 | exact scan |
| --- | --- | --- | --- | --- | --- | --- |
| recall@10 | 0.972 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 |
| ms per query | 6.4 | 8.2 | 8.8 | 9.3 | 15.3 | 107.1 |

Easy, clustered data saturates early. On real 768- or 1536-dimensional embeddings with millions of points, curves are flatter: going from 95% to 99% recall often costs 2-4x the query time. Always measure on a sample of your own data and queries.

Setting the same parameters in three engines:

```sql
-- pgvector
CREATE INDEX docs_hnsw ON docs USING hnsw (embedding vector_cosine_ops)
    WITH (m = 16, ef_construction = 64);
SET maintenance_work_mem = '2GB';            -- build the graph in memory; otherwise it spills and slows down
SET max_parallel_maintenance_workers = 4;    -- parallel builds (pgvector 0.6+)
SET hnsw.ef_search = 100;                    -- per session; use SET LOCAL inside a transaction
```

```bash
# Qdrant: collection-level defaults, per-query override
curl -X PUT http://localhost:6333/collections/docs -H 'Content-Type: application/json' \
  -d '{"vectors": {"size": 768, "distance": "Cosine"},
       "hnsw_config": {"m": 16, "ef_construct": 128}}'

curl -X POST http://localhost:6333/collections/docs/points/query -H 'Content-Type: application/json' \
  -d '{"query": [0.1, 0.2, 0.3], "limit": 10, "params": {"hnsw_ef": 128}}'
```

```python
# Milvus (pymilvus MilvusClient)
from pymilvus import MilvusClient

client = MilvusClient("http://localhost:19530")
index_params = client.prepare_index_params()
index_params.add_index(field_name="embedding", index_type="HNSW", metric_type="COSINE",
                       params={"M": 16, "efConstruction": 128})
client.create_index("docs", index_params)
hits = client.search("docs", data=[[0.1] * 768], limit=10, search_params={"params": {"ef": 128}})
```

A practical tuning loop: fix `M = 16` and `ef_construction = 128`, sweep `ef_search` until recall@10 meets the target on held-out queries, and only raise `M` if recall plateaus below the target at high `ef_search`.

### 2.6 Deletes, Updates & Graph Maintenance

Graph indexes are append-friendly and delete-hostile. Removing a node breaks the paths that ran through it, and repairing every incoming edge immediately is expensive. Engines therefore use **tombstones**: a deleted node is marked in a bitmap, skipped in results, but can still be traversed until a background job rebuilds or repairs the affected segment.

| Engine | Delete behaviour | Update behaviour | Maintenance you must plan for |
| --- | --- | --- | --- |
| pgvector | `DELETE` marks heap tuples dead; index entries stay until `VACUUM` removes them and repairs neighbour lists | `UPDATE` writes a new tuple version and a new index entry | `VACUUM` on HNSW indexes is slow for heavily updated tables; `REINDEX CONCURRENTLY` is often faster after bulk churn. |
| Qdrant | Points marked deleted in the segment; optimizers vacuum segments once `deleted_threshold` is crossed | Upsert = delete + insert into the mutable segment | Watch `optimizer_status` and segment counts after large deletes. |
| Milvus | Delete records in the log; compaction drops them | Upsert = delete + insert | Compaction must keep up, or queries filter many dead rows. |
| Starter | No delete; `add` rejects duplicate ids | Not supported | Mirrors the core limitation: HNSW has no in-place update. |

The starter makes the "no in-place update" rule explicit:

```python
from src.learn_vector_databases.vectordb import HNSWIndex, VectorItem

idx = HNSWIndex(dimensions=2)
idx.add(VectorItem("a", [0.0, 1.0]))
idx.add(VectorItem("a", [1.0, 0.0]))
# ValueError: Duplicate id 'a'; delete it first (HNSW has no in-place update)
```

Graph quality also degrades if `M` is too small for multi-modal data: the graph can split into components that greedy search cannot cross, and queries that enter on the wrong side silently miss their neighbours. Keep `M >= 8` (16 is the common default) and monitor recall over time, not only at launch.

### 2.7 Tree-Based Indexes (Annoy) & Locality-Sensitive Hashing (LSH)

**Annoy** (Spotify) builds a forest of random-projection trees: each node splits space with a hyperplane between two sampled points. Queries descend every tree with a priority queue and scan the union of candidate leaves.

- Strength: an index is one read-only file that can be memory-mapped, so many processes share it through the page cache.
- Weakness: static. Adding vectors means rebuilding the forest. Annoy is now mostly found in older recommendation systems; HNSW libraries (hnswlib, FAISS) replaced it for new work.

**LSH for cosine (random hyperplanes, also called SimHash)** hashes each vector to a bit signature: bit `i` is 1 if the vector is on the positive side of random hyperplane `i`. Two vectors at angle $\theta$ agree on each bit with probability $1 - \theta / \pi$, so similar vectors tend to land in the same bucket. Using several hash tables raises recall.

```python
from src.learn_vector_databases.geometry import RandomHyperplaneLSH

lsh = RandomHyperplaneLSH(dimensions=3, bits=8, seed=1)
lsh.add("cat", [0.9, 0.1, 0.0])
lsh.add("kitten", [0.85, 0.2, 0.05])
lsh.add("car", [0.05, 0.1, 0.95])
print(lsh.candidates([1.0, 0.1, 0.0]))     # likely ['cat', 'kitten']; 'car' sits in another bucket
print(RandomHyperplaneLSH.collision_probability(0.2))   # per-bit agreement for a 0.2 rad angle: ~0.936
```

| Index family | Build | Inserts | Memory | Recall/latency on dense embeddings | Where it still wins |
| --- | --- | --- | --- | --- | --- |
| LSH | Instant, data-independent | Trivial | Many tables needed for high recall | Behind HNSW and IVF | Near-duplicate detection, MinHash for Jaccard on sets, streaming dedup |
| Annoy | Moderate | Rebuild | Low, mmap-friendly | Behind HNSW | Read-only shared indexes |
| IVF | k-means training | Append to lists | Low | Good with enough probes; pairs with PQ | Very large, memory-constrained corpora |
| HNSW | Slowest per vector | Incremental | Highest (graph links) | Best in-memory trade-off | Default for most workloads |

### 2.8 DiskANN & the Vamana Graph

HNSW keeps the graph and the vectors in RAM. A billion 768-dimensional float32 vectors are about 3 TB before the graph, which is a lot of memory to rent. **DiskANN** (Subramanya et al., Microsoft Research, NeurIPS 2019) serves billion-scale search from one machine with an NVMe SSD:

```mermaid
graph TD
    subgraph DiskANNDiag["DiskANN memory layout"]
        RAM["RAM: tens of GB"] --> PQ["PQ-compressed copy of every vector"]
        RAM --> EntryPoint["Entry node(s)"]
        SSD["NVMe SSD: TBs"] --> VamanaGraph["Vamana graph: neighbour list + full vector per node"]
    end
    Query["Query q"] --> RouteRAM["Route with PQ distances in RAM"]
    RouteRAM --> FetchSSD["Batch async reads of candidate nodes"]
    FetchSSD --> VamanaGraph
    VamanaGraph --> FinalTopK["Re-rank with full vectors, return top-k"]
```

What makes Vamana different from HNSW:

1. **One flat layer.** No hierarchy; a well-chosen entry point (the medoid) plus long-range edges do the job of upper layers.
2. **The α parameter.** During pruning, a candidate is dropped only if an already-kept neighbour is closer to it by a factor of α (typically 1.2). α > 1 keeps more long edges, so searches cross the dataset in fewer hops, which means fewer SSD reads.
3. **Sector-aligned layout.** Each node's neighbour list and full vector are stored together in a 4 KB-aligned block, so one random read fetches both.

DiskANN-style indexes are available in Milvus (`DISKANN` index type), in Azure database services, and in PostgreSQL through the `pgvectorscale` extension (StreamingDiskANN). Expect a few milliseconds per query instead of sub-millisecond, at a fraction of the RAM.

### 2.9 Google ScaNN & Anisotropic Vector Quantization

Classic quantization minimises reconstruction error $\|\mathbf{x} - \tilde{\mathbf{x}}\|^2$. For **maximum inner product search** what matters is ranking error, and errors parallel to the data vector change inner products much more than perpendicular ones. **ScaNN** (Guo et al., ICML 2020) uses an **anisotropic loss** that weights those components differently:

$$\mathcal{L}(\mathbf{x}, \tilde{\mathbf{x}}) = h_{\parallel} \|\mathbf{r}_{\parallel}(\mathbf{x}, \tilde{\mathbf{x}})\|^2 + h_{\perp} \|\mathbf{r}_{\perp}(\mathbf{x}, \tilde{\mathbf{x}})\|^2, \quad h_{\parallel} \ge h_{\perp}$$

where $\mathbf{r}_{\parallel}$ and $\mathbf{r}_{\perp}$ are the parts of the residual parallel and perpendicular to $\mathbf{x}$. In the paper's benchmarks this beat the other libraries tested on glove-100 at equal recall. ScaNN ships as an open-source library and powers Google's managed vector search (Vertex AI Vector Search, and the ScaNN index in AlloyDB). The lesson carries beyond ScaNN: **optimise the quantizer for the score you rank by**, not for pretty reconstructions.

### 2.10 Choosing an Index

```mermaid
flowchart TD
    Start["How many vectors per searchable set?"] -->|"under ~50k, or tiny filtered subsets"| Flat["Flat / exact"]
    Start -->|"50k to tens of millions"| Mem{"Does vectors + graph fit in RAM?"}
    Mem -->|"yes"| HNSW["HNSW, tune ef_search"]
    Mem -->|"no"| Q["HNSW + quantization (Stage 3)"]
    Start -->|"hundreds of millions+"| Big{"RAM budget"}
    Big -->|"tight"| Disk["DiskANN / IVF-PQ"]
    Big -->|"generous"| Shard["Sharded HNSW (Stage 6)"]
    HNSW --> Churn{"Heavy deletes or rebuilds?"}
    Churn -->|"yes"| Ops["Plan vacuum / compaction / reindex"]
```

| Need | Index | Settings to start with | Watch out for |
| --- | --- | --- | --- |
| Small collection, exact answers | Flat | none | Latency grows linearly with N. |
| General in-memory search | HNSW | `m=16`, `ef_construction=128`, sweep `ef_search` | Graph memory, slow builds, delete churn. |
| Fast builds, bulk loads, lower memory | IVFFlat / IVF | `lists ≈ rows/1000`, `probes ≈ sqrt(lists)` | Build after loading; retrain on drift. |
| Billions, limited RAM | DiskANN or IVF-PQ | Engine defaults, then tune search list size | Higher latency, SSD IOPS. |
| Read-only shared index file | Annoy or an mmap'd HNSW | n/a | Rebuild to add data. |

### 2.11 Pitfalls

| Pitfall | Symptom | Fix |
| --- | --- | --- |
| Building IVFFlat before loading data | `NOTICE: ivfflat index created with little data`, then low recall | Load (or sample) data first, then `CREATE INDEX`; `REINDEX CONCURRENTLY` after big changes. |
| `hnsw.ef_search` lower than `LIMIT` | Query returns fewer rows than `LIMIT` | Keep `ef_search >= LIMIT`; use `SET LOCAL hnsw.ef_search = ...` for large k. |
| Query shape the planner cannot index | `EXPLAIN` shows `Seq Scan` and `Sort`; latency grows with table size | Use `ORDER BY embedding <=> $1 LIMIT k` with the operator that matches the index opclass (`vector_cosine_ops` needs `<=>`). |
| Opclass and operator mismatch | Index exists but is never used | Create the index with the opclass for the operator you query with, or one index per metric. |
| HNSW build spilling to disk | `NOTICE: hnsw graph no longer fits into maintenance_work_mem after N tuples`; builds take hours | Raise `maintenance_work_mem` for the build session; use parallel workers. |
| Qdrant collection below the indexing threshold | Queries are exact full scans; latency rises as data grows until the optimizer kicks in | Expected for small segments; check `indexed_vectors_count` in collection info and tune `optimizers_config.indexing_threshold` for tests. |
| Trusting recall at launch | Recall slips over months of deletes and inserts | Track recall@k against exact search on a fixed query sample in CI or a nightly job. |
| Tuning on random vectors | Parameters too low for real embeddings | Tune on a sample of real data and real queries. |

### 2.12 Best Practices

- **Measure recall with your own data**: exact search over a few thousand sampled queries is cheap and gives ground truth.
- **Tune `ef_search` first, `M` second**: `ef_search` is a runtime knob; changing `M` means a rebuild.
- **Keep build-time and query-time settings in config, not in code**: you will change them after looking at recall curves.
- **Load first, index second for bulk imports**: one bulk HNSW or IVF build is far faster than millions of incremental inserts.
- **Use `EXPLAIN` on every vector query you ship in pgvector**: a missing index scan is the most common silent performance bug.
- **Plan for deletes from day one**: decide who runs `VACUUM`, `REINDEX` or compaction and how you will know it is falling behind.

### 2.13 Hands-on Exercise

Run the recall sweep and find the smallest `ef_search` and `nprobe` that reach recall@10 of 0.99:

```bash
python -m src.learn_vector_databases.sweep --points 1000 --dims 32
```

**Expected:** HNSW already reports recall@10 = 1.000 at `ef_search=10` on this clustered data; IVF climbs from about 0.86 at `nprobe=1` to 1.000 at `nprobe=4` (out of 31 lists), and latency roughly doubles each time `nprobe` doubles. Then rerun with `--dims 128` and note how the numbers move. For the SQL half, run `sql/02_indexes.sql` and change `SET hnsw.ef_search = 40` to `10`, then compare the `recall_at_10_hits` value.

Solutions: [`src/learn_vector_databases/sweep.py`](src/learn_vector_databases/sweep.py), its test in [`tests/test_geometry.py`](tests/test_geometry.py), and [`sql/02_indexes.sql`](sql/02_indexes.sql).

[Back to top ⤴️](#-table-of-contents)

---

## 3. Stage 3: Quantization & Memory Compression

Vectors are big, and ANN indexes are fast only when the data they touch sits in RAM. This stage sizes that memory, then shrinks it with scalar quantization, half precision, product quantization and binary quantization, and recovers the lost accuracy with oversampling and rescoring. It builds on Stage 2's recall measurements. Afterwards you can estimate a cluster's RAM from first principles, pick a quantization scheme, and configure it in pgvector and Qdrant with a measured recall cost.

```mermaid
flowchart LR
    FP32["float32: 4 B/dim"] --> FP16["halfvec / float16: 2 B/dim"]
    FP16 --> SQ8["SQ8 int8: 1 B/dim"]
    SQ8 --> PQ["PQ: m bytes per vector"]
    PQ --> BQ["Binary: 1 bit/dim"]
    BQ --> Rescore["Oversample, then rescore with originals"]
    Rescore --> Recall["Recall back near float32"]
```

### 3.1 Sizing Memory: Vectors, Graph and Overhead

For `N` vectors of `D` float32 dimensions:

$$\text{Vector bytes} = N \times D \times 4$$

$$\text{HNSW layer-0 links} \approx N \times 2M \times b_{id}$$

where $b_{id}$ is the size of a neighbour id (4 bytes in most engines, 8 when ids are 64-bit). Upper layers add about $1/(M-1)$ more links, which is small. Real engines add per-node headers, payloads, visited-list buffers, allocator slack and segment duplication during optimisation, so in practice **budget 1.3-1.5x the raw vector size**.

```python
from src.learn_vector_databases.geometry import estimate_memory

for n in (1_000_000, 10_000_000, 100_000_000):
    est = estimate_memory(n, 1536, m=16)
    print(f"{n:>11,} x 1536: vectors {est.vectors_bytes / 1e9:7.1f} GB, "
          f"graph {est.graph_bytes / 1e9:5.2f} GB, budget ~{est.total_bytes * 1.35 / 1e9:6.0f} GB")
```

```text
  1,000,000 x 1536: vectors     6.1 GB, graph  0.13 GB, budget ~     8 GB
 10,000,000 x 1536: vectors    61.4 GB, graph  1.28 GB, budget ~    85 GB
100,000,000 x 1536: vectors   614.4 GB, graph 12.80 GB, budget ~   847 GB
```

| Line / API | Role | What happens at runtime |
| :--- | :--- | :--- |
| `estimate_memory(n, dims, m)` | Sizing helper | Returns raw vector bytes and layer-0 link bytes (`2 * m * 4` per vector). |
| `dtype="int8"` / `"float16"` / `"binary"` | Quantized sizes | 1, 2 or 1/8 bytes per dimension; used in 3.2-3.6. |
| `* 1.35` | Overhead factor | Rule-of-thumb headroom; measure the real number on your engine with a 1% sample. |

Two observations drive everything else in this stage. First, **vectors dominate**: at 1,536 dimensions the graph is about 2% of the total, so compressing vectors is where the savings are. Second, **memory, not CPU, sets the bill**: 100 million OpenAI-sized vectors need several large-memory machines in float32, but fit on one or two with 4-32x compression.

### 3.2 Scalar Quantization (SQ8): float32 to int8

**SQ8** maps each dimension's value range onto 256 integer buckets, cutting vector memory by 4x:

$$q_i = \operatorname{round}\left( 255 \times \frac{v_i - \text{low}_i}{\text{high}_i - \text{low}_i} \right), \quad q_i \in [0, 255]$$

```mermaid
flowchart LR
    Float["float32: 0.4128 (4 bytes)"] --> Range["Learned range for this dimension: low, high"]
    Range --> Scale["round((x - low) / (high - low) * 255), clamp to 0..255"]
    Scale --> Int8["uint8: 184 (1 byte)"]
    Int8 --> Back["Dequantize: low + q * (high - low) / 255"]
```

The range can be the per-dimension minimum and maximum, but one outlier then wastes most buckets. Production engines clip to a **quantile**: with `quantile = 0.99` the range spans the 0.5th to the 99.5th percentile and the rare values outside are clamped.

```python
from src.learn_vector_databases.vectordb import ScalarQuantizer

# 20 ordinary training vectors plus one outlier (9.0) in the first dimension
train = [[0.10 + 0.01 * i, -0.2 + 0.02 * i] for i in range(20)] + [[9.0, 0.1]]
sq_minmax = ScalarQuantizer(quantile=1.0)
sq_clip = ScalarQuantizer(quantile=0.9)      # small sample, so a lower quantile than production's 0.99
sq_minmax.fit(train)
sq_clip.fit(train)

v = [0.15, 0.0]
for sq in (sq_minmax, sq_clip):
    codes = sq.quantize(v)
    print(codes, [round(x, 4) for x in sq.dequantize(codes)])
```

```text
[1, 134] [0.1349, -0.0003]
[57, 135] [0.1502, -0.0]
```

With min-max scaling, the first dimension's range is 0.1 to 9.0, so all twenty ordinary values (0.10 to 0.29) share the first six buckets and 0.15 comes back as 0.1349. With quantile clipping, the range is 0.11 to 0.29, the ordinary values spread over all 256 buckets, and 0.15 comes back as 0.1502. The outlier itself is clamped to 255, which costs that one value some accuracy and saves everyone else's.

| Line / API | Role | What happens at runtime |
| :--- | :--- | :--- |
| `ScalarQuantizer(quantile)` | Configuration | `1.0` is min-max; `0.99` is the common production setting (Qdrant's `quantile`). |
| `fit(vectors)` | Training | Sorts each column of a sample and reads two percentiles. Seconds, not minutes, even for millions of vectors. |
| `quantize` | Encode | Scales, rounds and clamps to `0..255`. |
| `dequantize` | Decode | Bucket centre; the error per dimension is at most half a bucket width inside the range. |

Engines do not dequantize at query time. They compute distances directly on int8 codes using integer SIMD (for example AVX-512 VNNI or ARM dot-product instructions), which processes several times more dimensions per instruction than float32 arithmetic. On the starter's clustered 64-dim benchmark (3.8), SQ8 kept **recall@10 = 0.956** without any rescoring. On typical 768-1536-dim text embeddings the loss is usually around one point or less, which is why SQ8 is the usual first step.

### 3.3 Half Precision: float16, bfloat16 and pgvector `halfvec`

Halving precision halves memory with almost no effect on ranking, because neighbour order depends on relative distances, not on the seventh significant digit.

| Format | Bits (sign / exponent / mantissa) | Range | Typical use |
| --- | --- | --- | --- |
| float32 | 1 / 8 / 23 | about 1e-38 to 3e38 | Default storage, ground truth. |
| float16 | 1 / 5 / 10 | about 6e-5 to 65,504 | Vector storage and indexes; fine for unit vectors. |
| bfloat16 | 1 / 8 / 7 | Same as float32 | GPU training and inference; coarser mantissa, no overflow worries. |

pgvector's `halfvec` (0.7+) stores 2 bytes per dimension and indexes up to 4,000 dimensions, which is how you index 3,072-dimension models that exceed the 2,000-dimension limit of `vector`. You can keep the column in full precision and quantize only the index with an expression:

```sql
-- index stores float16, table keeps float32
CREATE INDEX docs_half ON docs USING hnsw ((embedding::halfvec(16)) halfvec_cosine_ops);

-- the query must repeat the same expression or the index is not used
SELECT id
FROM docs
ORDER BY embedding::halfvec(16) <=> (SELECT embedding FROM docs WHERE id = 42)::halfvec(16)
LIMIT 5;

-- storage per value
SELECT pg_column_size('[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]'::vector(16))  AS vector_bytes,   -- 72
       pg_column_size('[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]'::halfvec(16)) AS halfvec_bytes;  -- 40
```

`vector(n)` takes `4n + 8` bytes and `halfvec(n)` takes `2n + 8`. For raw vectors that never leave unit length, float16's limited range is not a concern; for unnormalised features with large magnitudes (above 65,504) it overflows to infinity, so check your data or use bfloat16 where the engine supports it.

### 3.4 Product Quantization (PQ): Sub-Vector Codebooks

When 2-4x is not enough, **product quantization** (Jégou, Douze and Schmid, 2011) reaches 16-64x. It splits each vector into `m` sub-vectors and runs k-means separately in each sub-space:

```mermaid
graph TD
    Vec["1536-dim float32 vector: 6,144 bytes"]
    Sub1["Sub-vector 1: dims 1-16"]
    Sub2["Sub-vector 2: dims 17-32"]
    SubM["Sub-vector 96: dims 1521-1536"]
    Vec --> Sub1
    Vec --> Sub2
    Vec --> SubM
    Sub1 --> Code1["nearest of 256 centroids: code 42"]
    Sub2 --> Code2["code 189"]
    SubM --> CodeM["code 12"]
    PQVec["PQ code: 96 bytes, 64x smaller"]
    Code1 --> PQVec
    Code2 --> PQVec
    CodeM --> PQVec
```

1. Split a `D`-dim vector into `m` sub-vectors of `D/m` dimensions (1536 / 96 = 16).
2. In each sub-space, train k-means with `ks = 256` centroids, so one code fits in a byte.
3. Encode a vector as the `m` indices of its nearest sub-centroids: 96 bytes instead of 6,144.
4. The codebooks themselves are tiny: `m * ks * (D/m) * 4 = ks * D * 4` bytes (about 1.5 MB here), shared by all vectors.

The starter's version is a few dozen lines:

```python
from src.learn_vector_databases.vectordb import ProductQuantizer
import random

rng = random.Random(0)
train = [[rng.gauss(0, 1) for _ in range(8)] for _ in range(300)]

pq = ProductQuantizer(dimensions=8, m=4, ks=16)   # 4 sub-vectors of 2 dims, 16 centroids each
pq.fit(train)
code = pq.encode(train[0])
print(list(code), len(code), "bytes")              # 4 codes in 0..15, 4 bytes vs 32 for float32
print([round(x, 2) for x in pq.decode(code)])      # lossy reconstruction of train[0]
```

| Line / API | Role | What happens at runtime |
| :--- | :--- | :--- |
| `ProductQuantizer(dimensions, m, ks)` | Shape | Rejects `dimensions % m != 0` and `ks > 256` (a code must fit in a byte). |
| `fit(train)` | Training | One k-means per sub-space. Needs at least `ks` training vectors; real systems use 50k-250k samples. |
| `encode(v)` | Compression | `m` nearest-centroid lookups, returned as `bytes`. |
| `decode(code)` | Reconstruction | Concatenates the chosen centroids. Used for debugging and SDC, not for ADC search. |

PQ is lossy enough that ranking by PQ codes alone loses noticeable recall. It shines combined with IVF (IVF-PQ: coarse clusters plus compressed residuals), in DiskANN (PQ codes in RAM for routing, full vectors on SSD), and with rescoring (3.8).

### 3.5 Asymmetric vs Symmetric Distance Computation (ADC vs SDC)

How do you compare an uncompressed query with millions of PQ codes quickly?

```mermaid
sequenceDiagram
    autonumber
    actor Query as Query q (float32)
    participant Table as Distance table m x 256
    participant Corpus as PQ codes
    Note over Query,Table: once per query
    Query->>Table: distance from each query sub-vector to every centroid of its sub-space
    Note over Table,Corpus: per candidate, no multiplications
    Table->>Corpus: read the candidate's m codes
    Corpus->>Corpus: sum table[j][code_j] over j
    Corpus-->>Query: approximate distances, keep top-k
```

- **SDC (symmetric)**: quantize the query too and look up centroid-to-centroid distances. Both sides carry quantization error.
- **ADC (asymmetric)**: keep the query exact; only the database side is quantized. The query builds an `m x ks` table of exact sub-distances once, then each candidate costs `m` table lookups and additions. ADC has half the noise of SDC at the same speed, so it is the default everywhere.

```python
table = pq.distance_table(train[1])        # m x ks squared distances, built once per query
approx = pq.adc_distance(table, pq.encode(train[2]))
exact = sum((a - b) ** 2 for a, b in zip(train[1], train[2]))
print(round(approx, 3), round(exact, 3))   # 19.503 22.051: same neighbourhood, not exact
```

The table for `m = 96, ks = 256` is 96 KB of float32, which fits in L2 cache, so the inner loop is cache-resident lookups. FAISS goes further with 4-bit codes and SIMD shuffles ("fast-scan" PQ) to do the lookups inside registers.

### 3.6 Production Product Quantizer with NumPy

The pure-Python starter shows the algorithm; vectorised NumPy shows how it is done in practice. This version needs `numpy` and `scikit-learn` (`pip install numpy scikit-learn`), which the starter does not install by default:

```python
import numpy as np
from sklearn.cluster import MiniBatchKMeans

class NumpyProductQuantizer:
    """PQ with asymmetric distance computation (ADC), vectorised with NumPy."""

    def __init__(self, d: int, m: int, k_sub: int = 256):
        assert d % m == 0, f"Dimension {d} must be divisible by m={m}"
        self.d, self.m, self.k_sub = d, m, k_sub
        self.d_sub = d // m
        self.codebooks = None                     # shape (m, k_sub, d_sub)

    def fit(self, training_vectors: np.ndarray) -> None:
        books = []
        for j in range(self.m):
            sub = training_vectors[:, j * self.d_sub:(j + 1) * self.d_sub]
            km = MiniBatchKMeans(n_clusters=self.k_sub, batch_size=2048, random_state=42, n_init="auto")
            km.fit(sub)
            books.append(km.cluster_centers_)
        self.codebooks = np.asarray(books, dtype=np.float32)

    def encode(self, vectors: np.ndarray) -> np.ndarray:
        codes = np.empty((vectors.shape[0], self.m), dtype=np.uint8)
        for j in range(self.m):
            sub = vectors[:, j * self.d_sub:(j + 1) * self.d_sub]            # (n, d_sub)
            dists = ((sub[:, None, :] - self.codebooks[j]) ** 2).sum(axis=2)  # (n, k_sub)
            codes[:, j] = dists.argmin(axis=1)
        return codes

    def search_adc(self, query: np.ndarray, codes: np.ndarray, top_k: int = 5):
        q = query.reshape(self.m, self.d_sub)
        table = ((self.codebooks - q[:, None, :]) ** 2).sum(axis=2)          # (m, k_sub)
        dists = table[np.arange(self.m), codes].sum(axis=1)                  # gather + sum: (n,)
        top = np.argpartition(dists, top_k)[:top_k]
        top = top[np.argsort(dists[top])]
        return top, dists[top]

if __name__ == "__main__":
    rng = np.random.default_rng(0)
    data = rng.standard_normal((20_000, 128)).astype(np.float32)
    pq = NumpyProductQuantizer(d=128, m=16)
    pq.fit(data[:10_000])
    codes = pq.encode(data)                                  # 20,000 x 16 bytes
    ids, dists = pq.search_adc(data[123], codes, top_k=5)
    print(ids, dists.round(2))                               # id 123 should be first
```

| Line / API | Role | What happens at runtime |
| :--- | :--- | :--- |
| `MiniBatchKMeans(n_init="auto")` | Codebook training | Mini-batches keep training fast on large samples. |
| `sub[:, None, :] - codebooks[j]` | Broadcasting | Builds an `(n, k_sub, d_sub)` difference tensor; batch `encode` calls for very large `n` to bound memory. |
| `table[np.arange(m), codes]` | ADC gather | Fancy indexing picks `table[j, codes[i, j]]` for every vector and sub-space in one call. |
| `np.argpartition` | Top-k | $O(n)$ selection instead of a full sort. |

### 3.7 Binary Quantization (BQ): One Bit per Dimension

**Binary quantization** keeps only the sign of each dimension:

$$b_i = \begin{cases} 1 & \text{if } v_i \ge 0 \\ 0 & \text{if } v_i < 0 \end{cases}$$

A 1,536-dimension vector shrinks from 6,144 bytes to 192 bytes (32x). Distance becomes Hamming distance: XOR the two bit strings and count the ones. Each 64-bit word takes one XOR and one population-count instruction, and SIMD versions handle 512 bits at a time.

```c
#include <stdint.h>

int hamming_distance(const uint64_t *u, const uint64_t *v, int words) {
    int dist = 0;
    for (int i = 0; i < words; ++i) {
        dist += __builtin_popcountll(u[i] ^ v[i]);   /* XOR, then count set bits */
    }
    return dist;
}
```

The starter packs bits into a Python integer; `int.bit_count()` is the population count:

```python
from src.learn_vector_databases.vectordb import BinaryQuantizer

bq = BinaryQuantizer(dimensions=8)
a = bq.quantize_to_bits([0.3, -0.1, 0.8, -0.5, 0.2, 0.0, -0.9, 0.4])
b = bq.quantize_to_bits([0.2, 0.1, 0.7, -0.4, -0.3, 0.1, -0.8, 0.5])
print(bin(a), bin(b), bq.hamming_distance(a, b))       # 2 bits differ (dims 1 and 4)
print(BinaryQuantizer.calculate_ram_savings(1_000_000, 1536))
# {'fp32_mb': 5859.38, 'bq_mb': 183.11, 'compression_ratio': 32.0, 'savings_percentage': 96.9}
```

BQ works when there is enough redundancy across dimensions: it is usually acceptable at 1,024+ dimensions on models whose values are centred around zero, and poor at low dimensions. On the starter's 64-dim benchmark, Hamming-only ranking reached just **recall@10 = 0.214**. Some embedding providers train models to tolerate binary output (Cohere's embed v3 family, for example, offers binary embeddings directly), and newer schemes (RaBitQ in Milvus 2.6, Elasticsearch's BBQ, multi-bit variants in recent Qdrant releases) add a correction term or a few extra bits to cut the error. With any of them, rescoring (next section) is not optional.

In pgvector, `binary_quantize` turns a `vector` into a `bit` string and `<~>` is Hamming distance:

```sql
CREATE INDEX docs_bits ON docs USING hnsw ((binary_quantize(embedding)::bit(16)) bit_hamming_ops);
```

### 3.8 Oversampling & Rescoring

Every quantizer above makes ranking noisier. The standard fix is a **two-phase search**: rank cheaply with compressed codes, keep `k * oversampling` candidates, then rescore only that shortlist with the original vectors (from RAM, mmap or disk) and return the best `k`.

```mermaid
flowchart LR
    Q["Query q"] --> Phase1["Phase 1: search compressed codes in RAM"]
    Phase1 --> Short["Shortlist of k x oversampling ids"]
    Short --> Fetch["Fetch original float32 vectors (RAM, mmap or SSD)"]
    Fetch --> Phase2["Phase 2: exact distance on the shortlist"]
    Phase2 --> Top["Final top-k"]
```

```python
def binary_search_with_rescore(items, query, k, oversampling=4.0, metric=DistanceMetric.COSINE):
    bq = BinaryQuantizer(len(query))
    q_bits = bq.quantize_to_bits(query)
    shortlist_size = max(k, int(math.ceil(k * oversampling)))
    shortlist = heapq.nsmallest(
        shortlist_size, items,
        key=lambda it: bq.hamming_distance(q_bits, bq.quantize_to_bits(it.vector)),
    )
    rescored = ((it, calculate_distance(query, it.vector, metric)) for it in shortlist)
    return heapq.nsmallest(k, rescored, key=lambda pair: pair[1])
```

Measured with `python -m src.learn_vector_databases.sweep --quantization --points 2000 --dims 64` (2,000 clustered 64-dim vectors, 50 queries, recall@10 against exact cosine):

| Method | Bytes per vector | Recall@10 |
| --- | --- | --- |
| float32 (exact) | 256 | 1.000 |
| SQ8, no rescoring | 64 | 0.956 |
| PQ (`m=16`, `ks=32`), ADC only | 16 (10 with 5-bit packing) | 0.272 |
| PQ, rescore 4x | 16 | 0.710 |
| BQ, Hamming only | 8 | 0.214 |
| BQ, rescore 4x | 8 | 0.638 |
| BQ, rescore 8x | 8 | 0.930 |
| BQ, rescore 16x | 8 | 1.000 |

This dataset is deliberately hard for coarse codes (tight clusters, only 64 dimensions), which makes the rescoring effect easy to see. The shape of the result holds generally: **compressed codes find the neighbourhood, originals pick the winners**, and the oversampling factor is the knob that trades extra reads for recall.

Configuring it in engines:

```sql
-- pgvector: oversample 40 on bits, re-rank with exact cosine (from sql/03_quantization.sql)
WITH q AS (SELECT embedding AS v FROM docs WHERE id = 42),
shortlist AS (
    SELECT id, embedding
    FROM docs
    ORDER BY binary_quantize(embedding)::bit(16) <~> binary_quantize((SELECT v FROM q))
    LIMIT 40
)
SELECT id, round((embedding <=> (SELECT v FROM q))::numeric, 4) AS cosine
FROM shortlist
ORDER BY embedding <=> (SELECT v FROM q)
LIMIT 5;
```

```bash
# Qdrant: binary codes in RAM, originals on disk, rescoring with 3x oversampling at query time
curl -X PUT http://localhost:6333/collections/docs_bq -H 'Content-Type: application/json' \
  -d '{"vectors": {"size": 1536, "distance": "Cosine", "on_disk": true},
       "quantization_config": {"binary": {"always_ram": true}}}'

curl -X POST http://localhost:6333/collections/docs_bq/points/query -H 'Content-Type: application/json' \
  -d '{"query": [0.01, 0.02, 0.03], "limit": 10,
       "params": {"quantization": {"rescore": true, "oversampling": 3.0}}}'
```

```bash
# Qdrant: SQ8 and PQ use the same switch
curl -X PUT http://localhost:6333/collections/docs_sq -H 'Content-Type: application/json' \
  -d '{"vectors": {"size": 768, "distance": "Cosine", "on_disk": true},
       "quantization_config": {"scalar": {"type": "int8", "quantile": 0.99, "always_ram": true}}}'

curl -X PUT http://localhost:6333/collections/docs_pq -H 'Content-Type: application/json' \
  -d '{"vectors": {"size": 768, "distance": "Cosine", "on_disk": true},
       "quantization_config": {"product": {"compression": "x16", "always_ram": true}}}'
```

`on_disk: true` with `always_ram: true` is the key combination: compressed codes stay in RAM for phase 1, full vectors live in mmap'd files and are read only for the shortlist.

### 3.9 Quantization Trade-off Matrix

Typical ranges for 768-1,536-dim text embeddings; your model and data decide the real numbers, so measure them.

| Quantization Method | Memory vs float32 | Typical Recall@10 loss (before rescoring) | Training | Query speed | Best suited for |
| :--- | :--- | :--- | :--- | :--- | :--- |
| **None (float32)** | 1x | 0 | none | baseline | Small corpora, ground truth, rescoring source. |
| **float16 / bfloat16** | 2x smaller | well under 0.1 points | none | similar or faster (less memory traffic) | Default when RAM allows; pgvector `halfvec`. |
| **SQ8 (int8)** | 4x | around 1 point | percentiles from a sample | faster with int8 SIMD | The usual first step for production RAG. |
| **PQ** | 16-64x | several points, more at high compression | k-means per sub-space | fast ADC; needs rescoring | Very large corpora, IVF-PQ, DiskANN routing. |
| **BQ (1-bit)** | 32x | large unless the model suits it | none | fastest (XOR + popcount) | High-dim models built for it, always with rescoring. |

### 3.10 Pitfalls

| Pitfall | Symptom | Fix |
| --- | --- | --- |
| Min-max SQ8 on data with outliers | Recall far below the expected ~1 point loss | Use a quantile (`0.99`) range; inspect per-dimension min/max on a sample. |
| BQ on low-dimensional or off-centre embeddings | Recall collapses (0.214 in 3.8) | Use SQ8 instead, or BQ only with large oversampling; check the model's guidance. |
| Rescoring disabled or originals unavailable | Results "close but wrong" in order; recall stuck | Keep originals (on disk is fine) and enable `rescore` / an exact re-rank step. |
| `on_disk` originals on slow network storage | p99 latency spikes when rescoring | Put originals on local NVMe; size oversampling to the IOPS budget. |
| Querying a `halfvec` expression index without the cast | `EXPLAIN` shows a sequential scan | Repeat the exact expression (`embedding::halfvec(n)`) in `ORDER BY`. |
| Training PQ on too few or unrepresentative vectors | `need at least ks training vectors` (starter) or poor codebooks | Train on 50k-250k vectors sampled across tenants and time; retrain after model changes. |
| float16 overflow on unnormalised features | `inf` values, NaN distances | Normalise or scale before casting; use bfloat16 where supported. |
| Comparing compression ratios without overhead | Real memory saving smaller than the table says | Include graph links, payload indexes and the originals (if in RAM). |

### 3.11 Best Practices

- **Start with SQ8 plus rescoring**: it gives a 4x cut with little recall loss and almost no tuning.
- **Quantize the index, keep the originals**: an expression index or `on_disk` originals let you change schemes later without re-embedding.
- **Tune oversampling against a recall target**: treat it like `ef_search`, a runtime knob measured on real queries.
- **Measure memory on a sample, then extrapolate**: load 1% of the data and read the engine's own memory metrics.
- **Keep quantization training data representative**: a codebook trained on one tenant or one month's data degrades on the rest.
- **Retest quantization when you change embedding models**: a model that suits BQ may be replaced by one that does not.

### 3.12 Hands-on Exercise

1. Use `estimate_memory` to size 50 million 768-dim vectors with `m=16` in float32, int8 and binary. **Expected:** about 154 GB, 38 GB and 4.8 GB of raw vectors, plus 6.4 GB of layer-0 links in every case, which shows the graph becoming the larger part at 1 bit per dimension.
2. Run `python -m src.learn_vector_databases.sweep --quantization --points 2000 --dims 64` and reproduce the table in 3.8. Then edit `quantization_report` to try `oversampling` 2 and 32 for BQ and find the smallest factor that reaches 0.95.
3. In pgvector, after `sql/03_quantization.sql`, take row 7 as the query, compute its exact top-5 neighbours with `ORDER BY embedding <=> q LIMIT 5` (excluding `id = 7`), and count how many of them the bit-shortlist query returns for shortlist sizes 5, 40 and 200. **Expected:** the overlap grows with the shortlist size. With only 16 dimensions the bit codes are coarse, so a small shortlist misses most true neighbours, which is the low-dimension BQ failure from 3.7 seen in SQL.

Solutions: [`src/learn_vector_databases/geometry.py`](src/learn_vector_databases/geometry.py) (`estimate_memory`), [`src/learn_vector_databases/sweep.py`](src/learn_vector_databases/sweep.py) (`quantization_report`), [`tests/test_geometry.py`](tests/test_geometry.py), [`sql/03_quantization.sql`](sql/03_quantization.sql).

[Back to top ⤴️](#-table-of-contents)

---

## 4. Stage 4: Database Landscape & Architecture

This stage compares the engines that implement Stages 1-3: purpose-built vector databases and the vector features of general-purpose databases. It assumes you know HNSW and quantization. Afterwards you can explain how each engine stores and indexes data, write the same query against six of them, and choose one with a capacity estimate rather than a feature list.

### 4.1 Dedicated Specialized Vector DBs vs Vector-Extended Databases

Engines fall into two families. Purpose-built vector databases are designed around the ANN index: storage, filtering, replication and APIs all serve vector queries. Vector-extended databases add a vector type and an ANN index to an engine that already has transactions, joins, full-text search or an in-memory data model.

```mermaid
flowchart TD
    Market["Vector Search Landscape"]

    subgraph Dedicated["1. Purpose-Built Vector Databases"]
        Qdrant["Qdrant: Rust, payload-aware HNSW, on-disk vectors"]
        Pinecone["Pinecone: managed serverless, closed source"]
        Milvus["Milvus: distributed, compute and storage separated"]
        Weaviate["Weaviate: Go, schema-first, built-in hybrid"]
        Chroma["Chroma: embedded or client-server, prototyping and edge"]
    end

    subgraph Extended["2. Vector-Extended Databases"]
        PG["PostgreSQL + pgvector: ACID, joins, SQL"]
        Redis["Redis Query Engine: in-memory, low latency"]
        ES["Elasticsearch / OpenSearch: Lucene HNSW + BM25"]
        ClickHouse["ClickHouse: analytics + vector distance functions"]
    end

    Market --> Dedicated
    Market --> Extended
```

#### Decision Matrix: When to Pick Which Category

| Requirement | Usual choice | Reason |
| :--- | :--- | :--- |
| Existing PostgreSQL stack, up to tens of millions of vectors | PostgreSQL + `pgvector` | No new system to run; ACID writes; vectors join directly to business tables. |
| Hundreds of millions of vectors, heavy writes, filtered search | Qdrant or Milvus | Segment-based storage, quantization with on-disk originals, filter-aware traversal, horizontal sharding. |
| No operations team, spiky or low traffic | Pinecone serverless (or a managed Qdrant / Milvus / Weaviate) | Capacity and index maintenance are the provider's job; cost follows usage. |
| Sub-millisecond lookups next to a cache or session store | Redis Query Engine | Everything is in RAM in a process the team already runs. |
| Full-text search is the main product, vectors are added | Elasticsearch / OpenSearch | Mature BM25, analyzers and aggregations, with HNSW fields in the same index. |

### 4.2 Architectural Breakdown: Qdrant, Pinecone, Milvus, Weaviate, ChromaDB

#### 1. Qdrant (Rust)

- **Engine**: a single Rust binary. A collection is split into shards, each shard into segments; each segment owns its vectors, payload and HNSW graph (4.7).
- **Payload-first filtering**: keyword, integer, float, bool, geo, datetime, text and UUID payload indexes. The planner uses them to choose between a filtered graph walk and an exact scan (Stage 5.4).
- **On-disk storage**: vectors and the graph can each be memory-mapped. A common layout keeps quantized codes in RAM and full vectors on NVMe, which often cuts RAM by most of the vector footprint.
- **Protocols**: REST on port 6333 and gRPC on 6334.

#### 2. Pinecone (managed serverless)

- **Engine**: a managed service that separates storage from compute. Index data lives in object storage; query workers cache the parts they need on local SSD (4.5).
- **Model**: indexes contain namespaces; a namespace is the unit of isolation and is the usual way to model a tenant.
- **Limitation**: closed source and available only as a service, so check data residency, private networking and export paths against the plan you buy.

#### 3. Milvus (distributed)

- **Engine**: a set of services: a proxy, coordinators and worker nodes (query, data and index roles), etcd for metadata, a log service for the write-ahead log (Pulsar or Kafka historically; Milvus 2.6 adds its own Woodpecker WAL and a streaming node), and MinIO or S3 for segment files. The exact roles change between releases (4.8).
- **Scale**: built for billions of vectors across many nodes; Milvus Lite and the standalone image cover local development.
- **Operations**: the distributed mode is a Kubernetes deployment with several stateful dependencies; budget for running it or use the managed offering.

#### 4. Weaviate (Go)

- **Engine**: schema-centric collections, each shard holding an HNSW (or flat, or dynamic) vector index plus an inverted index for properties and BM25.
- **Vectorizer modules**: optional integrations call OpenAI, Cohere, Hugging Face and other providers at import and query time, so the database can embed text itself.
- **Interface**: GraphQL and REST, plus gRPC used by the v4 clients. Vector, BM25 and hybrid queries are first-class.

#### 5. Chroma (embedded and client-server)

- **Engine**: runs inside a Python or JavaScript process or as a server. Early versions used DuckDB; current releases have a Rust core, keep metadata in SQLite and store HNSW index files alongside.
- **Best used for**: local development, notebooks, tests in CI and desktop or edge applications.

### 4.3 Relational & Document Extensions: PostgreSQL `pgvector`, Redis, OpenSearch

#### 1. PostgreSQL with `pgvector`

`pgvector` adds vector types, distance operators and two index access methods to PostgreSQL:

- **Indexes**:
  - `hnsw`: multi-layer graph index (pgvector 0.5.0+).
  - `ivfflat`: faster builds and lower memory, but lists are trained once, so recall drifts on changing tables.
- **Distance operators**:
  - `<->`: Euclidean distance ($L_2$).
  - `<#>`: negative inner product.
  - `<=>`: cosine distance.
  - `<+>`: L1 distance; `<~>` Hamming and `<%>` Jaccard on `bit` (0.7.0+).
- **Joins and filters in one statement**, which no dedicated vector database can match:

```sql
SELECT p.title, p.price, 1 - (v.embedding <=> $1) AS similarity
FROM product_vectors v
JOIN products p ON v.product_id = p.id
JOIN merchant_stores m ON p.store_id = m.id
WHERE m.is_active = true
  AND p.price <= 100.00
ORDER BY v.embedding <=> $1   -- order by the operator itself so an HNSW index can be used
LIMIT 10;
```

#### 2. Redis (Query Engine vector fields)

Vectors live in hashes or JSON documents and are indexed with `FT.CREATE` (the Query Engine, formerly RediSearch). Redis 8 also adds a separate vector set data type (`VADD`, `VSIM`).

```bash
# HNSW index over hashes whose keys start with doc:
redis-cli FT.CREATE docs_idx ON HASH PREFIX 1 doc: SCHEMA \
  tenant TAG \
  embedding VECTOR HNSW 6 TYPE FLOAT32 DIM 768 DISTANCE_METRIC COSINE

# KNN with a tag pre-filter. $vec is the raw little-endian float32 bytes of the query.
redis-cli FT.SEARCH docs_idx "(@tenant:{acme})=>[KNN 5 @embedding \$vec AS score]" \
  PARAMS 2 vec "<768 float32 bytes>" SORTBY score DIALECT 2
```

#### 3. Elasticsearch and OpenSearch

Both index vectors with Lucene HNSW graphs per segment. Elasticsearch's `dense_vector` field quantizes by default in recent versions (int8, and BBQ binary quantization for high dimensions); OpenSearch's k-NN plugin offers Lucene and Faiss engines.

```bash
# Elasticsearch: approximate kNN with a filter applied during the graph search
curl -s -X POST "localhost:9200/docs/_search" -H 'Content-Type: application/json' -d '{
  "knn": {
    "field": "embedding",
    "query_vector": [0.12, -0.03, 0.88],
    "k": 5,
    "num_candidates": 50,
    "filter": { "term": { "tenant": "acme" } }
  },
  "_source": ["title"]
}'
```

`num_candidates` plays the role of `ef_search` per shard: raising it improves recall and costs latency.

### 4.4 Storage Engine Layouts: In-Memory vs MMAP Disk-Backed vs Quantized RAM plus SSD

Where the vectors and the graph live sets both the cost and the latency floor:

```mermaid
flowchart TD
    StorageModel["Vector Storage Layouts"]

    subgraph PureRAM["1. All in RAM: Redis, default Milvus, small Qdrant"]
        M1["Vectors and graph in RAM"]
        M2["Lowest latency, highest cost per vector"]
    end

    subgraph MMAP["2. Memory-mapped: Qdrant on_disk, Annoy"]
        O1["Graph in RAM or mmap"]
        O2["Full vectors in files, read through mmap"]
        O3["OS page cache keeps hot pages in RAM"]
        O4["Latency depends on cache hit rate and SSD"]
    end

    subgraph QuantizedDisk["3. Quantized in RAM + rescoring from disk"]
        Q1["SQ8 / PQ / BQ codes in RAM for traversal"]
        Q2["Full vectors on NVMe for the top candidates"]
        Q3["Billions of vectors on modest hardware"]
    end

    StorageModel --> PureRAM
    StorageModel --> MMAP
    StorageModel --> QuantizedDisk
```

| Layout | RAM per 1M x 768-dim vectors (approx.) | p99 driver | Fails when |
| --- | --- | --- | --- |
| All in RAM, float32 | 2.9 GiB vectors + graph | CPU | The dataset outgrows the node. |
| Mmap, cold cache | Graph + page cache you can spare | SSD random reads | Working set exceeds page cache; network storage. |
| SQ8 in RAM + originals on disk | ~0.7 GiB codes + graph | Rescoring reads | Oversampling is set higher than the IOPS budget. |
| BQ in RAM + originals on disk | ~0.09 GiB codes + graph | Rescoring reads | The model does not tolerate 1-bit codes (Stage 3.7). |

### 4.5 Deep Dive into Pinecone Serverless Architecture

Pinecone serverless separates compute from storage so that idle indexes cost little:

```mermaid
sequenceDiagram
    autonumber
    actor Client as API Client
    participant Router as Request router
    participant Worker as Query worker (stateless)
    participant NVMe as Local SSD cache
    participant S3 as Object storage

    Client->>Router: Query vector + namespace
    Router->>Worker: Route to a worker for this index
    Worker->>NVMe: Are the needed index files cached?
    alt Cache miss
        Worker->>S3: Fetch index files
        S3-->>Worker: Bytes
        Worker->>NVMe: Warm the cache
    end
    Worker->>Worker: ANN search over cached files
    Worker-->>Client: Top-k matches
```

- **Storage and compute apart**: the durable copy of the index sits in object storage, so you pay for compute only while queries run.
- **Cache warming**: workers pull index files onto local SSD on demand.
- **Trade-off**: the first queries against a namespace that is not cached are slower than steady-state queries. Measure cold and warm latency separately if traffic per tenant is sparse.

### 4.6 Exhaustive Head-to-Head Engine Comparison

| Feature | PostgreSQL (`pgvector`) | Qdrant | Pinecone Serverless | Milvus | Weaviate |
| :--- | :--- | :--- | :--- | :--- | :--- |
| **Core language** | C | Rust | Proprietary | Go and C++ | Go |
| **License** | PostgreSQL License | Apache 2.0 | Proprietary SaaS | Apache 2.0 | BSD-3 |
| **Practical scale** | Tens of millions per node | Hundreds of millions per node, more with sharding | Managed, billions | Billions, distributed | Hundreds of millions, more with sharding |
| **Vector storage** | Table and index pages | RAM or mmap files per segment | Object storage + SSD cache | Segment files in object storage | RAM / mmap per shard |
| **ANN indexes** | HNSW, IVFFlat | HNSW (plus exact) | Proprietary | HNSW, IVF variants, DiskANN, GPU indexes | HNSW, flat, dynamic |
| **Filtering** | Full SQL `WHERE`, iterative scans | Payload indexes, filter-aware HNSW | Metadata filters | Boolean expressions, scalar indexes | Inverted index, filter-aware HNSW |
| **Transactions** | Full ACID | Per-point, WAL-backed | Eventual | Tunable consistency levels | Tunable consistency |
| **Quantization** | `halfvec`, `bit` + `binary_quantize` | SQ8, PQ, BQ (1, 1.5, 2-bit) | Managed | SQ8, PQ, RaBitQ (2.6) | SQ, PQ, BQ, RQ |
| **Deployment** | Any PostgreSQL | One binary or a cluster | API only | Standalone or Kubernetes cluster | Container or cluster |

Scale figures are orders of magnitude, not limits. They depend on dimensions, quantization, filters and hardware, which is why 4.11 estimates capacity instead of reading it from a table.

### 4.7 Inside a Qdrant Collection: Points, Segments and Payload

A Qdrant **point** is an id (unsigned integer or UUID), one or more vectors (named vectors let one point hold a dense, a sparse and a multi-vector side by side) and a JSON payload. Points live in **segments**. Writes go to small appendable segments; the optimizer merges them into larger segments and builds the HNSW graph once a segment crosses `indexing_threshold` (in kilobytes). This is the segmented write path of Stage 6.4, and it explains why `indexed_vectors_count` can lag `points_count`.

```mermaid
flowchart TD
    Coll["Collection: support"] --> Shard1["Shard 0"]
    Coll --> Shard2["Shard 1"]
    Shard1 --> WAL["WAL"]
    Shard1 --> SegA["Appendable segment: no HNSW yet, scanned exactly"]
    Shard1 --> SegB["Optimized segment: HNSW + payload indexes"]
    SegB --> Vec["Vector storage: RAM or mmap"]
    SegB --> Quant["Quantized codes"]
    SegB --> Pay["Payload storage + indexes"]
    SegB --> Graph["HNSW graph"]
```

Creating a collection and reading its state back (tested against Qdrant 1.20):

```bash
curl -s -X PUT http://localhost:6333/collections/support -H 'Content-Type: application/json' -d '{
  "vectors": { "size": 4, "distance": "Cosine" }
}'
curl -s -X PUT "http://localhost:6333/collections/support/points?wait=true" -H 'Content-Type: application/json' -d '{
  "points": [
    { "id": 1, "vector": [0.9, 0.1, 0, 0], "payload": { "tenant_id": "acme" } },
    { "id": 2, "vector": [0.8, 0.2, 0, 0], "payload": { "tenant_id": "globex" } }
  ]
}'
curl -s http://localhost:6333/collections/support
```

| Field in `GET /collections/{name}` | Meaning | What to do with it |
| --- | --- | --- |
| `status` | `green` (ready), `yellow` (optimizing), `grey` (optimizations pending until triggered), `red` (error) | Alert on `red`; expect `yellow` after bulk loads. |
| `optimizer_status` | `ok` or an error string | An error here means segments are not being merged or indexed. |
| `points_count` | Live points | Compare with your source of truth after a backfill. |
| `indexed_vectors_count` | Vectors already covered by an HNSW graph | Far below `points_count` means queries are scanning unindexed segments. |
| `segments_count` | Segments across local shards | Many small segments slow queries; the optimizer should merge them. |
| `config.hnsw_config`, `config.optimizer_config` | Effective settings, including defaults | Check `m`, `ef_construct`, `indexing_threshold` and `deleted_threshold` here, not in your client code. |

### 4.8 Inside Milvus: Growing and Sealed Segments, Consistency Levels

Milvus splits the same ideas across services. Inserts go through the proxy to the WAL (a message log), are applied to **growing segments** that query nodes search without an ANN index, and are **flushed** to object storage as **sealed segments** once they reach a size or time limit. Index nodes then build the vector index for each sealed segment. A search fans out to the query nodes holding the relevant segments and merges their top-k.

```mermaid
sequenceDiagram
    autonumber
    participant C as Client
    participant P as Proxy
    participant L as WAL (log service)
    participant D as Data / streaming node
    participant S as Object storage
    participant I as Index node
    participant Q as Query node

    C->>P: insert(rows)
    P->>L: append with timestamp
    L-->>D: consume
    D->>Q: growing segment, searchable by brute force
    D->>S: flush sealed segment
    S-->>I: build HNSW / IVF for the segment
    I->>S: write index files
    S-->>Q: load sealed segment + index
    C->>P: search(vector, consistency_level)
    P->>Q: query growing + sealed segments
    Q-->>C: merged top-k
```

Because every write carries a timestamp, Milvus lets each query choose how fresh its view must be:

| Consistency level | A search waits until the query node has applied... | Use for |
| --- | --- | --- |
| `Strong` | every write before the search's timestamp | Read-after-write tests, low write rates |
| `Bounded` (default) | writes older than a small staleness window | Most production search |
| `Session` | the writes made by this client | A user who must see their own upload |
| `Eventually` | nothing, it searches immediately | Highest throughput, analytics |

```python
from pymilvus import MilvusClient

client = MilvusClient("http://localhost:19530")
hits = client.search(
    collection_name="docs",
    data=[[0.12, -0.03, 0.88, 0.40]],
    limit=5,
    filter='tenant == "acme"',
    output_fields=["title"],
    search_params={"metric_type": "COSINE", "params": {"ef": 64}},
    consistency_level="Strong",     # override the collection default for this call
)
```

### 4.9 The Same Query in Six APIs

Every engine names the same concepts differently. Learn the mapping once and the APIs become syntax.

| Concept | pgvector | Qdrant | Milvus | Weaviate | Chroma | Elasticsearch |
| --- | --- | --- | --- | --- | --- | --- |
| Container | table + index | collection | collection | collection | collection | index |
| Record | row | point | entity | object | record (id, embedding, metadata, document) | document |
| Metadata | columns | payload | scalar fields / dynamic field | properties | metadata | fields |
| Query-time recall knob | `hnsw.ef_search` | `params.hnsw_ef` | `params.ef` | `ef` in the vector index config | `search_ef` in the collection's HNSW settings | `num_candidates` |
| Filter | `WHERE` | `filter` | `filter` expression | `filters` | `where` | `filter` inside `knn` |
| Tenant unit | column, partition, partial index | payload key with `is_tenant`, or shard key | partition key | tenant | collection or metadata | index, routing, or field |

"Top 5 nearest documents for tenant `acme`":

```sql
-- pgvector
SELECT id, title FROM docs WHERE tenant = 'acme' ORDER BY embedding <=> $1 LIMIT 5;
```

```bash
# Qdrant REST
curl -s -X POST http://localhost:6333/collections/docs/points/query -H 'Content-Type: application/json' -d '{
  "query": [0.12, -0.03, 0.88, 0.40], "limit": 5, "with_payload": ["title"],
  "filter": { "must": [ { "key": "tenant", "match": { "value": "acme" } } ] }
}'
```

```python
# Weaviate client v4
import weaviate
from weaviate.classes.query import Filter, MetadataQuery

with weaviate.connect_to_local() as client:
    docs = client.collections.get("Docs")
    res = docs.query.near_vector(
        near_vector=[0.12, -0.03, 0.88, 0.40],
        limit=5,
        filters=Filter.by_property("tenant").equal("acme"),
        return_metadata=MetadataQuery(distance=True),
    )
    for obj in res.objects:
        print(obj.properties["title"], obj.metadata.distance)
```

```python
# Chroma
import chromadb

client = chromadb.PersistentClient(path="./chroma-data")
docs = client.get_or_create_collection("docs")
docs.add(ids=["a1", "g1"], embeddings=[[0.1, 0.0, 0.9, 0.4], [0.9, 0.1, 0.0, 0.0]],
         metadatas=[{"tenant": "acme"}, {"tenant": "globex"}], documents=["Reset a password", "Billing hold"])
res = docs.query(query_embeddings=[[0.12, -0.03, 0.88, 0.40]], n_results=5, where={"tenant": "acme"})
print(res["ids"][0], res["distances"][0])
```

The Milvus and Elasticsearch forms are in 4.8 and 4.3. Two differences bite when porting code: **score direction** (Qdrant and Elasticsearch return similarity, higher is better; pgvector, Chroma and Weaviate's `distance` return distance, lower is better) and **default metric** (Chroma defaults to squared L2, so cosine-trained embeddings need the collection configured for cosine or normalised vectors).

### 4.10 Consistency, Durability & Transactions Compared

| Engine | Write acknowledged when | Read sees a write | Multi-record transaction | Backup unit |
| --- | --- | --- | --- | --- |
| pgvector | WAL is flushed (`synchronous_commit`), optionally on sync replicas | Immediately on the primary; replicas lag | Yes, full ACID with other tables | `pg_dump`, base backup + WAL archive |
| Qdrant | Written to the WAL of `write_consistency_factor` replicas; `wait=true` also waits until applied | After apply; `consistency` read parameter across replicas | No, per point (batches are not atomic across shards) | Collection or full snapshot |
| Milvus | Appended to the WAL | Depends on the query's consistency level (4.8) | No | Backup tool copying segment files and metadata |
| Weaviate | Per consistency level `ONE` / `QUORUM` / `ALL` | Same, plus async repair between replicas | No | Backup modules to object storage |
| Pinecone | Accepted by the service | Eventually; freshness is usually seconds | No | Collections / backups in the service |

The practical consequence: when vectors must change atomically with business rows (a product, its price and its embedding), pgvector gives that for free and every other engine needs an outbox or change-data-capture pipeline (Stage 6.6) plus idempotent upserts.

### 4.11 Choosing an Engine with a Capacity Estimate

Start from numbers: vector count in 12-24 months, dimensions, the recall target, the filter pattern and the write rate. Then size memory per layout with the starter's estimator:

```python
from src.learn_vector_databases.geometry import estimate_memory

for dtype in ("float32", "float16", "int8", "binary"):
    est = estimate_memory(count=100_000_000, dimensions=768, m=16, dtype=dtype)
    print(f"{dtype:>8}: vectors {est.vectors_bytes / 2**30:6.1f} GiB, "
          f"graph {est.graph_bytes / 2**30:5.1f} GiB, total {est.total_gib:6.1f} GiB")
```

```text
 float32: vectors  286.1 GiB, graph  11.9 GiB, total  298.0 GiB
 float16: vectors  143.1 GiB, graph  11.9 GiB, total  155.0 GiB
    int8: vectors   71.5 GiB, graph  11.9 GiB, total   83.4 GiB
  binary: vectors    8.9 GiB, graph  11.9 GiB, total   20.9 GiB
```

Multiply by the replication factor and add 30-50% for payloads, segment overhead and headroom for optimizer merges. 100 million float32 vectors with two replicas is roughly 800 GiB of RAM; the same data as SQ8 codes in RAM with originals on disk is closer to 230 GiB of RAM plus about 600 GiB of NVMe. That difference, not a benchmark chart, usually decides between "one large pgvector node", "a quantized Qdrant cluster" and "a managed service".

```mermaid
flowchart TD
    Start["New vector workload"] --> Q1{"Already on PostgreSQL and under ~50M vectors?"}
    Q1 -- yes --> Q2{"Need joins or ACID with business rows?"}
    Q2 -- yes --> PG["pgvector"]
    Q2 -- no --> PG2["pgvector first; revisit at scale"]
    Q1 -- no --> Q3{"Team can run stateful clusters?"}
    Q3 -- no --> Managed["Managed: Pinecone, Qdrant Cloud, Zilliz, Weaviate Cloud"]
    Q3 -- yes --> Q4{"Full-text search is the core product?"}
    Q4 -- yes --> ES["Elasticsearch / OpenSearch"]
    Q4 -- no --> Q5{"Billions of vectors, separate compute and storage?"}
    Q5 -- yes --> Milvus["Milvus"]
    Q5 -- no --> Qdrant["Qdrant or Weaviate"]
```

### 4.12 Pitfalls

| Pitfall | Symptom | Fix |
| --- | --- | --- |
| Porting code without checking score direction | Results come back in reverse order, or a `score > 0.8` threshold drops everything | Check whether the API returns distance or similarity; convert once in your client layer. |
| Chroma (or any engine) left on its default metric | Cosine-trained embeddings rank oddly; distances well above 1 | Configure cosine at collection creation or normalise vectors before insert. |
| Treating `points_count` as "searchable via HNSW" | Latency grows after a bulk load; `indexed_vectors_count` far below `points_count` | Wait for `status: green`, or check the optimizer; do not benchmark during indexing. |
| Reading a scale number from a vendor table | The cluster runs out of RAM well before the advertised size | Size with 4.11: vectors + graph + payload, times replicas, plus headroom. |
| Picking Milvus distributed for a 5M-vector app | Days spent on etcd, object storage and message queues | Use Milvus standalone or Lite, or a single-node engine, until scale requires more. |
| Assuming cross-record transactions in a vector database | A product row and its vector disagree after a partial failure | Use pgvector for atomicity, or an outbox plus idempotent upserts. |
| Running Redis vector search without a memory limit plan | `OOM command not allowed when used memory > 'maxmemory'` | Budget RAM for vectors and the graph; use quantized types or another engine for large corpora. |

### 4.13 Best Practices

- **Prototype on the engine you will run**: semantics differ (score direction, filters, consistency), so a prototype on Chroma does not validate a Milvus deployment.
- **Keep the embedding pipeline outside the database**: built-in vectorizers are convenient, but owning the model call makes migrations (M5) and batching explicit.
- **Estimate capacity before choosing**: one page of arithmetic (4.11) rules out more options than any feature matrix.
- **Read effective configuration from the server**: defaults change between versions; `GET /collections/{name}` or `\d+` in psql shows what is really set.
- **Prefer boring operations**: the engine your team can back up, restore and upgrade at 3 a.m. beats a slightly faster one it cannot.
- **Write an engine-neutral repository layer**: one interface for upsert, delete and filtered search keeps a later engine switch to a few hundred lines.

### 4.14 Hands-on Exercise

1. Start Qdrant (Stage 1.3), run the two `curl` commands in 4.7, then call `GET /collections/support`. **Expected:** `points_count: 2`, `indexed_vectors_count: 0`, because the segment is far below `indexing_threshold`; queries are exact until it grows.
2. Use `estimate_memory` to size 30 million 1,536-dim vectors at `m=16` in float32 and int8, with a replication factor of 2. **Expected:** about 172 GiB (float32) and 43 GiB (int8) of vectors per replica, plus 3.6 GiB of layer-0 graph in both cases; double everything for two replicas.
3. Port the pgvector query in 4.9 to one other engine of your choice and write down how its score differs. **Expected:** the same top-5 ids for the same normalised vectors, with distance turned into similarity (or the reverse).

Solutions: [`src/learn_vector_databases/geometry.py`](src/learn_vector_databases/geometry.py) (`estimate_memory`), [`tests/test_geometry.py`](tests/test_geometry.py), and the commands in 4.7 and 4.9.

[Back to top ⤴️](#-table-of-contents)

---

## 5. Stage 5: Filtering, Multi-Tenancy & Hybrid Search

Real queries carry business constraints: a tenant, a permission, a date range, an exact keyword. This stage shows why naive filtering breaks ANN recall, how engines filter inside the graph and plan by selectivity, how to isolate tenants, and how to fuse dense and lexical results. You need Stage 2 (HNSW) and the starter project; the SQL parts use the pgvector container from Stage 1.3.

### 5.1 The Filtering Dilemma: Post-Filtering vs Pre-Filtering Recall Collapse

Production vector queries rarely search the whole collection. They are constrained by metadata:

- "Find similar documents created by user 42 in 2026."
- "Find matching products in Electronics under $200."

There are two naive ways to combine a filter with an ANN index, and both fail somewhere:

```mermaid
flowchart TD
    subgraph PostFilter["1. Post-filtering: search, then filter"]
        P1["ANN search returns the global top ef candidates"]
        P1 --> P2["Apply WHERE category = 'Electronics'"]
        P2 --> P3["Selective filter: most candidates rejected, fewer than k rows left"]
    end

    subgraph PreFilter["2. Pre-filtering: filter, then brute force"]
        R1["Payload index returns every matching id"]
        R1 --> R2["Exact distance on each match"]
        R2 --> R3["Permissive filter: scores a large share of the collection"]
    end
```

1. **Post-filtering** runs the normal HNSW search for `ef` candidates and drops the ones that fail the filter. If 0.5% of documents match, the expected number of matches among 40 candidates is 0.2, so the result is usually empty.
2. **Pre-filtering** resolves the filter first and computes exact distances to every match. Recall is perfect, but when the filter matches 50% of a 100-million-vector collection, that is a 50-million-vector scan.

### 5.2 Single-Stage Payload-Filtered HNSW Graph Traversal

The third option, used by Qdrant, Weaviate, Milvus, Lucene and the starter, applies the filter **during** the graph walk:

```mermaid
flowchart TD
    Query["Query q with filter tenant = 'acme' AND price < 500"] --> Entry["Greedy descent to layer 0"]
    Entry --> Pop["Pop the closest unexpanded candidate"]
    Pop --> Nbrs["Score its neighbours"]
    Nbrs --> Check{"Neighbour passes the filter?"}
    Check -- yes --> Admit["Add to candidates AND to results"]
    Check -- no --> Bridge["Add to candidates only: it can still route the search"]
    Admit --> Stop{"results full and next candidate worse than worst result?"}
    Bridge --> Stop
    Stop -- no --> Pop
    Stop -- yes --> Done["Return the k best matching nodes"]
```

How it works:

1. The search navigates the graph as usual.
2. Each visited node is checked against the filter, typically with a bitmap from the payload index (5.6) rather than by parsing JSON.
3. A node that fails the filter is **not** added to the results, but its edges are still followed, so it acts as a bridge to matching nodes further away.
4. The search stops only when it holds `ef` **matching** results and no candidate can improve them.

This keeps recall high for moderately selective filters. It has its own failure mode: as the filter gets more selective, the walk must cross more non-matching nodes before it fills `ef` matching slots, so the cost climbs toward a full scan. If the matching nodes are not connected to each other through short paths, the walk can also miss them. Engines answer both problems in two ways: they build extra graph links among points that share a payload value (Qdrant's `payload_m`, 5.7), and a **query planner** switches to pre-filtering when the filter is very selective (5.4).

### 5.3 Measuring the Three Strategies in the Starter

[`src/learn_vector_databases/filtering.py`](src/learn_vector_databases/filtering.py) implements all three strategies over the starter HNSW and counts distance computations, which is the dominant cost of a vector query.

```python
from src.learn_vector_databases.filtering import (
    CountingHNSW, PayloadIndex, build_dataset, in_graph_search, post_filter_search, pre_filter_search,
)
from src.learn_vector_databases.vectordb import DistanceMetric

items = build_dataset(points=2000, dims=32)            # payload: bucket 0..99, tenant t0..t49
for it in items:
    it.payload["in_2"] = it.payload["bucket"] < 2      # a filter that matches about 2% of rows

hnsw = CountingHNSW(dimensions=32, metric=DistanceMetric.COSINE, M=16, ef_construction=64)
payload_index = PayloadIndex()
for it in items:
    hnsw.add(it)
    payload_index.add(it)

q, cond = items[0].vector, {"in_2": True}
for result in (post_filter_search(hnsw, q, 10, cond),
               in_graph_search(hnsw, payload_index, q, 10, cond),
               pre_filter_search(hnsw, payload_index, q, 10, cond)):
    print(result.strategy, len(result.hits), result.distance_calls)
```

`python -m src.learn_vector_databases.filtering` runs the full experiment: 2,000 clustered 32-dim vectors, 25 queries, `ef_search = 40`, recall@10 against exact filtered search.

| Filter matches | Strategy | Recall@10 | Distance computations |
| --- | --- | --- | --- |
| 50% (965 rows) | post-filter | 1.000 | 195 |
| 50% | in-graph | 1.000 | 214 |
| 50% | pre-filter | 1.000 | 965 |
| 10% (182 rows) | post-filter | 0.332 | 195 |
| 10% | in-graph | 1.000 | 953 |
| 10% | pre-filter | 1.000 | 182 |
| 2% (34 rows) | post-filter | 0.048 | 195 |
| 2% | in-graph | 1.000 | 2,058 |
| 2% | pre-filter | 1.000 | 34 |
| 0.5% (9 rows) | post-filter | 0.009 | 195 |
| 0.5% | in-graph | 1.000 | 2,058 |
| 0.5% | pre-filter | 1.000 | 9 |

Three lessons come out of one table:

- **Post-filtering costs the same at every selectivity and its recall falls with it**: at 2% it finds about one row in twenty.
- **In-graph filtering keeps recall, but its cost rises as the filter tightens**: at 2% it visits every node (2,058 calls is the whole graph plus the descent), because it never collects 40 matching results and so never meets its stopping condition.
- **Pre-filtering is cheapest exactly where in-graph is most expensive.** No single strategy wins, which is why engines plan.

| Line / API | Role | What happens at runtime |
| --- | --- | --- |
| `CountingHNSW._distance` | Instrumentation | Every distance call increments a counter; that number tracks query CPU. |
| `PayloadIndex.add` | Bitmap index | Sets bit `offset` in one Python-int bitmap per `(field, value)` pair. |
| `match_all(cond)` | Filter resolution | ANDs the bitmaps of each condition: one big-integer operation per condition. |
| `index._search_layer(..., accept=...)` | In-graph filter | `accept` decides admission to the results; every visited node is still expanded. |
| `pre_filter_search` | Exact over matches | Iterates the set bits and scores only those rows. |

### 5.4 Query Planning by Cardinality

A planner estimates how many points match the filter and picks a strategy before touching the graph:

```mermaid
flowchart TD
    F["Filter conditions"] --> Est["Estimate matching points from payload index statistics"]
    Est --> Small{"matches below threshold?"}
    Small -- yes --> Pre["Pre-filter: payload index lookup + exact scoring"]
    Small -- no --> Wide{"filter rejects most of the collection?"}
    Wide -- yes --> Graph["Filtered graph walk, helped by payload-specific links"]
    Wide -- no --> Plain["Filtered graph walk, filter checked per visited node"]
```

The starter's version is a few lines:

```python
from src.learn_vector_databases.filtering import planned_search

res = planned_search(hnsw, payload_index, q, 10, {"in_2": True}, brute_force_below=200)
print(res.strategy)        # planned->pre-filter: 34 matches is under the threshold
```

With `brute_force_below=200` the planner picked the cheapest exact strategy in every row of the 5.3 experiment: in-graph at 50% (214 calls) and pre-filter at 10%, 2% and 0.5% (182, 34 and 9 calls), all at recall 1.000.

How the real engines do it:

| Engine | Estimate from | Switches to exact scan when | Knob |
| --- | --- | --- | --- |
| Qdrant | Cardinality estimate from payload indexes | Estimated matches fall below `full_scan_threshold` (in KB of vectors, default 10,000) | `hnsw_config.full_scan_threshold`, per-query `params.exact` |
| pgvector | PostgreSQL statistics (`ANALYZE`) | The cost model prefers a B-tree / bitmap scan plus sort over the HNSW scan | Indexes you create, `hnsw.iterative_scan` |
| Weaviate | Filter result size | The filter matches fewer than `flatSearchCutoff` objects (default 40,000) | `flatSearchCutoff` in the vector index config |
| Milvus | Expression evaluation per segment | Implementation-specific per index type | Search params per index |

Unindexed payload fields defeat the planner: without a payload index there is no estimate, and every visited node needs a payload read. Index every field you filter on.

### 5.5 Filtering in pgvector: Iterative Scans, Partial Indexes and B-trees

pgvector's HNSW scan returns candidates in distance order and PostgreSQL applies `WHERE` on top, which is post-filtering. [`sql/04_filtering.sql`](sql/04_filtering.sql) loads 20,000 rows where tenant 1 owns 40% and 97 small tenants share the rest (about 0.6% each), then shows the problem and three fixes. Output from `pgvector/pgvector:pg17` with pgvector 0.8.7:

```text
NOTICE:  iterative_scan=off returned 1 of 10 rows
NOTICE:  iterative_scan=relaxed_order returned 10 of 10 rows
NOTICE:  filtered recall@10 = 1.00000000000000000000
NOTICE:  plan: Limit   ->  Index Scan using tickets_hnsw_t1 on tickets ...
```

**Fix 1: iterative index scans (0.8.0+).** The scan keeps walking the graph until `LIMIT` rows pass the filter or `hnsw.max_scan_tuples` is reached.

```sql
SET hnsw.iterative_scan = relaxed_order;   -- or strict_order to keep exact distance order
SET hnsw.max_scan_tuples = 20000;          -- upper bound on visited tuples per scan
SELECT id FROM tickets
WHERE tenant_id = 37
ORDER BY embedding <=> (SELECT embedding FROM tickets WHERE id = 1)
LIMIT 10;
```

**Fix 2: a partial HNSW index for a large tenant.** The planner uses it whenever the query repeats the predicate, and the walk only sees that tenant's rows.

```sql
CREATE INDEX tickets_hnsw_t1 ON tickets USING hnsw (embedding vector_cosine_ops) WHERE tenant_id = 1;
```

**Fix 3: a B-tree on the filter column for small tenants.** For a few hundred rows, exact scoring is cheaper and exact. With the index present the planner picks it on its own:

```text
 Limit
   ->  Sort
         Sort Key: ((tickets.embedding <=> (InitPlan 1).col1))
         ->  Bitmap Heap Scan on tickets
               Recheck Cond: (tenant_id = 37)
               ->  Bitmap Index Scan on tickets_tenant
```

| Tenant shape | pgvector layout | Why |
| --- | --- | --- |
| Few large tenants | Partial HNSW index per large tenant, or list partitioning by tenant | Each graph contains only that tenant's rows. |
| Many small tenants | B-tree on `tenant_id` + exact sort | A few hundred exact distances beat a graph walk. |
| Mixed | Both, plus a shared HNSW index with `iterative_scan` for medium tenants | The cost model picks per query once `ANALYZE` has run. |

### 5.6 Filter Optimization with Roaring Bitmaps

To check a filter in nanoseconds during a graph hop, engines keep one compressed bitmap per indexed value instead of evaluating conditions on raw payloads:

```mermaid
flowchart LR
    A["Bitmap: tenant = 'acme'"] --> AND["AND"]
    B["Bitmap: year = 2026"] --> AND
    AND --> R["Result bitmap: ids matching both"]
    R --> Card["Cardinality = popcount, feeds the planner"]
    R --> Test["Membership test per visited node"]
```

- **Compression**: Roaring bitmaps split the 32-bit id space into 65,536-id chunks and store each chunk as a sorted array of 16-bit values, a plain bitset or run-length runs, whichever is smallest.
- **Speed**: membership of one id is a chunk lookup plus a bit test; AND and OR of two bitmaps work chunk by chunk without decompressing.
- **Two jobs**: the same bitmap gives the planner its cardinality (`bit_count`) and gives the graph walk its per-node test.

The starter's `PayloadIndex` uses an uncompressed Python integer as the bitmap, which shows the operations without the compression:

```python
idx = PayloadIndex()
for i in range(10):
    idx.add(VectorItem(f"x{i}", [0.0], {"tenant": "a" if i < 4 else "b", "even": i % 2 == 0}))
both = idx.match_all({"tenant": "a", "even": True})   # bitmap AND
print(PayloadIndex.cardinality(both), list(idx.iter_ids(both)))   # 2 ['x0', 'x2']
```

### 5.7 Multi-Tenancy Isolation Patterns: Namespaces vs Collections vs Partition Keys

Multi-tenant SaaS products host thousands of customers in one deployment. The isolation pattern decides density, deletion cost and blast radius:

| Pattern | Mechanism | Pros | Cons / limits |
| :--- | :--- | :--- | :--- |
| **Collection per tenant** | Each tenant gets its own collection and HNSW index | Hard isolation; deleting a tenant is dropping a collection | Per-collection overhead (segments, WAL, threads, metadata); thousands of collections strain RAM and the control plane. |
| **Namespace / partition per tenant** | Logical partitions inside one index (Pinecone namespaces, Milvus partitions) | Clean separation; queries touch one partition | Limits on partitions per collection; some per-partition overhead. |
| **Shared collection + tenant key** | One collection, `tenant_id` in every payload, mandatory filter | Highest density; millions of tenants | Every query must carry the filter; isolation is a code-review concern. |
| **Shared + tenant-aware index** | Shared collection, but the engine groups data and graph links by tenant | Density of a shared collection with per-tenant locality | Engine-specific configuration. |
| **Tiered** | Small tenants shared; large tenants on dedicated shards or collections | Fits real, skewed tenant sizes | Placement logic and migrations between tiers. |

#### Qdrant: tenant-aware shared collection

Qdrant can build the HNSW graph per tenant inside a shared collection instead of one global graph. Set `m: 0` to skip the global graph and `payload_m` to build links among points with the same tenant value, and mark the tenant field with `is_tenant` so storage is grouped by tenant. Tested against Qdrant 1.20:

```bash
curl -s -X PUT http://localhost:6333/collections/support -H 'Content-Type: application/json' -d '{
  "vectors": { "size": 4, "distance": "Cosine" },
  "hnsw_config": { "payload_m": 16, "m": 0 }
}'
curl -s -X PUT http://localhost:6333/collections/support/index -H 'Content-Type: application/json' -d '{
  "field_name": "tenant_id",
  "field_schema": { "type": "keyword", "is_tenant": true }
}'
curl -s -X PUT http://localhost:6333/collections/support/index -H 'Content-Type: application/json' -d '{
  "field_name": "created_at", "field_schema": "datetime"
}'

curl -s -X POST http://localhost:6333/collections/support/points/query -H 'Content-Type: application/json' -d '{
  "query": [1, 0, 0, 0],
  "limit": 3,
  "filter": { "must": [
    { "key": "tenant_id", "match": { "value": "acme" } },
    { "key": "created_at", "range": { "gte": "2026-09-15T00:00:00Z" } }
  ] },
  "params": { "hnsw_ef": 128 },
  "with_payload": true
}'
```

With `m: 0` a query **without** a tenant filter has no global graph to use and falls back to a full scan. That is acceptable, even useful, when every query must carry a tenant anyway.

#### Production multi-tenant query in Qdrant (Python client)

```python
from qdrant_client import QdrantClient
from qdrant_client.models import FieldCondition, Filter, MatchValue

client = QdrantClient(host="localhost", port=6333)

hits = client.query_points(
    collection_name="enterprise_knowledge",
    query=[0.012, -0.045, 0.219, 0.812],
    query_filter=Filter(
        must=[
            FieldCondition(key="tenant_id", match=MatchValue(value="tenant_acme_corp")),   # isolation
            FieldCondition(key="is_confidential", match=MatchValue(value=False)),          # permission
        ]
    ),
    limit=5,
).points
```

### 5.8 Enterprise Multi-Tenancy in Milvus & Weaviate

#### A. Milvus partition keys

With a field marked `is_partition_key=True`, Milvus hashes its value to one of the collection's partitions. A filter on that field lets the search skip every other partition:

```python
from pymilvus import DataType, MilvusClient

client = MilvusClient("http://localhost:19530")

schema = MilvusClient.create_schema(auto_id=True)
schema.add_field("id", DataType.INT64, is_primary=True)
schema.add_field("tenant_id", DataType.VARCHAR, max_length=64, is_partition_key=True)
schema.add_field("embedding", DataType.FLOAT_VECTOR, dim=1536)

index_params = client.prepare_index_params()
index_params.add_index(field_name="embedding", index_type="HNSW", metric_type="COSINE",
                       params={"M": 16, "efConstruction": 128})
client.create_collection("tenant_documents", schema=schema, index_params=index_params)

res = client.search(
    "tenant_documents",
    data=[[0.05] * 1536],
    anns_field="embedding",
    filter='tenant_id == "tenant_acme"',     # routes to the partition that holds tenant_acme
    limit=5,
    search_params={"params": {"ef": 64}},
)
```

Many tenants hash into a fixed number of partitions, so the tenant filter is still needed inside the partition.

#### B. Weaviate tenants and activity states

Weaviate's native multi-tenancy gives each tenant its own shard inside a collection. Each tenant moves between states:

- **`ACTIVE`** (formerly `HOT`): loaded and queryable.
- **`INACTIVE`** (formerly `COLD`): on local disk, not loaded, no query memory used.
- **`OFFLOADED`**: moved to object storage by the offload module, freeing local disk.

```python
import weaviate
import weaviate.classes.config as wvc
from weaviate.classes.tenants import Tenant, TenantActivityStatus

client = weaviate.connect_to_local()
client.collections.create(
    name="SaaSKnowledge",
    multi_tenancy_config=wvc.Configure.multi_tenancy(enabled=True),
    properties=[wvc.Property(name="content", data_type=wvc.DataType.TEXT)],
)
col = client.collections.get("SaaSKnowledge")
col.tenants.create([
    Tenant(name="active_client_1", activity_status=TenantActivityStatus.ACTIVE),
    Tenant(name="dormant_client_9", activity_status=TenantActivityStatus.INACTIVE),
])
acme = col.with_tenant("active_client_1")      # every read and write is scoped to one tenant
client.close()
```

```mermaid
stateDiagram-v2
    [*] --> ACTIVE: tenant created
    ACTIVE --> INACTIVE: idle for N days
    INACTIVE --> ACTIVE: user logs in
    INACTIVE --> OFFLOADED: idle for months
    OFFLOADED --> ACTIVE: reactivate, data restored from object storage
    ACTIVE --> [*]: tenant deleted
```

### 5.9 Dynamic Tenant Rebalancing & Mitigating "Noisy Neighbors"

Tenant sizes in B2B products are heavily skewed: most tenants hold a few thousand vectors and query a few times a day, while a handful hold tens of millions and query constantly.

#### The noisy neighbour problem

When a large tenant bulk-loads data, segment merges and HNSW builds can take most of a node's CPU and disk bandwidth, and query latency for every small tenant on that node rises with it.

```mermaid
flowchart LR
    Router["Tenant router"] -->|"small tenants"| Shared["Shared pool: one collection, tenant filter"]
    Router -->|"whale tenants"| Dedicated["Dedicated shard or collection per whale"]
    Monitor["Size and QPS monitor"] -->|"tenant crosses threshold"| Move["Migrate tenant: copy, dual-write, switch route"]
    Move --> Dedicated
```

#### Remedies

1. **Tiered placement**: keep small tenants in a shared pool and move a tenant to its own shard or collection once it crosses a size or QPS threshold. In Qdrant this is custom sharding with a shard key per large tenant (distributed mode); in Milvus, a dedicated collection or database.
2. **Ingestion throttling**: rate-limit bulk writes per tenant and cap optimizer threads (`max_indexing_threads`, `max_optimization_threads`) so indexing cannot starve queries.
3. **Routing by partition key**: send a tenant's queries only to the shard that holds it (Stage 6.2), so one tenant's traffic does not fan out to every node.
4. **Per-tenant quotas**: limit vectors and QPS per plan, enforced in the API layer before the database.

### 5.10 Hybrid Search: Fusing Vector Proximity with Inverted Text Indexes

Dense embeddings capture meaning but blur exact tokens: product codes, error numbers, CVE ids, names. Lexical retrieval (BM25 or learned sparse vectors such as SPLADE) matches those tokens exactly but misses paraphrases. Hybrid search runs both and fuses the ranked lists.

```mermaid
flowchart LR
    Q["User query"] --> E["Dense encoder"]
    Q --> T["Tokenizer / sparse encoder"]
    E --> D["Dense ANN: top 25"]
    T --> S["Inverted index or sparse vectors: top 25"]
    D --> F["Fusion: RRF or score-based"]
    S --> F
    F --> R["Optional cross-encoder rerank (M2)"]
    R --> Out["Top k"]
```

#### BM25 in the starter

[`src/learn_vector_databases/hybrid.py`](src/learn_vector_databases/hybrid.py) has a small inverted index with Okapi BM25:

$$\text{score}(q, d) = \sum_{t \in q} \text{idf}(t) \cdot \frac{tf(t,d) \cdot (k_1 + 1)}{tf(t,d) + k_1 \cdot (1 - b + b \cdot |d| / \text{avgdl})}, \quad \text{idf}(t) = \ln\left(1 + \frac{N - n_t + 0.5}{n_t + 0.5}\right)$$

```python
from src.learn_vector_databases.hybrid import BM25Index, tokenize

print(tokenize("Patch CVE-2024-38077 now, v1.2.3!"))   # ['patch', 'cve-2024-38077', 'now', 'v1.2.3']

bm25 = BM25Index(k1=1.2, b=0.75)
bm25.add("kb1", "Patch for CVE-2024-38077 remote desktop licensing buffer overflow")
bm25.add("kb5", "Heap overflow mitigations in Windows services explained")
print(bm25.search("CVE-2024-38077 overflow"))           # kb1 first: it has the rare identifier
```

| Parameter | Effect | Typical value |
| --- | --- | --- |
| `k1` | How fast repeated terms stop adding score (term-frequency saturation) | 1.2-2.0 |
| `b` | How strongly long documents are penalised | 0.75 |
| `idf` | Rare terms weigh more than common ones | computed from document frequencies |

The tokenizer matters as much as the formula: the starter keeps `cve-2024-38077` as one token, while PostgreSQL's default parser splits it (5.12).

#### Hybrid search in Qdrant

Qdrant stores sparse vectors next to dense ones. With `"modifier": "idf"` on a sparse vector, the server applies IDF at query time, so the client only sends term frequencies (from a BM25-style tokenizer such as FastEmbed's `Qdrant/bm25` model). Tested against Qdrant 1.20:

```bash
curl -s -X PUT http://localhost:6333/collections/kb -H 'Content-Type: application/json' -d '{
  "vectors": { "dense": { "size": 4, "distance": "Cosine" } },
  "sparse_vectors": { "bm25": { "modifier": "idf" } }
}'

curl -s -X POST http://localhost:6333/collections/kb/points/query -H 'Content-Type: application/json' -d '{
  "prefetch": [
    { "query": [0.9, 0.4, 0, 0], "using": "dense", "limit": 20 },
    { "query": { "indices": [101, 202], "values": [1.0, 1.0] }, "using": "bm25", "limit": 20 }
  ],
  "query": { "fusion": "rrf" },
  "limit": 3
}'
```

The same request from Python:

```python
from qdrant_client import QdrantClient, models

client = QdrantClient(url="http://localhost:6333")
results = client.query_points(
    collection_name="kb",
    prefetch=[
        models.Prefetch(query=[0.9, 0.4, 0.0, 0.0], using="dense", limit=20),
        models.Prefetch(query=models.SparseVector(indices=[101, 202], values=[1.0, 1.0]), using="bm25", limit=20),
    ],
    query=models.FusionQuery(fusion=models.Fusion.RRF),
    limit=3,
)
```

Milvus 2.5+ can compute BM25 sparse vectors on the server from a text field (a `BM25` function in the schema), and Weaviate's `hybrid` query combines its own BM25 index with the vector index through an `alpha` weight.

### 5.11 Fusion Methods: RRF, Relative Score Fusion and DBSF

Dense and lexical scores live on unrelated scales (cosine 0-1, BM25 unbounded), so they cannot simply be added. Three fusion methods are in common use, all in [`hybrid.py`](src/learn_vector_databases/hybrid.py):

```python
def rrf(rankings, k=60, limit=10):
    """score(d) = sum over lists of 1 / (k + rank), rank starting at 1. Scores are ignored."""
    fused = {}
    for ranking in rankings:
        for rank, (doc_id, _score) in enumerate(ranking, start=1):
            fused[doc_id] = fused.get(doc_id, 0.0) + 1.0 / (k + rank)
    return sorted(fused.items(), key=lambda kv: (-kv[1], kv[0]))[:limit]
```

`python -m src.learn_vector_databases.hybrid` fuses a BM25 list and a dense list for the query "CVE-2024-38077 overflow":

```text
BM25:       [('kb1', 2.285), ('kb5', 0.931)]
dense:      [('kb2', 0.83), ('kb5', 0.8), ('kb1', 0.78), ('kb4', 0.61), ('kb3', 0.22)]
RRF:        [('kb1', 0.0323), ('kb5', 0.0323), ('kb2', 0.0164), ('kb4', 0.0156), ('kb3', 0.0154)]
RSF a=0.5:  [('kb1', 0.959), ('kb2', 0.5), ('kb5', 0.475), ('kb4', 0.32), ('kb3', 0.0)]
DBSF:       [('kb1', 1.263), ('kb5', 0.945), ('kb2', 0.633), ('kb4', 0.472), ('kb3', 0.186)]
```

`kb1`, the only document with the exact CVE id, is third on dense alone and first after any fusion. Under RRF it ties `kb5` to four decimals (ranks 3+1 against 2+2), which shows RRF's character: it rewards documents that both retrievers rank well and ignores how much better one score was.

| Method | Formula | Strength | Weakness | Engines |
| --- | --- | --- | --- | --- |
| RRF | $\sum 1 / (k + \text{rank})$, $k$ usually 60 | No score calibration needed; robust | Discards score gaps; a confident lexical hit counts like a weak one | Qdrant `fusion: rrf`, Elasticsearch `rrf` retriever, Milvus `RRFRanker`, Weaviate `rankedFusion` |
| Relative score fusion | min-max normalise each list, $\alpha \cdot \text{dense} + (1-\alpha) \cdot \text{lexical}$ | Keeps score gaps; one tunable weight | Sensitive to outliers and list length | Weaviate `relativeScoreFusion` (its default), Milvus `WeightedRanker` |
| DBSF | normalise each list with mean $\pm 3\sigma$, clip to 0-1, sum | Less sensitive to a single extreme score than min-max | Needs enough results per list for stable statistics | Qdrant `fusion: dbsf` |

Newer Qdrant releases also accept a parameterised form, `"query": { "rrf": { "k": 60 } }`. Tune fusion on judged queries (M1), not on intuition: the best `alpha` or `k` differs between a code-search corpus and a support-article corpus.

### 5.12 Hybrid Search in SQL with pgvector and `tsvector`

PostgreSQL can do both halves in one statement: a `tsvector` column with a GIN index for the lexical side and an HNSW index for the vector side, fused with RRF in SQL. From [`sql/05_hybrid.sql`](sql/05_hybrid.sql):

```sql
WITH lexical AS (
    SELECT id, row_number() OVER (ORDER BY ts_rank_cd(body_tsv, q) DESC, id) AS r
    FROM kb, websearch_to_tsquery('english', 'CVE-2024-38077 or overflow') AS q
    WHERE body_tsv @@ q
    ORDER BY r LIMIT 20
),
semantic AS (
    SELECT id, row_number() OVER (ORDER BY embedding <=> '[0.9, 0.4, 0.0, 0.0]', id) AS r
    FROM kb
    ORDER BY r LIMIT 20
)
SELECT id,
       coalesce(1.0 / (60 + l.r), 0) + coalesce(1.0 / (60 + s.r), 0) AS rrf,
       l.r AS lexical_rank, s.r AS semantic_rank
FROM lexical l
FULL OUTER JOIN semantic s USING (id)
ORDER BY rrf DESC, id;
```

```text
 id |   rrf   | lexical_rank | semantic_rank
----+---------+--------------+---------------
  4 | 0.03252 |            2 |             1
  1 | 0.03227 |            1 |             3
  2 | 0.01613 |              |             2
  3 | 0.01563 |              |             4
  5 | 0.01538 |              |             5
```

| Clause | Role | What happens at runtime |
| --- | --- | --- |
| `body_tsv ... GENERATED ALWAYS AS (to_tsvector(...)) STORED` | Lexical column | Kept in sync on every insert and update; indexed with GIN. |
| `websearch_to_tsquery('english', '... or ...')` | Query parsing | Turns user text into a `tsquery`; `or` becomes `\|`, quoted phrases become `<->`. |
| `row_number() OVER (ORDER BY ...)` | Ranks | RRF needs ranks, not scores. |
| `FULL OUTER JOIN ... USING (id)` | Union of both lists | A row found by only one side keeps its single contribution. |
| `coalesce(1.0 / (60 + r), 0)` | RRF term | Missing ranks contribute 0. |

The script ends with a check worth running on your own data:

```text
            tokens            |             query
------------------------------+--------------------------------
 '-2024':2 '-38077':3 'cve':1 | 'cve' <-> '-2024' <-> '-38077'
```

PostgreSQL's default parser splits `CVE-2024-38077` into `cve` and two signed integers, so a plain AND query for "CVE-2024-38077 overflow" matches nothing in this table. Identifiers, SKUs and error codes often need a custom text search configuration, a separate exact-match column, or a sparse encoder that keeps them whole.

### 5.13 Pitfalls

| Pitfall | Symptom | Fix |
| --- | --- | --- |
| Post-filtering a selective filter | Fewer than `k` results, or none; recall 0.05 at a 2% filter (5.3) | Use filter-aware search, iterative scans (pgvector) or pre-filtering for small match sets. |
| Filtering on an unindexed payload field | Filtered queries 10-100x slower than unfiltered ones | Create a payload index (Qdrant `PUT /collections/{c}/index`) or a B-tree / GIN index for every filter field. |
| pgvector filtered query without iterative scans | `LIMIT 10` returns 1 row (`iterative_scan=off returned 1 of 10 rows`) | `SET hnsw.iterative_scan = relaxed_order` and size `hnsw.max_scan_tuples`. |
| `relaxed_order` results used as if sorted | Rank 3 has a smaller distance than rank 2 | Re-sort in an outer query (`sql/04_filtering.sql`) or use `strict_order`. |
| A query path that forgets the tenant filter | Data from another tenant appears in results | Enforce the filter in one repository function; with Qdrant `m: 0`, unfiltered queries degrade to scans, which shows up in monitoring. |
| Collection per tenant at thousands of tenants | Node RAM and file handles climb with tenant count; slow startup | Shared collection with a tenant key, or tiered placement (5.9). |
| Adding BM25 and cosine scores directly | Lexical scores (5-20) swamp cosine (0-1), or the reverse | Use RRF, or normalise per list (relative score fusion, DBSF). |
| Default text tokenizer on identifiers | Exact codes never match lexically (`'cve' <-> '-2024' <-> '-38077'`) | Inspect `to_tsvector` output; add a keyword column or custom configuration. |
| Sparse vector indices from two different vocabularies | Hybrid results look random after a tokenizer upgrade | Version the sparse encoder with the collection, like an embedding model. |

### 5.14 Best Practices

- **Index every field you filter on**: the planner needs cardinality estimates and the graph walk needs cheap membership tests.
- **Make the tenant filter impossible to forget**: build it in a single repository function and test that unfiltered calls fail.
- **Measure filtered recall, not just unfiltered recall**: benchmark at the selectivities your real filters have (M1).
- **Match the isolation pattern to the tenant size distribution**: shared for the long tail, dedicated for the few large tenants.
- **Start hybrid with RRF**: it needs no score calibration; move to a weighted method only with judged queries showing a gain.
- **Retrieve more than you return**: prefetch 20-100 candidates per retriever, fuse, then cut to `k`, so fusion has material to work with.
- **Keep lexical and dense indexes in the same write path**: a document visible to one retriever and not the other produces confusing results.

### 5.15 Hands-on Exercise

1. Run `python -m src.learn_vector_databases.filtering`, then call `selectivity_report(ef_search=200)`. **Expected:** post-filtering now costs 505 distance computations at every selectivity (2.6x more) and reaches recall 1.0 at 10%, but only 0.316 at 2% and 0.089 at 0.5%. The planner's pre-filter rows are unchanged; its in-graph row at 50% rises from 214 to 934 calls, the price of a wider beam.
2. In `sql/04_filtering.sql`, rerun the tenant 37 query with `hnsw.iterative_scan = strict_order` and compare the order with `relaxed_order`. **Expected:** the same 10 ids; `strict_order` returns them already sorted by distance.
3. Add a third retriever to the hybrid demo: a "title match" list `[("kb4", 1.0)]`. Fuse with `rrf([dense, sparse, title])`. **Expected:** `kb4` moves from fourth to third (0.0320, just behind `kb1` and `kb5`) because it now appears in two lists; this is how RRF rewards agreement between retrievers.

Solutions: [`src/learn_vector_databases/filtering.py`](src/learn_vector_databases/filtering.py), [`src/learn_vector_databases/hybrid.py`](src/learn_vector_databases/hybrid.py), [`tests/test_stages_4_6.py`](tests/test_stages_4_6.py), [`sql/04_filtering.sql`](sql/04_filtering.sql), [`sql/05_hybrid.sql`](sql/05_hybrid.sql).

[Back to top ⤴️](#-table-of-contents)

---

## 6. Stage 6: Distributed Scaling & Production Operations

One machine eventually runs out of RAM, CPU or write throughput. This stage covers how vector databases shard and replicate, how their write path stays fast, and the routines (bulk loading, snapshots, alias swaps, monitoring, capacity planning) that keep them healthy. Every mechanism has a small runnable model in the starter: [`cluster.py`](src/learn_vector_databases/cluster.py) for routing and quorums, [`segments.py`](src/learn_vector_databases/segments.py) for the write path, and [`sql/06_operations.sql`](sql/06_operations.sql) for pgvector operations.

### 6.1 Distributed Topologies: Coordinators, Shard Replicas & Raft Consensus

Past a few hundred million vectors, a single node's RAM and CPU are exhausted. Distributed vector databases (Qdrant in distributed mode, Milvus, Weaviate, Pinecone) shard collections across nodes and replicate each shard:

```mermaid
flowchart TD
    Client["Client traffic: gRPC / REST"] --> LB["Load balancer"]

    subgraph Cluster["Distributed vector cluster"]
        LB --> Coord1["Node 1 (receives the request)"]
        LB --> Coord2["Node 2"]

        Raft["Raft: collection config, shard map, membership"]
        Coord1 <--> Raft
        Coord2 <--> Raft

        subgraph Shard1["Shard 1"]
            S1a["Replica on node A"] <--> S1b["Replica on node B"]
        end
        subgraph Shard2["Shard 2"]
            S2a["Replica on node C"] <--> S2b["Replica on node D"]
        end
        subgraph Shard3["Shard 3"]
            S3a["Replica on node E"] <--> S3b["Replica on node F"]
        end

        Coord1 --> Shard1
        Coord1 --> Shard2
        Coord1 --> Shard3
    end
```

#### How clustered vector search works

1. **Scatter**: the node that receives the query looks up the shard map. Without a shard key it sends the query to one replica of every shard in parallel.
2. **Local search**: each shard runs its own HNSW search and returns its local top-k.
3. **Gather**: the receiving node merges the lists by distance and returns the global top-k.

Raft (or another consensus protocol) is used for **metadata**: which collections exist, their settings and where each shard lives. Point data is usually replicated by the engine's own replication protocol, not through Raft, because pushing every vector through a consensus log would limit write throughput. Qdrant and Weaviate (for schema since 1.25) work this way; Milvus keeps metadata in etcd and data in its WAL and object storage.

### 6.2 Sharding: Hash Routing, Consistent Hashing and Shard Keys

Placement is a function from a key (the point id or a tenant id) to a shard. [`cluster.py`](src/learn_vector_databases/cluster.py) compares the options:

```python
from src.learn_vector_databases.cluster import ConsistentHashRing, moved_fraction, shard_for

keys = [f"doc-{i}" for i in range(10_000)]
before = {k: shard_for(k, 4) for k in keys}
after = {k: shard_for(k, 5) for k in keys}
print(f"modulo 4 -> 5 shards moves {moved_fraction(keys, before, after):.0%} of keys")

ring = ConsistentHashRing([f"node{i}" for i in range(4)], vnodes=64)
before = {k: ring.node_for(k) for k in keys}
ring.add_node("node4")
after = {k: ring.node_for(k) for k in keys}
print(f"consistent hashing 4 -> 5 nodes moves {moved_fraction(keys, before, after):.0%} of keys")
```

```text
modulo 4 -> 5 shards moves 80% of keys
consistent hashing 4 -> 5 nodes moves 18% of keys
```

```mermaid
flowchart LR
    K["key: tenant_id or point id"] --> H["blake2b hash, 64-bit"]
    H --> Mod{"Routing scheme"}
    Mod -- "modulo N" --> S["shard = hash mod N; resharding moves most keys"]
    Mod -- "ring with virtual nodes" --> R["next node clockwise; adding a node moves about 1/N"]
    Mod -- "custom shard key" --> C["explicit shard per key value; queries name the shard"]
```

| Line / API | Role | What happens at runtime |
| --- | --- | --- |
| `stable_hash` | Deterministic hash | blake2b gives the same value in every process. Python's `hash()` is salted per process and would scatter data differently on each restart. |
| `shard_for(key, n)` | Modulo routing | Cheap, uniform, but tied to `n`. |
| `ConsistentHashRing(vnodes=64)` | Ring routing | 64 positions per node smooth the load; a new node takes over arcs from all others. |
| `ShardedCollection.search(..., shard_key_value=...)` | Targeted query | With a shard key, one shard is searched instead of all of them (`touched == 1` in the tests). |

Engines expose the same choices. Qdrant hashes point ids over a fixed `shard_number` set at creation, and moves whole shards between nodes when the cluster grows, so it pays to create more shards than nodes up front. Its custom sharding (`"sharding_method": "custom"`, distributed mode only) lets a large tenant get its own shard key. Milvus routes by primary key hash into a fixed number of shards per collection and spreads segments across query nodes, so adding query nodes rebalances segments rather than rehashing keys.

```bash
# Qdrant: 6 shards on a 3-node cluster leaves room to rebalance onto 6 nodes later
curl -s -X PUT http://localhost:6333/collections/docs_v1 -H 'Content-Type: application/json' -d '{
  "vectors": { "size": 768, "distance": "Cosine" },
  "shard_number": 6,
  "replication_factor": 2,
  "write_consistency_factor": 1
}'
curl -s http://localhost:6333/collections/docs_v1/cluster     # local and remote shards, their state, transfers
```

Scatter-gather has a cost that grows with shard count: every query does `shards x ef_search` work and the slowest shard sets the latency. Each shard must also return its own top-k (not top-k divided by shards), because the global winners can all sit on one shard.

### 6.3 Replication and Consistency: Quorums in Practice

With N replicas, a write acknowledged by W of them and a read that asks R of them is guaranteed to see that write only when the two sets overlap, that is when $R + W > N$. `ReplicatedValue` in the starter models this:

```python
from src.learn_vector_databases.cluster import ReplicatedValue, overlapping

value = ReplicatedValue(n=3)
value.write("v1", w=3)
value.write("v2", w=1)                       # acknowledged by one replica only
print(value.read(r=1, start=2), overlapping(3, 1, 1))   # v1 False  -> stale read
print(value.read(r=3, start=2), overlapping(3, 1, 3))   # v2 True   -> sees the latest write
```

```mermaid
sequenceDiagram
    participant C as Client
    participant A as Replica A
    participant B as Replica B
    participant D as Replica C
    C->>A: write v2 (W = 1)
    A-->>C: ack
    Note over B,D: still hold v1 until async replication catches up
    C->>D: read (R = 1)
    D-->>C: v1, stale
    C->>A: read (R = 3)
    C->>B: read
    C->>D: read
    A-->>C: v2 (newest version wins)
```

| Engine | Write setting | Read setting | Default behaviour |
| --- | --- | --- | --- |
| Qdrant | `write_consistency_factor` (replicas that must confirm); `ordering` = `weak` / `medium` / `strong` per update | `?consistency=` an integer, `majority`, `quorum` or `all` | Factor 1, reads from one replica |
| Weaviate | Consistency level `ONE` / `QUORUM` / `ALL` per request | Same levels | `QUORUM`, with read repair |
| Milvus | Writes go through the WAL | `consistency_level` per query (4.8) | `Bounded` |
| pgvector | `synchronous_commit` and `synchronous_standby_names` | Read from the primary, or from replicas that may lag | Async replicas |

Vector search usually tolerates slightly stale reads: a document that appears a second late rarely matters. Reads that follow the user's own write (upload a file, then search it) do matter; use read-your-writes for that path only (`consistency=majority` in Qdrant, `Session` in Milvus, the primary in PostgreSQL).

### 6.4 High-Throughput Write Pipelines: WAL, Segment Immutability & Compaction

Inserting one vector into a live HNSW graph updates dozens of neighbour lists and contends with concurrent searches. Vector engines borrow the log-structured design of LSM trees and Lucene instead:

```mermaid
flowchart TD
    Insert["Batch upsert"] --> WAL["1. Append to the WAL: durability point"]
    WAL --> Grow["2. Apply to a growing segment: small, searched exactly"]
    Grow --> Full{"Growing segment over the threshold?"}
    Full -- yes --> Seal["3. Seal: the segment becomes immutable"]
    Seal --> Build["4. Background build: HNSW graph, quantized codes"]
    Build --> Disk["5. Sealed segment on disk, mmap or RAM"]
    Disk --> Compact{"Too many small segments or tombstones?"}
    Compact -- yes --> Merge["6. Compaction: rebuild live points into one segment"]
```

- **Writes never wait for graph construction**: they are durable once in the WAL and searchable once applied to the growing segment.
- **Graphs are built once per segment**, on background threads, from a fixed set of points, which is faster and gives better graphs than incremental inserts.
- **Updates and deletes are tombstones** on sealed segments; the graph is left alone until compaction rebuilds it (Qdrant's `deleted_threshold`, default 0.2, triggers this vacuum).

### 6.5 The Write Path in Code

[`SegmentedCollection`](src/learn_vector_databases/segments.py) implements that pipeline in about 200 lines:

```python
import os, random, tempfile

from src.learn_vector_databases.segments import SegmentedCollection
from src.learn_vector_databases.vectordb import VectorItem, l2_normalize

rng = random.Random(5)
with tempfile.TemporaryDirectory() as tmp:
    wal = os.path.join(tmp, "wal.jsonl")
    col = SegmentedCollection(dimensions=16, seal_threshold=100, wal_path=wal)
    for i in range(450):
        col.upsert(VectorItem(f"p{i}", l2_normalize([rng.gauss(0, 1) for _ in range(16)])))
    print(col.stats())
    for i in range(0, 200, 2):
        col.delete(f"p{i}")
    print(col.stats())
    print(col.compact(min_dead_ratio=0.3), col.stats())
    print(SegmentedCollection.recover(wal, dimensions=16, seal_threshold=100).stats())
```

```text
{'points': 450, 'growing': 50, 'sealed_segments': 4, 'tombstones': 0, 'wal_seq': 450}
{'points': 350, 'growing': 50, 'sealed_segments': 4, 'tombstones': 100, 'wal_seq': 550}
1 {'points': 350, 'growing': 50, 'sealed_segments': 3, 'tombstones': 0, 'wal_seq': 550}
{'points': 350, 'growing': 50, 'sealed_segments': 4, 'tombstones': 100, 'wal_seq': 550}
```

| Line / API | Role | What happens at runtime |
| --- | --- | --- |
| `_log(record)` | WAL append | One JSON line per operation; with `fsync=True`, `os.fsync` makes it durable before the call returns. |
| `upsert` | Write | Tombstones any previous version, adds to the growing segment, seals at `seal_threshold`. |
| `seal()` | Freeze + build | Builds one HNSW index from the growing points; the location map now points at the sealed segment. |
| `delete` | Tombstone | Adds the id to the segment's `deleted` set; the graph still contains the node and uses it for routing. |
| `search` | Fan-out + merge | Exact search on the growing segment, filtered HNSW on each sealed one (tombstones rejected by `accept`), then a k-way merge. |
| `compact(min_dead_ratio)` | Vacuum | Rebuilds the segments above the threshold from their live points; here two half-dead segments became one. |
| `recover(wal_path)` | Crash recovery | Replays the log in order and stops at a torn final line, rebuilding the exact pre-crash state (tombstones included, since compaction was not logged). |

Real engines add two things the model leaves out: they **truncate the WAL** after the data it covers is safely in flushed segments, and they **snapshot** segment files so recovery does not replay the whole history.

### 6.6 High-Throughput Ingestion: Batching, Bulk Loads and Kafka

Point-by-point HTTP upserts waste most of their time on round trips. A production ingestion path buffers and batches:

```mermaid
flowchart LR
    Src["Source of truth: DB, object store"] --> CDC["CDC / outbox events"]
    CDC --> Kafka["Kafka topic: document changes"]
    Kafka --> Embed["Embedding workers (GPU), batched"]
    Embed --> Out["Kafka topic: vectors"]
    Out --> Sink["Ingestion service: micro-batches of 256-2,000 points"]
    Sink --> VDB["Vector DB batch upsert (gRPC)"]
    Sink -.->|"failures"| DLQ["Dead-letter topic"]
```

- **Backpressure**: when the database is compacting, the topic absorbs the backlog instead of the embedding workers failing.
- **Idempotency**: key every point by a deterministic id derived from the document (for example a UUIDv5 of `tenant:doc_id:chunk`), so redelivered messages overwrite rather than duplicate.
- **Ordering**: partition the topic by document id so an update never overtakes an older version of the same document.
- **Batch size**: a few hundred to a few thousand points per request keeps both the network and the WAL efficient; measure, because the right size depends on dimensions and payload size.

For an initial bulk load, building the graph while data streams in wastes work. In Qdrant, turn indexing off for the load and back on afterwards, so each segment's graph is built once:

```bash
# Before the load: no HNSW builds (indexing_threshold 0 disables indexing)
curl -s -X PATCH http://localhost:6333/collections/docs_v1 -H 'Content-Type: application/json' \
  -d '{"optimizers_config": {"indexing_threshold": 0}}'

# ... upsert in parallel batches with wait=false ...

# After the load: restore the default (10000 KB in current releases) and let the optimizer build graphs
curl -s -X PATCH http://localhost:6333/collections/docs_v1 -H 'Content-Type: application/json' \
  -d '{"optimizers_config": {"indexing_threshold": 10000}}'
```

In pgvector the equivalent is loading with `COPY` into a table without the HNSW index, then `CREATE INDEX` with a large `maintenance_work_mem` and parallel workers (6.9).

### 6.7 Hardware Acceleration: SIMD, AVX-512, and ARM Neon Vectorization

Distance computation dominates query CPU: a 1,536-dim float32 dot product is 1,536 multiply-adds, done thousands of times per query. SIMD registers do many of them per instruction:

```mermaid
flowchart TD
    subgraph Scalar["Scalar: one multiply-add per instruction"]
        S1["a0 * b0"] --> S2["a1 * b1"] --> S3["a2 * b2"]
    end

    subgraph SIMD["AVX-512: 16 float32 lanes per instruction"]
        V512["512-bit register holds 16 floats of a and 16 of b"]
        V512 --> FMA["_mm512_fmadd_ps: 16 fused multiply-adds at once"]
    end
```

#### Instruction sets in use

- **x86-64**: AVX2 (256-bit, 8 float32 lanes), AVX-512 (16 lanes) and AVX-512 VNNI for int8 dot products, which is why SQ8 can be faster than float32.
- **ARM64 (Apple Silicon, AWS Graviton)**: Neon (128-bit, 4 float32 lanes) and SVE (scalable vector length).
- **Bit operations**: `POPCNT` and AVX-512 `VPOPCNTDQ` make binary-quantized Hamming distance a few instructions per 512 bits.

Engines detect the CPU at runtime and pick the widest kernel available. Two operational consequences: benchmark on the instance type you will run (an AVX-512 laptop result does not transfer to a Graviton node), and in containers make sure the image is not compiled for a lower baseline than the hardware supports. Hand-vectorised kernels typically run several times faster than scalar code; the gain depends on dimension, data type and whether the data is in cache.

### 6.8 Linux OS Page Cache Tuning for On-Disk Vector Storage

When vectors or graphs are memory-mapped (Qdrant `on_disk`, Milvus mmap, Lucene), the kernel's page cache is the vector cache, and its settings show up directly in p99 latency:

```bash
# /etc/sysctl.d/90-vector-db.conf, then: sudo sysctl --system

# Prefer dropping page cache over swapping out the database's own heap.
vm.swappiness = 1

# Start background writeback earlier so flushes do not stall queries.
vm.dirty_background_ratio = 5
vm.dirty_ratio = 10

# Large deployments map many segment files; the default (65530) can be too low.
vm.max_map_count = 1048576
```

```bash
# Is the working set in RAM? Watch major page faults and disk reads during load.
vmstat 1 5                       # "si"/"so" should be 0; high "bi" means reads from disk
cat /proc/$(pgrep -f qdrant)/status | grep -E 'VmRSS|VmSwap'
```

Size RAM so the hot part of the mmap'd data (the graph, and the quantized codes when they are not pinned with `always_ram`) fits in the page cache. Disk-backed layouts are fine on local NVMe and painful on network block storage, where each cache miss is a network round trip.

### 6.9 Snapshot Backups, Recovery & Zero-Downtime Index Rebuilding

#### 1. Snapshots in Qdrant

A snapshot is an archive of a collection's segments and configuration, created while the collection keeps serving traffic. Tested against Qdrant 1.20:

```bash
# Create, list, then download a snapshot of one collection
curl -s -X POST http://localhost:6333/collections/docs_v1/snapshots
curl -s http://localhost:6333/collections/docs_v1/snapshots
curl -s -o docs_v1.snapshot \
  "http://localhost:6333/collections/docs_v1/snapshots/<name-from-the-list>"

# Restore on another node from a URL or a local file path the server can read
curl -s -X PUT http://localhost:6333/collections/docs_v1/snapshots/recover -H 'Content-Type: application/json' \
  -d '{"location": "file:///qdrant/snapshots/docs_v1/<name>.snapshot"}'
```

In a cluster, snapshots are per node and per shard; back up every node, or use the managed offering's backup feature, and practise a restore before you need one.

#### 2. pgvector: concurrent rebuilds and build settings

From [`sql/06_operations.sql`](sql/06_operations.sql):

```sql
SET maintenance_work_mem = '256MB';            -- a graph that fits in memory builds much faster
SET max_parallel_maintenance_workers = 2;      -- parallel HNSW builds (pgvector 0.6.0+)
REINDEX INDEX CONCURRENTLY tickets_hnsw;       -- rebuild without blocking writes

SELECT c.relname, pg_size_pretty(pg_relation_size(c.oid)) AS size
FROM pg_class c
WHERE c.relname IN ('tickets', 'tickets_hnsw', 'tickets_hnsw_t1', 'tickets_tenant')
ORDER BY pg_relation_size(c.oid) DESC;
```

```text
     relname     |  size
-----------------+---------
 tickets_hnsw    | 7216 kB
 tickets_hnsw_t1 | 2904 kB
 tickets         | 2288 kB
 tickets_tenant  | 160 kB
```

The HNSW index on 20,000 16-dim vectors is three times the size of the table. Graph links per vector do not shrink with the dimension, so at low dimensions the index dominates; at 1,536 dimensions the vectors do. Watch a long build from another session with `SELECT phase, blocks_done, blocks_total FROM pg_stat_progress_create_index;`.

#### 3. Zero-downtime rebuilds with aliases (blue/green collections)

When the embedding model changes (768 to 1,536 dimensions) or the index parameters change (`m=16` to `m=32`), build a new collection next to the old one and switch an alias atomically:

```mermaid
flowchart LR
    App["Application queries alias: docs"] --> Alias{"alias docs"}
    Alias -->|"before"| V1["docs_v1: old model, live"]
    Alias -.->|"after one atomic switch"| V2["docs_v2: new model, built in the background"]
    Ingest["Ingestion: dual-write to v1 and v2 during the rebuild"] --> V1
    Ingest --> V2
```

```bash
curl -s -X POST http://localhost:6333/collections/aliases -H 'Content-Type: application/json' -d '{
  "actions": [
    { "delete_alias": { "alias_name": "docs" } },
    { "create_alias": { "alias_name": "docs", "collection_name": "docs_v2" } }
  ]
}'
curl -s http://localhost:6333/aliases
```

All actions in one request are applied together, so no query sees the alias missing. PostgreSQL gets the same guarantee from transactional DDL: `sql/06_operations.sql` swaps a view from `tickets` to a re-embedded `tickets_v2` inside `BEGIN ... COMMIT`. Masterclass M5 covers the full migration, including dual writes and shadow comparison.

### 6.10 Observability: What to Measure and Alert On

A vector database can be "up" and still wrong: recall can drift after deletes, a config change or a model update, without a single error. Monitor quality as well as health:

| Signal | Source | Alert when |
| --- | --- | --- |
| p50 / p99 search latency, by collection and filter shape | Application metrics, Qdrant `/metrics` | p99 above SLO for 5 minutes |
| QPS and error rate (timeouts, 5xx, `RESOURCE_EXHAUSTED`) | Application, gRPC metrics | Error rate above 1% |
| `points_count` vs source-of-truth count | Collection info vs database | Drift above 0.1% for an hour |
| `indexed_vectors_count / points_count` | Collection info | Below 0.95 outside bulk loads |
| Segment count, optimizer status | Collection info | Optimizer error; segment count climbing for hours |
| RAM, page-cache hit rate, major faults, disk read latency | Node exporter | RSS near the limit; sustained major faults |
| Replica state, shard transfers | `GET /collections/{c}/cluster` | Any replica not `Active` for 10 minutes |
| **Recall canary** | Scheduled job: ANN vs exact on a fixed query sample | Recall below target (for example 0.95) |
| Ingestion lag | Kafka consumer lag | Lag above the freshness SLO |

The recall canary is the signal teams most often miss. It needs a fixed sample of real queries and an exact search over the same data (a flat index, `params.exact: true` in Qdrant, or a sequential scan in PostgreSQL):

```python
import random

from src.learn_vector_databases.sweep import make_clustered
from src.learn_vector_databases.vectordb import DistanceMetric, ExactKNNIndex, HNSWIndex, VectorItem, recall_at_k


def recall_canary(index, exact, sample_queries, k=10, ef_search=None):
    """Mean recall@k of the live index against exact search on a fixed query sample."""
    scores = [recall_at_k(index.search(q, k=k, ef_search=ef_search), exact.search(q, k), k) for q in sample_queries]
    return sum(scores) / len(scores)


vectors = make_clustered(1500, 32, spread=1.0)
hnsw = HNSWIndex(dimensions=32, metric=DistanceMetric.COSINE, M=8, ef_construction=32)
exact = ExactKNNIndex(metric=DistanceMetric.COSINE)
for i, v in enumerate(vectors):
    item = VectorItem(f"p{i}", v)
    hnsw.add(item)
    exact.add(item)

queries = random.Random(1).sample(vectors, 30)
for ef in (10, 64):
    value = recall_canary(hnsw, exact, queries, ef_search=ef)
    print(f"ef_search={ef:<3} recall@10={value:.3f} {'OK' if value >= 0.95 else 'ALERT'}")
```

```text
ef_search=10  recall@10=0.997 OK
ef_search=64  recall@10=1.000 OK
```

```mermaid
flowchart LR
    Cron["Scheduler, every 15 min"] --> Sample["Fixed sample of 200 real queries"]
    Sample --> ANN["Production query path"]
    Sample --> Exact["Exact search, same filters"]
    ANN --> Cmp["recall@k"]
    Exact --> Cmp
    Cmp --> Metric["Gauge: vector_recall_canary"]
    Metric --> Alert{"below target?"}
    Alert -- yes --> Page["Alert with collection, filter shape, config version"]
```

Qdrant exposes Prometheus metrics at `GET /metrics` (for example `app_info`, `collections_total`, request counters and latency histograms); PostgreSQL has `pg_stat_statements` and `pg_stat_user_indexes` (`idx_scan` shows whether the HNSW index is used at all).

### 6.11 Capacity Planning and Cost

Capacity planning turns the Stage 3 and 4.11 arithmetic into a node count:

| Input | Example |
| --- | --- |
| Vectors in 18 months | 200 million |
| Dimensions, model | 1,024, cosine |
| Layout | SQ8 codes in RAM, float32 originals on NVMe, graph in RAM |
| Replication factor | 2 |
| Peak QPS, recall target | 800 QPS at recall@10 >= 0.95, p99 < 80 ms |

```python
from src.learn_vector_databases.geometry import estimate_memory

codes = estimate_memory(200_000_000, 1024, m=16, dtype="int8")
originals = estimate_memory(200_000_000, 1024, m=16, dtype="float32").vectors_bytes
ram_per_replica = codes.total_bytes * 1.4                # +40% for payload indexes, segments, headroom
print(f"RAM per replica  {ram_per_replica / 2**30:,.0f} GiB")
print(f"RAM total        {2 * ram_per_replica / 2**30:,.0f} GiB")
print(f"NVMe total       {2 * originals / 2**30:,.0f} GiB")
```

```text
RAM per replica  300 GiB
RAM total        601 GiB
NVMe total       1,526 GiB
```

With 128 GiB nodes and 70% usable for the database, that is about seven nodes; round up to eight so that losing one still leaves capacity, and create at least 16 shards so they spread evenly. Then validate QPS with a benchmark on one node holding one shard's worth of data (M1) and scale out by the measured per-node throughput, not by the RAM figure alone.

| Lever | Saves | Costs |
| --- | --- | --- |
| float32 to SQ8 with rescoring | ~4x vector RAM | Small recall loss, rescoring reads |
| Smaller model or Matryoshka truncation (M4) | RAM and CPU proportional to dimensions | Some recall; re-embedding |
| Lower `m` | Graph RAM | Recall at a given `ef_search` |
| Tiered tenants (5.9), offloading inactive tenants | RAM for idle data | Cold-start latency on reactivation |
| Replication factor 2 instead of 3 | One third of the fleet | Less headroom during node loss |

### 6.12 Pitfalls

| Pitfall | Symptom | Fix |
| --- | --- | --- |
| Routing with Python's `hash()` or another per-process hash | Points "disappear" after a restart; each process routes differently | Use a stable hash (`stable_hash` with blake2b) or the engine's own routing. |
| Fewer shards than future nodes | New nodes stay idle; cannot rebalance without resharding | Create several shards per node at the start (for example 2-4x the node count). |
| Each shard returns `k / shards` results | Recall drops when the true neighbours cluster on one shard | Every shard returns the full `k` (or more), then merge. |
| Read-your-writes path on async replicas | A user uploads a file and cannot find it | Use `consistency=majority` (Qdrant), `Session` (Milvus) or read the primary for that path. |
| Bulk load with indexing enabled | Load takes hours; CPU pinned by repeated graph builds | Disable indexing during the load (`indexing_threshold: 0`), re-enable afterwards. |
| Deletes without compaction | Memory and latency grow although `points_count` falls | Check tombstone ratio and optimizer status; tune `deleted_threshold`. |
| mmap'd vectors on network block storage | p99 jumps from milliseconds to hundreds of milliseconds under load | Local NVMe for mmap layouts; keep quantized codes in RAM. |
| Snapshots never restored | Restore fails during an incident (version mismatch, missing node snapshots) | Restore into a staging cluster on a schedule. |
| No recall monitoring | Quality silently degrades after a config or model change | Run a recall canary against exact search (6.10). |

### 6.13 Best Practices

- **Plan shard count for the cluster you will have, not the one you have**: resharding is far harder than moving whole shards.
- **Use replication for availability and reads, quantization for capacity**: do not add replicas to fix a RAM shortage.
- **Make ingestion idempotent and ordered per document**: deterministic point ids plus partitioned topics make retries safe.
- **Separate bulk loads from steady-state writes**: disable indexing for the load, then build once.
- **Version everything that shapes vectors**: model name, dimensions, tokenizer, quantization and index parameters belong in collection metadata and alias names.
- **Monitor recall as a first-class SLO**: latency without recall is half a picture.
- **Rehearse failure**: kill a node, restore a snapshot and flip an alias in staging before production needs it.

### 6.14 Hands-on Exercise

1. Build `ConsistentHashRing([f"node{i}" for i in range(4)], vnodes=4)`, count keys per node for 10,000 keys, add `node4` and measure `moved_fraction`. Repeat with `vnodes=64`. **Expected:** with 4 virtual nodes the busiest node holds about 2.4x the keys of the quietest (1,416 to 3,465) and adding a node moves 28% of keys; with 64 the spread is 2,315 to 2,792 and 18% move.
2. Write a test: 130 upserts with `seal_threshold=50` (two sealed segments, 30 growing), delete `p0`-`p44` (90% of the first segment), then call `compact(min_dead_ratio=0.5)`. **Expected:** it returns 0 (one segment rebuilt into one smaller segment), `sealed_segments` stays 2, `tombstones` becomes 0, `len(col)` is 85, and the second segment's `index` is the same object as before (`is`), proving untouched segments are not rebuilt.
3. Run `sql/04_filtering.sql` and `sql/06_operations.sql`, note `idx_scan` for `tickets_hnsw_t1`, then run `SELECT id FROM tickets WHERE tenant_id = 1 ORDER BY embedding <=> (SELECT embedding FROM tickets WHERE id = 2) LIMIT 5;` three times and query `pg_stat_user_indexes` again a second later. **Expected:** `idx_scan` for the partial index rises by 3 while the shared `tickets_hnsw` count does not change: the planner routes tenant 1 to its own graph.

Solutions: [`src/learn_vector_databases/cluster.py`](src/learn_vector_databases/cluster.py), [`src/learn_vector_databases/segments.py`](src/learn_vector_databases/segments.py), [`tests/test_stages_4_6.py`](tests/test_stages_4_6.py), [`sql/06_operations.sql`](sql/06_operations.sql).

[Back to top ⤴️](#-table-of-contents)

---

## M1. Masterclass: Benchmarking Vector Search

Every tuning decision in this guide ends with "measure it". This masterclass is how: what to measure, how to build ground truth, and how to read a recall/throughput curve without fooling yourself.

### M1.1 The ANN-Benchmarks Methodology: Recall@K vs QPS vs Build Cost

Claims such as "10x faster" mean nothing without the recall at which they were measured. The common reference is the **ANN-Benchmarks** methodology (Aumüller, Bernhardsson and Faithfull), which reports several quantities together:

```mermaid
flowchart LR
    subgraph Metrics["What a vector benchmark must report together"]
        M1["Recall@K against exact ground truth"]
        M2["Throughput (QPS) at a stated concurrency, and p50 / p99 latency"]
        M3["Index build time and ingestion rate"]
        M4["Memory and disk per vector"]
    end
```

#### How to measure true Recall@K

1. **Compute ground truth**: run exact search (a flat index or a full scan) to find the true $K$ nearest neighbours $G_q$ for each test query.
2. **Run the ANN query**: the same queries against the approximate index return $A_q$.
3. **Average the overlap**:
   $$\text{Recall@K} = \frac{1}{|Q|} \sum_{q \in Q} \frac{|A_q \cap G_q|}{K}$$

Many production retrieval systems set a target such as recall@10 of 0.95-0.98 at a fixed p99 latency, then find the cheapest configuration that meets it. Report recall and latency together: either number alone is meaningless, because any index can be made perfect (scan everything) or fast (return anything).

### M1.2 Worked Example: A Recall/Latency Sweep

[`src/learn_vector_databases/sweep.py`](src/learn_vector_databases/sweep.py) implements the method end to end on the starter indexes: generate clustered data, compute exact ground truth, build HNSW and IVF, then sweep the query-time knob and record mean recall@10 and latency per setting.

```bash
python -m src.learn_vector_databases.sweep --points 1000 --dims 32
python -m src.learn_vector_databases.sweep --quantization --points 2000 --dims 64
python -m src.learn_vector_databases.filtering      # the same method with filters (Stage 5.3)
```

```python
from src.learn_vector_databases.sweep import run_sweep

res = run_sweep(points=1000, dims=32, ef_values=(10, 40, 160), nprobe_values=(1, 4, 16))
for ef, recall, ms in res["hnsw"]:
    print(f"ef_search={ef:<4} recall@10={recall:.3f} {ms:.2f} ms")
```

Each `(setting, recall, latency)` triple is one point on the Pareto curve. The configuration to ship is the cheapest point at or above your recall target.

```mermaid
flowchart TD
    Data["Sample of production vectors + real queries"] --> GT["Exact ground truth, same metric and filters"]
    Data --> Build["Build candidate configs: m, ef_construction, quantization"]
    Build --> Sweep["Sweep query knobs: ef_search, oversampling, nprobe"]
    GT --> Score["recall@k per point"]
    Sweep --> Score
    Sweep --> Lat["p50 / p99 at fixed concurrency"]
    Score --> Pareto["Pareto frontier"]
    Lat --> Pareto
    Pareto --> Pick["Cheapest config meeting the recall and latency targets"]
```

### M1.3 Benchmark Tools and What Each Answers

| Tool | Measures | Good for | Blind spots |
| --- | --- | --- | --- |
| ANN-Benchmarks | Recall vs QPS for index libraries, single thread | Comparing algorithms and parameters | No filters, no concurrency, no network or durability |
| big-ann-benchmarks | Billion-scale tracks (filtered, sparse, streaming in later rounds) | Algorithms under memory limits | Research setups, not your workload |
| VectorDBBench | End-to-end database runs: load, concurrency, filters | Shortlisting engines | Vendor-run results need rerunning on your hardware |
| Engine's own tooling (for example a load generator) | Throughput for one engine | Capacity tests | Not comparable across engines |
| Your own harness (`sweep.py`, `filtering.py`) | Your vectors, your filters, your recall target | The final decision | Needs exact ground truth and real queries |

### M1.4 Production Checklist

- Ground truth comes from exact search over the same data and metric, on queries sampled from real traffic (not from the indexed vectors themselves).
- Report recall@k, p50/p99 latency, QPS at a fixed concurrency, build time and memory together.
- Warm caches before measuring, and measure again cold if restarts matter to you.
- Benchmark with filters and tenant distributions that match production; unfiltered numbers flatter every engine.
- Load the data volume you expect in a year; recall and latency at 1% of the data do not extrapolate.
- Run benchmarks while ingesting if production writes continuously; segment merges change the numbers.
- Re-run the benchmark when the embedding model, the data volume or the engine version changes.

[Back to top ⤴️](#-table-of-contents)

---

## M2. Masterclass: Hybrid Retrieval and Reranking Pipelines

Most production RAG and search systems do not run one vector query. They run several retrievers, fuse their candidates and rerank a short list with a slower, more accurate model. This masterclass builds that pipeline, extending Stage 5.10-5.12.

### M2.1 How a Multi-Stage Retrieval Pipeline Works

Each stage trades recall for precision at a different cost. Cheap retrievers cast a wide net; the reranker spends its budget only on a few dozen candidates.

```mermaid
flowchart LR
    Q["Query"] --> D["Dense ANN: top 50, ~5 ms"]
    Q --> L["BM25 / sparse: top 50, ~5 ms"]
    Q --> M["Metadata boosts: recency, popularity"]
    D --> F["Fusion: RRF or DBSF, top 30"]
    L --> F
    F --> X["Cross-encoder rerank: 30 pairs, 20-100 ms on GPU"]
    M --> X
    X --> K["Top 5 to the LLM or the UI"]
```

| Stage | Model type | Sees the query and document | Cost per document | Typical depth |
| --- | --- | --- | --- | --- |
| Dense retrieval | Bi-encoder: query and documents embedded separately | Separately, compared by one dot product | One distance computation | 50-200 |
| Lexical retrieval | BM25 or learned sparse (SPLADE) | Separately, matched by terms | Posting-list traversal | 50-200 |
| Fusion | Rank arithmetic | Neither | Negligible | 20-100 |
| Reranking | Cross-encoder (or an LLM) | Together, full attention across both | One model forward pass | 10-50 |

A bi-encoder must compress a document into one vector before it knows the query; a cross-encoder reads query and document together, which is why it ranks better and why it cannot be precomputed.

### M2.2 Worked Example: Fusion in the Starter and in Qdrant

The starter's fusion functions ([`hybrid.py`](src/learn_vector_databases/hybrid.py)) and the Qdrant Query API produce the same kind of result. Both were run for this guide on the same three documents (dense vectors and sparse term ids as in Stage 5.10):

```bash
for fusion in rrf dbsf; do
  curl -s -X POST http://localhost:6333/collections/kb/points/query -H 'Content-Type: application/json' -d "{
    \"prefetch\": [
      { \"query\": [0.9, 0.4, 0, 0], \"using\": \"dense\", \"limit\": 20 },
      { \"query\": { \"indices\": [101, 202], \"values\": [1.0, 1.0] }, \"using\": \"bm25\", \"limit\": 20 }
    ],
    \"query\": { \"fusion\": \"$fusion\" },
    \"limit\": 3
  }"
  echo
done
```

```text
{"result":{"points":[{"id":4,"score":0.8333334},{"id":1,"score":0.75},{"id":2,"score":0.33333334}]}, ...}
{"result":{"points":[{"id":4,"score":0.9886846},{"id":1,"score":0.9257834},{"id":2,"score":0.5855321}]}, ...}
```

The RRF scores match $1/(2 + r)$ summed over both lists with $r$ counted from 0: point 4 is first in dense and second in sparse, $1/2 + 1/3 = 0.833$. That is a much smaller constant than the textbook $k = 60$ the starter uses, so the top ranks count for more. With `"query": {"rrf": {"k": 60}}` the same request returned 0.03306 for point 4, which is $1/60 + 1/61$. Compare **orderings** across systems, not raw scores; Elasticsearch's `rrf` retriever and Milvus's `RRFRanker` have their own defaults too.

Multi-stage queries nest: a prefetch can itself contain prefetches, so "fuse dense and sparse, then rescore the fused list with a third vector" is one request:

```bash
curl -s -X POST http://localhost:6333/collections/kb/points/query -H 'Content-Type: application/json' -d '{
  "prefetch": {
    "prefetch": [
      { "query": [0.9, 0.4, 0, 0], "using": "dense", "limit": 50 },
      { "query": { "indices": [101, 202], "values": [1.0, 1.0] }, "using": "bm25", "limit": 50 }
    ],
    "query": { "fusion": "rrf" },
    "limit": 30
  },
  "query": [0.9, 0.4, 0, 0],
  "using": "dense",
  "limit": 5
}'
```

### M2.3 Cross-Encoder Reranking

A cross-encoder scores `(query, passage)` pairs. The `sentence-transformers` library wraps open models such as the MS MARCO MiniLM rerankers; hosted rerank APIs (Cohere, Voyage, Jina and others) take the same inputs over HTTP.

```python
# pip install sentence-transformers
from sentence_transformers import CrossEncoder

from src.learn_vector_databases.hybrid import BM25Index, rrf

corpus = {
    "kb1": "Patch for CVE-2024-38077 remote desktop licensing buffer overflow",
    "kb2": "How to harden remote desktop gateways against memory corruption attacks",
    "kb4": "Remote desktop licensing service: install and activate",
    "kb5": "Heap overflow mitigations in Windows services explained",
}
query = "is there a fix for CVE-2024-38077?"

bm25 = BM25Index()
for doc_id, text in corpus.items():
    bm25.add(doc_id, text)
dense = [("kb2", 0.83), ("kb5", 0.80), ("kb1", 0.78), ("kb4", 0.61)]   # from your embedding search
candidates = [doc_id for doc_id, _ in rrf([dense, bm25.search(query, 20)], limit=30)]

reranker = CrossEncoder("cross-encoder/ms-marco-MiniLM-L-6-v2")
scores = reranker.predict([(query, corpus[d]) for d in candidates])
for doc_id, score in sorted(zip(candidates, scores), key=lambda p: -p[1]):
    print(f"{score:7.3f}  {doc_id}  {corpus[doc_id]}")
```

| Line / API | Role | What happens at runtime |
| --- | --- | --- |
| `rrf([dense, bm25.search(...)], limit=30)` | Candidate set | Union of both retrievers, ordered by agreement; 30 is the rerank budget. |
| `CrossEncoder(name)` | Model load | Downloads the model once; load it at process start, not per request. |
| `reranker.predict(pairs)` | Scoring | One forward pass per pair, batched; returns relevance logits (higher is better). |
| `sorted(zip(...))` | Final order | The reranker's order replaces the fused order. |

Rerank latency grows linearly with candidates and with passage length. Cap both: rerank 20-50 candidates, truncate passages to the model's maximum input length, and cache scores for repeated queries.

### M2.4 Trade-offs: Which Pipeline to Run

| Pipeline | Quality on mixed queries | Latency | Cost | Choose when |
| --- | --- | --- | --- | --- |
| Dense only | Good on paraphrases, weak on codes and names | Lowest | Lowest | Short natural-language queries over prose |
| Lexical only | Strong on exact terms, weak on paraphrase | Low | Low | Code search, logs, identifiers |
| Hybrid + RRF | Robust across query types | Low (two parallel retrievers) | Low | The default starting point for RAG |
| Hybrid + weighted fusion | Better than RRF once tuned | Low | Low + tuning time | You have judged queries to tune `alpha` |
| Hybrid + cross-encoder | Usually the best ranking | +20-100 ms (GPU) or more on CPU | Model hosting | Top-5 quality matters (RAG context, support search) |
| Hybrid + LLM reranker | Can follow complex instructions | Hundreds of ms or more | Highest | Low QPS, high-value queries |

### M2.5 Production Checklist

- Build a judged query set (a few hundred queries with relevant documents marked) before tuning fusion or adding a reranker.
- Track nDCG@10 or recall@k of the final list, not only of each retriever.
- Run retrievers in parallel; the pipeline's latency is the slowest retriever plus fusion plus rerank.
- Set a timeout on the reranker and fall back to the fused order if it is exceeded.
- Version the sparse encoder and the reranker with the collection, like the embedding model.
- Log candidate lists with their source retriever so you can see which retriever found each final result.

[Back to top ⤴️](#-table-of-contents)

---

## M3. Masterclass: Multi-Vector Retrieval and Late Interaction

A single embedding per document forces a passage that covers three topics into one point in space. Late-interaction models (ColBERT and its successors, and ColPali-style models for document images) keep one vector **per token** and compare query tokens to document tokens at search time. This masterclass shows how that scoring works, why it costs so much storage, and how engines serve it.

### M3.1 How MaxSim Scoring Works

For a query with token vectors $q_1 \dots q_n$ and a document with token vectors $d_1 \dots d_m$:

$$\text{MaxSim}(Q, D) = \sum_{i=1}^{n} \max_{j} \; q_i \cdot d_j$$

Each query token finds its best-matching document token; the document score is the sum of those best matches.

```mermaid
flowchart LR
    subgraph Query["Query tokens"]
        q1["q1: 'reset'"]
        q2["q2: 'password'"]
    end
    subgraph Doc["Document tokens"]
        d1["d1: 'forgot'"]
        d2["d2: 'password'"]
        d3["d3: 'sign-in'"]
        d4["d4: 'reset'"]
    end
    q1 -->|"max = q1 . d4"| S["Sum of per-token maxima = document score"]
    q2 -->|"max = q2 . d2"| S
```

```python
from src.learn_vector_databases.multivector import maxsim

q = [[1.0, 0.0], [0.0, 1.0]]
d = [[1.0, 0.0], [0.6, 0.8]]
print(maxsim(q, d))      # 1.0 (q1 matches d1) + 0.8 (q2 best matches d2) = 1.8
```

A pooled (averaged) vector loses this: a document about "password reset" and "SAML" averages into a point near neither, while MaxSim still matches both query topics to the right tokens.

### M3.2 Worked Example: Candidate Generation Decides Recall

Exact MaxSim over every document is too slow at scale, so engines first generate candidates cheaply and run MaxSim only on them. [`multivector.py`](src/learn_vector_databases/multivector.py) compares two candidate generators against exact MaxSim, on 300 synthetic documents that each mix 2-4 topics (`python -m src.learn_vector_databases.multivector`):

```python
from src.learn_vector_databases.multivector import MultiVectorIndex, synthetic_corpus

corpus, queries = synthetic_corpus()          # 300 docs, 2-4 topics each, 3-8 tokens per topic
index = MultiVectorIndex()
for doc_id, tokens in corpus.items():
    index.add(doc_id, tokens)

q = queries[0]
exact = index.search_exact(q, 10)                         # MaxSim on every document
pooled = index.search(q, 10, candidates=30)               # mean-pooled shortlist, then MaxSim
token = index.search_token_candidates(q, 10, per_token=30)  # nearest tokens per query token, then MaxSim
```

```text
pooled shortlist  10 -> MaxSim recall@10 = 0.290
pooled shortlist  30 -> MaxSim recall@10 = 0.535
pooled shortlist 100 -> MaxSim recall@10 = 0.850
token candidates  10 per query token -> recall@10 = 0.765
token candidates  30 per query token -> recall@10 = 1.000
storage (floats): {'token_vectors': 160672, 'pooled_vectors': 9600}
```

- **Pooled candidates miss multi-topic documents**: even a 100-document shortlist (a third of the corpus) recovers only 85% of the true top 10.
- **Token-level candidates match the scoring model**: each query token pulls documents that own one of its nearest tokens, which is how ColBERT's original retrieval worked. Thirty tokens per query token reached full recall.
- **Storage is the price**: 160,672 floats of token vectors against 9,600 for one pooled vector per document, about 17x. Real ColBERT indexes compress token vectors (residual compression and centroids in PLAID) for this reason.

### M3.3 Multi-Vectors in Qdrant: Funnel with a Cheap First Stage

Qdrant stores a multi-vector as one named vector with `multivector_config` and scores it with MaxSim. Setting `hnsw_config.m: 0` on that vector skips building a graph over token vectors, because it is used only for rescoring. The first stage uses a cheap dense vector. Tested against Qdrant 1.20:

```bash
curl -s -X PUT http://localhost:6333/collections/mv -H 'Content-Type: application/json' -d '{
  "vectors": {
    "small":   { "size": 2, "distance": "Cosine" },
    "full":    { "size": 4, "distance": "Cosine" },
    "colbert": { "size": 4, "distance": "Cosine",
                 "multivector_config": { "comparator": "max_sim" },
                 "hnsw_config": { "m": 0 } }
  }
}'

curl -s -X PUT "http://localhost:6333/collections/mv/points?wait=true" -H 'Content-Type: application/json' -d '{
  "points": [
    { "id": 1, "vector": { "small": [0.9, 0.1], "full": [0.9, 0.1, 0.3, 0],
                           "colbert": [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0]] } },
    { "id": 2, "vector": { "small": [0.8, 0.3], "full": [0.8, 0.3, 0, 0.4],
                           "colbert": [[0.7, 0.7, 0, 0], [0.5, 0.5, 0.5, 0.5], [0, 0, 0, 1]] } }
  ]
}'

# small -> full -> MaxSim, one request
curl -s -X POST http://localhost:6333/collections/mv/points/query -H 'Content-Type: application/json' -d '{
  "prefetch": {
    "prefetch": { "query": [0.9, 0.1], "using": "small", "limit": 100 },
    "query": [0.9, 0.1, 0.3, 0], "using": "full", "limit": 20
  },
  "query": [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0]],
  "using": "colbert",
  "limit": 2
}'
```

```text
{"result":{"points":[{"id":1,"version":1,"score":3.0},{"id":2,"version":1,"score":1.9142135}]}, ...}
```

Point 1 scores 3.0 because each of the three query tokens matches one of its tokens exactly. One caution from testing: a multi-vector with exactly **two** token vectors was rejected by Qdrant 1.20's request validation ("indices: must be unique"), apparently because the two-element list was also a valid shape for a sparse vector. Real token sequences are longer, but keep the case in mind when writing tests with tiny fixtures.

### M3.4 Trade-offs: Single Vector, Multi-Vector, Cross-Encoder

| Approach | Index size per document | Query cost | Quality on long or multi-topic passages | Precomputable |
| --- | --- | --- | --- | --- |
| Single dense vector | 1 x d floats | One ANN search | Weakest; topics are averaged | Yes |
| Multi-vector (late interaction) | tokens x d (often 100-300 tokens, compressed) | Candidates + MaxSim on the shortlist | Strong; token-level matching | Yes |
| Cross-encoder rerank | None beyond the first stage | One model pass per candidate | Strongest per pair | No, needs the query |
| Smaller chunks + single vector | More vectors, each 1 x d | One ANN search | Better than big chunks; loses context across chunks | Yes |

Research approaches such as MUVERA turn a multi-vector set into one fixed-size vector for the first stage, so a standard HNSW index can generate candidates for MaxSim rescoring. The pattern is the same as M3.3: a cheap single-vector stage, then exact late interaction on the shortlist.

### M3.5 Production Checklist

- Budget storage first: tokens per document x dimensions x bytes, times replicas; quantize token vectors if the engine supports it.
- Use multi-vectors for rescoring a shortlist, not as the only index; disable HNSW on the token vectors (`m: 0`) when they only rescore.
- Measure candidate-generation recall against exact MaxSim (M3.2), not just final quality.
- Keep the document's token count bounded (chunking, model max length) so the worst-case MaxSim cost is bounded.
- Version the late-interaction model with the collection; token vectors from two model versions are not comparable.

[Back to top ⤴️](#-table-of-contents)

---

## M4. Masterclass: Matryoshka Embeddings and Funnel Search

Matryoshka Representation Learning (MRL) trains an embedding model so that the first 64, 128 or 256 dimensions are a usable embedding on their own. Several current embedding models are trained this way and accept a `dimensions` parameter (OpenAI's `text-embedding-3` family, Nomic, Jina and others). That turns dimensionality into a runtime knob: search a short prefix for speed, rescore with the full vector for quality.

### M4.1 How Truncation and Funnel Search Work

```mermaid
flowchart LR
    Full["Full vector: 1,024 dims"] --> T["Keep first 128 dims, re-normalise"]
    T --> I["HNSW index on 128-dim prefixes (8x smaller)"]
    Q["Query: full vector"] --> QT["Query prefix: 128 dims"]
    QT --> I
    I --> SL["Shortlist: 100 candidates"]
    SL --> R["Rescore with full 1,024-dim vectors"]
    Q --> R
    R --> K["Top k"]
```

Truncation must **re-normalise**: the prefix of a unit vector is shorter than 1, and cosine or dot-product scores on unnormalised prefixes are wrong.

```python
from src.learn_vector_databases.matryoshka import truncate

print(truncate([3.0, 4.0, 12.0], 2))     # [0.6, 0.8]: first two values, rescaled to unit length
```

### M4.2 Worked Example: Prefix Size vs Shortlist

[`matryoshka.py`](src/learn_vector_databases/matryoshka.py) generates 3,000 128-dim vectors whose variance decays across dimensions (a stand-in for an MRL model), then measures recall@10 against exact full-dimension search. Cost is counted in multiply-adds relative to a full scan (`python -m src.learn_vector_databases.matryoshka`):

```python
from src.learn_vector_databases.matryoshka import exact_top, funnel_search, matryoshka_like, truncate

data = matryoshka_like(3030, dims=128)
corpus, queries = data[:3000], data[3000:]
short = [truncate(v, 16) for v in corpus]                 # store the 16-dim prefixes
ids, cost = funnel_search(corpus, short, queries[0], k=10, shortlist=30)
truth = exact_top(corpus, queries[0], 10)
print(len(set(ids) & set(truth)) / 10, cost / (3000 * 128))
```

| Prefix dims | Rescore shortlist | Recall@10 | Cost vs full scan |
| --- | --- | --- | --- |
| 8 | none | 0.393 | 0.062 |
| 8 | 30 | 0.703 | 0.072 |
| 8 | 100 | 0.900 | 0.096 |
| 16 | none | 0.683 | 0.125 |
| 16 | 30 | 0.953 | 0.135 |
| 16 | 100 | 0.967 | 0.158 |
| 32 | none | 0.887 | 0.250 |
| 32 | 30 | 0.990 | 0.260 |
| 32 | 100 | 1.000 | 0.283 |

The prefix alone is a weak ranker (0.683 at 16 dims) but a good **candidate generator**: rescoring only 30 candidates with full vectors lifts it to 0.953 at 13.5% of the full-scan cost. This is the same "compressed codes find the neighbourhood, originals pick the winners" pattern as quantization rescoring in Stage 3.8, applied to dimensions instead of bits. The two combine: a binary-quantized 256-dim prefix in RAM is a very small first stage.

### M4.3 Funnels in Qdrant and pgvector

**Qdrant**: store the prefix and the full vector as two named vectors and nest the prefetch (the same request shape as M3.3, without the multi-vector stage):

```bash
curl -s -X POST http://localhost:6333/collections/mv/points/query -H 'Content-Type: application/json' -d '{
  "prefetch": { "query": [0.9, 0.1], "using": "small", "limit": 100 },
  "query": [0.9, 0.1, 0.3, 0],
  "using": "full",
  "limit": 10
}'
```

**pgvector**: index an expression over the prefix with `subvector` and `l2_normalize` (both pgvector 0.7.0+), shortlist with that index, then re-rank with the full column. From [`sql/07_funnel.sql`](sql/07_funnel.sql), which builds 5,000 16-dim vectors with decaying variance:

```sql
CREATE INDEX docs_mrl_prefix ON docs_mrl
    USING hnsw ((l2_normalize(subvector(embedding, 1, 8))::vector(8)) vector_cosine_ops);

WITH q AS (SELECT embedding AS v FROM docs_mrl WHERE id = 42),
shortlist AS (
    SELECT id, embedding
    FROM docs_mrl
    ORDER BY l2_normalize(subvector(embedding, 1, 8))::vector(8)
             <=> l2_normalize(subvector((SELECT v FROM q), 1, 8))::vector(8)
    LIMIT 100
)
SELECT id FROM shortlist ORDER BY embedding <=> (SELECT v FROM q) LIMIT 10;
```

```text
NOTICE:  funnel recall@10 = 10/10
```

The `ORDER BY` expression must match the index expression exactly, cast included, or PostgreSQL falls back to a sequential scan; the script checks the plan for `docs_mrl_prefix`. The same funnel over the uniformly random `docs` table from `sql/02_indexes.sql` recovered only 4-5 of the true top 10 in test runs: without the Matryoshka property, the first half of the dimensions is no better than any other half.

### M4.4 Trade-offs: Ways to Shrink the First Stage

| Technique | Shrinks | Needs | Recall recovery | Re-embedding needed |
| --- | --- | --- | --- | --- |
| Matryoshka truncation | Dimensions (2-16x) | A model trained with MRL | Rescore with full vectors | No, if you stored full vectors |
| Scalar quantization (SQ8) | Bytes per dimension (4x) | Nothing | Usually small loss; rescoring optional | No |
| Binary quantization | Bytes per dimension (32x) | A model that tolerates it | Rescoring required | No |
| PCA or random projection | Dimensions | A fitted projection | Rescoring | No, but projection must be refit |
| Smaller embedding model | Dimensions and model cost | A new model | No rescoring possible | Yes |

### M4.5 Production Checklist

- Confirm the model is trained for truncation; truncating an ordinary embedding loses far more quality.
- Store full-dimension vectors (on disk is fine) so you can rescore and change the prefix size later.
- Re-normalise prefixes before indexing and at query time.
- Tune prefix size and shortlist together against a recall target, as in M4.2.
- Keep the prefix size in the collection's metadata and alias name; mixing prefix sizes in one index silently breaks scores.

[Back to top ⤴️](#-table-of-contents)

---

## M5. Masterclass: Zero-Downtime Embedding Model Migration

Embedding models improve every few months, and a vector from model A cannot be compared with a vector from model B. Moving to a new model means re-embedding every document while search keeps working. This masterclass turns the alias swap from Stage 6.9 into a complete, reversible procedure.

### M5.1 The Migration State Machine

```mermaid
stateDiagram-v2
    [*] --> Live_v1
    Live_v1 --> DualWrite: create v2, start writing to both
    DualWrite --> Backfill: copy history into v2 in checkpointed batches
    Backfill --> Shadow: v2 complete, compare results on real queries
    Shadow --> Backfill: gaps found, replay failures
    Shadow --> Cutover: overlap and judged quality acceptable
    Cutover --> Rollback: errors or quality drop
    Rollback --> Shadow
    Cutover --> Retire_v1: rollback window passed
    Retire_v1 --> [*]
```

| Phase | Reads go to | Writes go to | Exit criterion |
| --- | --- | --- | --- |
| Live v1 | v1 | v1 | New model chosen |
| Dual write | v1 | v1 and v2 | Dual writes running without failures |
| Backfill | v1 | v1 and v2 | v2 point count equals the source of truth |
| Shadow | v1 (v2 in the background) | v1 and v2 | Overlap and judged metrics reviewed |
| Cutover | v2 (alias flipped) | v1 and v2 | Error rate and quality stable |
| Retire | v2 | v2 | Rollback window over; v1 dropped |

Dual writes start **before** the backfill so no document changed during the backfill is missed: the backfill may overwrite a newer dual-written version with an older one only if it reads stale data, which is why the backfill reads from the source of truth and upserts are keyed by a deterministic id.

### M5.2 Worked Example: The Pieces in Code

[`migration.py`](src/learn_vector_databases/migration.py) has the four building blocks; [`blueprint.py`](src/learn_vector_databases/blueprint.py) uses them in a full service (M6).

```python
from src.learn_vector_databases.blueprint import hashing_embedder
from src.learn_vector_databases.migration import AliasRegistry, Backfill, DualWriter, shadow_compare
from src.learn_vector_databases.segments import SegmentedCollection
from src.learn_vector_databases.vectordb import VectorItem

model_v1, model_v2 = hashing_embedder(32), hashing_embedder(64)     # stand-ins for two embedding models
collections = {"docs_v1": SegmentedCollection(32), "docs_v2": SegmentedCollection(64)}
source = {f"d{i}": f"support article {i} about topic {i % 9}" for i in range(300)}   # source of truth


def make_item(doc_id, vector, payload):
    return VectorItem(doc_id, vector, payload)


for doc_id, text in source.items():                                   # v1 is live
    collections["docs_v1"].upsert(make_item(doc_id, model_v1(text), {}))
aliases = AliasRegistry()
aliases.point("docs", "docs_v1")

# 1. Dual-write from now on: update the source of truth, then both collections.
writer = DualWriter(collections["docs_v1"], model_v1, collections["docs_v2"], model_v2)
source["d7"] = "support article 7 rewritten about refunds"
writer.write("d7", source["d7"], {}, make_item)

# 2. Backfill v2 from the source of truth in resumable batches.
backfill = Backfill(batch_size=100)
backfill.run([(d, t, {}) for d, t in source.items()], collections["docs_v2"], model_v2, make_item)
print("backfilled:", backfill.checkpoint, "points in v2:", len(collections["docs_v2"]))


# 3. Shadow-read the same queries against both versions.
def search(name, embed):
    return lambda q: [it.id for it, _ in collections[name].search(embed(q), k=10)]


report = shadow_compare(["refunds", "topic 3", "support article 12"],
                        search("docs_v1", model_v1), search("docs_v2", model_v2), k=10, worst=1)
print("shadow:", report)

# 4. Cut over atomically; one call rolls back.
aliases.point("docs", "docs_v2")
print("live:", aliases.resolve("docs"), "| after rollback:", aliases.rollback("docs"))
```

```text
backfilled: 300 points in v2: 300
shadow: {'mean_overlap': 0.5, 'worst': [(0.3, 'support article 12')]}
live: docs_v2 | after rollback: docs_v1
```

The update to `d7` reaches v2 twice, once through the dual write and once through the backfill, and both carry the new text because the backfill reads the source of truth, not v1. Run the module itself with `python -m src.learn_vector_databases.migration` for a checkpoint-and-resume demo.

| Piece | Guarantees | Does not guarantee |
| --- | --- | --- |
| `AliasRegistry.point` | Readers see the old or the new target, never neither | That v2 is complete; check counts first |
| `DualWriter.write` | v1 writes succeed even if v2 is down; v2 failures are recorded | Ordering between the two collections |
| `Backfill.run` | Resumable, idempotent batches | Freshness; dual writes cover changes during the run |
| `shadow_compare` | Finds queries whose results changed the most | That the new results are better; that needs judged labels |

Low overlap is not failure: a better model is supposed to change results. Use overlap to find the queries to review, and judged relevance (nDCG, recall on labelled queries) to decide.

### M5.3 Engine Commands for Each Step

| Step | Qdrant | pgvector | Milvus |
| --- | --- | --- | --- |
| Create v2 | `PUT /collections/docs_v2` with the new size | `CREATE TABLE docs_v2 (... vector(1536))` or a new column | `create_collection("docs_v2", ...)` |
| Bulk load | `indexing_threshold: 0` during the load (6.6) | `COPY`, then `CREATE INDEX` | `insert` in batches, or bulk import from files |
| Cut over | `POST /collections/aliases` with delete + create in one request | Swap a view in one transaction (`sql/06_operations.sql`) | `alter_alias("docs_v2", "docs")` |
| Roll back | Point the alias back | Swap the view back | `alter_alias("docs_v1", "docs")` |
| Retire | `DELETE /collections/docs_v1` | `DROP TABLE docs_v1` | `drop_collection("docs_v1")` |

A same-table pgvector migration is also possible: add `embedding_v2 vector(1536)`, backfill it in batches, build the index with `CREATE INDEX CONCURRENTLY`, switch the query, then drop the old column. It avoids copying payload columns but makes the table temporarily wider.

### M5.4 Trade-offs: Migration Strategies

| Strategy | Downtime | Extra capacity | Rollback | Risk |
| --- | --- | --- | --- | --- |
| In-place re-embed (overwrite vectors) | None, but results are mixed during the run | None | Re-embed again | Mixed-model results compare vectors that are not comparable |
| Blue/green collections + alias | None | 2x storage during migration | Instant alias flip | Needs dual writes and a backfill |
| New vector field in the same collection (named vector or column) | None | Extra vector per point | Switch the query field back | Collection is larger until the old field is dropped |
| Stop-the-world rebuild | Minutes to hours | None | Restore a snapshot | Only acceptable for internal tools |

### M5.5 Production Checklist

- Store the model name, version and dimensions with every collection (metadata, alias naming such as `docs_te3l_1536_v2`).
- Keep the source text (or a pointer to it) for every vector; without it you cannot re-embed.
- Start dual writes before the backfill and replay recorded failures before the shadow phase.
- Compare counts per tenant between v1, v2 and the source of truth before cutting over.
- Run shadow reads on real traffic and review the lowest-overlap queries by hand or with judged labels.
- Keep v1 until the rollback window has passed, then delete it and its snapshots on purpose.
- Re-embed queries with the same model as the collection they hit; a mismatch returns plausible-looking garbage.

[Back to top ⤴️](#-table-of-contents)

---

## M6. Masterclass: Production Blueprint, a Multi-Tenant Hybrid Retrieval Service

This blueprint combines Stages 2-6 and M2-M5 in one service: a shared multi-tenant collection with tuned HNSW, quantized vectors with originals on disk, payload indexes for tenant isolation, hybrid dense plus lexical retrieval with fusion, a segmented write path, and alias-based model migrations. It comes in two forms: a runnable in-process version in the starter, and a Qdrant service class for a real deployment.

### M6.1 Architecture

```mermaid
flowchart TD
    Client["API clients"] --> API["Retrieval API: auth, tenant from token"]
    API --> Repo["Repository: adds mandatory tenant filter"]
    Repo --> Alias["Alias kb -> kb_v2"]
    Alias --> Dense["Dense prefetch: HNSW over SQ8 codes, rescore originals"]
    Alias --> Sparse["Sparse prefetch: BM25 / idf sparse vectors"]
    Dense --> Fuse["RRF fusion"]
    Sparse --> Fuse
    Fuse --> Rerank["Optional cross-encoder rerank"]
    Rerank --> API

    Src["Source of truth: documents DB"] --> CDC["Outbox / CDC"]
    CDC --> Queue["Queue: per-document ordering"]
    Queue --> Workers["Embedding workers: dense + sparse"]
    Workers --> Upsert["Batched idempotent upserts"]
    Upsert --> Alias
    Ops["Ops: recall canary, snapshots, alias migrations"] --> Alias
```

| Decision | Choice | Why | Section |
| --- | --- | --- | --- |
| Tenancy | Shared collection, `tenant_id` keyword index with `is_tenant`, mandatory filter | Density for the long tail | 5.7 |
| Large tenants | Dedicated shard key or collection above a size threshold | Noisy-neighbour control | 5.9 |
| Dense index | HNSW `m=16`, `ef_construct=128`, `hnsw_ef` per query | Recall target at low memory | 2.5 |
| Memory | SQ8 codes in RAM, originals on disk, rescoring | 4x less RAM | 3.2, 3.8 |
| Lexical side | Sparse vectors with `modifier: idf` | Exact identifiers | 5.10 |
| Fusion | RRF; rerank top 30 when quality requires it | No score calibration | 5.11, M2 |
| Writes | Idempotent ids `tenant:doc:chunk`, batched upserts | Safe retries | 6.6 |
| Migrations | Versioned collections behind an alias | Reversible model changes | M5 |
| Monitoring | Latency, counts, indexed ratio, recall canary | Quality as an SLO | 6.10 |

### M6.2 The Runnable Blueprint in the Starter

[`src/learn_vector_databases/blueprint.py`](src/learn_vector_databases/blueprint.py) wires the starter modules together: `SegmentedCollection` for dense vectors, a `BM25Index` per tenant, `rrf` for fusion and `AliasRegistry` for versions. The embedder is injected; tests use a deterministic hashing embedder so the suite runs without a model download.

```python
from src.learn_vector_databases.blueprint import KnowledgeService, hashing_embedder

svc = KnowledgeService(hashing_embedder(64), dims=64)
for i, text in enumerate([
    "Reset a forgotten password from the sign-in page",
    "Rotate API keys every 90 days and revoke unused ones",
    "Error E1042 means the upload exceeded the 25 MB limit",
    "Enable single sign-on with SAML for your workspace",
]):
    svc.ingest("acme", f"a{i}", text)
svc.ingest("globex", "g0", "Error E1042 in Globex means a billing hold")

for mode in ("dense", "lexical", "hybrid"):
    print(f"{mode:>8}:", [h["doc_id"] for h in svc.search("acme", "what does error E1042 mean", k=3, mode=mode)])
print("tenant isolation, globex sees only:", [h["doc_id"] for h in svc.search("globex", "E1042")])
print("alias after re-embedding ->", svc.reembed(hashing_embedder(128), 128))   # builds kb_v2, flips the alias
print("hybrid after migration:", [h["doc_id"] for h in svc.search("acme", "E1042 upload limit", k=2)])
```

```text
   dense: ['a2', 'a1', 'a3']
 lexical: ['a2']
  hybrid: ['a2', 'a1', 'a3']
tenant isolation, globex sees only: ['g0']
alias after re-embedding -> kb_v2
hybrid after migration: ['a2', 'a0']
```

| Method | Combines | Guarantee tested in [`tests/test_masterclasses.py`](tests/test_masterclasses.py) |
| --- | --- | --- |
| `ingest(tenant, doc_id, text)` | Embed, WAL-backed upsert, BM25 add; id is `tenant:doc_id` | Tenants cannot overwrite each other's documents |
| `search(tenant, query, mode)` | Filtered dense search over all segments, BM25 for the tenant, RRF | The exact identifier wins; another tenant's data never appears; an empty tenant raises |
| `delete(tenant, doc_id)` | Tombstone in the segment; lexical hits are dropped if the point is gone | Deleted documents disappear from both retrievers |
| `reembed(new_embed, dims)` | Builds the next version from stored texts, flips the alias | Search works on the new version; deleted documents stay deleted |

### M6.3 The Qdrant Service Class

The production version of the same design uses `qdrant-client` 1.11 or newer (needed for `is_tenant`) (`pip install qdrant-client`) against Qdrant started as in Stage 1.3.

```python
# vector_service.py: standalone example, needs qdrant-client and a running Qdrant
import uuid

from qdrant_client import QdrantClient
from qdrant_client.models import (
    Distance,
    FieldCondition,
    Filter,
    HnswConfigDiff,
    KeywordIndexParams,
    MatchValue,
    PayloadSchemaType,
    PointStruct,
    ScalarQuantization,
    ScalarQuantizationConfig,
    ScalarType,
    SearchParams,
    VectorParams,
)


class EnterpriseVectorStore:
    def __init__(self, url: str = "http://localhost:6333", collection: str = "enterprise_knowledge_v1"):
        self.client = QdrantClient(url=url)
        self.collection_name = collection

    def initialize_collection(self) -> None:
        """Tuned HNSW, SQ8 codes in RAM, originals on disk, tenant-aware payload index."""
        if self.client.collection_exists(self.collection_name):
            return
        self.client.create_collection(
            collection_name=self.collection_name,
            vectors_config=VectorParams(size=1536, distance=Distance.COSINE, on_disk=True),
            hnsw_config=HnswConfigDiff(m=16, ef_construct=128, on_disk=False),
            quantization_config=ScalarQuantization(
                scalar=ScalarQuantizationConfig(type=ScalarType.INT8, quantile=0.99, always_ram=True)
            ),
        )
        self.client.create_payload_index(
            collection_name=self.collection_name,
            field_name="tenant_id",
            field_schema=KeywordIndexParams(type="keyword", is_tenant=True),
        )
        self.client.create_payload_index(
            collection_name=self.collection_name,
            field_name="created_timestamp",
            field_schema=PayloadSchemaType.INTEGER,
        )

    @staticmethod
    def point_id(tenant_id: str, document_id: str, chunk: int) -> str:
        """Deterministic id: retries and replays overwrite instead of duplicating."""
        return str(uuid.uuid5(uuid.NAMESPACE_URL, f"{tenant_id}:{document_id}:{chunk}"))

    def batch_upsert_documents(self, tenant_id: str, documents: list[dict]) -> None:
        points = [
            PointStruct(
                id=self.point_id(tenant_id, doc["document_id"], doc.get("chunk", 0)),
                vector=doc["embedding"],
                payload={
                    "tenant_id": tenant_id,
                    "document_id": doc["document_id"],
                    "content": doc["content"],
                    "created_timestamp": doc["created_timestamp"],
                    "is_active": True,
                },
            )
            for doc in documents
        ]
        self.client.upsert(collection_name=self.collection_name, points=points, wait=True)

    def search_tenant_documents(self, tenant_id: str, query_vector: list[float], top_k: int = 5):
        if not tenant_id:
            raise ValueError("tenant_id is mandatory")
        return self.client.query_points(
            collection_name=self.collection_name,
            query=query_vector,
            query_filter=Filter(
                must=[
                    FieldCondition(key="tenant_id", match=MatchValue(value=tenant_id)),
                    FieldCondition(key="is_active", match=MatchValue(value=True)),
                ]
            ),
            limit=top_k,
            search_params=SearchParams(hnsw_ef=64),
        ).points
```

| Line / API | Role | What happens at runtime |
| :--- | :--- | :--- |
| `VectorParams(on_disk=True)` | Originals on disk | Full float32 vectors live in mmap'd files; only rescoring reads them. |
| `HnswConfigDiff(m=16, ef_construct=128)` | Graph settings | Stage 2.5 defaults with a higher build beam for a better graph. |
| `ScalarQuantization(..., always_ram=True)` | SQ8 codes in RAM | 4x smaller vectors for traversal (Stage 3.2). |
| `KeywordIndexParams(is_tenant=True)` | Tenant index | Filter runs inside traversal and storage is grouped by tenant (Stage 5.7). |
| `uuid.uuid5(...)` | Idempotent ids | The same chunk always maps to the same point (Stage 6.6). |
| `upsert(..., wait=True)` | Durable write | Returns after the change is applied, so a following read sees it. |
| `query_points(..., query_filter=...)` | Filtered search | `must` conditions are ANDed; the tenant condition is never optional. |

### M6.4 Collection Definition for the Hybrid Version

The hybrid variant adds a sparse vector with server-side IDF and names the dense vector, so both can be prefetched and fused (Stage 5.10). The application always queries through the alias:

```bash
curl -s -X PUT http://localhost:6333/collections/kb_v1 -H 'Content-Type: application/json' -d '{
  "vectors": {
    "dense": { "size": 1536, "distance": "Cosine", "on_disk": true }
  },
  "sparse_vectors": { "bm25": { "modifier": "idf" } },
  "hnsw_config": { "m": 16, "ef_construct": 128, "payload_m": 16 },
  "quantization_config": { "scalar": { "type": "int8", "quantile": 0.99, "always_ram": true } }
}'
curl -s -X PUT http://localhost:6333/collections/kb_v1/index -H 'Content-Type: application/json' \
  -d '{"field_name": "tenant_id", "field_schema": {"type": "keyword", "is_tenant": true}}'
curl -s -X POST http://localhost:6333/collections/aliases -H 'Content-Type: application/json' \
  -d '{"actions": [{"create_alias": {"collection_name": "kb_v1", "alias_name": "kb"}}]}'
```

Keeping `m: 16` alongside `payload_m: 16` (unlike the `m: 0` setup in 5.7) keeps a global graph for internal cross-tenant jobs such as deduplication, at the cost of building both.

### M6.5 Trade-offs in the Blueprint

| Alternative | Gains | Loses | Switch when |
| --- | --- | --- | --- |
| Collection per tenant | Hard isolation, trivial deletes | Density; per-collection overhead | Few tenants with strict isolation contracts |
| pgvector instead of Qdrant | Joins and ACID with business data, one system | Horizontal scale, built-in hybrid fusion | Under tens of millions of vectors on an existing Postgres |
| No quantization | Simpler, no rescoring | 4x RAM | Small corpora |
| Binary quantization | 32x smaller codes | Needs a suitable model and heavy oversampling | Very large corpora of high-dimensional embeddings |
| Always rerank | Best top-5 quality | Latency and GPU cost | Answer quality dominates (RAG for support, legal) |
| Managed service | No operations | Control over versions and tuning, cost at scale | Small team, unpredictable load |

### M6.6 Production Checklist

- Tenant id comes from the authenticated token, never from the request body, and every query path adds the filter.
- Point ids are deterministic; ingestion is idempotent and ordered per document.
- Collection names carry the model and version; clients only use aliases.
- SQ8 with rescoring is measured against float32 on judged queries before launch.
- Payload indexes exist for every filter field, including `tenant_id` with `is_tenant`.
- Bulk loads disable indexing and re-enable it afterwards; the collection is `green` before traffic.
- Recall canary, point-count drift and indexed ratio are on the dashboard with alerts.
- Snapshots are taken on a schedule and restored into staging regularly.
- A runbook covers: rebuild a collection, flip and roll back an alias, move a large tenant to its own shard.

[Back to top ⤴️](#-table-of-contents)

---

## 7. Stage 7: Staff Vector Database Engineer Interview Handbook & Cheatsheet

The questions run from definitions to production scenarios. Definitions get a paragraph; design and scenario questions get the reasoning an interviewer is listening for: trade-offs, failure modes and how you would verify the fix.

### 7.1 Core Concepts (Q1-Q10)

#### Q1. What causes the Curse of Dimensionality in vector spaces, and how does it affect distance distributions?
In high dimensions ($D > 100$), the ratio of volume between an inscribed hypersphere and a bounding hypercube approaches zero: $\lim_{D \rightarrow \infty} \frac{V_{\text{sphere}}}{V_{\text{cube}}} = 0$. Furthermore, the variance of pairwise distances between points decreases relative to the mean distance: $\lim_{D \rightarrow \infty} \frac{\sigma_{\text{dist}}}{\mu_{\text{dist}}} = 0$. This distance concentration phenomenon means that all points in the dataset become approximately equidistant from the query point. Consequently, partitioning structures like k-d trees and B-trees must inspect almost every partition, degrading to $O(N)$ linear scans.

#### Q2. Why is Squared Euclidean Distance preferred over standard Euclidean Distance during vector indexing?
Euclidean distance is $\sqrt{\sum (u_i - v_i)^2}$. The square root function ($\sqrt{\cdot}$) is strictly monotonic: for all $a, b \ge 0$, $a < b \iff \sqrt{a} < \sqrt{b}$. Computing the square root on modern CPUs requires multiple clock cycles and cannot be vectorized as efficiently as fused multiply-add (FMA). Omitting the square root yields identical distance rankings while significantly reducing CPU instruction overhead.

#### Q3. Why do cosine similarity and dot product produce identical rankings on $L_2$-normalized vectors?
The Euclidean distance squared between two unit-normalized vectors ($\|\mathbf{u}\| = \|\mathbf{v}\| = 1$) expands to:
$$\|\mathbf{u} - \mathbf{v}\|^2 = \|\mathbf{u}\|^2 + \|\mathbf{v}\|^2 - 2(\mathbf{u} \cdot \mathbf{v}) = 1 + 1 - 2(\mathbf{u} \cdot \mathbf{v}) = 2 - 2(\mathbf{u} \cdot \mathbf{v})$$
Because $\cos(\theta) = \frac{\mathbf{u} \cdot \mathbf{v}}{\|\mathbf{u}\| \|\mathbf{v}\|} = \mathbf{u} \cdot \mathbf{v}$, we have:
$$d_{L_2}^2(\mathbf{u}, \mathbf{v}) = 2(1 - \cos(\theta))$$
Maximizing Cosine Similarity is algebraically identical to maximizing the Dot Product and minimizing Euclidean Distance.

#### Q4. What is Manhattan Distance ($L_1$), and when is it preferred over Euclidean Distance ($L_2$)?
Manhattan distance is the sum of absolute coordinate differences: $\sum |u_i - v_i|$. As proven by *Aggarwal et al.*, for high-dimensional applications, $L_p$ norms with lower values of $p$ (like $L_1$) preserve distance contrast significantly better than higher norms ($L_2$ or $L_\infty$) as dimensionality increases. It is also less sensitive to extreme outliers along individual feature dimensions.

#### Q5. What is Hamming distance, and how do modern CPUs accelerate it in hardware?
Hamming distance measures the number of bit positions in which two binary vectors differ. Modern x86_64 and ARM CPUs provide dedicated assembly instructions: the bitwise `XOR` instruction followed by `POPCNT` (Population Count). A 512-dimensional binary vector fits in an AVX-512 register; its Hamming distance takes a few instructions (XOR, population count, reduce).

#### Q6. How does vector magnitude affect Dot Product similarity compared to Cosine Similarity?
Dot Product ($\mathbf{u} \cdot \mathbf{v} = \|\mathbf{u}\| \|\mathbf{v}\| \cos(\theta)$) scales linearly with vector magnitude. If a document vector has an artificially large norm, its dot product with the query will be massive, even if their directional angle is wide. Cosine similarity divides by vector norms, isolating pure angular direction regardless of document length or feature scale.

#### Q7. What is the Hubness Problem in high-dimensional nearest-neighbor graphs?
In high dimensions, certain data points (called "hubs") become the nearest neighbors to an abnormally large number of other points across the dataset, regardless of semantic meaning. In graph-based indexes (like NSW), hubs create routing bottlenecks and degrade navigation diversity. HNSW mitigates this via heuristic edge selection that enforces spatial diversity.

#### Q8. What is the difference between dense and sparse vector spaces in terms of linear algebra?
Dense vectors exist in continuous low-dimensional spaces ($D \sim 10^3$) where coordinates are non-zero real numbers; operations rely on matrix multiplications (BLAS/LAPACK). Sparse vectors exist in extremely high-dimensional spaces ($D \sim 10^5$) where $>99.9\%$ of coordinates are zero; operations rely on inverted posting lists and sparse dot products (evaluating only the intersection of non-zero indices).

#### Q9. Can you store both dense and sparse vectors in the same database point in Qdrant or Milvus?
Yes. Modern engines support **Named Vectors** (multivector support), allowing a single document point to store both a 1536-dimensional dense embedding (for conceptual semantic search) and a 30,000-dimensional sparse vector (for exact BM25 keyword matching).

#### Q10. How does floating-point precision (FP32 vs FP16 vs BF16) affect vector similarity accuracy?
FP32 uses 1 sign bit, 8 exponent bits, and 23 mantissa bits. FP16 uses 1 sign, 5 exponent, and 10 mantissa bits. In vector similarity, the relative ordering of distances is remarkably resilient to slight precision degradation; switching from FP32 to FP16 reduces memory by 50% with $<0.1\%$ difference in Recall@10.

### 7.2 Internals & Performance (Q11-Q30)

#### Q11. What is the mathematical intuition behind HNSW's skip-list hierarchy?
In a standard 1D Skip-List, elements are randomly promoted to higher layers with probability $p$, creating express lanes that enable $O(\log N)$ search over linked lists. HNSW generalizes this to graphs: each node is assigned a maximum layer $l = \lfloor -\ln(\text{uniform}(0, 1)) \cdot m_L \rfloor$. The top layer contains a very sparse graph with long-range edges for coarse, rapid exploration across the entire metric space. As search descends to Layer 0, the graph becomes dense with short-range edges for fine-grained local clustering.

#### Q12. What does the parameter $M$ in HNSW control, and what is the rule for Layer 0?
$M$ defines the maximum number of bidirectional connections (edges) each node can maintain in layers $> 0$. On the ground layer (Layer 0), the maximum degree is configured as $M_0 = 2M$. Because Layer 0 holds 100% of all vectors, doubling its connectivity ensures dense local clustering and prevents graph disconnections.

#### Q13. What is the purpose of $efConstruction$ vs $efSearch$ in HNSW?
Both control the size of the dynamic priority queue of candidate neighbors during search. $efConstruction$ is used when inserting a new vector into the graph during index build; higher values build a higher-quality graph with better global connectivity. $efSearch$ is used at query time; it controls how extensively the search algorithm explores the neighborhood on Layer 0 before returning the Top-$K$ results.

#### Q14. How does HNSW's Heuristic Edge Selection prevent redundant graph clusters?
A naive algorithm connects a new node to its $M$ nearest neighbors. However, if those neighbors are all tightly clustered together, they provide redundant routing directions. HNSW's heuristic selects a neighbor only if it is closer to the base node than to any already-selected neighbor. This enforces **directional diversity**, ensuring edges fan out like spokes on a wheel in all directions.

#### Q15. In an Inverted File (IVF) index, why does increasing $nprobe$ improve recall but lower QPS?
IVF partitions vectors into `nlist` Voronoi cells. At query time, `nprobe` dictates how many of the closest centroid cells to scan. If $\text{nprobe} = 1$, only 1 cell is scanned; vectors belonging to the query that fell across a cell boundary are missed. Increasing $\text{nprobe}$ scans more cells, capturing boundary vectors and improving recall, but linearly increases the number of distance calculations, reducing throughput (QPS).

#### Q16. How do you choose the optimal `nlist` parameter for an IVF index?
Standard empirical rule: $\text{nlist} \approx 4\sqrt{N}$ to $16\sqrt{N}$, where $N$ is total vectors. For $1,000,000$ vectors, $\sqrt{N} = 1,000$, yielding an optimal `nlist` between $4,000$ and $16,000$.

#### Q17. What is the primary operational drawback of tree-based Annoy indexes compared to HNSW?
Annoy builds static, immutable binary tree forests. Once built, the index cannot accept incremental inserts or deletions. Adding a single new vector requires re-clustering and rebuilding the entire forest from scratch. In contrast, HNSW supports dynamic real-time inserts and deletions.

#### Q18. What is Graph Disconnection in HNSW and how can it occur?
If vectors are deleted from an HNSW graph without repairing neighbor edges, or if $M$ is configured too small ($M < 4$) on disconnected multi-modal data, the graph can fracture into isolated sub-graphs. A query entering the graph in one component can never reach the other component, resulting in severe recall collapse.

#### Q19. How does HNSW handle node deletions in production engines?
Deleting a node directly from an in-memory graph is expensive because all incoming edges must be redirected. Modern engines (like Qdrant) use **Tombstoning**: the node is marked as deleted in a bitmap (ignored during queries), and background compaction routines rebuild clean graph segments asynchronously.

#### Q20. What is the time complexity of an HNSW query with respect to dataset size $N$?
Search complexity in HNSW scales logarithmically: **$O(\log N)$**. Each layer traversal takes $O(1)$ greedy steps, and the number of layers scales as $O(\log N)$.

#### Q21. How does Product Quantization (PQ) decompose a high-dimensional metric space?
PQ decomposes a $D$-dimensional space into a Cartesian product of $M$ orthogonal low-dimensional subspaces: $\mathbb{R}^D = \mathbb{R}^{D^*} \times \dots \times \mathbb{R}^{D^*}$, where $D^* = D / M$. For each subspace, k-means clusters sub-vectors into $K^* = 256$ centroids. Any vector is represented by $M$ centroid indices (each fitting in 1 byte).

#### Q22. What is the difference between ADC (Asymmetric Distance Computation) and SDC (Symmetric Distance Computation) in PQ?
- **SDC**: Both the database vectors and the query vector are quantized. Distance is computed between centroid codebooks.
- **ADC**: The query vector is left uncompressed; only database vectors are quantized. The query computes exact distances to the 256 centroids per subspace once, storing them in an $M \times 256$ lookup table. ADC is far more accurate than SDC with identical search time.

#### Q23. Why does Product Quantization require an initial "training" phase?
PQ must learn the optimal centroid codebooks for each subspace via k-means clustering. This requires running training iterations across a representative sample (typically 50,000 to 250,000 vectors) to minimize quantization distortion error before encoding database vectors.

#### Q24. What is Scalar Quantization (SQ8) dynamic range clipping via quantiles?
If a dataset has extreme outliers (e.g. one dimension with a value of $+12.0$ while $99.9\%$ of values fall between $-0.5$ and $+0.5$), naive min-max scaling will compress the entire meaningful range into a tiny fraction of the 256 integer buckets. Quantile clipping sets bounds at statistical quantiles (e.g. 0.005 and 0.995 or $\mu \pm 3\sigma$), clamping outliers and preserving resolution for $99\%$ of the data.

#### Q25. How does 1-bit Binary Quantization (BQ) achieve a $32\times$ memory compression?
Standard FP32 uses 32 bits (4 bytes) per dimension. BQ compresses each dimension into a single binary bit ($0$ or $1$) based on $v_i \ge 0$. A 1536-dimensional vector requires $1536 \text{ bits} = 192\text{ bytes}$, down from $6,144\text{ bytes}$ ($6144 / 192 = 32$).

#### Q26. When does Binary Quantization (BQ) fail to preserve search recall?
BQ fails on embedding models that are not trained with isotropic representations or where angular distributions are concentrated in a narrow cone. BQ works best on models specifically trained for binary quantization (like `cohere-embed-v3`) or high-dimensional embeddings ($D \ge 1024$) where high dimensions compensate for 1-bit coordinate loss.

#### Q27. What is Residual Vector Quantization (RVQ)?
RVQ applies quantization recursively: a primary quantizer encodes the vector, and a second quantizer encodes the *quantization residual error* (the difference between the original vector and the first centroid). This provides higher fidelity than standard PQ at slightly higher codebook storage.

#### Q28. How does Quantization affect HNSW graph construction vs query search?
During graph construction, computing exact FP32 distances builds the highest-quality graph topology. In production, engines often use uncompressed FP32 vectors during index build, but compress the vectors using SQ8 or PQ in RAM for query-time distance calculations.

#### Q29. What is Over-Sampling (Re-scoring) in quantized vector search?
When querying a quantized index, the engine retrieves an expanded candidate set (e.g. Top-$4K$ candidates using fast quantized ADC or Hamming distance), then fetches the uncompressed FP32 vectors from NVMe disk for only those $4K$ candidates to compute exact distances and return the final Top-$K$ items.

#### Q30. What is the throughput advantage of computing distance using an ADC lookup table over raw float dot products?
In ADC, computing similarity requires zero multiplications or floating-point operations in the inner loop. The CPU merely executes $M$ array lookups into cache-resident memory tables and accumulates the looked-up values, which is several times cheaper per candidate than a full-dimension dot product.

### 7.3 Architecture & Design (Q31-Q50)

#### Q31. Why does post-filtering cause recall collapse when metadata selectivity is high?
If only 1 out of 1,000 vectors matches a filter condition (0.1% selectivity), an ANN index searching globally for Top-10 neighbors will almost certainly retrieve 10 non-matching vectors. Discarding non-matching items leaves the client with zero results, even though thousands of matching vectors exist in the corpus.

#### Q32. How does Qdrant's single-stage filtered HNSW traversal work?
During HNSW graph exploration, the search algorithm evaluates neighbor nodes against an in-memory payload index. If a neighbor node fails the filter, it is excluded from the candidate queue (cannot be returned in search results), but its outgoing graph edges are still traversed as a valid bridge to reach other nodes that may pass the filter.

#### Q33. How does Roaring Bitmaps accelerate metadata filtering in vector databases?
Roaring Bitmaps compress boolean arrays representing which document IDs match specific filter conditions. They provide $O(1)$ set intersection (`AND`), union (`OR`), and difference (`NOT`) using CPU bitwise instructions, allowing instantaneous metadata checks during vector graph traversal.

#### Q34. What is the multi-tenancy risk of using a "Collection-per-Tenant" model at scale?
Each collection allocates independent HNSW graphs, thread pools, file descriptors, and buffer caches. At 10,000 tenants, the cluster exhausts OS file handles, encounters severe memory fragmentation, and crashes from metadata overhead.

#### Q35. How does the "Shared Collection with Partition Key" pattern achieve scalable multi-tenancy?
All tenants reside within a single shared collection. Vectors are assigned a `tenant_id` payload field backed by a payload index. When a tenant queries, the engine uses payload-filtered HNSW traversal to restrict graph search strictly to that tenant's vectors, allowing millions of tenants on modest cluster footprints.

#### Q36. What is Reciprocal Rank Fusion (RRF) and why is it preferred over weighted score combination in hybrid search?
In hybrid search, dense vector scores (cosine similarity bounded in $[-1, 1]$) and sparse lexical scores (BM25 unbounded in $[0, \infty)$) have completely different mathematical distributions. Normalizing them requires fragile min-max scaling that drifts as data changes. RRF bypasses score calibration entirely by evaluating only ordinal rank positions.

#### Q37. How do you implement vector search with hard security boundaries (e.g. GDPR right-to-be-forgotten)?
Isolate personal data in relational stores with strict encryption. Store only anonymized embeddings and UUIDs in the vector store. When a user exercises their right-to-be-forgotten, delete their relational identity and trigger an immediate point deletion in the vector database via its primary ID index.

#### Q38. Can vector databases filter on geo-spatial coordinates?
Yes. Engines like Qdrant and Weaviate maintain dedicated Geo-payload indexes (GeoHash/R-Tree) supporting bounding box and radius queries (e.g. `geo_distance(lat, lon) < 10km`) evaluated concurrently during vector search.

#### Q39. What is pre-filtering index estimation?
Before traversing an HNSW graph, the query planner estimates the selectivity of the metadata filter. If the filter matches $<1\%$ of data, it uses filtered HNSW traversal. If the filter matches $>95\%$ of data, it uses standard HNSW with light post-filtering. If the filter matches $<100$ total points, it bypasses the graph entirely and performs a brute-force SIMD scan.

#### Q40. How does payload index memory compare to vector embedding memory?
Payload indexes (keyword hash maps, boolean bitmaps) are orders of magnitude smaller than high-dimensional vectors, typically consuming $<5\%$ of total database RAM.

#### Q41. How does a distributed vector database handle query scatter-gather?
A coordinator node receives the query and broadcasts it to all relevant shards across the cluster. Each shard independently scans its local HNSW index to retrieve its Top-$K$ items. The coordinator collects all shard responses (total $S \times K$ candidates), merges and deduplicates them, sorts them by distance, and returns the global Top-$K$ to the client.

#### Q42. What is the function of the Write-Ahead Log (WAL) in vector databases?
The WAL guarantees durability (ACID 'D'). Incoming vector insertions are appended sequentially to a disk log on NVMe before being indexed into volatile in-memory buffer segments. If a server loses power, the database replays the WAL on restart to restore all pending points without data loss.

#### Q43. How does segment compaction prevent disk fragmentation in Qdrant and Milvus?
As vectors are updated or deleted, segments become filled with dead space and tombstoned points. Background compaction merges multiple smaller immutable segments into a single consolidated segment, building a fresh, optimized HNSW graph with zero dead points and reclaiming disk space.

#### Q44. What are the trade-offs of storing vectors on NVMe SSD via `mmap()` versus storing them in RAM?
- **RAM**: Search latency is sub-millisecond ($1$–$3\text{ms}$); maximum QPS; highest infrastructure cost.
- **MMAP on NVMe SSD**: 75% cheaper RAM footprint; search latency is $5$–$12\text{ms}$; throughput bounded by NVMe IOPS. The OS automatically manages the page cache, keeping frequently queried hot vectors in memory while paging cold vectors from SSD.

#### Q45. What is the role of Raft consensus in a distributed vector database cluster?
Raft maintains cluster-wide consistency for metadata operations: collection creation, schema modifications, shard assignment maps, node membership, and replica synchronization states.

#### Q46. How do you achieve zero-downtime re-indexing when changing vector dimensionality or distance metrics?
Use the **Blue-Green Collection Alias Pattern**:
1. Create a new collection (`index_v2`) with the new parameters.
2. Ingest vectors and build the index in the background.
3. Atomically update the production collection alias from `index_v1` to `index_v2`.
4. Delete `index_v1` once traffic transitions.

#### Q47. What causes CPU throttling during heavy vector ingestion in containerized environments (Kubernetes)?
Building HNSW graphs is intensely CPU-bound (multi-threaded distance calculations). If Kubernetes CPU limits (`resources.limits.cpu`) are set without accommodating thread pools, the Linux CFS (Completely Fair Scheduler) throttles the container, causing ingestion latencies to spike exponentially. Set CPU requests equal to limits or run dedicated vector worker nodes.

#### Q48. How does SIMD AVX-512 Fused Multiply-Add (FMA) accelerate dot product calculations?
The instruction `_mm512_fmadd_ps(a, b, c)` takes three 512-bit registers containing 16 single-precision floats each, multiplies $a \times b$ and adds $c$ with a single rounding step. Cores with two FMA units can issue two of these per cycle, so 32 float32 multiply-adds per cycle at best, before memory bandwidth becomes the limit.

#### Q49. What is Index Warmup and how do you prevent cold-cache query latency spikes after a restart?
After an engine restarts, the HNSW graph edges and vectors reside on disk and are not yet cached in the OS page cache. Production deployment scripts execute a warmup suite of 1,000 synthetic vector queries against all collections before adding the node back to the load balancer pool.

#### Q50. How do you measure the Pareto frontier of a vector database configuration?
By plotting **Recall@10** on the x-axis against **Queries Per Second (QPS)** on the y-axis while varying query-time parameters ($efSearch$ or $nprobe$). The curve establishes the optimal trade-off frontier for your specific latency and accuracy SLAs.

### 7.4 Scenario & Debugging Questions (Q51-Q53)

#### Q51. Recall on your RAG system dropped from 0.96 to 0.80 after a weekend deploy, with no errors. How do you investigate?

Start by separating the retrieval change from everything else. Re-run the offline recall benchmark (exact search vs the production index on a fixed query sample). If offline recall is still 0.96, the problem is upstream: compare the embedding call before and after the deploy. The usual causes are a changed model or model version, a dropped query prefix for an asymmetric model, a new truncation of Matryoshka embeddings without re-normalisation, or a different text pre-processing step. Embed the same ten queries with the old and new code and compare the vectors directly.

If offline recall also fell, look at the index: was it rebuilt with different `m` or `ef_construction`, did a config change lower `ef_search`, or did a large delete leave many tombstones (Stage 2.6)? `EXPLAIN` in pgvector or the collection info in Qdrant will show whether the index is used and whether optimisation is still running.

Fix the root cause, then prevent a repeat: pin the embedding model and version in config, store it in each point's payload, and run the recall benchmark in CI so a drop fails the deploy instead of surfacing in user complaints.

#### Q52. A pgvector query with `WHERE tenant_id = $1 ORDER BY embedding <=> $2 LIMIT 10` sometimes returns 2 rows for small tenants. Why, and what do you do?

The HNSW index scan returns at most `hnsw.ef_search` candidates (40 by default) in distance order, and PostgreSQL applies the `tenant_id` filter afterwards. For a tenant that owns 0.1% of the rows, most of those 40 candidates belong to other tenants, so only a couple survive. This is post-filtering recall collapse (Stage 5.1) inside the planner.

Options, in order of preference: enable iterative index scans (`SET hnsw.iterative_scan = relaxed_order`, pgvector 0.8+) so the scan keeps going until `LIMIT` rows pass; for very small tenants, let the planner use a B-tree on `tenant_id` and an exact scan of that tenant's rows (often faster than the graph anyway); for a few very large tenants, use partial indexes (`WHERE tenant_id = 42`) or list partitioning by tenant so each partition has its own HNSW index. Raising `ef_search` alone helps but costs every query.

Prevent a repeat with a test that asserts `count(*) = LIMIT` for the smallest tenant in a staging dataset; `sql/02_indexes.sql` contains exactly that check.

#### Q53. Qdrant memory usage keeps growing after you enabled scalar quantization. What is happening?

Check three things. First, whether the originals are still in RAM: quantization adds int8 codes, it does not remove float32 vectors, so without `on_disk: true` on the vector config memory goes up, not down. Second, whether optimisation is in progress: while segments are rebuilt with quantization, old and new segments coexist and memory temporarily doubles for those segments. Third, the OS page cache: mmap'd originals read during rescoring show up as cached memory, which the kernel reclaims under pressure, so look at the process RSS and the cgroup's working set separately from cache.

The fix is usually `on_disk: true` for originals with `always_ram: true` for quantized codes, then waiting for the optimizer to finish. Prevent surprises by sizing with Stage 3.1's formula plus headroom for one segment rebuild, and alert on optimizer status rather than raw memory alone.

### 7.5 Staff Cheatsheet

| Need | Vector database answer | Gotcha |
| --- | --- | --- |
| Text embeddings, which metric? | Cosine, or dot product on normalised vectors | Dot product on unnormalised vectors ranks long vectors first. |
| Small collection or tiny filtered set | Exact (flat) scan | Scales linearly; set a size threshold. |
| General in-memory ANN | HNSW, `m=16`, `ef_construction=128`, sweep `ef_search` | `ef_search` must be at least `k`. |
| Bulk load into pgvector | Load first, then `CREATE INDEX`, raise `maintenance_work_mem` | Building IVFFlat on an empty table ruins recall. |
| Memory too high | SQ8 codes in RAM, originals on disk, rescoring on | Quantization without `on_disk` adds memory. |
| 3,072-dim model in pgvector | Index `embedding::halfvec(3072)` | Queries must use the same cast. |
| Filtered queries return too few rows | Filter during traversal (payload index, iterative scans) | Post-filtering collapses at high selectivity. |
| Many tenants | Shared collection plus mandatory `tenant_id` filter | A missing filter is a data leak. |
| Exact identifiers matter | Hybrid dense plus sparse with RRF | Score scales differ; fuse ranks, not scores. |
| Change model or index settings | New collection, backfill, alias swap | Never mix models in one vector field. |

#### Vector Database Core Architecture Comparison

| Feature / Metric | PostgreSQL (`pgvector`) | Qdrant | Pinecone (Serverless) | Milvus | Weaviate |
| :--- | :--- | :--- | :--- | :--- | :--- |
| **Primary Language** | C (PostgreSQL Extension) | **Rust** | Proprietary Cloud | C++ / Go | Go |
| **Deployment Model** | Self-hosted / Managed RDS | Self-hosted / Cloud | Managed SaaS Only | Self-hosted / Cloud | Self-hosted / Cloud |
| **Primary ANN Index** | HNSW, IVFFlat | **HNSW** | Proprietary HNSW | HNSW, IVF, SCaNN | HNSW |
| **On-Disk Vector Storage**| Table pages on disk | **Native MMAP on SSD** | S3 + Local SSD Cache | MinIO / S3 Chunks | Virtual memory |
| **Quantization Support** | Half-vec (FP16), Bit (BQ) | **SQ8, PQ, BQ** | Automatic Managed | SQ8, PQ | SQ8, PQ |
| **Payload Filtering** | Full SQL (`WHERE`) | **Single-Stage Filtered HNSW** | Metadata Pre-filter | Boolean Expression Filter | Inverted Index Filter |
| **Multi-Tenancy** | Schema, Table, RLS | **Tenant ID Partitioning** | Namespaces | Partition Keys | Multi-Tenancy Class |

#### Essential RAM Sizing Rules of Thumb

- **Raw FP32 Vectors**: $\text{RAM (GB)} = \frac{N \times D \times 4}{10^9}$
- **HNSW Graph Overhead**: Add **$25\% - 40\%$** to raw vector RAM.
- **Scalar Quantization (SQ8)**: Divide vector RAM by **$4\times$**.
- **Product Quantization (PQ)**: Divide vector RAM by **$16\times - 64\times$**.
- **Qdrant On-Disk Vectors**: Only keep HNSW graph in RAM ($\sim 1.5\text{ KB}$ per vector regardless of dimension $D$).

[Back to top ⤴️](#-table-of-contents)

---

## 🧪 Example Projects

| Project | Builds on | What you practise | Stretch goal |
| --- | --- | --- | --- |
| [Starter project](./src/learn_vector_databases/) and [API](./app/main.py) (in this repo) | [Stage 1](#1-stage-1-vector-foundations-metrics--first-queries) to [Stage 3](#3-stage-3-quantization--memory-compression) | Metrics, flat/IVF/HNSW indexes, SQ8/PQ/BQ, filtered search over HTTP | Add a `DELETE /points/{id}` endpoint with tombstones and a background rebuild. |
| Semantic search over your notes | [1.2](#12-embeddings-where-vectors-come-from), [1.4](#14-first-queries-with-pgvector), [2.5](#25-hnsw-hyperparameters-m-ef_construction-and-ef_search) | Chunking, embedding, pgvector HNSW, `EXPLAIN` | Add a recall@10 regression test against exact search. |
| Recall/latency benchmark harness | [2.1](#21-exact-knn-vs-approximate-nearest-neighbor--recallk), [M1](#m1-masterclass-benchmarking-vector-search) | Ground truth, sweeps, Pareto curves | Run the same harness against pgvector and Qdrant on one dataset and plot both. |
| Memory-budget planner | [3.1](#31-sizing-memory-vectors-graph-and-overhead), [3.9](#39-quantization-trade-off-matrix) | Sizing formulas, compression ratios | Read real memory from Qdrant's telemetry and compare it with the estimate. |
| Image similarity with CLIP | [1.2](#12-embeddings-where-vectors-come-from), [3.7](#37-binary-quantization-bq-one-bit-per-dimension) | Multimodal embeddings, cosine, BQ with rescoring | Text-to-image queries in the same collection. |
| Multi-tenant document search | [5.7](#57-multi-tenancy-isolation-patterns-namespaces-vs-collections-vs-partition-keys), [M6](#m6-masterclass-production-blueprint-a-multi-tenant-hybrid-retrieval-service) | Payload indexes, mandatory tenant filters | A test that fails if any query is sent without a tenant filter. |
| Hybrid search for technical docs | [1.8](#18-dense-sparse--hybrid-representations), [5.10](#510-hybrid-search-fusing-vector-proximity-with-inverted-text-indexes), [M2](#m2-masterclass-hybrid-retrieval-and-reranking-pipelines) | Sparse plus dense vectors, RRF | Add a cross-encoder re-ranker and measure the gain. |
| Zero-downtime model migration | [6.9](#69-snapshot-backups-recovery--zero-downtime-index-rebuilding), [M5](#m5-masterclass-zero-downtime-embedding-model-migration) | Shadow collection, backfill, alias swap | Dual-write during backfill and compare result overlap before switching. |

## 📝 Cheat Sheets

### CLI / Commands

```bash
# Local engines
docker run -d --name pgvector -e POSTGRES_PASSWORD=postgres -p 5432:5432 pgvector/pgvector:pg17
docker run -d --name qdrant -p 6333:6333 -p 6334:6334 -v qdrant_storage:/qdrant/storage qdrant/qdrant

# pgvector
psql "$DATABASE_URL" -c "CREATE EXTENSION IF NOT EXISTS vector;"
psql "$DATABASE_URL" -c "SELECT extversion FROM pg_extension WHERE extname = 'vector';"
psql "$DATABASE_URL" -c "ALTER EXTENSION vector UPDATE;"
bash sql/run-all.sh

# Qdrant REST
curl -s localhost:6333/collections                          # list collections
curl -s localhost:6333/collections/docs                     # status, indexed_vectors_count, config
curl -s -X POST localhost:6333/collections/docs/snapshots   # snapshot
curl -s localhost:6333/metrics                              # Prometheus metrics

# Starter project
pytest -q
python -m src.learn_vector_databases.main
python -m src.learn_vector_databases.sweep --points 1000 --dims 32
python -m src.learn_vector_databases.sweep --quantization --points 2000 --dims 64
uvicorn app.main:app --port 8000
```

### pgvector Quick Reference

| Task | Code |
| --- | --- |
| Column types | `vector(768)`, `halfvec(3072)`, `bit(1024)`, `sparsevec(30000)` |
| L2 / cosine / negative inner product / L1 | `a <-> b`, `a <=> b`, `a <#> b`, `a <+> b` |
| Hamming / Jaccard on bits | `a <~> b`, `a <%> b` |
| Cosine similarity for display | `1 - (a <=> b)` |
| HNSW index | `CREATE INDEX ON t USING hnsw (embedding vector_cosine_ops) WITH (m = 16, ef_construction = 64);` |
| IVFFlat index | `CREATE INDEX ON t USING ivfflat (embedding vector_cosine_ops) WITH (lists = 1000);` |
| Query-time knobs | `SET hnsw.ef_search = 100;` `SET ivfflat.probes = 10;` |
| Filtered queries that must fill `LIMIT` | `SET hnsw.iterative_scan = relaxed_order;` |
| FP16 expression index | `CREATE INDEX ON t USING hnsw ((embedding::halfvec(3072)) halfvec_cosine_ops);` |
| Binary index | `CREATE INDEX ON t USING hnsw ((binary_quantize(embedding)::bit(1536)) bit_hamming_ops);` |
| Normalise | `l2_normalize(embedding)` |
| Faster index builds | `SET maintenance_work_mem = '4GB'; SET max_parallel_maintenance_workers = 7;` |

### Qdrant Quick Reference

| Task | REST body or call |
| --- | --- |
| Create collection | `PUT /collections/docs {"vectors": {"size": 768, "distance": "Cosine"}}` |
| HNSW settings | `"hnsw_config": {"m": 16, "ef_construct": 128}` |
| SQ8 codes in RAM, originals on disk | `"vectors": {..., "on_disk": true}, "quantization_config": {"scalar": {"type": "int8", "quantile": 0.99, "always_ram": true}}` |
| Upsert | `PUT /collections/docs/points?wait=true {"points": [{"id": 1, "vector": [...], "payload": {...}}]}` |
| Query | `POST /collections/docs/points/query {"query": [...], "limit": 10, "with_payload": true}` |
| Filter | `"filter": {"must": [{"key": "tenant_id", "match": {"value": "acme"}}]}` |
| Per-query `ef` and rescoring | `"params": {"hnsw_ef": 128, "quantization": {"rescore": true, "oversampling": 2.0}}` |
| Payload index | `PUT /collections/docs/index {"field_name": "tenant_id", "field_schema": "keyword"}` |
| Alias swap | `POST /collections/aliases {"actions": [{"create_alias": {"collection_name": "docs_v2", "alias_name": "docs"}}]}` |

## 📚 Resources

- [pgvector repository and documentation](https://github.com/pgvector/pgvector)
- [pgvector changelog](https://github.com/pgvector/pgvector/blob/master/CHANGELOG.md)
- [PostgreSQL documentation](https://www.postgresql.org/docs/current/)
- [Qdrant documentation](https://qdrant.tech/documentation/)
- [Qdrant releases](https://github.com/qdrant/qdrant/releases)
- [Milvus documentation](https://milvus.io/docs)
- [Weaviate documentation](https://weaviate.io/developers/weaviate)
- [Pinecone documentation](https://docs.pinecone.io/)
- [Chroma documentation](https://docs.trychroma.com/)
- [FAISS repository and wiki](https://github.com/facebookresearch/faiss)
- [ANN-Benchmarks](https://ann-benchmarks.com/)
- [HNSW paper: Malkov and Yashunin, "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs"](https://arxiv.org/abs/1603.09320)
- [Product quantization paper: Jégou, Douze and Schmid](https://ieeexplore.ieee.org/document/5432202)
- [DiskANN repository (Microsoft Research)](https://github.com/microsoft/DiskANN)
- [ScaNN paper: Accelerating Large-Scale Inference with Anisotropic Vector Quantization](https://arxiv.org/abs/1908.10396)

## 🤝 Contributing

Contributions are welcome. Read the [contributing guide](https://github.com/TheLearningHubOrg/.github/blob/main/CONTRIBUTING.md) and the [code of conduct](https://github.com/TheLearningHubOrg/.github/blob/main/CODE_OF_CONDUCT.md) before you open a pull request. Commit messages follow [Conventional Commits](https://www.conventionalcommits.org/), which drive the automated changelog.

## 📄 License

This project is licensed under the MIT License. See the [LICENSE](LICENSE) file for details.

## 🙏 Acknowledgments

- [pgvector](https://github.com/pgvector/pgvector) and the [PostgreSQL](https://www.postgresql.org/) project
- [Qdrant](https://qdrant.tech/), [Milvus](https://milvus.io/), [Weaviate](https://weaviate.io/), [Chroma](https://www.trychroma.com/) and [Pinecone](https://www.pinecone.io/) for documenting their engines in depth
- [FAISS](https://github.com/facebookresearch/faiss) and [ANN-Benchmarks](https://ann-benchmarks.com/) for the reference implementations and benchmarks the field relies on
- [FastAPI](https://fastapi.tiangolo.com/), [Uvicorn](https://www.uvicorn.org/), [pytest](https://docs.pytest.org/) and [Ruff](https://docs.astral.sh/ruff/), which the starter project uses

## 🌐 Connect with me

- [Twitter](https://twitter.com/manthan_ank)
- [LinkedIn](https://www.linkedin.com/in/manthanank)
- [Facebook](https://www.facebook.com/manthanank/)
- [Instagram](https://www.instagram.com/manthan_ank/)
- [YouTube](https://www.youtube.com/@manthanank)
- [GitHub](https://github.com/manthanank)

## ☕ Support

If you like this learning repository and find it useful, consider buying me a coffee or sponsoring me through GitHub Sponsors. Your support helps me keep these guides up to date. Thank you!

[![Buy Me A Coffee](https://img.shields.io/badge/Buy%20Me%20a%20Coffee-donate-FFDD00?logo=buymeacoffee&logoColor=000)](https://www.buymeacoffee.com/manthanank)

[![Sponsor Me](https://img.shields.io/badge/Sponsor-GitHub-green?logo=github)](https://github.com/sponsors/manthanank)

---

Show your support by 🌟 the repository.