Prefiltrado KNN Manticore Search con ACORN-1

# Prefiltrado KNN en Manticore Search: Optimizando HNSW con ACORN-1

El prefiltrado KNN en Manticore Search versión 19.0.1+ integra filtros de atributos directamente en la travesía del grafo HNSW. Esto elimina la ineficiencia del post-filtrado, donde KNN escanea todo el conjunto de datos y luego se aplican los filtros. En un catálogo de 10 millones de productos con un filtro de categoría 'electrónicos' (5% de documentos), el post-filtrado podría devolver menos de los k resultados solicitados, desperdiciando recursos en nodos irrelevantes.

El prefiltrado verifica las condiciones durante la exploración de candidatos, asegurando exactamente k resultados de documentos que coincidan.

Problemas del post-filtrado y el cambio al prefiltrado

En el post-filtrado, HNSW ignora los filtros: el algoritmo encuentra los k vectores globalmente más cercanos y luego descarta los que no coinciden. Con filtros estrictos (p. ej., categoría='electrónicos' AND precio<500), el grafo explora principalmente áreas irrelevantes, reduciendo el recall y aumentando la latencia.

Ejemplo de consulta SQL con prefiltrado automático:

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;

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

Los filtros de categoría y precio se verifican durante la travesía de HNSW.

Prefiltrado ingenuo: Principios y limitaciones

El enfoque ingenuo recorre HNSW como siempre, pero solo añade nodos que pasen el filtro a la cola de prioridad. Los nodos no coincidentes aún ayudan en la navegación para mantener la conectividad del grafo.

Limitación: Se calculan distancias para todos los vecinos, independientemente de los filtros. Con 5% de selectividad, el 95% de los cálculos (la operación más costosa) se desperdicia.

ACORN-1 en Manticore: Optimización avanzada

Manticore implementa ACORN-1 para filtros selectivos (<60% de documentos):

• Verificación de filtro antes de distancia: Los vecinos se filtran antes de calcular la distancia. Los no coincidentes se saltan sin evaluación.
• Expansión adaptativa: Desde nodos no coincidentes, el algoritmo explora sus vecinos (hasta 3-4 niveles), enfocándose en encontrar candidatos adecuados.

Esto reduce los cálculos de distancia en un 95% con baja selectividad, acelerando las búsquedas sin pérdida de calidad.

ACORN-1 se activa automáticamente para alta selectividad.

Selección automática de estrategia de ejecución

El planificador de Manticore evalúa la selectividad usando histogramas de atributos:

• HNSW estándar: >60% documentos pasan el filtro — prefiltrado ingenuo.
• ACORN-1: 1–60% — traversa optimizada.
• Escaneo completo: <1% (p. ej., 50 de 10 millones) — escaneo directo de documentos filtrados, obviando HNSW.

Compara nodos HNSW esperados vs. tamaño del subconjunto filtrado.

Gestión de modos de filtrado

Post-filtrado (prefilter=0 o "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;

Escaneo completo (fullscan=1 o "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;

El post-filtrado es ideal para vecinos globales o >95% paso de documentos. El escaneo completo funciona para conjuntos filtrados minúsculos.

| Modo | Selectividad | Ventajas | Desventajas |

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

| Post-filtrado | Alta (>95%) | Simplicidad, predictibilidad | Menos de k resultados |

| Prefiltrado (ingenuo) | Media (60–95%) | k resultados fiables | Sobrecarga |

| ACORN-1 | Baja (1–60%) | Ahorro computacional | Complejidad implementación |

| Escaneo completo | Muy baja (<1%) | Recall exacto | Complejidad lineal |

Conclusiones clave

• El prefiltrado es el predeterminado para KNN+atributos, garantizando k resultados.
• ACORN-1 ahorra hasta 95% de cálculos de distancia con <60% selectividad.
• Escaneo completo automático para filtros ultra-selectivos.
• Post-filtrado para ranking global o depuración.
• El planificador se adapta por consulta/segmento usando histogramas.

— Editorial Team