Build Vector Search Inside a SQL Database

Vector Database from Scratch is a short hands-on course for systems and backend engineers. You will build a small in-memory vector database in Rust, start by running exact nearest-neighbor queries, and then add approximate indexes. The system will answer SQL top-k queries through DataFusion and make the tradeoff between recall, latency, and memory visible.

The original 2024 C++/BusTub course is preserved as a deprecated, unmaintained edition. It is no longer the recommended path for new learners.

Why Build a Vector Database?

Embeddings turn text, images, and other data into fixed-dimensional vectors. A vector database stores those vectors and retrieves the items closest to a query vector under a distance metric. Exact search compares the query with every stored vector. Approximate nearest-neighbor (ANN) indexes avoid much of that work in exchange for returning an imperfect result set.

This course builds vector search as a database feature rather than as an isolated ANN library. You will explore IVFFlat and graph indexes while seeing how vectors, distance expressions, query planning, execution, and indexes fit together behind one SQL top-k query.

What You Will Build

The six Rust days build:

1. An Arrow-backed vector table and a conservative DataFusion optimizer rule that selects a vector-index scan.
2. An IVFFlat index and recall harness that compare approximate results with exact search.
3. An NSW proximity graph with bounded reciprocal edges and adjustable search width.
4. An HNSW hierarchy that routes through sparse upper layers before searching the complete graph.
5. An IVF-PQ index that compresses residual candidate scoring and reranks a shortlist with exact distances.
6. A benchmark that compares Flat, IVFFlat, NSW, HNSW, and IVF-PQ on SIFT1M under the same Euclidean queries and k = 100, with an explicit non-parity smoke mode for quicker local feedback.

At its core, this is a regular Rust library. You will build a DataFusion adapter that recognizes a safe SQL top-k query and routes it to a vector index. The collection and indexes stay independent of Arrow and the query engine, so you can explore each layer on its own and then see them work together.

Learning Goals

After completing the course, you should be able to:

• define the semantics and edge cases of Euclidean, cosine, and inner-product search;
• preserve each row’s identity when converting vectors into Arrow arrays and a DataFusion TableProvider;
• explain how IVFFlat, graph indexes, and IVF-PQ trade build cost, representation size, latency, and recall;
• design benchmarks that compare ANN results with exact-search results;
• recognize when a SQL top-k query can safely use an approximate index; and
• separate a storage and search engine from its SQL interface.

What This Course Will Not Cover

You will not implement embedding models, persistent index files, online updates or deletes after an index is built, crash recovery, filtered ANN search, distributed execution, GPU kernels, or an HTTP service. You will implement the course’s indexes directly instead of calling an existing ANN library.

Those boundaries keep the course focused on vector search. They also make every required component small enough to test, measure, and explain.

Prerequisites

You should be comfortable with Rust ownership, traits, error handling, iterators, and Cargo. You should also know basic database concepts such as records, indexes, SQL ordering, and query plans.

Prior knowledge of nearest-neighbor algorithms, Apache Arrow, or DataFusion is not required. Day 1 introduces the small subset of DataFusion’s extension interface used by the course.

How to Use This Book

Start with the Rust course. It defines the architecture, system contract, starter workspace, progression, and scope. Each day pairs the book with starter code, focused tests, and a separate reference solution.

Each implementation day begins with a concrete goal, the relevant invariants, and a small prediction exercise. It ends with focused tests and a short reflection on what you observed.

Day 1 makes the table and optimizer rule runnable. Day 2 compares IVFFlat with exact search, Day 3 follows graph edges with NSW, and Day 4 adds sparse HNSW layers. Day 5 adds residual IVF-PQ behind the same collection and SQL boundary. Day 6 compares all five indexes under one fixed SIFT1M measurement contract, so the reported rank recall and latency fields describe the same data, queries, Euclidean metric, and k = 100.

Community

Join skyzh’s Discord server to study with the Vector Database from Scratch community.

About the Author

Chi is a database systems engineer and the author of Mini-LSM and LLM Serving in a Week. He has worked on storage and database systems including TiKV, AgateDB, TerarkDB, RisingWave, Neon, and RisingLight, and served as a teaching assistant for CMU’s Database Systems course.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

Build Vector Search in Rust

Begin with the supplied product tour. You will open an empty SQL session, create an in-memory points table, run a nearest-neighbor query, and attach an IVFFlat index to the table’s vector column. EXPLAIN makes the change in scan visible before you write any Rust.

The six implementation days then rebuild that path from the bottom up. Day 1 connects ordinary Arrow rows to DataFusion and adds the optimizer rule that can select a vector index safely. Days 2–5 implement IVFFlat, NSW, HNSW, and IVF-PQ behind the same query interface. Day 6 compares those four indexes with the exact flat baseline on SIFT1M. The benchmark keeps Euclidean distance and k = 100 fixed, and uses the same first-neighbor rank-recall definition and latency measurement procedure for all five indexes.

SELECT id, payload
FROM points
ORDER BY cosine_distance(embedding, [0.1, 0.2, 0.3])
LIMIT 10;

The product tour runs this shape of query through the supplied completed system. Before an index is attached, DataFusion scans every row, so the fallback result is exact. The tour then creates an IVFFlat index with two partitions and probes both of them. That particular indexed run still scores all five rows, although rows 3 and 5 tie for the third slot and SQL has no secondary ordering key to break the tie. IVFFlat becomes approximate when it probes only a subset of its partitions. In that case, DataFusion’s final sort orders the candidates returned by the index; it cannot recover rows that never entered the candidate set.

Day 1 asks you to build the table conversion, attachment, and planner path behind this observation. The later days replace the selected index while keeping the SQL interface and safety rule intact.

Where to Write Your Code

The repository-root Cargo workspace separates starter and reference trees:

vector-db-starter/
  core/                      dataset, IVFFlat, NSW, HNSW, benchmark, and IVF-PQ TODOs
  datafusion/                Day 1 Arrow table and optimizer-rule TODOs
vector-db/
  core/                      completed core reference
  datafusion/                completed DataFusion reference

The product tour executes a supplied example from vector-db/. Leave that completed implementation closed and unchanged. Your work begins in vector-db-starter/, where the TODOs are arranged in day order. The AGENTS.md files in the two starter crates state the same boundary.

From the repository root, check that the untouched starter compiles:

cargo check -p vector-db-from-scratch-core-starter
cargo check -p vector-db-from-scratch-datafusion-starter

The focused tests initially stop at todo! calls. Each day places its checkpoint command next to the code it exercises. At the end of a day, run cargo xtask test day_NN for that day’s work and cargo xtask test-through day_NN for the cumulative course.

One Query, Two Plans

Before index matching, the query is exact:

SortExec: TopK(fetch=10), ...
  DataSourceExec: partitions=1, ...

An ordinary MemTable emits Arrow rows. DataFusion evaluates the distance function for every row and uses its own bounded sort to produce the nearest ten. This is the exact fallback path.

On Day 1, you attach one index to an explicitly selected vector column, then implement a physical optimizer rule. It accepts only one compatible distance ordering over that configured field with a literal query vector. The matched scan asks the selected index for LIMIT k candidate row identities:

SortExec: TopK(fetch=10), ...
  VectorIndexScanExec: index=flat, metric=Cosine, query_dim=3, fetch=Some(10), ordered=false

The starter’s exact FlatIndex lets you exercise this rule on Day 1. Later days change the selected index:

SortExec: TopK(fetch=10), ...
  VectorIndexScanExec: index=ivf_flat, metric=Cosine, query_dim=3, fetch=Some(10), ordered=false

SortExec: TopK(fetch=10), ...
  VectorIndexScanExec: index=nsw, metric=Cosine, query_dim=3, fetch=Some(10), ordered=false

SortExec: TopK(fetch=10), ...
  VectorIndexScanExec: index=hnsw, metric=Cosine, query_dim=3, fetch=Some(10), ordered=false

The default plan retains DataFusion’s bounded sort. The index chooses the candidate rows, and SortExec orders those candidates for SQL. When an index guarantees that its output is already in the requested order, SET vector_search.ordered = true lets DataFusion skip the final sort.

The optimizer keeps the exact plan for filters, multiple sort keys, a non-literal query vector, another same-shaped vector column, the wrong distance function or direction, and dimension mismatches. This conservative behavior matters: for example, taking ANN top-k before applying a filter can change the answer.

Architecture

ordinary MemTable --> selected-column attachment --> DataFusion optimizer --> VectorIndexScanExec
                                                                            |-- exact FlatIndex
                                                                            |-- your IvfFlatIndex
                                                                            |-- your IvfPqIndex
                                                                            |-- your NswIndex
                                                                            `-- your HnswIndex

The DataFusion crate owns Arrow conversion and the SQL-facing execution path: pattern matching, plan properties, limits, and output batches. The core crate owns vector dimensions, metrics, search results, candidate selection, and deterministic result order. The later index implementations do not need to import DataFusion.

This split gives you two ways to check Days 1–5. Small Rust tests isolate the algorithm, while self-contained SQLLogicTests show that the Day 1 optimizer can reach it. Day 5 adds a focused planner/EXPLAIN test for IVF-PQ. Day 6 moves all five indexes into one full-SIFT1M comparison; its smaller smoke mode is explicitly not a parity run.

Rules That Stay Fixed

1. Dimension: a dataset has one nonzero dimension; every stored vector and query matches it.
2. Numeric domain: stored values are finite f32, while metric accumulation uses f64. Cosine inputs have nonzero norm.
3. Identity: each core row offset maps through the attachment’s checked snapshot location to the complete source row; no user field is row identity.
4. Ordering: lower internal distance is better. Ties use row offset. Dot product is negated at the metric boundary.
5. Exact baseline: exact search defines the expected result. When you report approximate latency, include recall from the same data, queries, metric, and k.
6. SQL safety: the optimizer selects an index only when expression, metric, direction, dimension, and limit match its contract. Unsupported shapes remain exact.

Course Progression

Day 1 establishes the end-to-end path: a Rust row becomes a core offset and an Arrow row, the optimizer recognizes a safe physical expression, and incompatible or filtered queries stay on the exact scan. This rule has to work before an approximate index can be reached from SQL.

The next four days change how candidates are found. IVFFlat trains centroids, rebuilds list membership after the final centroid update, and exposes probes as its recall/work control. NSW uses separate candidate and result frontiers while reciprocal pruning keeps the graph bounded. HNSW adds seeded, reproducible promotion, greedy upper-layer routing, and a layer-zero beam. IVF-PQ keeps coarse centroids, residual codebooks, approximate lookup-table scoring, and exact reranking as distinct parts of the search.

The final benchmark holds the workload still while those choices change. Exact first-neighbor truth is supplied or recomputed from the same data and queries, and every index uses the same Euclidean metric and k = 100. Cyclic warm-up and timing order make the resulting rank-recall and latency numbers comparable.

Scope

The course uses an immutable in-memory collection and a readable Euclidean residual IVF-PQ implementation. It does not add bit packing or optimized kernels. Online updates and deletes, index persistence, crash recovery, concurrent mutation, filtered ANN, GPU kernels, distributed execution, a general catalog, and a network service are outside the implementation.

The supplied shell includes a narrow CREATE INDEX bridge for eligible named or qualified in-memory tables. It supports multiple distinct attachments and rejects writes that would stale an indexed snapshot, but it is not a persistence or online-maintenance subsystem. Day 6 assumes that you have acquired SIFT1M locally. The repository provides parsers and small corruption fixtures, not the external corpus or benchmark results.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

Try the Vector Database from SQL

Start by running the supplied system. This gives you the complete SQL path before Day 1 asks you to build it: an ordinary in-memory table answers an exact nearest-neighbor query, then an IVFFlat index changes how the database finds candidates. You will compare the plans and results from both runs.

The tour uses the completed vector-db-from-scratch-datafusion example. Leave its source as it is for now; your own work begins on Day 1.

Launch the Supplied Shell

From the repository root, launch an interactive session with:

cargo run -p vector-db-from-scratch-datafusion --example sql

Each session starts empty. The supplied DataFusion CLI accepts semicolon-terminated SQL, including statements that span multiple lines. For a repeatable first run, paste this entire transcript into your terminal:

cargo run -p vector-db-from-scratch-datafusion --example sql <<'SQL'
CREATE TABLE points (id BIGINT NOT NULL, payload VARCHAR NOT NULL, embedding REAL[3] NOT NULL);
INSERT INTO points VALUES (1, 'one', [1.0, 0.0, 0.0]), (2, 'two', [0.9, 0.1, 0.0]), (3, 'three', [0.0, 1.0, 0.0]), (4, 'four', [-1.0, 0.0, 0.0]), (5, 'five', [0.0, 0.0, 1.0]);
EXPLAIN SELECT id, payload FROM points ORDER BY cosine_distance(embedding, [1.0, 0.0, 0.0]) LIMIT 3;
SELECT id, payload FROM points ORDER BY cosine_distance(embedding, [1.0, 0.0, 0.0]) LIMIT 3;
CREATE INDEX points_embedding_idx ON points USING ivfflat (embedding);
EXPLAIN SELECT id, payload FROM points ORDER BY cosine_distance(embedding, [1.0, 0.0, 0.0]) LIMIT 3;
SELECT id, payload FROM points ORDER BY cosine_distance(embedding, [1.0, 0.0, 0.0]) LIMIT 3;
SQL

Before you run it, predict which rows the exact scan should rank nearest. Afterward, compare that answer with the indexed result and identify which differences this tiny exhaustive tour can actually produce.

Watch the Scan Change

The first EXPLAIN shows DataFusion reading the ordinary in-memory table:

SortExec: TopK(fetch=3), ...
  DataSourceExec: partitions=1, ...

In this run, the exact query returns:

1  one
2  two
3  three

Rows 1 and 2 are uniquely nearest. Rows 3 and 5 have the same cosine distance and tie for the third slot, so without a secondary ORDER BY key SQL does not require DataFusion to choose between them deterministically.

The next command attaches an index. Although the following SELECT is byte-for-byte identical, its physical plan now reaches the course-owned scan:

SortExec: TopK(fetch=3), ...
  VectorIndexScanExec: index=ivf_flat, metric=Cosine, query_dim=3, fetch=Some(3), ordered=false

When the second SELECT executes this plan, the shell confirms the choice on standard error:

Vector index selected: index=ivf_flat, metric=Cosine, query_dim=3, fetch=3, ordered=false

In this run, the indexed query returns rows 1, 2, and 3 in the same order as the exact scan. The tiny tour builds two IVFFlat partitions and probes both, so it computes cosine distance for all five rows. Only the exact tie between rows 3 and 5 can change the third slot here. IVFFlat is generally approximate when it probes only a subset of its partitions; in those configurations, candidate membership and ordering may change. DataFusion applies the final sort to the candidates it receives, using the same cosine distance and LIMIT 3 from the SQL.

What CREATE INDEX Does Here

DataFusion parses and logically plans CREATE INDEX, but the pinned version does not provide a physical executor that can build this course’s index. The supplied shell handles that statement through a small bridge to the course’s existing attachment path. The session is configured for cosine IVFFlat; the statement supplies the index name, table, and vector column:

CREATE INDEX points_embedding_idx ON points USING ivfflat (embedding)

The name may be any unused index name, and the table may be bare or schema/catalog qualified. A single session can attach indexes to several table and column pairs because the bridge resolves the target from each SQL statement; it does not hard-code the points example. Each table must be a registered in-memory MemTable, and the selected column must be a non-null REAL[N] vector with positive width. The shell rejects duplicate names or attachments, missing tables or columns, other provider types, nullable fields, incompatible vector fields, and an index kind that differs from the session configuration.

An attachment is an immutable snapshot. After a table is indexed, INSERT, ALTER TABLE, and DROP TABLE against that table are rejected instead of making the index stale. Writes to unrelated tables remain legal, as does INSERT ... SELECT that reads indexed data into another table. A later insert would leave the snapshot behind, so the shell rejects it until the table update and a rebuilt index could become visible together. Index persistence, DROP INDEX, automatic rebuilding, and a general catalog lifecycle are outside this bridge.

Next, Day 1 opens the path you just ran. You will build the Arrow table, attach one vector field, and make the optimizer choose VectorIndexScanExec only for a safe match.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

Make the SQL Path Reach Your Index Safely

Day 1

Start from the two *-starter crates. Finish with ordinary Arrow tables, one explicitly attached vector index, and a conservative DataFusion optimizer rule.

The product tour began with an empty session and an ordinary in-memory points table. Its first nearest-neighbor query used DataFusion’s exact scan and returned rows 1, 2, and 3. After the tour attached an IVFFlat index to embedding, the same SQL reached VectorIndexScanExec and returned 1, 2, and 3 again. Rows 3 and 5 tie for that final slot, however, so SQL does not promise which one appears unless you add a secondary ordering key.

That small example probes both of its two partitions and therefore scores all five rows. IVFFlat is still an approximate index when it probes only a subset of its partitions: it may omit a true neighbor before DataFusion sees the candidates. The final sort orders the rows it receives; it does not make the candidate set exact.

Day 1 rebuilds the safe path beneath that tour. You will create an Arrow table, attach an exact FlatIndex to one selected vector field, and teach DataFusion to use the new scan only when the physical query matches the attachment.

Your first query uses the course’s small three-column table:

SELECT id, payload
FROM points
ORDER BY cosine_distance(embedding, [1.0, 0.0, 0.0])
LIMIT 3;

Before an index matches, DataFusion scans the MemTable, computes every distance, and keeps the nearest three with a bounded sort:

SortExec: TopK(fetch=3), ...
  DataSourceExec: partitions=1, ...

This fallback is exact for every valid query. An attachment may replace the leaf only when the SQL ordering uses its configured vector column with the expected metric, literal, dimension, and direction. A safe match leaves DataFusion’s final sort in place by default:

SortExec: TopK(fetch=3), ...
  VectorIndexScanExec: index=flat, metric=Cosine, query_dim=3, fetch=Some(3), ordered=false

Day 2 will put index=ivf_flat behind this same boundary.

From the Product Tour to Your First Checkpoint

The shell and its narrow CREATE INDEX bridge are already complete. So are the metric implementations, the exact FlatIndex, the public attachment and optimizer interfaces, and the snapshot lookup scaffolding. Examples and tests let you inspect both the physical plan and the returned rows.

Your five checkpoints fill in the path between those supplied pieces. First validate the core Dataset, then turn the small example into an Arrow MemTable. Next attach one selected field, recognize a safe top-k plan, and use index results to fetch complete source rows in SQL order.

You will modify:

vector-db-starter/core/src/dataset.rs
vector-db-starter/datafusion/src/lib.rs

The starter exposes the complete Day 1 API and marks your implementation points with TODOs. Work through those TODOs in checkpoint order, leaving the public APIs and tests unchanged. IVFFlat, NSW, HNSW, and IVF-PQ belong to later days.

Checkpoint 1: Validate the In-Memory Dataset

Implement the three TODOs in vector-db-starter/core/src/dataset.rs.

Dataset::try_new takes ownership of a nonempty set of finite f32 vectors with one positive dimension. Use the first row to establish that dimension, reject an empty dataset or zero-dimensional vector, and check every remaining row for the same length and finite components. Store the validated vectors as Arc<[Vec<f32>]>.

validate_for_metric rejects zero-norm stored rows for cosine distance. validate_query checks dimension, finiteness, and the same cosine boundary for a query. Use the existing VectorError variants.

cargo xtask test day_01::checkpoint_1

Checkpoint 2: Build the Introductory MemTable

A vector index belongs to one field of an ordinary table. The rest of the row keeps its normal Arrow types and layout.

The small VectorRow and vector_mem_table helper make the first conversion concrete:

id         UInt64
payload    Utf8
embedding  FixedSizeList<Float32, dimension>

Implement vector_mem_table in vector-db-starter/datafusion/src/lib.rs.

Build a Dataset from the VectorRow embeddings so the core validation establishes their shared dimension. Create the three Arrow arrays in input order, assemble one RecordBatch, and return it through an ordinary MemTable.

FixedSizeListArray stores vector components in one flat Float32Array. For two three-dimensional rows, its child values are:

[x0, y0, z0, x1, y1, z1]
 `---row 0--' `---row 1--'

