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

Start with a supplied product tour: launch an empty SQL session, create and populate an in-memory points table, attach an IVFFlat index to its selected vector column, and watch EXPLAIN change without changing the nearest rows. Across the six implementation days that follow, you will connect that table to DataFusion, implement the optimizer rule that selects a safe vector-index scan, build IVFFlat behind that rule, navigate a proximity graph with NSW, add HNSW hierarchy, compress residual candidate scoring with IVF-PQ, and compare all five indexes on SIFT1M. The first five days return to runnable SQL so you can inspect how the same product path changes as the index becomes more capable. The final day measures first-neighbor rank recall and latency directly under one shared Euclidean, k = 100 contract.

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

The product tour creates and fills the table, then runs a concrete query of this shape through the supplied completed system before you edit anything. DataFusion’s vector distance expression, bounded sort, and LIMIT return an exact result; after you create a named index on the selected vector column, that unchanged SQL reaches the course’s vector-index scan. Day 1 then asks you to build the safe table, attachment, and planner path behind that observation. Later, you will add IVFFlat as your own candidate selector behind the same interface.

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 one supplied example from vector-db/; you do not need to inspect or modify that implementation. After the tour, work in vector-db-starter/ and implement its TODOs in day order. Keep the completed reference source closed while you work through the exercises, as required by the starter’s AGENTS.md files.

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 names the exact tests that should pass before you move on, then closes with cargo x test-day N for that day’s work and cargo x test-through N 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.

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 only 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 selects candidates; SortExec owns SQL ordering. When the selected index returns rows in the requested order, SET vector_search.ordered = true tells DataFusion it can skip this final sort.

Filters, multiple sort keys, a non-literal query vector, another same-shaped vector column, the wrong distance function, the wrong direction, or a dimension mismatch keep the exact plan. In particular, taking ANN top-k before applying a filter can change the answer, so refusing that rewrite is a correctness requirement.

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, SQL-pattern matching, plan properties, limits, and output batches. The core crate owns dimensions, metrics, exact-search results, candidate selection, and deterministic result order. Later index implementations will not import DataFusion.

This separation gives Days 1–5 two useful views of each checkpoint: small Rust tests isolate the algorithm, while self-contained SQLLogicTests show that the Day 1 optimizer can reach it. Day 5 also keeps a focused planner/EXPLAIN test for IVF-PQ; Day 6 brings every index into one fixed full-SIFT1M comparison and an explicitly non-parity smoke mode.

System Contract

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 gives you an exact end-to-end query whose rows and physical plan you can inspect. Days 2–5 keep that SQL interface and safety rule in place while changing how candidate rows are selected. Day 6 then compares all five indexes without changing the SIFT1M data, queries, Euclidean metric, or k = 100; its smaller mode is labeled non-parity because it recomputes truth over a 10,000-row subset.

After Day 6, you should be able to explain:

• how row identity survives conversion from Rust structs to core offsets and Arrow arrays;
• which physical expression shapes are safe to lower to a vector index;
• why DataFusion retains exact fallback for filtered or incompatible top-k queries;
• why the optimizer rule must exist before an approximate index can be exercised from SQL;
• why IVFFlat must rebuild list membership after its final centroid update; and
• how probes trades candidate work for recall without changing SQL;
• why NSW needs separate candidate and result frontiers;
• how reciprocal pruning preserves a bounded graph;
• why HNSW uses greedy upper layers and a layer-zero beam;
• how seeded promotion makes comparisons reproducible;
• why IVF-PQ separates coarse centroids, residual codebooks, approximate scoring, and exact reranking; and
• how supplied or recomputed exact first-neighbor truth, cyclic warm-up and timing order, and one shared workload make rank recall and latency interpretable together.

Scope

These six days use an immutable in-memory collection and a readable Euclidean residual IVF-PQ implementation, but not bit packing or optimized kernels. Online updates or deletes, index persistence, crash recovery, concurrent mutation, filtered ANN, GPU kernels, distributed execution, general catalog semantics, and a network service remain outside this implementation. The supplied shell’s bounded CREATE INDEX bridge resolves eligible named or qualified in-memory tables, supports multiple distinct attachments, and rejects writes that would stale an indexed snapshot; it is not a persistence, online-maintenance, or general catalog subsystem. The final day also assumes a locally acquired SIFT1M directory; the repository supplies parsers and tiny 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

Before you implement the table adapter or optimizer, use the supplied system once. You will create and populate an ordinary in-memory table, run one nearest-neighbor query, attach an index to its vector column, and see the physical plan change while the SQL result stays the same.

This tour uses the completed vector-db-from-scratch-datafusion example. You do not need to read or modify its source. Your own work begins on Day 1.

Launch the Supplied Shell

For an interactive run, start from the repository root:

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

The supplied DataFusion CLI starts with an empty course session and accepts semicolon-terminated SQL, including statements that span multiple lines. For a repeatable first run from the repository root, paste the whole transcript below into your terminal instead of entering the statements interactively:

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 should be nearest and why creating an index must not change them.

Observe the Stable Query and Changing Plan

Before the index exists, DataFusion reads the ordinary in-memory table:

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

The first query returns these rows:

1  one
2  two
3  three

Prediction: The next command attaches an index, but the following SELECT is byte-for-byte identical. Which physical plan leaf should change, and which three rows must not?

The CREATE INDEX statement builds the session’s cosine IVFFlat index and attaches it to the vector column you selected. The second EXPLAIN reaches the course-owned scan:

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

The second query is byte-for-byte the same SQL and returns the same three rows. The index changes how candidates reach DataFusion’s final sort; it does not change the query contract.

Know What This Command Means

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 therefore owns a bounded bridge from that statement to the course’s existing attachment path. The session is configured for cosine IVFFlat, while the statement supplies the index name, resolved table, and selected 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. The bridge can attach indexes to multiple distinct table/column pairs in one session. Each target must be a registered in-memory MemTable, and its selected column must be a non-null REAL[N] vector with positive width. Duplicate names or attachments, missing tables or columns, providers other than MemTable, nullable fields, vector fields with the wrong physical type or zero width, and an index kind different from the session configuration are rejected before an attachment is installed.

