Inverted file index
Following the previous one.
This is also a way to index vectors in a database but it’s relatively simple.
How it works (and the complexity)
D = vector dimension
N= total vectors
K = number of clusters (nlist)
P = number of searched clusters (nprobe).
- Training
Do K-means to generate K clusters and each has a centroid (average of the vectors)
O(T * K * N-train * D)
N-train is the data set size we decide to train on
- Indexing
Create centroid to vector mapping
Centroid id -> List of Vector IDs / Raw Embeddings
Insertion (Single Vector): O(K*D)
Calculate distance to K centroids to find the closest bucket.
Total Build (N Vectors): O(N * K * D) Assigning all N vectors to their centroids.
- Querying, to find Top K vectors closest to the query
a. Pick P closest centroids (scan through all). O(K*D)
b. Scan all the lists and find the closet vectors.: Only scan the raw vectors stored inside those P lists. Each contains N/K vectors -> O(P * N/K *D)
Total: O((K + P * N/K) * D)
IVF v.s. HNSW
- Search Time: IVF is O(sqrt(N)) (usually K = sqrt(N)); HNSW is O(log N) (faster).
- Recall: IVF is moderate (bounded by nprobe); HNSW is very high (bounded by efSearch).
- RAM usage: IVF is low (~1x vector size); HNSW is high (2x-5x vector size for lots of graph edges).
- Build Time: IVF is fast (O(N * K)); HNSW is slow (O(N log N)). O(N * K) is actually > O(N log N), but in real world it’s faster due to simple matrix operation. While HNSW needs priority queues, locks for pointer updates.
- Streaming Inserts: IVF is poor (centroids drift, needs updates ); HNSW is excellent.
- Best For: IVF suits memory-constrained or static data; HNSW suits real-time, low-latency, dynamic applications.
Summary and about pgvector
Anyway, pgvector supports both.
You can easily just add a vector column to a table and select the index you want to use.
But there are pros and cons that you can easily achieve ACID transactions with other columns (compared to a standalong vector database), but vector operations are not cheap, e.g. if you add a new vector column to an existing table, building the index would probably lock the whole table for a while, and it requires extra effort to be smooth.
