Объяснение индекса

Индекс - это дополнительная структура, построенная поверх данных. Его внутренняя структура зависит от используемого алгоритма поиска ближайших соседей. Индекс ускоряет поиск, но требует дополнительного времени на предварительную обработку, места и оперативной памяти во время поиска. Кроме того, использование индекса обычно снижает коэффициент запоминания (хотя этот эффект и незначителен, но все же имеет значение). Поэтому в этой статье мы расскажем, как минимизировать затраты на использование индекса и при этом получить максимальную выгоду.

Обзор

В Milvus индексы специфичны для полей, а применимые типы индексов зависят от типов данных целевых полей. Будучи профессиональной векторной базой данных, Milvus уделяет особое внимание повышению производительности как векторного поиска, так и скалярной фильтрации, поэтому предлагает различные типы индексов.

В следующей таблице перечислены связи между типами данных полей и применимыми типами индексов.

Тип данных поля	Применяемые типы индексов
FLOAT_VECTOR FLOAT16_VECTOR BFLOAT16_VECTOR INT8_ВЕКТОР	FLAT IVF_FLAT IVF_SQ8 IVF_PQ IVF_RABITQ HNSW HNSW_SQ HNSW_PQ HNSW_PRQ DISKANN SCANN AISAQ GPU_CAGRA GPU_IVF_FLAT GPU_IVF_PQ GPU_BRUTE_FORCE
БИНАРНЫЙ_ВЕКТОР	BIN_FLAT BIN_IVF_FLAT MINHASH_LSH
РАЗРЕЖЕННЫЙ_ПЛОСКИЙ_ВЕКТОР	РАЗРЕЖЕННЫЙ_ИНВЕРТИРОВАННЫЙ_ИНДЕКС
VARCHAR	ИНВЕРТИРОВАННЫЙ (рекомендуется) BITMAP Тройка
BOOL	BITMAP (рекомендуется) ИНВЕРТИРОВАННЫЙ
INT8 INT16 INT32 INT64	ИНВЕРТИРОВАННЫЙ STL_SORT
FLOAT DOUBLE	ИНВЕРТИРОВАННЫЙ
ARRAY (элементы типов BOOL, INT8/16/32/64 и VARCHAR)	BITMAP (рекомендуется)
ARRAY (элементы типов BOOL, INT8/16/32/64, FLOAT, DOUBLE и VARCHAR)	ИНВЕРТИРОВАННЫЙ
JSON	ИНВЕРТИРОВАННЫЙ

Эта статья посвящена тому, как выбрать подходящие векторные индексы. Для скалярных полей вы всегда можете использовать рекомендуемый тип индекса.

Выбор подходящего типа индекса для векторного поиска может существенно повлиять на производительность и использование ресурсов. При выборе типа индекса для векторного поля необходимо учитывать различные факторы, включая базовую структуру данных, использование памяти и требования к производительности.

Анатомия векторного индекса

Как показано на диаграмме ниже, тип индекса в Milvus состоит из трех основных компонентов, а именно: структуры данных, квантования и уточнителя. Квантование и рафинер необязательны, но широко используются из-за значительного баланса "выгода-лучше-чем-затраты".

Анатомия векторного индекса

Во время создания индекса Milvus комбинирует выбранную структуру данных и метод квантования, чтобы определить оптимальную скорость расширения. Во время запроса система извлекает topK × expansion rate векторов-кандидатов, применяет рафинер для пересчета расстояний с большей точностью и, наконец, возвращает наиболее точные результаты topK. Этот гибридный подход позволяет сбалансировать скорость и точность, ограничивая ресурсоемкое уточнение отфильтрованным подмножеством кандидатов.

Структура данных

Структура данных является основополагающим слоем индекса. К распространенным типам относятся:

• Инвертированный файл (IVF)

  Типы индексов серии IVF позволяют Milvus группировать векторы в ведра с помощью разбиения на основе центроида. В общем случае можно предположить, что все векторы в ведерке, скорее всего, будут близки к вектору запроса, если центроид ведерка близок к вектору запроса. Исходя из этого предположения, Milvus сканирует только вкрапления векторов в тех ведрах, центроиды которых близки к вектору запроса, вместо того чтобы исследовать весь набор данных. Эта стратегия позволяет снизить вычислительные затраты, сохраняя приемлемую точность.

  Такой тип индексной структуры данных идеально подходит для больших массивов данных, требующих высокой производительности.