Prediction: Suppose the session also contains another eligible table with a different vector field. Which table, column, and index names must the bridge resolve from the SQL statement rather than hard-code from this points example?

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. The bridge does not add index persistence, DROP INDEX, automatic rebuilding, or a general catalog lifecycle.

Prediction: Why must a later INSERT into the indexed table be rejected unless the table update and a rebuilt index can become visible atomically?

That narrow boundary keeps the first experience concrete without turning the course into a parser or catalog project. Next, Day 1 opens the path you just used: you will build the Arrow table, attach one selected vector field, and make the optimizer choose VectorIndexScanExec only when doing so is safe.

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.

In the product tour, you began with an empty session, created and populated points, then ran the supplied shell before and after attaching an index to embedding. The SQL and nearest rows stayed fixed while the physical leaf changed from DataSourceExec to VectorIndexScanExec. Day 1 opens that path: you will build the Arrow table, bind one selected vector field to an index, and make the optimizer choose the new scan only when the query is safe.

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;

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

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

That plan is exact for every valid query. A vector index can select candidates only when the SQL ordering refers to the same metric, literal, dimension, direction, and configured vector column. A match changes the leaf while leaving 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 the same boundary.

From the Product Tour to Your First Checkpoint

The product tour showed the complete path before asking you to build it. Keep these boundaries separate as you work through the day:

You will modify:

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

The starter exposes the same public API as the reference but leaves the Day 1 implementation points as TODOs. Metric math, the exact FlatIndex, shared snapshot/lookup scaffolding, examples, and tests are ready. IVFFlat, NSW, HNSW, and IVF-PQ remain later learner work. Do not modify public APIs or tests while completing the exercises.

Checkpoint 1: Validate the In-Memory Dataset

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

A dataset must be nonempty, have a fixed nonzero dimension, and contain only finite f32 values. Dataset::try_new reads the first row to establish the dimension, rejects an empty dataset or zero-dimensional vector, then checks every row for equal length and finite components. Store the 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 test -p vector-db-from-scratch-core-starter --test indexes day_01_flat_search_is_deterministic_and_validates_queries
cargo test -p vector-db-from-scratch-core-starter --test indexes day_01_cosine_rejects_zero_norm_vectors

Checkpoint 2: Build the Introductory MemTable

A vector index belongs to one field of an ordinary table. It does not own a special (id, payload, vector) row format.

The small VectorRow and vector_mem_table helper remain the first example because they make Arrow construction easy to inspect:

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 to validate their shared dimension. Create the three Arrow arrays in the same input order, assemble one RecordBatch, then return 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.

Prediction: What breaks if the payload array is reordered while the embedding array keeps insertion order?

Checkpoint 3: Attach One Selected Vector Column

The public indexing surface is more general. Register any MemTable, then construct a VectorIndexAttachment with its table reference and selected vector-column name:

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 resolves each accepted CREATE INDEX target into this same attachment constructor. The bridge is already implemented; your Day 1 work is the attachment and execution path it calls.

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. A query ordered by text_embedding may use the attached index. The same query shape over image_embedding must remain on DataFusion’s exact scan and return the image-vector ranking. No field name or ordinal is inherently special; only the field selected by the attachment may use its index.

The attachment snapshots the registered MemTable batches. It copies only the selected vectors into the core Dataset and records a checked row location for each dataset ordinal:

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

The source Arrow buffers remain shared with the ordinary MemTable. Scalar columns and the unselected vector column stay normal table data. User columns are never row identity.

DataFusion has no generic stable point-lookup API for arbitrary TableProvider implementations. This adapter is therefore intentionally limited to registered in-memory MemTable instances. A disk or distributed provider would need its own stable row locator and lookup implementation.

An attachment must resolve the exact registered MemTable instance and the configured field. The selected field must exist, be FixedSizeList<Float32>, have a positive width, and contain no null list or null element. Each source row must contribute exactly one dataset vector and one checked snapshot row location.

A different positive list width is a valid schema choice; the core dataset takes its dimension from the selected field. The SQL matcher later rejects a literal whose width differs from that dataset. A zero-width selected field is invalid at construction.

Implement VectorIndexAttachment::try_new.

1. Resolve the table reference and prove the supplied Arc<MemTable> is the registered provider.
2. Snapshot every partition and batch, requiring one shared schema.
3. Resolve only the configured vector-column name.
4. Validate its Arrow type, positive width, and non-null values.
5. Copy those selected vectors into Dataset in batch/row order.
6. Build the requested core index and record the corresponding checked row locations.

The rich-schema tests make the ownership rule observable: text and image vectors have identical shapes but different rankings.

cargo test -p vector-db-from-scratch-datafusion-starter --test sql day_01_rich_schema_matches_only_the_configured_vector_column
cargo test -p vector-db-from-scratch-datafusion-starter --test sql day_01_rich_schema_rejects_a_missing_selected_column
cargo test -p vector-db-from-scratch-datafusion-starter --test sql day_01_rich_schema_rejects_a_scalar_selected_column
cargo test -p vector-db-from-scratch-datafusion-starter --test sql day_01_rich_schema_rejects_a_zero_width_selected_column
cargo test -p vector-db-from-scratch-datafusion-starter --test sql day_01_rich_schema_rejects_a_null_selected_value

Checkpoint 4: Match and Rewrite One Safe Top-k

Implement match_vector_order and VectorIndexOptimizer::rewrite_sort.

The optimizer may replace a scan only for one supported distance expression over the configured vector field, a literal query vector, a compatible metric and direction, a positive LIMIT, and a live source snapshot. Filters, multiple sort keys, non-literal vectors, another vector field, wrong metrics or directions, and invalid literals remain on DataFusion’s exact scan and sort.

Unless ordered output is explicitly enabled for the session, DataFusion retains the final bounded sort after the index selects candidates. Candidate order is not automatically SQL order.

The matcher accepts only:

1. one physical sort expression;
2. Euclidean array_distance/list_distance, cosine_distance, or dot inner_product/dot_product;
3. ascending Euclidean/cosine or descending dot-product order;
4. one vector Column and one literal;
5. the exact configured vector-column name after projection;
6. a finite literal with the index dataset’s dimension; and
7. a nonzero cosine literal.

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 the physical MemorySourceConfig still matches the attached table, snapshot, schema, projection, and unambiguous live provider. On a match, construct VectorIndexScanExec; otherwise leave the plan unchanged.

cargo test -p vector-db-from-scratch-datafusion-starter --test sql day_01_compatible_top_k_uses_vector_index_scan_and_keeps_sort
cargo test -p vector-db-from-scratch-datafusion-starter --test sql day_01_unsafe_sort_shapes_are_not_lowered
cargo test -p vector-db-from-scratch-datafusion-starter --test sql day_01_filter_keeps_datafusion_exact_fallback
cargo test -p vector-db-from-scratch-datafusion-starter --test sql day_01_dot_product_requires_descending_order

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. Reject an index result that does not resolve to the snapshot. The supplied lookup scaffolding reconstructs the requested projection in index-result order.

For ordered=true, return the scan with its accepted ordering property. For the default ordered=false path, 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 test -p vector-db-from-scratch-datafusion-starter --test sql day_01_ordered_session_mode_allows_sort_elision
cargo test -p vector-db-from-scratch-datafusion-starter --test sqllogictest day_01_table_and_optimizer_sql

The SQLLogicTest starts from an empty session: it creates and inserts the simple points table and a rich documents table, then attaches indexes to the selected columns. text_embedding reaches VectorIndexScanExec, while image_embedding stays on DataSourceExec and returns its different ranking.

Day 1 Review

Run the Day 1 focused and cumulative gates:

cargo x test-day 1
cargo x test-through 1

After the core tests, sql.rs, and the Day 1 SQLLogicTest pass, explain:

• how the simple VectorRow helper becomes an ordinary MemTable;
• why an attachment owns exactly one configured vector field;
• how an index dataset ordinal resolves to a projected source row;
• why the same-shaped image-vector query cannot use the text-vector index;
• where DataFusion performs exact fallback and final ordering; and
• why the supplied session rejects changes to an indexed table instead of letting its attachment become stale;
• how later approximate indexes reuse this boundary without weakening it.

IVFFlat implementation, filtered pushdown, joins, general DDL/catalog semantics, persistence, and disk row lookup remain outside Day 1. The product tour’s supplied bridge resolves an eligible in-memory table and selected vector column into the attachment path you implemented here. It can hold multiple distinct attachments, but it rejects mutation of an indexed table and 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 and a conservative DataFusion path that can use it. The SQL matcher, selected vector column, checked row lookup, and final SortExec are already working. Day 2 changes only how the index chooses candidates: IVFFlat groups dataset rows into inverted lists, then searches the lists nearest to the query. It is a coarse quantization index: comparing against a small set of centroids chooses which full-precision vectors to score.

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 the completed Day 1 case first:

cargo test -p vector-db-from-scratch-datafusion-starter --test sqllogictest day_01_table_and_optimizer_sql

Now run the Day 2 case before implementing IVFFlat:

cargo test -p vector-db-from-scratch-datafusion-starter --test sqllogictest day_02_ivfflat_sql

This second command is your product-level expected failure. It uses the same DataFusion integration with IndexConfig::IvfFlat, then reaches the unfinished IVFFlat constructor. At the end of the day, the same command must reach this plan and return 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 already 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 is the fraction of expected top-k row offsets present in the approximate top-k:

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

Use row membership, not distance equality or result position. The denominator is the number of exact results available within k, not always k itself. If exact search returns two rows for k = 10, an approximate index can recover at most those two rows. Define recall as 1.0 when that denominator is zero; an empty request has missed nothing.

cargo test -p vector-db-from-scratch-core-starter --test indexes day_02_recall_reports_result_overlap

This function gives the approximate result a correctness meaning. Timing and cross-index comparison remain separate; the final benchmark will measure 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 test -p vector-db-from-scratch-core-starter --test indexes day_02_ivf_rejects_invalid_build_configuration

Once invalid configurations fail before any training work, initialize the centroids. The starter supplies DeterministicRng; use it to shuffle row offsets, then copy the first partitions dataset rows. Sampling distinct offsets avoids beginning with the same row twice.

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 how your implementation consumes deterministic randomness. A second build with the same implementation, data, metric, configuration, and seed must reproduce its centroids, lists, and results; it does not need to copy the reference implementation’s centroid identities.

Prediction: If another correct implementation consumes the seeded generator in a different deterministic order, which properties must still hold even though its centroid row offsets can differ?

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

K-means begins from the seeded centroids and alternates between assigning vectors to their 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

For up to iterations rounds:

1. assign every vector to its nearest centroid;
2. stop early if the complete assignment vector did not change;
3. accumulate component-wise sums and counts for each partition; and
4. replace each non-empty centroid with its component-wise mean.

Keep sums in f64, as the starter’s metric code does for distances. Every nearest-centroid decision uses Metric::distance, including dot and cosine configurations.

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 result must contain every dataset row exactly once. An orphaned row is invisible to every query; a duplicate can occupy the result heap twice and crowd out a distinct row. Both copies use the same immutable vector and metric, so they do not acquire different exact distances.

The final rebuild matters because the preceding assignment can describe centroid positions from the previous round. Placing a row in the wrong list does not change exhaustive results when that row still appears exactly once, but it can reduce recall when a query probes only some lists.

Recover Empty and Zero-Mean Clusters

An empty cluster has no mean. Re-seed it from the row farthest from its nearest current centroid; do not divide by zero or silently remove a partition.

Cosine adds a different boundary: nonzero assigned vectors can average to the zero vector. Normalize every nonzero cosine centroid after the mean. If its norm is zero, replace it with an assigned dataset row, which has already passed Day 1’s nonzero-norm validation.

Prediction: The mean of [1, 0] and [-1, 0] is [0, 0]. What would cosine distance do with that centroid if you kept it? Which already validated row can safely replace it?

Run the deterministic-build and zero-mean cases:

cargo test -p vector-db-from-scratch-core-starter --test indexes day_02_ivf_build_is_seeded
cargo test -p vector-db-from-scratch-core-starter --test indexes day_02_ivf_cosine_recovers_from_a_zero_mean_cluster