Use i32::try_from(dataset.dimension()) for Arrow’s list width. Keep every array in the same row order: if the payload array is reordered while the embeddings stay in insertion order, a query will return payloads that belong to different vectors.

cargo xtask test day_01::checkpoint_2

Checkpoint 3: Attach One Selected Vector Column

The small helper is only an introduction. The indexing surface accepts any registered MemTable and binds an index to one named vector field. Construct that binding with VectorIndexAttachment:

let attachment = VectorIndexAttachment::try_new(
    &context,
    "documents",
    &table,
    "text_embedding",
    Metric::Euclidean,
    IndexConfig::Flat,
)
.await?;
let context = with_vector_indexes(&context, vec![attachment]);

The supplied SQL session uses this same constructor for every accepted CREATE INDEX. Its DDL bridge is already implemented; your Day 1 work begins where that bridge hands off the table and selected field.

The rich Day 1 test table deliberately puts ordinary scalar fields around two vector fields:

doc_key         Utf8
tenant_id       UInt32
price           Float64
inventory       Int32
text_embedding  FixedSizeList<Float32, 3>  <- selected
image_embedding FixedSizeList<Float32, 3>
active          Boolean

Both vector columns have the same type and width, but their nearest-neighbor orders differ. Attach the index to text_embedding and that field’s query may use it. The same query over image_embedding must keep DataFusion’s exact scan and return the image-vector ranking. Its shape alone is not enough: the attachment’s selected field owns the index.

The attachment snapshots every batch in the registered MemTable. It copies the selected vectors into the core Dataset and records where each dataset ordinal came from:

index dataset ordinal -> snapshot RowId -> checked batch/row -> projected output

The source Arrow buffers remain shared with the MemTable; scalar columns and the unselected vector column stay ordinary table data. A user column cannot stand in for row identity, so lookup follows the recorded snapshot location instead.

DataFusion has no generic stable point-lookup API for arbitrary TableProvider implementations. Day 1 therefore works only with registered in-memory MemTable instances. A disk or distributed provider would need its own stable row locator and lookup implementation.

Implement VectorIndexAttachment::try_new.

First resolve the table reference and confirm that the supplied Arc<MemTable> is the registered provider. Snapshot all of its partitions and batches under one shared schema, then resolve the configured field by name. That field must be FixedSizeList<Float32> with a positive width, no null lists, and no null elements.

Copy its vectors into Dataset in batch and row order. For every dataset ordinal, record the matching checked snapshot location, then build the requested core index. The selected field determines the dataset dimension, so any positive list width is valid here; the SQL matcher will reject a query literal with a different width. The rich-schema tests make the ownership rule visible because the same-shaped text and image fields produce different rankings.

cargo xtask test day_01::checkpoint_3

Checkpoint 4: Match and Rewrite One Safe Top-k

Implement match_vector_order and VectorIndexOptimizer::rewrite_sort.

The optimizer may replace a scan only when it recognizes one supported distance expression over the configured vector field, a literal query vector, a compatible metric and direction, a positive LIMIT, and the live source snapshot.

Match exactly one physical sort expression: ascending Euclidean array_distance/list_distance or cosine_distance, or descending dot inner_product/dot_product. The expression must pair one vector Column with one literal. After any projection, the column must still be the field selected by the attachment. The literal must be finite, match the index dataset’s dimension, and be nonzero for cosine distance.

DataFusion widens the fixed-size Float32 list to List<Float64> for its distance functions. match_vector_column accepts exactly that planner-added cast, while scalar_vector admits only values that preserve their exact f32 representation.

The optimizer must also prove that the physical MemorySourceConfig still matches the attached table, snapshot, schema, projection, and unambiguous live provider. Only then may it construct VectorIndexScanExec. Filters, multiple sort keys, non-literal vectors, another vector field, the wrong metric or direction, and invalid literals all keep DataFusion’s exact scan and sort.

Unless ordered output is explicitly enabled for the session, retain the final bounded sort after the index selects its candidates. The order returned by an index is not automatically SQL order.

cargo xtask test day_01::checkpoint_4

Checkpoint 5: Search, Fetch, and Preserve ORDER BY

Implement VectorIndexScanExec::selected_rows and ExecutionPlan::with_fetch.

Search the selected index for at most fetch rows. Every result must resolve through its checked location into the snapshot; reject one that does not. The supplied lookup scaffolding then reconstructs the requested projection in index-result order.

When ordered=true, the scan may expose its accepted ordering property. The default ordered=false path must clear that property and wrap the scan in SortExec::new(ordering, scan).with_fetch(Some(k)). The index chooses candidates; DataFusion still owns SQL’s nearest-first result.

cargo xtask test day_01::checkpoint_5

The SQLLogicTest assembles the same path from an empty session. It creates and fills the simple points table and the rich documents table, then attaches indexes to their selected fields. text_embedding reaches VectorIndexScanExec; image_embedding stays on DataSourceExec and returns its own ranking.

Day 1 Review

Run the Day 1 focused and cumulative gates:

cargo xtask test day_01
cargo xtask test-through day_01

At this point, trace one row through the whole system. vector_mem_table places the simple helper data in ordinary Arrow arrays. An attachment snapshots one selected vector field, maps each index ordinal to a checked batch and row, and uses that location to project the complete source row. A same-shaped vector field cannot borrow the attachment because its name and ranking belong to a different field.

Then trace the plan boundary. Unsupported query shapes stay on DataFusion’s exact scan and sort. A safe match lets the index choose candidates, while the default path keeps DataFusion’s final ordering. Later approximate indexes reuse this boundary, but their candidate set can be incomplete before the final sort. The supplied session protects the snapshot by rejecting changes to an indexed table instead of allowing its attachment to become stale.

IVFFlat implementation, filtered pushdown, joins, general DDL/catalog semantics, persistence, and disk row lookup remain outside Day 1. The product tour’s bridge can hold multiple attachments for eligible in-memory tables and selected fields; it does not provide persistence, automatic rebuilding, online maintenance, or a general catalog lifecycle.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

Narrow the Search with IVFFlat

Day 2

Complete Make the SQL Path Reach Your Index Safely first. Finish with a seeded IVFFlat index behind the same SQL top-k path, recall defined against exact search, and an explicit probes tradeoff.

Day 1 left you with an exact FlatIndex behind a conservative DataFusion path. The SQL matcher, selected vector column, checked row lookup, and final SortExec are already working. Day 2 leaves that path intact and changes candidate selection. IVFFlat groups rows into inverted lists around centroids, ranks those centroids for each query, and scores the full-precision vectors in the selected lists.

Start from the SQL Path You Already Own

The Day 2 SQL case keeps Day 1’s table, matcher, lookup, and Euclidean query:

SELECT id, payload
FROM points
ORDER BY array_distance(embedding, [1.0, 1.0, 1.0])
LIMIT 5;

From the repository root, confirm that your completed Day 1 path is still green:

cargo xtask test day_01

Then run the Day 2 SQL case:

cargo xtask test day_02::checkpoint_5

It uses the existing DataFusion integration with IndexConfig::IvfFlat and currently stops at the unfinished IVFFlat constructor. After the three learner-owned functions are complete, the same command reaches this plan and returns the five expected rows:

SortExec: TopK(fetch=5), ...
  VectorIndexScanExec: index=ivf_flat, metric=Euclidean, query_dim=3, fetch=Some(5), ordered=false

Your work is limited to three functions:

vector-db-starter/core/src/search.rs    recall_at_k
vector-db-starter/core/src/ivf.rs       IvfFlatIndex::try_new
vector-db-starter/core/src/ivf.rs       IvfFlatIndex::search_with_probes

The starter supplies Dataset, Metric, TopK, DeterministicRng, the IVFFlat configuration and public index shell, and the complete Day 1 DataFusion path. Keep those public APIs and the Day 1 tests unchanged.

Checkpoint 1: Define Recall against Flat Search

Implement recall_at_k in search.rs. Recall measures how many row offsets from the exact top-k also appear in the approximate top-k:

expected = [0, 1, 2]
actual   = [0, 2, 9]
recall@3 = 2 / 3

Compare row membership rather than distance equality or result position, and count each row at most once. The denominator is the number of exact results available within k, which can be smaller than k. If exact search returns two rows for k = 10, those two rows form the whole expected set. Define recall as 1.0 when that set is empty.

cargo xtask test day_02::checkpoint_1

This overlap gives the approximate result a correctness measure. Day 6 will handle timing and compare all five indexes under one shared workload.

Checkpoint 2: Validate and Seed the Build

Implement the validation boundary at the start of IvfFlatIndex::try_new. The configuration must satisfy 1 <= probes <= partitions <= rows with iterations > 0. Call dataset.validate_for_metric(metric) before training so cosine builds reject zero-norm rows just as exact search does.

cargo xtask test day_02::checkpoint_2

After validation, initialize the centroids. Use the supplied DeterministicRng to shuffle the row offsets, then copy the first partitions dataset rows. Each selected offset is distinct, so two centroids never begin from the same row.

For a tiny build with six rows and two partitions, the initial state is:

dataset rows:     0 1 2 3 4 5
seeded centroids: two distinct shuffled row offsets
assignments:      unknown until the first assignment pass

The selected rows depend on both the seed and the order in which your implementation consumes the generator. Build the same index twice and its centroids, lists, and results must match. Another correct implementation can consume the same seed differently and choose different initial rows, so matching a reference centroid identity is not part of the contract.

Before the index exists, all points belong to one unpartitioned dataset, so an exact query compares its target with every point.

K-means alternates between assigning every vector to its nearest centroid and moving each centroid to the mean of its assigned vectors. Each colored region will become one inverted list.

Checkpoint 3: Alternate Assignment and Update

Run at most iterations rounds. In each round, assign every vector to its nearest centroid using Metric::distance. If the complete assignment vector has not changed, training can stop. Otherwise, accumulate a component-wise sum and row count for each partition, then replace each non-empty centroid with its mean. Keep the sums in f64, as the supplied metric code does for distances; Euclidean, dot, and cosine builds must use their configured metric throughout.

repeat up to iterations:
    next_assignments = nearest_centroid(row) for every row
    if next_assignments == assignments:
        stop
    assignments = next_assignments
    recompute each centroid from its assigned rows

rebuild lists once using the final centroids

After the last centroid update, assign every vector once more using the final centroids. The rebuilt lists must contain every dataset row exactly once. An omitted row becomes invisible to every query. A duplicate can occupy the result heap twice and crowd out a distinct row even though both copies have the same exact distance.

The extra assignment matters because the preceding one described the centroid positions before their final update. A row left in an old list is still found when every partition is probed, but it can be missed by a subset-probe query.

Recover Empty and Zero-Mean Clusters

An empty cluster has no mean. Re-seed it from the dataset row farthest from its nearest current centroid so the configured partition count stays intact.

Cosine needs a separate recovery. Nonzero assigned vectors can still average to the zero vector: [1, 0] and [-1, 0] are the smallest example. Normalize a nonzero cosine centroid after computing its mean. When the mean has zero norm, replace it with one of that cluster’s assigned rows, whose nonzero norm was already checked by Day 1 validation. Keeping the zero mean would make the next cosine-distance calculation invalid.

Run the deterministic-build and zero-mean cases:

cargo xtask test day_02::checkpoint_3

Checkpoint 4: Probe Lists at Query Time

Implement search_with_probes. Validate the query and require 1 <= probes <= partitions before scanning a list. Score each centroid against the query and sort the resulting Neighbor values nearest-first. The first probes entries select the lists to visit; score every row in their union with the original metric, feed it into the supplied TopK, and return the retained neighbors nearest-first. A probe count above the partition count is an error, not permission to revisit a partition.

Centroid assignment, centroid ranking, and candidate scoring all use the index metric. Mixing them would select lists for one notion of distance and order their rows by another. Keep one TopK across the union of candidates because SQL asks for the best k overall, not a separate result from each list.

The red vector below probes its nearest centroid’s list. It can miss a closer point just across the partition boundary:

Probing the next-nearest list exposes more candidates. Increasing probes does more candidate work and makes a true neighbor less likely to be missed:

Suppose the list sizes by ID are [10, 40, 5], while the query ranks the IDs as [2, 0, 1]. With probes = 1, search reads the five rows in list 2. With probes = 2, it also reads the ten rows in list 0. probes controls which candidates can enter the heap; k controls how many of them remain in the result.

Measure recall against exact search with the same data, query, metric, and k, so candidate selection is the only changing variable.

Probe every partition for the exactness boundary. IVFFlat then visits every dataset row and must produce the same complete ordered result as FlatIndex, including tie order:

cargo xtask test day_02::checkpoint_4

If this case fails, inspect list completeness, metric choice, heap retention, and final sorting. Every row was available, so subset probing cannot explain a difference.

Checkpoint 5: Put IVFFlat behind the Same SQL

Return to the product-level case you ran at the start:

cargo xtask test day_02::checkpoint_5

The SQL text and Day 1 matcher are unchanged. DataFusion passes LIMIT 5 through with_fetch, and VectorIndexScanExec calls IvfFlatIndex::search with the configured probes. The generic bounded sort still produces the final SQL order. Unsupported query shapes remain on the exact DataSourceExec path.

The test probes all three partitions, so its five returned rows match exact search. A smaller probe count may select a different candidate set.

