Press enter or click to view image in full size

Machine Learning

Vector Database

Matrice

Hnsw

Building PyVecDB: What I Learned Building a Vector Database from Scratch

Funboy Ea

4 min read

·

Dec 19, 2025

--

2

Listen

Share

Building a vector database isn’t just about storing numbers; over the course of this short write up, I’ll explain things I learnt while experimenting with vectors in a latent space. I have also attached the repo that holds python code I experimented with, a lightweight vector db in python: pyvecdb

1. The Foundation: Distance Metrics

Before you decide to search, you have to define what “close” means. I explored three core metrics:

• Euclidean Distance (L2): Think of this as a ruler measuring the straight-line distance between two points. It’s sensitive to the “length” (magnitude) of the vectors.
• Cosine Similarity: This ignores how long the vectors are and only looks at the angle between them. It’s perfect for text because it doesn’t care if one document is longer than another, as long as they talk about the same things.
• Dot Product: A measure of how much two vectors point in the same direction.

TIP
Vectors are often normalized for Cosine Similarity. This “squashes” them into a unit sphere so we can focus entirely on the direction/angle.

2. The Scaling Wall: Flat vs. HNSW

When I started, I used a Flat Index (Brute Force). This is simple: compare your query to every single vector in the database.

• It’s 100% accurate.
• It’s slow. At O(N) complexity, if you have a million vectors, you’re doing a million comparisons every time “search” is hit.

To solve this, I moved to HNSW (Hierarchical Navigable Small World).

What Actually Is HNSW?

HNSW is based on an idea from the 2016 paper “Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs” by Malkov and Yashunin. The core insight? Combine two concepts:

1. Small World Networks: Like the “six degrees of separation” concept, these graphs have short paths between any two nodes. HNSW uses “skip list” inspiration to create these shortcuts.
2. Navigable Networks: Not all connections are equal. HNSW builds a hierarchy where long-range links at the top help you navigate quickly to the right region, and short-range links at the bottom help you find exact neighbors.

Think of it like a map with multiple zoom levels:

1. Top Layers (Sparse): “Expressways” with fewer nodes but long-range connections. You jump across the dataset quickly.
2. Middle Layers: Progressively denser neighborhoods as you zoom in.
3. Bottom Layer (Dense): Every single vector exists here with “local street” connections to nearby neighbors.

The Search Process:

• Start at the top layer with a random entry point
• Greedily navigate to the closest node at that layer
• Drop down a layer and repeat
• Continue till you reach the bottom and find the nearest neighbors

This brings search complexity down to O(log N) with high probability, which is a massive win… more often than not.

The Key Parameters (From the Paper)

The HNSW algorithm has two critical parameters that control the speed/accuracy trade-off:

• M: Maximum number of bidirectional connections per node (except layer 0, which uses M x 2). Higher M = better recall but more memory and slower construction. The paper suggests M = 12–48 for most use cases.
• efConstruction: Size of the dynamic candidate list during construction. Higher values = better quality graph but slower index building. The paper recommends efConstruction = 100–500.
• efSearch: Size of the dynamic candidate list during search. You can tune this at query time! Higher ef = better recall but slower search.

The paper shows that with proper tuning, HNSW can achieve 95%+ recall while being orders of magnitude faster than brute force.

3. The “Small Scale” Trap

Here’s the most interesting thing I learned: HNSW has overhead.

In my tests:

• At 10k vectors, HNSW was only 1.33x faster than brute force.
• At 25k vectors, the gap started to widen significantly.

The Lesson: For very small datasets, the “expressway” of HNSW actually takes longer to navigate than just checking everyone. Building and traversing the multi-layer graph structure has a cost. The

advantage only really kicks in once the dataset is large enough to justify the complex structure.

This is similar to what the paper discusses: HNSW’s construction time is O(NlogN), so there’s an upfront investment. For tiny datasets, its like paying that cost without reaping rewards.

4. From Python to Production

I initially tried to implement HNSW in pure Python. It was a great way to learn the algorithm, but I quickly realized it’s almost impossible to reach “production status” that way.

Python’s overhead for individual object lookups and loops is too high for the millions of operations HNSW requires. The C++ implementation achieves its impressive benchmarks because of cache-friendly data structures and tight memory management, python abstracts most of this.

To make PyVecDB fast, I integrated hnswlib, a high-performance C++ implementation.

Optimization Tricks I Used(raw python implementation):

• Hybrid Storage: I used a Dictionary for instant lookups (like getting a specific vector by ID) and a NumPy Matrix for massive speed gains during search. The matrix allows us to compare the query against all vectors at once using vectorized math, which is much faster than looping.
• Vectorization: Instead of comparing vectors one-by-one, I used NumPy matrices to compare them in batches.

Why the Paper’s Algorithm Works So Well

The HNSW paper introduced several clever tricks:

• Probability-based layer assignment: Each node is randomly assigned a maximum layer with exponentially decreasing probability. This creates the natural hierarchy without complex balancing logic.
• Heuristic for selecting neighbors: When connecting nodes, HNSW uses a “SELECT-NEIGHBORS-HEURISTIC” that prioritizes diverse connections over just the closest ones, preventing clustering and maintaining navigability.
• Bidirectional links: Every connection works both ways, so you can traverse the graph efficiently in any direction.

Conclusion

Building PyVecDB reminded me that engineering is all about trade-offs. You trade memory for speed, and you trade simplicity for scale. If you’re building for a few thousand items, keep it simple. If you’re building for the world, embrace the complexity of HNSW.