Checkpoint 4: Probe Lists at Query Time

Implement search_with_probes:

1. validate the query and 1 <= probes <= partitions;
2. compute one Neighbor per centroid and sort centroids nearest-first;
3. visit row offsets from the first probes lists;
4. score those dataset rows with the original metric; and
5. feed every candidate into the existing TopK and return nearest-first.

Reject an invalid probe count before scanning any list. A request above the partition count is an error, not permission to visit a uniquely ranked partition more than once.

Centroid assignment, centroid ranking, and candidate scoring must all use the same metric. Mixing metrics produces a result set ordered by a criterion the probe loop never optimized. Do not return a separate top-k from each list: the SQL query asks for the best k across the union of candidates.

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 those candidates. Increasing probes does more candidate work, but it is less likely to miss a true neighbor:

Suppose ranked list IDs are [2, 0, 1] and their sizes are [10, 40, 5]. With probes = 1, search reads the five rows in list 2. With probes = 2, it reads those five plus the ten rows in list 0. k controls retained output; probes controls which candidates can enter it.

Approximate and exact recall runs must use identical data, queries, metric, and k. Changing any of these between runs makes the recall number meaningless.

The decisive boundary is to probe every partition. IVFFlat then visits every dataset row and must produce the same complete ordered result as FlatIndex, including tie order:

cargo test -p vector-db-from-scratch-core-starter --test indexes day_02_ivf_scanning_every_partition_matches_exact_search

If this fails, inspect list completeness, metric choice, heap retention, and final sorting. With every list open, approximation is no longer an explanation.

Checkpoint 5: Put IVFFlat behind the Same SQL

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

cargo test -p vector-db-from-scratch-datafusion-starter --test sqllogictest day_02_ivfflat_sql

The SQL text and the matcher you implemented on Day 1 are unchanged. DataFusion passes LIMIT 5 through Day 1’s with_fetch. VectorIndexScanExec calls IvfFlatIndex::search, which uses the configured probes; the generic bounded sort remains responsible for final SQL ordering. Unsupported query shapes still use the exact DataSourceExec path.

The test uses all three partitions, so its five returned rows must match exact search. This is an integration check, not a claim that a smaller probe count always returns the same rows.

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 issues one cosine top-k over the same five-row table through a Flat attachment and then 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. The product contract did not change; the candidate-selection implementation did. Smaller probe counts expose the recall/work tradeoff you reasoned about above, while 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 x test-day 2
cargo x test-through 2

After the five Day 2 core tests, Day 2 SQLLogicTest, and product example pass, choose one concrete build and query and explain:

• why the configuration is rejected before training;
• why list membership must be rebuilt after the final centroid update;
• how a dataset row flows from assignment to a probed list to TopK;
• why empty and zero-mean cosine clusters need different recovery logic;
• why probing every list is an exactness test; and
• how Day 1’s optimizer rule reaches a new index without changing its SQL safety contract;
• which same-implementation properties a seed fixes without fixing the reference implementation’s centroid identities.

Keep this checkpoint focused on in-memory IVFFlat. Persistent postings, online centroid retraining, product quantization, cross-index timing, and reproducible latency targets remain outside Day 2.

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.

Start from the Product You Already Have

Day 2 ended with one five-row table and one SQL query running through IVFFlat. Run it again from the repository root:

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)

Day 3 keeps that query and fixture fixed. What changes is how the core index proposes candidate row offsets: IVFFlat probes centroid lists, while navigable small world (NSW) search follows edges in a proximity graph. DataFusion’s bounded SortExec still owns final SQL ordering.

The cumulative starter already contains these two files:

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

You own four TODOs:

1. search_layer;
2. prune_neighbors;
3. NswIndex::try_new; and
4. NswIndex::search_with_ef.

The same starter also declares greedy_search, HNSW, and IVF-PQ surfaces for later days. Leave those future TODOs alone. The supplied crate-internal tests let you finish one NSW boundary at a time without making graph helpers public.

Checkpoint 1: Search One Supplied Layer

An NSW graph has no centroid that points directly at the query. Search begins from one or more entry points and explores their connected neighbors.

For top-k search, keep three pieces of state:

• C, a min-heap whose nearest candidate is the next vertex to expand;
• W, a bounded max-heap whose top is the worst retained result; and
• visited, a set that prevents a row from being measured or expanded twice.

Seed all three from the valid, unique entry points.

Pop the nearest item from C. For each unseen neighbor, compute its distance once. If it can improve W, add it to both frontiers and trim W back to the search width.

A candidate may add nothing because all its neighbors were already visited. Other pending candidates can still continue the search.

Multiple entry points can reach different graph regions, but no heap width can cross a disconnected component without an entry point or edge into it.

W retains only the nearest vertices found within the current width.

When W is full and the nearest pending candidate is strictly worse than W.worst, this bounded NSW search stops.

The strict comparison matters. A candidate equal to W.worst must still be expanded. This stopping rule limits work; it does not prove that every unseen path is worse, because a worse intermediate vertex could lead to a closer vertex later.

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; return no rows when none are allowed. Ignore duplicate or out-of-range entry points. During insertion, allowed_rows = r means only previous rows 0..r exist.

Run only this checkpoint’s supplied test:

cargo test -p vector-db-from-scratch-core-starter \
  graph_tests::day_03_search_layer_respects_bounds_and_expands_equal_frontier -- --exact

Before the implementation it reaches the Day 3 traversal TODO. Afterward it checks allowed rows, disconnected components, duplicate and invalid entry points, nearest-first uniqueness, and the strict-worse stopping boundary.

Prediction: If every entry point is in one of two disconnected components, why can increasing ef not return a row from the other component?

Checkpoint 2: Keep a Bounded Neighbor List

Rows are inserted one at a time. Search the graph built so far with width ef_construction, then choose at most max_connections neighbors for the new row.

Adding reciprocal edges can push an existing endpoint over the degree cap.

Implement prune_neighbors in graph.rs. Deduplicate the supplied neighbor rows, order them by distance from the owner, break distance ties by row offset, and truncate to max_connections.