Checkpoint 6: Run the Day 2 Product Loop

Run the supplied example after the focused core and SQL tests pass:

cargo run -p vector-db-from-scratch-datafusion-starter --example ivfflat_sql

The example runs one cosine top-k over the same five-row table, first through a Flat attachment and then through a seeded IVFFlat attachment with all partitions probed. Compare the two EXPLAIN leaves:

VectorIndexScanExec: index=flat, metric=Cosine, query_dim=3, fetch=Some(3), ordered=false
VectorIndexScanExec: index=ivf_flat, metric=Cosine, query_dim=3, fetch=Some(3), ordered=false

Both runs keep DataFusion’s final SortExec and return the same three rows. Only candidate selection changed. Smaller probe counts expose the recall/work tradeoff; Day 6 owns the release-mode latency comparison across all five indexes.

Day 2 Review

Run the Day 2 focused gate, then the cumulative course through Day 2:

cargo xtask test day_02
cargo xtask test-through day_02

Choose one concrete build and query, then trace it from validation through the SQL result. Explain how the seed initializes that build, why list membership is rebuilt after the final centroid update, and how one dataset row moves from assignment to a probed list and into TopK. Account separately for an empty cluster and a zero-mean cosine cluster.

Finally, connect the core index to Day 1: the optimizer’s safety rule is unchanged, the index supplies candidates, and the final sort still belongs to DataFusion. Probing every list should recover Flat search, while subset probing may trade recall for less candidate work. Persistent postings, online centroid retraining, product quantization, cross-index timing, and reproducible latency targets remain for later work.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

Navigate a Proximity Graph with NSW

Day 3

Complete Narrow the Search with IVFFlat first. You will replace centroid/list selection with graph reachability while keeping the SQL matcher, row lookup, and final top-k sort supplied.

Move from Lists to a Graph

Day 2 ended with a five-row cosine query running through IVFFlat. From the repository root, run that product path once more:

cargo run -p vector-db-from-scratch-datafusion-starter --example ivfflat_sql

The seeded IVFFlat plan contains index=ivf_flat, and its LIMIT 3 result is:

(1, one)
(2, two)
(3, three)

Today only the source of candidate row offsets changes. IVFFlat opens selected centroid lists; navigable small world (NSW) search follows edges between nearby vectors. The table, query, matcher, row lookup, and final SortExec stay put.

The cumulative starter already contains the two files you will change:

vector-db-starter/core/src/graph.rs
vector-db-starter/core/src/nsw.rs

Four TODOs form one path through the index: search_layer explores a graph, prune_neighbors bounds its degree, NswIndex::try_new inserts the stored rows, and NswIndex::search_with_ef queries the result. Leave the starter’s greedy_search, HNSW, and IVF-PQ TODOs for later days. The crate-internal tests can exercise graph helpers without making them public.

Checkpoint 1: Search One Supplied Layer

An NSW graph has no centroid that points directly at the query. Search starts at one or more supplied entry points and discovers only vertices connected to them.

The walk needs three pieces of state. C is nearest-first, so its next item is the vertex to expand. W is bounded and worst-first, so its top item is the first result to evict when a closer row arrives. visited ensures that each row is measured and expanded at most once. Seed all three from the valid, unique entry points.

Here is a concrete trace. Suppose rows 0, 1, and 2 store the one-dimensional values 0, 1, and 2, with edges 0—1—2. Rows 3 and 4 form a separate component. For query 0, entry row 2, and width 3, the search first retains row 2 at distance 2. Expanding row 2 discovers row 1 at distance 1; expanding row 1 then discovers row 0 at distance 0. W finally returns rows 0, 1, and 2 in that order.

Revisiting row 2 through row 1 does nothing because it is already in visited. An expansion that adds nothing does not end the whole search; another pending candidate may still open a useful path.

No choice of width can make that entry at row 2 reach rows 3 and 4. A second entry point or an edge into their component is required.

Whenever a closer row arrives, keep only the nearest ef rows in W.

Once W is full, stop only when the nearest pending candidate is strictly worse than W.worst.

A candidate equal to W.worst in public (distance, row) order must still be expanded because it may lead somewhere better. Even this strict rule is approximate: a worse intermediate vertex can hide a path to a closer one.

C = valid unique entry points as a min-heap by distance
W = the same points as a bounded max-heap by distance
visited = the same row offsets

while C is not empty:
    candidate = C.pop_nearest()
    if W is full and candidate is strictly worse than W.worst:
        break

    for neighbor in candidate.neighbors:
        if neighbor is outside allowed_rows or already visited:
            continue
        mark neighbor visited
        measure its distance once
        if W is not full or neighbor is better than W.worst:
            C.push(neighbor)
            W.push(neighbor)
            trim W to the search width

return W from nearest to farthest

Implement search_layer in graph.rs. Clamp ef to at least one and at most allowed_rows, and return no rows when none are allowed. Ignore duplicate or out-of-range entry points. During insertion, allowed_rows = r means that only the earlier rows 0..r exist.

cargo xtask test day_03::checkpoint_1

Before the implementation, this command reaches the traversal TODO. Afterward it covers the trace above, row bounds, disconnected components, duplicate and invalid entries, nearest-first uniqueness, and strict stopping.

Checkpoint 2: Keep a Bounded Neighbor List

Rows enter the graph one at a time. Before row r can connect, search the graph of earlier rows with width ef_construction, then select at most max_connections of the nearest candidates.

Each connection is reciprocal, so adding a new row can push an older endpoint past the degree cap.

Implement prune_neighbors in graph.rs. Deduplicate the supplied row offsets, order them by distance from the owner, break distance ties by row offset, and truncate to max_connections. In the focused fixture, owner row 0 sees candidate rows [2, 1, 1, 3]; rows 1 and 2 are equally distant, so a cap of two keeps [1, 2].

cargo xtask test day_03::checkpoint_2

The fixture is already self-free and isolates deduplication, ordering, tie-breaking, and the cap. The graph builder owns the separate rule that a row never appears in its own adjacency list.

Checkpoint 3: Build a Reciprocal Graph

Implement NswIndex::try_new in nsw.rs. Validate the stored vectors for the selected metric, then reject a graph budget unless max_connections > 0, ef_construction >= max_connections, and ef_search > 0.

The first row becomes the initial entry point without a search. For every later row r, call search_layer with allowed_rows = r, connect r to the nearest selected candidates in both directions, prune r and the older endpoints, then make r the entry point for the next insertion. For example, if row 4 connects to rows 1 and 3, first add 4—1 and 4—3. If pruning row 1 then rejects row 4, remove the reverse 4 -> 1 edge as well.

The finished graph must be deterministic, duplicate-free, self-free, reciprocal, and within the degree cap:

cargo xtask test day_03::checkpoint_3

This checkpoint covers stored-vector and configuration validation without calling search_with_ef, so construction failures remain local.

Checkpoint 4: Query with a Width Budget

Implement NswIndex::search_with_ef. Validate the query dimension, finite values, and selected metric, and reject a zero search width. Start from the graph entry point and call search_layer with width ef_search.max(k). Return at most k neighbors, nearest-first.

The .max(k) floor keeps the result request separate from the exploration hint. A request for five rows with ef_search = 1 still needs room for five retained results. More width can expose more of the connected graph, but it cannot cross a missing edge.

cargo xtask test day_03::checkpoint_4

The connected high-width fixture matches FlatIndex. Treat that as one observed result: NSW is not generally exact for arbitrary data, widths, or disconnected graphs.

Return to the Same SQL Product

With all four TODOs complete, run the supplied comparison:

cargo run -p vector-db-from-scratch-datafusion-starter --example nsw_sql

It executes the same five-vector cosine query twice. The first plan contains:

VectorIndexScanExec: index=ivf_flat, metric=Cosine, query_dim=3, fetch=Some(3), ordered=false

The second contains:

VectorIndexScanExec: index=nsw, metric=Cosine, query_dim=3, fetch=Some(3), ordered=false

Both retain the supplied SortExec and show the same three rows:

(1, one)
(2, two)
(3, three)

Only the candidate route changed. The attachment chooses the index, the matcher recognizes the supported top-k shape, row lookup resolves the returned offsets, and DataFusion performs the final sort. Equal rows in this example do not establish general recall, work, or performance.

The Checkpoint 4 command also runs a separate SQLLogicTest with eight rows and LIMIT 5. It verifies the index=nsw plan leaf, the supplied final sort, and its own five expected rows. Unsupported SQL shapes continue to use the supplied exact DataSourceExec path.

Finish Day 3

Run the focused Day 3 gate and then the cumulative course through Day 3:

cargo xtask test day_03
cargo xtask test-through day_03

The insertion and query traces now meet at the same graph boundary: opposite heap orderings choose what expands and what survives; strict stopping bounds exploration; reciprocal pruning keeps both endpoints consistent; ef_search.max(k) leaves room for the requested result; and connectivity decides which rows can be reached at all.

Day 3 deliberately builds one immutable graph layer. Hierarchy arrives with HNSW on Day 4. Deletion, concurrent mutation, persistence, filtering pushdown, general DDL/catalog behavior, benchmarking, and neighbor diversification are separate problems and do not change this checkpoint.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

Add Hierarchy with HNSW

Day 4

Complete Navigate a Proximity Graph with NSW first. You will turn that one-layer graph into a seeded hierarchy, route through its sparse upper layers, and run the same SQL top-k through index=hnsw.

Start from the NSW Product

Day 3 ended with IVFFlat and NSW proposing candidates for the same five-row cosine query. Run that comparison again from the repository root:

cargo run -p vector-db-from-scratch-datafusion-starter --example nsw_sql

The second plan contains index=nsw, and both indexes return:

(1, one)
(2, two)
(3, three)

Keep that result in view while you build HNSW. The SQL matcher, source-row lookup, and final SortExec will not change. Only the route that proposes candidate row offsets changes: NSW starts in one graph containing every row, while HNSW makes coarse moves through sparse upper layers before searching the all-row graph at layer zero. The finished SQL plan will say index=hnsw; DataFusion will still own the final ordering of the returned rows.

The cumulative starter leaves three Day 4 units unfinished:

vector-db-starter/core/src/graph.rs        greedy_search
vector-db-starter/core/src/hnsw.rs         HnswIndex::try_new
vector-db-starter/core/src/hnsw.rs         HnswIndex::search_with_ef

Day 3 already supplied search_layer, prune_neighbors, deterministic (distance, row) ordering, and the DataFusion boundary. try_new is one build operation: assign each row a level and connect that row before moving to the next one.

Checkpoint 1: Route Through One Upper Layer

Layer zero contains every vector. A row promoted to level L also belongs to every layer below L, so each higher layer is a smaller set of possible waypoints.

A query enters at the global entry point in the highest layer. Within an upper layer, greedy_search looks at the allowed neighbors and moves only when the best one strictly improves the public (distance, row) order. Distance ties therefore prefer the lower row offset. Because every accepted move improves the total order, the walk must stop.

current = distance(query, entry)
loop:
    next = minimum allowed neighbor by (distance, row)
    if next is strictly better than current:
        current = next
    else:
        return current.row

Implement greedy_search in graph.rs. During construction of row r, allowed_rows = r keeps the walk inside rows that already exist. During a query, all stored rows are allowed. This helper returns one handoff row; it is not the bounded multi-candidate search that produces the final top-k.

Run the focused helper test:

cargo xtask test day_04::checkpoint_1

The fixture starts at row 2. Row 1 wins an equal-distance tie by row offset. A closer row 3 is first outside allowed_rows, then becomes reachable when the bound grows. Returning the starting row unconditionally, ignoring the bound, or comparing distance without the row tie-break all fail here.

Checkpoint 2: Build the Seeded Nested Graph

Implement HnswIndex::try_new in hnsw.rs. Begin by validating the stored vectors for the selected metric. The graph budget is invalid when max_connections is zero, ef_construction is smaller than max_connections, ef_search is zero, or max_level is zero.

For each dataset row, the supplied deterministic generator flips a seeded coin until the first failure or max_level. A sampled level of one places the row in layers one and zero, not layer two. Rebuilding with the same implementation and seed must reproduce the same levels and graph. A different valid implementation may consume random values in another order, so the tests check repeatability and invariants rather than a reference level prefix.

Each stored layer has one adjacency slot per dataset row. Extend the existing layers when a row arrives and create any missing layers through its sampled level. A row outside a layer keeps an empty slot there. This makes membership visible from both levels[r] and the layer storage, and it keeps upper-layer membership nested.

The first row needs no search. Put it in all of its included layers and make it the global entry point. Every later row starts from that entry. Greedily cross layers above the new row’s own level; then, in each layer the new row shares with the existing graph, use Day 3’s search_layer to choose nearby earlier rows. Add reciprocal edges, prune both endpoints to max_connections, and remove the reverse edge whenever pruning rejects one direction.

target_level = seeded_geometric_level()
entry = top entry point

for level above target_level, from highest down:
    entry = greedy_search(layer[level], new_vector, entry)

for shared level from min(highest, target_level) down to 0:
    candidates = search_layer(layer[level], new_vector, [entry], ef_construction)
    connect the nearest max_connections candidates in both directions
    prune every affected endpoint and remove rejected reciprocal edges
    entry = nearest candidate, when one exists

if target_level is above the previous highest level:
    make the new row the global entry point

Here is one concrete route. Suppose row 0 stores [0] at level two, row 1 stores [4] at level zero, and row 2 stores [8] at level one, with the eligible rows connected in their shared layers. Now row 3, storing [7], is promoted to level one. It begins at row 0. Layer two has no better waypoint, so row 0 descends into layer one; there, the bounded search reaches row 2 and connects the new row to that nearer candidate before construction continues at layer zero. Because level one is not above the old top level, row 0 remains the global entry point. Later, a query for [7.2] starts at row 0 in layer two, moves from row 0 toward row 2 in layer one, and hands row 2 to the wider layer-zero search. The hierarchy shortened the route to a useful region; layer zero still decides the returned candidate set.

The finished graph stores dataset ordinals, not source row IDs. The supplied DataFusion adapter performs that mapping after search. Within every layer, adjacency must stay degree-bounded, duplicate-free, self-free, and reciprocal. Update the global entry point only when the new row creates a new top layer.

Run the construction test:

cargo xtask test day_04::checkpoint_2

It exercises invalid budgets and metric data, repeated seeded builds, nested membership, the degree cap, and reciprocal edge cleanup. It also rejects injected self-edges; Checkpoint 3 is the first supplied gate that requires a positive promoted level. The test deliberately permits any level sequence produced repeatably by a valid implementation.

Checkpoint 3: Search from the Top Layer

Implement HnswIndex::search_with_ef. Validate the query dimension, finite values, and selected metric before routing, and reject an explicit search width of zero.

Begin at the global entry point. Run greedy_search once in each upper layer, carrying its single returned row down to the next layer. At layer zero, switch back to Day 3’s search_layer with width ef_search.max(k), then keep at most the nearest k results.

entry = top entry point
for level from highest down to 1:
    entry = greedy_search(layer[level], query, entry)

candidates = search_layer(
    layer[0],
    query,
    entry_points=[entry],
    width=max(k, ef_search),
)
return nearest k candidates

The .max(k) floor separates result count from exploration width. Asking for five rows with ef_search = 1 still requires room to retain five candidates.

Run the Checkpoint 3 gate:

cargo xtask test day_04::checkpoint_3

The gate covers query validation, zero width, nearest-first ordering, the width floor, upper-layer descent, and the supplied DataFusion paths. On one connected fixture, a high-width HNSW search matches FlatIndex. That is a bounded observation. This nearest-neighbor pruning rule can leave layer zero disconnected, and increasing the width cannot cross an absent edge, so the course makes no general exactness, connectivity, recall, or performance claim.

Return to the SQL Product

The Checkpoint 3 gate also runs a self-contained SQLLogicTest. It creates and populates its own table, records the exact scan plan, attaches an HNSW index, and checks the new plan and rows. The indexed plan contains:

VectorIndexScanExec: index=hnsw, metric=Euclidean, query_dim=3, fetch=Some(5), ordered=false

Its five-row Euclidean query returns:

1 point-1
0 point-0
2 point-2
3 point-3
4 point-4

HNSW returns core dataset ordinals. The supplied adapter resolves them to snapshot source rows, and the supplied SortExec performs the final SQL ordering. Unsupported query shapes continue through the exact scan path. These five rows demonstrate the product handoff only; they do not turn the small fixture into a general recall or speed result.

Finish Day 4

Run the focused Day 4 gate and then the cumulative course through Day 4:

cargo xtask test day_04
cargo xtask test-through day_04

