How does a vectorDB actually work?

In this article

1. Before you start
2. Why interviewers ask this
3. Vector database from first principles
4. The Staff-level answer
5. The rubric
6. Three variants of this question
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one step of the vector database and embeddings learning path.

Why interviewers ask this

A wrong picture of a vectorDB costs real systems quality: if you think it returns the exact nearest items, you will not notice when relevant documents silently go missing. Candidates report the question in AI engineering interviews, and it separates people who have called a vector search library from people who know what runs underneath.

A weak answer says "it stores embeddings and finds similar ones." A strong answer names the two jobs, storage and search, explains why searching everything is too slow, and describes one index in enough detail to follow. A Staff-level answer adds the cost of the shortcut: recall below one, memory limits, and how you would measure and tune both.

Vector database from first principles

Product quantization

Product quantization (PQ) is a compression method that splits each vector into pieces and replaces every piece with the number of its nearest stored centre, so a long vector becomes a short code.

In plain words

Think of a huge library with no catalogue. To find books like yours, you would check every shelf. That works, but it is slow. A vectorDB builds a catalogue first. The catalogue sends you to a few shelves. You check only those.

The analogy breaks in one place. A real catalogue is exact. This one is a guess about where the best books are, so it can send you away from a good shelf.

In one precise sentence, a vectorDB is a store of vectors plus an index that answers nearest-neighbour queries approximately, with persistence, updates and filtering around it. The Faiss paper calls vector similarity search a core functionality of vector databases and describes Faiss as a toolkit of indexing methods.

1 · Exact scan2 · List index3 · Recall trade4 · Graph index5 · Short codesReplay

Step-by-step description

1. Compare the query with every vector.
2. Scan only the closest lists.
3. A true neighbour can be missed.
4. Descend from a sparse layer.
5. Compress vectors into codes.

• Exact search compares the query with every stored vector.
• A list index scans only the nearest lists, so a true neighbour in another list can be missed.
• A layered graph walks from a sparse top layer down to the dense bottom layer.
• Product quantization stores each vector as a short code.

Step 1: Exact search compares the query with every stored vector

Exact search, also called brute force, computes the distance from the query to each stored vector and keeps the closest few. The Faiss paper notes that for large datasets this approach becomes too slow. By default, pgvector does exactly this and gives perfect recall.

How "closest" is measured is a choice of distance function: pgvector supports L2 distance, inner product and cosine distance, among others. An index is added for each distance function you want to use (pgvector README), for example vector_cosine_ops for cosine (Neon docs).

Input: one query vector and the whole collection. Output: the true top few. The cost is one distance per stored vector, and each distance touches every dimension. Take an illustrative collection of 1,000,000 vectors with 768 numbers each: one query needs 768,000,000 multiply-adds, and the raw numbers at four bytes each take 3,072,000,000 bytes.¹ You now know the baseline every index tries to beat.

Step 2: An index of lists searches only the nearest few

The ivfflat index in pgvector is a list-based design. It runs k-means. K-means is a method that groups vectors around centre points called centroids. The index divides the vectors into lists, one per centroid (Microsoft Learn). A query is compared with the centroids, then only the closest lists are scanned. The number of lists scanned is called probes, and it is 1 by default (pgvector README). The vector indexing page covers how such indexes are built.

Take the same illustrative million vectors in 1,000 even lists. One probe costs 1,000 centroid comparisons plus about 1,000 vectors, so 2,000 distances against 1,000,000. Ten probes cost 11,000, about 91 times fewer than the exact scan.¹ Raising probes buys recall and costs speed. Setting probes to the number of lists makes the search exact again (Microsoft Learn). The lists must be built from existing data, so load data before indexing.

Text description of the diagram

• An exact scan costs 1,000,000 distance computations.
• Ten lists cost 11,000 and one list costs 2,000.

Step 3: An approximate index can miss the true nearest neighbour

An approximate index can return a worse neighbour than an exact search, because the closest vector can sit in a list the query never opens. The Neon docs say a query near the edge of a cluster can miss closer neighbours in adjacent clusters, which lowers recall. The pgvector README says an index trades some recall for speed, and that you will see different results after adding one.

A tiny illustrative example shows it. Two list centres, placed by hand rather than computed by k-means, sit at (0, 0) and (10, 0), with four points around each. The query (4.5, 0) is 4.5 from the first centre and 5.5 from the second, so one probe opens the first list. The best point there is at distance 2.5, but the point (6, 0) in the other list is at distance 1.5. Two probes find it.¹ That is a recall loss of one neighbour out of one, caused only by the cluster boundary.

Step 4: A layered graph walks from a sparse top layer down

Hierarchical Navigable Small World (HNSW) is a graph index that links each vector to nearby vectors and stacks several graphs, from a sparse top layer to a bottom layer that holds every vector, each linked to a few close neighbours. Malkov and Yashunin build a multi-layer structure of proximity graphs, and each element's top layer is drawn at random with exponentially decaying probability.

A query enters at the sparse top layer, moves greedily to the closest vector it can reach, drops one layer, and repeats until the bottom layer. The authors report that starting from the upper layer gives logarithmic complexity scaling; the authors show this experimentally rather than as a worst-case bound.

