ACORN-1을 사용한 Manticore Search의 KNN 사전 필터링

# Manticore Search에서 KNN 사전 필터링: HNSW 최적화와 ACORN-1

Manticore Search 버전 19.0.1+의 KNN 사전 필터링은 속성 필터를 HNSW 그래프 탐색에 직접 통합합니다. 이는 KNN이 전체 데이터셋을 스캔한 후 필터를 적용하는 사후 필터링의 비효율성을 제거합니다. 1천만 개 제품 카탈로그에서 '전자제품' 카테고리 필터(문서의 5%)를 적용할 때, 사후 필터링은 요청된 k 결과보다 적은 결과를 반환할 수 있으며, 관련 없는 노드에 자원을 낭비합니다.

사전 필터링은 후보 탐색 중 조건을 확인하여 일치하는 문서에서 정확히 k개의 결과를 보장합니다.

사후 필터링의 문제점과 사전 필터링으로의 전환

사후 필터링에서는 HNSW가 필터를 무시합니다: 알고리즘은 전역 k개의 가장 가까운 벡터를 찾은 후 비일치 항목을 버립니다. 엄격한 필터(예: category='electronics' AND price<500)에서 그래프는 대부분 관련 없는 영역을 탐색하여 재현율을 낮추고 지연 시간을 증가시킵니다.

자동 사전 필터링이 적용된 예제 SQL 쿼리:

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;

JSON 형식으로 동등한 쿼리:

{
    "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 탐색 중에 확인됩니다.

단순 사전 필터링: 원리와 한계

단순 접근법은 HNSW를 평소처럼 탐색하지만 필터를 통과한 노드만 우선순위 큐에 추가합니다. 비일치 노드는 그래프 연결성을 유지하기 위해 여전히 탐색에 도움을 줍니다.

한계: 필터와 무관하게 모든 이웃에 대해 거리 계산이 수행됩니다. 5% 선택성에서 95%의 계산(가장 비용이 많이 드는 작업)이 낭비됩니다.

Manticore의 ACORN-1: 고급 최적화

Manticore는 선택적 필터(문서의 <60%)에 대해 ACORN-1을 구현합니다:

• 거리 계산 전 필터 확인: 이웃은 거리 계산 전에 필터링됩니다. 비일치 항목은 평가 없이 건너뜁니다.
• 적응형 확장: 비일치 노드에서 알고리즘은 이웃(최대 3~4 레벨)을 탐색하며 적합한 후보를 중점적으로 찾습니다.

이는 낮은 선택성에서 거리 계산을 95% 줄여 검색 속도를 높이면서 품질 손실 없이 처리합니다.

ACORN-1은 높은 선택성에서 자동 활성화됩니다.

자동 실행 전략 선택

Manticore의 플래너는 속성 히스토그램을 사용해 선택성을 평가합니다:

• 표준 HNSW: >60% 문서가 필터 통과 — 단순 사전 필터링.
• ACORN-1: 1–60% — 최적화된 탐색.
• 전체 스캔: <1% (예: 1천만 중 50개) — HNSW를 우회하고 필터링된 문서를 직접 스캔.

예상 HNSW 방문 노드 수와 필터링된 부분집합 크기를 비교합니다.

필터링 모드 관리

사후 필터링 (prefilter=0 또는 "prefilter": false):

SELECT id, knn_dist()
FROM products
WHERE knn(embedding, (0.12, 0.45, 0.78, 0.33), { prefilter=0 })
  AND category = 'electronics'
LIMIT 10;

전체 스캔 (fullscan=1 또는 "fullscan": true):

SELECT id, knn_dist()
FROM products
WHERE knn(embedding, (0.12, 0.45, 0.78, 0.33), { fullscan=1 })
  AND category = 'electronics'
LIMIT 10;

사후 필터링은 전역 가장 가까운 이웃이 필요하거나 >95% 문서가 통과하는 경우에 적합합니다. 전체 스캔은 매우 작은 필터링 집합에 효과적입니다.

| 모드 | 선택성 | 장점 | 단점 |

|------|-------------|------------|---------------|

| 사후 필터링 | 높음 (>95%) | 간단함, 예측 가능 | k 결과 미만 |

| 사전 필터링 (단순) | 중간 (60–95%) | 안정적 k 결과 | 오버헤드 |

| ACORN-1 | 낮음 (1–60%) | 계산 절감 | 구현 복잡성 |

| 전체 스캔 | 매우 낮음 (<1%) | 정확한 재현율 | 선형 복잡도 |

주요 요약

• KNN+속성에 대한 기본값은 사전 필터링으로 k 결과를 보장합니다.
• ACORN-1은 <60% 선택성에서 최대 95% 거리 계산을 절감합니다.
• 초선택적 필터에 자동 전체 스캔.
• 전역 랭킹이나 디버깅에 사후 필터링.
• 플래너는 히스토그램을 사용해 쿼리/세그먼트별로 적응합니다.

— Editorial Team