Run the crate-internal helper test:

cargo test -p vector-db-from-scratch-core-starter \
  graph_tests::day_03_prune_neighbors_is_deterministic_and_bounded -- --exact

Its direct fixture is self-free and isolates deduplication, ordering, tie-breaking, and the cap. The graph builder—not this synthetic helper input—owns the invariant that no adjacency list contains its own row.

Checkpoint 3: Build a Reciprocal Graph

Implement NswIndex::try_new in nsw.rs.

Validate stored vectors for the selected metric before building. The graph budget must satisfy:

• max_connections > 0;
• ef_construction >= max_connections; and
• ef_search > 0.

Add the first row without searching. For each later row r, search only 0..r, add reciprocal edges to the selected neighbors, and prune every affected endpoint. If pruning removes a -> b, also remove b -> a.

The completed graph must be deterministic, duplicate-free, self-free, reciprocal, and within the configured degree cap. Run its focused construction test:

cargo test -p vector-db-from-scratch-core-starter --test indexes \
  day_03_nsw_rejects_invalid_build_configuration_and_builds_a_bounded_reciprocal_graph -- --exact

This test owns stored-vector and configuration validation plus the built-graph invariants. It does not require search_with_ef.

Checkpoint 4: Query with a Width Budget

Implement NswIndex::search_with_ef.

Validate the query for dimension, finite values, and the selected metric. Reject a zero search width. Search from the graph entry point with ef_search.max(k), return at most k rows, and keep them nearest-first.

The .max(k) floor separates the requested result count from the caller’s exploration hint: asking for five rows with ef_search = 1 still needs a result frontier that can hold five rows.

Run the query test:

cargo test -p vector-db-from-scratch-core-starter --test indexes \
  day_03_nsw_search_validates_widens_and_matches_exact_on_connected_fixture -- --exact

It checks query validation, zero width, the ef_search.max(k) floor, ordering, and one connected high-width fixture that matches FlatIndex. That equality is an observation about this fixture, not a claim that NSW is exact for arbitrary data, widths, or disconnected graphs.

Return to the Same SQL Product

Now run the supplied, TODO-free 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)

The example demonstrates the Day 2 → Day 3 handoff through the existing attachment, matcher, source-row lookup, and final sort. Equal rows here do not establish general recall, work, or performance.

Keep the separate five-result SQL fixture green:

cargo test -p vector-db-from-scratch-datafusion-starter --test sqllogictest day_03_nsw_sql -- --exact

That SQLLogicTest uses a different eight-row fixture and LIMIT 5. It verifies index=nsw, the supplied final sort, and its own five expected rows. Unsupported SQL shapes continue to use the supplied exact path.

Day 3 Review

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

cargo x test-day 3
cargo x test-through 3

Choose one insertion and one query and explain:

• why C and W need opposite heap orderings;
• why the stopping comparison is strict;
• how a rejected edge is removed from both endpoints;
• why ef_search.max(k) is necessary; and
• why a disconnected component remains unreachable without an entry point or edge into it.

Keep Day 3 to one immutable graph layer. Hierarchy, deletion, concurrent mutation, persistence, filtered pushdown, general DDL/catalog behavior, benchmarking, and neighbor-diversification heuristics belong outside 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 one five-row table and one cosine-distance query running through IVFFlat and NSW. From the repository root, run that supplied comparison again:

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)

Day 4 keeps the SQL matcher, source-row lookup, and final SortExec fixed. You will change the core candidate path: instead of starting every query in one graph that contains every row, HNSW first makes coarse moves through sparse upper layers and then reuses Day 3’s bounded search in the all-row layer-zero graph.

Prediction: In a before-and-after SQL comparison whose table and query are unchanged, which plan field should change? Why must the returned rows still satisfy the same SQL ordering contract even though the route proposing them changes?

The cumulative starter leaves exactly 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 metric ordering, and the DataFusion boundary. try_new is one complete build operation: level assignment and graph construction share the same insertion loop, so you will implement and check them together.

Checkpoint 1: Route Through One Upper Layer

Layer zero contains every vector. Each higher layer contains a progressively smaller subset, and a row promoted to level L belongs to every layer from zero through L.

A query begins at the global entry point in the highest layer. Within one upper layer, greedy_search repeatedly moves to the best allowed neighbor only when that neighbor strictly improves the public (distance, row) order. Equal geometric distance can therefore move to a lower row offset, but every move still decreases the total order and the walk terminates.

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. Respect allowed_rows: during construction, row r may route only through rows 0..r; during a query, every stored row is allowed. Do not turn this into a beam search. Upper layers choose one coarse handoff, while layer zero will retain multiple candidates for top-k output.

Run the focused helper test:

cargo test -p vector-db-from-scratch-core-starter --lib \
  graph_tests::day_04_greedy_search_moves_on_public_tie_order_and_respects_bounds -- --exact

Its fixture begins at row 2. An equal-distance row 1 wins by row offset, while a closer row 3 is first excluded and then admitted by changing allowed_rows. A no-op walk or a distance-only tie comparison fails at this checkpoint.

Checkpoint 2: Build the Seeded Nested Graph

Implement the complete HnswIndex::try_new unit in hnsw.rs. Validate stored vectors for the selected metric and reject an invalid graph budget:

• max_connections must be greater than zero;
• ef_construction must be at least max_connections;
• ef_search must be greater than zero; and
• max_level must be greater than zero.

For each dataset row, use the supplied deterministic generator to flip a seeded coin until the first failure or max_level. A sampled level of one places the row in layers one and zero, but not layer two.

As each row arrives, extend the adjacency storage of every existing layer and create missing layers through the sampled level. Rows that do not belong to a layer keep an empty adjacency list there. That shape makes these two facts directly inspectable:

• levels[r] is the highest layer containing row r; and
• membership is nested: appearing in an upper layer requires appearing in every lower layer.

The first row needs no search. Store it in every included layer and make it the entry point. For each later row, start from the current global entry point. Greedily descend through layers above the new row’s sampled level. At every layer the new row joins, reuse Day 3’s search_layer with ef_construction, connect the nearest max_connections candidates, and prune reciprocal edges back to the cap.

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

