Add: USearch

ClickHouse · rschu1ze · Aug 21, 2023 · Aug 15, 2023 · Aug 16, 2023 · Aug 16, 2023
commit 48c62fd75e2977ee9b23ceea070782188536c2ba
diff --git a/.gitmodules b/.gitmodules
@@ -347,3 +347,6 @@
 [submodule "contrib/incbin"]
 	path = contrib/incbin
 	url = https://github.com/graphitemaster/incbin.git
+[submodule "contrib/usearch"]
+	path = contrib/usearch
+	url = https://github.com/unum-cloud/usearch.git
diff --git a/contrib/CMakeLists.txt b/contrib/CMakeLists.txt
@@ -196,6 +196,7 @@ if (ARCH_S390X)
     add_contrib(crc32-s390x-cmake crc32-s390x)
 endif()
 add_contrib (annoy-cmake annoy)
+add_contrib (usearch-cmake usearch)
 add_contrib (xxHash-cmake xxHash)
 
 add_contrib (libbcrypt-cmake libbcrypt)

diff --git a/contrib/usearch b/contrib/usearch
diff --git a/contrib/usearch-cmake/CMakeLists.txt b/contrib/usearch-cmake/CMakeLists.txt
@@ -0,0 +1,15 @@
+option(ENABLE_USEARCH "Enable USearch (Approximate Neighborhood Search, HNSW) support" ${ENABLE_LIBRARIES})
+
+if (NOT ENABLE_USEARCH)
+    message (STATUS "Not using usearch")
+    return()
+endif()
+
+set(USEARCH_PROJECT_DIR "${ClickHouse_SOURCE_DIR}/contrib/usearch")
+set(USEARCH_SOURCE_DIR "${USEARCH_PROJECT_DIR}/include")
+
+add_library(_usearch INTERFACE)
+target_include_directories(_usearch SYSTEM INTERFACE ${USEARCH_PROJECT_DIR}/fp16/include ${USEARCH_PROJECT_DIR}/robin-map/include ${USEARCH_PROJECT_DIR}/simsimd/include ${USEARCH_SOURCE_DIR})
+
+add_library(ch_contrib::usearch ALIAS _usearch)
+target_compile_definitions(_usearch INTERFACE ENABLE_USEARCH)
diff --git a/docs/en/engines/table-engines/mergetree-family/annindexes.md b/docs/en/engines/table-engines/mergetree-family/annindexes.md
@@ -142,6 +142,8 @@ was specified for ANN indexes, the default value is 100 million.
 
 - [Annoy](/docs/en/engines/table-engines/mergetree-family/annindexes.md#annoy-annoy)
 
+- [USearch](/docs/en/engines/table-engines/mergetree-family/annindexes.md#usearch-usearch)
+
 ## Annoy {#annoy}
 
 Annoy indexes are currently experimental, to use them you first need to `SET allow_experimental_annoy_index = 1`. They are also currently
@@ -216,3 +218,42 @@ ORDER BY L2Distance(vectors, Point)
 LIMIT N
 SETTINGS annoy_index_search_k_nodes=100;
 ```
+
+
+## USearch {#usearch}
+
+USearch indexes are currently experimental, to use them you first need to `SET allow_experimental_usearch_index = 1`.
+
+This type of ANN index implements [the HNSW algorithm](https://github.com/unum-cloud/usearch).
+
+Syntax to create an USearch index over an [Array](../../../sql-reference/data-types/array.md) column:
+
+```sql
+CREATE TABLE table_with_usearch_index
+(
+  id Int64,
+  vectors Array(Float32),
+  INDEX [ann_index_name] vectors TYPE usearch([Distance]) [GRANULARITY N]
+)
+ENGINE = MergeTree
+ORDER BY id;
+```
+
+Syntax to create an ANN index over a [Tuple](../../../sql-reference/data-types/tuple.md) column:
+
+```sql
+CREATE TABLE table_with_usearch_index
+(
+  id Int64,
+  vectors Tuple(Float32[, Float32[, ...]]),
+  INDEX [ann_index_name] vectors TYPE usearch([Distance]) [GRANULARITY N]
+)
+ENGINE = MergeTree
+ORDER BY id;
+```
+
+USearch currently supports two distance functions:
+- `L2Distance`, also called Euclidean distance, is the length of a line segment between two points in Euclidean space
+  ([Wikipedia](https://en.wikipedia.org/wiki/Euclidean_distance)).
+- `cosineDistance`, also called cosine similarity, is the cosine of the angle between two (non-zero) vectors
+  ([Wikipedia](https://en.wikipedia.org/wiki/Cosine_similarity)).
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
@@ -599,6 +599,10 @@ if (TARGET ch_contrib::annoy)
     dbms_target_link_libraries(PUBLIC ch_contrib::annoy)
 endif()
 
+if (TARGET ch_contrib::usearch)
+    dbms_target_link_libraries(PUBLIC ch_contrib::usearch)
+endif()
+
 if (TARGET ch_rust::skim)
     dbms_target_include_directories(PRIVATE $<TARGET_PROPERTY:ch_rust::skim,INTERFACE_INCLUDE_DIRECTORIES>)
     dbms_target_link_libraries(PUBLIC ch_rust::skim)

diff --git a/src/Core/Settings.h b/src/Core/Settings.h
@@ -772,6 +772,7 @@ class IColumn;
     M(Bool, allow_experimental_hash_functions, false, "Enable experimental hash functions", 0) \
     M(Bool, allow_experimental_object_type, false, "Allow Object and JSON data types", 0) \
     M(Bool, allow_experimental_annoy_index, false, "Allows to use Annoy index. Disabled by default because this feature is experimental", 0) \
+    M(Bool, allow_experimental_usearch_index, false, "Allows to use USearch index. Disabled by default because this feature is experimental", 0) \
     M(UInt64, max_limit_for_ann_queries, 1'000'000, "SELECT queries with LIMIT bigger than this setting cannot use ANN indexes. Helps to prevent memory overflows in ANN search indexes.", 0) \
     M(Int64, annoy_index_search_k_nodes, -1, "SELECT queries search up to this many nodes in Annoy indexes.", 0) \
     M(Bool, throw_on_unsupported_query_inside_transaction, true, "Throw exception if unsupported query is used inside transaction", 0) \