• Структура на основе графов

  Графовая структура данных для векторного поиска, например Hierarchical Navigable Small World(HNSW), представляет собой многоуровневый граф, в котором каждый вектор соединяется со своими ближайшими соседями. Запросы перемещаются по этой иерархии, начиная с грубых верхних слоев и переходя на нижние, что обеспечивает эффективную сложность поиска за логарифмическое время.

  Этот тип индексной структуры данных отлично подходит для высокоразмерных пространств и сценариев, требующих запросов с низкой задержкой.

Квантование

Квантование позволяет сократить занимаемую память и вычислительные затраты за счет более грубого представления:

• Скалярная квантование (например, SQ8) позволяет Milvus сжимать каждую размерность вектора в один байт (8 бит), сокращая использование памяти на 75 % по сравнению с 32-битными плавающими числами при сохранении разумной точности.

• Product Quantization(PQ) позволяет Milvus разбивать векторы на подвекторы и кодировать их с помощью кластеризации на основе кодовой книги. Это позволяет достичь более высоких коэффициентов сжатия (например, 4-32x) ценой незначительного снижения запоминания, что делает его подходящим для сред с ограниченным объемом памяти.

Рафинер

Квантование по своей сути несет потери. Для поддержания коэффициента отзыва квантование постоянно создает больше кандидатов top-K, чем необходимо, что позволяет рафинерам использовать более высокую точность для дальнейшего отбора результатов top-K из этих кандидатов, повышая коэффициент отзыва.

Например, рафинер FP32 работает с кандидатами результатов поиска, возвращенными квантованием, пересчитывая расстояния, используя точность FP32, а не квантованные значения.

Это очень важно для приложений, требующих компромисса между эффективностью и точностью поиска, таких как семантический поиск или рекомендательные системы, где незначительные изменения расстояний существенно влияют на качество результатов.

Резюме

Эта многоуровневая архитектура - грубая фильтрация с помощью структур данных, эффективные вычисления с помощью квантования и настройка точности с помощью уточнения - позволяет Milvus адаптивно оптимизировать компромисс между точностью и производительностью.

Компромиссы в производительности

При оценке производительности очень важно сбалансировать время сборки, количество запросов в секунду (QPS) и скорость запоминания. Общие правила таковы:

• Графовые типы индексов обычно превосходят варианты ЭКО по QPS.

• ЭКО-варианты особенно хорошо подходят для сценариев с большим topK (например, более 2 000).

• PQ обычно обеспечивает лучший коэффициент запоминания при одинаковой степени сжатия по сравнению с SQ, хотя последний обеспечивает более высокую производительность.

• Использование жестких дисков для части индекса (как в DiskANN) помогает управлять большими наборами данных, но при этом возникают потенциальные узкие места в IOPS.

Емкость

Пропускная способность обычно включает в себя соотношение между размером данных и доступной оперативной памятью. Когда речь идет о емкости, учитывайте следующее:

• Если четверть необработанных данных помещается в памяти, рассмотрите DiskANN из-за его стабильной задержки.

• Если все исходные данные помещаются в память, рассмотрите типы индексов на основе памяти и mmap.

• Вы можете использовать типы индексов с квантованием и mmap, чтобы обменять точность на максимальную емкость.

Отзыв

Отзыв обычно связан с коэффициентом фильтрации, который относится к данным, отфильтрованным перед поиском. При работе с отзывом учитывайте следующее:

• Если коэффициент фильтрации составляет менее 85 %, индексы на основе графов превосходят варианты ЭКО.

• Если коэффициент фильтрации составляет от 85 % до 95 %, используйте варианты ЭКО.

• Если коэффициент фильтрации превышает 98 %, используйте Brute-Force (FLAT) для получения наиболее точных результатов поиска.

Производительность

Производительность поиска обычно включает в себя top-K, то есть количество записей, которые возвращает поиск. При работе с производительностью учитывайте следующее:

• Для поиска с небольшим top-K (например, 2 000), требующего высокого коэффициента запоминания, графовые типы индексов превосходят варианты ЭКО.

• Для поиска с большим top-K (по сравнению с общим количеством векторных вкраплений) варианты ЭКО являются лучшим выбором, чем графовые типы индексов.

• Для поиска со средним размером top-K и высоким коэффициентом фильтрации лучше использовать варианты ЭКО.

Матрица принятия решений: Выбор наиболее подходящего типа индекса

Следующая таблица представляет собой матрицу решений, на которую вы можете ориентироваться при выборе подходящего типа индекса.

Сценарий	Рекомендуемый индекс	Примечания
Исходные данные помещаются в памяти	HNSW, ЭКО + уточнение	Используйте HNSW для низкогоk/ высокого запоминания.
Сырые данные на диске, SSD	DiskANN	Оптимально для запросов, чувствительных к задержкам.
Необработанные данные на диске, ограниченное количество оперативной памяти	IVFPQ/SQ + mmap	Баланс между доступом к памяти и диску.
Высокий коэффициент фильтрации (>95 %)	Brute-Force (FLAT)	Избегает накладных расходов на индексы для маленьких наборов кандидатов.
Большой k (≥1 % от набора данных)	ЭКО	Обрезка кластеров сокращает вычисления.
Чрезвычайно высокий коэффициент отзыва (>99 %)	Brute-Force (FLAT) + GPU	--

Оценка использования памяти

На потребление памяти индексом влияют его структура данных, степень сжатия за счет квантования и используемый рефайнер. Вообще говоря, индексы на основе графов обычно занимают больше памяти из-за структуры графа (например, HNSW), что обычно влечет за собой заметные накладные расходы на пространство в расчете на вектор. ЭКО и его разновидности, напротив, более эффективны с точки зрения памяти, так как занимают меньше места на векторе. Однако продвинутые техники, такие как DiskANN, позволяют размещать части индекса, например граф или рефайнер, на диске, что снижает нагрузку на память при сохранении производительности.

В частности, использование памяти индексом может быть рассчитано следующим образом:

Использование памяти ЭКО-индекса

ЭКО-индексы балансируют между эффективностью использования памяти и производительностью поиска за счет разбиения данных на кластеры. Ниже приведена разбивка памяти, используемой 1 миллионом 128-мерных векторов, проиндексированных с помощью вариантов ЭКО.

1. Рассчитайте память, используемую центроидами.

   Типы индексов серии IVF позволяют Milvus группировать векторы в кластеры с помощью разбиения на основе центроидов. Каждый центроид включается в индекс при встраивании необработанных векторов. Если разделить векторы на 2 000 кластеров, расход памяти можно рассчитать следующим образом:

   2,000 clusters × 128 dimensions × 4 bytes = 1.0 MB
   

2. Вычислите память, используемую при назначении кластеров.

   Каждый векторный эмбеддинг назначается кластеру и хранится в виде целочисленных идентификаторов. Для 2 000 кластеров достаточно целого числа размером 2 байта. Использование памяти можно рассчитать следующим образом:

   1,000,000 vectors × 2 bytes = 2.0 MB
   

3. Рассчитайте сжатие, вызванное квантованием.

   В вариантах ЭКО обычно используются PQ и SQ8, и расход памяти можно оценить следующим образом:

   • Использование PQ с 8 субквантователями

     1,000,000 vectors × 8 bytes = 8.0 MB
     

   • Использование SQ8

     1,000,000 vectors × 128 dimensions × 1 byte = 128 MB 
     

   В следующей таблице приведены расчетные значения использования памяти при различных конфигурациях:

   Конфигурация	Оценка памяти	Общая память
   IVF-PQ (без доработки)	1,0 МБ + 2,0 МБ + 8,0 МБ	11,0 МБ
   IVF-PQ + 10% необработанное уточнение	1,0 МБ + 2,0 МБ + 8,0 МБ + 51,2 МБ	62,2 МБ
   ЭКО-SQ8 (без доработки)	1,0 МБ + 2,0 МБ + 128 МБ	131,0 МБ
   IVF-FLAT (полные необработанные векторы)	1,0 МБ + 2,0 МБ + 512 МБ	515,0 МБ