Illustratively, if each layer keeps one vector in 16 from the layer below, a million vectors give layers of about 1,000,000, 62,500, 3,906, 244, 15 and 1 vectors.¹ The one-in-16 ratio is chosen to echo the pgvector default of m = 16 links per vector (pgvector README). The pgvector search width, hnsw.ef_search, the size of the dynamic candidate list, is 40 by default (same README).

Step 5: Quantization shrinks the vectors so more fit in memory

Storing every number at full precision limits how many vectors fit in memory. Product quantization splits a vector into pieces and quantizes each piece separately, so a vector becomes a short code of indices (Jegou et al., 2011). The same paper says eight pieces and 256 centres each is often a reasonable choice, but that setting was for 128-dimensional Scale-Invariant Feature Transform (SIFT) image descriptors; longer vectors usually need more pieces.

With the paper's eight pieces, each code is eight bytes, one byte per piece. A 768-number vector at four bytes per number is 3,072 bytes, so the code is 384 times smaller before overhead.¹ The codebooks of centres add 786,432 bytes in total, shared by every vector.¹ A more realistic illustrative choice for 768 numbers is 96 pieces: each code is 96 bytes, 32 times smaller, and a million codes take 96,000,000 bytes.¹ The price is accuracy: distances become estimates, so quantized indexes often re-check a few candidates against the full vectors.

The Staff-level answer

What makes it Staff-level is the fifth and sixth sentences: it treats recall as something you measure and tune, and it names the cost of each shortcut instead of presenting the index as free.

The rubric

Three variants of this question

What is the difference between a vector database and a vector index library like Faiss?

A library such as Faiss is a toolkit of indexing methods that search, cluster and compress vectors (Douze et al.). A vector database wraps an index with storage, updates and filtering. pgvector, for example, is an extension that adds this to Postgres.

How does HNSW search find neighbours without checking everything?

It starts in a sparse top layer, moves to the closest vector it can reach, then repeats one layer lower, so each layer narrows the region before the dense bottom layer (Malkov and Yashunin).

What changes if the data grows from a million to a billion vectors?

Memory becomes the limit first. The illustrative raw vectors grow from 3,072,000,000 bytes to 3,072 gigabytes, while product quantization codes grow to 8 gigabytes with eight pieces or 96 gigabytes with 96 pieces.¹ So you compress, shard across machines, and re-measure recall.

Common mistakes

• "A vectorDB returns the true nearest neighbours." (wrong) An approximate index can skip them. (right) "It returns close neighbours with a measured recall below one, unless I search exactly."
• "An index only makes the query faster, like in a normal table." (wrong) In pgvector the results can change after you add one, per its README. (right) "A vector index trades recall for speed, so I test results before and after."
• "HNSW is strictly better than the list index." (wrong) It queries faster at a given recall but builds slower and uses more memory (pgvector README). (right) "I pick by build time, memory and recall target."
• "One probe is fine." (wrong) A query near a list edge misses neighbours in the next list. (right) "I raise probes until recall on a test set is acceptable."

Follow-up questions

How do you tell whether an approximate index is good enough?

Run a sample of real queries through exact search and through the index, then compare the top results; the share of exact results the index also returns is its recall. Raise probes or search width until recall meets your target, and record the latency you pay.

How does filtering by metadata interact with the index?

A filter can be applied before, during or after the index scan. If it is applied after, a query asking for ten results can return fewer, because some of the ten candidates are filtered out. Check how your database orders the two; metadata filtering covers the options.

Is a vector database more than an index?

Yes. The index finds neighbours, while the database adds persistence, updates, deletes, metadata filters and access control. That is why pgvector can live inside an ordinary relational database. Updates matter too: list centres are fixed when the index is built, so lists can drift out of balance as new data arrives and recall can fall until the index is rebuilt, and graph indexes need care when vectors are deleted.

Why add a reranker after the vector search?

The first stage is built to be fast and approximate. A cross-encoder reranker reads the query and each candidate together and orders the short list more carefully. Many vectors come from a two-tower model, which is why they can be precomputed.

When would you combine keyword search with vector search?

When exact words matter, such as names or error codes, that vectors blur. Hybrid search merges both result lists. The models producing the vectors are covered in the transformer overview.

Sources

1. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (arXiv 1603.09320) — arXiv (Malkov and Yashunin); IEEE TPAMI 2020, 30 Mar 2016
2. pgvector README — pgvector project (GitHub), master branch, read 2026-10-26, 26 Oct 2026
3. The Faiss library (arXiv 2401.08281) — arXiv (Douze et al.), v4, 23 Oct 2025
4. Product quantization for nearest neighbor search — IEEE TPAMI 33(1) (Jegou, Douze, Schmid), 1 Jan 2011
5. How to optimize performance when using pgvector — Microsoft Learn, read 2026-10-26, 26 Oct 2026
6. Optimize pgvector search — Neon Docs, read 2026-10-26, 26 Oct 2026
7. The pgvector extension — Neon Docs, read 2026-10-26, 26 Oct 2026