90x sooner than pgvector — Lantern’s HNSW Index Creation Time

2024-01-02 12:21:03

Lantern is a Postgres extension to allow performant vector search utilizing an index. Lantern is constructed utilizing Usearch, an optimized C++ implementation of the HNSW algorithm, essentially the most performant algorithm for vector search.

On this put up we focus on the importance of index creation instances and the way Lantern permits 90x sooner index creation instances than pgvector, one other common vector search Postgres extension, utilizing exterior indexing. We additionally examine Lantern’s efficiency in opposition to Pinecone, a preferred, closed-source hosted vector database.

Why quick index creation issues

Index creation time impacts how shortly a developer can add vector search to their information. On a single core, producing an index on 1 billion vectors might take days and even weeks.

It additionally impacts how shortly a developer can experiment with totally different parameters to optimize their index. HNSW depends on two parameters for index development:

The M parameter controls the variety of neighbors that every node within the graph will preserve. Larger values result in longer development instances, longer question instances, and better reminiscence utilization, however lead to a higher-quality index.
The ef_construction parameter determines what number of nodes will probably be traversed throughout index development. Larger values result in longer development instances however lead to a higher-quality index.

Usually, there’s a tradeoff between recall and latency. The perfect set of parameters requires experimentation to search out. It will depend on the appliance’s recall / latency wants and the information itself (what recall is feasible given the information distribution). This experimentation might turn out to be untenable with gradual index creation instances.

How exterior index creation permits parallelism

With Postgres, HNSW index creation is single-threaded. This prevents the utilization of a number of cores to hurry up index creation. As well as, the index creation course of is resource-intensive, which may decelerate different database operations. The latter would pose an issue even when HNSW index creation have been multi-threaded.

Lantern permits builders to create an index externally, after which import the index as a file into their database. With exterior index creation, the core database stays unburdened throughout index creation, and the index will be created utilizing a number of cores. This allows vital efficiency enhancements.

Beneath we present the outcomes of two units of experiments with Lantern: one with index creation occurring inside Postgres, and one with index creation occurring externally. We examine Lantern’s efficiency in opposition to pgvector and Pinecone.

Lantern’s single-core index creation efficiency

Experiment Setup

We use the next datasets

sift – 1 million vectors of 128 dimensions, downloadable here
wiki – 1 million vectors of 1536 dimensions generated utilizing the text-embedding-ada-002 mannequin

The experiments have been run on a Linode occasion with 32 Cores and 64GB of RAM.

The SQL to create a desk, copy the information, and create the index utilizing Lantern follows

CREATE TABLE wiki1m (id SERIAL, v REAL[]);
COPY wiki1m (v) FROM '/tmp/wiki1m.csv' WITH CSV;
CREATE INDEX ON wiki1m USING hnsw (v) WITH (dim=128, m=8, ef_construction=128, ef=128);

Desk: Index Creation Occasions for Sift

Desk: Index Creation Occasions for Wiki

Graph: Index Creation Velocity

Utilizing exterior index creation, Lantern is 90x sooner than pgvector

Outcomes Overview

17x efficiency enchancment in comparison with creating the index on a single thread.
90x efficiency enchancment in comparison with pgvector, and a 6x enchancment over Pinecone for sift dataset
48x efficiency enchancment over pgvector, in addition to a 3x enchancment over Pinecone with 32 pods
Pinecone index on 32 p2 pods prices $3,889.44 / month. 32 CPU Linode prices $576 / month. Lantern is over 6x cheaper and 6x sooner!

Graph: Index Creation Velocity with 32 Cores

Graph: Index Creation Velocity with 2 – 32 Cores

Positive-tuning the recall utilizing parameters m=16, ef_construction=128, and ef=128 for Lantern, we are able to obtain a 99% recall@5 for sift dataset, with the index creation taking solely 50 seconds.

Discover {that a} 2 Core Linode Server working Lantern outperforms Pinecone’s 32 pod cluster – because of this Lantern will be 60x cheaper than Pinecone for a similar efficiency.

Exterior index creation with Lantern

Implementation Particulars

Here’s a transient overview of how Lantern’s exterior index creation works below the hood.

We use the row’s ctid as a label for our nodes throughout index creation. Later, this label is used to retrieve the precise row from Postgres, because it represents the bodily location of the row.

We use Postgres’s large object performance for information switch. We use the lo_export operate to export the indexable information to the file system. After producing the index utilizing Usearch on the file system, we then use the lo_import operate to switch the index file to the database server.

How one can use exterior index creation

Set up the Lantern CLI
Create an index from an everyday Postgres desk through the create-index utility

Here’s a stroll via:

First, set up the Lantern CLI:

cargo set up --git https://github.com/lanterndata/lantern_extras --bin lantern-cli

Subsequent, use the create-index utility to externally create and import our index to Postgres:

Word: In the event you encounter ONNXRuntime, points, arrange onnx runtime manually utilizing these steps and export the required env variables.

lantern-cli create-index 
    --uri postgresql://postgres@localhost:5432/testlive 
    --table sift 
    --column v 
    -m 8 
    --efc 128 
    --ef 64 
    -d 128 
    --metric-kind cos 
    --out index.usearch 
    --import

The --uri parameter specifies the database connection URI, and the --table and --column parameters specify the desk and column to index. The index parameters are -m, --efc, --ef, -d (dimension of column), and --metric-kind (l2sq, cos, or hamming). The --out parameter specifies the output file identify. If --import can also be specified, the externally created index will probably be mechanically imported to Postgres after creation, and the short-term output file will probably be eliminated.

The desk will probably be completely locked in the course of the index creation course of to keep away from inconsistency. To reindex the information, use choose lantern_reindex_external_index('<index_name>'); in case you have lantern_extras extension put in in your database, or use the identical CLI command as above and supply the --index-name argument. Within the latter case, the prevailing index will probably be dropped and a brand new one will probably be created.

Conclusion

On this put up, we mentioned the importance of index creation instances, Lantern’s exterior indexing course of, and shared our benchmarking outcomes in opposition to pgvector and Pinecone.

For a deeper dive into the code, you possibly can try our core repo or the Lantern Extras repo. Our core repo permits vector search in Postgres, whereas Lantern Extras offers routines for exterior index era and embedding administration.

Source Link