diff options
27 files changed, 427 insertions, 431 deletions
diff --git a/ydb/docs/en/core/concepts/_includes/secondary_indexes.md b/ydb/docs/en/core/concepts/_includes/secondary_indexes.md index 33df2780429..1e06300c5ce 100644 --- a/ydb/docs/en/core/concepts/_includes/secondary_indexes.md +++ b/ydb/docs/en/core/concepts/_includes/secondary_indexes.md @@ -33,9 +33,9 @@ Currently, a unique index cannot be added to an existing table. ## Vector Index -[Vector Index](vector_indexes.md) is a special type of secondary index. +[Vector Index](../../dev/vector-indexes.md) is a special type of secondary index. -Unlike secondary indexes, which optimize equality or range searches, vector indexes allow similarity searches based on distance or similarity functions. +Unlike secondary indexes, which optimize equality or range searches, vector indexes allow [vector search](../vector_search.md) based on distance or similarity functions. ### Creating a Secondary Index Online {#index-add} diff --git a/ydb/docs/en/core/concepts/_includes/vector_indexes.md b/ydb/docs/en/core/concepts/_includes/vector_indexes.md deleted file mode 100644 index 37e95ec8395..00000000000 --- a/ydb/docs/en/core/concepts/_includes/vector_indexes.md +++ /dev/null @@ -1,118 +0,0 @@ -# Vector indexes - -{{ ydb-short-name }} supports [vector indexes](https://en.wikipedia.org/wiki/Vector_database) to efficiently find the top k rows with vector values closest to a query vector. Unlike [secondary indexes](secondary_indexes.md) that optimize equality or range queries, vector indexes enable similarity search based on distance or similarity functions. - -Vector indexes are particularly useful for: - -* recommendation systems (finding similar items/users) -* semantic search (matching text embeddings) -* image similarity search -* anomaly detection (finding outliers) -* classification systems (finding nearest labeled examples) - -## Vector index characteristics {#characteristics} - -Vector indexes in {{ ydb-short-name }}: - -* Solve nearest neighbor search problems using similarity or distance functions -* Support multiple distance/similarity functions: "inner_product", "cosine" similarity and "cosine", "euclidean", "manhattan" distance -* Currently implement a single index type: `vector_kmeans_tree` - -### Vector index `vector_kmeans_tree` type {#vector-kmeans-tree-type} - -The `vector_kmeans_tree` index implements a hierarchical clustering structure. Its organization includes: - -1. Hierarchical clustering: - - - The index builds multiple levels of k-means clusters - - At each level, vectors are partitioned into specified number of clusters in power of level - - First level clusters the entire dataset - - Subsequent levels recursively cluster each parent cluster's contents - -2. Search process: - - - During queries, the index examines only the most promising clusters - - This search space pruning avoids exhaustive search through all vectors - -3. Parameters: - - - `levels`: The number of tree levels (typically 1-3). Controls search depth - - `clusters`: The number of clusters on each level (typically 64-512). Determines search breadth at each level - -## Vector index types {#types} - -### Basic vector index {#basic} - -The simplest form that indexes vectors without additional filtering capabilities. For example: - -```yql -ALTER TABLE my_table - ADD INDEX my_index - GLOBAL USING vector_kmeans_tree - ON (embedding) - WITH (distance=cosine, type="uint8", dimension=512, levels=2, clusters=128); -``` - -### Vector index with covered columns {#covering} - -Includes additional columns to avoid reading from the main table during queries: - -```yql -ALTER TABLE my_table - ADD INDEX my_index - GLOBAL USING vector_kmeans_tree - ON (embedding) COVER (data) - WITH (distance=cosine, type="uint8", dimension=512, levels=2, clusters=128); -``` - -### Prefixed vector index {#prefixed} - -Allows filtering by prefix columns before performing vector search: - -```yql -ALTER TABLE my_table - ADD INDEX my_index - GLOBAL USING vector_kmeans_tree - ON (user, embedding) - WITH (distance=cosine, type="uint8", dimension=512, levels=2, clusters=128); -``` - -### Prefixed vector index with covered columns {#prefixed-covering} - -Combines prefix filtering with covered columns for optimal performance: - -```yql -ALTER TABLE my_table - ADD INDEX my_index - GLOBAL USING vector_kmeans_tree - ON (user, embedding) COVER (data) - WITH (distance=cosine, type="uint8", dimension=512, levels=2, clusters=128); -``` - -## Creating vector indexes {#creation} - -Vector indexes can be created: - -* When creating a table with the YQL [`CREATE TABLE` statement](../../yql/reference/syntax/create_table/vector_index.md) -* Added to an existing table with the YQL [`ALTER TABLE` statement](../../yql/reference/syntax/alter_table/indexes.md) - -For more information about vector index parameters, see [`CREATE TABLE` statement](../../yql/reference/syntax/create_table/vector_index.md). - -## Using vector indexes {#usage} - -Query vector indexes using the VIEW syntax in YQL. For prefixed indexes, include the prefix columns in the WHERE clause: - -```yql -SELECT user, data -FROM my_table VIEW my_index -WHERE user = "..." -ORDER BY Knn::CosineSimilarity(embedding, ...) DESC -LIMIT 10; -``` - - -## Limitations {#limitations} - -Currently not supported: -* modifying rows in indexed tables -* bit vector type diff --git a/ydb/docs/en/core/concepts/_includes/vector_search_approximate.md b/ydb/docs/en/core/concepts/_includes/vector_search_approximate.md new file mode 100644 index 00000000000..4858902bda0 --- /dev/null +++ b/ydb/docs/en/core/concepts/_includes/vector_search_approximate.md @@ -0,0 +1,14 @@ +Approximate methods do not perform a complete enumeration of the initial data. This allows significantly speeding up the search process, although it might lead to some reduction in the quality of the results. + +[Scalar Quantization](../../yql/reference/udf/list/knn.md#approximate-vector-search-scalar-quantization) is a method of reducing vector dimensionality, where a set of coordinates is mapped into a space of smaller dimensions. + +{{ ydb-short-name }} supports vector searching for vector types `Float`, `Int8`, `Uint8`, and `Bit`. Consequently, it is possible to apply scalar quantization to transform data from `Float` to any of these types. + +Scalar quantization reduces the time required for reading and writing data by decreasing the number of bytes. For example, when quantizing from `Float` to `Bit`, each vector is reduced by 32 times. + +[Approximate vector search without an index](../../yql/reference/udf/list/knn.md#approximate-vector-search-examples) uses a very simple additional data structure - a set of vectors with other quantization. This allows the use of a simple search algorithm: first, a rough preliminary search is performed on the compressed vectors, followed by refining the results on the original vectors. + +Main advantages: + +* Full support for [transactions](../../concepts/glossary.md#transactions), including in strict consistency mode. +* Instant application of data modification operations: insertion, update, deletion. diff --git a/ydb/docs/en/core/concepts/_includes/vector_search_exact.md b/ydb/docs/en/core/concepts/_includes/vector_search_exact.md new file mode 100644 index 00000000000..c0b06665518 --- /dev/null +++ b/ydb/docs/en/core/concepts/_includes/vector_search_exact.md @@ -0,0 +1,9 @@ +The foundation of the exact method is the calculation of the distance from the query vector to all the vectors in the dataset. This algorithm, also known as the naive approach or brute force method, has a runtime of `O(dn)`, where `n` is the number of vectors in the dataset, and `d` is their dimensionality. + +[Exact vector search](../../yql/reference/udf/list/knn.md#exact-vector-search-examples) is best utilized if the complete enumeration of the vectors occurs within acceptable time limits. This includes cases where they can be pre-filtered based on some condition, such as a user identifier. In such instances, the exact method may perform faster than the current implementation of [vector indexes](../../dev/vector-indexes.md). + +Main advantages: + +* No need for additional data structures, such as specialized [vector indexes](../../concepts/glossary.md#vector-index). +* Full support for [transactions](../../concepts/glossary.md#transactions), including in strict consistency mode. +* Instant execution of data modification operations: insertion, update, deletion. diff --git a/ydb/docs/en/core/concepts/glossary.md b/ydb/docs/en/core/concepts/glossary.md index 007e6586ebe..8df88164eea 100644 --- a/ydb/docs/en/core/concepts/glossary.md +++ b/ydb/docs/en/core/concepts/glossary.md @@ -100,7 +100,7 @@ Technically, tablets are [actors](#actor) with a persistent state reliably saved Together, these mechanisms allow {{ ydb-short-name }} to provide [strict consistency](https://en.wikipedia.org/wiki/Consistency_model#Strict_consistency). -The implementation of distributed transactions is covered in a separate article [{#T}](../contributor/datashard-distributed-txs.md), while below there's a list of several [related terms](#distributed-transaction-implementation). +The implementation of distributed transactions is covered in a separate article [{#T}](../contributor/datashard-distributed-txs.md), while below there's a list of several [related terms](#deterministic-transactions). ### Interactive transactions {#interactive-transaction} @@ -162,9 +162,10 @@ A special type of **secondary index** is singled out separately - [vector index] #### Vector Index {#vector-index} -A **vector index** is an additional data structure used to speed up the [nearest neighbor search](https://en.wikipedia.org/wiki/Nearest_neighbor_search), typically when the data is too large for the [index-less approach](../yql/reference/udf/list/knn.md) to handle the load. Unlike the primary index, vector indexes are managed independently of the underlying table data. Thus, a table can have multiple vector indexes for different scenarios. For more information about using vector indexes in {{ ydb-short-name }}, see [{#T}](vector_indexes.md). +**Vector index** is an additional data structure used to speed up the [vector search](vector_search.md) when there is a large amount of data, and the [exact vector search without an index](../yql/reference/udf/list/knn.md) does not perform satisfactorily. The capabilities of {{ ydb-short-name }} regarding vector indexes are described in a separate article [{#T}](../dev/vector-indexes.md). + +**Vector index** is distinct from a [secondary index](#secondary-index) as it solves other tasks. -A **vector index** is allocated separately from the [secondary index] (#secondary-index), as it solves other tasks. #### Column family {#column-family} diff --git a/ydb/docs/en/core/concepts/toc_i.yaml b/ydb/docs/en/core/concepts/toc_i.yaml index 8a412dcc03d..d1100619417 100644 --- a/ydb/docs/en/core/concepts/toc_i.yaml +++ b/ydb/docs/en/core/concepts/toc_i.yaml @@ -14,8 +14,8 @@ items: href: transactions.md - name: Secondary indexes href: secondary_indexes.md -- name: Vector indexes - href: vector_indexes.md +- name: Vector search + href: vector_search.md - name: Change Data Capture (CDC) href: cdc.md when: feature_changefeed diff --git a/ydb/docs/en/core/concepts/vector_indexes.md b/ydb/docs/en/core/concepts/vector_indexes.md deleted file mode 100644 index 1d84e130e61..00000000000 --- a/ydb/docs/en/core/concepts/vector_indexes.md +++ /dev/null @@ -1 +0,0 @@ -{% include [vector_indexes.md](_includes/vector_indexes.md) %} diff --git a/ydb/docs/en/core/concepts/vector_search.md b/ydb/docs/en/core/concepts/vector_search.md new file mode 100644 index 00000000000..7775a7ef6cb --- /dev/null +++ b/ydb/docs/en/core/concepts/vector_search.md @@ -0,0 +1,48 @@ +# Vector search + +## Concept of vector search + +**Vector search**, also known as [nearest neighbor search](https://en.wikipedia.org/wiki/Nearest_neighbor_search) (NN), is an optimization problem where the goal is to find the nearest vector (or a set of vectors) in a given dataset relative to a specified query vector. The proximity between vectors is determined using distance or similarity metrics. + +Vector search is actively used in the following areas: + +* recommendation systems +* semantic search +* search for similar images +* anomaly detection +* classification systems + +In addition, **vector search** in {{ ydb-short-name }} is widely applied in machine learning (ML) and artificial intelligence (AI) tasks. It is particularly useful in Retrieval-Augmented Generation (RAG) approaches, which utilize vector search to retrieve relevant information from large volumes of data, significantly enhancing the quality of generative models. + +Methods for solving vector search tasks can be divided into three major categories: + +* [exact methods](#vector-search-exact) +* [approximate methods without index](#vector-search-approximate) +* [approximate methods with index](#vector-search-index) + +The choice of a method depends on the number of vectors and the nature of the workload. Exact methods search slowly but update quickly, whereas indexes do the opposite. + +## Exact vector search {#vector-search-exact} + +{% include [vector_search_exact.md](_includes/vector_search_exact.md) %} + +Learn more about [exact vector search](../yql/reference/udf/list/knn.md#exact-vector-search-examples). + +## Approximate vector search without index {#vector-search-approximate} + +{% include [vector_search_approximate.md](_includes/vector_search_approximate.md) %} + +Learn more about [approximate vector search without index](../yql/reference/udf/list/knn.md#approximate-vector-search-examples). + +## Approximate vector search with index {#vector-search-index} + +When the data volume significantly increases, non-index approaches cease to work within acceptable time limits. In such cases, additional data structures are necessary such as [vector indexes](../dev/vector-indexes.md), which accelerate the search process. + +Main advantage: + +* ability to work with a large number of vectors + +Disadvantages: + +* index construction may take considerable time +* in the current version, data modification operations such as insertion, update, and deletion are not supported diff --git a/ydb/docs/en/core/dev/vector-indexes.md b/ydb/docs/en/core/dev/vector-indexes.md index d20eefce420..0d3fa540867 100644 --- a/ydb/docs/en/core/dev/vector-indexes.md +++ b/ydb/docs/en/core/dev/vector-indexes.md @@ -1,62 +1,130 @@ -# Vector indexes +# Vector Indexes -[Vector indexes](https://en.wikipedia.org/wiki/Vector_database) are specialized data structures that enable efficient similarity search in high-dimensional spaces. Unlike traditional indexes that optimize exact lookups, vector indexes allow finding the most similar items to a query vector based on mathematical distance or similarity measures. +[Vector indexes](../concepts/glossary.md#vector-index) are specialized data structures that enable efficient [vector search](../concepts/vector_search.md) in multidimensional spaces. Unlike [secondary indexes](../concepts/glossary.md#secondary-index), which optimize searching by equality or range, vector indexes allow similarity searching based on distance or similarity functions. -Data in a {{ ydb-short-name }} table is stored and sorted by a primary key, enabling efficient point lookups and range scans. Vector indexes provide similar efficiency for nearest neighbor searches in vector spaces, which is particularly valuable for working with embeddings and other high-dimensional data representations. +Data in a {{ ydb-short-name }} table is stored and sorted by the primary key, ensuring efficient searching by exact match and range scanning. Vector indexes provide similar efficiency for nearest neighbor searches in vector spaces. -This article describes practical operations with vector indexes. For conceptual information about vector index types and their characteristics, see [Vector indexes](../concepts/vector_indexes.md) in the Concepts section. +## Characteristics of Vector Indexes {#characteristics} -## Creating vector indexes {#create} +Vector indexes in {{ ydb-short-name }} address the nearest neighbor search problem using [similarity or distance functions](../yql/reference/udf/list/knn.md#functions). Several distance/similarity functions are supported: "inner_product", "cosine" (similarity) and "cosine", "euclidean", "manhattan" (distance). -A vector index can be created with the following YQL commands: -* [`CREATE TABLE`](../yql/reference/syntax/create_table/index.md) -* [`ALTER TABLE`](../yql/reference/syntax/alter_table/index.md) +The current implementation offers one type of index: `vector_kmeans_tree`. -Example of creating a prefixed vector index with covered columns: +## Vector Index Type `vector_kmeans_tree` {#kmeans-tree-type} + +The `vector_kmeans_tree` index implements hierarchical data clustering. The structure of the index includes: + +1. Hierarchical clustering: + + * the index builds multiple levels of k-means clusters + * at each level, vectors are distributed across a predefined number of clusters raised to the power of the level + * the first level clusters the entire dataset + * subsequent levels recursively cluster the contents of each parent cluster + +2. Search process: + + * search proceeds recursively from the first level to the subsequent ones + * during queries, the index analyzes only the most promising clusters + * such search space pruning avoids complete enumeration of all vectors + +3. Parameters: + + * `levels`: number of levels in the tree, defining search depth (recommended 1-3) + * `clusters`: number of clusters in k-means, defining search width (recommended 64-512) + +Internally, a vector index consists of hidden index tables named `indexImpl*Table`. In [selection queries](#select) using the vector index, the index tables will appear in [query statistics](query-plans-optimization.md). + +## Types of Vector Indexes {#types} + +A vector index can be **covering**, meaning it includes additional columns to enable reading from the index without accessing the main table. + +Alternatively, it can be **prefixed**, allowing for additional columns to be used for quick filtering during reading. + +Below are examples of creating vector indexes of different types. + +### Basic Vector Index {#basic} + +Global vector index on the `embedding` column: + +```yql +ALTER TABLE my_table + ADD INDEX my_index + GLOBAL USING vector_kmeans_tree + ON (embedding) + WITH (distance=cosine, vector_type="uint8", vector_dimension=512, levels=2, clusters=128); +``` + +### Vector Index with Covering Columns {#covering} + +A covering vector index, including an additional column `data` to avoid reading from the main table during a search: + +```yql +ALTER TABLE my_table + ADD INDEX my_index + GLOBAL USING vector_kmeans_tree + ON (embedding) COVER (data) + WITH (distance=cosine, vector_type="uint8", vector_dimension=512, levels=2, clusters=128); +``` + +### Prefixed Vector Index {#prefixed} + +A prefixed vector index, allowing filtering by the prefix column `user` during vector search: + +```yql +ALTER TABLE my_table + ADD INDEX my_index + GLOBAL USING vector_kmeans_tree + ON (user, embedding) + WITH (distance=cosine, vector_type="uint8", vector_dimension=512, levels=2, clusters=128); +``` + +### Prefixed Vector Index with Covering Columns {#prefixed-covering} + +A prefixed vector index with covering columns: ```yql ALTER TABLE my_table ADD INDEX my_index GLOBAL USING vector_kmeans_tree ON (user, embedding) COVER (data) - WITH (distance=cosine, type="uint8", dimension=512, levels=2, clusters=128); + WITH (distance=cosine, vector_type="uint8", vector_dimension=512, levels=2, clusters=128); ``` -Key parameters for `vector_kmeans_tree`: -* `distance`/`similarity`: Metric function ("cosine", "euclidean", etc.) -* `type`: Data type ("float", "int8", "uint8") -* `dimension`: Number of dimensions (<= 16384) -* `levels`: Tree depth -* `clusters`: Number of clusters per level (values > 1000 may impact performance) +## Creating Vector Indexes {#creation} -Since building a vector index requires processing existing data, index creation on populated tables may take significant time. This operation runs in the background, allowing continued table access during construction. The index becomes available automatically when ready. +Vector indexes can be created: -## Using vector indexes for similarity search {#use} +* during table creation using the YQL operator [CREATE TABLE](../yql/reference/syntax/create_table/vector_index.md); +* added to an existing table using the YQL operator [ALTER TABLE](../yql/reference/syntax/alter_table/indexes.md). -To perform similarity searches, explicitly specify the index name in the VIEW clause. For prefixed indexes, include prefix column conditions in the WHERE clause: +## Using Vector Indexes {#select} + +Queries to vector indexes are executed using the `VIEW` syntax in YQL. For prefixed indexes, specify the prefix columns in the `WHERE` clause: ```yql DECLARE $query_vector AS List<Uint8>; SELECT user, data FROM my_table VIEW my_index -WHERE user = "john_doe" ORDER BY Knn::CosineSimilarity(embedding, $query_vector) DESC LIMIT 10; ``` -Without the VIEW clause, the query would perform a full table scan with brute-force vector comparison. +For more details on executing `SELECT` queries using vector indexes, see the section [VIEW VECTOR INDEX](../yql/reference/syntax/select/vector_index.md). -## Checking the cost of queries {#cost} +{% note info %} -Any query made in a transactional application should be checked in terms of the number of I/O operations it performed in the database and how much CPU was used to run it. You should also make sure these indicators don't continuously grow as the database volume grows. {{ ydb-short-name }} returns statistics required for the analysis after running each query. +If the `VIEW` expression is not used, the query will perform a full table scan with pairwise comparison of vectors. -If you use the {{ ydb-short-name }} CLI, select the `--stats` option to enable printing statistics after executing the `yql` command. All {{ ydb-short-name }} SDKs also contain structures with statistics returned after running a query. If you make a query in the UI, you'll see a tab with statistics next to the results tab. +It is recommended to check the optimality of the written query using [query statistics](query-plans-optimization.md). In particular, ensure there is no full scan of the main table. -{% note warning %} +{% endnote %} -Vector indexes currently don't support data modification operations. -Any attempt to modify rows in indexed tables will fail. -This limitation will be removed in future releases. +## Limitations of Vector Indexes {#limitations} -{% endnote %} +Currently not supported: + +* modifying rows in tables with vector indexes +* using bit vectors + +These limitations may be removed in future versions. diff --git a/ydb/docs/en/core/reference/observability/metrics/index.md b/ydb/docs/en/core/reference/observability/metrics/index.md index 15af7e34db7..57a6d35e2c4 100644 --- a/ydb/docs/en/core/reference/observability/metrics/index.md +++ b/ydb/docs/en/core/reference/observability/metrics/index.md @@ -5,7 +5,7 @@ | Metric name<br/>Type, units of measurement | Description<br/>Labels | | ----- | ----- | | `resources.storage.used_bytes`<br/>`IGAUGE`, bytes | The size of user and service data stored in distributed network storage. `resources.storage.used_bytes` = `resources.storage.table.used_bytes` + `resources.storage.topic.used_bytes`. | -| `resources.storage.table.used_bytes`<br/>`IGAUGE`, bytes | The size of user and service data stored by tables in distributed network storage. Service data includes the data of the primary, [secondary indexes](../../../concepts/secondary_indexes.md) and [vector indexes](../../../concepts/vector_indexes.md). | +| `resources.storage.table.used_bytes`<br/>`IGAUGE`, bytes | The size of user and service data stored by tables in distributed network storage. Service data includes the data of the primary, [secondary indexes](../../../concepts/glossary.md#secondary-index) and [vector indexes](../../../concepts/glossary.md#vector-index). | | `resources.storage.topic.used_bytes`<br/>`IGAUGE`, bytes | The size of storage used by topics. This metric sums the `topic.storage_bytes` values of all topics. | | `resources.storage.limit_bytes`<br/>`IGAUGE`, bytes | A limit on the size of user and service data that a database can store in distributed network storage. | diff --git a/ydb/docs/en/core/reference/ydb-cli/export-import/_includes/s3_export.md b/ydb/docs/en/core/reference/ydb-cli/export-import/_includes/s3_export.md index c4e4a213909..b9bee3dbb73 100644 --- a/ydb/docs/en/core/reference/ydb-cli/export-import/_includes/s3_export.md +++ b/ydb/docs/en/core/reference/ydb-cli/export-import/_includes/s3_export.md @@ -12,8 +12,8 @@ The export feature is available only for objects of the following types: - [Directory](../../../../concepts/datamodel/dir.md) - [Row-oriented table](../../../../concepts/datamodel/table.md#row-oriented-tables) -- [Secondary index](../../../../concepts/secondary_indexes.md) -- [Vector index](../../../../concepts/vector_indexes.md) +- [Secondary index](../../../../concepts/glossary.md#secondary-index) +- [Vector index](../../../../concepts/glossary.md#vector-index) {% endnote %} diff --git a/ydb/docs/en/core/yql/reference/syntax/create_table/vector_index.md b/ydb/docs/en/core/yql/reference/syntax/create_table/vector_index.md index dde90405863..67375799000 100644 --- a/ydb/docs/en/core/yql/reference/syntax/create_table/vector_index.md +++ b/ydb/docs/en/core/yql/reference/syntax/create_table/vector_index.md @@ -10,7 +10,7 @@ You should use `ALTER TABLE ... ADD INDEX` to add a vector index to an existing {% endnote %} -The INDEX construct is used to define a [vector index](../../../../concepts/vector_indexes.md) in a [row-oriented](../../../../concepts/datamodel/table.md#row-oriented-tables) table: +The INDEX construct is used to define a [vector index](../../../../concepts/glossary.md#vector-index) in a [row-oriented](../../../../concepts/datamodel/table.md#row-oriented-tables) table: ```yql CREATE TABLE table_name ( @@ -29,8 +29,8 @@ Where: * **Cover_columns** is a list of comma-separated column names in the created table, which will be stored in the index in addition to the search columns, making it possible to fetch additional data without accessing the table for it. * **Index_parameters** is a list of comma-separated key-value parameters: * parameters for any vector **index_type**: - * `dimension` is a number of dimension in the indexed embedding (<= 16384) - * `type` is a type of value in the indexed embedding, can be `float`, `uint8`, `int8`, `bit` + * `vector_dimension` is a number of dimension in the indexed embedding (<= 16384) + * `vector_type` is a type of value in the indexed embedding, can be `float`, `uint8`, `int8`, `bit` * `distance` is a type of the distance function which will be used for this index. Valid values: `cosine`, `manhattan`, `euclidean`. * `similarity` is a type of the similarity function which will be used for this index. Valid values: `inner_product`, `cosine`. * parameters specific to `vector_kmeans_tree`: @@ -47,7 +47,7 @@ The `distance` and `similarity` parameters can not be specified together. {% note warning %} -The `type=bit` vector index is not supported yet. +The `vector_type=bit` vector index is not supported yet. {% endnote %} @@ -62,7 +62,7 @@ CREATE TABLE user_articles ( embedding String, INDEX emb_cosine_idx GLOBAL SYNC USING vector_kmeans_tree ON (user, embedding) COVER (title, text) - WITH (dimension=512, type="float", distance="cosine", clusters=128, levels=2), + WITH (distance="cosine", vector_type="float", vector_dimension=512, clusters=128, levels=2), PRIMARY KEY (article_id) ) ``` diff --git a/ydb/docs/en/core/yql/reference/udf/list/knn.md b/ydb/docs/en/core/yql/reference/udf/list/knn.md index becb6b8db39..25c93d17d1b 100644 --- a/ydb/docs/en/core/yql/reference/udf/list/knn.md +++ b/ydb/docs/en/core/yql/reference/udf/list/knn.md @@ -1,41 +1,18 @@ # KNN -## Introduction +## Introduction {#introduction} -[Nearest Neighbor search](https://en.wikipedia.org/wiki/Nearest_neighbor_search) (NN) is an optimization task that consists of finding the closest point in a given dataset to a given query point. Closeness can be defined in terms of distance or similarity metrics. -A generalization of the NN problem is the [k-NN problem](https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm), where it's required to find the `k` nearest points to the query point. This can be useful in various applications such as image classification, recommendation systems, etc. +One specific case of [vector search](../../../../concepts/vector_search.md) is the [k-NN](https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm) problem, where it is required to find the `k` nearest points to the query point. This can be useful in various applications such as image classification, recommendation systems, etc. The k-NN problem solution is divided into two major subclasses of methods: exact and approximate. -### Exact method +### Exact method {#exact-method} -The exact method is based on calculating the distance from the query point to every other point in the database. This algorithm, also known as the naive approach, has a complexity of `O(dn)`, where `n` is the number of points in the dataset, and `d` is its dimension. +{% include [vector_search_exact.md](../../../../concepts/_includes/vector_search_exact.md) %} -The advantage of the method is that there is no need for additional data structures, such as specialized vector indexes. -The disadvantage is the need for a full data scan. But this disadvantage is insignificant in cases where data has been pre-filtered, for example, by user ID. +### Approximate methods {#approximate-methods} -Example: - -```yql -$TargetEmbedding = Knn::ToBinaryStringFloat([1.2f, 2.3f, 3.4f, 4.5f]); - -SELECT id, fact, embedding FROM Facts -WHERE user="Williams" -ORDER BY Knn::CosineDistance(embedding, $TargetEmbedding) -LIMIT 10; -``` - -### Approximate methods - -Approximate methods do not perform a complete search of the source data. Due to this, they work significantly faster, although they may result in some loss of quality. - -This document provides an [example of approximate search](#approximate-search-examples) using scalar quantization. This example does not require the creation of a secondary vector index. - -**Scalar quantization** is a method to compress vectors by mapping coordinates to a smaller space. -This module supports exact search for `Float`, `Int8`, `Uint8`, `Bit` vectors. -So, it's possible to apply scalar quantization from `Float` to one of these other types. - -Scalar quantization decreases read/write times by reducing vector size in bytes. For example, after quantization from `Float` to `Bit,` each vector becomes 32 times smaller. +{% include [vector_search_approximate.md](../../../../concepts/_includes/vector_search_approximate.md) %} {% note info %} @@ -43,16 +20,16 @@ It is recommended to measure if such quantization provides sufficient accuracy/r {% endnote %} -## Data types +## Data types {#data-types} In mathematics, a vector of real or integer numbers is used to store points. In this module, vectors are stored in the `String` data type, which is a binary serialized representation of a vector. -## Functions +## Functions {#functions} Vector functions are implemented as user-defined functions (UDF) in the `Knn` module. -### Functions for converting between vector and binary representations +### Functions for converting between vector and binary representations {#functions-convert} Conversion functions are needed to serialize vectors into an internal binary representation and vice versa. @@ -62,7 +39,7 @@ All serialization functions wrap returned `String` data into [Tagged](../../type The binary representation of the vector can be stored in the {{ ydb-short-name }} table column. Currently {{ ydb-short-name }} does not support storing `Tagged`, so before storing binary representation vectors you must call [Untag](../../builtins/basic#as-tagged). {% endif %} -#### Function signatures +#### Function signatures {#functions-convert-signature} ```yql Knn::ToBinaryStringFloat(List<Float>{Flags:AutoMap})->Tagged<String, "FloatVector"> @@ -75,11 +52,11 @@ Knn::ToBinaryStringBit(List<Int8>{Flags:AutoMap})->Tagged<String, "BitVector"> Knn::FloatFromBinaryString(String{Flags:AutoMap})->List<Float>? ``` -#### Implementation details +#### Implementation details {#functions-convert-details} The `ToBinaryStringBit` function maps coordinates that are greater than `0` to `1`. All other coordinates are mapped to `0`. -### Distance and similarity functions +### Distance and similarity functions {#functions-distance} The distance and similarity functions take two lists of real numbers as input and return the distance/similarity between them. @@ -100,7 +77,7 @@ Distance functions: * manhattan distance `ManhattanDistance`, also known as `L1 distance` (sum of modules of coordinate differences) * euclidean distance `EuclideanDistance`, also known as `L2 distance` (square root of the sum of squares of coordinate differences) -#### Function signatures +#### Function signatures {#functions-distance-signatures} ```yql Knn::InnerProductSimilarity(String{Flags:AutoMap}, String{Flags:AutoMap})->Float? @@ -126,11 +103,11 @@ Error: Failed to find UDF function: Knn.CosineDistance, reason: Error: Module: K {% endnote %} -## Еxact search examples +## Exact search examples {#exact-vector-search-examples} {% if backend_name == "YDB" %} -### Creating a table +### Creating a table {#exact-vector-search-examples-create} ```yql CREATE TABLE Facts ( @@ -142,7 +119,7 @@ CREATE TABLE Facts ( ); ``` -### Adding vectors +### Adding vectors {#exact-vector-search-examples-upsert} ```yql $vector = [1.f, 2.f, 3.f, 4.f]; @@ -152,7 +129,7 @@ VALUES (123, "Williams", "Full name is John Williams", Untag(Knn::ToBinaryString {% else %} -### Data declaration +### Data declaration {#exact-vector-search-examples-create-list} ```yql $vector = [1.f, 2.f, 3.f, 4.f]; @@ -168,7 +145,7 @@ $facts = AsList( {% endif %} -### Exact search of K nearest vectors +### Exact search of K nearest vectors {#exact-vector-search-k-nearest} {% if backend_name == "YDB" %} @@ -196,7 +173,7 @@ LIMIT $K; {% endif %} -### Exact search of vectors in radius R +### Exact search of vectors in radius R {#exact-vector-search-radius} {% if backend_name == "YDB" %} @@ -220,28 +197,28 @@ WHERE Knn::CosineDistance(embedding, $TargetEmbedding) < $R; {% endif %} -## Approximate search examples +## Approximate search examples {#approximate-vector-search-examples} -This example differs from the [exact search example](#еxact-search-examples) by using bit quantization. +This example differs from the [exact search example](#exact-vector-search-examples) by using bit quantization. This allows to first do a approximate preliminary search by the `embedding_bit` column, and then refine the results by the original vector column `embegging`. {% if backend_name == "YDB" %} -### Creating a table +### Creating a table {#approximate-vector-search-examples-create} ```yql CREATE TABLE Facts ( - id Uint64, -- Id of fact - user Utf8, -- User name - fact Utf8, -- Human-readable description of a user fact - embedding String, -- Binary representation of embedding vector (result of Knn::ToBinaryStringFloat) + id Uint64, -- Id of fact + user Utf8, -- User name + fact Utf8, -- Human-readable description of a user fact + embedding String, -- Binary representation of embedding vector (result of Knn::ToBinaryStringFloat) embedding_bit String, -- Binary representation of embedding vector (result of Knn::ToBinaryStringBit) PRIMARY KEY (id) ); ``` -### Adding vectors +### Adding vectors {#approximate-vector-search-examples-upsert} ```yql $vector = [1.f, 2.f, 3.f, 4.f]; @@ -251,7 +228,7 @@ VALUES (123, "Williams", "Full name is John Williams", Untag(Knn::ToBinaryString {% else %} -### Data declaration +### Data declaration {#approximate-vector-search-examples-create-list} ```yql $vector = [1.f, 2.f, 3.f, 4.f]; @@ -268,13 +245,13 @@ $facts = AsList( {% endif %} -### Scalar quantization +### Scalar quantization {#approximate-vector-search-scalar-quantization} An ML model can do quantization, or it can be done manually with YQL. Below there is a quantization example in YQL. -#### Float -> Int8 +#### Float -> Int8 {#approximate-vector-search-scalar-quantization-map} ```yql $MapInt8 = ($x) -> { @@ -288,7 +265,7 @@ $FloatList = [-1.2f, 2.3f, 3.4f, -4.7f]; SELECT ListMap($FloatList, $MapInt8); ``` -### Approximate search of K nearest vectors: bit quantization +### Approximate search of K nearest vectors: bit quantization {#approximate-vector-search-scalar-quantization-example} Approximate search algorithm: diff --git a/ydb/docs/redirects.yaml b/ydb/docs/redirects.yaml index 66fc31f62d1..25dc0349faf 100644 --- a/ydb/docs/redirects.yaml +++ b/ydb/docs/redirects.yaml @@ -33,6 +33,8 @@ common: to: /public-materials/videos.md - from: /concepts/databases.md to: /concepts/glossary.md + - from: /concepts/vector_index.md + to: concepts/vector_search.md - from: /postgresql/pg-dump.md to: /postgresql/import.md - from: /concepts/column-table.md diff --git a/ydb/docs/ru/core/concepts/_includes/secondary_indexes.md b/ydb/docs/ru/core/concepts/_includes/secondary_indexes.md index acb1f9a485b..ba0fc092725 100644 --- a/ydb/docs/ru/core/concepts/_includes/secondary_indexes.md +++ b/ydb/docs/ru/core/concepts/_includes/secondary_indexes.md @@ -31,11 +31,11 @@ В настоящее время уникальный индекс не может быть добавлен в существующую таблицу. -## Векторый индекс +## Векторный индекс -[Векторный индекс](vector_indexes.md) является особым видом вторичного индекса. +[Векторный индекс](../../dev/vector-indexes.md) является особым видом вторичного индекса. -В отличие от вторичных индексов, оптимизирующих поиск по равенству или диапазону, векторные индексы позволяют выполнять поиск по сходству на основе функций расстояния или схожести. +В отличие от вторичных индексов, оптимизирующих поиск по равенству или диапазону, векторные индексы позволяют выполнять [векторный поиск](../vector_search.md) на основе функций расстояния или схожести. ## Онлайн-создание вторичного индекса {#index-add} diff --git a/ydb/docs/ru/core/concepts/_includes/vector_indexes.md b/ydb/docs/ru/core/concepts/_includes/vector_indexes.md deleted file mode 100644 index 3cabd89c4f0..00000000000 --- a/ydb/docs/ru/core/concepts/_includes/vector_indexes.md +++ /dev/null @@ -1,119 +0,0 @@ -# Векторные индексы - -{{ ydb-short-name }} поддерживает [векторные индексы](https://en.wikipedia.org/wiki/Vector_database) для эффективного приближенного поиска k ближайших строк к вектору запроса (ANN поиск). В отличие от [вторичных индексов](secondary_indexes.md), оптимизирующих поиск по равенству или диапазону, векторные индексы позволяют выполнять поиск по сходству на основе функций расстояния или схожести. - -Векторные индексы особенно полезны для: - -* рекомендательных систем (поиск похожих товаров/пользователей; -* cемантического поиска (сопоставление текстовых эмбеддингов); -* поиска похожих изображений; -* обнаружения аномалий (поиск выбросов); -* классификационных систем (поиск ближайших размеченных примеров). - -## Характеристики векторных индексов {#characteristics} - -Векторные индексы в {{ ydb-short-name }} решают задачу поиска ближайших соседей с использованием функций схожести или расстояния. - -Поддерживается несколько функций расстояния/схожести: "inner_product", "cosine" (схожесть) и "cosine", "euclidean" и "manhattan" (расстояние). - -В текущей реализации доступен один тип индекса: `vector_kmeans_tree`. - -### Векторный индекс типа `vector_kmeans_tree` {#vector-kmeans-tree-type} - -Индекс `vector_kmeans_tree` реализует иерархическую кластеризацию данных. Его структура включает: - -1. Иерархическая кластеризация: - - - индекс строит несколько уровней k-means кластеров; - - на каждом уровне векторы распределяются по заданному количеству кластеров в степени уровня; - - первый уровень кластеризует весь набор данных; - - последующие уровни рекурсивно кластеризуют содержимое каждого родительского кластера. - -2. Процесс поиска: - - - поиск идет рекурсивно от первого уровня к последующим; - - при выполнении запросов индекс анализирует только наиболее перспективные кластеры; - - такое усечение пространства поиска позволяет избежать полного перебора всех векторов. - -3. Параметры: - - - `levels`: число уровней в дереве, задает глубину поиска (обычно 1-3); - - `clusters`: число кластеров в k-means, определяет ширину поиска (обычно 64-512). - -## Типы векторных индексов {#types} - -### Базовый векторный индекс {#basic} - -Глобальный векторный индекс по колонке `embedding`: - -```yql -ALTER TABLE my_table - ADD INDEX my_index - GLOBAL USING vector_kmeans_tree - ON (embedding) - WITH (distance=cosine, type="uint8", dimension=512, levels=2, clusters=128); -``` - -### Векторный индекс с покрывающими колонками {#covering} - -Покрывающий векторный индекс, включающий дополнительную колонку `data`, чтобы избежать чтения из основной таблицы при поиске: - -```yql -ALTER TABLE my_table - ADD INDEX my_index - GLOBAL USING vector_kmeans_tree - ON (embedding) COVER (data) - WITH (distance=cosine, type="uint8", dimension=512, levels=2, clusters=128); -``` - -### Векторный индекс с префиксом {#prefixed} - -Векторный индекс с префиксом, позволяющий фильтровать по префиксной колонке `user` в момент выполнения векторного поиска: - -```yql -ALTER TABLE my_table - ADD INDEX my_index - GLOBAL USING vector_kmeans_tree - ON (user, embedding) - WITH (distance=cosine, type="uint8", dimension=512, levels=2, clusters=128); -``` - -### Векторный индекс с префиксом и покрывающими колонками {#prefixed-covering} - -Векторный индекс с префиксом и покрывающими колонками: - -```yql -ALTER TABLE my_table - ADD INDEX my_index - GLOBAL USING vector_kmeans_tree - ON (user, embedding) COVER (data) - WITH (distance=cosine, type="uint8", dimension=512, levels=2, clusters=128); -``` - -## Создание векторных индексов {#creation} - -Векторные индексы можно создавать: - -* при создании таблицы с помощью YQL-оператора [CREATE TABLE](../../yql/reference/syntax/create_table/vector_index.md); -* добавлять к существующей таблице с помощью YQL-оператора [ALTER TABLE](../../yql/reference/syntax/alter_table/indexes.md). - -Подробнее про параметры создания векторного индекса смотри в [CREATE TABLE](../../yql/reference/syntax/create_table/vector_index.md) - -## Использование векторных индексов {#usage} - -Запросы к векторным индексам выполняются с использованием синтаксиса VIEW в YQL. Для индексов с префиксом укажите префиксные колонки в условии WHERE: - -```yql -SELECT user, data -FROM my_table VIEW my_index -WHERE user = "..." -ORDER BY Knn::CosineSimilarity(embedding, ...) DESC -LIMIT 10; -``` - -## Ограничения {#limitations} - -В настоящее время не поддерживается: - -* изменение строк в индексированных таблицах; -* тип битовых векторов.
\ No newline at end of file diff --git a/ydb/docs/ru/core/concepts/_includes/vector_search_approximate.md b/ydb/docs/ru/core/concepts/_includes/vector_search_approximate.md new file mode 100644 index 00000000000..36d503591b8 --- /dev/null +++ b/ydb/docs/ru/core/concepts/_includes/vector_search_approximate.md @@ -0,0 +1,14 @@ +Приближенные методы не осуществляют полный перебор исходных данных. Это позволяет значительно ускорить процесс поиска, хотя и может привести к некоторому снижению качества результатов. + +[Скалярное квантование](../../yql/reference/udf/list/knn.md#approximate-vector-search-scalar-quantization) — это метод уменьшения размерности векторов, при котором множество координат отображается в пространство меньшей размерности. + +{{ ydb-short-name }} поддерживает векторный поиск по векторам типов `Float`, `Int8`, `Uint8`, `Bit`. Следовательно, возможно применение скалярного квантования для преобразования данных из `Float` в любой из этих типов. + +Скалярное квантование сокращает время, необходимое для чтения и записи данных, за счёт уменьшения числа байт. Например, при квантовании из `Float` в `Bit` каждый вектор сокращается в 32 раза. + +[Приближенный векторный поиск без индекса](../../yql/reference/udf/list/knn.md#approximate-vector-search-examples) использует очень простую дополнительную структуру данных - множество векторов с другими квантованием. Это позволяет использовать простой алгоритм поиска: сначала грубый предварительный поиск по сжатым векторам, а затем уточнять результаты по исходным векторам. + +Основные преимущества: + +* полная поддержка [транзакций](../../concepts/glossary.md#transactions),в том числе в режиме строгой согласованности; +* мгновенное применение операций модификации данных: вставка, обновление, удаление.
\ No newline at end of file diff --git a/ydb/docs/ru/core/concepts/_includes/vector_search_exact.md b/ydb/docs/ru/core/concepts/_includes/vector_search_exact.md new file mode 100644 index 00000000000..1bee313e9ca --- /dev/null +++ b/ydb/docs/ru/core/concepts/_includes/vector_search_exact.md @@ -0,0 +1,9 @@ +В основе точного метода лежит вычисление расстояния от вектора запроса до всех векторов в наборе данных. Этот алгоритм, также известный как наивный подход или метод грубой силы, имеет время выполнения `O(dn)`, где `n` — количество векторов в наборе данных, а `d` — их размерность. + +[Точный векторный поиск](../../yql/reference/udf/list/knn.md#exact-vector-search-examples) лучше использовать, если полный перебор искомых векторов происходит за приемлемое время. В том числе, когда их можно предварительно отфильтровать по некоторому условию, например, по идентификатору пользователя. В таких случаях точный метод может работать быстрее, чем текущая реализация [векторных индексов](../../dev/vector-indexes.md) + +Основные преимущества: + +* отсутствие необходимости в дополнительных структурах данных, таких как специализированные [векторные индексы](../../concepts/glossary.md#vector-index); +* полная поддержка [транзакций](../../concepts/glossary.md#transactions), в том числе в режиме строгой согласованности; +* мгновенное применение операций модификации данных: вставка, обновление, удаление.
\ No newline at end of file diff --git a/ydb/docs/ru/core/concepts/glossary.md b/ydb/docs/ru/core/concepts/glossary.md index 3b677efee8f..0b90ab4906e 100644 --- a/ydb/docs/ru/core/concepts/glossary.md +++ b/ydb/docs/ru/core/concepts/glossary.md @@ -102,7 +102,7 @@ {% if oss %} -Реализация распределённых транзакций рассмотрена в отдельной статье [{#T}](../contributor/datashard-distributed-txs.md), а ниже приведён список нескольких [связанных терминов](#distributed-transaction-implementation). +Реализация распределённых транзакций рассмотрена в отдельной статье [{#T}](../contributor/datashard-distributed-txs.md), а ниже приведён список нескольких [связанных терминов](#deterministic-transactions). {% endif %} @@ -156,9 +156,9 @@ #### Векторный индекс {#vector-index} -**Векторный индекс** или **vector index** — это дополнительная структура данных, используемая для ускорения решения задачи [поиска ближайшего соседа](https://en.wikipedia.org/wiki/Nearest_neighbor_search), когда данных достаточно много и [точный векторный поиск без индекса](../yql/reference/udf/list/knn.md) не работает удовлетворительно. В отличие от первичного индекса, векторные индексы управляются независимо от основных данных таблицы. Таким образом, у таблицы может быть несколько векторных индексов для различных сценариев. Возможности {{ ydb-short-name }} в отношении векторных индексов описаны в отдельной статье [{#T}](vector_indexes.md). +**Векторный индекс** или **vector index** — это дополнительная структура данных, используемая для ускорения решения задачи [векторного поиска](vector_search.md), когда данных достаточно много и [точный векторный поиск без индекса](../yql/reference/udf/list/knn.md) не работает удовлетворительно. Возможности {{ ydb-short-name }} в отношении векторных индексов описаны в отдельной статье [{#T}](../dev/vector-indexes.md). -**Векторый индекс** выделяется отдельно от [вторичного индекса](#secondary-index), так как решает иные задачи. +**Векторный индекс** выделяется отдельно от [вторичного индекса](#secondary-index), так как решает иные задачи. #### Семейство колонок {#column-family} diff --git a/ydb/docs/ru/core/concepts/toc_i.yaml b/ydb/docs/ru/core/concepts/toc_i.yaml index 5b7b17d29f3..7421b5075b8 100644 --- a/ydb/docs/ru/core/concepts/toc_i.yaml +++ b/ydb/docs/ru/core/concepts/toc_i.yaml @@ -14,8 +14,8 @@ items: href: transactions.md - name: Вторичные индексы href: secondary_indexes.md -- name: Векторные индексы - href: vector_indexes.md +- name: Векторный поиск + href: vector_search.md - name: Change Data Capture (CDC) href: cdc.md when: feature_changefeed diff --git a/ydb/docs/ru/core/concepts/vector_indexes.md b/ydb/docs/ru/core/concepts/vector_indexes.md deleted file mode 100644 index 1d84e130e61..00000000000 --- a/ydb/docs/ru/core/concepts/vector_indexes.md +++ /dev/null @@ -1 +0,0 @@ -{% include [vector_indexes.md](_includes/vector_indexes.md) %} diff --git a/ydb/docs/ru/core/concepts/vector_search.md b/ydb/docs/ru/core/concepts/vector_search.md new file mode 100644 index 00000000000..e0f5fefa36f --- /dev/null +++ b/ydb/docs/ru/core/concepts/vector_search.md @@ -0,0 +1,49 @@ +# Векторный поиск + +## Понятие векторного поиска + +**Векторный поиск**, также известный как [поиск ближайшего соседа](https://en.wikipedia.org/wiki/Nearest_neighbor_search) (NN), представляет собой задачу оптимизации, в которой необходимо найти ближайший вектор (или множество векторов) в данном наборе данных относительно заданного вектора запроса. Близость между векторами определяется с помощью метрик расстояния или сходства. + +Векторный поиск активно используется в следующих областях: + +* рекомендательные системы; +* семантический поиск; +* поиск похожих изображений; +* обнаружение аномалий; +* классификационные системы. + +Кроме того, **векторный поиск** в {{ ydb-short-name }} широко применяется в задачах машинного обучения (ML) и искусственного интеллекта (AI). Он особенно полезен в подходах Retrieval-Augmented Generation (RAG), которые используют векторный поиск для извлечения релевантной информации из больших объемов данных, что значительно улучшает качество генеративных моделей. + +Методы решения задач векторного поиска можно разделить на три крупных категории: + +* [точные методы](#vector-search-exact); +* [приближенные методы без индекса](#vector-search-approximate); +* [приближенные методы с индексом](#vector-search-index). + +Выбор метода зависит от числа векторов и от характера нагрузки. Точные методы медленно ищут и быстро обновляются, индексы - наоборот. + +## Точный векторный поиск {#vector-search-exact} + +{% include [vector_search_exact.md](_includes/vector_search_exact.md) %} + +Подробнее о [точном векторном поиске](../yql/reference/udf/list/knn.md#exact-vector-search-examples). + +## Приближенный векторный поиск без индекса {#vector-search-approximate} + +{% include [vector_search_approximate.md](_includes/vector_search_approximate.md) %} + +Подробнее о [приближенном векторном поиске без индекса](../yql/reference/udf/list/knn.md#approximate-vector-search-examples). + +## Приближенный векторный поиск с индексом {#vector-search-index} + +Когда объем данных существенно увеличивается, подходы без индекса перестают работать за приемлемое время. +В таких случаях необходимы дополнительные структуры данных — [векторные индексы](../dev/vector-indexes.md), которые ускоряют процесс поиска. + +Основное преимущество: + +* возможность работы с большим числом векторов. + +Недостатки: + +* построение индекса может занимать существенное время; +* в текущей версии не поддерживаются операции модификации данных: вставка, обновление, удаление.
\ No newline at end of file diff --git a/ydb/docs/ru/core/dev/vector-indexes.md b/ydb/docs/ru/core/dev/vector-indexes.md index 0ba7d8148a7..d7b83025bf2 100644 --- a/ydb/docs/ru/core/dev/vector-indexes.md +++ b/ydb/docs/ru/core/dev/vector-indexes.md @@ -1,61 +1,131 @@ # Векторные индексы -[Векторные индексы](https://en.wikipedia.org/wiki/Vector_database) — это специализированные структуры данных, позволяющие эффективно выполнять поиск схожести в многомерных пространствах. В отличие от традиционных индексов, оптимизированных для точных совпадений, векторные индексы помогают находить наиболее похожие элементы на основе математических мер расстояния или схожести. +[Векторные индексы](../concepts/glossary.md#vector-index) — это специализированные структуры данных, которые позволяют эффективно выполнять [векторный поиск](../concepts/vector_search.md) в многомерных пространствах. В отличие от [вторичных индексов](../concepts/glossary.md#secondary-index), которые оптимизируют поиск по равенству или диапазону, векторные индексы позволяют выполнять поиск по сходству на основе функций расстояния или схожести. -Данные в таблице {{ ydb-short-name }} хранятся и сортируются по первичному ключу, что обеспечивает эффективный поиск по точному совпадению и сканирование диапазонов. Векторные индексы предоставляют аналогичную эффективность для поиска ближайших соседей в векторных пространствах, что особенно ценно при работе с эмбеддингами и другими многомерными представлениями данных. +Данные в таблице {{ ydb-short-name }} хранятся и сортируются по первичному ключу, что обеспечивает эффективный поиск по точному совпадению и сканирование диапазонов. Векторные индексы предоставляют аналогичную эффективность для поиска ближайших соседей в векторных пространствах. -В этой статье описаны практические операции с векторными индексами. Концептуальную информацию о типах векторных индексов и их характеристиках см. в разделе [Векторные индексы](../concepts/vector_indexes.md) в категории "Концепции". +## Характеристики векторных индексов {#characteristics} -## Создание векторных индексов {#create} +Векторные индексы в {{ ydb-short-name }} решают задачу поиска ближайших соседей с использованием [функций схожести или расстояния](../yql/reference/udf/list/knn.md#functions). Поддерживается несколько функций расстояния/схожести: "inner_product", "cosine" (схожесть) и "cosine", "euclidean", "manhattan" (расстояние). -Векторный индекс можно создать: -* При создании таблицы с помощью [YQL-команды `CREATE TABLE`](../yql/reference/syntax/create_table/vector_index.md) -* Добавить к существующей таблице с помощью [YQL-команды `ALTER TABLE`](../yql/reference/syntax/alter_table/vector_index.md) +В текущей реализации доступен один тип индекса: `vector_kmeans_tree`. -Пример создания префиксного векторного индекса с покрывающими колонками: +## Векторный индекс типа `vector_kmeans_tree` {#kmeans-tree-type} + +Индекс `vector_kmeans_tree` реализует иерархическую кластеризацию данных. Структура индекса включает: + +1. Иерархическая кластеризация: + + * индекс строит несколько уровней k-means кластеров; + * на каждом уровне векторы распределяются по заданному количеству кластеров в степени уровня; + * первый уровень кластеризует весь набор данных; + * последующие уровни рекурсивно кластеризуют содержимое каждого родительского кластера. + +2. Процесс поиска: + + * поиск идет рекурсивно от первого уровня к последующим; + * при выполнении запросов индекс анализирует только наиболее перспективные кластеры; + * такое усечение пространства поиска позволяет избежать полного перебора всех векторов. + +3. Параметры: + + * `levels`: число уровней в дереве, задает глубину поиска (рекомендуется 1-3); + * `clusters`: количество кластеров в k-means, определяющее ширину поиска (рекомендуется 64-512). + +Внутри векторный индекс состоит из скрытых индексных таблиц вида `indexImpl*Table`. В [запросах на выборку](#select) с использованием векторного индекса, индексные таблицы будут отображены в [статистике запросов](query-plans-optimization.md). + +## Виды векторных индексов {#types} + +Векторный индекс может быть **покрывающим**, что означает включение дополнительных колонок для возможности чтения из индекса без обращения к основной таблице. + +Или же он может быть **префиксным**, что позволяет учитывать дополнительные колонки для быстрой фильтрации при выполнении чтения. + +Ниже приведены примеры создания векторного индекса различных типов. + + +### Базовый векторный индекс {#basic} + +Глобальный векторный индекс по колонке `embedding`: + +```yql +ALTER TABLE my_table + ADD INDEX my_index + GLOBAL USING vector_kmeans_tree + ON (embedding) + WITH (distance=cosine, vector_type="uint8", vector_dimension=512, levels=2, clusters=128); +``` + +### Векторный индекс с покрывающими колонками {#covering} + +Покрывающий векторный индекс, включающий дополнительную колонку `data`, чтобы избежать чтения из основной таблицы при поиске: + +```yql +ALTER TABLE my_table + ADD INDEX my_index + GLOBAL USING vector_kmeans_tree + ON (embedding) COVER (data) + WITH (distance=cosine, vector_type="uint8", vector_dimension=512, levels=2, clusters=128); +``` + +### Векторный индекс с префиксом {#prefixed} + +Векторный индекс с префиксом, позволяющий фильтровать по префиксной колонке `user` в момент выполнения векторного поиска: + +```yql +ALTER TABLE my_table + ADD INDEX my_index + GLOBAL USING vector_kmeans_tree + ON (user, embedding) + WITH (distance=cosine, vector_type="uint8", vector_dimension=512, levels=2, clusters=128); +``` + +### Векторный индекс с префиксом и покрывающими колонками {#prefixed-covering} + +Векторный индекс с префиксом и покрывающими колонками: ```yql ALTER TABLE my_table ADD INDEX my_index GLOBAL USING vector_kmeans_tree ON (user, embedding) COVER (data) - WITH (distance=cosine, type="uint8", dimension=512, levels=2, clusters=128); + WITH (distance=cosine, vector_type="uint8", vector_dimension=512, levels=2, clusters=128); ``` -Подробное описание параметров векторного индекса смотри в [YQL-команде `CREATE TABLE`](../yql/reference/syntax/create_table/vector_index.md). +## Создание векторных индексов {#creation} -Поскольку построение векторного индекса требует обработки существующих данных, создание индекса для заполненной таблицы может занять значительное время. Эта операция выполняется в фоновом режиме, позволяя продолжать работу с таблицей во время построения. Индекс становится доступным автоматически после завершения. +Векторные индексы можно создавать: -## Использование векторных индексов для поиска схожести {#use} +* при создании таблицы с помощью YQL-оператора [CREATE TABLE](../yql/reference/syntax/create_table/vector_index.md); +* добавлять к существующей таблице с помощью YQL-оператора [ALTER TABLE](../yql/reference/syntax/alter_table/indexes.md). -Для выполнения поиска схожести явно укажите имя индекса в предложении VIEW. Для префиксных индексов включите условия для префиксных колонок в предложение WHERE: +## Использование векторных индексов {#select} + +Запросы к векторным индексам выполняются с использованием синтаксиса `VIEW` в YQL. Для индексов с префиксом укажите префиксные колонки в условии `WHERE`: ```yql DECLARE $query_vector AS List<Uint8>; SELECT user, data FROM my_table VIEW my_index -WHERE user = "john_doe" ORDER BY Knn::CosineSimilarity(embedding, $query_vector) DESC LIMIT 10; ``` +Подробнее о выполнении запросов `SELECT` с использованием векторных индексов можно прочитать в разделе [VIEW VECTOR INDEX](../yql/reference/syntax/select/vector_index.md). + {% note info %} -Без предложения VIEW запрос выполнит полное сканирование таблицы с попарным сравнением векторов. +Если не использовать выражение `VIEW`, запрос выполнит полное сканирование таблицы с попарным сравнением векторов. -{% endnote %} +Рекомендуется проверять оптимальность написанного запроса, используя [статистику запросов](query-plans-optimization.md). В частности, следует следить за отсутствием полного сканирования (full scan) основной таблицы. -## Проверка стоимости запросов {#cost} - -Любой запрос в транзакционном приложении должен проверяться с точки зрения количества операций ввода-вывода и используемых вычислительных ресурсов. Также необходимо убедиться, что эти показатели не растут постоянно с увеличением объема данных. {{ ydb-short-name }} [возвращает статистику](query-plans-optimization.md), необходимую для анализа, после выполнения каждого запроса. +{% endnote %} -При использовании CLI {{ ydb-short-name }} выберите опцию `--stats`, чтобы включить вывод статистики после выполнения команды `yql`. Все SDK {{ ydb-short-name }} также содержат структуры со статистикой, возвращаемой после выполнения запроса. В пользовательском интерфейсе статистика отображается на отдельной вкладке рядом с результатами запроса. +## Ограничения векторных индексов {#limitations} -{% note warning %} +В настоящее время не поддерживается: -В текущей версии векторные индексы не поддерживают операции модификации данных. -Любая попытка изменить строки в индексированных таблицах завершится ошибкой. -Это ограничение будет снято в будущих релизах. +* изменение строк в таблицах с векторными индексами; +* использование битовых векторов. -{% endnote %}
\ No newline at end of file +Эти ограничения могут быть сняты в будущих версиях.
\ No newline at end of file diff --git a/ydb/docs/ru/core/reference/observability/metrics/index.md b/ydb/docs/ru/core/reference/observability/metrics/index.md index f166b1f0390..400ead9ef04 100644 --- a/ydb/docs/ru/core/reference/observability/metrics/index.md +++ b/ydb/docs/ru/core/reference/observability/metrics/index.md @@ -11,7 +11,7 @@ Имя метрики<br/>Тип, единицы измерения | Описание<br/>Метки ----- | ----- `resources.storage.used_bytes`<br/>`IGAUGE`, байты | Размер пользовательских и служебных данных, сохраненных в распределенном сетевом хранилище. `resources.storage.used_bytes` = `resources.storage.table.used_bytes` + `resources.storage.topic.used_bytes`. -`resources.storage.table.used_bytes`<br/>`IGAUGE`, байты | Размер пользовательских и служебных данных, сохраненных таблицами в распределенном сетевом хранилище. К служебным данным относятся данные первичного, [вторичных индексов](../../../concepts/secondary_indexes.md) и [векторных индексов](../../../concepts/vector_indexes.md). +`resources.storage.table.used_bytes`<br/>`IGAUGE`, байты | Размер пользовательских и служебных данных, сохраненных таблицами в распределенном сетевом хранилище. К служебным данным относятся данные первичного, [вторичных индексов](../../../concepts/glossary.md#secondary-index) и [векторных индексов](../../../concepts/glossary.md#vector-index). `resources.storage.topic.used_bytes`<br/>`IGAUGE`, байты | Размер распределенного сетевого хранилища, используемого топиками. Равен сумме значений `topic.storage_bytes` всех топиков. `resources.storage.limit_bytes`<br/>`IGAUGE`, байты | Ограничение на размер пользовательских и служебных данных, которые база данных может сохранить в распределенном сетевом хранилище. diff --git a/ydb/docs/ru/core/reference/ydb-cli/export-import/_includes/export-s3.md b/ydb/docs/ru/core/reference/ydb-cli/export-import/_includes/export-s3.md index 3a7e39afcda..e97accbb3f4 100644 --- a/ydb/docs/ru/core/reference/ydb-cli/export-import/_includes/export-s3.md +++ b/ydb/docs/ru/core/reference/ydb-cli/export-import/_includes/export-s3.md @@ -12,8 +12,8 @@ - [директория](../../../../concepts/datamodel/dir.md); - [строковая таблица](../../../../concepts/datamodel/table.md#row-oriented-tables); -- [вторичный индекс](../../../../concepts/secondary_indexes.md). -- [векторый индекс](../../../../concepts/vector_indexes.md). +- [вторичный индекс](../../../../concepts/glossary.md#secondary-index). +- [векторный индекс](../../../../concepts/glossary.md#vector-index). {% endnote %} diff --git a/ydb/docs/ru/core/yql/reference/syntax/create_table/vector_index.md b/ydb/docs/ru/core/yql/reference/syntax/create_table/vector_index.md index 115cec1d3df..126e1c14e13 100644 --- a/ydb/docs/ru/core/yql/reference/syntax/create_table/vector_index.md +++ b/ydb/docs/ru/core/yql/reference/syntax/create_table/vector_index.md @@ -14,7 +14,7 @@ {% endnote %} -Конструкция INDEX используется для определения [векторного индекса](../../../../concepts/vector_indexes.md) в [строчно-ориентированных](../../../../concepts/datamodel/table.md#row-oriented-tables) таблицах: +Конструкция INDEX используется для определения [векторного индекса](../../../../concepts/glossary.md#vector-index) в [строчно-ориентированных](../../../../concepts/datamodel/table.md#row-oriented-tables) таблицах: ```yql CREATE TABLE table_name ( @@ -33,24 +33,22 @@ CREATE TABLE table_name ( * **покрывающие_колонки** - дополнительные колонки таблицы, сохраняемые в индексе для возможности их извлечения без обращения к основной таблице * **параметры_индекса** - список параметров в формате ключ-значение: * общие параметры для всех векторных индексов: - * `dimension` - размерность вектора эмбеддинга (<= 16384); - * `type` - тип значений вектора (`float`, `uint8`, `int8`, `bit`); + * `vector_dimension` - размерность вектора эмбеддинга (<= 16384); + * `vector_type` - тип значений вектора (`float`, `uint8`, `int8`, `bit`); * `distance` - функция расстояния (`cosine`, `manhattan`, `euclidean`) или `similarity` - функция схожести (`inner_product`, `cosine`). * специфичные параметры для `vector_kmeans_tree`: * `clusters` - количество центроидов для алгоритма k-means (значения > 1000 могут ухудшить производительность); * `levels` - количество уровней в дереве. - {% note warning %} Параметры `distance` и `similarity` не могут быть указаны одновременно. {% endnote %} - {% note warning %} -Векторные индексы с `type=bit` в настоящее время не поддерживаются +Векторные индексы с `vector_type=bit` в настоящее время не поддерживаются {% endnote %} @@ -65,7 +63,7 @@ CREATE TABLE user_articles ( embedding String, INDEX emb_cosine_idx GLOBAL SYNC USING vector_kmeans_tree ON (user, embedding) COVER (title, text) - WITH (dimension=512, type="float", distance="cosine", clusters=128, levels=2), + WITH (distance="cosine", vector_type="float", vector_dimension=512, clusters=128, levels=2), PRIMARY KEY (article_id) ) ``` diff --git a/ydb/docs/ru/core/yql/reference/udf/list/knn.md b/ydb/docs/ru/core/yql/reference/udf/list/knn.md index ba92ae6b123..0925dada027 100644 --- a/ydb/docs/ru/core/yql/reference/udf/list/knn.md +++ b/ydb/docs/ru/core/yql/reference/udf/list/knn.md @@ -1,42 +1,18 @@ # KNN -## Введение +## Введение {#introduction} -[Поиск ближайшего соседа](https://en.wikipedia.org/wiki/Nearest_neighbor_search) (NN) - это задача оптимизации, заключающаяся в нахождении ближайшей точки (или набора точек) в заданном наборе данных к заданной точке запроса. Близость может быть определена в терминах метрики расстояния или сходства. -Обобщением задачи NN является задача [k-NN](https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm), где от нас требуется найти `k` ближайших точек к точке запроса. Это может быть полезно в различных приложениях, таких как классификация изображений, рекомендательные системы и многое другое. +Одним из частных случаев [векторного поиска](../../../../concepts/vector_search.md) является задача [k-NN](https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm), где требуется найти `k` ближайших точек к точке запроса. Это может быть полезно в различных приложениях, таких как классификация изображений, рекомендательные системы и многое другое. Решения задачи k-NN разбивается на два крупных подкласса методов: точные и приближенные. -### Точный метод +### Точный метод {#exact-method} -В основе точного метода лежит вычисление расстояния от точки запроса до каждой другой точки в базе данных. Этот алгоритм, также известный как наивный подход, имеет время выполнения `O(dn)`, где `n` - количество точек в наборе данных, а `d` - его размерность. +{% include [vector_search_exact.md](../../../../concepts/_includes/vector_search_exact.md) %} -Преимуществом метода является отсутствие необходимости в дополнительных структурах данных, вроде специализированных векторных индексов. -Недостатком является необходимость полного перебора данных. Но данный недостаток является несущественным в случаях, когда произошла предварительная фильтрация данных, например, по идентификатору пользователя. +### Приближенные методы {#approximate-methods} -Пример: - -```yql -$TargetEmbedding = Knn::ToBinaryStringFloat([1.2f, 2.3f, 3.4f, 4.5f]); - -SELECT id, fact, embedding FROM Facts -WHERE user="Williams" -ORDER BY Knn::CosineDistance(embedding, $TargetEmbedding) -LIMIT 10; -``` - -### Приближенные методы - -Приближенные методы не производят полный перебор исходных данных, за счет этого работают существенно быстрее, хоть и допускают некоторое ухудшение качества поиска. - -В данном документе приведен [пример приближенного поиска](#примеры-приближенного-поиска) с помощью скалярного квантования, не требущий построения вторичного векторного индекса. - -**Скалярное квантование** это метод сжатия векторов, когда множество координат отображаются в множество меньшей размерности. -Этот модуль поддерживает точный поиск по `Float`, `Int8`, `Uint8`, `Bit` векторам. -Соответственно, возможно скалярное квантование из `Float` в один из этих типов. - -Скалярное квантование уменьшает время необходимое для чтения/записи, поскольку число байт сокращается в разы. -Например, при квантовании из `Float` в `Bit` каждый вектор становится меньше в `32` раза. +{% include [vector_search_approximate.md](../../../../concepts/_includes/vector_search_approximate.md) %} {% note info %} @@ -44,16 +20,16 @@ LIMIT 10; {% endnote %} -## Типы данных +## Типы данных {#data-types} В математике для хранения точек используется вектор вещественных или целых чисел. В этом модуле вектора представлены типом данных `String`, который является бинарным сериализованным представлением вектора. -## Функции +## Функции {#functions} Функции работы с векторами реализовываются в виде пользовательских функций (UDF) в модуле `Knn`. -### Функции преобразования вектора в бинарное представление +### Функции преобразования вектора в бинарное представление {#functions-convert} Функции преобразования нужны для сериализации векторов во внутреннее бинарное представление и обратно. @@ -64,7 +40,7 @@ LIMIT 10; В настоящий момент {{ ydb-short-name }} не поддерживает хранение `Tagged` типов и поэтому перед сохранением бинарного представления векторов нужно извлечь `String` с помощью функции [Untag](../../builtins/basic#as-tagged). {% endif %} -#### Сигнатуры функций +#### Сигнатуры функций {#functions-convert-signature} ```yql Knn::ToBinaryStringFloat(List<Float>{Flags:AutoMap})->Tagged<String, "FloatVector"> @@ -77,11 +53,11 @@ Knn::ToBinaryStringBit(List<Int8>{Flags:AutoMap})->Tagged<String, "BitVector"> Knn::FloatFromBinaryString(String{Flags:AutoMap})->List<Float>? ``` -#### Детали имплементации +#### Детали имплементации {#functions-convert-details} `ToBinaryStringBit` преобразует в `1` все координаты которые больше `0`, остальные координаты преобразуются в `0`. -### Функции расстояния и сходства +### Функции расстояния и сходства {#functions-distance} Функции расстояния и сходства принимают на вход два вектора и возвращают расстояние/сходство между ними. @@ -102,7 +78,7 @@ Knn::FloatFromBinaryString(String{Flags:AutoMap})->List<Float>? * манхэттенское расстояние `ManhattanDistance`, также известно как `L1 distance` (сумма модулей покоординатной разности) * Евклидово расстояние `EuclideanDistance`, также известно как `L2 distance` (корень суммы квадратов покоординатной разности) -#### Сигнатуры функций +#### Сигнатуры функций {#functions-distance-signatures} ```yql Knn::InnerProductSimilarity(String{Flags:AutoMap}, String{Flags:AutoMap})->Float? @@ -128,11 +104,11 @@ Error: Failed to find UDF function: Knn.CosineDistance, reason: Error: Module: K {% endnote %} -## Примеры точного поиска +## Примеры точного поиска {#exact-vector-search-examples} {% if backend_name == "YDB" %} -### Создание таблицы +### Создание таблицы {#exact-vector-search-examples-create} ```yql CREATE TABLE Facts ( @@ -144,7 +120,7 @@ CREATE TABLE Facts ( ); ``` -### Добавление векторов +### Добавление векторов {#exact-vector-search-examples-upsert} ```yql $vector = [1.f, 2.f, 3.f, 4.f]; @@ -154,7 +130,7 @@ VALUES (123, "Williams", "Full name is John Williams", Untag(Knn::ToBinaryString {% else %} -### Декларация данных +### Декларация данных {#exact-vector-search-examples-create-list} ```yql $vector = [1.f, 2.f, 3.f, 4.f]; @@ -170,7 +146,7 @@ $facts = AsList( {% endif %} -### Точный поиск K ближайших векторов +### Точный поиск K ближайших векторов {#exact-vector-search-k-nearest} {% if backend_name == "YDB" %} @@ -198,7 +174,7 @@ LIMIT $K; {% endif %} -### Точный поиск векторов, находящихся в радиусе R +### Точный поиск векторов, находящихся в радиусе R {#exact-vector-search-radius} {% if backend_name == "YDB" %} @@ -222,14 +198,14 @@ WHERE Knn::CosineDistance(embedding, $TargetEmbedding) < $R; {% endif %} -## Примеры приближенного поиска +## Примеры приближенного поиска {#approximate-vector-search-examples} -Данный пример отличается от [примера с точным поиском](#примеры-точного-поиска) использованием битового квантования. +Данный пример отличается от [примера с точным поиском](#exact-vector-search-examples) использованием битового квантования. Это позволяет сначала делать грубый предварительный поиск по колонке `embedding_bit`, а затем уточнять результаты по основной колонке с векторами `embedding`. {% if backend_name == "YDB" %} -### Создание таблицы +### Создание таблицы {#approximate-vector-search-examples-create} ```yql CREATE TABLE Facts ( @@ -242,7 +218,7 @@ CREATE TABLE Facts ( ); ``` -### Добавление векторов +### Добавление векторов {#approximate-vector-search-examples-upsert} ```yql $vector = [1.f, 2.f, 3.f, 4.f]; @@ -252,7 +228,7 @@ VALUES (123, "Williams", "Full name is John Williams", Untag(Knn::ToBinaryString {% else %} -### Декларация данных +### Декларация данных {#approximate-vector-search-examples-create-list} ```yql $vector = [1.f, 2.f, 3.f, 4.f]; @@ -269,13 +245,13 @@ $facts = AsList( {% endif %} -### Скалярное квантование +### Скалярное квантование {#approximate-vector-search-scalar-quantization} ML модель может выполнять квантование или это можно сделать вручную с помощью YQL. Ниже приведен пример квантования в YQL. -#### Float -> Int8 +#### Float -> Int8 {#approximate-vector-search-scalar-quantization-map} ```yql $MapInt8 = ($x) -> { @@ -289,7 +265,7 @@ $FloatList = [-1.2f, 2.3f, 3.4f, -4.7f]; SELECT ListMap($FloatList, $MapInt8); ``` -### Приближенный поиск K ближайших векторов: битовое квантование +### Приближенный поиск K ближайших векторов: битовое квантование {#approximate-vector-search-scalar-quantization-example} Алгоритм приближенного поиска: |