Build Vector Search Inside a SQL Database

Write You a Vector Database 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 four Rust chapters 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.

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 and graph indexes trade build cost, memory, 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. Chapter 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 available chapter pairs the book with starter code, focused tests, and a separate reference solution.

Each implementation chapter 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.

Chapter 1 makes the table and optimizer rule runnable. Chapter 2 compares IVFFlat with exact search, Chapter 3 follows graph edges with NSW, and Chapter 4 adds sparse HNSW layers. Every approximate index uses the same collection API and SQL query, so you can inspect the physical plan and results without changing the optimizer contract.

Community

Join skyzh’s Discord server to study with the write-you-a-vector-db 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/write-you-a-vector-db.
write-you-a-vector-db © 2024-2026 by Alex Chi Z. All Rights Reserved.

Build Vector Search in Rust

Across four chapters, you will connect an in-memory vector 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, and add HNSW hierarchy. Every chapter ends with a runnable SQL query, so you can inspect how the physical plan changes as the index becomes more capable.

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

Your first SQL query uses DataFusion’s vector distance expressions, bounded sort, and LIMIT to return an exact result. The starter includes a FlatIndex, which checks every vector, while you connect the table to the query planner. You will then add IVFFlat as your own candidate selector behind the same query.

Choose Your Workspace

The Cargo workspace under rust/ separates starter and reference trees:

vector-starter/
  core/                      dataset, IVFFlat, NSW, and HNSW TODOs
  datafusion/                Chapter 1 Arrow table and optimizer-rule TODOs
vector/
  core/                      completed core reference
  datafusion/                completed DataFusion reference

Work in vector-starter/ and implement its TODOs in chapter order. The vector/ tree contains completed references; keep it 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:

cd rust
cargo check -p vector-core-starter
cargo check -p vector-datafusion-starter

The focused tests initially stop at todo! calls. Each chapter names the exact tests that should pass before you move on.

One Query, Two Plans

Before index matching, the query is exact:

SortExec: TopK(fetch=10), ...
  VectorScanExec: rows=..., fetch=None

VectorScanExec emits Arrow rows. DataFusion evaluates the distance function for every row and uses its own bounded sort to produce the nearest ten.

In Chapter 1, you implement ExecutionPlan::try_pushdown_sort. It accepts only one compatible distance ordering over the embedding column with a literal query vector. with_fetch receives LIMIT k, and the matched scan asks the selected index for k candidate row offsets:

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 in Chapter 1. Later chapters 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, 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

SQL + DataFusion optimizer --> VectorTable / VectorScanExec --> VectorIndex
                                                                  |
                                                        exact FlatIndex
                                                                  |
                                                       your IvfFlatIndex
                                                                  |
                                                          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 each index chapter two useful views of the same checkpoint: small Rust tests isolate the algorithm, while an SQLLogicTest shows that the Chapter 1 optimizer can reach it.

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: core row offset r maps to Arrow batch row r, which carries the corresponding external ID and payload.
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

Chapter 1 gives you an exact end-to-end query whose rows and physical plan you can inspect. Chapters 2–4 keep that SQL interface and safety rule in place while changing how candidate rows are selected.

After Chapter 4, 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; and
• how reciprocal pruning preserves a bounded graph;
• why HNSW uses greedy upper layers and a layer-zero beam; and
• how seeded promotion makes comparisons reproducible.

Scope

These chapters use an immutable in-memory collection. Online updates or deletes, index persistence, crash recovery, concurrent mutation, filtered ANN, quantization, GPU kernels, distributed execution, DDL, and a network service remain outside this implementation.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/write-you-a-vector-db.
write-you-a-vector-db © 2024-2026 by Alex Chi Z. All Rights Reserved.

Build an In-Memory Vector Table and Match Its Index

Chapter 1

Start from the two *-starter crates. Finish with an exact SQL top-k query, an Arrow-backed table, and a safe DataFusion optimizer rule that can select a vector index.