The runner selects tests only through HNSW, so unfinished Day 5 IVF-PQ work stays outside this gate. At this point the three implementations form one path: a strict greedy walk chooses each upper-layer handoff, seeded insertion builds nested reciprocal layers from prior rows, and bounded layer-zero search returns the candidates that DataFusion maps and sorts.

This course index remains immutable and in memory. Deletion, concurrent mutation, persistence, production neighbor diversification, and adaptive search budgets would require a different learner contract; they are not hidden parts of Day 4.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

Compress IVFFlat with Product Quantization

Day 5

Complete Add Hierarchy with HNSW first. Build a residual IVF-PQ index that scores compact codes, reranks a shortlist with full vectors, and exposes the representation accounting used by the final benchmark.

IVFFlat narrows a query to a few lists, but scoring those lists still reads every component of every candidate vector. On a large dataset, that inner loop can dominate the search. IVF-PQ keeps the coarse lists and replaces each candidate’s scoring representation with a short sequence of learned codeword IDs. It uses those IDs to choose a shortlist, then returns to the original vectors for the final distances.

Follow one row through that path. Its IVF centroid c chooses the list. Subtracting c from the row vector x gives an eight-dimensional residual, which we split into two four-dimensional pieces:

residual = [ 0.7, -0.1, 0.3, 0.2 | -0.4, 0.8, 0.1, -0.2 ]
             subvector 0              subvector 1

Each slice position has its own codebook. With four codewords in each codebook, this residual is represented by two choices:

subvector 0 -> codeword 2
subvector 1 -> codeword 0
PQ code     -> [2, 0]

The course stores each ID as a u8, so this row contributes two code bytes. The codebooks are shared by every row. What they approximate is the residual, not the original vector:

r = x - c

That distinction matters during search. The IVF centroid decides which lists are probed; each PQ codeword approximates one slice of a residual within those lists. Rebuilding with equal data and configuration must reproduce the same coarse centroids, PQ codebooks, list sizes, codes, and search results.

For a query q, each probed list has its own centroid c. Subtract that same c from the query and compare each query slice with the codewords for that position:

• an IVF centroid chooses the inverted list;
• a PQ codeword approximates one slice of the residual inside that list.

This is the residual IVF-PQ design introduced by Jégou, Douze, and Schmid, often called IVFADC. The Faiss index guide describes the same coarse-quantizer-plus-residual-PQ decomposition.

Score the Codes, then Rerank

Build one squared-Euclidean lookup table for every slice position in the probed list:

table[m][j] = squared_l2((query - coarse_centroid)[m], codebook[m][j])

The encoded row [2, 0] now needs two table reads instead of reading its eight stored components:

score(code) = table[0][code[0]] + ... + table[M - 1][code[M - 1]]

The query remains full precision while the stored residual is quantized, which makes this asymmetric distance computation. Apply the same lookup process to every encoded row in the probed lists and retain the best min(max(rerank, k), rows) row offsets. Those offsets stay attached to their source rows when the original vectors are read for exact Euclidean reranking:

probed lists -> PQ score -> rerank shortlist -> exact distance -> top-k

With four subquantizers and sixteen codewords per codebook, one probed list builds 64 lookup entries. Each encoded row then reads four entries and combines them into one approximate score. The base Dataset remains available because the shortlist still needs exact reranking.

This also fixes the meaning of the byte counters. encoded_bytes() plus codebook_bytes() measures only the PQ search representation. It does not include the retained full vectors, coarse centroids, row IDs, list allocations, or other index and process overhead.

Build IVF-PQ in Rust

You will modify:

vector-db-starter/core/src/pq.rs

The starter already exposes IvfPqConfig, IvfPqIndex, its VectorIndex implementation, byte-accounting methods, and the DataFusion IndexConfig::IvfPq path. Your two unfinished units are IvfPqIndex::try_new and IvfPqIndex::search_with_probes; the first two checkpoints develop different parts of the same try_new implementation.

All commands on this page run against the cumulative starter workspace. Complete Days 1–4 first, because an untouched starter reaches an earlier todo!() before it can exercise Day 5.

IvfPqConfig separates the main budgets:

This implementation accepts only Metric::Euclidean. Supporting cosine or inner product would change how vectors, residuals, and codeword scores relate, so those metrics return a configuration error here.

Checkpoint 1: Validate the Layout

Begin IvfPqIndex::try_new with the two invalid cases exercised by the supplied Checkpoint 1 test: reject any metric except Euclidean, and reject a subquantizer count that does not divide the vector dimension.

cargo xtask test day_05::checkpoint_1

Checkpoint 2: Train and Encode Residual Codebooks

Checkpoint 2 is the first supplied test that constructs a valid index. Before that construction can reach training, add the remaining constructor checks:

• 1 <= probes <= partitions <= rows and iterations > 0;
• subquantizers > 0;
• 2 <= codebook_size <= min(256, rows); and
• rerank > 0.

These checks are required prerequisites for Checkpoint 2. Its supplied cases use valid values for them rather than grading their failure branches individually.

Continue try_new by building the coarse partition with the configured partitions, probes, iterations, and seed. Once its final centroids are known, assign every row again and compute row - centroid. That final reassignment gives every row exactly one list and ensures its residual uses the centroid for that list.

Split every residual into equal contiguous slices. For each subquantizer:

1. choose codebook_size distinct seeded residual rows;
2. copy that slice from each chosen row as an initial codeword;
3. assign every residual slice to its nearest codeword under squared Euclidean distance;
4. replace each non-empty codeword with the component-wise mean of its assignments; and
5. stop after convergence or iterations rounds.

When a cluster receives no residual slices, leave that codeword unchanged. Reuse the deterministic RNG from src/search.rs, but derive a different deterministic seed for each subquantizer so their initial row choices are independent. After training, encode every row with exactly one valid u8 code for each slice position.

cargo xtask test day_05::checkpoint_2

This gate checks deterministic training, complete list membership, code layout, and byte accounting. At this point try_new is complete; the index is built, but its search function remains the second starter todo!().

Checkpoint 3: Scan Codes and Rerank

Implement search_with_probes by following the query path from the opening trace:

1. validate the query, probe count, and nonzero rerank budget;
2. rank coarse centroids and visit the nearest lists;
3. build residual lookup tables for each visited list;
4. sum one table entry per code with a shortlist budget of at least k, even when rerank < k;
5. compute exact Euclidean distances for the shortlist row offsets; and
6. return exact top-k results in the public (distance, row) order.

Use f64 for coarse selection, lookup sums, and exact rerank distances. A value crosses the public Neighbor boundary only when it is finite and representable as f32; convert there and apply the public (distance, row) order. Keep the row offset beside every code and every shortlisted distance. If unrepresentable exact distances leave fewer than min(k, rows) valid results, return an error instead of a shortened answer.

Run the complete Checkpoint 3 gate:

cargo xtask test day_05::checkpoint_3

This checkpoint probes every list and reranks every row, so its result must match exact search for that bounded case. The other cases cover large finite values, representation failures, public ordering, and the unchanged Day 1 adapter. The physical plan names index=ivf_pq; the matcher remains conservative and DataFusion still applies the final bounded sort.

Checkpoint 4: Inspect the Search Representation

For any built index:

• encoded_bytes() counts stored PQ codes;
• codebook_bytes() counts shared PQ codeword components;
• full_precision_bytes() counts the retained dataset’s vector components.

These counters let the final day print the retained vector components beside the codes and shared codebooks. Their ratio is useful only for that representation accounting: it is not total-memory compression and it is not a measured speed or quality result.

Return to the SQL Product

Run the self-contained Day 5 SQLLogicTest:

cargo xtask test day_05::checkpoint_4

The fixture creates and fills its own eight-row table. Before it attaches the index, the plan contains:

DataSourceExec: partitions=1, partition_sizes=[1]

After CREATE INDEX ... USING ivfpq, the same bounded top-k query contains:

VectorIndexScanExec: index=ivf_pq, metric=Euclidean, query_dim=3, fetch=Some(5), ordered=false

and returns:

1 point-1
0 point-0
2 point-2
3 point-3
4 point-4

The fixture gives you one deterministic handoff from an exact scan to the supplied IVF-PQ SQL adapter. The matcher still falls back for unsupported query shapes, and the bounded final sort stays in the plan. Broader recall, latency, and memory comparisons belong to the final benchmark workload.

Check the Completed Day

Run the Day 5 focused gate, then the cumulative course through Day 5:

cargo xtask test day_05
cargo xtask test-through day_05

When both commands pass, trace one result all the way back: its coarse centroid chose a list, its residual slices chose PQ codewords, lookup sums placed its row offset in the shortlist, and its retained original vector supplied the exact distance used by the final ordering. The three byte counters describe the representations used along that path; they do not measure the whole index.

Day 5 leaves bit-packed codes, cosine and inner-product support, optimized product quantization, SIMD table scans, persistent layouts, separate training samples, and removing full vectors from memory for later work. The next chapter uses a fixed external workload to make measured comparisons across all five indexes.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

Benchmark Five Indexes on SIFT1M

Day 6

Complete Compress IVFFlat with Product Quantization first. Then bring Flat, IVFFlat, NSW, HNSW, and IVF-PQ together in one release-mode benchmark over the external SIFT1M corpus.

This final day gives the five indexes the same work: Euclidean search with k = 100. With SIFT1M on disk, your first useful run is smoke mode. It validates the complete corpus, keeps 10,000 base rows and 100 queries, recomputes exact top-100 truth for that smaller base, builds every index, and reports latency and quality from the same searches. Progress goes to standard error while the finished report goes to standard output, so you can redirect the report without losing sight of a long-running phase.

The course does not contain a benchmark result to copy. You will finish the executable, check it without a corpus, and then decide whether to run smoke mode or the much larger full experiment on your own machine.

Start from the Completed Indexes

Your Day 5 starter already contains the five index implementations. Keep that boundary green from the repository root:

cargo xtask test-through day_05

Now open:

vector-db-starter/core/examples/recall.rs

Most of the benchmark is supplied. The vector-db-from-scratch-benchmark-support crate parses the command line, validates SIFT files, selects full or smoke sizes, balances warm-up and timed searches, computes quality, and selects latency percentiles. The example fixes the five configurations, output format, result validation, and IVF-PQ byte accounting.

Four todo!() calls are yours. Checkpoint 1 replaces the three constructor TODOs for NSW, HNSW, and IVF-PQ. Checkpoint 2 replaces report_percentiles with calls to the supplied nearest-rank helper. Nothing else in the example needs to be designed for this day.

The support crate has a fast, corpus-free test suite. Run it before editing:

cargo test -p vector-db-from-scratch-benchmark-support

With your Days 1–5 work in place, the Day 6 selector should stop at the four new TODO boundaries:

cargo xtask test day_06

A fresh checkout still has earlier-course TODOs and will fail before it reaches this boundary. Either way, no SIFT1M download is needed for the selector.

Acquire and Validate SIFT1M

Obtain SIFT1M from the TexMex ANN corpus and follow the terms published there. The course neither redistributes the corpus nor supplies an archive checksum or a separate dataset license claim.

Pass a directory that directly contains these three extracted files:

Both modes scan all three files before building an index. The loader checks every little-endian dimension header, the exact record and byte counts, truncation and trailing bytes, finite vector components, and ground-truth IDs that are nonnegative, in range, and unique within a row. A usage error exits with status 2; a data or index error exits with status 1. The only public invocation shape is:

usage: recall [--smoke] <sift1m-dir>

There is no synthetic fallback, arbitrary row limit, environment-variable run mode, or interactive prompt. Only the ignored integration tests use SIFT1M_DIR to locate a developer’s corpus.

What Smoke Mode Changes

Smoke mode is not a miniature parity result. Its exact neighbors are recomputed after the base changes, so its quality and timing describe the selected subset only. Full mode uses all one million base vectors, all 10,000 queries, and the supplied exact top 100. Its parity label records the corpus, Euclidean ordering, k = 100, first-neighbor hit rates, and top-100 overlap; it does not claim identical parameters, storage, floating-point paths, or timings across other implementations.

Keep the Five Configurations Fixed

These are the Rust course configurations, not universal tuning advice. One detail in the NSW and HNSW rows is easy to miss: the stored search width is 40, but search(query, 100) uses max(ef_search, k), so this benchmark actually explores with an effective width of 100. The report records both numbers instead of presenting 40 as the work performed.

Checkpoint 1: Construct the Remaining Indexes

Replace build_nsw, build_hnsw, and build_ivf_pq with their matching constructors. Pass through the supplied dataset, metric, and configuration, and return constructor errors rather than switching to another index or setting.

The example prepares each immutable dataset clone, metric, and configuration before starting the clock. Preserve that line: a build_s sample contains only the constructor. File loading, validation, query preparation, truth selection, dataset cloning, and configuration construction remain outside it.

Run the constructor checkpoint:

cargo xtask test day_06::checkpoint_1

The tests accept more than one deterministic RNG trajectory. A seed must repeat within your implementation; it does not make your IVFFlat centroids or HNSW levels match another implementation’s internal samples.

Checkpoint 2: Select p50 and p99

Replace report_percentiles with two calls to the supplied percentile helper. The input duration slice is already sorted and nonempty. The helper uses nearest rank: for percentage p and n samples, it selects this zero-based position, clamped to the last sample:

ceil(p / 100 * n) - 1

Interpolation or a floor fraction of n - 1 would describe a different statistic. When the p50 and p99 calls are in place, run the complete example boundary:

cargo xtask test day_06::checkpoint_2

This checkpoint covers the constructors and percentile selection together with the fixed inventory, configurations, mode-specific truth, result validation, quality and returned-count summaries, report order, and full-mode IVF-PQ accounting.

Follow Progress without Polluting the Report

The program writes best-effort progress to standard error and holds standard output until the entire report is valid. Redirecting stdout therefore captures only the workload, five index rows, and IVF-PQ accounting. A bad input file, constructor error, wrong result count, duplicate or out-of-range row, nonfinite distance, unordered result, or result longer than k aborts before any stdout report line is printed. Progress already written to stderr may remain visible.

For a noninteractive stderr stream, each counted phase prints 0%, 25%, 50%, 75%, and 100% as separate lines. A terminal redraws those milestones in place. Loading counts every physical row even in smoke mode because the complete files are still validated; recomputing smoke truth counts the selected 100 queries. Builds can expose no useful fractional work, so each prints only start and complete.

Warm-up completes 20 query rounds, or 100 searches across five indexes. The timed phase completes 100 rounds and 500 searches in smoke mode, or 10,000 rounds and 50,000 searches in full mode. Each milestone advances only after all five indexes finish a round and their elapsed times have been captured. Progress writing is outside the samples, and a closed or unwritable stderr stream does not abort the benchmark.

Read the Measurement Loop

Warm-up uses the first min(20, query_count) queries, and the timed pass uses every selected query. Both rotate the starting index so that no one implementation always runs first:

(query_ordinal + offset) % 5

Only search(query, 100) is inside a latency sample. Result validation, quality calculation, latency sorting, percentile selection, formatting, and printing happen afterward. Search errors are returned rather than skipped. search_s is the sum of all per-query samples, and qps is query_count / search_s.

Interpret Quality and Under-fill

For each query, first_hit follows one exact row: the first neighbor in the exact top 100. The three fields record how far into the returned prefix the benchmark must look before finding it:

first_hit@1      exact first neighbor appears at rank 1
first_hit@10     exact first neighbor appears somewhere in ranks 1..10
first_hit@100    exact first neighbor appears somewhere in ranks 1..100

Each field is binary for one query and averaged across all selected queries. Because each wider prefix contains the narrower one, the final rates must satisfy:

0 <= first_hit@1 <= first_hit@10 <= first_hit@100 <= 1
0 <= overlap@100 <= 1

overlap@100 answers a different question: how many returned row IDs belong to the exact top 100? It always divides by 100. If an index returns 50 valid rows and all 50 are exact neighbors, its overlap is 0.5, not 1.0; the absent rows count as misses. returned_min, returned_avg, and returned_max make that valid under-fill visible instead of hiding it behind a quality average.

The report accepts between zero and min(k, base_rows) distinct, in-range rows in public nearest-first Neighbor order, all with finite distances. Flat has the stronger contract: exactly 100 rows and 1.0 for every quality field. The ignored external smoke tests are also deliberately stricter than the general report path: they require 100 distinct rows from each configured index, plus exact Flat quality and broad 0.05 first-hit@100 and overlap@100 floors for the approximate indexes. Those floors catch broken integrations; they are not production targets.

Run Smoke, Then Full SIFT1M

After both checkpoints pass, supply the extracted corpus directory. Run the first command for the 10,000-row smoke experiment. The second command is the optional full SIFT1M run:

cargo run --release -p vector-db-from-scratch-core-starter --example recall -- --smoke /absolute/path/to/sift1M
cargo run --release -p vector-db-from-scratch-core-starter --example recall -- /absolute/path/to/sift1M