Every layer must remain deterministic, degree-bounded, duplicate-free, self-free, and reciprocal. Keep core row values as dataset ordinals; the supplied DataFusion adapter maps those ordinals through its snapshot row-ID boundary later.

Run the construction test:

cargo test -p vector-db-from-scratch-core-starter --test indexes \
  day_04_hnsw_rejects_invalid_configuration_and_builds_seeded_nested_layers -- --exact

It checks invalid budgets, same-implementation repeatability, nested membership, degree caps, and the absence of duplicate or self-edges. It also checks every retained edge at both endpoints. A correct deterministic implementation may consume randomness differently from the reference and therefore produce another valid level sequence and top layer; the tests do not require the reference implementation’s prefix. Forcing every sampled level to zero or injecting a self-edge still fails here rather than being hidden by a later recall result.

Prediction: If a deterministic level sampler changes its RNG consumption order, which graph invariants and repeated build observations must remain true even though the sampled level prefix may change?

Checkpoint 3: Search from the Top Layer

Implement HnswIndex::search_with_ef. Validate the query for dimension, finite values, and the selected metric, and reject a zero explicit search width.

Begin at the stored global entry point. Call greedy_search once per upper layer, from the top layer down through layer one, carrying the returned row into the next layer. At layer zero, call Day 3’s search_layer with width ef_search.max(k), then truncate the nearest-first result to k.

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 the requested result count from the exploration hint. A caller asking for five rows with ef_search = 1 still needs a result frontier capable of holding five rows.

Run the query test:

cargo test -p vector-db-from-scratch-core-starter --test indexes \
  day_04_hnsw_search_validates_widens_and_recovers_neighbors -- --exact

It checks query validation, zero width, result ordering, the ef_search.max(k) floor, and one connected high-width fixture. Matching FlatIndex on that fixture is a bounded observation, not a promise that HNSW is exact for arbitrary datasets or search budgets.

Return to the SQL Product

First confirm that the unchanged Day 1 adapter can select the completed HNSW index:

cargo test -p vector-db-from-scratch-datafusion-starter --test sql day_04_hnsw_is_visible_in_explain

Then run the self-contained Day 4 SQLLogicTest:

cargo test -p vector-db-from-scratch-datafusion-starter --test sqllogictest day_04_hnsw_sql -- --exact

The fixture creates and populates its own table, checks the exact plan, attaches an HNSW index, and checks the changed plan. Its indexed plan contains:

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

and its five-row Euclidean query returns:

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

This small comparison shows the product handoff, not a performance or general-recall result. HNSW proposes core dataset ordinals; the supplied adapter resolves them to source rows, and the supplied SortExec still owns final SQL ordering. Unsupported SQL shapes continue to use the exact scan.

The fixture uses Euclidean distance and LIMIT 5; it verifies index=hnsw, the supplied final sort, and the expected rows without depending on mutable interactive-shell state.

Check the Course Through Day 4

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

cargo x test-day 4
cargo x test-through 4

The runner selects only the tests assigned through HNSW, so unfinished Day 5 IVF-PQ work cannot turn this Day 4 gate red.

Day 4 Review

Choose one insertion and one query and explain:

• why a promoted row must also belong to every lower layer;
• why the seed changes graph structure but must reproduce the same structure when repeated;
• why construction carries one entry point downward before connecting the new row;
• why query-time upper layers use greedy routing while layer zero keeps a bounded frontier;
• when the global entry point changes; and
• why equal rows in the supplied SQL comparison say nothing about general recall or speed.

The Day 4 index is immutable and in memory. Deletion, concurrent mutation, persistence, production neighbor-diversification heuristics, and adaptive search budgets would change the learner contract rather than complete 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.

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 avoids comparing a query with every row, but it still reads every component of every vector in the probed lists. Product quantization replaces that candidate-scoring representation with a short sequence of learned codeword IDs.

Day 5 follows the product-quantization design introduced by Jégou, Douze, and Schmid. It combines a coarse IVF partition with product quantization of residuals, the structure commonly called IVFADC or IVF-PQ. The Faiss index guide uses the same coarse-quantizer-plus-residual-PQ decomposition.

Split Residuals into Subvectors

Suppose a residual has eight dimensions. Split it into two four-dimensional subvectors:

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

Train a separate codebook for each subvector position. If each codebook has four codewords, encoding chooses one ID from each side:

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

The course stores each ID as a u8, so an encoded row uses one byte per subquantizer. Shared codebooks add a fixed cost rather than a full vector for every row.

IVF already assigns every vector x to a coarse centroid c. Encode the residual instead of the original vector:

r = x - c

Keep the two learned structures distinct:

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

Equal data and configuration must produce equal coarse centroids, PQ codebooks, list sizes, codes, and search results.

Score Codes, then Rerank

For each probed list, subtract its coarse centroid from the query and build one squared-Euclidean lookup table per subquantizer:

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

A row’s approximate score is a sum of table lookups:

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

The query stays full precision while stored residuals are quantized, so this is asymmetric distance computation. Keep the best min(max(rerank, k), rows) row offsets under the approximate score, then compute exact Euclidean distance from the original dataset and select the final k:

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

The base Dataset remains available for exact reranking. Therefore encoded_bytes() plus codebook_bytes() describes the PQ search representation, not total index or process memory. It excludes retained full vectors, coarse centroids, row IDs, list allocations, and other overhead.

Prediction: With four subquantizers and sixteen codewords per codebook, how many table entries does one probed list need? How many additions score one encoded row after the tables exist?

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. Keep those public APIs, existing indexes, and tests unchanged.

All commands on this page exercise the cumulative starter workspace. Complete Days 1–4 first; an untouched starter stops at an earlier todo!() before it reaches Day 5.

IvfPqConfig separates the main budgets:

The index accepts only Metric::Euclidean. Cosine and inner-product quantization need additional representation and scoring choices; returning plausible numbers would not establish a consistent metric contract.

Checkpoint 1: Validate the Layout and Build Coarse Lists

Implement IvfPqIndex::try_new. Validate before training:

• 1 <= probes <= partitions <= rows and iterations > 0;
• subquantizers > 0 and the dimension divides evenly into that many slices;
• 2 <= codebook_size <= min(256, rows);
• rerank > 0; and
• the metric is Euclidean.

Build the coarse partition with the same partitions, probes, iterations, and seed. Assign every row against the final centroids, then compute row - centroid. Rebuilding membership after the final centroid update preserves the complete one-list-per-row invariant from Day 2.

Run the focused layout boundary:

cargo test -p vector-db-from-scratch-core-starter --test indexes day_05_ivf_pq_validates_its_euclidean_code_layout

Checkpoint 2: Train and Encode Residual Codebooks

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.

Keep a codeword unchanged when its cluster is empty. Reuse the deterministic RNG from src/search.rs, deriving a different deterministic seed for each subquantizer. Then encode every row with exactly one valid u8 code per subquantizer.

cargo test -p vector-db-from-scratch-core-starter --test indexes day_05_ivf_pq_build_is_seeded_and_codes_each_row

The test checks deterministic training, complete list membership, code layout, and byte accounting.

Checkpoint 3: Scan Codes and Rerank

Implement search_with_probes:

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.

Keep coarse selection, lookup scores, and exact rerank distances in f64. At the public Neighbor boundary, retain only finite distances representable as f32, convert them, and apply the public tie-break. Row identity must remain attached to each code through both candidate stages. If discarding an unrepresentable exact distance would leave fewer than min(k, rows) results, return an error instead of silently returning an incomplete result.

Probe every list and rerank every row as an exactness boundary:

cargo test -p vector-db-from-scratch-core-starter --test indexes day_05_ivf_pq_full_scan_and_rerank_matches_exact_search

Then run the complete IVF-PQ core group:

cargo test -p vector-db-from-scratch-core-starter --test indexes day_05_ivf_pq_

These cases also cover large finite values, representability, and public ordering. Finally, confirm the unchanged Day 1 adapter can select the completed Euclidean index:

cargo test -p vector-db-from-scratch-datafusion-starter --test sql day_05_ivf_pq_is_visible_in_explain

The physical plan names index=ivf_pq while retaining the same conservative matcher and 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.

Do not describe the ratio between full-precision vector bytes and code-plus-codebook bytes as total-memory compression. The final day prints the exact accounting beside the shared five-index benchmark, where its scope can be read with the workload and search configuration.

Return to the SQL Product

Run the self-contained Day 5 SQLLogicTest:

cargo test -p vector-db-from-scratch-datafusion-starter --test sqllogictest day_05_ivf_pq_sql -- --exact

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

This fixture verifies one deterministic handoff from an exact scan to the supplied IVF-PQ SQL adapter. It does not establish external-corpus recall, latency, memory use, or general exactness.

Day 5 Review

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

cargo x test-day 5
cargo x test-through 5

After the IVF-PQ core tests and DataFusion plan check pass, explain:

• why IVF centroids and PQ codewords solve different parts of search;
• why stored and query residuals use the selected list’s same coarse centroid;
• how asymmetric lookup tables avoid reconstructing every candidate;
• why reranking still needs the original vectors;
• which bytes the search-representation accounting includes and excludes; and
• why a compact representation alone does not establish a latency or recall ranking.

Keep Day 5 focused on an executable IVF-PQ mental model. Bit-packed codes, cosine or inner-product support, optimized product quantization, SIMD table scans, persistent layouts, training samples separate from indexed rows, and removing full vectors from memory remain outside its scope.

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. Finish with one release-mode benchmark that compares Flat, IVFFlat, NSW, HNSW, and IVF-PQ on the external SIFT1M corpus under the same Euclidean queries and k = 100 contract.

A search-time number is not useful by itself. An approximate index can look fast by returning the wrong neighbors, while recall from another workload cannot explain the latency you measured. Day 6 therefore prints timing and result quality from the same run.

The benchmark has two explicit modes. The default full run uses all one million SIFT base vectors, all 10,000 queries, and the supplied first exact neighbor. The smaller --smoke run follows the same five-index code path but selects 10,000 base rows and 100 queries, then recomputes exact truth over that subset. It is quick external-data feedback, not a full parity result.

Start from the Completed Indexes

Your Day 5 starter already contains the five index implementations. Before opening the benchmark, keep their product paths green from the repository root:

cargo test -p vector-db-from-scratch-datafusion-starter --test sqllogictest day_01_table_and_optimizer_sql -- --exact
cargo test -p vector-db-from-scratch-datafusion-starter --test sqllogictest day_02_ivfflat_sql -- --exact
cargo test -p vector-db-from-scratch-datafusion-starter --test sqllogictest day_03_nsw_sql -- --exact
cargo test -p vector-db-from-scratch-datafusion-starter --test sqllogictest day_04_hnsw_sql -- --exact
cargo test -p vector-db-from-scratch-datafusion-starter --test sqllogictest day_05_ivf_pq_sql -- --exact

Now open:

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

The supplied vector-db-from-scratch-benchmark-support crate owns command-line parsing, SIFT file validation, the full and smoke mode sizes, cyclic warm-up and timing, rank-recall calculation, and nearest-rank percentile selection. The example already owns the five configurations, report layout, result validation, and IVF-PQ accounting. You complete exactly four Day 6 ownership points:

1. construct NSW;
2. construct HNSW;
3. construct IVF-PQ; and
4. call the supplied percentile helper for p50 and p99.

Run the support tests before changing the example:

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

They use tiny little-endian fixtures and deliberately corrupted inputs, so they need no external download. The raw starter’s example test is expected to stop at a Day 6 todo!() until you finish both checkpoints below:

cargo test -p vector-db-from-scratch-core-starter --example recall

Acquire and Validate SIFT1M

Obtain SIFT1M from the TexMex ANN corpus and follow the terms published there. The course does not redistribute or download the corpus, and it does not publish an archive checksum or a separate dataset license claim.

Pass a directory that directly contains these three extracted files:

The loader scans and validates the complete files before the first index build in both modes. It checks each little-endian dimension header, exact byte and record 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 public invocation is deliberately narrow:

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

There is no no-argument synthetic fallback, arbitrary row limit, environment-variable run mode, or interactive prompt. Ignored integration tests alone use SIFT1M_DIR to find a developer’s local corpus.