4. Рассчитайте накладные расходы на уточнение.

   Варианты ЭКО часто используются в паре с рефайнером для повторного ранжирования кандидатов. Для поиска, извлекающего 10 лучших результатов с коэффициентом расширения 5, затраты на уточнение можно оценить следующим образом:

   10 (topK) x 5 (expansion rate) = 50 candidates
   50 candidates x 128 dimensions x 4 bytes = 25.6 KB
   

Использование памяти индекса на основе графов

Индексы на основе графов, такие как HNSW, требуют значительного объема памяти для хранения как структуры графа, так и необработанных векторных вкраплений. Ниже приводится подробная разбивка памяти, потребляемой 1 миллионом 128-мерных векторов, проиндексированных с помощью индекса типа HNSW.

1. Вычислите память, используемую структурой графа.

   Каждый вектор в HNSW поддерживает связи со своими соседями. При степени графа (ребра на узел), равной 32, потребляемая память может быть рассчитана следующим образом:

   1,000,000 vectors × 32 links × 4 bytes (for 32-bit integer storage) = 128 MB  
   

2. Вычислите память, используемую необработанными векторными вкраплениями.

   Память, потребляемую при хранении несжатых векторов FP32, можно рассчитать следующим образом:

   1,000,000 vectors × 128 dimensions × 4 bytes = 512 MB  
   

   При использовании HNSW для индексации 1 миллиона 128-мерных векторных вкраплений общее количество используемой памяти составит 128 МБ (граф) + 512 МБ (векторы) = 640 МБ.

3. Рассчитайте сжатие, вызванное квантованием.

   Квантование уменьшает размер вектора. Например, использование PQ с 8 субквантователями (8 байт на вектор) приводит к значительному сжатию. Память, занимаемую сжатыми векторными вкраплениями, можно рассчитать следующим образом:

   1,000,000 vectors × 8 bytes = 8 MB
   

   При этом достигается 64-кратное сжатие по сравнению с вкраплениями необработанных векторов, а общее количество памяти, используемое индексом типа HNSWPQ, составит 128 МБ (граф) + 8 МБ (сжатый вектор) = 136 МБ.

4. Рассчитайте накладные расходы на уточнение.

   Уточнение, такое как повторное ранжирование с использованием необработанных векторов, временно загружает в память высокоточные данные. Для поиска, извлекающего 10 лучших результатов с частотой расширения 5, накладные расходы на уточнение можно оценить следующим образом:

   10 (topK) x 5 (expansion rate) = 50 candidates
   50 candidates x 128 dimensions x 4 bytes = 25.6 KB
   

Другие соображения

В то время как ЭКО и индексы на основе графов оптимизируют использование памяти за счет квантования, файлы с отображением памяти (mmap) и DiskANN решают проблемы, когда наборы данных превышают объем доступной памяти с произвольным доступом (RAM).

DiskANN

DiskANN - это индекс на основе графа Vamana, который соединяет точки данных для эффективной навигации во время поиска, применяя при этом PQ для уменьшения размера векторов и быстрого вычисления приблизительного расстояния между ними.

Граф Vamana хранится на диске, что позволяет DiskANN работать с большими наборами данных, которые в противном случае были бы слишком велики, чтобы поместиться в памяти. Это особенно полезно для наборов данных из миллиардов точек.

Файлы с отображением памяти (mmap)

Сопоставление с памятью (Mmap) обеспечивает прямой доступ из памяти к большим файлам на диске, позволяя Milvus хранить индексы и данные как в памяти, так и на жестких дисках. Такой подход помогает оптимизировать операции ввода-вывода, снижая накладные расходы на вызовы ввода-вывода в зависимости от частоты доступа, тем самым увеличивая емкость хранения коллекций без существенного влияния на производительность поиска.

В частности, вы можете настроить Milvus на отображение в памяти исходных данных в определенных полях вместо их полной загрузки в память. Таким образом, вы можете получить прямой доступ к полям, не беспокоясь о проблемах с памятью, и расширить емкость коллекции.