尧图网站建设 
作者来自 Elastic Panagiotis BailisElasticsearch 现在会针对每个查询决定是在向量搜索之前还是之后执行 kNN 过滤。在一个包含 1000 万个向量的数据集上在 120 组基准测试中有 104 组采用后置过滤的速度更快同时仍能返回 k 个结果。现在Elasticsearch 会针对每个查询决定是在向量搜索之前还是之后应用 kNN 过滤。在包含 100 万个向量的 segment 上在搜索之后检查一个宽泛的match_phrase过滤条件耗时不到 1 毫秒而在搜索之前检查则需要 33.4 毫秒。在包含 1000 万个向量的数据集上在 120 组基准测试中后置过滤有 104 组速度更快同时 recall 与前置过滤相差不超过 0.01。你可以通过这个面向 Search AI 的自主学习实践课程亲自体验向量搜索。你现在可以开始免费云试用也可以在你的本地机器上试用 Elastic。Elasticsearch 现在会针对每个查询决定是在向量搜索之前还是之后应用 kNN 过滤。knn子句中的过滤条件例如租户 ID 或语言会作为前置过滤运行因此会在搜索开始之前对每个 segment 中的每个文档进行评估。当过滤条件匹配数据集中的足够多文档时Elasticsearch 会先执行向量搜索然后只针对返回的候选项检查过滤条件。候选池的大小会通过统计方式确定以确保至少有k个结果通过过滤。如果结果数量不足Elasticsearch 会重试一次然后回退到前置过滤搜索。你的查询保持不变并且仍然可以获得 k 个结果。预计这项功能将在 Elasticsearch 9.6 中默认启用。kNN 过滤在 Elasticsearch 中如何工作简单回顾一下Elasticsearch 针对dense_vector字段提供了两种近似最近邻结构。HNSW是一种邻近图搜索会从一个邻居移动到另一个邻居同时将目前找到的距离最近的num_candidates个向量保留为搜索波束。IVF即bbq_disk索引类型会围绕质心对向量进行聚类每个质心都有一个包含其向量的倒排列表并扫描距离查询最近的倒排列表它扫描的 segment 比例即访问比例由num_candidates和k推导得出。HNSW 图和 DiskBBQ 这两篇文章对二者都有深入介绍。接下来所有内容的关键在于这两种结构都不是一个覆盖整个索引的单一结构。每个 Lucene segment 都拥有自己的 HNSW 图或自己的一组 IVF 倒排列表因此 kNN 查询会分别搜索每个 segment 并合并结果首先在每个 shard 内合并然后再由协调节点进行合并。因此搜索在开始探索之前需要准备的任何内容都需要针对每个 segment 分别准备一次。现在让我们在 kNN 查询中添加一个filterPOST my-index/_search { knn: { field: embedding, query_vector: [0.12, -0.03, ...], k: 10, num_candidates: 100, filter: { term: { language: en } } } }因为过滤条件位于knn子句内部所以它属于前置过滤这 10 个结果是在所有匹配language: en的文档中距离最近的 10 个文档。为了实现这一点搜索必须知道它遇到的每个文档是否通过过滤条件。在每个 segment 中这一过程分为两个步骤。步骤 1将过滤条件物化为 bitset这两种结构都不会按照 doc ID 顺序访问文档。HNSW 遍历会跳转到图中的邻居而 IVF 会一次扫描一个质心对应的倒排列表这意味着文档 ID 会按照向量邻近关系所决定的任意顺序到达。搜索需要随时回答 “doc 84,219 是否匹配” 这样的问题而过滤条件的常规DocIdSetIterator只能向前移动无法做到这一点。在搜索开始之前会在整个 segment 上完整执行过滤条件并将匹配结果记录到 bitset 中。对于 HNSW这一过程发生在 Lucene 的AcceptDocs中// org.apache.lucene.search.AcceptDocs private void createBitSetAcceptDocsIfNecessary() throws IOException { if (acceptBitSet null) { acceptBitSet Objects.requireNonNull(createBitSet(iterator(), liveDocs, maxDoc)); cardinality acceptBitSet.cardinality(); } }createBitSet会将过滤条件的迭代器一直遍历到末尾并根据匹配的文档数量填充一个大小为 segment 的maxDoc的FixedBitSet或者填充一个稀疏 bitset。IVF 会执行等价的操作在扫描第一个倒排列表之前通过 Elasticsearch 自己的ESAcceptDocs完成这一过程。无论哪种方式其成本都取决于 segment 的大小以及计算过滤条件的开销而不是取决于搜索随后会访问 segment 的多少内容。步骤 2跳过未通过过滤条件的文档未通过过滤条件的文档不会计入结果。搜索必须访问 segment 中更多的内容以收集足够多的通过过滤条件的文档HNSW 会进一步遍历图而 IVF 会额外扫描几个倒排列表。两者都会对这一过程进行限制。例如HNSW 会在访问的向量数量达到过滤条件匹配的文档数量后停止遍历图并直接对匹配的文档进行评分。对于匹配数据集大部分内容的过滤条件而言额外工作量很小下一节中的 profile 就展示了这一点。结论是过滤条件导致的额外搜索工作是有界的而且很少是过滤查询耗时的主要来源。步骤 1 中的物化过程则没有这样的界限。这就是为什么真正值得关注的情况不是限制性很强的过滤条件而是宽泛的过滤条件例如匹配数据集 90% 的内容。它几乎不会剪枝也不会增加多少搜索工作但仍然需要在每个 segment 中完整地执行物化付出全部成本。为什么经过过滤的 kNN 搜索可能比未经过滤的搜索更慢搜索 profile 会直接展示这一成本不过它可能并不在你第一时间想到的位置。Lucene 的 kNN 查询几乎所有工作都在rewrite中完成。对于 HNSWAbstractKnnVectorQuery#rewrite会物化过滤条件、搜索每个 segment、合并各个 segment 的结果并返回一个包含最终文档 ID 和分数的DocAndScoreQuery。IVF 执行相同的操作并返回 Elasticsearch 的KnnScoreDocQuery。等到查询以通常意义上的方式执行时搜索已经结束剩下的只是返回一个预先计算好的命中列表。顶层knn子句会在 DFS 阶段运行因此它的 profile 会出现在profile.shards[].dfs.knn[]下。下面是一个未经过滤的搜索使用k: 10和num_candidates: 100针对包含 100 万个向量的单个 HNSW segment 执行其中每项明细都经过精简只保留非零项{ dfs: { knn: [ { vector_operations_count: 2378, query: [ { type: DocAndScoreQuery, description: DocAndScoreQuery[177025,...][0.7580181,...],0.7580181, time_in_nanos: 5708, breakdown: { create_weight: 1250, build_scorer: 2583, next_doc: 1041, score: 834, ... } } ], rewrite_time: 5158917, collector: [...] } ] } }rewrite_time为 5.2 毫秒这就是 kNN 搜索的耗时。DocAndScoreQuery项耗时不到 6 微秒它只负责返回这 10 个命中结果。现在添加一个匹配 90% 文档的match_phrase过滤条件。在实际应用中一个几乎匹配整个数据集的短语并不是常见的过滤条件但它可以清晰地隔离出其中的影响它几乎不会缩小搜索范围却需要较高的计算成本。大多数实际中匹配范围如此广泛的过滤条件其成本都介于这个过滤条件和我们下面进行比较的term过滤条件之间。{ dfs: { knn: [ { vector_operations_count: 2682, query: [ { type: CachingEnableFilterQuery, description: (ConstantScore(body:\red fox\))^0.0, time_in_nanos: 33595666, breakdown: { create_weight: 9125, build_scorer: 174083, next_doc: 15708, into_bit_set: 33396750, into_bit_set_count: 1, ... }, children: [ { type: PhraseQuery, description: body:\red fox\, time_in_nanos: 33589916, breakdown: {...} } ] }, { type: DocAndScoreQuery, description: DocAndScoreQuery[163399,...][0.7200494,...],0.7580181, time_in_nanos: 4092, breakdown: {...} } ], rewrite_time: 40076834, collector: [...] } ] } }发生了三件事过滤条件有了自己的条目与DocAndScoreQuery并列而不是位于其中因为它会在 kNN 查询的 rewrite 阶段运行。CachingEnableFilterQuery是 Elasticsearch 放在 kNN 过滤条件外面的包装器用于确保查询缓存始终认为这些过滤条件值得缓存你编写的查询就是它的子查询。在bbq_disk字段上条目名称有所不同但过滤条件的显示方式相同。into_bit_set就是步骤 1 中的物化过程通过一次调用在整个 segment 上运行短语查询并将每个匹配项记录到 bitset 中。这耗时 33.4 毫秒。这段时间包含在rewrite_time中而不是在其基础上额外增加rewrite_time从 5.2 毫秒增加到 40.1 毫秒其中过滤条件占据了差值中的 33.6 毫秒。匹配少于约 1/128 文档的过滤条件会改为逐个文档收集到稀疏 bitset 中因此其成本会显示在next_doc下。vector_operations_count几乎没有变化。它增加了 13%这大致符合预期因为每 10 个被访问的文档中有 1 个未通过过滤条件。这个查询超过 80% 的耗时都花在了计算过滤条件上。阅读这类 profile 时需要注意一点profile 会绕过查询缓存因此即使未进行 profile 的请求可以从缓存中找到某个过滤条件profile 也始终显示该过滤条件未缓存时的成本。kNN 过滤成本物化与额外搜索工作这两个 profile 之间的差异由两项成本构成值得将它们分开因为它们的增长方式不同。过滤条件物化是每个 segment 都必须付出的成本与 segment 大小成正比并且发生在任何向量处理之前。它的成本完全取决于查询类型过滤条件物化成本termon a keyword低 —— 读取一个倒排列表以批量方式执行intoBitSetrangeon a numeric or date field通常较低 —— 遍历 pointsBKD索引只有单独使用 doc values 的字段index: false才需要检查每个文档match_phrase对每个包含这些词项的文档进行位置解码和交集运算成本最高boolof several clauses每个子句的成本加上合取/析取操作的额外处理Cached filter命中缓存时几乎没有成本缓存未命中时则需要付出完整成本在上面这个包含 100 万个文档的 segment 中一个匹配相同 90% 文档的term过滤条件在into_bit_set中的耗时约为 0.3 毫秒大约比短语过滤条件低 100 倍。而且成本会随着 segment 增大而增长在下面的基准测试中一个匹配 1000 万个文档中 90% 的match_phrase过滤条件会使 HNSW 查询耗时从 2.3 毫秒增加到 395 毫秒。额外搜索工作会在此基础上增加一些成本但正如我们看到的它是有界的而且对于宽泛的过滤条件来说很小上面的 13%。物化成本占据主导地位因此一个使用宽泛且计算成本高的过滤条件的 kNN 搜索大部分时间可能都花在与向量比较无关的工作上。它最终得到的答案也与未经过滤的结果高度重叠如果一个过滤条件匹配整个数据集的 90%并且与查询无关那么整体上距离最近的 10 个邻居中大约已经有 9 个通过了过滤条件而未通过的那些会被排名仅稍微靠后的文档替代。这就是本文其余部分所要讨论的不对称性。过滤条件的成本取决于需要对多少个文档进行评估而将过滤条件从向量搜索之前移到之后会让这个数量发生数量级的变化前置过滤会在向量搜索之前对 segment 中的每个文档执行过滤条件评估后置过滤则只对向量搜索返回的候选文档执行过滤条件评估。kNN 搜索中的前置过滤与后置过滤如果我们直接使用后置过滤呢这个观察并不新鲜而且 Elasticsearch 一直都允许你利用这一点。将过滤条件移到knn子句外部它就会变成后置过滤kNN搜索不受限制地运行然后将过滤条件应用于它返回的k个结果。POST my-index/_search { query: { bool: { filter: { term: { language: en } }, must: { knn: { field: embedding, query_vector: [0.12, -0.03, ...], k: 10, num_candidates: 100 } } } } }我们在如何选择 Elasticsearch 中的精确 kNN 搜索与近似 kNN 搜索中详细讨论过这种权衡其中关键问题可以简单概括为在 kNN 中使用后置过滤的问题在于过滤条件是在我们获取 top k 结果之后才应用的。这意味着最终返回的结果可能少于 k 个因为我们需要从已经从 HNSW 图中检索到的 top k 结果中移除不符合过滤条件的元素。请求 10 个返回 6 个。或者 2 个。或者 0 个。向量搜索不知道过滤条件的存在因此无法保证它返回的结果中有 10 个能够通过过滤条件。唯一可用的补救方法是手动进行过量收集请求k: 50然后希望其中有 10 个能够通过过滤条件。这样你就会陷入一个尴尬的境地你必须猜测这个倍数而正确的倍数取决于过滤条件对于当前这个查询的选择性而通常情况下你并不知道这一点。猜得太低你就会在没有任何提示的情况下返回较短的结果集。猜得太高你就需要为不必要的搜索付出代价而这恰恰是你原本想避免的成本。无论哪种情况k都不再代表 API 所声明的含义因此分页、size以及任何下游处理都必须单独进行推理。因此这两种方案都不太令人满意。前置过滤是正确的但可能会出现异常缓慢的情况。后置过滤速度快但却将统计问题转嫁给了用户而且仍然无法提供任何保证。下表比较了这两种方案以及下一节将介绍的自动后置过滤。前置过滤手动后置过滤自动后置过滤过滤条件放在哪里knn子句内部knn子句外部在bool查询中knn子句内部不变过滤条件在哪些对象上进行评估每个 segment 中的每个文档向量搜索返回的k个结果向量搜索返回的候选项返回 k 个结果是不保证是如果需要则回退到前置过滤谁负责确定候选池大小不需要你通过猜测k的倍数Elasticsearch根据过滤条件的估计选择性最适合高选择性的过滤条件可以接受较短结果集的情况宽泛的过滤条件默认选择性为 0.7 或更高但我们可以做得更好关键在于在这两种方案之间进行选择不一定非得由用户决定而且也不必针对整个索引只做一次决定。Elasticsearch 在 rewrite 阶段会保留过滤条件的Weight。它可以估算过滤条件的选择性判断对于当前查询在当前 shard 上后置过滤是否值得采用根据这个估算值而不是猜测来确定过量收集的规模并在底层保留一个正确性保障机制这样即使估算不准确付出的代价也是延迟而不是结果缺失。这就是自动后置过滤为 HNSW 和 IVFbbq_disk带来的能力。重要的是这一切都不会改变你编写的查询你仍然以表达前置过滤的方式编写查询仍然获得前置过滤的语义而具体如何满足这一要求则交由搜索引擎决定。依次包含四个步骤估算过滤条件的选择性。使用这个估算值确定过量收集的规模。如果结果数量不足则重试一次。如果仍然不足则回退到原始查询。估算 kNN 过滤条件的选择性首先我们需要得到一个数字用来回答 “这个过滤条件允许数据集中的多少内容通过” 一个成本低廉且效果出乎意料地好的方法是询问过滤条件自身的 scorer了解它预计会匹配多少文档然后除以该字段实际建立索引的向量数量public static float computeSelectivity(Weight filterWeight, ListLeafReaderContext leaves, int totalVectors) throws IOException { long filterCost 0; for (LeafReaderContext leafCtx : leaves) { ScorerSupplier ss filterWeight.scorerSupplier(leafCtx); if (ss ! null) { filterCost ss.cost(); } } return totalVectors 0 ? Math.min(1f, (float) filterCost / totalVectors) : 0f; }有两点使这一过程成本很低。ScorerSupplier#cost()是一个估算值。对于 term 查询来说它就是倒排列表的长度这个值可以直接从元数据中读取因此无需物化任何内容。分母则是来自 codec 的向量数量而不是maxDoc因此对于只有部分文档包含该字段的情况这个比例不会受到影响。有两点使这个估算并不完美而这两点都会在后续处理中得到解决而不是假装它们不存在。对于合取查询cost()是一个上界因此选择性可能会被高估。更根本的问题是选择性是 shard 的一个全局属性而真正重要的是过滤条件在查询向量邻域内的通过率。对于一个与向量内容无关的过滤条件两者是一致的。对于一个与向量内容存在相关性的过滤条件两者则可能向任意一个方向产生偏差。假设language: en匹配某个 shard 中 90% 的文档。对于一个英文查询几乎所有最近邻都是英文文档。因此本地通过率接近 100%而全局估算值只是比较保守。对于一个用西班牙语编写的查询最近邻可能主要来自那 10% 的非英文文档因此本地通过率可能远低于 90%即使全局估算值并没有发生变化。下面的重试和回退过程就是为了处理第二种情况。使用二项式模型确定候选池大小给定选择性p未过滤搜索应该收集多少个原始候选项m才能获得至少k个通过过滤条件的结果最简单的答案是。这样可以让你平均获得个通过过滤条件的结果这意味着大约有一半的情况下结果数量仍然不足。平均值在这里并不是正确的工具我们需要的是一个高概率保证。因此可以将每个候选项建模为以概率p独立通过过滤条件。这样个候选项中通过过滤条件的结果数量就是一个二项式随机变量现在我们不再要求均值等于k而是要求k位于均值的下方距离均值为Z个标准差精确地对m求解会得到一个二次方程。将m≈k/p代入方差项则可以得到一个封闭形式其结果略微偏保守而这正是我们希望出现的误差方向Z是一个置信度调节参数第一轮成功的概率约为Φ(Z)。实现中使用Z2.5也就是约 99.4%。这里有一个值得明确说明的假设那就是独立性。我们之所以采用这一假设是因为在没有任何信号表明过滤条件与向量内容之间存在怎样的相关性的情况下这是我们唯一能够做出的假设。下面的重试和回退过程正是为了覆盖这一假设不成立的情况。后置过滤会收集多少额外候选项在代码中这个公式再加上一些保护措施就是/** * Minimum round-1 oversample factor. Round 1 always asks for at least this many × * the target count, regardless of what the binomial variance formula computes. Active * when selectivity is near 1, where the variance term collapses to ≈ 0. */ float POST_FILTER_OVERSAMPLE_FLOOR 1.2f; float POST_FILTER_OVERSAMPLE_Z_SCORE 2.5f; static double zMargin(int k, float selectivity) { return POST_FILTER_OVERSAMPLE_Z_SCORE * Math.sqrt(k * (1.0f - selectivity) / selectivity); } static int computeScaledK(int k, float selectivity) { double zMargin zMargin(k, selectivity); double floor Math.min(Math.ceil(k * POST_FILTER_OVERSAMPLE_FLOOR), NUM_CANDS_LIMIT); return (int) Math.clamp(Math.ceil((k zMargin) / selectivity), floor, NUM_CANDS_LIMIT); }1.2 倍的下限很重要因为当p→1时方差项会趋近于 0而公式会恰好返回k从而没有为少量确实会被过滤掉的文档留下任何余量。NUM_CANDS_LIMIT上限10,000则可以防止过滤条件过于严格时请求一个无限增长的候选池。对于k10和Z2.5得到的过量收集比例为选择性pZσ裕量候选项m过量收集0.990.7912下限1.2x0.951.81131.3x0.902.64151.5x0.803.95181.8x0.705.18222.2x0.557.15323.2x注意这些数值都相当适中而且随着k增大相对于k的比例会缩小因为标准差随着k增长而均值也随着k增长。在k100、p0.55时过量收集比例只有 2.2 倍而k10时则为 3.2 倍。请求 15 个结果而不是 10 个与在一个包含 1000 万个文档的 segment 上物化一个昂贵的过滤条件相比几乎不值一提。还有一个预算不能与k混为一谈弄错这一点很容易导致搜索参数被意外重新调节。对于 HNSWnum_candidates是 beam 宽度是一个独立的调节参数。delegate 会保留用户设置的值但将其下限设为扩大的k如果 beam 比请求的结果数量还窄就无法返回这些结果static int cappedNumCands(int numCands, int scaledK) { return Math.clamp(numCands, scaledK, NUM_CANDS_LIMIT); }这里有一个值得特别说明的结果HNSW delegate 返回的候选项数量会多于扩大的k。每个 segment 的图遍历都会保留完整的 beam最多num_candidates个候选项并对其中每一个候选项检查过滤条件。在 HNSW 中扩大的k主要在num_candidates接近k时才真正重要在通常使用更宽 beam 的情况下第一轮有足够多的候选项可供选择。对于 IVFnum_candidates只有相对于k才有意义codec 根据两者的比例计算访问比例。如果在k增大时保持num_candidates不变就会在不知不觉中减少搜索范围而 IVF 会对其进行缩放以保持这个比例static int numCandsPreservingRatio(int numCands, int k, int newK) { if (k 0) { return Math.clamp(numCands, newK, NUM_CANDS_LIMIT); } long scaled (long) Math.ceil((double) numCands * newK / k); return Math.clamp(scaled, newK, NUM_CANDS_LIMIT); }后置过滤结果不足时进行重试二项式模型的校准目标是约 99.4% 的成功率而它所依赖的独立性假设可能并不成立。因此第一轮有时会出现结果不足。重试轮次会将“通常足够”变成“足够”。只有当结果不足看起来更像是运气不好而不是模型错误时才会执行重试。如果第一轮返回的通过过滤条件的结果远少于全局选择性所预测的数量这就表明过滤条件与查询邻域存在相关性而这正是二项式模型明确无法处理的情况。更多轮次无法修复一个错误的模型因此我们会提前退出double expectedHits k * (double) selectivity; double threshold expectedHits * 0.5; boolean shouldExit scoreDocsCount threshold;;如果实际通过过滤条件的结果少于预测数量的一半就意味着过滤条件对这个查询的向量邻域并不友好此时前置过滤才是正确的工具。对于k 5会跳过这项检查因为预期结果数量太小这个比例没有实际意义。重试并不只是用更大的k再运行一次这样会再次找到相同的候选项。它必须搜索一些新的区域因此需要传递三部分状态int remaining expectedBaseQueryDocMatches - scoreDocs.length; int retryK PostFilterableKnnQuery.computeScaledK(remaining, selectivity); Query retry postFilterQuery.createRetryQuery(searcher.getIndexReader(), excluded, seedDocsPerLeaf, retryK); TopDocs retryDocs searcher.search(retry, retryK);排除集合。第一轮中看到的每个文档——无论通过还是未通过过滤条件——都会通过ExcludeDocsQuery排除。HNSW 会将它组合到 accept-docs 中IVF 则将其传递给倒排列表遍历使 codec 直接跳过这些文档。种子入口点。对于 HNSW如果从顶层重新开始图遍历就会再次沿着相同的路径向下搜索。因此重试会从第一轮中距离最近的匹配项开始播种每个 segment 最多四个这样它一开始就处于正确的邻域中然后向外扩展int[][] seedDocsPerLeaf nearestSeedsPerLeaf(matching, MAX_SEEDS_PER_LEAF);IVF 暂时忽略种子它已经知道哪些质心距离最近只需重新扫描这些质心同时跳过已排除的文档。重新调整目标数量。remaining是通过过滤条件的结果中的不足数量。它会再次使用相同的选择性传入computeScaledK以针对重试过程中同样会发生的结果损耗进行扩充。恰好只重试一次。第二次重试就等于追逐一个模型已经证明错误的分布而下面的回退机制成本更低并且能够严格保证正确性。回退到前置过滤回退轮次使自动后置过滤可以安全地默认启用。如果后置过滤没有产生完整的候选池就丢弃它的结果然后改为运行原始的前置过滤查询。if (scoreDocs.length expectedBaseQueryDocMatches) { logger.debug( post filtering retrieved only [{}] results, less than the desired [{}] results. Falling back to original query, scoreDocs.length, expectedBaseQueryDocMatches ); return null; }从postFilterRewrite返回null会让rewrite进入常规路径Query rewritten ((Query) innerQuery).rewrite(searcher); this.totalVectorOps innerQuery.totalVectorOps(); return rewritten;用户的查询就是回退方案。这意味着错误的选择性估算所带来的最坏情况是延迟浪费了一次候选项收集然后再执行原本就会执行的前置过滤搜索而绝不会导致结果集过短或结果错误。正是这一特性使得像ScorerSupplier#cost()这样粗略的估算也足够好它只需要在足够多的情况下估算正确从而弥补估算错误时所付出的成本。简而言之第一轮之后如果至少有k个候选项通过过滤条件则返回距离最近的k个。如果通过过滤条件的候选项少于预期数量的一半0.5⋅p⋅k则提前退出执行前置过滤查询。否则重试一次。如果此时至少有k个候选项通过过滤条件则返回距离最近的k个如果仍然不足则回退到前置过滤查询。相同的两项检查每轮一行。所有前置过滤结果都与单独执行前置过滤时完全一致。还有一个与分数正确性有关的细节值得注意。对于量化字段近似分数会通过一次精确的重新评分过程进行校正。通常情况下IVF 会在自己的rewrite中完成这一过程但对于后置过滤 delegate必须在过滤之后进行否则我们就会对那些即将被丢弃的文档进行重新评分。delegate 会跳过这一步而 orchestrator 会在候选池最终确定后通过finalizeTopK回调执行这一过程。如果没有这个钩子后置过滤的结果会携带原始的量化分数而回退结果则会携带精确分数从而在同一次搜索中混用两个不同的分数域。一个经过过滤的 kNN 查询从头到尾假设你在一个包含 1000 万个文档的 shard 上运行以下查询其中language: en能匹配其中 900 万个文档{ knn: { field: embedding, query_vector: [...], k: 10, num_candidates: 100, filter: { term: { language: en } } } }1. Rewrite。PostFilterKnnQuery#rewrite构建过滤条件的Weight并将其与embedding上的FieldExistsQuery合取这样没有向量的文档就不会被计入但不会执行这个过滤条件。2. 估算。在各个 segment 上通过ScorerSupplier#cost()得到约 900 万而实际建立索引的向量数量为 1000 万p0.9。这高于默认的 0.7 阈值因此启用后置过滤。如果结果只有 0.4我们就会在这里停止并运行普通的前置过滤查询。3. 确定第一轮的规模。m⌈(102.510⋅0.1/0.9)/0.9⌉15因此会构建一个不带过滤条件的 delegate请求 15 个结果而不是 10 个。它的搜索预算遵循前面的规则对于 HNSWnum_candidates保持为 100即 beam 宽度对于 IVF则将其缩放到 150这样访问比例就不会发生变化。4. 执行无过滤搜索。delegate 在所有 segment 上运行不使用 accept-docs bitset不会进行过滤条件物化也不会进行额外搜索。每个 segment 都会保留自身搜索收集到的所有候选项因此 orchestrator 无需重新推导这些候选项。对于 HNSW这是该 segment 的整个 beam最多 100 个候选项对于 IVF则是所请求 15 个结果的一个小倍数因为 IVF 会进行过量收集以吸收出现在多个倒排列表中的文档。5. 将过滤条件应用于候选项而不是 1000 万个文档。applyFilter按 doc-ID 顺序遍历每个 segment 的候选项并通过Lucene#asSequentialAccessBits对它们进行测试。对于暴露TwoPhaseIterator的过滤条件每个候选项只需要执行一次 approximation advance并且只有当 approximation 命中该候选项时才调用matches()。这正是整个方案的核心过滤条件只针对每个候选项进行一次评估而不是针对 segment 中的每个文档进行评估。这也意味着过滤条件不再需要通过缓存来实现快速执行。在前置过滤中避免每次查询都为物化付出成本的常用方法是使用过滤条件缓存该缓存会存储过滤条件针对每个 segment 的 bitset以便重复使用。只有当某个过滤条件被使用足够多次并进入缓存后这种方式才会有所帮助而且每个新 segment 都需要从冷缓存开始。后置过滤没有值得缓存的内容applyFilter会告诉过滤条件它只需要面对少量候选项而 Lucene 的查询缓存也不会为一个匹配数百万个文档、但实际上只会检查其中极少一部分的过滤条件创建 bitset。这个过滤条件第一次使用时的速度与第一百次使用时一样快。6. 检查是否达到目标。目标是用户请求的 10 个结果。对于一个能够通过 90% 文档的过滤条件大约每 10 个候选项中有 9 个能够通过过滤条件因此跨各个 segment 后通过的数量远超过 10 个。我们进行去重并保留距离最近的 10 个。假设只有 7 个不同的候选项通过了过滤条件就像之前提到的西班牙语查询那样当过滤条件与查询存在相关性时就可能发生这种情况。7 高于针对不友好过滤条件的阈值10×0.9×0.54.5因此会触发重试排除之前已经看到的每个候选项无论它是否通过过滤条件从每个 segment 中距离最近的、最多 4 个通过过滤条件的候选项开始播种然后请求computeScaledK(3, 0.9) 5个额外结果以弥补 3 个结果的不足。如果这样仍然无法达到 10 个结果就运行前置过滤查询此时后置过滤除了候选项收集之外没有产生任何额外成本。7. Finalize。通过 introselect 按分数选择 topk并将结果包装在KnnScoreDocQuery中。过滤条件只在向量搜索返回的候选项上进行评估而不是在 1000 万个文档上进行评估。向量搜索不受过滤条件限制并且返回的文档与前置过滤原本会找到的 10 个文档相同同时还能保证如果结果不一致你最终会得到前置过滤查询的结果。最多 1000 万个向量上的后置过滤与前置过滤基准测试基准测试设置为了测量这里的性能上限我们进行了强制对比每种配置都运行两次一次使用前置过滤一次使用后置过滤并绕过自适应逻辑使两种策略都无法回退到另一种策略。这比生产环境中的实际行为更加严苛真实实现会针对每个查询进行选择并在必要时回退但这种测试能够清晰展示每种策略在哪些情况下更有优势。测试网格5 个数据集从 523K 到 1000 万个向量不等每个数据集都分别使用 IVF 和 HNSW 建立索引同时采用单 segment 和多 segment 布局针对 5 种过滤条件和 7 种选择性分别运行前置过滤和后置过滤5 × 2 × 2 × 5 × 7 × 2 1400 次测量也就是 700 组匹配的前置/后置过滤对比。7 种选择性分别为 0.55、0.7、0.8、0.9、0.95、0.99 和 1.0其中 1.0 表示没有过滤条件。固定使用num_candidates1000、k10、1% 的访问比例、未缓存的过滤条件以及每个测试点 300 个查询。IVF 使用clusterSize384HNSW 使用m16、efConstruction200全程使用 1-bit 量化。过滤条件均未进行缓存。这是前置过滤的冷启动情况如果过滤条件在多个查询之间重复使用温热的过滤条件缓存会缩小两者之间的差距。这也是后置过滤唯一会遇到的情况因为后置过滤从一开始就不会依赖缓存。并非每个数据集都具有可供range、term和phrase过滤条件使用的 numeric、keyword 或 text 字段。如果缺少某个字段我们就添加该字段并使用随机内容填充。然后对数据集进行采样选择与目标 D% 文档匹配的过滤值range是针对 numeric 字段的范围查询其边界经过选择使 D% 的文档落在该范围内。term匹配一个 keyword 值该值存在于 D% 的文档中。phrase是针对 text 字段的短语查询查询的短语出现在 D% 的文档中。对它进行评估意味着需要检查词项位置而不仅仅是检查词项是否存在因此它是这里物化成本最高的过滤条件。range_term在bool查询中组合range和term两个过滤条件。random匹配随机选择的 D% 文档。不同数据集规模和过滤条件类型下的结果对于过滤而言数据集最重要的属性是其大小因为物化过滤条件所需的时间与每个 segment 中的文档数量成正比。我们使用这 5 个数据集来展示随着数据集规模增长两种策略之间的差异并在下面使用最大的cohere-msmarco-10M数据集1000 万个向量、1024 个维度、float32给出详细数据。在选择性低于 1.0 的情况下按数据集规模统计的后置过滤相对于前置过滤的中位速度提升。蓝色表示后置过滤更快红色表示前置过滤更快。后置过滤几乎在所有情况下都占据优势在每一种数据集规模、两种索引类型以及两种布局中都是如此。具体领先多少取决于物化过滤条件的成本而在大多数布局中随着数据集规模增长这一差距也会扩大。在低于 1.0x 的 100 个测试单元中有 16 个属于多 segment 布局下成本较低的term或range过滤条件最低为 0.68x。在cohere-msmarco-10M数据集上120 组过滤条件对比中有 104 组采用后置过滤时速度更快其中单 segment 上的全部 60 组都是如此另外还有 2 组基本持平差异在 2% 以内。剩余的 14 组是多 segment 布局下成本较低的range和term过滤条件其中前置过滤最多只领先 1.33x1.76 ms 对 2.34 ms。延迟与选择性之间的曲线直接展示了其中的机制cohere-msmarco-10M 单 segment 上延迟与过滤条件选择性的关系。红色表示前置过滤蓝色表示后置过滤实线表示 IVF虚线表示 HNSW。蓝色的后置过滤曲线几乎是平的。对于后置过滤而言延迟主要由 kNN 搜索本身决定而 kNN 搜索不受过滤条件限制因此无论过滤条件匹配多少文档其成本都基本相同。在此基础上将过滤条件应用于候选项所增加的成本很小而且即使过滤条件的范围不断缩小过量收集的规模也仍然很小。对于给定的过滤条件类型而言延迟几乎不受选择性影响在中位配置下从整个 0.55–0.99 范围来看延迟变化约为 10%而前置过滤约为 50%。红色的前置过滤曲线位于其上方差距大致相当于物化过滤条件的成本也就是说过滤条件越昂贵两者之间的差距就越大当选择性达到 1.0 时两条曲线最终汇合因为此时没有需要评估的过滤条件。召回率基本与策略无关140 组对比中的每一组召回率差异都在 0.01 以内因此这里的权衡实际上纯粹是延迟上的权衡。每个点代表 cohere-msmarco-10M 上 140 组前置/后置过滤对比中的一组。左图召回率。右图对数尺度下的延迟位于对角线下方的点表示后置过滤速度更快。局限性相关过滤条件与多 segment 布局有两个注意事项值得明确说明。这些过滤条件与向量基本不相关。基于随机内容构建的过滤条件会独立地通过文档而不受文档在向量空间中所处位置的影响这正是二项分布模型所采用的假设。结果也体现了这一点在任何单一配置中5 种过滤条件之间的召回率差异最多为 0.04并且在每种选择性下中位召回率都在 0.74–0.75 之间。对于相关过滤条件例如前面提到的language示例重试、提前退出和回退机制会发挥作用即使选择性估算不准确也能确保结果正确。衡量这种加速效果有多少能够延伸到高度相关的过滤条件是下一步很自然的基准测试方向。多 segment 布局会缩小后置过滤的优势。比较热力图中的单 segment 和多 segment 面板。固定的每个 segment 成本需要支付更多次而前置过滤则可以在每个 segment 较小的maxDoc上摊销其 bitset 成本。后置过滤在成本较高的过滤条件上仍然更快只是领先幅度较小。如何启用和调整自动后置过滤自动后置过滤计划在 Elasticsearch 9.6 以及即将发布的 Elastic Cloud Serverless 版本中默认启用。启用后你无需修改查询继续将过滤条件写在knn子句内部每个 shard 都会针对每个查询自行决定是否值得尝试后置过滤。调整后置过滤选择性阈值这一决策由一个索引设置index.dense_vector.post_filter_selectivity_threshold控制其默认值为 0.7。当查询的估计选择性大于或等于该阈值时查询会进入后置过滤流程。因此该阈值实际上规定了过滤条件必须有多宽泛才会尝试使用后置过滤阈值行为1.0关闭。没有任何过滤条件能够满足要求。0.9只有非常宽泛的过滤条件 —— 匹配 90% 以上数据集的过滤条件 —— 才会使用后置过滤。0.7(默认值)匹配 70% 以上文档的过滤条件使用后置过滤。0.0每个带过滤条件的 kNN 查询都会尝试使用后置过滤。如果你的过滤条件通常需要较高的评估成本可以降低该值来针对索引进行调整也可以将其设置为1.0从而完全选择退出。你可以在索引设置中进行配置PUT my-index { settings: { index.dense_vector.post_filter_selectivity_threshold: 0.5 }, mappings: { properties: { embedding: { type: dense_vector, dims: 1024, index_options: { type: bbq_hnsw } } } } }范围与局限性值得了解一下适用范围同时适用于HNSW和bbq_disk**IVF**字段支持float、bfloat16和byte元素类型以及 HNSW 上的bit向量。嵌套向量字段也受到支持但有一个需要注意的地方由于嵌套 kNN 搜索每个 parent 只保留一个命中结果因此一个已经产生匹配结果的 parent 会在重试时作为一个完整块被排除而一个 child 只是被过滤掉的 parent 仍然有资格参与重试 —— 它下面更深层的 child 仍然可能通过过滤条件。查询语义保持不变。你仍然编写前置过滤并获得前置过滤语义。请求体没有任何变化这纯粹是一个执行策略决策。profile 会显示实际运行的是哪种策略。当查询使用后置过滤时过滤条件对应的条目中没有into_bit_set过滤条件会逐个候选项进行检查这意味着它会针对向量搜索返回的每个候选项报告一次advance。在前面的短语过滤示例中这意味着有 100 次advance调用beam 中的每个候选项一次总耗时远低于 1 毫秒而不是 33.4 ms 的into_bit_set。在向量搜索自身的命中列表旁边还会出现第二个命中列表条目其中包含保存最终 topk的KnnScoreDocQuery。如果想查看单次决策重试、提前退出、回退以及这些决策背后的选择性估算请将logger.org.elasticsearch.search.vectors.PostFilterKnnQuery: DEBUG设置为DEBUG。Elasticsearch 中过滤 kNN 搜索的下一步我们最感兴趣的改进方向包括更好的选择性估算。ScorerSupplier#cost()不需要额外成本但比较粗略而且会高估 conjunction。Elasticsearch 已经在跟踪更丰富的字段统计信息如果将这些统计信息接入或者在 segment 的有限范围内对过滤条件进行采样就可以让阈值不必设置得如此保守。提前检测相关性。针对 hostile filter 的提前退出属于响应式机制只有在花费一轮搜索发现过滤条件与查询邻域存在相关性之后我们才知道这一点。如果在做出决策之前就能估算过滤条件的局部通过率例如根据图遍历的 seed 文档或者使用缓存的每查询统计信息就可以将其转变为低成本的前置路由决策并安全地降低阈值。基于成本的路由。基准测试表明合适的阈值不仅取决于选择性也同样取决于过滤条件类型与term过滤条件相比match_phrase过滤条件的物化成本高出几个数量级因此即使在低得多的选择性下也值得使用后置过滤。基于过滤条件查询结构而不仅仅是选择性建立成本模型可以让引擎针对每个查询做出这一决策而不是依赖单个每索引阈值。按 segment 做出决策。目前的路由是在 shard 级别进行的但不同 segment 之间的选择性和 segment 大小可能有所不同。按 segment 做出决策后同一个查询中就可以让较小的 segment 使用前置过滤而较大的 segment 使用后置过滤。更广泛来说这一观点并不局限于 kNN。Elasticsearch 已经投入大量工作来提升向量比较的速度量化、SIMD、更好的 HNSW 图以及更适合磁盘的 IVF 索引并因此实现了向量比较不再是瓶颈的查询。当一次过滤后的 kNN 搜索大部分时间都花在物化昂贵的过滤条件上时真正值得进行的优化并不是让距离函数更快而是意识到要回答一个关于十个文档的问题并不需要在 1000 万个文档上运行过滤条件。常见问题kNN 搜索中的前置过滤和后置过滤有什么区别前置过滤会在向量搜索运行期间应用过滤条件因此 top k 结果是匹配过滤条件的文档中距离最近的 k 个文档。后置过滤则不受限制地运行向量搜索然后再对结果应用过滤条件这样速度更快但可能返回少于 k 个结果除非搜索首先过量收集候选项。为什么过滤后的 kNN 查询有时会比未过滤查询更慢前置过滤会在进行任何向量比较之前为每个 segment 将过滤条件物化为 bitset而其成本与 segment 大小成正比而不是与搜索实际访问的文档数量成正比。对于match_phrase这样的高成本过滤条件这项工作可能成为查询的主要成本即使过滤条件匹配几乎所有文档、因此实际上排除了很少的文档也必须完整承担这项成本。原文Elasticsearch kNN filter: Pre-filtering vs. post-filtering | Elasticsearch Labs 检查 100 个候选项，而不是 1000 万个文档：更快速的 Elasticsearch kNN 过滤
作者来自 Elastic Panagiotis BailisElasticsearch 现在会针对每个查询决定是在向量搜索之前还是之后执行 kNN 过滤。在一个包含 1000 万个向量的数据集上在 120 组基准测试中有 104 组采用后置过滤的速度更快同时仍能返回 k 个结果。现在Elasticsearch 会针对每个查询决定是在向量搜索之前还是之后应用 kNN 过滤。在包含 100 万个向量的 segment 上在搜索之后检查一个宽泛的match_phrase过滤条件耗时不到 1 毫秒而在搜索之前检查则需要 33.4 毫秒。在包含 1000 万个向量的数据集上在 120 组基准测试中后置过滤有 104 组速度更快同时 recall 与前置过滤相差不超过 0.01。你可以通过这个面向 Search AI 的自主学习实践课程亲自体验向量搜索。你现在可以开始免费云试用也可以在你的本地机器上试用 Elastic。Elasticsearch 现在会针对每个查询决定是在向量搜索之前还是之后应用 kNN 过滤。knn子句中的过滤条件例如租户 ID 或语言会作为前置过滤运行因此会在搜索开始之前对每个 segment 中的每个文档进行评估。当过滤条件匹配数据集中的足够多文档时Elasticsearch 会先执行向量搜索然后只针对返回的候选项检查过滤条件。候选池的大小会通过统计方式确定以确保至少有k个结果通过过滤。如果结果数量不足Elasticsearch 会重试一次然后回退到前置过滤搜索。你的查询保持不变并且仍然可以获得 k 个结果。预计这项功能将在 Elasticsearch 9.6 中默认启用。kNN 过滤在 Elasticsearch 中如何工作简单回顾一下Elasticsearch 针对dense_vector字段提供了两种近似最近邻结构。HNSW是一种邻近图搜索会从一个邻居移动到另一个邻居同时将目前找到的距离最近的num_candidates个向量保留为搜索波束。IVF即bbq_disk索引类型会围绕质心对向量进行聚类每个质心都有一个包含其向量的倒排列表并扫描距离查询最近的倒排列表它扫描的 segment 比例即访问比例由num_candidates和k推导得出。HNSW 图和 DiskBBQ 这两篇文章对二者都有深入介绍。接下来所有内容的关键在于这两种结构都不是一个覆盖整个索引的单一结构。每个 Lucene segment 都拥有自己的 HNSW 图或自己的一组 IVF 倒排列表因此 kNN 查询会分别搜索每个 segment 并合并结果首先在每个 shard 内合并然后再由协调节点进行合并。因此搜索在开始探索之前需要准备的任何内容都需要针对每个 segment 分别准备一次。现在让我们在 kNN 查询中添加一个filterPOST my-index/_search { knn: { field: embedding, query_vector: [0.12, -0.03, ...], k: 10, num_candidates: 100, filter: { term: { language: en } } } }因为过滤条件位于knn子句内部所以它属于前置过滤这 10 个结果是在所有匹配language: en的文档中距离最近的 10 个文档。为了实现这一点搜索必须知道它遇到的每个文档是否通过过滤条件。在每个 segment 中这一过程分为两个步骤。步骤 1将过滤条件物化为 bitset这两种结构都不会按照 doc ID 顺序访问文档。HNSW 遍历会跳转到图中的邻居而 IVF 会一次扫描一个质心对应的倒排列表这意味着文档 ID 会按照向量邻近关系所决定的任意顺序到达。搜索需要随时回答 “doc 84,219 是否匹配” 这样的问题而过滤条件的常规DocIdSetIterator只能向前移动无法做到这一点。在搜索开始之前会在整个 segment 上完整执行过滤条件并将匹配结果记录到 bitset 中。对于 HNSW这一过程发生在 Lucene 的AcceptDocs中// org.apache.lucene.search.AcceptDocs private void createBitSetAcceptDocsIfNecessary() throws IOException { if (acceptBitSet null) { acceptBitSet Objects.requireNonNull(createBitSet(iterator(), liveDocs, maxDoc)); cardinality acceptBitSet.cardinality(); } }createBitSet会将过滤条件的迭代器一直遍历到末尾并根据匹配的文档数量填充一个大小为 segment 的maxDoc的FixedBitSet或者填充一个稀疏 bitset。IVF 会执行等价的操作在扫描第一个倒排列表之前通过 Elasticsearch 自己的ESAcceptDocs完成这一过程。无论哪种方式其成本都取决于 segment 的大小以及计算过滤条件的开销而不是取决于搜索随后会访问 segment 的多少内容。步骤 2跳过未通过过滤条件的文档未通过过滤条件的文档不会计入结果。搜索必须访问 segment 中更多的内容以收集足够多的通过过滤条件的文档HNSW 会进一步遍历图而 IVF 会额外扫描几个倒排列表。两者都会对这一过程进行限制。例如HNSW 会在访问的向量数量达到过滤条件匹配的文档数量后停止遍历图并直接对匹配的文档进行评分。对于匹配数据集大部分内容的过滤条件而言额外工作量很小下一节中的 profile 就展示了这一点。结论是过滤条件导致的额外搜索工作是有界的而且很少是过滤查询耗时的主要来源。步骤 1 中的物化过程则没有这样的界限。这就是为什么真正值得关注的情况不是限制性很强的过滤条件而是宽泛的过滤条件例如匹配数据集 90% 的内容。它几乎不会剪枝也不会增加多少搜索工作但仍然需要在每个 segment 中完整地执行物化付出全部成本。为什么经过过滤的 kNN 搜索可能比未经过滤的搜索更慢搜索 profile 会直接展示这一成本不过它可能并不在你第一时间想到的位置。Lucene 的 kNN 查询几乎所有工作都在rewrite中完成。对于 HNSWAbstractKnnVectorQuery#rewrite会物化过滤条件、搜索每个 segment、合并各个 segment 的结果并返回一个包含最终文档 ID 和分数的DocAndScoreQuery。IVF 执行相同的操作并返回 Elasticsearch 的KnnScoreDocQuery。等到查询以通常意义上的方式执行时搜索已经结束剩下的只是返回一个预先计算好的命中列表。顶层knn子句会在 DFS 阶段运行因此它的 profile 会出现在profile.shards[].dfs.knn[]下。下面是一个未经过滤的搜索使用k: 10和num_candidates: 100针对包含 100 万个向量的单个 HNSW segment 执行其中每项明细都经过精简只保留非零项{ dfs: { knn: [ { vector_operations_count: 2378, query: [ { type: DocAndScoreQuery, description: DocAndScoreQuery[177025,...][0.7580181,...],0.7580181, time_in_nanos: 5708, breakdown: { create_weight: 1250, build_scorer: 2583, next_doc: 1041, score: 834, ... } } ], rewrite_time: 5158917, collector: [...] } ] } }rewrite_time为 5.2 毫秒这就是 kNN 搜索的耗时。DocAndScoreQuery项耗时不到 6 微秒它只负责返回这 10 个命中结果。现在添加一个匹配 90% 文档的match_phrase过滤条件。在实际应用中一个几乎匹配整个数据集的短语并不是常见的过滤条件但它可以清晰地隔离出其中的影响它几乎不会缩小搜索范围却需要较高的计算成本。大多数实际中匹配范围如此广泛的过滤条件其成本都介于这个过滤条件和我们下面进行比较的term过滤条件之间。{ dfs: { knn: [ { vector_operations_count: 2682, query: [ { type: CachingEnableFilterQuery, description: (ConstantScore(body:\red fox\))^0.0, time_in_nanos: 33595666, breakdown: { create_weight: 9125, build_scorer: 174083, next_doc: 15708, into_bit_set: 33396750, into_bit_set_count: 1, ... }, children: [ { type: PhraseQuery, description: body:\red fox\, time_in_nanos: 33589916, breakdown: {...} } ] }, { type: DocAndScoreQuery, description: DocAndScoreQuery[163399,...][0.7200494,...],0.7580181, time_in_nanos: 4092, breakdown: {...} } ], rewrite_time: 40076834, collector: [...] } ] } }发生了三件事过滤条件有了自己的条目与DocAndScoreQuery并列而不是位于其中因为它会在 kNN 查询的 rewrite 阶段运行。CachingEnableFilterQuery是 Elasticsearch 放在 kNN 过滤条件外面的包装器用于确保查询缓存始终认为这些过滤条件值得缓存你编写的查询就是它的子查询。在bbq_disk字段上条目名称有所不同但过滤条件的显示方式相同。into_bit_set就是步骤 1 中的物化过程通过一次调用在整个 segment 上运行短语查询并将每个匹配项记录到 bitset 中。这耗时 33.4 毫秒。这段时间包含在rewrite_time中而不是在其基础上额外增加rewrite_time从 5.2 毫秒增加到 40.1 毫秒其中过滤条件占据了差值中的 33.6 毫秒。匹配少于约 1/128 文档的过滤条件会改为逐个文档收集到稀疏 bitset 中因此其成本会显示在next_doc下。vector_operations_count几乎没有变化。它增加了 13%这大致符合预期因为每 10 个被访问的文档中有 1 个未通过过滤条件。这个查询超过 80% 的耗时都花在了计算过滤条件上。阅读这类 profile 时需要注意一点profile 会绕过查询缓存因此即使未进行 profile 的请求可以从缓存中找到某个过滤条件profile 也始终显示该过滤条件未缓存时的成本。kNN 过滤成本物化与额外搜索工作这两个 profile 之间的差异由两项成本构成值得将它们分开因为它们的增长方式不同。过滤条件物化是每个 segment 都必须付出的成本与 segment 大小成正比并且发生在任何向量处理之前。它的成本完全取决于查询类型过滤条件物化成本termon a keyword低 —— 读取一个倒排列表以批量方式执行intoBitSetrangeon a numeric or date field通常较低 —— 遍历 pointsBKD索引只有单独使用 doc values 的字段index: false才需要检查每个文档match_phrase对每个包含这些词项的文档进行位置解码和交集运算成本最高boolof several clauses每个子句的成本加上合取/析取操作的额外处理Cached filter命中缓存时几乎没有成本缓存未命中时则需要付出完整成本在上面这个包含 100 万个文档的 segment 中一个匹配相同 90% 文档的term过滤条件在into_bit_set中的耗时约为 0.3 毫秒大约比短语过滤条件低 100 倍。而且成本会随着 segment 增大而增长在下面的基准测试中一个匹配 1000 万个文档中 90% 的match_phrase过滤条件会使 HNSW 查询耗时从 2.3 毫秒增加到 395 毫秒。额外搜索工作会在此基础上增加一些成本但正如我们看到的它是有界的而且对于宽泛的过滤条件来说很小上面的 13%。物化成本占据主导地位因此一个使用宽泛且计算成本高的过滤条件的 kNN 搜索大部分时间可能都花在与向量比较无关的工作上。它最终得到的答案也与未经过滤的结果高度重叠如果一个过滤条件匹配整个数据集的 90%并且与查询无关那么整体上距离最近的 10 个邻居中大约已经有 9 个通过了过滤条件而未通过的那些会被排名仅稍微靠后的文档替代。这就是本文其余部分所要讨论的不对称性。过滤条件的成本取决于需要对多少个文档进行评估而将过滤条件从向量搜索之前移到之后会让这个数量发生数量级的变化前置过滤会在向量搜索之前对 segment 中的每个文档执行过滤条件评估后置过滤则只对向量搜索返回的候选文档执行过滤条件评估。kNN 搜索中的前置过滤与后置过滤如果我们直接使用后置过滤呢这个观察并不新鲜而且 Elasticsearch 一直都允许你利用这一点。将过滤条件移到knn子句外部它就会变成后置过滤kNN搜索不受限制地运行然后将过滤条件应用于它返回的k个结果。POST my-index/_search { query: { bool: { filter: { term: { language: en } }, must: { knn: { field: embedding, query_vector: [0.12, -0.03, ...], k: 10, num_candidates: 100 } } } } }我们在如何选择 Elasticsearch 中的精确 kNN 搜索与近似 kNN 搜索中详细讨论过这种权衡其中关键问题可以简单概括为在 kNN 中使用后置过滤的问题在于过滤条件是在我们获取 top k 结果之后才应用的。这意味着最终返回的结果可能少于 k 个因为我们需要从已经从 HNSW 图中检索到的 top k 结果中移除不符合过滤条件的元素。请求 10 个返回 6 个。或者 2 个。或者 0 个。向量搜索不知道过滤条件的存在因此无法保证它返回的结果中有 10 个能够通过过滤条件。唯一可用的补救方法是手动进行过量收集请求k: 50然后希望其中有 10 个能够通过过滤条件。这样你就会陷入一个尴尬的境地你必须猜测这个倍数而正确的倍数取决于过滤条件对于当前这个查询的选择性而通常情况下你并不知道这一点。猜得太低你就会在没有任何提示的情况下返回较短的结果集。猜得太高你就需要为不必要的搜索付出代价而这恰恰是你原本想避免的成本。无论哪种情况k都不再代表 API 所声明的含义因此分页、size以及任何下游处理都必须单独进行推理。因此这两种方案都不太令人满意。前置过滤是正确的但可能会出现异常缓慢的情况。后置过滤速度快但却将统计问题转嫁给了用户而且仍然无法提供任何保证。下表比较了这两种方案以及下一节将介绍的自动后置过滤。前置过滤手动后置过滤自动后置过滤过滤条件放在哪里knn子句内部knn子句外部在bool查询中knn子句内部不变过滤条件在哪些对象上进行评估每个 segment 中的每个文档向量搜索返回的k个结果向量搜索返回的候选项返回 k 个结果是不保证是如果需要则回退到前置过滤谁负责确定候选池大小不需要你通过猜测k的倍数Elasticsearch根据过滤条件的估计选择性最适合高选择性的过滤条件可以接受较短结果集的情况宽泛的过滤条件默认选择性为 0.7 或更高但我们可以做得更好关键在于在这两种方案之间进行选择不一定非得由用户决定而且也不必针对整个索引只做一次决定。Elasticsearch 在 rewrite 阶段会保留过滤条件的Weight。它可以估算过滤条件的选择性判断对于当前查询在当前 shard 上后置过滤是否值得采用根据这个估算值而不是猜测来确定过量收集的规模并在底层保留一个正确性保障机制这样即使估算不准确付出的代价也是延迟而不是结果缺失。这就是自动后置过滤为 HNSW 和 IVFbbq_disk带来的能力。重要的是这一切都不会改变你编写的查询你仍然以表达前置过滤的方式编写查询仍然获得前置过滤的语义而具体如何满足这一要求则交由搜索引擎决定。依次包含四个步骤估算过滤条件的选择性。使用这个估算值确定过量收集的规模。如果结果数量不足则重试一次。如果仍然不足则回退到原始查询。估算 kNN 过滤条件的选择性首先我们需要得到一个数字用来回答 “这个过滤条件允许数据集中的多少内容通过” 一个成本低廉且效果出乎意料地好的方法是询问过滤条件自身的 scorer了解它预计会匹配多少文档然后除以该字段实际建立索引的向量数量public static float computeSelectivity(Weight filterWeight, ListLeafReaderContext leaves, int totalVectors) throws IOException { long filterCost 0; for (LeafReaderContext leafCtx : leaves) { ScorerSupplier ss filterWeight.scorerSupplier(leafCtx); if (ss ! null) { filterCost ss.cost(); } } return totalVectors 0 ? Math.min(1f, (float) filterCost / totalVectors) : 0f; }有两点使这一过程成本很低。ScorerSupplier#cost()是一个估算值。对于 term 查询来说它就是倒排列表的长度这个值可以直接从元数据中读取因此无需物化任何内容。分母则是来自 codec 的向量数量而不是maxDoc因此对于只有部分文档包含该字段的情况这个比例不会受到影响。有两点使这个估算并不完美而这两点都会在后续处理中得到解决而不是假装它们不存在。对于合取查询cost()是一个上界因此选择性可能会被高估。更根本的问题是选择性是 shard 的一个全局属性而真正重要的是过滤条件在查询向量邻域内的通过率。对于一个与向量内容无关的过滤条件两者是一致的。对于一个与向量内容存在相关性的过滤条件两者则可能向任意一个方向产生偏差。假设language: en匹配某个 shard 中 90% 的文档。对于一个英文查询几乎所有最近邻都是英文文档。因此本地通过率接近 100%而全局估算值只是比较保守。对于一个用西班牙语编写的查询最近邻可能主要来自那 10% 的非英文文档因此本地通过率可能远低于 90%即使全局估算值并没有发生变化。下面的重试和回退过程就是为了处理第二种情况。使用二项式模型确定候选池大小给定选择性p未过滤搜索应该收集多少个原始候选项m才能获得至少k个通过过滤条件的结果最简单的答案是。这样可以让你平均获得个通过过滤条件的结果这意味着大约有一半的情况下结果数量仍然不足。平均值在这里并不是正确的工具我们需要的是一个高概率保证。因此可以将每个候选项建模为以概率p独立通过过滤条件。这样个候选项中通过过滤条件的结果数量就是一个二项式随机变量现在我们不再要求均值等于k而是要求k位于均值的下方距离均值为Z个标准差精确地对m求解会得到一个二次方程。将m≈k/p代入方差项则可以得到一个封闭形式其结果略微偏保守而这正是我们希望出现的误差方向Z是一个置信度调节参数第一轮成功的概率约为Φ(Z)。实现中使用Z2.5也就是约 99.4%。这里有一个值得明确说明的假设那就是独立性。我们之所以采用这一假设是因为在没有任何信号表明过滤条件与向量内容之间存在怎样的相关性的情况下这是我们唯一能够做出的假设。下面的重试和回退过程正是为了覆盖这一假设不成立的情况。后置过滤会收集多少额外候选项在代码中这个公式再加上一些保护措施就是/** * Minimum round-1 oversample factor. Round 1 always asks for at least this many × * the target count, regardless of what the binomial variance formula computes. Active * when selectivity is near 1, where the variance term collapses to ≈ 0. */ float POST_FILTER_OVERSAMPLE_FLOOR 1.2f; float POST_FILTER_OVERSAMPLE_Z_SCORE 2.5f; static double zMargin(int k, float selectivity) { return POST_FILTER_OVERSAMPLE_Z_SCORE * Math.sqrt(k * (1.0f - selectivity) / selectivity); } static int computeScaledK(int k, float selectivity) { double zMargin zMargin(k, selectivity); double floor Math.min(Math.ceil(k * POST_FILTER_OVERSAMPLE_FLOOR), NUM_CANDS_LIMIT); return (int) Math.clamp(Math.ceil((k zMargin) / selectivity), floor, NUM_CANDS_LIMIT); }1.2 倍的下限很重要因为当p→1时方差项会趋近于 0而公式会恰好返回k从而没有为少量确实会被过滤掉的文档留下任何余量。NUM_CANDS_LIMIT上限10,000则可以防止过滤条件过于严格时请求一个无限增长的候选池。对于k10和Z2.5得到的过量收集比例为选择性pZσ裕量候选项m过量收集0.990.7912下限1.2x0.951.81131.3x0.902.64151.5x0.803.95181.8x0.705.18222.2x0.557.15323.2x注意这些数值都相当适中而且随着k增大相对于k的比例会缩小因为标准差随着k增长而均值也随着k增长。在k100、p0.55时过量收集比例只有 2.2 倍而k10时则为 3.2 倍。请求 15 个结果而不是 10 个与在一个包含 1000 万个文档的 segment 上物化一个昂贵的过滤条件相比几乎不值一提。还有一个预算不能与k混为一谈弄错这一点很容易导致搜索参数被意外重新调节。对于 HNSWnum_candidates是 beam 宽度是一个独立的调节参数。delegate 会保留用户设置的值但将其下限设为扩大的k如果 beam 比请求的结果数量还窄就无法返回这些结果static int cappedNumCands(int numCands, int scaledK) { return Math.clamp(numCands, scaledK, NUM_CANDS_LIMIT); }这里有一个值得特别说明的结果HNSW delegate 返回的候选项数量会多于扩大的k。每个 segment 的图遍历都会保留完整的 beam最多num_candidates个候选项并对其中每一个候选项检查过滤条件。在 HNSW 中扩大的k主要在num_candidates接近k时才真正重要在通常使用更宽 beam 的情况下第一轮有足够多的候选项可供选择。对于 IVFnum_candidates只有相对于k才有意义codec 根据两者的比例计算访问比例。如果在k增大时保持num_candidates不变就会在不知不觉中减少搜索范围而 IVF 会对其进行缩放以保持这个比例static int numCandsPreservingRatio(int numCands, int k, int newK) { if (k 0) { return Math.clamp(numCands, newK, NUM_CANDS_LIMIT); } long scaled (long) Math.ceil((double) numCands * newK / k); return Math.clamp(scaled, newK, NUM_CANDS_LIMIT); }后置过滤结果不足时进行重试二项式模型的校准目标是约 99.4% 的成功率而它所依赖的独立性假设可能并不成立。因此第一轮有时会出现结果不足。重试轮次会将“通常足够”变成“足够”。只有当结果不足看起来更像是运气不好而不是模型错误时才会执行重试。如果第一轮返回的通过过滤条件的结果远少于全局选择性所预测的数量这就表明过滤条件与查询邻域存在相关性而这正是二项式模型明确无法处理的情况。更多轮次无法修复一个错误的模型因此我们会提前退出double expectedHits k * (double) selectivity; double threshold expectedHits * 0.5; boolean shouldExit scoreDocsCount threshold;;如果实际通过过滤条件的结果少于预测数量的一半就意味着过滤条件对这个查询的向量邻域并不友好此时前置过滤才是正确的工具。对于k 5会跳过这项检查因为预期结果数量太小这个比例没有实际意义。重试并不只是用更大的k再运行一次这样会再次找到相同的候选项。它必须搜索一些新的区域因此需要传递三部分状态int remaining expectedBaseQueryDocMatches - scoreDocs.length; int retryK PostFilterableKnnQuery.computeScaledK(remaining, selectivity); Query retry postFilterQuery.createRetryQuery(searcher.getIndexReader(), excluded, seedDocsPerLeaf, retryK); TopDocs retryDocs searcher.search(retry, retryK);排除集合。第一轮中看到的每个文档——无论通过还是未通过过滤条件——都会通过ExcludeDocsQuery排除。HNSW 会将它组合到 accept-docs 中IVF 则将其传递给倒排列表遍历使 codec 直接跳过这些文档。种子入口点。对于 HNSW如果从顶层重新开始图遍历就会再次沿着相同的路径向下搜索。因此重试会从第一轮中距离最近的匹配项开始播种每个 segment 最多四个这样它一开始就处于正确的邻域中然后向外扩展int[][] seedDocsPerLeaf nearestSeedsPerLeaf(matching, MAX_SEEDS_PER_LEAF);IVF 暂时忽略种子它已经知道哪些质心距离最近只需重新扫描这些质心同时跳过已排除的文档。重新调整目标数量。remaining是通过过滤条件的结果中的不足数量。它会再次使用相同的选择性传入computeScaledK以针对重试过程中同样会发生的结果损耗进行扩充。恰好只重试一次。第二次重试就等于追逐一个模型已经证明错误的分布而下面的回退机制成本更低并且能够严格保证正确性。回退到前置过滤回退轮次使自动后置过滤可以安全地默认启用。如果后置过滤没有产生完整的候选池就丢弃它的结果然后改为运行原始的前置过滤查询。if (scoreDocs.length expectedBaseQueryDocMatches) { logger.debug( post filtering retrieved only [{}] results, less than the desired [{}] results. Falling back to original query, scoreDocs.length, expectedBaseQueryDocMatches ); return null; }从postFilterRewrite返回null会让rewrite进入常规路径Query rewritten ((Query) innerQuery).rewrite(searcher); this.totalVectorOps innerQuery.totalVectorOps(); return rewritten;用户的查询就是回退方案。这意味着错误的选择性估算所带来的最坏情况是延迟浪费了一次候选项收集然后再执行原本就会执行的前置过滤搜索而绝不会导致结果集过短或结果错误。正是这一特性使得像ScorerSupplier#cost()这样粗略的估算也足够好它只需要在足够多的情况下估算正确从而弥补估算错误时所付出的成本。简而言之第一轮之后如果至少有k个候选项通过过滤条件则返回距离最近的k个。如果通过过滤条件的候选项少于预期数量的一半0.5⋅p⋅k则提前退出执行前置过滤查询。否则重试一次。如果此时至少有k个候选项通过过滤条件则返回距离最近的k个如果仍然不足则回退到前置过滤查询。相同的两项检查每轮一行。所有前置过滤结果都与单独执行前置过滤时完全一致。还有一个与分数正确性有关的细节值得注意。对于量化字段近似分数会通过一次精确的重新评分过程进行校正。通常情况下IVF 会在自己的rewrite中完成这一过程但对于后置过滤 delegate必须在过滤之后进行否则我们就会对那些即将被丢弃的文档进行重新评分。delegate 会跳过这一步而 orchestrator 会在候选池最终确定后通过finalizeTopK回调执行这一过程。如果没有这个钩子后置过滤的结果会携带原始的量化分数而回退结果则会携带精确分数从而在同一次搜索中混用两个不同的分数域。一个经过过滤的 kNN 查询从头到尾假设你在一个包含 1000 万个文档的 shard 上运行以下查询其中language: en能匹配其中 900 万个文档{ knn: { field: embedding, query_vector: [...], k: 10, num_candidates: 100, filter: { term: { language: en } } } }1. Rewrite。PostFilterKnnQuery#rewrite构建过滤条件的Weight并将其与embedding上的FieldExistsQuery合取这样没有向量的文档就不会被计入但不会执行这个过滤条件。2. 估算。在各个 segment 上通过ScorerSupplier#cost()得到约 900 万而实际建立索引的向量数量为 1000 万p0.9。这高于默认的 0.7 阈值因此启用后置过滤。如果结果只有 0.4我们就会在这里停止并运行普通的前置过滤查询。3. 确定第一轮的规模。m⌈(102.510⋅0.1/0.9)/0.9⌉15因此会构建一个不带过滤条件的 delegate请求 15 个结果而不是 10 个。它的搜索预算遵循前面的规则对于 HNSWnum_candidates保持为 100即 beam 宽度对于 IVF则将其缩放到 150这样访问比例就不会发生变化。4. 执行无过滤搜索。delegate 在所有 segment 上运行不使用 accept-docs bitset不会进行过滤条件物化也不会进行额外搜索。每个 segment 都会保留自身搜索收集到的所有候选项因此 orchestrator 无需重新推导这些候选项。对于 HNSW这是该 segment 的整个 beam最多 100 个候选项对于 IVF则是所请求 15 个结果的一个小倍数因为 IVF 会进行过量收集以吸收出现在多个倒排列表中的文档。5. 将过滤条件应用于候选项而不是 1000 万个文档。applyFilter按 doc-ID 顺序遍历每个 segment 的候选项并通过Lucene#asSequentialAccessBits对它们进行测试。对于暴露TwoPhaseIterator的过滤条件每个候选项只需要执行一次 approximation advance并且只有当 approximation 命中该候选项时才调用matches()。这正是整个方案的核心过滤条件只针对每个候选项进行一次评估而不是针对 segment 中的每个文档进行评估。这也意味着过滤条件不再需要通过缓存来实现快速执行。在前置过滤中避免每次查询都为物化付出成本的常用方法是使用过滤条件缓存该缓存会存储过滤条件针对每个 segment 的 bitset以便重复使用。只有当某个过滤条件被使用足够多次并进入缓存后这种方式才会有所帮助而且每个新 segment 都需要从冷缓存开始。后置过滤没有值得缓存的内容applyFilter会告诉过滤条件它只需要面对少量候选项而 Lucene 的查询缓存也不会为一个匹配数百万个文档、但实际上只会检查其中极少一部分的过滤条件创建 bitset。这个过滤条件第一次使用时的速度与第一百次使用时一样快。6. 检查是否达到目标。目标是用户请求的 10 个结果。对于一个能够通过 90% 文档的过滤条件大约每 10 个候选项中有 9 个能够通过过滤条件因此跨各个 segment 后通过的数量远超过 10 个。我们进行去重并保留距离最近的 10 个。假设只有 7 个不同的候选项通过了过滤条件就像之前提到的西班牙语查询那样当过滤条件与查询存在相关性时就可能发生这种情况。7 高于针对不友好过滤条件的阈值10×0.9×0.54.5因此会触发重试排除之前已经看到的每个候选项无论它是否通过过滤条件从每个 segment 中距离最近的、最多 4 个通过过滤条件的候选项开始播种然后请求computeScaledK(3, 0.9) 5个额外结果以弥补 3 个结果的不足。如果这样仍然无法达到 10 个结果就运行前置过滤查询此时后置过滤除了候选项收集之外没有产生任何额外成本。7. Finalize。通过 introselect 按分数选择 topk并将结果包装在KnnScoreDocQuery中。过滤条件只在向量搜索返回的候选项上进行评估而不是在 1000 万个文档上进行评估。向量搜索不受过滤条件限制并且返回的文档与前置过滤原本会找到的 10 个文档相同同时还能保证如果结果不一致你最终会得到前置过滤查询的结果。最多 1000 万个向量上的后置过滤与前置过滤基准测试基准测试设置为了测量这里的性能上限我们进行了强制对比每种配置都运行两次一次使用前置过滤一次使用后置过滤并绕过自适应逻辑使两种策略都无法回退到另一种策略。这比生产环境中的实际行为更加严苛真实实现会针对每个查询进行选择并在必要时回退但这种测试能够清晰展示每种策略在哪些情况下更有优势。测试网格5 个数据集从 523K 到 1000 万个向量不等每个数据集都分别使用 IVF 和 HNSW 建立索引同时采用单 segment 和多 segment 布局针对 5 种过滤条件和 7 种选择性分别运行前置过滤和后置过滤5 × 2 × 2 × 5 × 7 × 2 1400 次测量也就是 700 组匹配的前置/后置过滤对比。7 种选择性分别为 0.55、0.7、0.8、0.9、0.95、0.99 和 1.0其中 1.0 表示没有过滤条件。固定使用num_candidates1000、k10、1% 的访问比例、未缓存的过滤条件以及每个测试点 300 个查询。IVF 使用clusterSize384HNSW 使用m16、efConstruction200全程使用 1-bit 量化。过滤条件均未进行缓存。这是前置过滤的冷启动情况如果过滤条件在多个查询之间重复使用温热的过滤条件缓存会缩小两者之间的差距。这也是后置过滤唯一会遇到的情况因为后置过滤从一开始就不会依赖缓存。并非每个数据集都具有可供range、term和phrase过滤条件使用的 numeric、keyword 或 text 字段。如果缺少某个字段我们就添加该字段并使用随机内容填充。然后对数据集进行采样选择与目标 D% 文档匹配的过滤值range是针对 numeric 字段的范围查询其边界经过选择使 D% 的文档落在该范围内。term匹配一个 keyword 值该值存在于 D% 的文档中。phrase是针对 text 字段的短语查询查询的短语出现在 D% 的文档中。对它进行评估意味着需要检查词项位置而不仅仅是检查词项是否存在因此它是这里物化成本最高的过滤条件。range_term在bool查询中组合range和term两个过滤条件。random匹配随机选择的 D% 文档。不同数据集规模和过滤条件类型下的结果对于过滤而言数据集最重要的属性是其大小因为物化过滤条件所需的时间与每个 segment 中的文档数量成正比。我们使用这 5 个数据集来展示随着数据集规模增长两种策略之间的差异并在下面使用最大的cohere-msmarco-10M数据集1000 万个向量、1024 个维度、float32给出详细数据。在选择性低于 1.0 的情况下按数据集规模统计的后置过滤相对于前置过滤的中位速度提升。蓝色表示后置过滤更快红色表示前置过滤更快。后置过滤几乎在所有情况下都占据优势在每一种数据集规模、两种索引类型以及两种布局中都是如此。具体领先多少取决于物化过滤条件的成本而在大多数布局中随着数据集规模增长这一差距也会扩大。在低于 1.0x 的 100 个测试单元中有 16 个属于多 segment 布局下成本较低的term或range过滤条件最低为 0.68x。在cohere-msmarco-10M数据集上120 组过滤条件对比中有 104 组采用后置过滤时速度更快其中单 segment 上的全部 60 组都是如此另外还有 2 组基本持平差异在 2% 以内。剩余的 14 组是多 segment 布局下成本较低的range和term过滤条件其中前置过滤最多只领先 1.33x1.76 ms 对 2.34 ms。延迟与选择性之间的曲线直接展示了其中的机制cohere-msmarco-10M 单 segment 上延迟与过滤条件选择性的关系。红色表示前置过滤蓝色表示后置过滤实线表示 IVF虚线表示 HNSW。蓝色的后置过滤曲线几乎是平的。对于后置过滤而言延迟主要由 kNN 搜索本身决定而 kNN 搜索不受过滤条件限制因此无论过滤条件匹配多少文档其成本都基本相同。在此基础上将过滤条件应用于候选项所增加的成本很小而且即使过滤条件的范围不断缩小过量收集的规模也仍然很小。对于给定的过滤条件类型而言延迟几乎不受选择性影响在中位配置下从整个 0.55–0.99 范围来看延迟变化约为 10%而前置过滤约为 50%。红色的前置过滤曲线位于其上方差距大致相当于物化过滤条件的成本也就是说过滤条件越昂贵两者之间的差距就越大当选择性达到 1.0 时两条曲线最终汇合因为此时没有需要评估的过滤条件。召回率基本与策略无关140 组对比中的每一组召回率差异都在 0.01 以内因此这里的权衡实际上纯粹是延迟上的权衡。每个点代表 cohere-msmarco-10M 上 140 组前置/后置过滤对比中的一组。左图召回率。右图对数尺度下的延迟位于对角线下方的点表示后置过滤速度更快。局限性相关过滤条件与多 segment 布局有两个注意事项值得明确说明。这些过滤条件与向量基本不相关。基于随机内容构建的过滤条件会独立地通过文档而不受文档在向量空间中所处位置的影响这正是二项分布模型所采用的假设。结果也体现了这一点在任何单一配置中5 种过滤条件之间的召回率差异最多为 0.04并且在每种选择性下中位召回率都在 0.74–0.75 之间。对于相关过滤条件例如前面提到的language示例重试、提前退出和回退机制会发挥作用即使选择性估算不准确也能确保结果正确。衡量这种加速效果有多少能够延伸到高度相关的过滤条件是下一步很自然的基准测试方向。多 segment 布局会缩小后置过滤的优势。比较热力图中的单 segment 和多 segment 面板。固定的每个 segment 成本需要支付更多次而前置过滤则可以在每个 segment 较小的maxDoc上摊销其 bitset 成本。后置过滤在成本较高的过滤条件上仍然更快只是领先幅度较小。如何启用和调整自动后置过滤自动后置过滤计划在 Elasticsearch 9.6 以及即将发布的 Elastic Cloud Serverless 版本中默认启用。启用后你无需修改查询继续将过滤条件写在knn子句内部每个 shard 都会针对每个查询自行决定是否值得尝试后置过滤。调整后置过滤选择性阈值这一决策由一个索引设置index.dense_vector.post_filter_selectivity_threshold控制其默认值为 0.7。当查询的估计选择性大于或等于该阈值时查询会进入后置过滤流程。因此该阈值实际上规定了过滤条件必须有多宽泛才会尝试使用后置过滤阈值行为1.0关闭。没有任何过滤条件能够满足要求。0.9只有非常宽泛的过滤条件 —— 匹配 90% 以上数据集的过滤条件 —— 才会使用后置过滤。0.7(默认值)匹配 70% 以上文档的过滤条件使用后置过滤。0.0每个带过滤条件的 kNN 查询都会尝试使用后置过滤。如果你的过滤条件通常需要较高的评估成本可以降低该值来针对索引进行调整也可以将其设置为1.0从而完全选择退出。你可以在索引设置中进行配置PUT my-index { settings: { index.dense_vector.post_filter_selectivity_threshold: 0.5 }, mappings: { properties: { embedding: { type: dense_vector, dims: 1024, index_options: { type: bbq_hnsw } } } } }范围与局限性值得了解一下适用范围同时适用于HNSW和bbq_disk**IVF**字段支持float、bfloat16和byte元素类型以及 HNSW 上的bit向量。嵌套向量字段也受到支持但有一个需要注意的地方由于嵌套 kNN 搜索每个 parent 只保留一个命中结果因此一个已经产生匹配结果的 parent 会在重试时作为一个完整块被排除而一个 child 只是被过滤掉的 parent 仍然有资格参与重试 —— 它下面更深层的 child 仍然可能通过过滤条件。查询语义保持不变。你仍然编写前置过滤并获得前置过滤语义。请求体没有任何变化这纯粹是一个执行策略决策。profile 会显示实际运行的是哪种策略。当查询使用后置过滤时过滤条件对应的条目中没有into_bit_set过滤条件会逐个候选项进行检查这意味着它会针对向量搜索返回的每个候选项报告一次advance。在前面的短语过滤示例中这意味着有 100 次advance调用beam 中的每个候选项一次总耗时远低于 1 毫秒而不是 33.4 ms 的into_bit_set。在向量搜索自身的命中列表旁边还会出现第二个命中列表条目其中包含保存最终 topk的KnnScoreDocQuery。如果想查看单次决策重试、提前退出、回退以及这些决策背后的选择性估算请将logger.org.elasticsearch.search.vectors.PostFilterKnnQuery: DEBUG设置为DEBUG。Elasticsearch 中过滤 kNN 搜索的下一步我们最感兴趣的改进方向包括更好的选择性估算。ScorerSupplier#cost()不需要额外成本但比较粗略而且会高估 conjunction。Elasticsearch 已经在跟踪更丰富的字段统计信息如果将这些统计信息接入或者在 segment 的有限范围内对过滤条件进行采样就可以让阈值不必设置得如此保守。提前检测相关性。针对 hostile filter 的提前退出属于响应式机制只有在花费一轮搜索发现过滤条件与查询邻域存在相关性之后我们才知道这一点。如果在做出决策之前就能估算过滤条件的局部通过率例如根据图遍历的 seed 文档或者使用缓存的每查询统计信息就可以将其转变为低成本的前置路由决策并安全地降低阈值。基于成本的路由。基准测试表明合适的阈值不仅取决于选择性也同样取决于过滤条件类型与term过滤条件相比match_phrase过滤条件的物化成本高出几个数量级因此即使在低得多的选择性下也值得使用后置过滤。基于过滤条件查询结构而不仅仅是选择性建立成本模型可以让引擎针对每个查询做出这一决策而不是依赖单个每索引阈值。按 segment 做出决策。目前的路由是在 shard 级别进行的但不同 segment 之间的选择性和 segment 大小可能有所不同。按 segment 做出决策后同一个查询中就可以让较小的 segment 使用前置过滤而较大的 segment 使用后置过滤。更广泛来说这一观点并不局限于 kNN。Elasticsearch 已经投入大量工作来提升向量比较的速度量化、SIMD、更好的 HNSW 图以及更适合磁盘的 IVF 索引并因此实现了向量比较不再是瓶颈的查询。当一次过滤后的 kNN 搜索大部分时间都花在物化昂贵的过滤条件上时真正值得进行的优化并不是让距离函数更快而是意识到要回答一个关于十个文档的问题并不需要在 1000 万个文档上运行过滤条件。常见问题kNN 搜索中的前置过滤和后置过滤有什么区别前置过滤会在向量搜索运行期间应用过滤条件因此 top k 结果是匹配过滤条件的文档中距离最近的 k 个文档。后置过滤则不受限制地运行向量搜索然后再对结果应用过滤条件这样速度更快但可能返回少于 k 个结果除非搜索首先过量收集候选项。为什么过滤后的 kNN 查询有时会比未过滤查询更慢前置过滤会在进行任何向量比较之前为每个 segment 将过滤条件物化为 bitset而其成本与 segment 大小成正比而不是与搜索实际访问的文档数量成正比。对于match_phrase这样的高成本过滤条件这项工作可能成为查询的主要成本即使过滤条件匹配几乎所有文档、因此实际上排除了很少的文档也必须完整承担这项成本。原文Elasticsearch kNN filter: Pre-filtering vs. post-filtering | Elasticsearch Labs