Keep the Two Modes Distinct

The full label records parity with the BusTub course’s corpus, Euclidean ordering, k = 100, and first-neighbor rank recall. It does not claim identical index parameters, storage, floating-point paths, or timings across implementations.

Prediction: Smoke mode runs the same index implementations and report code. Why can its 10,000-row, 100-query result still not stand in for the full SIFT1M parity run?

Freeze the Five Configurations

Do not tune one index while leaving the others at the course defaults:

These are fixed Rust course configurations, not a universal tuning recommendation or a promise of configuration parity with the deprecated C++ implementation.

Checkpoint 1: Construct the Remaining Indexes

Implement build_nsw, build_hnsw, and build_ivf_pq with the supplied dataset, Euclidean metric, and configuration. Return constructor errors instead of substituting another configuration or index.

The surrounding code clones the immutable Dataset before each build and creates the metric and configuration before starting the timer. Keep that boundary: each build_s measurement contains only the corresponding index constructor. File I/O, validation, query preparation, truth selection, dataset cloning, and configuration construction are not build time.

Before moving to reporting, rerun the invariant gate that permits more than one deterministic RNG trajectory:

cargo test -p vector-db-from-scratch-core-starter --test indexes \
  day_06_randomized_indexes_preserve_invariants_across_seed_trajectories -- --exact

A seed promises repeatability within your implementation. It does not require your IVFFlat centroids or HNSW level sequence to equal the reference implementation’s internal samples.

Checkpoint 2: Select p50 and p99

Implement report_percentiles by calling the supplied percentile helper on the sorted, nonempty duration slice. The helper uses nearest rank. For percentage p and n samples, it selects this zero-based position, clamped to the final sample:

ceil(p / 100 * n) - 1

Do not replace it with interpolation or a floor fraction of n - 1; that would change the report contract. Once all four ownership points are complete, run the five behavioral example tests:

cargo test -p vector-db-from-scratch-core-starter --example recall day_06_

This gate pins the completed constructors and percentile selection, fixed inventory and configurations, full-versus-smoke truth selection, result validation, rank-prefix averaging, report order, and full-mode IVF-PQ accounting.

Read the Supplied Measurement Loop

The support crate warms the first min(20, query_count) queries, then times every selected query. Warm-up and timed passes both rotate the five indexes with:

(query_ordinal + offset) % 5

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

Prediction: Which of parsing, index construction, result validation, recall calculation, and printing belong outside the search timer? Why would a faster row be uninterpretable if its recall fields were missing?

Interpret First-neighbor Rank Recall

For each query, the benchmark chooses one exact nearest-neighbor row ID. It then asks whether that ID appears within the first 1, 10, and 100 returned rows:

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

Each answer is binary for one query, and the report averages it across all selected queries. This is not set recall over the exact top 100.

Prediction: How does “the exact first neighbor appears within the first 10 results” differ from “10 of the exact top 100 neighbors were recovered”?

Before recall is computed, every result must contain min(k, base_rows) distinct, in-range rows in public nearest-first Neighbor order, with finite distances. The summary also requires:

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

Flat must report 1.0 at all three ranks.

Prediction: Why must widening the inspected prefix make rank recall monotonic? Name one result-order, duplicate-row, or parser defect that could otherwise make the report untrustworthy.

Run Smoke, Then Full SIFT1M

From the repository root, run the completed starter in release mode with an explicit corpus directory:

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 against the completed reference 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; a practical starting point is at least 8 GiB of free memory and roughly 1 GiB of free disk beyond the extracted corpus and build outputs. These are planning guidelines, not benchmark results or pass/fail thresholds.

For one narrower external-data check, the supplied ignored tests expose each index separately. For example:

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

The analogous test names are day_06_sift_flat_smoke, day_06_sift_ivf_flat_smoke, day_06_sift_nsw_smoke, and day_06_sift_hnsw_smoke. These tests use the fixed smoke subset. Flat must match exact rank recall; approximate indexes must return ordered unique rows, monotonic rank recall, same-implementation repeatability where seeded, and a broad R@100 >= 0.05 floor. That floor is a bug detector, not a production-quality target.

Read the Report without Inventing Results

Every 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-first-neighbor|recomputed-flat-selected-base}

It then prints five rows in flat, ivf_flat, nsw, hnsw, ivf_pq order:

{name}: config={stable-config}, build_s={:.3}, search_s={:.3}, qps={:.1}, r@1={:.4}, r@10={:.4}, r@100={:.4}, p50_ms={:.3}, p99_ms={:.3}

The final line isolates IVF-PQ search-representation accounting:

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

In full mode, 4,000,000 code bytes plus 8,192 codebook bytes make a 4,008,192-byte search representation. The comparison against 512,000,000 full-vector component bytes prints 127.7x. This is not resident memory or total-index compression: it excludes retained vectors used for reranking, centroids, row IDs, list and graph containers, allocator overhead, and the other four live indexes.

Record observed timings and rank recall only from a run you actually performed, together with its mode, machine, and fixed configuration. Do not infer a universal fastest index, quality ranking, or latency threshold from this run.

Day 6 Review

Run the Day 6 focused gate, then the complete cumulative course:

cargo x test-day 6
cargo x test-through 6

These commands compile but do not execute the ignored external-corpus SIFT1M tests. Use the explicit SIFT1M_DIR=... --ignored --exact command above when you have acquired the corpus.

After the release run you chose completes, explain:

• why all indexes must share data, queries, Euclidean metric, and k = 100;
• why full mode uses the supplied first neighbor while smoke mode recomputes truth over its selected base;
• why a seeded build must repeat within one implementation without copying reference centroids or levels;
• what belongs inside and outside constructor and search timers;
• how first-neighbor rank recall differs from top-100 set recall;
• why R@1 <= R@10 <= R@100 must hold;
• why smoke output remains non-parity; and
• which bytes the IVF-PQ accounting includes and excludes.

Parameter sweeps, resident-memory measurement, multiple benchmark processes, and confidence intervals are useful next steps. They are not evidence supplied by this single-process course benchmark.

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 (WIP)

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.