KNN-Vorfilterung Manticore Search mit ACORN-1

KNN-Vorfilterung in Manticore Search: HNSW-Optimierung mit ACORN-1

Die KNN-Vorfilterung in Manticore Search ab Version 19.0.1+ integriert Attributfilter direkt in die HNSW-Graphdurchsuchung. Dadurch entfällt die Ineffizienz der Nachfilterung, bei der KNN den gesamten Datensatz durchsucht und Filter danach angewendet werden. In einem Katalog mit 10 Millionen Produkten und einem Filter für die Kategorie „Elektronik“ (5 % der Dokumente) liefert die Nachfilterung oft weniger als die gewünschten k Ergebnisse und verschwendet Ressourcen an irrelevanten Knoten.

Die Vorfilterung prüft Bedingungen während der Kandidatensuche und gewährleistet exakt k Ergebnisse aus passenden Dokumenten.

Probleme der Nachfilterung und der Wechsel zur Vorfilterung

Bei der Nachfilterung ignoriert HNSW die Filter: Der Algorithmus findet die global k nächsten Vektoren und verwirft dann die Nichtpassenden. Bei strengen Filtern (z. B. Kategorie='Elektronik' UND Preis<500) durchsucht der Graph hauptsächlich irrelevante Bereiche, was den Recall mindert und die Latenz erhöht.

Beispiel-SQL-Abfrage mit automatischer Vorfilterung:

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;

Äquivalent in 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
}

Kategorie- und Preis-Filter werden während der HNSW-Durchsuchung geprüft.

Naive Vorfilterung: Prinzipien und Grenzen

Der naive Ansatz durchläuft HNSW wie gewohnt, fügt aber nur filterpassende Knoten in die Prioritätswarteschlange ein. Nichtpassende Knoten unterstützen dennoch die Navigation, um die Graphverbundenheit zu wahren.

Grenze: Entfernungen werden für alle Nachbarn berechnet, unabhängig von Filtern. Bei 5 % Selektivität sind 95 % der Berechnungen (der teuerste Schritt) verschwendet.

ACORN-1 in Manticore: Fortgeschrittene Optimierung

Manticore setzt ACORN-1 für selektive Filter (<60 % der Dokumente) ein:

• Filterprüfung vor Entfernungsberechnung: Nachbarn werden gefiltert, bevor Entfernungen berechnet werden. Nichtpassende werden übersprungen.
• Adaptive Erweiterung: Von nichtpassenden Knoten aus erkundet der Algorithmus deren Nachbarn (bis zu 3–4 Ebenen), um passende Kandidaten zu finden.

Das spart bei niedriger Selektivität bis zu 95 % der Entfernungsberechnungen und beschleunigt Suchen ohne Qualitätsverlust.

ACORN-1 aktiviert sich bei hoher Selektivität automatisch nicht.

Automatische Auswahl der Ausführungsstrategie

Der Planner von Manticore bewertet die Selektivität anhand von Attribut-Histogrammen:

• Standard-HNSW: >60 % Dokumente passieren Filter – naive Vorfilterung.
• ACORN-1: 1–60 % – optimierte Durchsuchung.
• Vollscan: <1 % (z. B. 50 von 10 Millionen) – direkter Scan der gefilterten Dokumente, HNSW umgangen.

Es vergleicht erwartete HNSW-Knotenbesuche mit der Größe des gefilterten Teilsatzes.

Verwalten der Filtermodi

Nachfilterung (prefilter=0 oder "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;

Vollscan (fullscan=1 oder "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;

Nachfilterung eignet sich für globale nächste Nachbarn oder >95 % Durchlass. Vollscan für winzige gefilterte Mengen.

| Modus | Selektivität | Vorteile | Nachteile |

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

| Nachfilterung | Hoch (>95 %) | Einfachheit, Vorhersagbarkeit | Weniger als k Ergebnisse |

| Vorfilterung (naiv) | Mittel (60–95 %) | Sichere k Ergebnisse | Overhead |

| ACORN-1 | Niedrig (1–60 %) | Rechensparsamkeit | Implementierungsaufwand |

| Vollscan | Sehr niedrig (<1 %) | Exakter Recall | Lineare Komplexität |

Wichtige Erkenntnisse

• Vorfilterung ist Standard für KNN+Attribute und garantiert k Ergebnisse.
• ACORN-1 spart bis zu 95 % Entfernungsberechnungen bei <60 % Selektivität.
• Automatischer Vollscan für extrem selektive Filter.
• Nachfilterung für globale Ranglisten oder Debugging.
• Planner passt pro Abfrage/pro Segment anhand von Histogrammen an.

— Editorial Team