Why We Need Vector Databases? KNN & Vector Search | FDE Chapter 9

This chapter explores the fundamental challenges of scaling vector embeddings in production environments. We analyze why storing embeddings in application memory or traditional relational databases fails at scale, dissect the mathematical and computational complexities of K-Nearest Neighbors (KNN) search, and evaluate spatial indexing structures like KD-Trees to understand why high-dimensional vector spaces require specialized Vector Databases.

1. Recapping the Naive Movie Recommendation Engine ("Movie Match")

In our previous implementation of the "Movie Match" recommendation engine, we built a simple catalog of 30 movies (e.g., Interstellar, Batman, Superman, etc.). The workflow to recommend movies based on a user query operated as follows:

While this naive approach works perfectly for a toy dataset of 30 movies, it relies entirely on keeping all vector embeddings in the application's volatile memory (RAM) as a list of floating-point arrays (List<float[]>).

2. The Scaling Wall: Why RAM-Based Storage Fails

In real-world production applications, catalogs are massive and cannot fit into application memory. Consider the scale of modern digital platforms:

• Spotify: Hosts over 100 million songs in its catalog.
• Google Search: Indexes 3 to 4 billion public web pages.
• Amazon: Manages catalogs containing millions of products.
• Netflix: Recommends thousands of media assets to millions of concurrent users.

If we attempt to scale our naive RAM-based storage to these volumes, the application will rapidly run out of memory (OOM), crash, and fail to provide persistence. This brings us to two fundamental engineering questions:

1. How do we store vectors securely and persistently?
2. How do we search through these vectors efficiently?

3. Can We Just Use Traditional Databases (SQL/NoSQL)?

To solve the persistence problem, a natural first instinct is to store vectors in a traditional relational database (like PostgreSQL or MySQL) or a NoSQL database (like MongoDB).

The Proposed Database Schema

We could design a movies table containing the following columns:

Why Traditional Databases Fail: Exact Matching vs. Similarity Matching

Traditional databases are architected for Exact Matching, whereas vector search requires Similarity Matching.

• Exact Matching (SQL): When executing a query like SELECT * FROM movies WHERE id = 3 or WHERE genre = 'Sci-Fi', the database engine uses B-Trees or B+ Trees. It performs binary-like splits to locate the exact record in $O(\log N)$ time. The result is binary: a row either matches the condition (True) or it does not (False).
• Similarity Matching (Vector): We never query a vector database for an exact match (e.g., WHERE embedding = [0.4, 0.7, 0.1]). Two vectors almost never match exactly unless they represent the identical source text. Instead, we ask for vectors that are closest to our query vector $Q$. This requires calculating a continuous similarity score (between 0.0 and 1.0) for every single record.

Traditional indexes (B-Trees) cannot index multi-dimensional floating-point arrays for similarity searches. Consequently, a traditional database is forced to perform a full table scan, calculating the similarity score for every single row sequentially.

The Metadata Problem: Why We Must Store Extra Attributes

You might wonder: If we have the vector embedding, why do we need to store the movie's name, description, and genre separately?

Conceptually: Embedding generation is a one-way, lossy forward process (similar to cryptographic hashing).

You cannot reverse a vector embedding back into its original text description.

Therefore, we must store the original attributes (Name, Description, Genre, Release Year) alongside the vector as Metadata. Once the vector database identifies the nearest matching vector IDs, it retrieves this metadata to display human-readable results to the end-user.

4. Mathematical Complexity of Naive Vector Search (KNN)

To understand why naive search (K-Nearest Neighbors / Linear Scan) does not scale, let us calculate its exact computational and storage overhead.

Time Complexity Analysis

Let:

