Векторный индекс¶
В этом разделе описывается функциональность векторных индексов StarRocks и то, как выполнять поиск Approximate Nearest Neighbor Search (ANNS) с их помощью.
Функциональность векторных индексов поддерживается только в кластерах shared-nothing версии v3.4 и новее.
Обзор¶
В настоящее время StarRocks поддерживает векторные индексы на уровне файлов Segment. Индекс отображает каждый искомый элемент в его row ID внутри файлов Segment, что позволяет быстро извлекать данные за счет прямой локализации соответствующих строк без полного перебора и вычисления расстояний между векторами. Система предоставляет два типа векторных индексов: Inverted File with Product Quantization (IVFPQ) и Hierarchical Navigable Small World (HNSW), каждый со своей организацией структуры.
Inverted File with Product Quantization (IVFPQ)¶
IVFPQ — это метод приблизительного поиска ближайших соседей в больших наборах высокоразмерных векторов, широко используемый в задачах векторного поиска в глубоком обучении и машинном обучении. IVFPQ состоит из двух основных компонентов: inverted file и product quantization.
Inverted File: метод индексирования. Датасет делится на несколько кластеров (ячейки Вороного), каждый со своим центроидом (seed point). Каждый вектор относится к ближайшему центру. При поиске просматривается только ближайший кластер, что существенно сокращает область и сложность поиска.
Product Quantization: техника сжатия данных. Вектор делится на под-векторы и каждый под-вектор квантуется, сопоставляясь с ближайшей точкой из предопределенного набора. Это снижает издержки хранения и вычислений при сохранении высокой точности.
Комбинируя inverted files и product quantization, IVFPQ обеспечивает эффективный приблизительный поиск ближайших соседей в больших и высокоразмерных наборах данных.
Hierarchical Navigable Small World (HNSW)¶
HNSW — графовый алгоритм поиска ближайших соседей в высоких размерностях, также широко применяемый в векторном поиске.
HNSW строит иерархический граф, где каждый уровень — это navigable small world (NSW) граф. В вершинах находятся точки данных, рёбра отражают степень близости. Верхние уровни содержат меньше вершин с более разреженными связями для быстрого глобального поиска, а нижние уровни — все вершины с более плотными связями для точного локального поиска.
При векторном поиске HNSW начинает с верхнего уровня, быстро находит область примерно ближайших соседей, затем спускается по уровням для нахождения точных ближайших соседей внизу.
HNSW сочетает эффективность и точность, что делает его адаптивным к различным распределениям данных и запросов.
Сравнение IVFPQ и HNSW¶
Коэффициент сжатия данных: IVFPQ имеет более высокий коэффициент сжатия (порядка 1:0.15). Индекс даёт предварительную сортировку после грубого ранжирования, поскольку
PQсжимает векторы. Для финального результата требуется дополнительное точное ранжирование, что повышает вычислительные затраты и задержку. HNSW имеет меньший коэффициент сжатия (порядка 1:0.8) и обеспечивает точное ранжирование без дополнительной обработки, что снижает вычислительные затраты и задержку, но повышает затраты на хранение.Настройка recall: оба индекса поддерживают настройку полноты (recall) через параметры, но при сопоставимых значениях
recallу IVFPQ вычислительные затраты выше.Стратегия кэширования: IVFPQ позволяет балансировать стоимость памяти и задержку вычислений, регулируя долю кэша для блоков индекса, тогда как HNSW в текущей реализации поддерживает только кэширование целого файла.
Использование¶
Каждая таблица поддерживает только один векторный индекс.
Предварительные требования¶
Перед созданием векторных индексов необходимо включить функциональность, установив параметр конфигурации FE enable_experimental_vector в значение true.
Включить динамически:
ADMIN SET FRONTEND CONFIG ("enable_experimental_vector" = "true");
Для постоянного включения добавьте enable_experimental_vector = true в конфигурационный файл FE fe.conf и перезапустите FE.
Создать векторный индекс¶
В этом руководстве индексы создаются при создании таблиц. Вы также можете добавить индекс к существующей таблице.
Пример создания HNSW индекса
hnsw_vectorпо столбцуvectorв таблицеhnsw:CREATE TABLE hnsw ( id BIGINT(20) NOT NULL COMMENT "", vector ARRAY<FLOAT> NOT NULL COMMENT "", INDEX hnsw_vector (vector) USING VECTOR ( "index_type" = "hnsw", "dim"="5", "metric_type" = "l2_distance", "is_vector_normed" = "false", "M" = "16", "efconstruction" = "40" ) ) ENGINE=OLAP DUPLICATE KEY(id) DISTRIBUTED BY HASH(id) BUCKETS 1;Пример создания IVFPQ индекса
ivfpq_vectorпо столбцуvectorв таблицеivfpq:CREATE TABLE ivfpq ( id BIGINT(20) NOT NULL COMMENT "", vector ARRAY<FLOAT> NOT NULL COMMENT "", INDEX ivfpq_vector (vector) USING VECTOR ( "index_type" = "ivfpq", "dim"="5", "metric_type" = "l2_distance", "is_vector_normed" = "false", "nbits" = "16", "nlist" = "40" ) ) ENGINE=OLAP DUPLICATE KEY(id) DISTRIBUTED BY HASH(id) BUCKETS 1;
Параметры построения индекса¶
USING VECTOR
По умолчанию: N/A
Обязательный: Да
Описание: создает векторный индекс.
index_type
По умолчанию: N/A
Обязательный: Да
Описание: тип векторного индекса. Допустимые значения:
hnswиivfpq.
dim
По умолчанию: N/A
Обязательный: Да
Описание: размерность индекса. После построения индекса векторы, не соответствующие размерности, будут отвергнуты при загрузке в базовый столбец. Должно быть целым числом ≥
1.
metric_type
По умолчанию: N/A
Обязательный: Да
Описание: метрика (функция измерения) векторного индекса. Допустимые значения:
l2_distance: Евклидово расстояние. Чем меньше значение, тем выше схожесть.cosine_similarity: Косинусное сходство. Чем больше значение, тем выше схожесть.
is_vector_normed
По умолчанию: false
Обязательный: Нет
Описание: указывает, нормализованы ли векторы. Допустимые значения:
trueиfalse. Влияет только приmetric_type = cosine_similarity. Если векторы нормализованы, значение вычисляемых расстояний будет в диапазоне [-1, 1]. Сумма квадратов должна быть1, иначе вернется ошибка.
M
По умолчанию: 16
Обязательный: Нет
Описание: параметр для HNSW. Количество двунаправленных соединений, создаваемых для каждого нового элемента при построении графа. Целое число ≥
2. ЗначениеMнапрямую влияет на эффективность и точность построения и поиска. При построении каждая вершина пытается установить связи с ближайшимиMвершинами. Если у вершины уже естьMсвязей, но найден более близкий сосед, самая дальняя связь удаляется и устанавливается связь с более близким соседом. Поиск начинается с точки входа и идет по соседним вершинам. БольшееM— шире область поиска и выше эффективность, но дороже построение и хранение.
efconstruction
По умолчанию: 40
Обязательный: Нет
Описание: параметр для HNSW. Размер списка кандидатов ближайших соседей. Целое число ≥
1. Управляет глубиной поиска при построении графа: определяет размер списка кандидатов для каждой вершины. Чем большеefconstruction, тем больше кандидатов рассматривается, тем выше качество графа (например, связность), но тем выше время и сложность построения.
nbits
По умолчанию: 16
Обязательный: Нет
Описание: параметр для IVFPQ. Точность Product Quantization (PQ). Должно быть кратно
8. При IVFPQ каждый вектор делится на несколько под-векторов и квантуется;nbitsопределяет, во сколько бит квантуется каждый под-вектор. Чем большеnbits, тем выше точность квантизации, но выше издержки хранения и вычислений.
nlist
По умолчанию: 16
Обязательный: Нет
Описание: параметр для IVFPQ. Количество кластеров (inverted lists). Целое число ≥
1. Датасет делится на кластеры, центроид каждого кластера соответствует inverted list. Поиск сначала находит ближайший центроид, затем извлекает соседей из соответствующего inverted list. Большееnlist— тоньше кластеризация и выше точность, но дороже поиск.
M_IVFPQ
Обязательный: Да
Описание: параметр для IVFPQ. Количество под-векторов, на которые будет разделен исходный вектор. Индекс IVFPQ делит
dim-мерный вектор наM_IVFPQравных по длине под-векторов. Следовательно,M_IVFPQдолжен быть делителемdim.
Добавление векторного индекса¶
Вы можете добавить векторные индексы к существующей таблице, используя операторы CREATE INDEX или ALTER TABLE ADD INDEX.
CREATE INDEX ivfpq_vector
ON ivfpq (vector)
USING VECTOR (
"index_type" = "ivfpq",
"metric_type" = "l2_distance",
"is_vector_normed" = "false",
"dim"="5",
"nlist" = "256",
"nbits"="10"
);
ALTER TABLE ivfpq
ADD INDEX ivfpq_vector (vector)
USING VECTOR (
"index_type" = "ivfpq",
"metric_type" = "l2_distance",
"is_vector_normed" = "false",
"dim"="5",
"nlist" = "256",
"nbits"="10"
);
Управление векторными индексами¶
Просмотреть векторный индекс¶
Вы можете посмотреть определение векторного индекса с помощью команды SHOW CREATE TABLE:
mysql> SHOW CREATE TABLE hnsw \G
*************************** 1. row ***************************
Table: hnsw
Create Table: CREATE TABLE hnsw (
id bigint(20) NOT NULL COMMENT "",
vector array<float> NOT NULL COMMENT "",
INDEX index_vector (vector) USING VECTOR("dim" = "5", "efconstruction" = "40", "index_type" = "hnsw", "is_vector_normed" = "false", "M" = "512", "metric_type" = "l2_distance") COMMENT ''
) ENGINE=OLAP
DUPLICATE KEY(id)
DISTRIBUTED BY HASH(id) BUCKETS 1
PROPERTIES (
"compression" = "LZ4",
"fast_schema_evolution" = "true",
"replicated_storage" = "false",
"replication_num" = "3"
);
1 row in set (0.00 sec)
Удалить векторный индекс¶
Удалять векторные индексы можно с помощью DROP INDEX или ALTER TABLE DROP INDEX.
DROP INDEX ivfpq_vector ON ivfpq;
ALTER TABLE ivfpq DROP INDEX ivfpq_vector;
Выполнение ANNS с векторными индексами¶
Перед запуском векторного поиска убедитесь, что параметр конфигурации FE enable_experimental_vector установлен в true.
Требования к запросам на основе векторного индекса¶
SELECT *, <vector_index_distance_func>(v1, [1,2,3]) as dis
FROM table_name
WHERE <vector_index_distance_func>(v1, [1,2,3]) <= 10
ORDER BY <vector_index_distance_func>(v1, [1,2,3])
LIMIT 10
Чтобы использовать векторный индекс в запросах, необходимо соблюсти все нижеперечисленные требования:
Требования к ORDER BY:
Формат:
ORDER BY <vector_index_distance_func>(vector_column, constant_array)без дополнительных столбцов вORDER BY.Требования к имени
<vector_index_distance_func>:При
metric_type = l2_distanceимя функции должно бытьapprox_l2_distance.При
metric_type = cosine_similarity—approx_cosine_similarity.
Требования к параметрам
<vector_index_distance_func>:Один из аргументов
constant_array— константныйARRAY<FLOAT>с размерностью, совпадающей сdimиндекса.Другой аргумент
vector_column— столбец, по которому построен векторный индекс.
Направление сортировки:
При
metric_type = l2_distance—ASC.При
metric_type = cosine_similarity—DESC.
Обязателен
LIMIT N.
Требования к предикатам:
Все предикаты — это выражения
<vector_index_distance_func>, объединенные операторомANDи сравнением (>или<). Направление сравнения должно соответствоватьASC/DESC.Требование 1:
Для
l2_distance:col_ref <= constant.Для
cosine_similarity:col_ref >= constant.Здесь
col_ref— результат<vector_index_distance_func>(vector_column, constant_array), который можно привести кFLOATилиDOUBLE, например:approx_l2_distance(v1, [1,2,3])CAST(approx_l2_distance(v1, [1,2,3]) AS FLOAT)CAST(approx_l2_distance(v1, [1,2,3]) AS DOUBLE)
Требование 2:
Предикат должен использовать
AND, при этом каждый дочерний предикат удовлетворяет Требованию 1.
Подготовка¶
Создайте таблицы с векторными индексами и вставьте векторные данные:
CREATE TABLE test_hnsw (
id BIGINT(20) NOT NULL COMMENT "",
vector ARRAY<FLOAT> NOT NULL COMMENT "",
INDEX index_vector (vector) USING VECTOR (
"index_type" = "hnsw",
"metric_type" = "l2_distance",
"is_vector_normed" = "false",
"M" = "512",
"dim"="5")
) ENGINE=OLAP
DUPLICATE KEY(id)
DISTRIBUTED BY HASH(id) BUCKETS 1;
INSERT INTO test_hnsw VALUES
(1, [1,2,3,4,5]),
(2, [4,5,6,7,8]);
CREATE TABLE test_ivfpq (
id BIGINT(20) NOT NULL COMMENT "",
vector ARRAY<FLOAT> NOT NULL COMMENT "",
INDEX index_vector (vector) USING VECTOR (
"index_type" = "ivfpq",
"metric_type" = "l2_distance",
"is_vector_normed" = "false",
"nlist" = "256",
"nbits"="8",
"dim"="5",
"M_IVFPQ"="1")
) ENGINE=OLAP
DUPLICATE KEY(id)
DISTRIBUTED BY HASH(id) BUCKETS 1;
INSERT INTO test_ivfpq VALUES
(1, [1,2,3,4,5]),
(2, [4,5,6,7,8]);
Выполнение векторного поиска¶
Приблизительный поиск¶
Приблизительные поиски задействуют векторный индекс и ускоряют выполнение.
Следующий пример ищет top-1 приблизительного ближайшего соседа для вектора [1,1,1,1,1].
SELECT id, approx_l2_distance([1,1,1,1,1], vector)
FROM test_hnsw
ORDER BY approx_l2_distance([1,1,1,1,1], vector)
LIMIT 1;
Комбинирование скалярного и векторного поиска¶
Можно комбинировать скалярный и векторный поиск.
SELECT id, approx_l2_distance([1,1,1,1,1], vector)
FROM test_hnsw
WHERE id = 1
ORDER BY approx_l2_distance([1,1,1,1,1], vector)
LIMIT 1;
Поиск по диапазону¶
Можно выполнять поиск по диапазону для векторных данных.
В следующем примере устанавливается условие score < 40 для индекса и фильтруются векторы по диапазону score.
SELECT * FROM (
SELECT id, approx_l2_distance([1,1,1,1,1], vector) score
FROM test_hnsw
) a
WHERE score < 40
ORDER BY score
LIMIT 1;
Точные вычисления¶
Точные вычисления игнорируют векторный индекс и напрямую считают расстояния между векторами для получения точного результата.
SELECT id, l2_distance([1,1,1,1,1], vector)
FROM test_hnsw WHERE id = 1
ORDER BY l2_distance([1,1,1,1,1], vector)
LIMIT 1;
Примечание:
Разные метрики по-разному трактуют «схожесть». Для l2_distance меньшие значения означают более высокую схожесть; для cosine_similarity — большие значения. Поэтому при вычислении topN направление сортировки должно соответствовать направлению метрики: используйте ORDER BY ASC LIMIT x для l2_distance и ORDER BY DESC LIMIT x для cosine_similarity.
Тонкая настройка параметров индекса для поиска¶
Настройка параметров важна, так как влияет и на производительность, и на точность. Рекомендуется подбирать параметры на небольшом датасете и переходить к большим только после достижения ожидаемых recall и задержки.
Параметры поиска передаются через hints в SQL.
Для индекса HNSW¶
Перед началом убедитесь, что векторный столбец построен с индексом HNSW.
SELECT
/*+ SET_VAR (ann_params='{efsearch=256}') */
id, approx_l2_distance([1,1,1,1,1], vector)
FROM test_hnsw
WHERE id = 1
ORDER BY approx_l2_distance([1,1,1,1,1], vector)
LIMIT 1;
Параметр efsearch:
По умолчанию: 16
Обязательный: Нет
Описание: параметр, управляющий компромиссом точность/скорость. При поиске по иерархическому графу задает размер списка кандидатов. Чем больше
efsearch, тем выше точность, но ниже скорость.
Для индекса IVFPQ¶
Перед началом убедитесь, что векторный столбец построен с индексом IVFPQ.
SELECT
/*+ SET_VAR (ann_params='{nprobe=256,max_codes=0,scan_table_threshold=0,polysemous_ht=0,range_search_confidence=0.1}') */
id, approx_l2_distance([1,1,1,1,1], vector)
FROM test_ivfpq
ORDER BY approx_l2_distance([1,1,1,1,1], vector)
LIMIT 1;
Параметры:
nprobe
По умолчанию: 1
Обязательный: Нет
Описание: количество inverted lists, проверяемых во время поиска. Большее
nprobeдает выше точность, но ниже скорость.
max_codes
По умолчанию: 0
Обязательный: Нет
Описание: максимальное количество codes, проверяемых на один inverted list. Также влияет на точность и скорость.
scan_table_threshold
По умолчанию: 0
Обязательный: Нет
Описание: параметр, управляющий polysemous hashing. Когда Hamming distance между хэшем элемента и хэшем искомого вектора меньше порога, элемент добавляется в список кандидатов.
polysemous_ht
По умолчанию: 0
Обязательный: Нет
Описание: параметр, управляющий polysemous hashing. Когда Hamming distance между хэшем элемента и хэшем искомого вектора меньше порога, элемент напрямую добавляется в результаты.
range_search_confidence
По умолчанию: 0.1
Обязательный: Нет
Описание: «уверенность» приблизительного range search. Диапазон: [0, 1]. Значение
1дает наиболее точные результаты.
Вычисление приблизительного recall¶
Приблизительный recall можно оценить пересечением topK из полного перебора и из приблизительного поиска: Recall = TP / (TP + FN).
-- Approximate retrieval
SELECT id
FROM test_hnsw
ORDER BY approx_l2_distance([1,1,1,1,1], vector)
LIMIT 5;
8
9
7
5
1
-- Brute-force retrieval
SELECT id
FROM test_hnsw
ORDER BY l2_distance([1,1,1,1,1], vector)
LIMIT 5;
8
9
5
7
10
В примере выше приблизительный поиск вернул 8, 9, 7 и 5. Корректный результат — 8, 9, 5, 7 и 10. В этом случае recall равен 4/5 = 80%.
Проверка, что векторный индекс задействован¶
Выполните команду EXPLAIN для запроса. Если в свойствах OlapScanNode указано VECTORINDEX: ON, значит векторный индекс применен к приблизительному поиску.
Пример:
> EXPLAIN SELECT id FROM t_test_vector_table ORDER BY approx_l2_distance([1,1,1,1,1], vector) LIMIT 5;
+-----------------------------------------------------------------------------------------------------------------------------------------------------+
| Explain String |
+-----------------------------------------------------------------------------------------------------------------------------------------------------+
| PLAN FRAGMENT 0 |
| OUTPUT EXPRS:1: id |
| PARTITION: UNPARTITIONED |
| |
| RESULT SINK |
| |
| 4:Project |
| | <slot 1> : 1: id |
| | limit: 5 |
| | |
| 3:MERGING-EXCHANGE |
| limit: 5 |
| |
| PLAN FRAGMENT 1 |
| OUTPUT EXPRS: |
| PARTITION: RANDOM |
| |
| STREAM DATA SINK |
| EXCHANGE ID: 03 |
| UNPARTITIONED |
| |
| 2:TOP-N |
| | order by: <slot 3> 3: approx_l2_distance ASC |
| | offset: 0 |
| | limit: 5 |
| | |
| 1:Project |
| | <slot 1> : 1: id |
| | <slot 3> : 4: __vector_approx_l2_distance |
| | |
| 0:OlapScanNode |
| TABLE: t_test_vector_table |
| VECTORINDEX: ON |
| IVFPQ: OFF, Distance Column: <4:__vector_approx_l2_distance>, LimitK: 5, Order: ASC, Query Vector: [1, 1, 1, 1, 1], Predicate Range: -1.0 |
| PREAGGREGATION: ON |
| partitions=1/1 |
| rollup: t_test_vector_table |
| tabletRatio=1/1 |
| tabletList=11302 |
| cardinality=2 |
| avgRowSize=4.0 |
+-----------------------------------------------------------------------------------------------------------------------------------------------------+
Ограничения¶
Каждая таблица поддерживает только один векторный индекс.