You can compare behavior with the completed executable without reading its source:

cargo run --release -p vector-db-from-scratch-core --example recall -- --smoke /absolute/path/to/sift1M
cargo run --release -p vector-db-from-scratch-core --example recall -- /absolute/path/to/sift1M

The full run needs the extracted 525,200,000-byte corpus payload plus build products. Budget tens of minutes and several GiB of working memory; at least 8 GiB of free memory and roughly 1 GiB of free disk beyond the corpus and build outputs is a practical starting point, not a benchmark result or pass/fail threshold.

If you want to exercise one index with external data, the ignored tests expose it separately. For IVF-PQ:

SIFT1M_DIR=/absolute/path/to/sift1M \
  cargo test -p vector-db-from-scratch-core-starter --test sift_smoke \
  day_06::checkpoint_2::sift_ivf_pq_smoke -- --ignored --exact

The analogous names end in sift_flat_smoke, sift_ivf_flat_smoke, sift_nsw_smoke, and sift_hnsw_smoke under the same day_06::checkpoint_2 namespace.

Read the Finished Report

Every successful run begins with one workload line:

workload: mode={sift1m-full|sift1m-smoke}, parity={bustub-sift1m|non-parity}, rows={1000000|10000}, dimensions=128, queries={10000|100}, metric=euclidean, k=100, truth={supplied-sift1m-top-100|recomputed-flat-selected-base-top-100}

Five rows follow in flat, ivf_flat, nsw, hnsw, ivf_pq order:

{name}: config={stable-config}, build_s={:.3}, search_s={:.3}, qps={:.1}, first_hit@1={:.4}, first_hit@10={:.4}, first_hit@100={:.4}, overlap@100={:.4}, returned_min={n}, returned_avg={:.1}, returned_max={n}, p50_ms={:.3}, p99_ms={:.3}

The final line is narrower than a memory measurement:

ivf_pq search representation: codes_bytes={u64}, codebooks_bytes={u64}, search_bytes={u64}, full_vectors_bytes={u64}, compression={:.1}x

For the full data, four million code bytes plus 8,192 codebook bytes produce a 4,008,192-byte search representation. Compared with 512,000,000 full-vector component bytes, the line prints 127.7x. That ratio describes only codes plus codebooks versus vector components. It excludes the original vectors retained for reranking, coarse centroids, row IDs, list and graph containers, allocator overhead, and the other four live indexes. It is not resident memory or total-index compression.

Record timings and quality only from a run you actually performed, together with its mode, machine, and fixed configuration. One run cannot establish a universal fastest index, quality ranking, latency threshold, general exactness, or graph connectivity.

Finish the Course Boundary

The focused and cumulative gates compile the benchmark but skip the ignored SIFT1M tests:

cargo xtask test day_06
cargo xtask test-through day_06

Once they pass, you have a complete corpus-free implementation boundary. Smoke mode is the practical first external check when you have acquired SIFT1M. The full-data command above remains optional: run it only with the corpus and resources available, and treat any numbers it produces as observations from that machine and configuration—not as measurements supplied or promised by the course.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

Where to Go Next

Across six days, the Rust course builds an immutable in-memory collection, exact fallback, IVFFlat, NSW, HNSW, residual IVF-PQ, SQL query support, and a shared five-index SIFT1M rank-recall and latency benchmark. A teaching system still leaves plenty of room to explore the storage, query-processing, and serving concerns of a production vector database.

One SQL Query, Many Layers

Vector search does not have to live behind a separate service. A SQL engine can support it through a small set of extension points: vector values and distance expressions at the interface, exact or approximate indexes underneath, and a planner rule that connects an ORDER BY distance query with LIMIT k to the right execution plan. The code at each boundary can be small; making the boundaries agree is the database work.

Andy Pavlo made a similar observation in Databases in 2023: A Year in Review: vector search spread quickly because it can often be added as a new access method and index rather than a new database architecture. This course lets you see that integration layer by layer, behind one SQL top-k query.

Once that system works, several extensions make good independent projects.

Storage and Index Layout

• Map immutable vector and index files directly instead of decoding them into many heap allocations.
• Compare array-of-structures and structure-of-arrays layouts for distance evaluation and graph traversal.
• Extend IVF-PQ with scalar quantization, bit-packed codes, or optimized product quantization.
• Rebuild large indexes with bounded memory and resumable checkpoints.

Query Processing

• Extend the DataFusion adapter with safe filtered top-k pushdown, general DDL/catalog semantics, and index selection.
• Add hybrid lexical and vector retrieval with an explicit score-combination contract.
• Explore pre-filtering, in-traversal filtering, post-filtering, and adaptive oversampling for selective predicates.
• Add a reranking stage that fetches full-precision vectors only for the final candidates.

Serving

• Add a thin HTTP or gRPC adapter over the same collection API.
• Define request validation, cancellation, admission control, and graceful shutdown.
• Compare library, SQL, and network measurements without hiding serialization or queueing cost.

Transactions and Distribution

• Define snapshot semantics across base segments, mutation logs, and index generations.
• Replicate the mutation log and decide when an acknowledged write becomes searchable.
• Shard collections, merge per-shard top-k results, and measure how routing affects recall.
• Move immutable generations to object storage and separate compute from storage.

Hardware-Aware Search

• Vectorize exact distance calculations with portable SIMD.
• Batch queries to improve cache reuse and throughput without hiding tail latency.
• Compare CPU and GPU search only after including transfer, queueing, and batching costs.
• Compare SIFT1M observations with embedding distributions, dimensions, and hardware from the workload you actually intend to serve.

For any extension, use exact search as the baseline, state the workload, and report correctness together with performance. A vector index is useful only when its speedup is attached to a result-quality and lifecycle contract.

Why This Course Exists

My first close look at vector databases came during my 2023 internship at Neon. Nikita added me to a Slack channel called #vector, where Konstantin was building pg_embedding, a PostgreSQL extension with HNSW support. The project was later discontinued after pgvector added HNSW, but it left me with the question that became this course: what actually has to change inside a database to make one SQL vector query work?

That question led me to build the original version of this course on BusTub. Thanks to Yuchen, Avery, Ruijie, and the 15-445 course staff for reviewing and merging the upstream vector-type change that made it possible. The Rust and DataFusion course continues the same investigation with a small in-memory system whose layers can be read end to end.

Feedback

The six Rust days include starter code, executable references, focused tests, SQL plan checks for Days 1–5, required residual IVF-PQ, and a final SIFT1M benchmark across all five indexes. Feedback about the scope, ordering, external-data workflow, or architecture is welcome.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

C++ Course over BusTub (Deprecated)

In this edition, you will add vector search to a modified version of BusTub, CMU’s educational database system. The index chapters build from IVFFlat through one-layer NSW to hierarchical HNSW. The SIFT1M chapter is an optional benchmark capstone for comparing IVFFlat and HNSW.

Course Order

Follow the chapters in order:

1. implement vector distances, insertion, and sequential scan;
2. implement exact k-nearest-neighbor queries with sort, limit, and Top-N;
3. match a safe SQL top-k query to a compatible vector index;
4. implement IVFFlat;
5. implement a one-layer NSW graph;
6. extend NSW into a hierarchical HNSW index; and
7. benchmark IVFFlat and HNSW on SIFT1M.

The diagram shows the same algorithm dependencies through HNSW. It is useful as a map, but it does not make the chapters independent.

Environment Setup

Use the course’s frozen BusTub snapshot. These chapters and the SIFT1M benchmark were checked against commit b9799536dfb054cd616d781d8801616c7812fb2b.

git clone https://github.com/skyzh/bustub-vectordb
cd bustub-vectordb
git checkout b9799536dfb054cd616d781d8801616c7812fb2b

The intended environments are Ubuntu 22.04 and macOS. Follow the starter repository’s Build section to install its platform packages. The project uses CMake, C++17, and LLVM/Clang 14. Use LLVM/Clang 14 even if your Mac already has a newer Apple Clang. Newer compilers warn about deprecated code in the starter’s 2024 dependencies, and the starter treats those warnings as build errors.

From the bustub-vectordb directory, create a build directory:

mkdir build
cd build

On Ubuntu, configure with Clang 14:

cmake -DCMAKE_POLICY_VERSION_MINIMUM=3.5 \
  -DCMAKE_C_COMPILER=clang-14 \
  -DCMAKE_CXX_COMPILER=clang++-14 \
  ..

On macOS with Homebrew’s llvm@14, configure with:

cmake -DCMAKE_POLICY_VERSION_MINIMUM=3.5 \
  -DCMAKE_C_COMPILER="$(brew --prefix llvm@14)/bin/clang" \
  -DCMAKE_CXX_COMPILER="$(brew --prefix llvm@14)/bin/clang++" \
  ..

Then build the two course binaries:

make -j8 shell sqllogictest

The policy option lets the starter’s older vendored CMake projects configure under CMake 4. Unless a chapter creates a separate build directory, later build and test commands assume that your working directory is bustub-vectordb/build.

Run the SQL shell:

$ ./bin/bustub-shell
bustub> SELECT ARRAY [1.0, 2.0, 3.0];
+-------------+
| __unnamed#0 |
+-------------+
| [1,2,3]     |
+-------------+

In this starter, an ARRAY expression becomes a vector only when every element is a decimal literal such as 1.0. Integer literals such as 1 are outside the required path.

What the Starter Adds

The starter narrows BusTub to the parts used by this course:

• In-memory table storage. A modified table heap and buffer pool keep the course data in memory.
• Vector expressions. The parser, type system, and expression tree already recognize three vector-distance operations.
• Vector-index interfaces. VectorIndex, IVFFlatIndex, and HNSWIndex connect index construction, insertion, and lookup.
• Vector-index execution. A plan node and executor can turn ordered vector-index RIDs back into table tuples.
• SIFT1M benchmark harness. An optional executable loads the standard 128-dimensional corpus, runs HNSW queries, and reports 1-nearest-neighbor recall at ranks 1, 10, and 100.

Some executor work overlaps with CMU’s Database Systems assignments. KEEP PRIVATE applies only to files marked with that label: do not commit or publish your implementations of those paths. The IVFFlat, NSW, HNSW, and benchmark files are not part of that restriction and may be published. Because the starter already tracks placeholder versions of some private files, .gitignore alone will not hide changes to them; check the staged diff before publishing.

How to Check Each Chapter

The vector.*.slt files use statement ok, so they mainly prove that a statement ran without an error. Their verbose output is an inspection aid, not a complete correctness oracle. Where a stricter BusTub SQLLogicTest exists, the chapter names it. For every checkpoint, also explain:

• how a tuple or query moves through the code you changed;
• the invariant that keeps its result correct;
• one input that could break a careless implementation; and
• which test would expose that failure.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

Vector Expressions and Storage

This checkpoint makes the smallest end-to-end vector query work. You will implement the three distance functions, insert rows into the table and any vector indexes on it, and scan the rows back out.

Files you will likely modify:

src/execution/insert_executor.cpp                    (KEEP PRIVATE)
src/execution/seq_scan_executor.cpp                  (KEEP PRIVATE)
src/include/execution/executors/insert_executor.h    (KEEP PRIVATE)
src/include/execution/executors/seq_scan_executor.h  (KEEP PRIVATE)
src/include/execution/expressions/vector_expression.h

Checkpoint 1: Compute Distances

Implement ComputeDistance in src/include/execution/expressions/vector_expression.h:

L2 distance (Euclidean distance)

\( \lVert \mathbf{a} - \mathbf{b} \rVert = \sqrt {(a_1 - b_1)^2 + (a_2 - b_2)^2 + \cdots + (a_n - b_n)^2} \)

Cosine distance

\( 1 - \frac { \mathbf{a} \cdot \mathbf{b} } {\lVert \mathbf{a} \rVert \lVert \mathbf{b} \rVert} \)

Negative inner-product distance

\( - \mathbf{a} \cdot \mathbf{b} = - (a_1 b_1 + a_2 b_2 + \cdots + a_n b_n) \)

Apply these equations to the query a = [1, 0]. Comparing a with itself gives L2, cosine, and negative inner-product distances of 0, 0, and -1. Comparing it with the orthogonal vector b = [0, 1] gives sqrt(2), 1, and 0. The exact match therefore has the smaller value for all three operations, including the negative inner product.

Course rule: Inputs have equal dimensions. The starter asserts this invariant. Cosine-distance inputs in the required tests also have nonzero norms; if you extend the system to accept zero vectors, reject them or define their behavior explicitly instead of relying on division by zero.

Checkpoint 2: Insert and Scan Rows

How BusTub Stores a Row

A TableHeap is page-organized row storage. The original BusTub abstraction is disk-oriented, but this course’s modified buffer pool keeps its pages in memory.

A Tuple is the serialized form of one row. On the intended little-endian machines, three INTEGER values 1, 2, 3 use four bytes each:

01 00 00 00  02 00 00 00  03 00 00 00

The bytes alone do not identify their types. A Schema supplies the number, order, and type of the columns so BusTub can decode them. The three relevant representations are:

• Tuple: serialized row bytes;
• Schema: the position and type of each column; and
• Value: an in-memory typed value, such as an integer or std::vector<double>.

Related lecture: Database Storage Part 2 (CMU Intro to Database Systems)

Execution Model

BusTub uses the Volcano execution model. Each executor has Init and Next methods. The execution engine calls Init once, then calls Next until it returns false. An executor initializes its child before pulling tuples from it.

Related lectures:

• Query Execution Part 1 (CMU Intro to Database Systems)
• Query Execution Part 2 (CMU Intro to Database Systems)

Insert Executor

Run this statement in bustub-shell to inspect the insert plan directly:

EXPLAIN (o) INSERT INTO t1 VALUES (ARRAY [1.0, 2.0, 3.0]);

An INSERT plan pulls rows from a child Values executor:

Insert { table_oid=24 }
  Values { rows=1 }

Initialize plan_, child_executor_, table_heap_, and the table’s vector-index list from the executor context. The catalog returns every index on the table, so keep only indexes whose implementation can be dynamically cast to VectorIndex *.

Course rules:

• Init initializes the child, consumes all of its tuples, and inserts each tuple into the table heap.
• Update a vector index only after the table insert succeeds and returns an RID.
• A vector index has exactly one key attribute in this course. Use that column position to read a Value, call Value::GetVector, and pass the vector and the inserted RID to InsertVectorEntry.
• Next emits one tuple containing the number of inserted rows, then returns false on later calls.

Sequential Scan Executor

Initialize plan_ and table_heap_ from the table OID. In Init, create a TableIterator with MakeIterator. In each successful Next call:

1. read the current (TupleMeta, Tuple) pair with TableIterator::GetTuple;
2. copy both the tuple and TableIterator::GetRID() to the output parameters; and
3. advance the iterator exactly once.

Return false immediately when TableIterator::IsEnd() is true. The required course path is append-only, so it does not ask this simplified scan to skip deleted tuples.

Verify the Checkpoint

From bustub-vectordb/build, build and run the vector checkpoint:

make -j8 sqllogictest
./bin/bustub-sqllogictest ../test/sql/vector.01-insert-scan.slt --verbose

Compare the distance and scan rows with the reference below:

<main>:1
SELECT ARRAY [1.0, 1.0, 1.0] <-> ARRAY [-1.0, -1.0, -1.0] as distance;
----
3.464102	

<main>:4
SELECT ARRAY [1.0, 1.0, 1.0] <=> ARRAY [-1.0, -1.0, -1.0] as distance;
----
2.000000	

<main>:7
SELECT inner_product(ARRAY [1.0, 1.0, 1.0], ARRAY [-1.0, -1.0, -1.0]) as distance;
----
3.000000	

<main>:10
CREATE TABLE t1(v1 VECTOR(3), v2 integer);
----
Table created with id = 24	

<main>:13
INSERT INTO t1 VALUES (ARRAY [1.0, 1.0, 1.0], 1), (ARRAY [2.0, 1.0, 1.0], 2), (ARRAY [3.0, 1.0, 1.0], 3), (ARRAY [4.0, 1.0, 1.0], 4);
----
0	

<main>:16
SELECT * FROM t1;
----
[1,1,1]	1	
[2,1,1]	2	
[3,1,1]	3	
[4,1,1]	4	

<main>:19
SELECT v1, ARRAY [1.0, 1.0, 1.0] <-> v1 as distance FROM t1;
----
[1,1,1]	0.000000	
[2,1,1]	1.000000	
[3,1,1]	2.000000	
[4,1,1]	3.000000	

<main>:22
SELECT v1, ARRAY [1.0, 1.0, 1.0] <=> v1 as distance FROM t1;
----
[1,1,1]	0.000000	
[2,1,1]	0.057191	
[3,1,1]	0.129612	
[4,1,1]	0.183503	

