Need help with pgANN?
Click the “chat” button below for chat support from the developer who created it, or find similar developers for support.

About the developer

netrasys
147 Stars 9 Forks MIT License 25 Commits 2 Opened issues

Description

Fast Approximate Nearest Neighbor (ANN) searches with a PostgreSQL database.

Services available

!
?

Need anything else?

Contributors list

pgANN

Approximate Nearest Neighbor (ANN) searches using a PostgreSQL backend.

Background

Approximate Nearest Neighbor approaches are a powerful tool for various AI/ML tasks, however many existing tools (faiss,Annoy, Nearpy etc.) are "in memory"i.e. the vectors needed to be loaded into RAM, and then model trained therefrom. Furthermore, such models once trained could not be updated i.e. any CRUD operation necessitates a fresh training run.

The challenge for us was to: - hold extremely large datasets in memory and - support CRUDs which makes it challenging in an "online" environment where fresh data is continuously accumulated.

We are open-sourcing a simple, but effective approach that provides ANN searches using the powerful PostgreSQL database. At Netra we use this tool internally for managing & searching our image collections for further processing and/or feed into our Deep learning models. We consistently see

sub-second
response times on the order of a few million rows on a 32Gb/8 vcpu Ubuntu 16 box. We hope this is of use to the AI community.

Feedback and PRs very welcome!

Advantages

  • leverages postgres database queries & indexes (no additional tooling needed)
  • associated metadata is fetched alongwith the "neighbors" (i.e. fewer moving parts)
  • no re-training needed for CRUDs due to query time ranking ("online mode")
  • should scale with tried & tested database scaling techniques (partioning etc.)

Challenges

  • cube
    type doesn't seem to work for > 100 dimensions, so we need to perform dimensionality reduction. Example for dim. reduction included in the sample code
  • haven't tested with sparse vectors, but in theory should work decently with appropriate dimensionality reduction techniques
  • pgANN might not perform as accurately as some of the better known approaches, but you can use pgANN to fetch a subset of (say) a fw thousand and then
    rerank
    based on your favorite metric. Unfortunately, there are no easy wins in ANN approaches, hopefully pgANN gets you a "good enough" subset for your reranking.

Update Oct 2, 2019: There is a docker instance available here that claims "Postgres DB docker image with increased limit for CUBE datatype (set to 2048)". I haven't had a chance to try it, but this seems pretty useful (Credit due to @andrey-avdeev for this suggestion.)

Requirements

  • Postgres 10.x+ or higher (we haven't tested on PG 9.6+, but
    cube
    ,
    GIST
    and distance operators are available on 9.6+, so it might work)
  • Cube extension from Postgres

Setup

  1. Make sure you are logged in as superuser into pg and run:

    create extension cube;
  2. We shall use the example of an

    images
    table to illustrate the approach, the images table stores the url, any metadata tags, vectors and the embeddings for the vectors in the table. You can of course modify table structure to your needs.
CREATE TABLE images(
   id serial PRIMARY KEY,
   image_url text UNIQUE NOT NULL,
   tags text,
   vectors double precision[],
   embeddings cube   
);
  1. Create a GIST index on the embeddings column which stores a 100-dimensional embedding of the original vector:

create index ix_gist on images using GIST (embeddings);

Note: you might need to create other indexes (b-tree etc.) on other fields for efficient searching & sorting, but that's outside our scope

Populating db

Now we are ready to populate the database with vectors and associated embeddings.

Note: we are using the dataset library for interfacing with postgres, but this should work just as well with your favorite driver (psycopg2 etc.)

db = dataset.connect('postgresql://user:[email protected]@localhost:5432/yourdb')
tbl = db['images']

for image in images: vect = get_image_vector(image) #

Querying

We can start querying the database even as population is in progress

    query_vector = [...]
    query_emb = get_embedding(query_vector)
    thresh = 0.25 #  cube({0}) < thresh order by embeddings  cube({0}) asc limit 10".format((emb_string))
    results = db.query(sql)
    for result in results:
      print(result['url'], result['tags'])

Note: pgsql cube extension supports multiple distance parameters. Here is a quick summary:

  •  Euclidean distance
    ,
  • <=> Chebyshev (L-inf metric) distance
    , and
  •  Taxicab distance
    .

More details here.

## Improving Performance

Here are some steps you can use to squeeze more performance out of pgANN:

  • Reduce dimensionality (using
    UMAP
    ,
    t-SNE
    or
    ) and using that as an embedding
  • Horizontal partitioning data across multiple tables and using parallelism to combine results
  • Use some hashing technique (
    LSH/MinHash
    for example) to create a common signature for each row and use it as a filter during your query (reducing the lookup space)
  • Try different distance operators (
    Euclidean
    , vs
    Chebyshev
    vs
    Taxicab
    ),
  • Remove sorting from your query. e.g
    sql = "select id,embeddings from images where embeddings  cube({0}) <0.5".format((emb_string))

In these cases, you will need to fetch a significant N from the DB query and then re-rank based on your favorite similarity metric. Some combination of those might get you to some query times you can live with. Unfortunately ANN is largely ignored by the AI/DL community and there is significant research that needs to happen.

We use cookies. If you continue to browse the site, you agree to the use of cookies. For more information on our use of cookies please see our Privacy Policy.