Manticore Search 中的 KNN 预过滤

Manticore Search 中的 KNN 预过滤

已发布: Mar 29, 2026
自动翻译: KNN prefiltering in Manticore Search

向量搜索很少孤立发生。你几乎总是会有过滤器——价格范围、类别、日期窗口、地理边界。问题是：这些过滤器何时被应用？

答案对结果质量产生惊人的影响。

KNN 预过滤功能从 Manticore Search 版本 19.0.1 开始可用。

后过滤的问题

考虑一个包含 1000 万件商品的目录。用户要求查询向量的 10 个最近邻，但限制为 category = 'electronics'。使用后过滤时，KNN 搜索首先在整个数据集上运行，然后将过滤器应用于结果。如果电子产品占目录的 5%，图会探索大量无关的节点。更糟糕的是，最近的 k 个邻居可能根本不是电子产品，因此最终结果集可能远小于请求的。要求 10 个结果，只得到 2 个。

这是后过滤的根本限制：HNSW 图不知道你的过滤器。它找到的是整体上最近的向量，而不是符合你标准的最近向量。过滤器越选择性，问题越严重。

预过滤的不同之处

预过滤将过滤器直接传递到 HNSW 图遍历过程中。当算法探索候选节点时，每个节点在添加到结果堆之前都会被检查过滤器。只有匹配的文档才会贡献到最终的 k 个结果中。这意味着只要你请求的 k 个匹配文档存在于数据集中，你就能可靠地得到 k 个结果。

在 Manticore Search 中，当查询结合 KNN 搜索和属性过滤器时，默认启用预过滤。不需要特殊语法：

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;

category = 'electronics' 和 price < 500 都在 HNSW 遍历期间被评估，而不是之后。等效的 JSON 查询：

POST /search
{
    "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
}

简单预过滤及其局限性

显而易见的第一种方法是直接的：正常遍历 HNSW 图，为每个邻居计算距离，但仅将符合过滤器的节点添加到结果堆中。被过滤的节点仍参与导航——如果一个不匹配的节点有竞争力的距离，它会进入候选队列，其邻居会被探索。过滤器仅控制哪些内容进入结果。

这实际上运行得相当不错。由于被过滤的节点仍被遍历，图保持连接。但它有一个性能问题，随着过滤器的选择性增强而恶化：每个未访问的邻居都会计算距离，无论是否通过过滤器。距离计算是搜索中最昂贵的操作。当过滤器匹配 5% 的文档时，95% 的工作量产生的结果会被立即丢弃。算法为导航支付了全部成本，但大部分工作没有产生结果。

Manticore 的解决方案：ACORN-1

Manticore 使用基于 ACORN-1 的算法（来自 ACORN 论文，SIGMOD 2024），在两个方面改进了简单预过滤：

对被过滤的节点不计算距离。 当访问一个节点的邻居时，ACORN-1 首先检查过滤器，仅对通过的节点计算距离。被过滤的邻居永远不会被评分。当 95% 的节点未通过过滤器时，这比简单方法节省了约 95% 的距离计算工作。

通过被过滤节点的自适应扩展。 当邻居未通过过滤器时，算法会查看该节点自身的邻居，寻找更远的通过过滤器的节点。如果这些邻居也未通过过滤器且尚未找到足够的匹配候选，它会继续扩展——3 跳、4 跳，直到需要为止。过滤器越选择性，算法扩展得越激进。这种有针对性的非匹配区域行走方式可以找到匹配候选，而无需评分沿途的非匹配节点。

想象一下在城市中寻找意大利餐厅。简单方法会检查每家餐厅的菜单，只保留意大利餐厅。ACORN-1 会先看招牌——“法式，跳过；泰式，跳过”——而无需进入店内。当看到一连串非意大利餐厅时，它会走过它们，每转一个角都窥探一下，直到找到另一边的意大利餐厅。

当通过过滤器的文档少于 60% 时，Manticore 会激活 ACORN-1。当阈值高于此，简单预过滤本身运行良好。

自动暴力回退

预过滤在广泛的过滤选择性范围内表现良好，但有一个极端情况：如果只有 50 个文档符合过滤器（在 1000 万个文档中）？即使使用 ACORN-1，遍历 HNSW 图会访问比直接扫描这 50 个文档多得多的节点。

Manticore 会自动检测到这一点。当启用预过滤时，查询规划器会估计 HNSW 遍历的成本与对过滤子集进行暴力距离扫描的成本。它使用基于直方图的选择性估计来预测通过过滤器的文档数量，然后将其与 HNSW 预计访问的节点数进行比较。如果暴力方法更便宜，Manticore 会完全跳过 HNSW，直接扫描过滤后的文档。

这意味着你无需考虑边缘情况。预过滤会自适应：中等选择性使用 ACORN-1，极端选择性使用暴力方法，无过滤时使用标准 HNSW。

何时使用后过滤

预过滤并非总是最佳选择。在某些情况下，后过滤更优：

当你想要最接近的向量而不管过滤条件时。 后过滤会从完整数据集中获取k个最近邻，然后移除不匹配的结果。如果你的应用可以容忍获得少于k个结果，并且你最关心的是向量距离的质量，那么后过滤更简单且可预测。
当过滤条件匹配大多数文档时。 如果95%的文档通过过滤，预过滤几乎没有任何好处，却增加了开销——几乎所有候选者都会匹配。
当你进行调试或基准测试时。 后过滤为你提供了一个干净的基准线：纯HNSW结果加上顶部的过滤器。这使得更容易确定质量问题是来自图还是过滤器。

要在 SQL 中明确请求后过滤：

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

在 JSON 中，将 "prefilter": false 设置在 knn 对象内部：

POST /search
{
    "table": "products",
    "knn": {
        "field": "embedding",
        "query": [0.12, 0.45, 0.78, 0.33],
        "prefilter": false
    },
    "query": {
        "equals": { "category": "electronics" }
    },
    "limit": 10
}

强制使用暴力扫描

如果你知道你的数据集足够小，或者你的过滤条件足够选择性，使得线性扫描是正确的策略，你可以直接强制使用暴力模式：

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

这会完全跳过HNSW，并在通过过滤的所有文档上计算精确距离。它以线性时间扫描为代价，保证完美的召回率。

总结

预过滤是 Manticore 的默认设置，对于大多数过滤后的 KNN 查询来说是正确的选择。它保证你获得k个结果（如果存在）。Manticore 会根据过滤器的选择性自动选择最佳策略：当大多数文档匹配时使用标准过滤后的HNSW，当少于60%的文档通过时使用ACORN-1（节省过滤掉的节点的距离计算），当过滤后的子集足够小可以直接扫描时使用暴力扫描。查询规划器会按查询和分段估算过滤选择性，因此无需调整。

在需要全局最接近的向量且可以容忍获得少于k个结果时，使用后过滤（SQL 中的 prefilter=0，JSON 中的 "prefilter": false）。当知道线性扫描是你的数据的正确策略时，使用暴力扫描（SQL 中的 fullscan=1，JSON 中的 "fullscan": true）。