liveBook · Manning

HNSW

As explained in Just Use Postgres!

An HNSW index is a graph-based approximate nearest-neighbor index using a hierarchical navigable small-world graph.

HNSW is a graph-based approximate nearest-neighbor index for vector embeddings. In a movie recommendation service, it speeds up searches for films related to a phrase without comparing that phrase with every movie embedding. section 8.0 section 8.5

The index builds a multilayer graph: sparse upper layers provide broad navigation, while denser lower layers contain more connected vectors. Search starts at the highest layer, follows nearby nodes, and descends toward the most relevant region. section 8.5.2

Create an HNSW index for cosine similarity

CREATE INDEX movie_embeddings_hnsw_idx ON omdb.movies USING hnsw (movie_embedding vector_cosine_ops) WITH (m = 8, ef_construction = 16); section 8.5.2

                            QUERY PLAN
-----------------------------------------------------------------
 Limit (actual time=1.889..1.923 rows=3 loops=1)
   InitPlan 1
     ->  Seq Scan on phrases_dictionary
 ➥        (actual time=0.025..0.026 rows=1 loops=1)
           Filter: (phrase = 'May the force be with you'::text)
           Rows Removed by Filter: 3
   ->  Index Scan using movie_embeddings_hnsw_idx on movies
 ➥      (actual time=1.887..1.918 rows=3 loops=1)
         Order By: (movie_embedding <=> (InitPlan 1).col1)
 Planning Time: 0.205 ms
 Execution Time: 1.970 ms
(9 rows)

An execution plan shows the query switching from a sequential scan to an HNSW index scan, reducing the demonstrated execution time to about two milliseconds. section 8.5.2

Use HNSW with these practical expectations:

  • Treat results as approximate: the index compares a query embedding with only a subset of stored embeddings, so recall is not guaranteed to be perfect. section 8.5
  • Remove an alternative vector index when it is no longer needed; the example drops the existing IVFFlat index before creating HNSW. section 8.5.2
  • Increase search accuracy for a query by setting hnsw.ef_search locally to 50 before running the similarity search. section 8.5.2
Listing 8.14 Improving search accuracy with HNSW
BEGIN;
SET LOCAL hnsw.ef_search = 50;

SELECT id, name
FROM omdb.movies
ORDER BY movie_embedding <=> 
  (SELECT phrase_embedding
  FROM omdb.phrases_dictionary
  WHERE phrase = 
  'A movie about a Jedi who fights against the dark side of the force')
LIMIT 3;

COMMIT;

A transaction-scoped setting demonstrates how to trade additional search effort for improved HNSW accuracy. section 8.5.2

How Just Use Postgres! covers it

How deep it goes
Explains graph layers, traversal, index creation, execution plans, recall, and ef_search, without deeper implementation theory.
Examples
Demonstrates movie-embedding searches, PostgreSQL index definitions, execution plans, returned movie rows, and ef_search tuning.
What it assumes
Assumes stored vector embeddings and introduces their use with PostgreSQL vector similarity queries.
What you can do after
Operate/configure HNSW in PostgreSQL, inspect its query plan, and adjust search accuracy with ef_search.
How it connects
Connects HNSW with vector embeddings, approximate nearest-neighbor search, cosine similarity, IVFFlat, pgvector, and RAG.
Cover of Just Use Postgres!
liveBookmanning.com
Read Just Use Postgres! on liveBook Get the book at manning.com

Also explained in

Compare how 7 books explain HNSW →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Just Use Postgres!. The section links point to the parts of the book it draws on.