A naive nearest-neighbor scan over 100M vectors is 400GB of math per query. Pinecone, Weaviate, Qdrant, and pgvector all give you 50ms recall@10 ≥ 0.95 on the same hardware — because of one idea: approximate nearest neighbor indexes (HNSW, IVF-PQ). This lesson is how Spotify finds your next song in 50ms and how Notion AI searches 100M+ pages without burning a datacenter.
Learning Objectives
After this lesson, you will be able to:
Understand why comparing every single vector one by one is too slow for real applications, and how approximate nearest neighbor (ANN) algorithms trade tiny accuracy losses for massive speed gains
Compare three indexing strategies -- HNSW (graph-based for fast queries), IVF (cluster-based for large scale), and product quantization (compression-based for memory efficiency) -- and know when to pick each one
Evaluate popular vector databases -- Pinecone (managed), Weaviate (open-source with hybrid search), ChromaDB (prototyping), Qdrant (high-performance), pgvector (PostgreSQL extension) -- and choose the right one
Design pre-filtering strategies that combine metadata constraints with vector search in a single pass to avoid wasting retrieval budget on out-of-scope documents
This lesson covers the infrastructure that powers every AI search feature you have ever used. It might feel technical, but the core ideas are surprisingly intuitive once you see the analogies. You have got this.
Vector databases do exactly this for embedding vectors. They build clever index structures that let you find the most similar vectors among billions without comparing against every single one. The trade-off: you might occasionally miss the absolute best match, but you find very good matches thousands of times faster.
In the previous lesson, we learned how to convert text to vectors and measure similarity with cosine similarity. But computing cosine similarity between a query vector and every vector in your database is an O(n*d) operation -- linear in both the number of vectors (n) and their dimensionality (d). For a million documents with 1536-dimensional embeddings, that is 1.5 billion floating-point operations per query. For a billion documents, it is 1.5 trillion operations. This is where approximate nearest neighbor (ANN) algorithms and vector databases become essential.
During ingestion, every document chunk is converted to a dense vector using an embedding model. These vectors -- each a list of hundreds or thousands of floating-point numbers -- are stored in the vector database alongside the original text and metadata.
A user asks a question: "How do I reset my password?" This raw text needs to be compared against millions of stored document vectors to find the most relevant ones.
The query is passed through the same embedding model used during ingestion. This produces a query vector in the same high-dimensional space as the document vectors. Now the question and all documents exist as points on the same map.
Instead of comparing the query against every stored vector (brute force), the database uses an approximate nearest neighbor algorithm like HNSW. It starts at the top layer of a hierarchical graph, greedily navigates toward the query's neighborhood, and drops through layers for finer-grained search -- examining only thousands of candidates out of millions.
The search returns the K vectors closest to the query (typically K = 5 to 20). Each result includes a similarity score indicating how close the match is. These are the document chunks whose meaning is most similar to the query.
The vector database looks up the original text and metadata associated with each returned vector. The chunk text, source document name, page number, and any other metadata are sent back to the RAG pipeline, which feeds them to the LLM as context for generating an answer.
At small scale (under 100K vectors), brute-force search is perfectly fine. Many RAG prototypes work this way. But production systems with millions to billions of vectors need something smarter.
Try it! Install ChromaDB (pip install chromadb) and add 10 short text snippets. Search with a question and see the results ranked by similarity. You just used a vector database. Now imagine doing this with 10 million documents -- that is why the indexing algorithms below exist.
Hierarchical Navigable Small World (HNSW) is the most popular indexing algorithm for vector search. It builds a multi-layered graph where each vector is a node, connected to its nearest neighbors.
What Do You Think?
If you have a billion vectors and need to find the 10 most similar, how many vectors does HNSW typically compare against?
Try it: Watch HNSW navigate the graph to find your answerInteractive
Loading visualization...
HNSW typically examines only a few thousand candidates to find near-optimal results among billions. Here is how it works:
Random subsets of nodes are promoted to higher layers, forming a hierarchy. Layer 1 might have 10% of nodes. Layer 2 might have 1%. The top layer has very few nodes but provides long-range connections -- like highways connecting distant cities.
To find nearest neighbors, start at the top layer. Greedily move to the closest node. Drop to the next layer. Greedily move again. Each layer provides finer granularity. By the time you reach Layer 0, you are in the right neighborhood and only need local refinement.
The hierarchy creates "skip connections" across the vector space. Without them, you would need to traverse many local edges to get from one side to the other. With the highway layers, you can jump across the space in a few hops, then refine locally. This is what makes search logarithmic rather than linear.
Both HNSW and IVF can be combined with Product Quantization (PQ) to dramatically reduce memory usage. PQ compresses each vector from, say, 1536 floats (6 KB) down to 48-192 bytes.
Brute-force search is impractical at scale. Comparing a query vector against millions of stored vectors is too slow for production; approximate nearest neighbor (ANN) algorithms trade tiny accuracy losses for massive speed gains
HNSW is the most popular ANN index. Hierarchical Navigable Small World graphs enable sub-millisecond search over millions of vectors by building a multi-layer graph structure for efficient traversal
Product quantization compresses vectors for memory efficiency. By splitting vectors into subgroups and quantizing each separately, PQ dramatically reduces memory usage while maintaining good search quality
Choose your vector database based on scale and requirements. ChromaDB for prototyping, pgvector for PostgreSQL-based systems, Pinecone/Weaviate for managed scale, and FAISS/Qdrant for high-performance self-hosted deployments
The 2026 landscape stabilized: pgvector for <10M and Postgres-native shops, Qdrant or Weaviate for self-hosted with filtering, Pinecone serverless for pay-as-you-go, LanceDB for embedded/edge, and Vespa for late-interaction / ColPali workloads.
DB
Best for
Index
Filtering
Hybrid
Late-interaction (ColBERT/ColPali)
Pricing model
pgvector 0.7+
Postgres shops, <10M vec
HNSW + IVFFlat
SQL where
via tsvector
no
self-host
Qdrant 1.10+
self-hosted, rich filters
HNSW + scalar/int8
yes (payload index)
yes
yes (multi-vector)
self-host or cloud
Weaviate 1.25+
hybrid + ColBERT
HNSW
yes
native (alpha param)
yes (since 2024)
self-host or cloud
Pinecone Serverless
pay-as-you-go, no ops
proprietary
yes
sparse-dense built-in
partial
$0.03 / M reads
Vespa
Yahoo/Spotify-scale, late-interaction
HNSW + tensor
yes (YQL)
first-class
mature
self-host or cloud
LanceDB
embedded, edge, local
IVF-PQ + diskANN
yes
yes
partial
self-host (zero infra)
Milvus 2.4+
distributed, billion-scale
HNSW + IVF + DiskANN
yes
yes
partial
self-host or Zilliz Cloud
Turbopuffer
object-storage-backed, cheap cold
proprietary on S3
yes
partial
no
$0.04 / M reads (~70% cheaper)
ChromaDB
prototyping, single-process
HNSW
yes
partial
no
self-host, in-process
Rules of thumb that hold up in 2026:
< 1M vectors and Postgres in stack: just use pgvector. The latency and ops simplicity win.
Need ColPali / multi-vector retrieval: Vespa, Weaviate, or Qdrant 1.10+.
Going from zero queries to 10M queries this month: Pinecone Serverless (pay-as-you-go).
Cold-tier vectors (rarely queried, must be cheap to keep): Turbopuffer or LanceDB-on-S3.
Why can't we use brute-force cosine similarity search at scale?
You now understand how vectors are stored and searched efficiently. But we skipped a crucial step: how do you turn large documents into the right-sized chunks for embedding? Next up: Chunking Strategies -- the often-overlooked step that makes or breaks RAG quality.