Vector Search: Brute Force KNN and the Indexing Problem

In Topic 08, we built semantic movie search using embeddings. It worked well for 30 films.

But what happens when the catalogue grows to 10 million products, 80 million songs, or hundreds of millions of records?

The algorithm can stay correct while becoming too slow and expensive.

This topic explains why brute-force vector search doesn't scale, why ordinary database indexes aren't enough, and why the next topic introduces approximate nearest neighbour search.

1. The problem: 30 films vs millions of vectors

When a user searches for “a lost astronaut trying to get home,” our app:

For 30 films, comparing every vector is fine. For 100 million vectors, the same code must perform 100 million comparisons for every query.

The central problem is that the search checks every stored vector, every time.

2. First understand the key terms

For example, K = 3 means return the three closest matches.

3. Storing vectors is not the same as searching them

A common misconception is that MySQL or PostgreSQL cannot store vectors. They can store vectors in formats such as JSON, raw bytes, or a supported vector type.

CREATE TABLE movies (
    id          INT PRIMARY KEY,
    title       VARCHAR(200),
    description TEXT,
    embedding   JSON
);

JSON is easy to understand, but can be bulky because every number is represented as text. A binary or native vector format can be more compact.

The important distinction is:

• Storage problem: Where do millions of vectors live?
• Search problem: How do we find the closest vectors quickly?

Solving the storage problem doesn't automatically make the search fast.

Remember: A normal database can store vectors. The harder problem is searching them by similarity.

4. Exact lookup vs similarity lookup

Consider these vectors:

Query Q = [0.3, 0.7, 0.2]

A = [0.31, 0.69, 0.22]
B = [0.28, 0.72, 0.19]
C = [-0.6, 0.1, 0.8]

An exact match checks whether a stored vector equals Q. None does, so it returns nothing.

A similarity search asks which vectors are closest to Q. A and B are close, even though neither is identical.

Semantic search usually needs similarity lookup because users can express the same idea in different words.

5. How brute-force KNN works

The simplest vector database needs only three operations:

1. Store the ID, vector, and metadata.
2. Convert the user's query into a vector using the same embedding model.
3. Compare it against every stored vector and keep the top K.

The embedding model and vector store have separate jobs:

• The embedding model converts meaning into numbers.
• The vector store compares those numbers.

Important: Use the same embedding model for stored vectors and query vectors. Different models can produce incompatible vector spaces.

The cost of one comparison

A vector has D dimensions. Comparing two vectors requires work across those dimensions.

For a dot product:

Q · V = Q₁ × V₁ + Q₂ × V₂ + ... + Q_D × V_D

For cosine similarity, we also account for the vector lengths. If both vectors have already been normalised to length 1, cosine similarity reduces to their dot product.

If the vector has 1,536 dimensions, each comparison involves approximately 1,536 multiply-add operations.

With N stored vectors, the total work per query is proportional to:

O(N × D)

Here:

• N = number of stored vectors
• D = dimensions per vector

Calculate the work

For 10 million vectors, each with 1,536 dimensions:

10,000,000 × 1,536 = 15,360,000,000

That is approximately 15.36 billion multiply-adds for one query.

This is why brute force becomes expensive at scale. The exact execution time depends on the hardware, implementation, and parallelisation, but the amount of work grows with N × D.

6. The memory bill

Search requires storage as well as compute.

A float32 number uses 4 bytes. A vector with 1,536 numbers therefore requires:

1,536 × 4 = 6,144 bytes

That's roughly 6 KB per vector.

Raw vector storage: storage required for 1,536-dimensional float32 vectors, excluding metadata and indexes.

These use decimal GB (1 GB = 1,000,000,000 bytes), the same way the note's cost calculator prints them.

A real system also needs space for IDs, metadata, indexes, replicas, and working memory. Storing the same numbers as JSON text generally takes more space.

Why not keep everything on disk?

Disks provide more capacity, but reading millions of vectors from disk for every query adds substantial latency. Moving the data to disk reduces the RAM requirement; it does not solve the need to scan all the vectors.

This gives brute-force search two major scaling costs:

• Compute: Score every vector.
• Data access: Read or fetch every vector.

7. Make Top K cheaper with a min heap

After scoring all vectors, we need to return only the K highest scores.

The simplest approach is to sort every score and take the first K. But if we have one million scores and only need the top 10, sorting all one million is unnecessary work.

A min heap keeps the weakest of the current best K scores at the top.

Imagine a leaderboard with three places:

• If there are fewer than three scores, add the new score.
• Once full, compare a new score with the weakest score.
• If the new score is better, replace the weakest.
• Otherwise, discard the new score.

The heap improves the cost of selecting the top K. However, it does not eliminate the N vector comparisons. Brute-force search remains O(N × D) for scoring, with additional heap maintenance.

In Node.js, JavaScript doesn't provide a built-in heap, so the course lab implements a small TopKHeap class.

8. Why B-trees work for normal database queries

A database index is extra data built ahead of time to help the database avoid scanning every row.

For example:

SELECT *
FROM orders
WHERE bill_amount = 450;

If bill_amount is indexed, the database can navigate an ordered structure to find the values equal to 450 instead of checking every order.

A B-tree stores sorted values in a tree. Each decision narrows the range of possible matches.

The tree follows the relevant range and skips unrelated branches.

Why does this work? A single number has a clear order. If you're searching for 450 and a value is 310, you know values below 310 cannot equal 450.

