HNSW Indexing for Recall

Welcome to HNSW indexing! In the previous lesson, we explored IVFFlat for speed. Now, we'll dive into Hierarchical Navigable Small World (HNSW), an advanced indexing technique in pgvector.

HNSW is excellent when you need to find most of the relevant results, even if it means a slight trade-off in query speed compared to IVFFlat. This is known as high recall.

Remember IVFFlat indexes? They partition data for faster, approximate searches, optimizing for speed. HNSW takes a different approach to prioritize recall.

• IVFFlat: Faster queries, good enough recall.
• HNSW: Higher recall (finds more true positives), potentially slower build and query times.

Choosing between them depends on your application's needs: speed or comprehensive results.

Imagine HNSW as a multi-layered graph. It connects similar vectors across different layers:

• Top layers: Sparse graphs, quickly navigate large distances.
• Bottom layers: Dense graphs, fine-tune search for nearest neighbors.

This structure allows for efficient approximate nearest neighbor (ANN) search, quickly narrowing down the search space to find highly similar vectors.

To use HNSW, you first need the pgvector extension. Then, you can create an HNSW index on your vector column. Here's the basic syntax:

CREATE INDEX ON items USING HNSW (embedding vector_l2_ops);

The vector_l2_ops specifies using L2 (Euclidean) distance. Other operators like vector_cosine_ops for cosine similarity are also available.

The m parameter determines the maximum number of connections a node (vector) has in the HNSW graph on each layer. It's crucial for index quality:

• Higher m: More connections, better recall, but increases index size and build time.
• Lower m: Fewer connections, smaller index, faster build, but lower recall.

A common value for m is between 8 and 16, but it depends on your dataset and desired accuracy.

The ef_construction parameter controls the size of the dynamic candidate list during graph construction. It impacts how thoroughly the index is built:

• Higher ef_construction: More thorough search during build, better index quality (higher recall), but significantly slower build time.
• Lower ef_construction: Faster build, but potentially lower recall.

It's generally recommended to set ef_construction to a value 2-4 times m, or even higher for very high recall needs.

Let's create a table and then an HNSW index with specific parameters. This example uses m=16 and ef_construction=64.

Once your HNSW index is built, pgvector automatically uses it for similarity queries. The query syntax is the same as for other vector indexes:

SELECT id, embedding <-> '[1,2,3]' AS distance FROM docs ORDER BY distance LIMIT 3;

However, HNSW introduces another parameter at query time: ef_search.

The ef_search parameter controls the size of the dynamic candidate list during the actual search operation. You set this via a session variable:

• Higher ef_search: More thorough search at query time, higher recall, but slower query execution.
• Lower ef_search: Faster queries, but potentially lower recall.

You typically set ef_search equal to or higher than ef_construction for optimal results, or tune it based on real-world query performance.

While HNSW offers superior recall, it comes with trade-offs:

• Memory Usage: HNSW indexes are generally larger and consume more memory than IVFFlat.
• Build Time: Index creation can be significantly slower, especially with high m and ef_construction.
• Query Latency: Queries might be slightly slower than IVFFlat, depending on ef_search.

Always test with your specific dataset to find the best balance of parameters for your application.

Which HNSW parameter primarily affects the recall and build time of the index by controlling the thoroughness of the graph construction?

Great job! You've explored HNSW indexing in pgvector.

• HNSW prioritizes recall, aiming to find most relevant results.
• It works by building a multi-layered graph structure.
• Key parameters are m (max connections) and ef_construction (build thoroughness).
• ef_search tunes query-time recall and speed.
• HNSW indexes can be larger and slower to build/query than IVFFlat, but offer higher recall.

Next, we'll learn how to tune queries for optimal performance!