Préfiltrage KNN Manticore Search avec ACORN-1

# Prétraitement KNN dans Manticore Search : Optimisation HNSW avec ACORN-1

Le prétraitement KNN dans Manticore Search version 19.0.1+ intègre directement les filtres d'attributs dans la traversée du graphe HNSW. Cela élimine l'inefficacité du post-filtrage, où KNN parcourt l'ensemble du jeu de données avant d'appliquer les filtres. Dans un catalogue de 10 millions de produits avec un filtre de catégorie 'électronique' (5 % des documents), le post-filtrage peut renvoyer moins que les k résultats demandés, gaspillant des ressources sur des nœuds non pertinents.

Le prétraitement vérifie les conditions pendant l'exploration des candidats, garantissant exactement k résultats parmi les documents correspondants.

Problèmes du post-filtrage et passage au prétraitement

Dans le post-filtrage, HNSW ignore les filtres : l'algorithme trouve les k vecteurs les plus proches globalement, puis élimine les non-correspondants. Avec des filtres stricts (ex. : catégorie='électronique' ET prix<500), le graphe explore majoritairement des zones non pertinentes, réduisant le rappel et augmentant la latence.

Exemple de requête SQL avec prétraitement automatique :

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 en 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
}

Les filtres de catégorie et de prix sont vérifiés pendant la traversée HNSW.

Prétraitement naïf : Principes et limites

L'approche naïve traverse HNSW comme d'habitude mais n'ajoute à la file de priorité que les nœuds passant les filtres. Les nœuds non correspondants aident encore à la navigation pour maintenir la connectivité du graphe.

Limite : Les distances sont calculées pour tous les voisins, indépendamment des filtres. À 5 % de sélectivité, 95 % des calculs (opération la plus coûteuse) sont gaspillés.

ACORN-1 dans Manticore : Optimisation avancée

Manticore implémente ACORN-1 pour les filtres sélectifs (<60 % des documents) :

• Vérification du filtre avant distance : Les voisins sont filtrés avant le calcul de distance. Les non-correspondants sont ignorés sans évaluation.
• Expansion adaptative : À partir de nœuds non correspondants, l'algorithme explore leurs voisins (jusqu'à 3-4 niveaux), en se concentrant sur la recherche de candidats valides.

Cela réduit les calculs de distance de 95 % à faible sélectivité, accélérant les recherches sans perte de qualité.

ACORN-1 s'active automatiquement pour les fortes sélectivités.

Sélection automatique de la stratégie d'exécution

Le planificateur de Manticore évalue la sélectivité via les histogrammes d'attributs :

• HNSW standard : >60 % des documents passent le filtre — prétraitement naïf.
• ACORN-1 : 1-60 % — traversée optimisée.
• Balayage complet : <1 % (ex. : 50 sur 10 millions) — balayage direct des documents filtrés, contournant HNSW.

Il compare le nombre attendu de nœuds HNSW visités à la taille du sous-ensemble filtré.

Gestion des modes de filtrage

Post-filtrage (prefilter=0 ou "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;

Balayage complet (fullscan=1 ou "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;

Le post-filtrage convient aux cas nécessitant les voisins globaux ou >95 % de passage. Le balayage complet est idéal pour les ensembles filtrés minuscules.

| Mode | Sélectivité | Avantages | Inconvénients |

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

| Post-filtrage | Élevée (>95 %) | Simplicité, prévisibilité | Moins de k résultats |

| Prétraitement (naïf) | Moyenne (60-95 %) | k résultats fiables | Surcharge |

| ACORN-1 | Faible (1-60 %) | Économies de calcul | Complexité d'implémentation |

| Balayage complet | Très faible (<1 %) | Rappel exact | Complexité linéaire |

Points clés

• Le prétraitement est la valeur par défaut pour KNN+attributs, garantissant k résultats.
• ACORN-1 économise jusqu'à 95 % des calculs de distance à <60 % de sélectivité.
• Balayage complet automatique pour les filtres ultra-sélectifs.
• Post-filtrage pour un classement global ou du débogage.
• Le planificateur s'adapte par requête/par segment via les histogrammes.

— Editorial Team