Speeding up vector recall 5x with HNSW

Author

Silas Marvin

October 2, 2023

PostgresML makes it easy to use machine learning with your database and to scale workloads horizontally in our cloud. Our SDK makes it even easier.

HNSW (hierarchical navigable small worlds) is an indexing method that greatly improves vector recall

Introducing HNSW

Underneath the hood our SDK utilizes pgvector to store, index, and recall vectors. Up until this point our SDK used IVFFlat indexing to divide vectors into lists, search a subset of those lists, and return the closest vector matches.

While the IVFFlat indexing method is fast, it is not as fast as HNSW. Thanks to the latest update of pgvector our SDK now utilizes HNSW indexing, creating multi-layer graphs instead of lists and removing the required training step IVFFlat imposed.

The results are not disappointing.

Comparing HNSW and IVFFlat

In one of our previous posts: Tuning vector recall while generating query embeddings in the database we were working on a dataset with over 5 million Amazon Movie Reviews, and after embedding the reviews, performed semantic similarity search to get the closest 5 reviews.

Let's run that query again:

content_copy link edit
WITH request AS (
SELECT pgml.embed(
'intfloat/e5-large',
'query: Best 1980''s scifi movie'
)::vector(1024) AS embedding
)
SELECT
id,
1 - (
review_embedding_e5_large <=> (
SELECT embedding FROM request
)
) AS cosine_similarity
FROM pgml.amazon_us_reviews
ORDER BY review_embedding_e5_large <=> (SELECT embedding FROM request)
LIMIT 5;
timer 89.118 ms
review_body product_title star_rating total_votes cosine_similarity
best 80s SciFi movie ever The Adventures of Buckaroo Banzai Across the Eighth Dimension 5 1 0.9495371273162286
the best of 80s sci fi horror! The Blob 5 2 0.9097434758143605
Three of the best sci-fi movies of the seventies Sci-Fi: Triple Feature (BD) [Blu-ray] 5 0 0.9008723412875651
best sci fi movie ever The Day the Earth Stood Still (Special Edition) [Blu-ray] 5 2 0.8943620968858654
Great Science Fiction movie Bloodsport / Timecop (Action Double Feature) [Blu-ray] 5 0 0.894282454374093

This query utilized IVFFlat indexing and queried through over 5 million rows in 89.118ms. Pretty fast!

Let's drop our IVFFlat index and create an HNSW index.

content_copy link edit
DROP INDEX index_amazon_us_reviews_on_review_embedding_e5_large;
CREATE INDEX CONCURRENTLY ON pgml.amazon_us_reviews USING hnsw (review_embedding_e5_large vector_cosine_ops);
timer 10255099.233 ms (02:50:55.099)

Now let's try the query again utilizing the new HNSW index we created.

content_copy link edit
WITH request AS (
SELECT pgml.embed(
'intfloat/e5-large',
'query: Best 1980''s scifi movie'
)::vector(1024) AS embedding
)
SELECT
id,
1 - (
review_embedding_e5_large <=> (
SELECT embedding FROM request
)
) AS cosine_similarity
FROM pgml.amazon_us_reviews
ORDER BY review_embedding_e5_large <=> (SELECT embedding FROM request)
LIMIT 5;
timer 17.465 ms
review_body product_title star_rating total_votes cosine_similarity
best 80s SciFi movie ever The Adventures of Buckaroo Banzai Across the Eighth Dimension 5 1 0.9495371273162286
the best of 80s sci fi horror! The Blob 5 2 0.9097434758143605
One of the Better 80's Sci-Fi Krull (Special Edition) 3 5 0.9093884940741694
Good 1980s movie Can't Buy Me Love 4 0 0.9090294438721961
great 80's movie How I Got Into College 5 0 0.9016508795301296

Not only are the results better (the cosine_similarity is higher overall), but HNSW is over 5x faster, reducing our search and embedding time to 17.465ms.

This is a massive upgrade to the recall speed utilized by our SDK and greatly improves overall performance.

For a deeper dive into HNSW checkout Jonathan Katz's excellent article on HNSW in pgvector.

Have Questions?

Join our Discord and ask us anything! We're friendly and would love to talk about PostgresML and PgCat.

Try It Out

Try PostresML using our free serverless cloud. It comes with GPUs, 5 GiB of space and plenty of datasets to get you started.