Векторная база данных на практике: точный поиск, HNSW и IVF

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

11 мин чтенияai · векторный поиск · hnsw · ivf

Коротко

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

  • Точный поиск сравнивает все допустимые векторы. Это отправная точка для небольшого каталога и эталон для измерений.
  • Приближённый поиск ближайших соседей (approximate nearest neighbor search, ANN) проверяет часть пространства. Он тратит меньше работы, но пропускает соседей.
  • HNSW идёт по графу, IVF открывает несколько групп вокруг ближайших центров. Настройки обоих измеряйте под теми же фильтрами, что и в рабочем поиске.
  • Выбирайте индекс по полноте, задержке, памяти и свежести результата. Один тест по замороженному каталогу не покажет, что происходит при массовом обновлении остатков.

Сквозной пример с каталогом

Покупатель задаёт запрос «лёгкие непромокаемые ботинки для города», выбирает размер 42 и самовывоз из Казани. У каждой карточки есть описание, идентификатор, список размеров и остатки. Кодировщик превращает описание и поисковую фразу в эмбеддинги. Сходство помогает подобрать модель обуви, а остаток определяет, можно ли показать её для выбранного пункта.

Предположим, ближайшие к запросу три карточки находятся на другом складе. Четвёртая и пятая подходят. Если индекс вернул три результата, а приложение проверило остатки только потом, пользователь увидит пустой список. На тех же данных точный поиск среди карточек, доступных в Казани, вернёт два товара. При измерении качества сравнивайте индекс именно с этим эталоном. Сравнение с глобальной выдачей присвоит вашей системе ошибку за корректно скрытые карточки.

ШагКто → комуДанные
ПодготовкаКаталог → кодировщикТекст модели, материал и назначение
ЗагрузкаКаталог и кодировщик → индексВектор, ID, метаданные и версия пространства
ПоискПриложение → индексВектор запроса, размер 42, склад Казани, число результатов
УточнениеИндекс → приложениеID кандидатов, их оценки и применённые фильтры
ПоказПриложение → покупательПодходящие карточки с подтверждённым наличием

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

Как устроен точный эталон

Фильтруйте кандидатов, затем вычисляйте расстояние от запроса до каждой оставшейся записи. Для первых десяти результатов полного порядка не требуется: держите кучу из десяти кандидатов и заменяйте худшего при улучшении. Число сравнений векторов всё равно пропорционально числу допустимых кандидатов и размерности. Выигрыш от фильтра появляется только если движок ограничил набор до расчёта расстояний.

Предположим, описания кодируются в 768 координат. В документации Flat-индексов Faiss на вектор отводится четыре байта на координату. Для миллиона карточек это около 3,07 ГБ только на векторы и 768 млн пар координат на полный проход по одному вопросу. Если фильтр отобрал 5 000 карточек, число пар падает до 3,84 млн. Здесь нет памяти на граф, метаданные, реплики и текст. Время запроса надо измерить на своём оборудовании, поскольку оно зависит от пропускной способности памяти, реализации сравнения и одновременной нагрузки.

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

Что меняет HNSW

HNSW (Hierarchical Navigable Small World) — многоуровневый граф близости. В работе Малкова и Яшунина верхние слои содержат разреженные подмножества точек, по которым поиск быстро перемещается в нужную область. На нижнем уровне граф гуще. Там алгоритм проверяет несколько перспективных путей и находит соседей точнее. На схеме каталога верхние слои напоминают переход между областями «городская обувь», «туризм» и «зимняя обувь», но связи строятся по расстояниям, без этих ярлыков.

Ширина поиска задаёт, сколько перспективных вариантов держать при обходе. При маленькой ширине ответ приходит быстрее, но часть нужных путей отбрасывается. Увеличение числа связей при построении даёт графу больше путей ценой памяти. Эти параметры воздействуют на разные этапы. Если просто удвоить ширину обхода, неудачно построенные связи останутся. Если перестроить граф плотнее, каждый запрос всё равно нужно проверить с рабочим бюджетом. В терминологии Faiss соответствующие параметры включают efSearch, efConstruction и M.

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

