Векторный поиск редко используется сам по себе. Почти всегда есть фильтры — диапазон цен, категория, временное окно, географическая граница. Вопрос в том, когда именно эти фильтры применяются.
Ответ неожиданно сильно влияет на качество результатов.
Предварительная фильтрация KNN доступна в Manticore Search начиная с версии 19.0.1.
Проблема постфильтрации
Рассмотрим каталог товаров из 10 миллионов позиций. Пользователь запрашивает 10 ближайших соседей к вектору запроса, ограничивая выборку условием category = 'electronics'. При постфильтрации поиск KNN сначала выполняется по всему набору данных, а уже потом к результатам применяется фильтр. Если электроника составляет 5 % каталога, граф в основном исследует нерелевантные для такого запроса узлы. Хуже того, многие из k ближайших соседей могут вообще не относиться к электронике, поэтому итоговый набор результатов может оказаться намного меньше запрошенного. Просим 10 результатов, получаем 2.
Это фундаментальное ограничение постфильтрации: граф HNSW не учитывает ваши фильтры. Он находит ближайшие векторы вообще, а не ближайшие векторы, которые соответствуют вашим критериям. Чем избирательнее фильтр, тем заметнее становится проблема.
Что меняет предфильтрация
Предварительная фильтрация передаёт фильтр прямо в процесс обхода графа HNSW. По мере того как алгоритм исследует кандидатные узлы, каждый из них проверяется на соответствие фильтру до того, как будет добавлен в кучу результатов. Только подходящие документы вносят вклад в итоговые k результатов. Это означает, что вы стабильно получаете именно те k результатов, которые запросили, при условии, что в наборе данных вообще существует k подходящих документов.
В Manticore Search предварительная фильтрация включена по умолчанию, когда запрос сочетает поиск KNN с фильтрами по атрибутам. Никакого специального синтаксиса не требуется:
SELECT id, title, knn_dist() FROM products WHERE knn(embedding, (0.12, 0.45, 0.78, 0.33)) AND category = 'electronics' AND price < 500 LIMIT 10;
И category = 'electronics', и price < 500 проверяются прямо во время обхода HNSW, а не после. Эквивалентный JSON‑запрос:
POST /search { "table": "products", "knn": { "field": "embedding", "query": [0.12, 0.45, 0.78, 0.33] }, "query": { "bool": { "must": [ { "equals": { "category": "electronics" } }, { "range": { "price": { "lt": 500 } } } ] } }, "limit": 10 }
Наивная предварительная фильтрация и её ограничения
Очевидный первый подход довольно прост: обходить граф HNSW обычным способом, вычислять расстояния до каждого соседа, но добавлять в кучу результатов только узлы, соответствующие фильтру. Отфильтрованные узлы всё равно участвуют в навигации — если несоответствующий узел имеет конкурентное расстояние, он попадает в очередь кандидатов, и мы исследуем его соседей. Фильтр лишь ограничивает то, что попадает в результаты.
На практике это действительно работает неплохо. Граф остаётся связным, потому что отфильтрованные узлы всё ещё участвуют в обходе. Но по мере роста избирательности фильтра проявляется серьёзная проблема с производительностью: для каждого ещё не посещённого соседа приходится вычислять расстояние независимо от того, проходит ли он фильтр. А вычисление расстояния — самая дорогая операция во всём поиске. Если фильтру соответствует 5 % документов, то 95 % этой работы уходит на результаты, которые тут же отбрасываются. Алгоритм платит полную цену за навигацию, но почти ничего не получает от большей части выполненной работы.
Как Manticore решает проблему: ACORN-1
Manticore использует алгоритм на основе ACORN-1 (из статьи ACORN , SIGMOD 2024), который улучшает наивную предфильтрацию двумя способами:
Без вычисления расстояния для отфильтрованных узлов. При посещении соседей узла ACORN-1 сначала проверяет фильтр и вычисляет расстояние только для тех узлов, которые его проходят. Отфильтрованные соседи вообще не оцениваются. Если 95 % узлов не проходят фильтр, это экономит примерно 95 % работы по вычислению расстояний по сравнению с наивным подходом.
Адаптивное расширение через отфильтрованные узлы. Когда сосед не проходит фильтр, алгоритм просматривает уже его соседей в поисках узлов, которые проходят фильтр и находятся дальше. Если и эти соседи не проходят фильтр, а подходящих кандидатов пока недостаточно, процесс продолжается — на 3 перехода, на 4 перехода, столько, сколько нужно. Чем избирательнее фильтр, тем агрессивнее расширяется алгоритм. Такой целенаправленный обход несоответствующих областей позволяет добраться до подходящих кандидатов без оценки несоответствующих узлов по пути.
Представьте, что вы ищете итальянские рестораны в городе. При наивном подходе приходится заходить в каждый ресторан, проверять меню и оставлять только итальянские. ACORN-1 сначала смотрит на вывеску — «Французский, пропустить; Тайский, пропустить» — даже не заходя внутрь. А когда он видит квартал, где итальянских ресторанов нет, он идёт дальше, заглядывая за каждый угол, пока не найдёт итальянское заведение по соседству.
Manticore активирует ACORN-1, когда фильтр проходит менее чем 60 % всех документов. Выше этого порога наивная предварительная фильтрация сама по себе работает достаточно хорошо.
Автоматический переход к полному перебору
Предварительная фильтрация хорошо работает в широком диапазоне избирательности фильтра, но есть крайний случай: что, если фильтру соответствуют всего 50 документов из 10 миллионов? Обход графа HNSW — даже с ACORN-1 — посетит намного больше узлов, чем простое сканирование этих 50 документов напрямую.
Manticore обнаруживает это автоматически. Когда предварительная фильтрация включена, планировщик запросов оценивает стоимость обхода HNSW по сравнению с полным перебором расстояний по отфильтрованному подмножеству. Он использует оценки избирательности на основе гистограмм, чтобы предсказать, сколько документов пройдёт фильтр, а затем сравнивает это с ожидаемым числом узлов, которые посетит HNSW. Если полный перебор дешевле, Manticore полностью пропускает HNSW и напрямую сканирует отфильтрованные документы.
Это означает, что вам не нужно думать о крайних случаях. Предфильтрация адаптируется: ACORN-1 для умеренной избирательности, полный перебор для экстремальной и стандартный HNSW, когда фильтра нет вовсе.
Когда всё-таки стоит использовать постфильтрацию
Предфильтрация не всегда лучший выбор. В некоторых случаях предпочтительнее постфильтрация:
Когда вам нужны ближайшие векторы независимо от фильтров. Постфильтрация возвращает k ближайших соседей из полного набора данных, а затем удаляет несоответствующие. Если ваше приложение допускает, что результатов будет меньше k, и вам важнее качество векторных расстояний, постфильтрация оказывается проще и предсказуемее.
Когда фильтр проходит у большинства документов. Если 95 % документов проходят фильтр, предварительная фильтрация только добавляет накладные расходы почти без пользы — почти каждый кандидат всё равно подходит.
Когда вы отлаживаете систему или проводите бенчмарк. Постфильтрация даёт чистую базовую линию: результаты чистого HNSW с наложенным поверх фильтром. Так проще понять, связана ли проблема качества с графом или с самим фильтром.
Как явно запросить постфильтрацию в SQL:
SELECT id, knn_dist() FROM products WHERE knn(embedding, (0.12, 0.45, 0.78, 0.33), { prefilter=0 }) AND category = 'electronics' LIMIT 10;
В JSON установите "prefilter": false внутри объекта knn:
POST /search { "table": "products", "knn": { "field": "embedding", "query": [0.12, 0.45, 0.78, 0.33], "prefilter": false }, "query": { "equals": { "category": "electronics" } }, "limit": 10 }
Принудительный полный перебор
Если ваш набор данных достаточно мал или фильтры достаточно избирательны и здесь лучше линейное сканирование, вы можете принудительно включить режим полного перебора напрямую:
SELECT id, knn_dist() FROM products WHERE knn(embedding, (0.12, 0.45, 0.78, 0.33), { fullscan=1 }) AND category = 'electronics' LIMIT 10;
Это полностью обходит HNSW и вычисляет точные расстояния по всем документам, прошедшим фильтр. Такой режим гарантирует идеальную полноту ценой линейного сканирования.
Итоги
Предфильтрация — это режим по умолчанию в Manticore и правильный выбор для большинства KNN-запросов с фильтрами. Она гарантирует получение k результатов, если они существуют. Manticore автоматически выбирает лучшую стратегию в зависимости от избирательности фильтра: стандартный отфильтрованный HNSW, когда подходит большинство документов, ACORN‑1, когда проходит менее 60 % документов, и полный перебор, когда отфильтрованное подмножество достаточно мало для прямого сканирования. Планировщик запросов оценивает избирательность фильтра для каждого запроса и каждого сегмента, поэтому вручную настраивать ничего не нужно.
Используйте постфильтрацию (prefilter=0 в SQL, "prefilter": false в JSON), когда вам нужны ближайшие векторы по всему набору данных и вы можете допустить меньше k результатов. Используйте полный перебор (fullscan=1 в SQL, "fullscan": true в JSON), когда знаете, что линейное сканирование — правильная стратегия для ваших данных.
