What is the ideal database that allows fast cosine distance?

Question

I'm currently trying to store many feature vectors in a database so that, upon request, I can compare an incoming feature vector against many other (if not all) stored in the db. I would need to compute the Cosine Distance and only return, for example, the first 10 closest matches. Such vector will be of size ~1000 or so.

Every request will have a feature vector and will need to run a comparison against all feature vectors belonging to a subset within the db (which will most likely be in the order of thousands of entries per subset in the worst case scenario).

Which database offers the flexibility to run such a query efficiently ?

I looked into postgres but I was wondering if there were alternatives that better fit this problem. Not sure it matters much, but I'm most likely going to be using Python.

I found this article about doing it in SQL.

EDIT: I am open to alternative solutions for this problem that are not necessarily tied to SQL.

Answer 1

If it's only a few thousand entries each with a 1,000 features, you may just be able to keep it in RAM if you are running this on some kind of server. Then when you get a new feature vector, just run cosine similarity routine. An easy way to do this is just use something standard like pandas and scikit-learn.

Alternatively you can keep everything in SQL, load it into something like pandas and use scikit-learn.

I'm actually not sure you'll get much of a speed up, if any, by writing the computation in SQL itself.

Answer 2

If you need to scale beyond 1000 entries in the future, a brute-force approach to find the exact neighbors will become increasingly prohibitive from a computational standpoint. To future-proof your solution, I would recommend looking into the well-researched field of approximate nearest neighbors (ANN) techniques. Obviously there is a speed/accuracy tradeoff, but as of this writing, there is really no other way to scale your search to millions or billions of entries.

The big tech companies rely almost exclusively on techniques like these. Think about...

• Facebook querying similar faces to suggest people to tag in your photos
• Spotify recommending semantically similar songs
• Google searching images similar to one you uploaded

This article is an excellent overview of current state-of-the-art algorithms along with their pros and cons. Below, I've linked several popular open-source implementations. All 3 have Python bindings

• Facebook FAISS
• Spotify Annoy
• Google ScaNN

Answer 3

If you are afraid that the dataset is big that a regular database might not handle it, you could consider an alternative implementation such as SimHash.

From Wikipedia,

In computer science, SimHash is a technique for quickly estimating how similar two sets are. The algorithm is used by the Google Crawler to find near duplicate pages. It was created by Moses Charikar.

Here is the research paper from Google and here several implementations in Python

Answer 4

A brute force approach has O(n) search complexity no matter if you do it in Python or a database. For faster queries you need a tree-structured multidimensional lookup table, for example, a k-d tree. For Python, there are implementations of a k-d tree in both SciPy and Scikit-Learn:

• https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.KDTree.html
• https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KDTree.html

If you need a standalone database solution, see:

• PostgreSQL with Cube extension supplemented with a GIST index created on a table for fast vector queries, details: https://dba.stackexchange.com/a/163915/177276
• ElasticSearch with its cosineSimilarity function, read more here; possibly extended with this plugin for speedup - although both perform an exhaustive search.
• A dedicated DB solution for vector similarity search, like AquilaDB that utilizes Facebook's FAISS and Spotify's Annoy libraries internally.

Answer 5

1. Is there a reason why you need to do this in SQL? Most architecture patterns would advise against keeping formulas and logic in the database layer. Why not create another layer - outside the database - with a language that can do the computations you need?
2. You can also do the calculations ahead of time and store them in a cached lookup table on the database. Do all the computations you need and then import them into your database and then just run standard SQL SELECT statements to pull the results at run-time.

Answer 6

See: Vector Similarity Search with Azure SQL database and OpenAI

/*
    From GitHub project: Azure-Samples/azure-sql-db-openai
*/
ALTER   function [dbo].[SimilarContentArticles](@vector nvarchar(max))
returns table
as
return with cteVector as
(
    select 
        cast([key] as int) as [vector_value_id],
        cast([value] as float) as [vector_value]
    from 
        openjson(@vector)
),
cteSimilar as
(
select top (5)
    v2.ArticleDetailId, 
    sum(v1.[vector_value] * v2.[vector_value]) / 
        (
            sqrt(sum(v1.[vector_value] * v1.[vector_value])) 
            * 
            sqrt(sum(v2.[vector_value] * v2.[vector_value]))
        ) as cosine_distance
from 
    cteVector v1
inner join 
    dbo.ArticleVectorData v2 on v1.vector_value_id = v2.vector_value_id
group by
    v2.ArticleDetailId
order by
    cosine_distance desc
)
select 
    (select [ArticleName] from [Article] where id = a.ArticleId) as ArticleName,
    a.ArticleContent,
    a.ArticleSequence,
    r.cosine_distance
from 
    cteSimilar r
inner join 
    dbo.[ArticleDetail] a on r.ArticleDetailId = a.id

Answer 7

would be one that uses an inverted index and stores the vectors in a compact format such as sparse vectors or quantized vectors.