Index support for similarity search

[jiashenC]

Goal

Support index creation on columns of table.

SQL Syntax

CREATE INDEX [IF NOT EXISTS] name ON table (column1, column2 ... columnN);

Initial Index Support

I plan to use HNSW index as my starting point, because it requires minimal parameter to create the index. Others all need some sort of parameters.

Discussion Questions

• Should we automatically infer the feature dimension or add some syntax in SQL to mandate that?
• There are different index in FAISS. I think we can easily support that by adding USING method syntax support. I wonder should I support this in the first PR or we can add support later but just support HNSW first?
• Do we just wrap FAISS inside the CreateIndexExecutor or create some things similar to UDF?

User workflow

Image Dataset

1. Create an index on a image dataset

CREATE INDEX IF NOT EXISTS name ON MyImages USING FeatureExtractor(data);

2. Find similar data points in the dataset

SELECT id, data FROM table WHERE similarity(open(source_image_path), data, FeatureExtractor) > 0.8;

Few other queries:
Return Top-5 similar images

SELECT id, data FROM table WHERE similarity(open(source_image_path), data, FeatureExtractor)  STOP AFTER 5;

Search for similar images with threshold of 0.8 and also return top-5

SELECT id, data FROM table WHERE similarity(open(source_image_path), data, FeatureExtractor) > 0.8 STOP AFTER 5;

Video Dataset

1. CREATE a table with all the faces in the video dataset

CREATE MATERIALIZED VIEW IF NOT EXISTS MyFaces (id, data, bbox) 
    AS SELECT id, data, F.bbox FROM video LATERAL JOIN UNNEST(FaceDetector(data).bboxes) AS F(bbox);

2. Create an index on the feature vectors of the faces

CREATE INDEX IF NOT EXISTS faces_index ON MyFaces USING FeatureExtractor(Crop(data, bbox));

3. Reverse face search

SELECT id, bbox FROM MyFaces WHERE similarity(open(source_face_path), Crop(data, bbox), FeatureExtractor) > 0.8;

Feature requirements

1. Support CREATE INDEX command on features (FunctionalExpression) using faiss. In the first version, we can hardcode a fixed index type. In the future, we can support adding more parameters based on which index faiss index type to pick. Note, additionally, we need to keep a reverse mapping from faiss index number to the source table.
2. Automatically replace the similarity predicate to an index scan using faiss. This requires matching the FunctionalExpression, retrieving the matched features from faiss, using reverse mapping to get source table row_id, and lastly using row_id to get the source table row. Since we will use primary keys for the reverse mapping, we can leverage indexes to speed up the retrievals.
3. similarity keyword: similarity(data1, data2, UDF, METRIC) - We can set the default value of metric to euclidean. Can easily provide metrics supported by faiss.
4. If no index is available, we evaluate the similarity predicate and return the results.

Future Support

1. Store compressed vectors on disk to save space in the create materialized command.
2. Advanced query:

SELECT id, bbox FROM MyFaces WHERE similarity(select data from MyImages WHERE name = "dog.png" , Crop(data, bbox), FeatureExtractor) > 0.8;

[jiashenC]

@gaurav274 @pchunduri6 @xzdandy @jarulraj

[jiashenC]

Two questions after the draft change by @gaurav274.

1. Is similarity() > 0.8 practical for users? First of all, I think users will only care about the top matches but won't have knowledge about actual distance. Secondly, the feature input can be in various formats, so I think it is hard for users to figure out what threshold to use. I think query like SELECT ... WHERE ORDERBY similarity(...) STOP AFTER 5 is more likely to be used by user?

2. The USING syntax is used in a different way than my initial draft. Initially, I plan to use it to specify the index type alone, but here it seems to specify the feature extractor. We should probably reiterate this syntax.

[gaurav274]

1. STOP AFTER 5 returns the top 5. It implicitly means we return the ordered list.
2. I thought we could move all the optional things to the end of the query.

[jiashenC]

1. My main concern is similarity(...) > threshold syntax. I think greater than threshold syntax is not very useful and also hard for users to figure out a threshold value to use. Do you plan to just use the distance value as the threshold? If so, the value of distance can have large range.

2. Is it a convention that STOP AFTER always returns ordered list? My understanding is STOP AFTER is equivalent to LIMIT. For LIMIT, it can run on unordered list unless ORDERBY is enforced (source). In that case, the results will just be nondeterministic.

[pchunduri6]

I quite like the new design. It is more intuitive and works well with the current syntax. Regarding the above discussion:

1. I agree with @jiashenC that threshold could either be optional or omitted. I believe different applications will also have different threshold ranges.
2. Can we use a keyword like TOP 5 instead of STOP AFTER, so that it is more obvious that the output is an ordered list?

[gaurav274]

1. Yes, I agree the threshold is not intuitive. There is an optional example
   SELECT id, data FROM table WHERE similarity(open(source_image_path), data, FeatureExtractor) TOP 5;
   Is this also not intuitive?

Few references:
a) The closest I found in Postgres was pg_trgm. It deals with similarity between strings.
b) @jiashenC User can provide the similarity metric similarity(data1, data2, UDF, METRIC). But we can default it to euclidean distance or someone else for now.
Another motivation is to support finding dissimilar images ( similarity(..) < 0.2)

2. STOP AFTER is borrowed from extending sql. We can use TOP.

[xzdandy]

I like it! Looks good. Regarding the USING and index type, we can introduce a new keyword. But in reality, it probably faces a similar issue like the similarity distance, which is that users are likely to not have an idea which index type to use.