• $N$ = Total number of vectors in the database.
• $D$ = Dimensionality of each vector (e.g., $1536$ dimensions for OpenAI's standard embeddings).

To find the nearest neighbor to a query vector $Q$, we must compute the dot product (or cosine similarity) against all $N$ vectors. A single dot product between two $D$-dimensional vectors requires:

• $D$ multiplications
• $D - 1$ additions

Thus, the time complexity to search for a single query is:

Real-World Example: 10 Million Vectors

Suppose we have a modest dataset of $N = 10 \text{ million}$ vectors, each with $D = 1536$ dimensions.

Performing 15.36 billion floating-point operations (FLOPs) for a single search query is computationally devastating. If your application receives 100 concurrent queries per second, the system will instantly freeze under the computational load.

Storage Complexity Analysis

Let us calculate the raw memory required to store these vectors.

• Each dimension of a vector is represented by a single-precision floating-point number (Float32), which consumes 4 bytes of memory.
• For a $1536$-dimensional vector:

• For $10 \text{ million}$ vectors:

Note: This $60 \text{ GB}$ figure represents only the raw vector embeddings. It does not include the database indexes, metadata (titles, descriptions), or overhead from the database engine itself. Storing this entirely in RAM is highly expensive and inefficient.

5. The Concept of Indexing: 1D Space vs. Multi-Dimensional Space

To bypass the $O(N \times D)$ brute-force search, we must build an index. Let us first examine how indexing works in a simple 1-Dimensional (1D) space, and why it fails when we add dimensions.

1D Indexing: Binary Search

Imagine our movie embeddings are 1-Dimensional (each movie is represented by a single number). We have the following catalog:

• Interstellar: $12$
• Superman: $35$
• Titanic: $42$
• Batman: $67$
• Other movies: $80, 86, 99$

If we sort this array, we get: [12, 35, 42, 67, 80, 86, 99].

Now, a user submits a query $Q$ which embeds to the value $38$. Instead of comparing $38$ to all 7 numbers, we perform a Binary Search:

By locating the exact insertion point, we know the nearest neighbors must be the adjacent elements: $35$ (Superman) and $42$ (Titanic).

• $\text{Distance}(38, 35) = \vert 38 - 35\vert = 3$
• $\text{Distance}(38, 42) = \vert 38 - 42\vert = 4$

The nearest neighbor is $35$ (Superman). We achieved this in $O(\log N)$ time with only 3 comparisons instead of 7.

Why We Cannot Sort Multi-Dimensional Vectors

In 1D space, numbers have a natural total ordering (e.g., $12 < 35 < 42$). In multi-dimensional space, this ordering breaks down.

Consider two 2D vectors:

• Vector $A = [2, 7]$
• Vector $B = [5, 1]$

Which vector is "smaller"?

• If we compare by the X-axis: $2 < 5 \implies A < B$
• If we compare by the Y-axis: $7 > 1 \implies A > B$

Because there is no natural total ordering, we cannot sort multi-dimensional vectors in a simple linear array to perform standard binary search.

6. KD-Trees (K-Dimensional Trees) Explained

To bring the efficiency of binary search to multi-dimensional spaces, computer scientists designed KD-Trees (K-Dimensional Trees).

The Core Mental Model

A KD-Tree is a binary tree where every node is a $K$-dimensional point. The tree construction alternates the splitting dimension at each level of the tree:

• Level 0 (Root): Split the space vertically using the X-axis.
• Level 1: Split the remaining subspaces horizontally using the Y-axis.
• Level 2: Split again using the X-axis (or Z-axis if 3D), and so on.

Step-by-Step KD-Tree Construction

Let us construct a 2D KD-Tree using the following six coordinate points:

• $A(1, 8)$
• $B(2, 3)$
• $C(4, 5)$
• $D(6, 6)$
• $E(7, 2)$
• $F(8, 7)$

Step 1: Split at Level 0 (X-Axis)

First, we sort all points by their X-coordinate:

We select the median point as our root. The median is $D(6,6)$ (X-coordinate = 6).

• Root Node: $D(6, 6)$
• Left Subtree Points (X < 6): $A(1, 8), \ B(2, 3), \ C(4, 5)$
• Right Subtree Points (X > 6): $E(7, 2), \ F(8, 7)$

Step 2: Split at Level 1 (Y-Axis)

Now, we split the left and right subtrees using their Y-coordinates.

• Left Subtree: Sort $\{A(1,8), B(2,3), C(4,5)\}$ by Y:

The median is **$C(4,5)$** (Y-coordinate = 5).
*   Left child of $C$: $B(2,3)$ (Y < 5)
*   Right child of $C$: $A(1,8)$ (Y > 5)

• Right Subtree: Sort $\{E(7,2), F(8,7)\}$ by Y:

We select **$F(8,7)$** as the median split.
*   Left child of $F$: $E(7,2)$ (Y < 7)
*   Right child of $F$: None

The Resulting KD-Tree Structure

               D(6,6)  [Split on X]
              /      \
      C(4,5)          F(8,7)  [Split on Y]
     /      \        /
  B(2,3)  A(1,8)  E(7,2)  [Split on X]

7. Searching and Pruning in a KD-Tree

Let us search this KD-Tree for the nearest neighbor to a Query Vector $Q(7, 6)$.

Query Q = (7, 6)
Best Distance Tracked = infinity

Step 1: Traverse Down to the Leaf Node

We start at the root $D(6,6)$.

1. At Root $D(6,6)$ [Split on X]:
   • Compare $Q_x$ ($7$) with $D_x$ ($6$). Since $7 > 6$, we must go to the right child ($F$).
   • Calculate distance to $D$:

    *   **Best Distance So Far**: $1.0$ (Node $D$)

2. At Right Child $F(8,7)$ [Split on Y]: * Compare $Q_y$ ($6$) with $F_y$ ($7$). Since $6 < 7$, we must go to the left child ($E$). * Calculate distance to $F$:

    *   Since $1.41 > 1.0$, our best distance remains $1.0$ (Node $D$).

3. At Leaf Child $E(7,2)$ [Split on X]: * Calculate distance to $E$:

    *   Since $4.0 > 1.0$, our best distance remains $1.0$ (Node $D$).

Step 2: The Pruning / Backtracking Rule

We have reached a leaf node. However, to guarantee that we have found the absolute nearest neighbor, we must backtrack and check if we can safely prune (ignore) the subtrees we bypassed.

The Pruning Rule: Calculate the perpendicular distance from the query point $Q$ to the splitting plane of the parent node.

• If $\text{Distance to Splitting Plane} \ge \text{Best Distance So Far}$, we can safely prune the entire opposite side of the tree.
• If $\text{Distance to Splitting Plane} < \text{Best Distance So Far}$, a closer point might exist on the other side. We must search the opposite subtree.

Let us apply this rule as we backtrack from $F(8,7)$:

• The splitting plane at $F$ was $Y = 7$.
• Our query $Q$ has $Y = 6$.
• $\text{Distance to Plane} = \vert 6 - 7\vert = 1.0$.
• Our $\text{Best Distance So Far}$ is $1.0$ (Node $D$).
• Since $\text{Distance to Plane} \ (1.0) \le \text{Best Distance So Far} \ (1.0)$, the hypersphere of our search intersects the boundary. We cannot prune the right side of $F$. We must search it (though in this case, it is empty).

Now backtrack to the root $D(6,6)$:

• The splitting plane at $D$ was $X = 6$.
• Our query $Q$ has $X = 7$.
• $\text{Distance to Plane} = \vert 7 - 6\vert = 1.0$.
• Our $\text{Best Distance So Far}$ is $1.0$.
• Since $\text{Distance to Plane} \ (1.0) \le \text{Best Distance So Far} \ (1.0)$, we cannot prune the left subtree of $D$. We are forced to backtrack and search the entire left subtree $\{C, B, A\}$.

8. The Curse of Dimensionality: Why KD-Trees Fail at Scale

While KD-Trees work beautifully in 2D or 3D spaces, they completely break down when applied to high-dimensional embeddings (such as $1536$ dimensions). This failure is caused by the Curse of Dimensionality.

Why High Dimensions Break Pruning

As the number of dimensions $D$ increases, the volume of the space grows exponentially, and data points become extremely sparse. More importantly, the number of splitting planes increases to match the dimensions.

With $1536$ dimensions, a query vector $Q$ will have $1536$ different coordinates. The probability that $Q$ lies extremely close to at least one splitting plane boundary approaches $100\%$.

Official Definition: The Curse of Dimensionality

"The Curse of Dimensionality does not mean that adding one extra dimension suddenly breaks search. Rather, it means that every extra dimension adds more possible ways for points to differ, and more regions that might contain a neighbor.

As dimensions keep increasing, our ability to safely eliminate (prune) larger parts of the search space gets weaker and weaker. Eventually, an exact search structure must inspect so much of the dataset that it starts behaving almost exactly like a brute-force linear scan."

Because of this, exact spatial indexing structures like KD-Trees, R-Trees, or Octrees are completely useless for high-dimensional vector search.

9. Summary and Key Takeaways

• RAM Storage is Unscalable: Storing vector embeddings in application memory works for small catalogs (e.g., 30 items) but causes Out-Of-Memory (OOM) crashes when scaling to millions of records (e.g., Spotify, Google, Amazon).
• Traditional Databases are Incompatible: SQL and NoSQL databases are built for Exact Matching (using B-Trees for $O(\log N)$ lookups). Vector search requires Similarity Matching (calculating continuous similarity scores), which forces traditional databases to perform slow, full-table scans.
• Embeddings are One-Way: Vector generation is a lossy, one-way process. You cannot reconstruct a movie's title or description from its vector embedding. Therefore, databases must store original attributes as Metadata alongside the vectors.
• High Computational Cost: A naive K-Nearest Neighbors (KNN) search has a time complexity of $O(N \times D)$. For 10 million vectors with 1536 dimensions, a single query requires 15.36 billion floating-point operations.
• High Storage Cost: Storing 10 million 1536-dimensional vectors in Float32 format requires 60 GB of raw memory, excluding metadata and indexing overhead.
• Total Ordering Fails in Multi-Dimension: Unlike 1D numbers, multi-dimensional vectors cannot be sorted sequentially because they lack a natural total ordering.
• KD-Trees Split Space Alternately: KD-Trees attempt to solve multi-dimensional search by alternating coordinate splits (X-axis, Y-axis) at each tree level to partition space.
• The Curse of Dimensionality Destroys Trees: In high-dimensional spaces (e.g., 1536D), a query vector is almost guaranteed to lie close to a splitting plane boundary. This invalidates the pruning rule, forces the algorithm to backtrack through almost every branch, and degenerates the search back to an $O(N)$ brute-force scan.
• The Need for Vector Databases: To solve both the storage and search efficiency problems in high dimensions, we must move away from exact search algorithms and adopt specialized Vector Databases that utilize Approximate Nearest Neighbor (ANN) search algorithms.