<main>:25
SELECT v1, inner_product(ARRAY [1.0, 1.0, 1.0], v1) as distance FROM t1;
----
[1,1,1]	-3.000000	
[2,1,1]	-4.000000	
[3,1,1]	-5.000000	
[4,1,1]	-6.000000	

Predict before testing: what should Next do for an empty table, and what would break if an index received a different RID from the one returned by InsertTuple?

You are done when you can trace an input vector from ValuesExecutor, through tuple storage and InsertVectorEntry, and back through SeqScanExecutor, and explain how the schema and RID preserve its meaning and identity.

Bonus Tasks

Implement the Buffer Pool Manager

The starter provides a mock buffer pool manager and a modified table heap, so the required course path keeps all data in memory. As a bonus, you can replace them with the persistent buffer pool manager from project 1 of CMU 15-445/645. Revert both the starter’s buffer-pool change and its table-heap change before beginning; reverting only one side can cause memory leaks and deadlocks.

Implement Delete and Update

Implement the delete and update executors so they update both the table heap and every vector index. BusTub marks deleted tuples instead of immediately removing their storage, so use UpdateTupleMeta for deletion and model an update as a deletion followed by an insertion. You will also need to extend VectorIndex with a way to remove entries.

Validate Inserts

Add dimension validation before inserting into a VECTOR(n) column. For example, reject a vector of dimension 3 or 5 when the column is declared as VECTOR(4).

These tasks overlap further with CMU’s Database Systems projects. KEEP PRIVATE applies to affected assignment files in this section: add those paths to your solution repository’s .gitignore, do not commit or publish them, and remember that .gitignore does not hide changes to placeholder files already tracked by the starter.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

Exact K-Nearest Neighbors

This chapter turns an ordinary table scan into exact k-nearest-neighbor search. First you will implement general-purpose sort and limit executors. Then you will replace that pair with a bounded Top-N executor.

Complete Vector Expressions and Storage first. You will likely modify these private BusTub assignment files:

src/execution/sort_executor.cpp                      (KEEP PRIVATE)
src/execution/topn_executor.cpp                      (KEEP PRIVATE)
src/execution/limit_executor.cpp                     (KEEP PRIVATE)
src/include/execution/executors/sort_executor.h      (KEEP PRIVATE)
src/include/execution/executors/topn_executor.h      (KEEP PRIVATE)
src/include/execution/executors/limit_executor.h     (KEEP PRIVATE)
src/optimizer/sort_limit_as_topn.cpp                 (KEEP PRIVATE)

The Query

CREATE TABLE t1(v1 VECTOR(3), v2 integer);
SELECT v1 FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 3;

This is an exact k-nearest-neighbor query with k = 3. [1.0, 1.0, 1.0] is the query vector, <-> computes its L2 distance to each stored v1, ORDER BY ranks rows from smallest distance to largest, and LIMIT 3 keeps the three nearest vectors. Because this chapter has not introduced an approximate index, the query computes every row’s distance.

Before the Top-N rewrite, run the following statement in bustub-shell:

EXPLAIN (o) SELECT v1 FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 3;

Its plan has this shape:

Limit { limit=3 }
  Sort { order_bys=[("Default", "l2_dist([1.000000,1.000000,1.000000], #0.0)")] }
    Projection { exprs=["#0.0"] }
      SeqScan { table=t1 }

#0.0 means column 0 from child 0. Evaluate each order-by expression against the child tuple and the child’s output schema.

Checkpoint 1: Sort and Limit

The sort executor is a pipeline breaker: Init consumes and stores every (Tuple, RID) from its child, then sorts the stored entries. Next emits them one at a time. Keep the RID paired with its tuple throughout the sort.

Course rules:

• The required vector query has one non-null distance key in ascending or default order. Broader SQL sorting semantics are outside this course’s scope.
• Preserve any order among complete ties; the vector reference allows tied rows to appear in either order.

The limit executor initializes its child and forwards at most limit entries. It must handle limit = 0 and a child with fewer rows without pulling or emitting an extra tuple.

From bustub-vectordb/build, run:

make -j8 sqllogictest
./bin/bustub-sqllogictest ../test/sql/vector.02-naive-knn.slt --verbose

The vector file exercises all three distance functions. Compare its exact-query rows with the first reference output.

<main>:1
CREATE TABLE t1(v1 VECTOR(3), v2 integer);
----
Table created with id = 24	

<main>:4
INSERT INTO t1 VALUES (ARRAY [-1.0, 1.0, 1.0], -1), (ARRAY [-2.0, 1.0, 1.0], -2), (ARRAY [-3.0, 1.0, 1.0], -3), (ARRAY [-4.0, 1.0, 1.0], -4), (ARRAY [1.0, 1.0, 1.0], 1), (ARRAY [2.0, 1.0, 1.0], 2), (ARRAY [3.0, 1.0, 1.0], 3), (ARRAY [4.0, 1.0, 1.0], 4);
----
0	

<main>:7
EXPLAIN (o) SELECT v1 FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 3;
----
=== OPTIMIZER ===
Limit { limit=3 }
  Sort { order_bys=[("Default", "l2_dist([1.000000,1.000000,1.000000], #0.0)")] }
    Projection { exprs=["#0.0"] }
      SeqScan { table=t1 }
	

<main>:10
EXPLAIN (o) SELECT * FROM (SELECT v1, ARRAY [0.5, 1.0, 1.0] <-> v1 as distance FROM t1) ORDER BY distance LIMIT 3;
----
=== OPTIMIZER ===
Limit { limit=3 }
  Sort { order_bys=[("Default", "#0.1")] }
    Projection { exprs=["#0.0", "l2_dist([0.500000,1.000000,1.000000], #0.0)"] }
      SeqScan { table=t1 }
	

<main>:13
EXPLAIN (o) SELECT * FROM (SELECT v1, ARRAY [0.5, 1.0, 1.0] <=> v1 as distance FROM t1) ORDER BY distance LIMIT 3;
----
=== OPTIMIZER ===
Limit { limit=3 }
  Sort { order_bys=[("Default", "#0.1")] }
    Projection { exprs=["#0.0", "cosine_similarity([0.500000,1.000000,1.000000], #0.0)"] }
      SeqScan { table=t1 }
	

<main>:16
EXPLAIN (o) SELECT * FROM (SELECT v1, inner_product(ARRAY [0.5, 1.0, 1.0], v1) as distance FROM t1) ORDER BY distance LIMIT 3;
----
=== OPTIMIZER ===
Limit { limit=3 }
  Sort { order_bys=[("Default", "#0.1")] }
    Projection { exprs=["#0.0", "inner_product([0.500000,1.000000,1.000000], #0.0)"] }
      SeqScan { table=t1 }
	

<main>:19
SELECT v1 FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 3;
----
[1,1,1]	
[2,1,1]	
[-1,1,1]	

<main>:22
SELECT * FROM (SELECT v1, ARRAY [0.5, 1.0, 1.0] <-> v1 as distance FROM t1) ORDER BY distance LIMIT 3;
----
[1,1,1]	0.500000	
[-1,1,1]	1.500000	
[2,1,1]	1.500000	

<main>:25
SELECT * FROM (SELECT v1, ARRAY [0.5, 1.0, 1.0] <=> v1 as distance FROM t1) ORDER BY distance LIMIT 3;
----
[1,1,1]	0.037750	
[2,1,1]	0.183503	
[3,1,1]	0.296474	

<main>:28
SELECT * FROM (SELECT v1, inner_product(ARRAY [0.5, 1.0, 1.0], v1) as distance FROM t1) ORDER BY distance LIMIT 3;
----
[4,1,1]	-4.000000	
[3,1,1]	-3.500000	
[2,1,1]	-3.000000	

Checkpoint 2: Bounded Top-N

Sorting all n rows costs O(n log n) and stores all n entries. For LIMIT k, a max-heap can retain only the best k entries in O(n log k) time and O(k) space.

First implement OptimizeSortLimitAsTopN. It should replace only a Limit whose direct child is a Sort, copy the sort’s order-by list and the limit into a TopNPlanNode, and preserve the sort’s child.

Then implement TopNExecutor:

1. initialize the child;
2. evaluate the same full ordering used by SortExecutor;
3. keep at most k best (Tuple, RID) entries in a max-heap, with the worst retained entry at the top; and
4. emit the retained entries in final best-to-worst order.

Popping a max-heap directly produces the worst retained row first. Reverse that sequence, or use another equivalent method, before Next begins emitting. Keep the retained container bounded to k entries.

Prediction: If the input distances are 4, 1, 3, 2 and k = 2, which values remain after each input? The final output must be 1, 2, even though the heap’s top is 2.

Run:

./bin/bustub-sqllogictest ../test/sql/vector.02-naive-knn.slt --verbose

The EXPLAIN output should now contain TopN instead of Limit over Sort, and its query rows should match the exact checkpoint apart from allowed tie ordering.

<main>:1
CREATE TABLE t1(v1 VECTOR(3), v2 integer);
----
Table created with id = 24	

<main>:4
INSERT INTO t1 VALUES (ARRAY [-1.0, 1.0, 1.0], -1), (ARRAY [-2.0, 1.0, 1.0], -2), (ARRAY [-3.0, 1.0, 1.0], -3), (ARRAY [-4.0, 1.0, 1.0], -4), (ARRAY [1.0, 1.0, 1.0], 1), (ARRAY [2.0, 1.0, 1.0], 2), (ARRAY [3.0, 1.0, 1.0], 3), (ARRAY [4.0, 1.0, 1.0], 4);
----
0	

<main>:7
EXPLAIN (o) SELECT v1 FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 3;
----
=== OPTIMIZER ===
TopN { n=3, order_bys=[("Default", "l2_dist([1.000000,1.000000,1.000000], #0.0)")]}
  Projection { exprs=["#0.0"] }
    SeqScan { table=t1 }
	

<main>:10
EXPLAIN (o) SELECT * FROM (SELECT v1, ARRAY [0.5, 1.0, 1.0] <-> v1 as distance FROM t1) ORDER BY distance LIMIT 3;
----
=== OPTIMIZER ===
TopN { n=3, order_bys=[("Default", "#0.1")]}
  Projection { exprs=["#0.0", "l2_dist([0.500000,1.000000,1.000000], #0.0)"] }
    SeqScan { table=t1 }
	

<main>:13
EXPLAIN (o) SELECT * FROM (SELECT v1, ARRAY [0.5, 1.0, 1.0] <=> v1 as distance FROM t1) ORDER BY distance LIMIT 3;
----
=== OPTIMIZER ===
TopN { n=3, order_bys=[("Default", "#0.1")]}
  Projection { exprs=["#0.0", "cosine_similarity([0.500000,1.000000,1.000000], #0.0)"] }
    SeqScan { table=t1 }
	

<main>:16
EXPLAIN (o) SELECT * FROM (SELECT v1, inner_product(ARRAY [0.5, 1.0, 1.0], v1) as distance FROM t1) ORDER BY distance LIMIT 3;
----
=== OPTIMIZER ===
TopN { n=3, order_bys=[("Default", "#0.1")]}
  Projection { exprs=["#0.0", "inner_product([0.500000,1.000000,1.000000], #0.0)"] }
    SeqScan { table=t1 }
	

<main>:19
SELECT v1 FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 3;
----
[1,1,1]	
[2,1,1]	
[3,1,1]	

<main>:22
SELECT * FROM (SELECT v1, ARRAY [0.5, 1.0, 1.0] <-> v1 as distance FROM t1) ORDER BY distance LIMIT 3;
----
[1,1,1]	0.500000	
[2,1,1]	1.500000	
[-1,1,1]	1.500000	

<main>:25
SELECT * FROM (SELECT v1, ARRAY [0.5, 1.0, 1.0] <=> v1 as distance FROM t1) ORDER BY distance LIMIT 3;
----
[1,1,1]	0.037750	
[2,1,1]	0.183503	
[3,1,1]	0.296474	

<main>:28
SELECT * FROM (SELECT v1, inner_product(ARRAY [0.5, 1.0, 1.0], v1) as distance FROM t1) ORDER BY distance LIMIT 3;
----
[4,1,1]	-4.000000	
[3,1,1]	-3.500000	
[2,1,1]	-3.000000	

You are done when you can explain why changing the Top-N heap from a max-heap to a min-heap would retain the wrong end of the ordering, and how the optimizer rewrite preserves the original plan’s result.

Related lecture: Query Planning & Optimization (CMU Intro to Database Systems)

Optional Extension

Extend vector construction to accept mixed integer and decimal array literals, or a cast such as '[1.0, 1.0, 1.0]'::VECTOR(3).

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

Matching a Vector Index

This chapter replaces a safe exact top-k plan with VectorIndexScanPlanNode. The index implementations are still stubs, so this checkpoint verifies plan matching and fallback behavior, not approximate-search results.

Complete Exact K-Nearest Neighbors first. You will likely modify:

src/optimizer/vector_index_scan.cpp
src/optimizer/optimizer_custom_rules.cpp

Related lecture: Query Planning & Optimization (CMU Intro to Database Systems)

Goal

Create a vector table and an HNSW index:

CREATE TABLE t1(v1 VECTOR(3), v2 integer);
CREATE INDEX t1v1hnsw ON t1 USING hnsw (v1 vector_l2_ops) WITH (m = 5, ef_construction = 64, ef_search = 10);

Your goal is to make compatible L2 top-k queries use this index while leaving unsafe or incompatible queries on the exact path.

Start from the Unoptimized Shape

The starter runs OptimizeAsVectorIndexScan before OptimizeSortLimitAsTopN. Keep that order for the default path and match a Limit over Sort. After creating t1 and a compatible vector index, run these statements directly in bustub-shell to exercise the supported projections:

EXPLAIN (o) SELECT v1 FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 2;
EXPLAIN (o) SELECT * FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 2;
EXPLAIN (o) SELECT v1, ARRAY [1.0, 1.0, 1.0] <-> v1 FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 2;
EXPLAIN (o) SELECT v2, v1 FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 2;

Before the vector-index rewrite, the rule sees these plan shapes.

Case 1: Sort directly over SeqScan

Limit { limit=2 }
  Sort { order_bys=[("Default", "l2_dist([1.000000,1.000000,1.000000], #0.0)")] }
    SeqScan { table=t1 }

Here #0.0 directly names the vector column in the table schema.

Case 2: Sort over a projected vector column

Limit { limit=2 }
  Sort { order_bys=[("Default", "l2_dist([1.000000,1.000000,1.000000], #0.0)")] }
    Projection { exprs=["#0.0"] }
      SeqScan { table=t1 }

The sort expression names projection column #0.0, which maps to table column #0.0.

Case 3: Sort over a projection that also computes distance

Limit { limit=2 }
  Sort { order_bys=[("Default", "l2_dist([1.000000,1.000000,1.000000], #0.0)")] }
    Projection { exprs=["#0.0", "l2_dist([1.000000,1.000000,1.000000], #0.0)"] }
      SeqScan { table=t1 }

The projected distance does not change the lookup: the sort expression still reaches table column #0.0 through the projection.

Case 4: Sort over reordered projected columns

Limit { limit=2 }
  Sort { order_bys=[("Default", "l2_dist([1.000000,1.000000,1.000000], #0.1)")] }
    Projection { exprs=["#0.1", "#0.0"] }
      SeqScan { table=t1 }

Here the sort expression names projection column #0.1, which maps back to table column #0.0. Do not assume that the vector column is always the first projected column.

If no vector index matches, the later optimizer rule will still convert this pair to exact TopN. Moving the vector rule after the Top-N rule and matching TopN instead is a valid extension, but do not try to support both shapes until the default path works.

VectorIndexScanExecutor emits the table’s original schema. If the matched plan contained a projection, clone that projection above the new scan so the query still returns the same columns in the same order.

Safe Match Contract

Course rule: Rewrite only when all of the following are true:

• the shape is the supported Limit/Sort/optional Projection/SeqScan chain;
• there is exactly one order-by expression and its direction is Default or ascending;
• the expression is a VectorExpression between a literal ArrayExpression and a table column;
• the selected index is a VectorIndex whose single key attribute is that table column;
• VectorIndex::distance_fn_ matches the query’s vector expression type; and
• the optional vector_index_method setting permits that index type.

The VectorIndexScanPlanNode stores an ArrayExpression as its base vector, so a column-to-column or other non-literal query is outside this checkpoint. Filters, joins, multiple sort keys, descending distance, and unsupported plan shapes must remain on the exact path. A fast plan that changes query meaning is a correctness bug.

Prediction: Suppose only a vector_cosine_ops index exists and the query orders by <-> L2 distance. Should the optimizer use the index? It must not: the ranking contract is different, so the exact TopN plan should remain.

