Similarity Search & Indexing

Similarity search is the core operation of a vector database, finding the closest vectors in high-dimensional space to a given query vector. Unlike relational database searches that rely on exact matching, vector database retrievals are approximate and probabilistic, relying on coordinate geometry distance metrics.

📐 1. Distance Metrics

The choice of distance metric dictates how similarity is calculated in coordinate space. It must match the metric used during the training phase of the embedding model.

Euclidean Distance (L2)

Measures the straight-line distance between two points in Euclidean space:

\[d(\mathbf{u}, \mathbf{v}) = \sqrt{\sum_{i=1}^{n} (u_i - v_i)^2}\]

• Properties: Always positive. Values range from 0 (identical) to \infty.
• Best For: Dense vectors where the absolute magnitude of individual dimensions is highly meaningful (e.g., coordinates, physical measurements).

Cosine Similarity

Measures the cosine of the angle between two vectors, ignoring their absolute magnitudes:

\[\text{sim}(\mathbf{u}, \mathbf{v}) = \frac{\mathbf{u} \cdot \mathbf{v}}{\|\mathbf{u}\| \|\mathbf{v}\|} = \frac{\sum_{i=1}^{n} u_i v_i}{\sqrt{\sum_{i=1}^{n} u_i^2} \sqrt{\sum_{i=1}^{n} v_i^2}}\]

• Properties: Scale-invariant. Values range from -1 (opposite) to 1 (identical).
• Best For: Document search and natural language embeddings, where document length (vector magnitude) should not bias the relevance score.

Dot Product (Inner Product)

Calculates the sum of products of corresponding coordinates:

\[\text{sim}(\mathbf{u}, \mathbf{v}) = \mathbf{u} \cdot \mathbf{v} = \sum_{i=1}^{n} u_i v_i\]

• Properties: Computationally cheap (no square root or division).
• Best For: Recommendation systems. When vectors are normalized to unit length (\|\mathbf{u}\| = 1), the Dot Product is mathematically equivalent to Cosine Similarity.

🗂️ 2. Index Structures & Parameters

To search millions of vectors in milliseconds, databases build index graphs or trees.

HNSW (Hierarchical Navigable Small World)

HNSW builds a multi-layer graph structure where the top layers contain sparse connections (fast routing across long distances) and the bottom layers contain dense connections (detailed nearest-neighbor search).

• M (Max connections per node): Higher values increase recall accuracy on complex high-dimensional spaces but increase memory usage and index build times. Typical values: 8 to 64.
• ef_construction (Search depth during construction): Controls graph build quality. Higher values increase search accuracy but slow down indexing writes. Typical values: 64 to 512.
• ef_search (Search depth during query): Dynamic parameter specifying candidate list size during query traversal. Increasing ef_search improves search recall at the cost of query latency.

Production pgvector HNSW Schema (PostgreSQL)

-- Enable pgvector extension
CREATE EXTENSION IF NOT EXISTS vector;
 
-- Create table with vector column (e.g. OpenAI 1536 dimensions)
CREATE TABLE document_embeddings (
    id BIGSERIAL PRIMARY KEY,
    document_id UUID NOT NULL,
    content TEXT NOT NULL,
    embedding vector(1536) NOT NULL,
    metadata JSONB
);
 
-- Construct HNSW index optimizing for Cosine Distance
-- M=16, ef_construction=64
CREATE INDEX ON document_embeddings 
USING hnsw (embedding vector_cosine_ops) 
WITH (m = 16, ef_construction = 64);

IVF (Inverted File Index)

IVF divides vector space into Voronoi cells using k-means clustering.

• nlist (Number of cluster centroids): Determines partition granularity.
• nprobe (Number of centroids to search during query): Controls query precision. Increasing nprobe searches more clusters, increasing recall accuracy but increasing latency.

🚦 3. Metadata Filtering Topologies

Production queries combine vector search with structured metadata filters (e.g., matching a vector and checking permissions or date ranges).