Your first query asks for the three rows closest to one query vector:

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

Start from the exact plan. Scan every row, compute its distance to the query, and keep the nearest three with a bounded top-k sort:

SortExec: TopK(fetch=3), ...
  VectorScanExec: rows=..., fetch=None

This plan is correct for every valid query shape because it does not skip any rows. A vector index can avoid scanning the whole collection, but only when the query and the index describe the same ranking. The matcher must check the distance function, embedding column, literal query vector, sort direction, dimension, and LIMIT; a mismatch keeps the exact plan.

After your rule recognizes a compatible index, the physical plan becomes:

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

With FlatIndex, you can confirm both the exact result and the matched physical plan. In Chapter 2, index=ivf_flat will appear behind the same rule.

Build the Exact Path and Matcher in Rust

You will modify:

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

Metric math, a FlatIndex that checks every vector, Arrow result execution, and all tests are ready for you to use. You will build the storage and extension boundary around them: validated vectors, an Arrow-backed table, a physical scan, and a rule that recognizes one safe top-k shape. Do not modify public APIs or tests.

Invariants

1. I1 — Valid vectors: a dataset is non-empty, has nonzero fixed dimension, and contains only finite f32 values.
2. I2 — Consistent row identity: each external id is unique, while a core row offset identifies the same row in the dataset and Arrow batch.
3. I3 — Faithful Arrow shape: the table schema is id: UInt64, payload: Utf8, and embedding: FixedSizeList<Float32> with the dataset dimension.
4. I4 — Safe match: an index scan is selected only for one supported distance expression over embedding, a literal query vector, a compatible metric and direction, and a valid dimension.
5. I5 — Exact fallback: filters, multiple sort keys, non-literal vectors, wrong metrics, wrong directions, and invalid query vectors remain on VectorScanExec plus DataFusion’s exact sort.
6. I6 — SQL owns ordering: unless the vector scan returns rows in the requested order, DataFusion retains its bounded sort after the index selects candidates.

Checkpoint 1: Validate the In-Memory Dataset

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

Dataset::try_new reads the first row to establish 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>]>; later exact and approximate indexes can cheaply share immutable data.

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 rather than panicking on input.

Prediction: For a two-dimensional dataset, should query [1.0] reach the DataFusion optimizer? It should be rejected at the vector boundary; allowing a mismatched literal into an index scan would make the plan claim a contract the index cannot satisfy.

Use the starter’s FlatIndex to exercise these checks:

cd rust
cargo test -p vector-core-starter --test indexes flat_search_is_deterministic_and_validates_queries
cargo test -p vector-core-starter --test indexes cosine_rejects_zero_norm_vectors

The exact-search and top-k helpers are already in place, so you can keep this checkpoint focused on the validation boundary.

Checkpoint 2: Turn Rows into an Arrow Table

Implement VectorTable::try_new in vector-starter/datafusion/src/lib.rs.

Preserve Identity

First reject duplicate external IDs with a HashSet. Then build Dataset from the embeddings in exactly the same row order. If Arrow batch row 4 and dataset row 4 refer to different inputs, an index will return the wrong payload even when its search result is otherwise correct.

Build the selected IndexConfig over that dataset. Chapter 1 passes IndexConfig::Flat; Chapter 2 will pass IndexConfig::IvfFlat without changing table construction.

Define the Schema

DataFusion executes over Arrow arrays. Construct this schema:

id         UInt64
payload    Utf8
embedding  FixedSizeList<Float32, dimension>

FixedSizeListArray stores all embedding components in one flat Float32Array; the list width tells Arrow where each row begins and ends. For two three-dimensional rows, the child values are laid out as:

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

Use i32::try_from(dataset.dimension()) for Arrow’s list width and return a plan error if the dimension cannot fit. Create UInt64Array, StringArray, and FixedSizeListArray, then assemble one RecordBatch with the schema.