A sorted dictionary works the same way: you jump to a section and rule out the parts that cannot contain your word.

The secret is order. A B-tree can efficiently navigate a one-dimensional ordered value. But vector search is different: a vector contains many numbers, and there's no single order that captures all similarity relationships.

9. What is a k-d tree?

A k-d tree (k-dimensional tree) attempts to index points in multidimensional space.

Instead of sorting every point by one global order, it splits the space one axis at a time.

• In 2D, split by x, then y, then x again.
• In 3D, cycle through x, y, and z.
• Continue cycling through the available dimensions.

Imagine a city map. First divide the city into east and west, then divide each half into north and south. Each resulting region contains fewer points.

Example: seven tea stalls

The course's example has seven stalls with coordinates:

Split on x at the root. The middle point is D (6, 5). The left side contains A, B, C; the right side contains E, F, G. The next level splits each side using y.

A balanced tree of one million points can have roughly 20 levels, because 2^20 is about one million. In low dimensions, this structure can help nearest-neighbour search avoid checking many points.

10. How k-d tree pruning works

Pruning means skipping a whole branch when it cannot contain a better answer than the best match found so far.

Suppose the query point is Q = [9, 7].

The course's example visits D, then G, then F:

• D (6, 5) is about 3.61 units from Q.
• G (9, 4) is 3 units away.
• F (8, 8) is about 1.41 units away, becoming the best match.

Now the search considers whether the skipped branches might beat F.

The split line for G's y = 4 is 3 units from Q. Since the best match is only 1.41 units away, the branch containing E cannot improve the answer. It is pruned.

Likewise, the x = 6 split line is 3 units away, so the left branch containing A, B, and C is pruned.

The lab compares squared distances to avoid calculating square roots at every node. Squaring preserves the ordering of non-negative distances.

In code, the key logic looks like this:

const gap = query[node.axis] - node.point.coords[node.axis];

const near = gap < 0 ? node.left : node.right;
const far = gap < 0 ? node.right : node.left;

visit(near, query, search);

if (gap * gap < search.bestSquared) {
  visit(far, query, search);
}

The tree checks the far side only if it could still contain a closer point.

11. Why k-d trees fail for high-dimensional embeddings

A k-d tree can work well for 2D points on a map. Why not use it for a 1,536-dimensional embedding?

This is where the curse of dimensionality comes in: many indexing techniques become less effective as the number of dimensions grows.

There are two main reasons in the course.

Reason 1: The tree splits on only a few axes during a search.

A tree with one million points may have about 20 levels. If the embedding has 1,536 dimensions, a search path visits only around 20 split levels. The other dimensions still affect the distance, but those axes aren't used to prune branches along that path.

Reason 2: Pruning becomes much less effective.

In many dimensions, even the nearest point can be relatively far away in total distance. But each split line is measured along just one axis. The query often cannot prove that the far branch is too distant, so the algorithm must visit it.

The course's lab tests dimensions 2, 3, 8, 32, and 128. The trend is that the fraction of visited points grows as the dimension count increases. Real embeddings can cluster by topic, but k-d trees still tend to perform poorly for hundreds or thousands of dimensions.

12. So what should we use at scale?

This topic ends by setting up the next one.

The course introduces approximate nearest neighbour search in Topic 10, including approaches such as IVF and HNSW. Their goal is to avoid examining every vector while still returning useful, highly similar results.

Interview revision

"What is KNN?"

K Nearest Neighbours: find the K stored vectors closest to a query vector.

"Why is brute-force vector search expensive?"

It compares the query against every vector. Its scoring cost grows as O(N × D).

"Does using a min heap make brute-force search faster?"

It reduces the work and memory needed to select the top K results, but it doesn't remove the need to score all N vectors.

"Can a relational database store embeddings?"

Yes. The challenge is efficient similarity search, not simply storing the numbers.

"Why does a B-tree work well for ordinary database lookups?"

It uses ordered values to skip ranges that cannot contain the answer.

"What does a k-d tree do?"

It divides multidimensional space one axis at a time and prunes branches that cannot contain a closer point.

"What is the curse of dimensionality?"

As dimensions grow, many spatial indexes lose their ability to rule out large parts of the search space.

"What is the next step when exact search becomes too expensive?"

Use an approximate nearest neighbour index to examine fewer vectors and return results that are close to the true nearest neighbours.

Quick quiz

1. What does N represent in the cost O(N × D)?

• Number of vectors
• Number of dimensions
• Number of returned results

2. What does a min heap improve in brute-force search?

• It avoids embedding the query
• It reduces the cost of keeping the top K scores
• It avoids comparing every vector

3. Why do B-trees work well for exact lookups?

• They understand semantic meaning
• They use an ordered structure to skip irrelevant ranges
• They calculate embeddings automatically

4. What is pruning in a k-d tree?

• Deleting old vectors
• Skipping a branch that cannot contain a better answer
• Reducing the embedding dimension

5. Why can a k-d tree struggle with 1,536-dimensional embeddings?

• It cannot store floating-point numbers
• It must use SQL
• It often cannot prune enough branches

6. What is the main idea behind ANN search?

• Always scan every vector for a guaranteed exact result
• Examine fewer vectors and accept that results may not be exactly optimal
• Replace embeddings with keywords

Remember this: Brute force checks everything and is exact. A heap makes top-K selection cheaper, but not the scan itself. Traditional indexes work by skipping data using order; high-dimensional vectors don't offer the same simple order. That's why the next topic moves to ANN indexing.