Что меняет IVF

IVF (inverted file) хранит списки векторов вокруг центроидов, то есть представителей групп. На построении индекс назначает векторы спискам. На запросе он сортирует центры по расстоянию и открывает несколько лучших списков. В IVF Flat внутри выбранных списков сравнение идёт по исходным векторам. В описании Faiss этот путь отделён от вариантов, которые дополнительно сжимают векторы. При сжатии изменяется ещё и точность самих оценок.

Представьте, что список «городские ботинки» заканчивается рядом со списком «лёгкая походная обувь». Самый близкий подходящий товар оказался по другую сторону границы. Сравнение только первого списка его пропустит. Увеличение nprobe, числа просматриваемых списков, даст больше кандидатов. Открывая все списки IVF Flat, вы возвращаетесь к сравнению всех их точек при тех же фильтрах. Следите также за перекосом размера списков. Один переполненный список может доминировать в хвосте задержки, даже когда среднее число просмотренных позиций выглядит хорошо.

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

На границе двух списков, пример на Python

Свернём вектор обуви до одной координаты, чтобы расположение было видно без рисунка. Центры и распределение заданы вручную. Запрос равен 4,9 и тянется к левому центру 0. При этом ближайшая доступная точка находится в правом списке. Четвёртый товар совсем близок, но он другого размера. Сначала вычислим точный эталон, затем проверим два бюджета IVF.

def nearest(query, rows, size, k): allowed = [(name, abs(point - query)) for name, point, stocked_size in rows if stocked_size == size] return sorted(allowed, key=lambda row: (row[1], row[0]))[:k] groups = [ (0.0, [("Город", 4.0, 42), ("Ботинок 41", 4.8, 41)]), (10.0, [("Мембрана", 5.1, 42), ("Трек", 10.0, 42)]), ] query = 4.9 all_rows = [row for _, rows in groups for row in rows] truth = nearest(query, all_rows, 42, 2) expected = {name for name, _ in truth} print("Точный поиск:", ", ".join(name for name, _ in truth)) ordered = sorted(groups, key=lambda group: abs(query - group[0])) for probes in (1, 2): candidates = [row for _, rows in ordered[:probes] for row in rows] found = [name for name, _ in nearest(query, candidates, 42, 2)] recall = len(expected.intersection(found)) / len(expected) print(f"Списков: {probes}, выдача: {', '.join(found)}, Recall@2: {recall:.2f}") assert [name for name, _ in truth] == ["Мембрана", "Город"]

Вывод программы.

Точный поиск: Мембрана, Город Списков: 1, выдача: Город, Recall@2: 0.50 Списков: 2, выдача: Мембрана, Город, Recall@2: 1.00

Recall@k, или полнота среди первых k, здесь равна доле точных соседей, которых сохранил приближённый поиск. При одном списке из двух найден один, то есть 0,50. Пустые эталоны оценивайте отдельно. Если магазин не продаёт размер 49, пустая выдача для него правильна, а деление на число эталонных соседей здесь ничего не определяет. Для интерфейса дополнительно измеряйте, сколько раз вы показали меньше двух карточек, когда в каталоге доступны как минимум две.

Как выбрать режим для рабочего каталога

Проверьте популярный и редкий размеры по отдельности. Один вариант — искать точно после фильтра, когда осталось мало строк. Второй — использовать HNSW или IVF с учётом метаданных, если движок поддерживает подходящий план. Третий — взять больше кандидатов и применить постфильтр. Последний путь годится, только если вы измеряете пустую выдачу и ограничиваете число повторных расширений. Если среди первых двадцати почти нет товара размера 42 из Казани, ещё двадцать проверок редко окупают такой план без изменения области поиска.