Prediction: What breaks if you sort the IDs before creating their Arrow array but leave embeddings in insertion order? Trace the row offset returned by an index to the payload DataFusion would emit.

Run the duplicate-ID boundary test:

cargo test -p vector-datafusion-starter --test sql table_rejects_duplicate_ids

Checkpoint 3: Expose a TableProvider and Exact Scan

DataFusion asks a TableProvider for a physical plan through scan. Implement the TODO in that method by creating the existing VectorScanExec in ScanMode::Full.

Pass through:

• the Arrow batch and selected core index;
• DataFusion’s requested projection and limit;
• the session’s vector_search.ordered option; and
• no ordering yet, because the initial scan has not accepted a sort.

The executor uses project_schema to preserve the requested column order, take to build result arrays from row offsets, and MemoryStream to emit one batch. In full mode it returns ordinary table rows. DataFusion evaluates the distance function and exact SortExec above that scan.

At this point, DataFusion can read your table and return exact top-k results. Run the query once and inspect how the scan, distance expression, and bounded sort fit together.

Checkpoint 4: Match One Safe Vector Ordering

Implement match_vector_order and try_pushdown_sort. DataFusion calls the latter while planning the physical query.

The matcher accepts only all of the following:

1. exactly one PhysicalSortExpr;
2. a supported scalar function: Euclidean array_distance/list_distance, cosine_distance, or inner_product/dot_product;
3. ascending order for Euclidean/cosine or descending order for dot product;
4. one Column and one Literal argument, allowing either argument order;
5. the column named embedding in the projected schema;
6. a literal vector that scalar_vector can convert to finite f32 values;
7. query dimension equal to the index dataset; and
8. a nonzero cosine query.

uncast and scalar_vector are already implemented. They remove harmless cast wrappers and decode list literals backed by integer, f32, or f64 Arrow arrays. Use them to build a conservative matching rule.

When matching fails, return SortOrderPushdownResult::Unsupported; DataFusion keeps the exact scan and sort. When it succeeds, clone the scan into ScanMode::Vector { query }, retain the requested ordering, and return SortOrderPushdownResult::Exact.

Prediction: A cosine index exists, but the query uses array_distance. Both functions accept the same vector shapes. Should the rule select the index? No—the metric changes ranking, so I4 requires exact fallback.

Run the positive and negative plan tests:

cargo test -p vector-datafusion-starter --test sql compatible_top_k_uses_vector_index_scan_and_keeps_sort
cargo test -p vector-datafusion-starter --test sql unsafe_sort_shapes_are_not_lowered
cargo test -p vector-datafusion-starter --test sql filter_keeps_datafusion_exact_fallback
cargo test -p vector-datafusion-starter --test sql dot_product_requires_descending_order

Checkpoint 5: Push LIMIT Without Stealing ORDER BY

Implement ExecutionPlan::with_fetch. DataFusion calls it after sort pushdown and passes LIMIT k.

DataFusion 54.1.0 does not expose supported SQL optimizer hints for choosing this plan. Register vector_search.ordered as a session option instead; DataFusion reads its value whenever it generates a new physical plan. This keeps the SQL query portable while making the executor’s ordering guarantee explicit for the session.

Clone the scan and store the new fetch value. When the session option is ordered=true, return the scan directly; this mode is valid only when the selected index returns rows in the accepted order. If no ordering or no fetch exists, also return the scan.

For the default ordered=false path, clear the scan’s claimed ordering property and wrap it in DataFusion’s SortExec::new(ordering, scan).with_fetch(Some(k)). The index chooses candidate row offsets; DataFusion still owns nearest-first SQL output.

This detail prevents a subtle optimizer bug. Claiming exact ordering while an approximate executor returns candidates in heap or traversal order can produce the right set in the wrong order.

Verify both modes and the end-to-end SQL file:

cargo test -p vector-datafusion-starter --test sql ordered_session_mode_allows_sort_elision
cargo test -p vector-datafusion-starter --test sqllogictest day1_table_and_optimizer_sql

