Indexed Vector Similarity and kNN Search

[alexey-milovidov]

Use case

Search and analytics on datasets with vector embeddings.

Describe the solution you'd like

The solution is being implemented by the team led by @FArthur-cmd

[qieqieplus]

Good to see a soluntion for KNN(maybe ANN sometime later?)
I actually wrote one arrayDistance myself as my toy project to learn Clickhouse.

[alexey-milovidov]

@qieqieplus Now we also have Lp norms and distance functions:

https://presentations.clickhouse.com/release_21.11/#20
#27933

Good for non-indexed, brute-force search.

[FArthur-cmd]

In fact, we are now working with algorithms for ANN

[qieqieplus]

@qieqieplus Now we also have Lp norms and distance functions:

https://presentations.clickhouse.com/release_21.11/#20 #27933

Good for non-indexed, brute-force search.

Yes I'm aware of that, as I commented in #27933, those functions only work for data type tuple.
Correct me if i'm wrong, but data type array could be much more suitable for high dimensional dense vectors (like
hundreds if not thousands dimensions, in real world scenario), especially for engines other than memory .

I made a quick benchmark of BF search on L2Distance and a naive array based approach using higher-order functions:
SELECT id, arraySum(arrayMap((x, y)->(x - y) * (x - y), feature, [?])) as l2sqr from ? order by l2sqr limit 10;
Also with my native arrayL2Distance implementation backed by BLAS library Eigen.

With 1Million random generate 256D Uint8 vectors, each query time and memory increased:
L2Distance: 500ms ~ 700ms, 982MB
array functions: 400ms ~ 500ms, 410MB
native arrayL2Distance: 240ms ~ 320ms, 298MB

Test Platform: CPU: Xeon(R) CPU E5-2630 v4

[alexey-milovidov]

@qieqieplus Yes, it makes sense to implement functions on arrays with BLAS, the performance numbers are very impressive.
I will be happy if you'll send a PR.

[qieqieplus]

@alexey-milovidov I'm glad to. I'll send a PR when ready.

[zhanglistar]

Wow, clickhouse now is a set of many tools.

[FArthur-cmd]

Faiss index #37011

HNSW index #37007

[FArthur-cmd]

Annoy #37215
DiskANN #37392

[Sivannnnnn]

Hi, when is Clickhouse going to launch vector retrieval for KNN or Ann? Any plans?
@alexey-milovidov @FArthur-cmd

[alexey-milovidov]

ClickHouse For AI presentation: https://presentations.clickhouse.com/meetup74/ai/
A practical overview of vector search in ClickHouse: https://clickhouse.com/blog/vector-search-clickhouse-p2

[alexey-milovidov]

Video: https://www.youtube.com/watch?v=hGRNcftpqAk

[alexey-milovidov]

Attempt to make Annoy index ready to use: #50312

But it is not required, as in the video above, I showed how to construct the same index manually, and it allows tuning between speed and precision dynamically.