Předfiltrace KNN Manticore Search s ACORN-1

Předfiltrace KNN v Manticore Search: optimalizace HNSW s ACORN-1

Předfiltrace KNN v Manticore Search verze 19.0.1+ integruje atributní filtry přímo do přímého průchodu grafem HNSW. To odstraňuje neefektivitu postfiltrace, kde KNN skenuje celý dataset a filtry se aplikují dodatečně. V katalogu s 10 miliony produktů s filtrem podle kategorie 'electronics' (5 % dokumentů) může postfiltrace vrátit méně než požadovaných k výsledků, což plýtvá prostředky na nerelevantní uzly.

Předfiltrace kontroluje podmínky ve fázi zkoumání kandidátů, zajišťuje přesných k výsledků z vhodných dokumentů.

Problémy postfiltrace a přechod k předfiltraci

V postfiltraci HNSW ignoruje filtry: algoritmus najde k nejbližších vektorů globálně, pak odfiltruje neodpovídající. Při přísných filtrech (například category='electronics' AND price<500) graf zkoumá převážně nerelevantní oblasti, snižuje recall a zvyšuje latenci.

Příklad SQL dotazu s automatickou předfiltrací:

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;

Ekvivalent v 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
}

Filtry category a price se kontrolují během průchodu HNSW.

Naivní předfiltrace: principy a omezení

Naivní přístup obchází HNSW standardně, ale přidává do prioritní fronty pouze uzly, které projdou filtrem. Neodpovídající uzly se účastní navigace, což zajišťuje spojitost grafu.

Omezení: vzdálenosti se počítají pro všechny sousedy, nezávisle na filtru. Při selektivitě 5 % je 95 % výpočtů (nejnáročnější operace) promrhaných.

ACORN-1 v Manticore: pokročilá optimalizace

Manticore implementuje ACORN-1 pro selektivní filtry (<60 % dokumentů):

• Kontrola filtru před vzdáleností: sousedi se kontrolují na filtr před výpočtem vzdálenosti. Odfiltrovaní jsou přeskočeni bez hodnocení.
• Adaptivní rozšíření: z neodpovídajících uzlů algoritmus přechází k jejich sousedům (až 3–4 úrovně), soustředě na hledání vhodných kandidátů.

To snižuje výpočty vzdáleností o 95 % při nízké selektivitě, urychluje vyhledávání bez ztráty kvality.

ACORN-1 se aktivuje automaticky při vysoké selektivitě.

Automatický výběr strategie provádění

Plánovač Manticore vyhodnocuje selektivitu podle histogramů atributů:

• Standardní HNSW: >60 % dokumentů prochází filtrem — naivní předfiltrace.
• ACORN-1: 1–60 % — optimalizovaný průchod.
• Fullscan: <1 % (například 50 z 10 milionů) — přímé skenování odfiltrovaných dokumentů, obejití HNSW.

Srovnání nákladů: očekávaný počet navštívených uzlů HNSW vs. velikost odfiltrované podmnožiny.

Řízení režimů filtrace

Postfiltrace (prefilter=0 nebo "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;

Úplný průchod (fullscan=1 nebo "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;

Postfiltrace je vhodná pro případy, kde jsou důležití globální nejbližší sousedé nebo >95 % dokumentů prochází filtrem. Fullscan — pro malé odfiltrované množiny.

| Režim | Selektivita | Výhody | Nevýhody |

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

| Postfiltrace | Vysoká (>95%) | Jednoduchost, předvídatelnost | Méně k výsledků |

| Předfiltrace (naivní) | Střední (60–95%) | Stabilní k výsledků | Režijní náklady |

| ACORN-1 | Nízká (1–60%) | Úspora výpočtů | Složitost implementace |

| Fullscan | Velmi nízká (<1%) | Přesná úplnost | Lineární složitost |

Co je důležité

• Předfiltrace — výchozí pro KNN+atributy, garantuje k výsledků.
• ACORN-1 šetří až 95 % výpočtů vzdáleností při selektivitě <60 %.
• Automatický fullscan pro extrémně selektivní filtry.
• Postfiltrace pro globální hodnocení nebo ladění.
• Plánovač se přizpůsobuje per-dotaz/per-segment podle histogramů.

— Editorial Team