The SQLLogicTest asserts physical operators as well as rows. Its filtered case must remain exact; setting ordered mode may remove the generic sort, and setting it back to false must restore that sort in the next generated plan.

Review Your Chapter 1 Result

After the two core tests, all sql.rs tests, and the Chapter 1 SQLLogicTest pass, choose one query and explain:

• how an input row becomes a dataset offset and three aligned Arrow arrays;
• where DataFusion performs exact distance, top-k, and final ordering;
• which comparison prevents a cosine query from using a Euclidean index;
• why a column-to-column distance expression stays exact; and
• how the same matching rule can later reach an approximate index without weakening exact fallback.

Keep your Chapter 1 changes in the two files named at the start. IVFFlat, filtered pushdown, DDL, and persistence remain outside this chapter.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/write-you-a-vector-db.
write-you-a-vector-db © 2024-2026 by Alex Chi Z. All Rights Reserved.

Restrict Search with IVFFlat

Chapter 2

Complete Build an In-Memory Vector Table and Match Its Index first. Finish with a seeded IVFFlat index, recall measured against exact search, and the same SQL top-k running through index=ivf_flat.

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.

How IVFFlat Works

IVFFlat builds clusters over vectors already stored in the collection. 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 a configured number of nearby lists instead of every vector.

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

At build time, k-means chooses 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.

After the last centroid update, assign every vector once more using the final centroids. The result is one list per centroid, and vectors in the same region will be searched together.

The red vector in the next diagram asks for its nearest neighbors. If lookup searches only 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 the number of probes does more work, but it is less likely to miss a true neighbor:

Build IVFFlat in Rust

Chapter 1 left you with an exact SQL path and a FlatIndex that checks every vector. You will now build IVFFlat to choose a smaller candidate set for the same query, then compare its result with exact search.

You will modify:

rust/vector-starter/core/src/ivf.rs
rust/vector-starter/core/src/search.rs        recall_at_k only

Keep the Chapter 1 DataFusion rule, public APIs, and tests unchanged. Your work stays in the two files above.

Invariants

1. I1 — Valid budget: 1 <= probes <= partitions <= rows, and iterations > 0.
2. I2 — Complete assignment: after training, every dataset row appears in exactly one inverted list.
3. I3 — Seeded build: equal data, metric, configuration, and seed produce equal centroids and list sizes.
4. I4 — Metric consistency: centroid assignment, centroid ranking, and candidate scoring all use the index metric.
5. I5 — Exact limit: searching all partitions produces the same ordered top-k as FlatIndex.
6. I6 — Comparable measurement: exact and approximate runs use the same data, queries, metric, and k.

Checkpoint 1: Measure Recall

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. Define recall as 1.0 when the exact denominator is zero; an empty request has missed nothing.

cd rust
cargo test -p vector-core-starter --test indexes recall_reports_result_overlap

Prediction: If exact search returns two rows because the dataset contains two rows while k = 10, should the denominator be 2 or 10? Relate your answer to what the approximate index could possibly return.

Checkpoint 2: Validate and Seed the Build

Implement IvfFlatIndex::try_new in ivf.rs. Start by validating the Chapter 2 configuration and calling dataset.validate_for_metric(metric).

The starter supplies DeterministicRng. Use it to shuffle row offsets, then copy the first partitions dataset rows as initial centroids. Sampling distinct offsets avoids beginning with the same row twice.

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

dataset rows:     0 1 2 3 4 5
seeded centroids: row 4, row 1
assignments:      unknown until the first assignment pass

The exact selected rows depend on the seed, but a second build with the same inputs must make the same choice.

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

The final rebuild establishes I2. Without it, list membership may describe centroid positions from the previous round.

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 another 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 Chapter 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 seeded and zero-mean cases:

cargo test -p vector-core-starter --test indexes ivf_build_is_seeded
cargo test -p vector-core-starter --test indexes 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 all candidates into the existing TopK and return nearest-first.

Do not return a separate top-k from each list. The SQL query asks for the best k across the union of candidates.

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.

A useful boundary test is to probe every partition. IVFFlat then visits every dataset row and must match exact search, including tie order:

cargo test -p vector-core-starter --test indexes ivf_scanning_every_partition_matches_exact_search

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

Checkpoint 5: Draw a Recall/Work Curve

The included example creates one deterministic dataset and query set, computes the exact results once with FlatIndex, and reports IVFFlat recall and latency:

cargo run --release -p vector-core-starter --example recall

Change probes while keeping the seed, rows, queries, metric, and k fixed. Record at least a small-probe point and an all-partitions point. Timings vary by machine, so compare how candidate work and recall change instead of aiming for a fixed microsecond target.

As probes approaches partitions, candidate work approaches exact search and recall must reach 1.0 on the same deterministic workload.

Checkpoint 6: Use IVFFlat from SQL

Run the Chapter 2 SQLLogicTest:

cargo test -p vector-datafusion-starter --test sqllogictest day2_ivfflat_sql

The SQL text and the matcher you implemented in Chapter 1 are unchanged. Only IndexConfig changes:

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

DataFusion passes LIMIT 5 through Chapter 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 VectorScanExec path.

Review Your Chapter 2 Result

After the four Chapter 2 core tests, recall example, and Chapter 2 SQLLogicTest pass, choose one concrete build and query and explain:

• 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 Chapter 1’s optimizer rule reaches a new index without changing its safety contract.

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

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/write-you-a-vector-db.
write-you-a-vector-db © 2024-2026 by Alex Chi Z. All Rights Reserved.

Navigate a Proximity Graph with NSW

Chapter 3

Complete Restrict Search with IVFFlat first. Finish with a bounded-degree NSW graph, best-first search measured against exact results, and the same SQL top-k running through index=nsw.

NSW is the graph-based building block of HNSW. It starts from one or more entry points and follows graph edges toward vectors closer to the query. Because it explores only connected neighbors instead of comparing every stored vector, it can answer with less work and can also stop before reaching the true nearest neighbor.

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 has no global ordering or centroid that points directly to the answer.

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

The walk stops when none of the current vertex’s neighbors is closer. It may stop at a local minimum instead of the globally nearest vector, which is why NSW is approximate.

Multiple Entry Points and k Neighbors

Now ask for three neighbors while starting from two entry points. Maintain three pieces of state:

• C, a min-heap whose nearest candidate is the next vertex to explore;
• W, a max-heap whose top is the worst of the best visited vertices; and
• visited, a set that prevents a vertex from being expanded twice.

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

Pop the nearest item from C. For each unseen neighbor, compute its distance once. If it can still improve the bounded result frontier, add it to both C and W, then keep only the best three vertices in W.

A later candidate may have only neighbors that are already visited. Expanding it adds nothing, but the search can continue with the remaining candidates.

The second entry point reaches another part of the graph. It does not guarantee exact search, but it reduces the chance that one poorly placed entry point traps the walk in the wrong region.

Continue popping the nearest candidate and updating W. Even after many vertices have been visited, W retains only the best search-width candidates found so far.

Once W is full, compare the nearest pending candidate with its worst result. If the pending candidate is farther away, no queued path can improve the current frontier, so the search stops.

C = entry points as a min-heap by distance
W = unique entry points as a bounded max-heap by distance
visited = unique entry points

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

    for neighbor in candidate.neighbors:
        if neighbor is already visited:
            continue
        mark neighbor visited
        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

Prediction: If the graph has two disconnected components and every entry point is in the first component, can this search return a vertex from the second? Explain why changing the heap width cannot create a missing edge.

Insert into the Graph

Insert rows one at a time. To place a new vector, search the existing graph with width ef_construction and select its nearest max_connections candidates.