Выберите требования до теста. Например, эксперимент допускает потерю нескольких соседей, но запрещает показывать недоступный товар. Прогоните каждый вариант на тех же запросах и зафиксируйте Recall@10, задержку p95, расход памяти и время построения. Затем повторите измерение, пока обновляются цены и остатки. Если при записи тормозит поиск, статическая таблица сравнения индексов скрыла рабочую проблему.

Посмотрите и на качество самого представления. Высокий Recall@10 подтверждает совпадение с точным поиском по вектору. Если точный эталон ставит сандалии выше ботинок, индекс исправно воспроизводит слабое ранжирование. Для артикулов оставьте инвертированный индекс или точное поле. Для запросов по описанию проверьте полезность карточек на размеченных покупательских запросах, а не только на внутреннем эталоне векторов.

Что делать, если индекс отстал от каталога

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

В потоке обновлений передавайте номер версии карточки. Если событие с версией 15 пришло после версии 16, оно не должно возвращать старый остаток или описание. Удаление проверяйте тем же способом. После снятия товара с продажи отправьте позднее событие с его прежним состоянием и убедитесь, что карточка не появилась вновь. В тестах новой сборки запишите позицию обработки потока и снимок каталога. Это позволит отличить пропуск при загрузке от задержки обновления и восстановить обработку с нужного места после перезапуска.

Типичные ошибки

  1. Возвращаете меньше карточек после постфильтра. Пользователь видит один товар вместо пяти. Сравните число кандидатов до и после фильтра с точным эталоном на том же размере и складе.
  2. Проверяете индекс другой метрикой. Выдача расходится даже на полном переборе. Напечатайте несколько расстояний и убедитесь, что оба пути одинаково нормализуют векторы и сортируют оценки.
  3. Увеличиваете параметры вслепую. Широкий обход улучшил полноту, но сломал p95. Снимите несколько точек полноты и задержки и выберите минимальный бюджет, который проходит обе границы.
  4. Забываете про изменения каталога. После массового ввода новой категории один список переполнен. Сравните размеры списков до и после и разделите замеры по старым и новым категориям.
  5. Отождествляете качество индекса с качеством поиска. Индекс возвращает точных соседей, а отзывы покупателей ухудшаются. Проверьте эталоны пригодности товаров отдельно от совпадения векторных результатов.

Когда отдельная база лишняя

При 5 000 карточках после фильтра сначала замерьте точное сравнение рядом с существующим хранилищем. Если оно выдерживает нагрузку, отдельный кластер создаст работу по обновлению и контролю доступности. Если нужна точная карточка по артикулу, используйте поле артикула. Добавляйте ANN там, где измерения показали дорогой перебор, и сохраняйте точный путь для проверки. У двух запросов одного каталога вполне могут быть разные планы.

Что спрашивают на собеседовании

  1. Что приближает ANN? Он ищет подмножество истинных ближайших соседей по заданной метрике. Я сравню первые десять результатов с точным поиском по тем же допустимым товарам.
  2. Чем отличаются HNSW и IVF? Первый следует по графу близости, второй открывает списки около ближайших центров. Для графа я настраиваю ширину обхода, для IVF — число открываемых списков.
  3. Почему запрос с фильтром потерял результаты? Если я отфильтровал только первые десять глобальных соседей, доступные товары могли остаться за их пределами. Я сравню поведение с точным поиском по складу и проверю план запроса.
  4. Когда оставить точный поиск? Я оставлю его, если задержка на допустимом подмножестве укладывается в требование под рабочей нагрузкой. Для 5 000 строк и миллиона строк выводы могут различаться.
  5. Как оценить смену индекса? Зафиксирую снимок и сравню метрику полноты, задержку, память и скорость обновления. После этого проверю типичные покупательские запросы на полезность карточек.

Потренироваться в спокойной обстановке

Все задачи