Fast vector similarity search (PostgreSQL)

A medida que los vector datasets crecen, las similarity queries que escaneen cada fila pueden volverse demasiado lentas. Esto se soluciona mediante vector indexes.

IMPORTANTE

Sin un index, pgvector ejecuta exact nearest-neighbor search. La BBDD calcula la distancia entre el query vector y cada vector de la tabla, entonces devuelve las filas con las distancias más pequeñas. Esto garantiza encontrar el nearest neighbor verdadero, pero el coste computacional crece con el número de filas.

/IMPORTANTE

Para tablas pequeñas (<10.000 rows) sirve el exact nearest-neighbour pero lo que a una tabla con 100.000 vectores le puede llevar 500 ms, a una tabla con 1.000.000 de vectores le puede llevar 5s.

Approximate nearest-neightbour (ANN) search intercambia precisión perfecta por mejora en velocidad. ANN organiza vectores en estructuras que permiten a la BBDD examinar solo un subset de vectores durante las queries. Los resultados pueden fallar a veces y dejarse algunos true nearest neighbours, pero las queries se completan en milisegundos independientemente del tamaño de la tabla.

Choose IVFFlat when:

  • memory usage is a concern
  • faster index builds for frequently changing data
  • trade query performance for lower resource usage
  • slightly lower recall

Choose HNSW when:

  • query performance is your primary concern
  • high recall (99%) with low latency
  • your dataset doesn’t change frequently
  • memory constraints aren’t severe

Inverted File Flat (IVFFlat) indexes

IVFFlat particiona vectores en clusters durante la creación del index. Cuando haces una query, la BBDD identifica los clusters más cercanos a tu query vector y busca solo dentro de esos clusters, en vez de escanear la tabla entera.

Cada cluster tiene un centroid. Esto es la posición media de todos los vectores del cluster. Cuando ejecutas una query, pgvector calcula distancias desde tu query a cada centroid, identifica los clusters más cercanos y busca solo en ellos.

el param lists controla el número de clusters. luego el param vector_cosine_ops tiene que ser el mismo que el distance operator que usemos para las queries <=>, etc

CREATE INDEX documents_embedding_idx ON documents
USING ivfflat (embedding vector_cosine_ops)
WITH (lists = 100);
Operator class Distance opwerator Use case
vector_12_ops <-> L2 Euclidean distance
vector_cosine_ops <=> Cosine distance
vector_ip_ops <#> Negative inner product

IVFFlat indexes requiere que existan datos para entrenar al clustering algorithm. Crear un index en una tabla vacía produce un index que no se puede usar para queries - primero cargar los datos, luego crear el índice. Si la distribución de datos cambia significativamente después de añadir datos puede ser necesario hacer un rebuild del índice

Hierarchical Navigable Small World (HNSW) indexes

HNSW indexes usan una graph structure multi-capa para similarity search. Tiene una mejro performance que IVFFlat, aunque consume más memoria y tiene longer build times.

HNSW construye una graph estructure navegable, en vez de particionar vectores en clusters (como have IVFFlat). HNSW construye un grafo donde cada vector es un nodo conectado a su nearest neighbours, organizados en múltiples capas.
La top layer contiene la menor cantidad de nodos espaciados lejos unos de otros. Cada capa a un nivel más bajo contiene más nodos con conexiones más densas, y la última capa contiene todos los nodos.

Cuando haces una query, el algoritmo comienza en la top layer y navega por el grafo, moviéndose a lower layers a medida que se acerca al query vector. Es un coarse-to-fine approach which narrows down the search space.

el param m es el número máximo de conexiones por nodo en el grafo. el param ef_construction controla el width de la búsqueda durante index building - valores más altos crean indices de mayor calidad pero son más lentos de construir. para PROD usar valores 100-200

CREATE INDEX documents_embedding_idx ON documents
USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 64);

A diferencia de IVFFlat, los indices HNSW se pueden crear en tablas vacías - se hace update de la graph structure a medida que se insertan nuevas filas