Add reciprocal edges between the new vertex and each selected neighbor. Some endpoints may now exceed the degree cap.

For every overfull endpoint, sort its neighbors by distance from that endpoint and retain only the closest configured number. Distance ties use row offset so equal inputs produce the same graph.

Remove every rejected edge from both endpoints. The final graph has no self-edges or duplicate edges, every remaining edge is reciprocal, and each vertex stays within the degree cap.

Build NSW in Rust

You will modify:

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

The starter already exposes NswConfig, NswIndex, the shared Neighbor ordering, and bounded TopK helpers. Keep the public APIs, tests, metric behavior, and Chapter 1 DataFusion matcher unchanged.

Invariants

1. I1 — Valid budget: max_connections > 0, ef_construction >= max_connections, and ef_search > 0.
2. I2 — Visit once: one layer search computes each visited row’s query distance at most once.
3. I3 — Two frontiers: C expands the nearest pending candidate while bounded W tracks the worst retained result.
4. I4 — Safe stop: traversal stops only when W is full and the nearest pending candidate is worse than W’s worst member.
5. I5 — Bounded reciprocal graph: adjacency lists contain no duplicates or self-edges, every edge appears at both endpoints, and every degree is at most max_connections.
6. I6 — Deterministic order: all result and pruning ties use row offset after distance.

Checkpoint 1: Search a Supplied Layer

Implement search_layer in graph.rs. Respect allowed_rows while building: when row r is inserted, only rows 0..r exist in the searchable graph. Ignore duplicate or out-of-range entry points, and return nearest-first results.

Use ef.max(1) as the frontier width. A larger ef explores and retains more candidates; it may improve recall but does not make a disconnected graph connected.

Checkpoint 2: Connect and Prune

Implement prune_neighbors. Remove duplicates, order neighbors by their distance from the owner, break ties by row offset, and truncate to max_connections.

Then implement NswIndex::try_new. Validate the dataset and configuration, add the first row without searching, and insert each later row through the existing graph. When pruning rejects an edge, remove it from both endpoints so I5 still holds.

Checkpoint 3: Query and Compare with Exact Search

Implement search_with_ef. Validate the query and search from the graph entry point with width ef_search.max(k), then return at most the nearest k results.

Run the focused graph test:

cd rust
cargo test -p vector-core-starter --test indexes nsw_high_ef_matches_exact_search_on_connected_fixture

The fixture checks a connected graph at a high search width, exact top-k overlap, reciprocal edges, and the degree cap. It does not claim exact recall for every dataset or smaller search width.

Checkpoint 4: Use NSW from SQL

Run the Chapter 3 SQLLogicTest:

cargo test -p vector-datafusion-starter --test sqllogictest day3_nsw_sql

The SQL text and optimizer rule remain unchanged. Only the selected core index changes:

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

The NSW graph chooses candidate row offsets. DataFusion’s bounded sort still owns final SQL ordering, and unsupported query shapes still use the exact scan.

Review Your Chapter 3 Result

After the focused core test and SQLLogicTest pass, choose one insertion and one query and explain:

• why candidate and result frontiers need opposite heap orderings;
• which comparison permits early stopping;
• how a rejected edge is removed from both adjacency lists;
• how ef_search changes work and recall without changing SQL; and
• why a disconnected component remains unreachable without an entry point or edge into it.

Keep this chapter focused on one immutable graph layer. Hierarchy, deletion, concurrent mutation, persistence, and sophisticated neighbor-diversification heuristics remain 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/write-you-a-vector-db.
write-you-a-vector-db © 2024-2026 by Alex Chi Z. All Rights Reserved.

Add Hierarchy with HNSW

Chapter 4

Complete Navigate a Proximity Graph with NSW first. Finish with seeded sparse graph layers, greedy upper-layer descent, layer-zero beam search, and the same SQL top-k running through index=hnsw.