Index Selection Setting

Optimizer::vector_index_match_method_ comes from SET vector_index_method=...:

• empty: accept a compatible IVFFlat or HNSW index;
• hnsw: accept only HNSW;
• ivfflat: accept only IVFFlat; and
• none: use exact search.

The catalog stores table indexes in an unordered map, so the particular compatible index chosen by the empty setting is not a stable preference rule. Use hnsw or ivfflat when a deterministic choice matters.

Verify the Checkpoint

From bustub-vectordb/build, run:

make -j8 sqllogictest
./bin/bustub-sqllogictest ../test/sql/vector.03-index-selection.slt --verbose

The file uses statement ok, so inspect every EXPLAIN block. The positive cases should contain VectorIndexScan; after SET vector_index_method=none, the plan should contain exact TopN.

<main>:1
CREATE TABLE t1(v1 VECTOR(3), v2 integer);
----
Table created with id = 24	

<main>:4
CREATE INDEX t1v1ivfflat ON t1 USING ivfflat (v1 vector_l2_ops) WITH (lists = 10, probe_lists = 3);
----
Index created with id = 0 with type = VectorIVFFlat	

<main>:7
CREATE INDEX t1v1hnsw ON t1 USING hnsw (v1 vector_l2_ops) WITH (m = 5, ef_construction = 64, ef_search = 10);
----
Index created with id = 1 with type = VectorHNSW	

<main>:10
EXPLAIN (o) SELECT v1 FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 2;
----
=== OPTIMIZER ===
Projection { exprs=["#0.0"] }
  VectorIndexScan { index_oid=1, index_name=t1v1hnsw, table_oid=24, table_name=t1 base_vector=[1.000000,1.000000,1.000000], limit=2 }
	

<main>:13
EXPLAIN (o) SELECT * FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 2;
----
=== OPTIMIZER ===
VectorIndexScan { index_oid=1, index_name=t1v1hnsw, table_oid=24, table_name=t1 base_vector=[1.000000,1.000000,1.000000], limit=2 }
	

<main>:16
EXPLAIN (o) SELECT v1, ARRAY [1.0, 1.0, 1.0] <-> v1 FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 2;
----
=== OPTIMIZER ===
Projection { exprs=["#0.0", "l2_dist([1.000000,1.000000,1.000000], #0.0)"] }
  VectorIndexScan { index_oid=1, index_name=t1v1hnsw, table_oid=24, table_name=t1 base_vector=[1.000000,1.000000,1.000000], limit=2 }
	

<main>:19
EXPLAIN (o) SELECT v2, v1 FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 2;
----
=== OPTIMIZER ===
Projection { exprs=["#0.1", "#0.0"] }
  VectorIndexScan { index_oid=1, index_name=t1v1hnsw, table_oid=24, table_name=t1 base_vector=[1.000000,1.000000,1.000000], limit=2 }
	

<main>:22
set vector_index_method=none
----

<main>:25
EXPLAIN (o) SELECT v1 FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 2;
----
=== OPTIMIZER ===
TopN { n=2, order_bys=[("Default", "l2_dist([1.000000,1.000000,1.000000], #0.0)")]}
  Projection { exprs=["#0.0"] }
    SeqScan { table=t1 }
	

<main>:28
set vector_index_method=ivfflat
----

<main>:31
EXPLAIN (o) SELECT v1 FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 2;
----
=== OPTIMIZER ===
Projection { exprs=["#0.0"] }
  VectorIndexScan { index_oid=0, index_name=t1v1ivfflat, table_oid=24, table_name=t1 base_vector=[1.000000,1.000000,1.000000], limit=2 }
	

<main>:34
set vector_index_method=hnsw
----

<main>:37
EXPLAIN (o) SELECT v1 FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 2;
----
=== OPTIMIZER ===
Projection { exprs=["#0.0"] }
  VectorIndexScan { index_oid=1, index_name=t1v1hnsw, table_oid=24, table_name=t1 base_vector=[1.000000,1.000000,1.000000], limit=2 }
	

Add at least one negative manual case before moving on: use a metric mismatch, ORDER BY ... DESC, or an extra filter and confirm that the plan stays exact. You are done when you can point to the comparison that checks the table column and the comparison that checks distance_fn_, and explain what incorrect rows each prevents.

Optional Extension

Support a plan that sorts by a projected distance alias:

EXPLAIN (o)
SELECT *
FROM (SELECT v1, ARRAY [1.0, 1.0, 1.0] <-> v1 AS distance FROM t1)
ORDER BY distance
LIMIT 2;

Before the Top-N rewrite, that query has this plan:

Limit { limit=2 }
  Sort { order_bys=[("Default", "#0.1")] }
    Projection { exprs=["#0.0", "l2_dist([1.000000,1.000000,1.000000], #0.0)"] }
      SeqScan { table=t1 }

The sort expression is a column reference to the projection’s computed distance. Trace it one additional step before applying the same safety contract. This form reuses the projected distance instead of computing it again.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

IVFFlat (Inverted File Flat) Index

IVFFlat is a simple quantization-based vector index that splits data into buckets to accelerate vector similarity search. A query probes only the nearest buckets, reducing distance calculations at the cost of possibly missing a true neighbor.

Complete the exact-search and optimizer chapters first. You will likely modify:

src/include/storage/index/ivfflat_index.h
src/storage/index/ivfflat_index.cpp

Related reading: IVF visualization in Pinecone’s Faiss guide

How IVFFlat Works

IVFFlat builds lists clusters over vectors already stored in the table. Each cluster has a centroid and a list of the vectors closest to that centroid. At lookup time, the index compares the query with the centroids first, then searches only probe_lists nearby lists instead of every vector. Searching less data makes the query faster, but skipping lists can miss a true neighbor, so IVFFlat returns approximate nearest neighbors.

Build the Lists

The checkpoint creates an IVFFlat index after the table already contains data. lists is the number of centroids and probe_lists is the number of centroid lists searched per query.

The first diagram shows the vectors before the index exists. They all belong to one unpartitioned data set, so an exact query would compare its target with every point.

When the user creates the index, K-means chooses lists initial centroids and alternates between assigning vectors to their nearest centroid and moving each centroid to the mean of its assigned vectors. In the second diagram, each colored centroid represents one future list. A boundary in the Voronoi diagram marks positions equally distant from the two centroids on either side.

Once the centroids are fixed, visit every stored vector and place (vector, RID) in the list for its nearest centroid under distance_fn_. The third diagram shows the resulting buckets: vectors in the same region will be searched together.

Diagram generated with websvg.github.io/voronoi and edited with OmniGraffle.

Course rules:

• Require 1 <= lists <= initial_data.size() and 1 <= probe_lists <= lists for a usable index.
• Build data stores each vector together with its RID.
• Every distance comparison uses the index’s distance_fn_.
• If a K-means cluster is empty, retain its previous centroid for that iteration. Never divide by zero or silently remove a list.
• The required IVFFlat checkpoint is not usable when built on an empty table. BuildIndex may return for empty input, but later insertion into that untrained index is outside the supported path.

A fixed number of iterations, such as 500, is acceptable. Stopping after convergence is also valid. A fixed random seed makes debugging repeatable; a nondeterministic seed is allowed, so exact approximate results may differ.

centroids = sample_distinct(initial_data, lists)
repeat up to 500 times:
    buckets = one empty bucket per centroid
    for (vector, rid) in initial_data:
        bucket_id = nearest_centroid(vector, centroids, distance_fn)
        buckets[bucket_id].append((vector, rid))

    for each bucket_id:
        if buckets[bucket_id] is not empty:
            centroids[bucket_id] = component_wise_mean(buckets[bucket_id].vectors)

rebuild buckets once using the final centroids

The final rebuild matters: otherwise the stored memberships describe the previous centroids rather than the centroids you return.

Insert a New Vector

Insertion finds the nearest existing centroid and appends (vector, RID) to that list. It does not retrain K-means.

In the diagram, the red vector is closest to centroid A, so insertion adds it to list A. The centroid stays where it was; the index does not rerun K-means for each row. This makes insertion cheap, but a changed data distribution can make the old centroids poor. Rebuilding is an operational choice, not part of this checkpoint.

Look Up Neighbors

The red vector in the next diagram is a query asking for its five nearest neighbors. If lookup searches only its nearest centroid’s list A, it can return five candidates from A, but some points just across the boundary in list B are actually closer to the query.

Probing both A and B exposes those candidates. Lookup computes distances within both lists, combines their local candidates, and keeps the best five overall. Increasing probe_lists repeats this idea across more nearby buckets: it does more work, but it is less likely to miss a true neighbor.

Implement ScanVectorKey(base_vector, limit) as follows:

1. return an empty result for limit = 0;
2. find the probe_lists_ nearest centroids;
3. evaluate the vectors in those lists;
4. retain the best limit candidates across all probed lists; and
5. return their RIDs sorted from smallest to largest distance.

The vector-index scan executor trusts this order and does not sort again. Returning the right RIDs in heap order is therefore incorrect.

You may keep a local top-k result per list and merge those results, or feed all probed candidates into one bounded heap. Both choices preserve the contract.

Prediction: If the query is just across the boundary from its nearest centroid, what happens to recall when probe_lists changes from 1 to 2? Which part of the lookup code should change, and which parts should not?

Verify the Checkpoint

From bustub-vectordb/build, run:

make -j8 sqllogictest
./bin/bustub-sqllogictest ../test/sql/vector.04-ivfflat.slt --verbose

Confirm that EXPLAIN contains VectorIndexScan, inserts after index construction are searchable, the result has at most LIMIT rows, and distances are nondecreasing. Random initialization can change which approximate rows appear.

<main>:1
CREATE TABLE t1(v1 VECTOR(3), v2 integer);
----
Table created with id = 24	

<main>:4
INSERT INTO t1 VALUES (ARRAY [-1.0, 1.0, 1.0], -1), (ARRAY [-3.0, 1.0, 1.0], -3), (ARRAY [-2.0, 1.0, 1.0], -2), (ARRAY [-4.0, 1.0, 1.0], -4), (ARRAY [0.0, 1.0, 1.0], 0), (ARRAY [2.0, 1.0, 1.0], 2), (ARRAY [4.0, 1.0, 1.0], 4), (ARRAY [5.0, 1.0, 1.0], 5);
----
0	

<main>:7
CREATE INDEX t1v1ivfflat ON t1 USING ivfflat (v1 vector_l2_ops) WITH (lists = 3, probe_lists = 2);
----
Index created with id = 0 with type = VectorIVFFlat	

<main>:10
EXPLAIN (o) SELECT v1, v2, ARRAY [1.0, 1.0, 1.0] <-> v1 as distance FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 3;
----
=== OPTIMIZER ===
Projection { exprs=["#0.0", "#0.1", "l2_dist([1.000000,1.000000,1.000000], #0.0)"] }
  VectorIndexScan { index_oid=0, index_name=t1v1ivfflat, table_oid=24, table_name=t1 base_vector=[1.000000,1.000000,1.000000], limit=3 }
	

<main>:13
SELECT v1, v2, ARRAY [1.0, 1.0, 1.0] <-> v1 as distance FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 3;
----
[0,1,1]	0	1.000000	
[2,1,1]	2	1.000000	
[-1,1,1]	-1	2.000000	

<main>:16
INSERT INTO t1 VALUES  (ARRAY [1.0, 1.0, 1.0], 1), (ARRAY [3.0, 1.0, 1.0], 3);
----
0	

<main>:19
SELECT v1, v2, ARRAY [1.0, 1.0, 1.0] <-> v1 as distance FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 5;
----
[1,1,1]	1	0.000000	
[2,1,1]	2	1.000000	
[0,1,1]	0	1.000000	
[-1,1,1]	-1	2.000000	
[3,1,1]	3	2.000000	

For an adversarial check, run the same query once with SET vector_index_method=none and once with SET vector_index_method=ivfflat. Treat exact Top-N as the oracle: every returned IVFFlat RID must exist, while overlap with the exact top-k measures recall.

You are done when you can explain why the final bucket rebuild is necessary, how (vector, RID) flows from index build to table lookup, and how increasing probe_lists trades work for recall.

Optional Extensions

• Implement Elkan’s accelerated K-means algorithm.
• Add an explicit index-rebuild operation.
• Add deletion and update interfaces.
• Design a persistent layout after restoring the full buffer-pool path.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

NSW (Navigable Small Worlds) Index

NSW is the graph-based building block of HNSW: it starts from one or more entry points and greedily follows neighbors closer to the query vector. This chapter implements it as the last fully specified checkpoint in the C++ course. The starter represents the graph as layers_[0] inside HNSWIndex so the next, optional chapter can add hierarchy.

Complete the previous chapters first. You will likely modify:

src/include/storage/index/hnsw_index.h
src/storage/index/hnsw_index.cpp

Related readings:

• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
• HNSW in Pinecone’s Faiss guide

Search One Layer

One Entry Point and One Neighbor

The first diagram shows an NSW graph in two dimensions. The highlighted red vertex is the entry point, and the query vector is elsewhere in the space. Search begins at the entry point because the graph does not provide a global ordering or a centroid that points directly to the answer.

Compare the query with every neighbor of the current vertex and move to a neighbor that is closer. Repeating this greedy step walks through the graph toward the query.

The walk stops when none of the current vertex’s neighbors is closer. Because it explores only graph edges, it can stop at a local minimum instead of the globally nearest vector; NSW is therefore an approximate index.

Multiple Entry Points and k Neighbors

Now ask for three neighbors while starting from two entry points. Searching multiple regions reduces the chance that one poorly placed entry point traps the walk in the wrong part of the graph. For k-nearest-neighbor search, maintain:

• C, a min-heap of candidates to explore, with the nearest candidate on top;
• W, a max-heap of the best visited candidates, with the worst retained result on top; and
• visited, a set that prevents repeated graph expansion.

Seed all three structures from both entry points. The next diagram shows the initial state before any vertex is expanded.

The nearest item in C is entry point 1. Pop it, mark its unseen neighbors as visited, add promising neighbors to C and W, and keep only the three best visited candidates in W.

The next candidate is the highlighted vertex below. Its neighbors have already been visited, so expanding it does not add anything to either queue.

Entry point 2 is now the nearest unexplored candidate. Expanding it adds candidates from a different part of the graph, which is the benefit of seeding the search from more than one location.

Continue popping the nearest candidate and updating W. Even when many vertices have been visited, W retains only the three closest ones found so far.

Eventually the nearest candidate left in C is farther from the query than the worst result in the full W. No queued candidate can improve the result, so the search stops.

C = entry_points as a min-heap by distance
W = unique entry_points as a max-heap by distance
visited = unique entry_points

while C is not empty:
    candidate = C.pop_nearest()
    if W is full and distance(candidate) > distance(W.worst):
        break

    for neighbor in candidate.neighbors:
        if neighbor is already visited:
            continue
        mark neighbor visited
        if W is not full or distance(neighbor) < distance(W.worst):
            C.push(neighbor)
            W.push(neighbor)
            trim W to the search width

return W sorted from nearest to farthest

Why Multiple Entry Points Matter

If the same graph asks for two neighbors but starts only from entry point 1, the search can reach the state below and stop: every remaining candidate in C is worse than both results in W, even though the graph contains closer vertices in another region. A second entry point seeds that region directly; it does not guarantee exact search, but it reduces this failure mode.

Course rules for NSW::SearchLayer:

• return an empty vector for limit = 0, no entry points, or an empty layer;
• ignore duplicate entry-point IDs and never visit a vertex more than once;
• use dist_fn_ for every comparison; and
• return at most limit vertex IDs, sorted from nearest to farthest.

Insert into the Graph

To insert the highlighted new vector, search the existing graph with width ef_construction, then select its nearest m candidates as neighbors. The first diagram shows those selected connections.

NSW::Connect creates an undirected edge between the new vertex and each selected neighbor. Those new edges can put an existing vertex over the layer’s m_max_ degree cap, as in the second diagram.

For every overfull vertex, re-select its nearest m_max_ neighbors. The third diagram marks the edges that survive this pruning decision.

Finally, remove every rejected edge from both endpoints. The last diagram is the resulting graph; updating only the overfull vertex would leave one-sided edges and break the undirected-graph invariant.

Course rules for insertion:

• The first vertex is added without searching or connecting.
• Do not create self-edges or duplicate edges.
• Keep edges_[a] and edges_[b] symmetric after both connection and pruning.
• SelectNeighbors returns at most m unique IDs ordered by dist_fn_.
• Add the new vertex to the layer exactly once.

The starter parameters mean:

• m_: how many neighbors a new vertex selects;
• ef_construction_: the insertion-search width;
• ef_search_: the query-search width;
• m_max_: the upper-layer degree cap reserved for HNSW; and
• m_max_0_: the layer-0 degree cap. The starter derives it as m_ * m_ and assigns it to layers_[0].m_max_.

Require m > 1, ef_construction >= m, and ef_search >= 1. The first condition also keeps the starter’s m_l_ = 1 / log(m) finite for the optional HNSW extension.

For a SQL LIMIT k, search layer 0 with width max(k, ef_search_), then select and return the nearest k RIDs. This ensures that a request for more than ef_search_ rows can still return k rows, while a larger ef_search_ can improve recall.

Verify the Checkpoint

From bustub-vectordb/build, run:

make -j8 sqllogictest
./bin/bustub-sqllogictest ../test/sql/vector.05-hnsw.slt --verbose

Confirm that results are sorted by distance, inserts after index construction are searchable, and the LIMIT 5 query can return five rows even though the test index uses ef_search = 3. Random build order can change tie ordering.

<main>:1
CREATE TABLE t1(v1 VECTOR(3), v2 integer);
----
Table created with id = 24	

<main>:4
INSERT INTO t1 VALUES (ARRAY [0.0, 1.0, 1.0], 0), (ARRAY [1.0, 1.0, 1.0], 1), (ARRAY [2.0, 1.0, 1.0], 2), (ARRAY [3.0, 1.0, 1.0], 3), (ARRAY [4.0, 1.0, 1.0], 4), (ARRAY [5.0, 1.0, 1.0], 5);
----
0	

<main>:7
CREATE INDEX t1v1hnsw ON t1 USING hnsw (v1 vector_l2_ops) WITH (m = 3, ef_construction = 3, ef_search = 3);
----
Index created with id = 0 with type = VectorHNSW	

<main>:10
EXPLAIN (o) SELECT v1, v2, ARRAY [1.0, 1.0, 1.0] <-> v1 as distance FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 3;
----
=== OPTIMIZER ===
Projection { exprs=["#0.0", "#0.1", "l2_dist([1.000000,1.000000,1.000000], #0.0)"] }
  VectorIndexScan { index_oid=0, index_name=t1v1hnsw, table_oid=24, table_name=t1 base_vector=[1.000000,1.000000,1.000000], limit=3 }
	

<main>:13
SELECT v1, v2, ARRAY [1.0, 1.0, 1.0] <-> v1 as distance FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 3;
----
[1,1,1]	1	0.000000	
[2,1,1]	2	1.000000	
[0,1,1]	0	1.000000	

<main>:16
INSERT INTO t1 VALUES (ARRAY [-1.0, 1.0, 1.0], -1), (ARRAY [-2.0, 1.0, 1.0], -2), (ARRAY [-3.0, 1.0, 1.0], -3), (ARRAY [-4.0, 1.0, 1.0], -4);
----
0	

<main>:19
SELECT v1, v2, ARRAY [1.0, 1.0, 1.0] <-> v1 as distance FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 5;
----
[1,1,1]	1	0.000000	
[2,1,1]	2	1.000000	
[0,1,1]	0	1.000000	
[3,1,1]	3	2.000000	
[-1,1,1]	-1	2.000000	

Also compare an NSW query with SET vector_index_method=none. Exact Top-N is the oracle for recall, not a requirement that every approximate result match.

Prediction: If the graph has two disconnected components and every entry point is in the first component, can SearchLayer return a vertex from the second? Explain why the visited and stop-condition code cannot repair missing connectivity.

You are done when you can trace one vertex ID through vertices_, layers_[0].edges_, rids_, and the table lookup, and explain what would break if pruning removed only one side of an undirected edge.

Optional Extensions

• Implement the paper’s heuristic neighbor-selection rule.
• Add deletion and update support.
• Persist the graph after defining a stable on-disk layout.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

HNSW (Hierarchical Navigable Small Worlds) Index

The previous chapter stored its one-layer NSW graph in layers_[0]. In this chapter, you will add sparse NSW layers above it and use them during insertion and lookup. This hierarchy makes graph search more efficient, much like a skip list or mipmap: upper layers make long jumps, while layer 0 still contains every vertex and produces the final candidates.

Files you will likely modify:

src/include/storage/index/hnsw_index.h
src/storage/index/hnsw_index.cpp

Related readings:

• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
• HNSW in Pinecone’s Faiss guide

How Hierarchy Works

Layer 0 contains every vector. Each higher layer contains a progressively smaller random subset, much like the sparse levels of a skip list or the lower-resolution levels of a mipmap. Search starts in the sparsest top layer, where one edge can cross a large part of the data set, then carries the nearest vertex found there down as the entry point to the next layer. Layer 0 performs the final k-nearest-neighbor search.

The diagram shows the same vector IDs repeated across nested layers. A vertex that appears in an upper layer must also appear in every layer below it. Sparse upper-layer edges provide long jumps; denser lower-layer edges refine the search around the query.

What Must Hold, and What Breaks If It Doesn’t

The hierarchy stays coherent only while each upper-layer vertex also exists in the layers below and every stored identifier names the same global vector.

Layer 0 contains every vertex. A vertex missing there can never appear in the final candidate search, even if an upper layer found it.

Membership is nested: a vertex in layer L also appears in every lower layer. Without that nesting, the entry point selected in one layer may not exist in the next layer down.

Every layer stores global vertex IDs that index vertices_ and rids_. Treating a layer-local position as a global ID makes lookup compare or return the wrong record.

Upper layers use m_max_, while layer 0 uses m_max_0_. Swapping or ignoring these bounds can make the navigation layers too dense or leave the final search layer too sparse.

Edges remain symmetric within each layer. A one-sided edge makes reachability depend on traversal direction and leaves pruning with two different views of the graph.

The top entry point belongs to the current highest nonempty layer. A stale entry point starts lookup from a vertex that the first search layer does not contain.

The starter header has no dedicated top-entry-point field. You may add one, or derive it consistently from the highest layer. That representation is your choice; the invariants are not.

Lookup

In the lookup diagram, search begins at the entry point in the highest layer. A width-1 greedy search finds that layer’s nearest vertex to the query; that vertex becomes the entry point for the layer below. Repeat this descent through each upper layer. At layer 0, widen the search to max(k, ef_search_) candidates and return the nearest k RIDs in distance order. The upper layers navigate quickly; layer 0 produces the result.

entry_points = [top_entry_point]
for level from highest_level down to 1:
    entry_points = layers[level].search(target, limit=1, entry_points)

candidates = layers[0].search(
    target,
    limit=max(k, ef_search),
    entry_points=entry_points,
)
return nearest k candidates

Return an empty result for an empty index or k = 0; do not call DefaultEntryPoint() on an empty layer.

Insertion

Draw a random U strictly greater than zero and compute \( \text{level} = \lfloor -\ln(U) \times m_L \rfloor \). The starter sets \( m_L = 1 / \ln(m) \), which requires m > 1.

Suppose the random level is 1, as in the first diagram. The new vector belongs to layers 1 and 0, but not to layer 2. This random promotion is what makes higher layers progressively sparser.

Start at the current top layer and use width-1 searches until reaching the new vector’s highest target layer. At that layer and every layer below it, search ef_construction_ candidates, select the nearest m_, connect the new vertex, and prune both sides of rejected edges. The second diagram follows those connections down through the layers that contain the new vector.

if the index is empty:
    create layers 0 through target_level
    add the first vertex to every layer
    make it the top entry point
    return

entry_points = [top_entry_point]
for level from current_highest down to target_level + 1:
    entry_points = layers[level].search(target, limit=1, entry_points)

for level from min(current_highest, target_level) down to 0:
    candidates = layers[level].search(target, ef_construction, entry_points)
    neighbors = nearest m candidates
    add the new vertex to this layer and connect it to neighbors
    prune overfull endpoints while preserving symmetric edges
    entry_points = candidates

if target_level is above current_highest:
    create each missing upper layer with only the new vertex
    make the new vertex the top entry point

This outline still leaves engineering choices such as random seeding and helper layout to the implementer. Refer to the paper for the complete algorithm.

Verify the Checkpoint

From bustub-vectordb/build, run the same SQLLogicTest used in the NSW chapter:

make -j8 sqllogictest
./bin/bustub-sqllogictest ../test/sql/vector.05-hnsw.slt --verbose

<main>:1
CREATE TABLE t1(v1 VECTOR(3), v2 integer);
----
Table created with id = 24	

<main>:4
INSERT INTO t1 VALUES (ARRAY [0.0, 1.0, 1.0], 0), (ARRAY [1.0, 1.0, 1.0], 1), (ARRAY [2.0, 1.0, 1.0], 2), (ARRAY [3.0, 1.0, 1.0], 3), (ARRAY [4.0, 1.0, 1.0], 4), (ARRAY [5.0, 1.0, 1.0], 5);
----
0	

<main>:7
CREATE INDEX t1v1hnsw ON t1 USING hnsw (v1 vector_l2_ops) WITH (m = 3, ef_construction = 3, ef_search = 3);
----
Index created with id = 0 with type = VectorHNSW	

<main>:10
EXPLAIN (o) SELECT v1, v2, ARRAY [1.0, 1.0, 1.0] <-> v1 as distance FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 3;
----
=== OPTIMIZER ===
Projection { exprs=["#0.0", "#0.1", "l2_dist([1.000000,1.000000,1.000000], #0.0)"] }
  VectorIndexScan { index_oid=0, index_name=t1v1hnsw, table_oid=24, table_name=t1 base_vector=[1.000000,1.000000,1.000000], limit=3 }
	

<main>:13
SELECT v1, v2, ARRAY [1.0, 1.0, 1.0] <-> v1 as distance FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 3;
----
[1,1,1]	1	0.000000	
[0,1,1]	0	1.000000	
[2,1,1]	2	1.000000	

<main>:16
INSERT INTO t1 VALUES (ARRAY [-1.0, 1.0, 1.0], -1), (ARRAY [-2.0, 1.0, 1.0], -2), (ARRAY [-3.0, 1.0, 1.0], -3), (ARRAY [-4.0, 1.0, 1.0], -4);
----
0	

<main>:19
SELECT v1, v2, ARRAY [1.0, 1.0, 1.0] <-> v1 as distance FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 5;
----
[1,1,1]	1	0.000000	
[0,1,1]	0	1.000000	
[2,1,1]	2	1.000000	
[3,1,1]	3	2.000000	
[-1,1,1]	-1	2.000000	

Confirm that the nearest-neighbor queries use a vector index scan and return rows in distance order. Random layer selection can make your output differ from the reference.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

Benchmarking IVFFlat and HNSW on SIFT1M

Small SQL fixtures expose correctness bugs, but they do not show how an approximate index behaves at realistic scale. This capstone uses the standard SIFT1M corpus to connect three quantities:

• the time spent loading data and preparing the index;
• end-to-end query throughput; and
• the probability that the exact nearest neighbor appears near the top of an approximate result.

The benchmark harness is tools/vectordb_bench/vectordb_bench.cpp. Its provided configuration uses HNSW; a later section shows the small control-flow change needed to benchmark IVFFlat.

What the Harness Measures

On each run, bustub-vectordb-bench:

1. creates t1(v1 VECTOR(128), v2 INTEGER);
2. creates an L2 HNSW index with m = 16, ef_construction = 64, and ef_search = 100;
3. reads one million base vectors and inserts each through an SQL statement;
4. reads 10,000 query vectors and their exact ground-truth neighbors;
5. asks BusTub for 100 rows per query; and
6. reports cumulative timestamps and R@1, R@10, and R@100.

The index exists before the first row is inserted. “Loading database” therefore includes SQL construction and parsing, table insertion, and incremental HNSW maintenance. It is not a pure bulk-index-build timer.

Queries also run one at a time through the full SQL path. Their elapsed time includes SQL parsing, planning, index execution, tuple materialization, result conversion, and metric bookkeeping. Treat this as an end-to-end BusTub measurement, not as the latency of the HNSW search function by itself.

The harness logs failed inserts, but it does not check each query’s ExecuteSql return value. If a run produces empty results, check query execution before tuning the index.

What R@R Means

For each query, SIFT1M supplies the exact nearest vector as the first ground-truth ID. The harness checks whether that one ID appears within the first 1, 10, or 100 approximate results. This is 1-nearest-neighbor recall at rank R, matching the convention used by Faiss’s SIFT1M experiments. It is not the fraction of the exact top 100 set that BusTub recovered.

The recall values should always follow:

0 <= R@1 <= R@10 <= R@100 <= 1

A result can have low R@1 and high R@100: the correct neighbor was found, but ranked behind other candidates.

Build an Optimized Benchmark

Create a Release build for the benchmark. On Ubuntu, from the repository root:

cmake -S . -B build-bench \
  -DCMAKE_BUILD_TYPE=Release \
  -DCMAKE_POLICY_VERSION_MINIMUM=3.5 \
  -DCMAKE_C_COMPILER=clang-14 \
  -DCMAKE_CXX_COMPILER=clang++-14
cmake --build build-bench --target vectordb-bench -j8

On macOS, use the llvm@14 compiler paths from the overview instead. The executable is build-bench/bin/bustub-vectordb-bench.

Prepare SIFT1M

Download ANN_SIFT1M from the TexMex corpus page, which is also the source named by the Faiss benchmark documentation. The course does not redistribute the dataset. The benchmark’s FvecsRead and IvecsRead functions read the corpus files directly; no conversion script or separate reader is required. Extract or copy the files into this layout:

build-bench/
  sift1M/
    sift_base.fvecs
    sift_query.fvecs
    sift_groundtruth.ivecs

The harness does not use sift_learn.fvecs. Check the required paths before starting:

test -f build-bench/sift1M/sift_base.fvecs
test -f build-bench/sift1M/sift_query.fvecs
test -f build-bench/sift1M/sift_groundtruth.ivecs

SIFT1M contains one million 128-dimensional base vectors and 10,000 queries. BusTub stores vectors as doubles in both the table and the graph, keeps table pages in memory, and allocates a large buffer pool in the harness. Plan for several gigabytes of available memory. The million individual SQL inserts can also take substantial time.

Run the HNSW Benchmark

Run from the directory that directly contains sift1M:

cd build-bench
./bin/bustub-vectordb-bench | tee run.txt
cd ..

All timestamps are seconds since process start. Use the timestamp printed beside Loading queries as the end of the base-row load and incremental graph build. Use the difference between Doing query, #0 and Compute recalls as the query duration:

query_seconds = compute_recalls_timestamp - first_query_timestamp
queries_per_second = 10000 / query_seconds

Run an IVFFlat Benchmark

The provided harness creates its HNSW index before loading rows, so each insert incrementally updates the graph. IVFFlat has a different build path: it learns centroids from data already in the table. To benchmark IVFFlat in your working copy:

1. keep the base-vector insertion loop in InsertIndexVectorData;
2. move index creation after that loop; and
3. replace the HNSW statement with an IVFFlat statement such as:

CREATE INDEX t1v1ivfflat ON t1 USING ivfflat
  (v1 vector_l2_ops) WITH (lists = 10, probe_lists = 3);

Add timestamps immediately before and after CREATE INDEX if you want to separate table loading from the offline IVFFlat build. The query reader, ground-truth reader, and recall calculation can stay unchanged.

Explore One Tradeoff

HNSW

The index SQL is the create_index string in vectordb_bench.cpp. Keep m = 16 and ef_construction = 64 fixed, then compare ef_search = 100 and ef_search = 200.

Each benchmark query uses LIMIT 100, so k = 100. The lookup contract from the HNSW chapter searches with width max(k, ef_search). As a result, ef_search = 50 and ef_search = 100 both produce an effective width of 100; comparing 100 with 200 actually changes the number of candidates the graph search may retain.

Rebuild and rerun after changing the string. For a controlled comparison, use the same random seed in your HNSW implementation; otherwise repeat each configuration and report the variation.

IVFFlat

Keep lists fixed and change probe_lists, for example from 1 to 3. The first run searches one centroid list per query; the second searches three. This directly exposes the IVFFlat tradeoff between scanning more candidates and finding more of the exact neighbors.

The following compact table is enough to compare the runs:

For HNSW, preparation includes row insertion and incremental graph maintenance. For IVFFlat, it includes row insertion followed by the offline centroid build, so the preparation column represents the complete path to a queryable index in both cases.

Reading the Results

The benchmark is most useful as a comparison rather than a pass/fail exercise. Keep the command output and the table, then add a short explanation of what changed when you increased ef_search or probe_lists. If R@10 or R@100 rises while R@1 stays flat, the exact neighbor is appearing in the candidate set without consistently ranking first. If the numbers do not change at all, trace the parameter from the SQL option into the index lookup before drawing a conclusion.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/vector-db-from-scratch.
vector-db-from-scratch-book © 2024-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.