Векторный поиск редко происходит изолированно. Почти всегда есть фильтры — диапазон цен, категория, временное окно, географическая граница. Вопрос: когда эти фильтры применяются?
Ответ оказывает неожиданно большое влияние на качество результатов.
Предфильтрация 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), когда вы знаете, что линейное сканирование — правильная стратегия для ваших данных.