The previous chapter searches one NSW graph containing every vector. HNSW adds sparse graph layers above it, much like a skip list or a mipmap: upper layers make long jumps across the collection, while the complete layer zero refines the search around the query.

How Hierarchy Works

Layer zero contains every vector. Each higher layer contains a progressively smaller random subset. A vertex that appears in an upper layer also appears in every layer below it.

The diagram repeats the same vector IDs across nested layers. Sparse upper-layer edges cross large parts of the dataset; denser lower-layer edges make shorter moves. The highest promoted vertex becomes the entry point for the whole index.

Look Up a Query

Begin at the entry point in the highest layer. Greedily follow closer neighbors until no adjacent vertex improves the distance, then carry that vertex down as the entry point for the next layer.

Upper layers use a width-one greedy walk because their job is coarse routing. At layer zero, reuse the NSW best-first search from Chapter 3 with width max(k, ef_search), then return the nearest k candidates.

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

Prediction: Why would using the full beam width in every sparse upper layer do more work without changing the final result contract? Which layer still needs multiple candidates to produce top-k output?

Insert a Vector

Assign each new vector a random maximum level. The course uses repeated seeded coin flips: every successful flip promotes the vector one layer higher, up to max_level. This produces many layer-zero vertices and progressively fewer vertices in higher layers.

Suppose the new vector reaches level one. It belongs to layers one and zero, but not layer two.

Start at the current top entry point. Greedily descend through layers above the new vector’s level. At each layer the new vector joins, run the Chapter 3 best-first search with ef_construction, choose the nearest max_connections candidates, add reciprocal edges, and prune both sides of rejected edges.

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
    prune reciprocal edges to the degree cap
    entry = nearest candidate

if target_level is above the previous highest level:
    add the missing sparse layers
    make the new vector the top entry point

When the first vector creates the index, add it to every layer through its sampled level and use it as the entry point. When a later vector reaches a new highest level, its new upper layers initially contain only that vector.

Build HNSW in Rust

You will modify:

rust/vector-starter/core/src/graph.rs        greedy_search only
rust/vector-starter/core/src/hnsw.rs

The starter already contains the Chapter 3 layer search and pruning interfaces, a deterministic random-number generator, and the public HNSW configuration and inspection methods. Keep the NSW behavior, metric ordering, public APIs, and DataFusion matcher unchanged.

Invariants

1. I1 — Nested membership: row r appears in every layer from zero through levels[r] and in no higher layer.
2. I2 — Seeded levels: equal data, configuration, and seed produce the same level sequence and top level.
3. I3 — Valid budget: max_connections > 0, ef_construction >= max_connections, ef_search > 0, and max_level > 0.
4. I4 — Greedy descent: upper layers move only to a strictly closer neighbor and pass one entry point downward.
5. I5 — Layer-zero beam: final search uses the Chapter 3 two-frontier traversal with width ef_search.max(k).
6. I6 — Bounded reciprocal layers: every layer preserves the degree cap, contains no duplicate or self-edges, and stores every remaining edge at both endpoints.
7. I7 — Stable identity: every layer stores the same core row offsets used by the dataset and Arrow batch.

Checkpoint 1: Descend One Layer

Implement greedy_search in graph.rs. Start from one valid entry point, repeatedly choose its nearest allowed neighbor, and move only when that neighbor is strictly better than the current vertex. A strict improvement prevents cycles and makes distance-and-row tie order deterministic.

Checkpoint 2: Assign Seeded Levels

Validate HnswConfig, then sample one capped geometric level per dataset row from the supplied deterministic generator. Store the sampled levels so two builds with the same seed can be compared directly.

As rows arrive, extend every existing layer’s adjacency storage and create missing upper layers through the row’s sampled level. Rows below a layer’s membership threshold keep an empty adjacency list in that layer.

Checkpoint 3: Build the Layered Graph

Implement the insertion descent and connection loops from the algorithm above. Reuse the Chapter 3 search and pruning rules. At every connected layer, remove rejected edges from both endpoints and preserve the same deterministic neighbor order.