Filtering Topologies Comparison

1. Pre-Filtering: Evaluates metadata constraints first, then performs vector search on the filtered subset. Fails to leverage indexes if the filtered subset is large; can result in full table scans.
2. Post-Filtering: Performs standard vector search first, retrieving the top k candidates, and then filters out entries that do not match metadata constraints. Can return far fewer than k results (or even zero results) if metadata filters are highly restrictive.
3. Single-Stage (Iterative) Filtering: The search algorithm traverses the index graph, dynamically evaluating metadata constraints at each node. Preserves both high recall and low query latency. (Native in Qdrant and Pinecone).

🔗 4. Hybrid Search & Retrieval Fusion

Pure semantic search can fail on exact keyword queries (like product IDs or specific log codes). Modern architectures combine Dense Retrieval (capturing meaning) and Sparse Retrieval (exact keyword matching, e.g., BM25) and merge their results using Reciprocal Rank Fusion (RRF).

Hybrid Retrieval & Reranking Architecture

Reciprocal Rank Fusion (RRF) Python Implementation

RRF aggregates rankings from different search systems without requiring score normalization. It calculates an RRF score for each document based on its ranks in the dense and sparse result lists:

from typing import List, Dict, Tuple
 
def reciprocal_rank_fusion(
    dense_results: List[str],  # List of Doc IDs ordered by dense relevance
    sparse_results: List[str], # List of Doc IDs ordered by sparse relevance
    k: int = 60                # Constant parameter mitigating outlier ranks
) -> List[Tuple[str, float]]:
    rrf_scores: Dict[str, float] = {}
 
    # 1. Score dense results
    for rank, doc_id in enumerate(dense_results, start=1):
        rrf_scores[doc_id] = rrf_scores.get(doc_id, 0.0) + (1.0 / (k + rank))
 
    # 2. Score sparse results
    for rank, doc_id in enumerate(sparse_results, start=1):
        rrf_scores[doc_id] = rrf_scores.get(doc_id, 0.0) + (1.0 / (k + rank))
 
    # 3. Sort candidates by fused score
    sorted_results = sorted(rrf_scores.items(), key=lambda item: item[1], reverse=True)
    return sorted_results
 
# Example usage:
# dense_list = ["doc_1", "doc_2", "doc_3"]
# sparse_list = ["doc_3", "doc_1", "doc_5"]
# fused = reciprocal_rank_fusion(dense_list, sparse_list)
# print(fused)

🔄 5. Index Lifecycle Management

As embedding models evolve, database indexes must be migrated. Changing models requires regenerating embeddings for the entire corpus. Use a Blue/Green Index Migration workflow to update indexes without downtime:

Migration Operational Steps

1. Dual Writing: Configure your ingestion worker queue to write incoming documents to both the active v1 index and the new v2 index simultaneously.
2. Backfilling: Run a background batch process to extract documents, pass them to the v2 embedding model, and write them to the v2 index.
3. Validation: Run parallel tests comparing v1 and v2 recall accuracy before switching traffic.
4. Traffic Shift: Update the API gateway router to point query traffic to the v2 index.
5. Deprecation: Delete the v1 index segment to reclaim storage.

🛠️ 6. Retrieval Quality Debugging Playbook

When an LLM produces a hallucination or fails to answer a query, trace the retrieval path using the playbook workflow below:

Common Failure Points

• Poor Chunking: Chunks are too small (context is fragmented) or too large (noise degrades vector similarity).
• Metadata Filter Errors: Filters are overly restrictive (blocking correct matches) or lack index keys (causing slow scans).
• Reranking Decay: The reranker model drops highly relevant semantic chunks because it was not fine-tuned on the domain jargon.

🔗 Related Sections

• Understanding Vector Databases — Storage layers, client connection pools, quantization parameters, and 2026 stack choices.
• RAG Anatomy — Pipeline integration of retrieval databases into generation workflows.
• Agent Security & Guardrails — How to handle row-level security and access control boundaries.