Prefiltracja KNN Manticore Search z ACORN-1

Prefiltracja KNN w Manticore Search: optymalizacja HNSW z ACORN-1

Wstępna filtracja KNN w Manticore Search wersji 19.0.1+ integruje filtry atrybutowe bezpośrednio w obwodzie grafu HNSW. Eliminuje to nieefektywność postfiltracji, gdzie KNN skanuje cały zbiór danych, a filtry są stosowane post factum. W katalogu z 10 milionami produktów z filtrem według kategorii 'elektronika' (5% dokumentów) postfiltracja może zwrócić mniej niż żądane k wyników, marnując zasoby na nieistotne węzły.

Prefiltracja sprawdza warunki na etapie badania kandydatów, zapewniając dokładne k wyników z odpowiednich dokumentów.

Problemy postfiltracji i przejście do prefiltracji

W postfiltracji HNSW ignoruje filtry: algorytm znajduje k najbliższych wektorów globalnie, a następnie odsiewa niepasujące. Przy ścisłych filtrach (np. kategoria='elektronika' AND cena<500) graf bada głównie nieistotne obszary, zmniejszając recall i zwiększając opóźnienie.

Przykład zapytania SQL z automatyczną prefiltracją:

SELECT id, title, knn_dist()
FROM products
WHERE knn(embedding, (0.12, 0.45, 0.78, 0.33))
  AND kategoria = 'elektronika'
  AND cena < 500
LIMIT 10;

Ekwivalent w JSON:

{
    "table": "products",
    "knn": {
        "field": "embedding",
        "query": [0.12, 0.45, 0.78, 0.33]
    },
    "query": {
        "bool": {
            "must": [
                { "equals": { "kategoria": "elektronika" } },
                { "range": { "cena": { "lt": 500 } } }
            ]
        }
    },
    "limit": 10
}

Filtry category i price są sprawdzane podczas przechodzenia HNSW.

Naiwna prefiltracja: zasady i ograniczenia

Naiwne podejście przechodzi HNSW standardowo, ale dodaje do kolejki priorytetowej tylko węzły spełniające filtr. Niepasujące węzły uczestniczą w nawigacji, zapewniając spójność grafu.

Ograniczenie: odległości są obliczane dla wszystkich sąsiadów, niezależnie od filtra. Przy selektywności 5%, 95% obliczeń (najbardziej kosztowna operacja) jest marnowana.

ACORN-1 w Manticore: zaawansowana optymalizacja

Manticore implementuje ACORN-1 dla selektywnych filtrów (<60% dokumentów):

• Sprawdzenie filtra przed odległością: sąsiedzi są sprawdzani pod kątem filtra przed obliczeniem odległości. Odfiltrowani są pomijani bez oceny.
• Adaptacyjne rozszerzenie: od niepasujących węzłów algorytm przechodzi do ich sąsiadów (do 3–4 poziomów), skupiając się na znalezieniu pasujących kandydatów.

To redukuje obliczenia odległości o 95% przy niskiej selektywności, przyspieszając wyszukiwanie bez utraty jakości.

ACORN-1 jest aktywowany automatycznie przy wysokiej selektywności.

Automatyczny wybór strategii wykonania

Planista Manticore ocenia selektywność na podstawie histogramów atrybutów:

• Standardowy HNSW: >60% dokumentów spełnia filtr — naiwna prefiltracja.
• ACORN-1: 1–60% — zoptymalizowane przejście.
• Fullscan: <1% (np. 50 z 10 mln) — bezpośrednie skanowanie odfiltrowanych dokumentów, omijając HNSW.

Porównanie kosztów: oczekiwana liczba odwiedzonych węzłów HNSW vs. rozmiar odfiltrowanego podzbioru.

Zarządzanie trybami filtracji

Postfiltracja (prefilter=0 lub "prefilter": false):

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

Pełne skanowanie (fullscan=1 lub "fullscan": true):

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

Postfiltracja jest odpowiednia dla przypadków, gdzie ważni są globalni najbliżsi sąsiedzi lub >95% dokumentów spełnia filtr. Fullscan — dla małych odfiltrowanych zbiorów.

| Tryb | Selektywność | Zalety | Wady |

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

| Postfiltracja | Wysoka (>95%) | Prostota, przewidywalność | Mniej k wyników |

| Prefiltracja (naiwna) | Średnia (60–95%) | Stabilne k wyniki | Nakłady dodatkowe |

| ACORN-1 | Niska (1–60%) | Oszczędność obliczeń | Złożoność implementacji |

| Fullscan | Bardzo niska (<1%) | Dokładna pełność | Liniowa złożoność |

Co jest ważne

• Prefiltracja jest domyślna dla KNN+atrybuty, gwarantuje k wyników.
• ACORN-1 oszczędza do 95% obliczeń odległości przy selektywności <60%.
• Automatyczne fullscan dla ekstremalnie selektywnych filtrów.
• Postfiltracja dla globalnego rankingu lub debugowania.
• Planista adaptuje się per-zapytanie/per-segment na podstawie histogramów.

— Editorial Team