Update the global entry point only when the new row’s level is higher than the previous top level.

Checkpoint 4: Search from Top to Bottom

Implement search_with_ef. Validate the query and search width, greedily descend every upper layer, then call search_layer at layer zero with ef_search.max(k). Truncate the nearest-first result to k.

Run the focused test:

cd rust
cargo test -p vector-core-starter --test indexes hnsw_is_seeded_and_high_ef_recovers_neighbors

The test checks seeded level assignment, nested membership, degree bounds, reciprocal edges, and exact overlap on one connected fixture at a high search width. It does not make HNSW exact for arbitrary data or smaller budgets.

Checkpoint 5: Use HNSW from SQL

Run the Chapter 4 SQLLogicTest:

cargo test -p vector-datafusion-starter --test sqllogictest day4_hnsw_sql

The unchanged SQL boundary now exposes the hierarchical index:

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

HNSW selects candidates; DataFusion still owns final SQL ordering. Filters and incompatible distance expressions remain on the exact scan.

Review Your Chapter 4 Result

After the focused test and SQLLogicTest pass, choose one promoted row and one query and explain:

• why membership must be nested across layers;
• how one entry point moves from the top layer to layer zero;
• why upper layers use greedy search while layer zero keeps a beam;
• when the global entry point changes; and
• how the seed affects graph structure and a fair recall comparison.

Keep this chapter focused on an immutable in-memory HNSW index. Deletion, concurrent mutation, persistence, production neighbor-diversification heuristics, and adaptive search budgets remain 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/write-you-a-vector-db.
write-you-a-vector-db © 2024-2026 by Alex Chi Z. All Rights Reserved.

Where to Go Next

The Rust course builds an immutable in-memory collection, exact fallback, IVFFlat, NSW, HNSW, and SQL query support. 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.
• Add scalar or product quantization, then measure memory, latency, and recall together.
• Rebuild large indexes with bounded memory and resumable checkpoints.

Query Processing

• Extend the DataFusion adapter with safe filtered top-k pushdown, DDL, 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.
• Profile real embedding dimensions and datasets instead of relying on tiny synthetic vectors.

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 four Rust chapters include starter code, executable references, focused tests, and SQL plan checks. Feedback about the scope, ordering, datasets, 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/write-you-a-vector-db.
write-you-a-vector-db © 2024-2026 by Alex Chi Z. All Rights Reserved.

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/write-you-a-vector-db.
write-you-a-vector-db © 2024-2026 by Alex Chi Z. All Rights Reserved.

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/write-you-a-vector-db.
write-you-a-vector-db © 2024-2026 by Alex Chi Z. All Rights Reserved.

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/write-you-a-vector-db.
write-you-a-vector-db © 2024-2026 by Alex Chi Z. All Rights Reserved.

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/write-you-a-vector-db.
write-you-a-vector-db © 2024-2026 by Alex Chi Z. All Rights Reserved.

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/write-you-a-vector-db.
write-you-a-vector-db © 2024-2026 by Alex Chi Z. All Rights Reserved.

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/write-you-a-vector-db.
write-you-a-vector-db © 2024-2026 by Alex Chi Z. All Rights Reserved.

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.

Layer Invariants

Your implementation should preserve these rules:

• layer 0 contains every vertex;
• membership is nested: a vertex in layer L also appears in every lower layer;
• each layer stores global vertex IDs into vertices_ and rids_;
• upper layers use m_max_, while layer 0 uses m_max_0_;
• edges remain symmetric within each layer; and
• the top entry point belongs to the current highest nonempty layer.

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/write-you-a-vector-db.
write-you-a-vector-db © 2024-2026 by Alex Chi Z. All Rights Reserved.

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/write-you-a-vector-db.
write-you-a-vector-db © 2024-2026 by Alex Chi Z. All Rights Reserved.