Elasticsearch DSL 语法中 queries/filters 执行顺序探秘

作者: 梁尔舒,李昀晖

写在前面

我们之前应该都了解链表求交、求并的算法,但是很少在实际工作中见过这些算法是怎么体现的,解决了哪些场景下的问题,其实 lucene 解决链表求交并的算法非常漂亮。最近因为工作中需要排查线上总是出现某些检索 DSL 执行比较慢,在网上到处找底层具体执行的资料,发现资料少之又少,讲 API 的文章千篇一律,直到在官网找到一篇漂亮的文章还特么全网没找到翻译,便借此机会系统学习了 DSL 在 lucene 底层到底是怎么执行的以及 profile API 工具的使用。在这里我把这篇文章的翻译分享给国人,以飨各位长期以来对我的关注和支持!😄

lucene 检索执行时序图
teena3o8rz.png

我们现在开始:

我们经常有这样的疑问——filters 之间执行的顺序是怎么样的,以及 filter 查询是在 query 查询之前还是之后,等等这些问题。这确实是非常重要的问题:诀窍就在于执行一个 query 时优先处理 cheap bits(代价更小的比如较短的 posting list)。也许你可能在过去听说或看过 filter 查询的执行优先于 query,因为大家都觉得我们不对不匹配过滤器的文档计算分数。但实际情况要复杂一些。

同样,该问题的措词表明我们要遍历所有文档,并检查 query/filter 是否一一匹配,而事实则更加微妙:我们的索引结构可以帮助有效地跳过可能不匹配的文档。

查询/过滤器如何运行?

在解释查询如何工作之前,我无法让您深入了解查询的执行顺序。 查询和过滤器具备着以下操作:

  • cost():查询/过滤器匹配多少文档的近似值。
  • docID():当前文档 ID,初始化为-1。
  • advance(target):查找可能匹配的目标之后的第一个文档。(skipList操作
  • nextDoc(): 查找可能匹配的下一个(按文档 ID 顺序)文档。 这是 Advance(docID()+ 1)的优化版本。*
  • matches():检查当前文档是否匹配。
  • matchCost():调用 matches() 的成本估算。
  • score():计算当前文档的分数。

这有点复杂,但是存在所有这些操作的充分理由! 在此阶段需要注意的最重要的一点是,匹配的文档分为两个阶段。 首先是一个 approximations 的过程(找到近似匹配的 doc),它可以有效地迭代倒排中与查询匹配的文档的超集(超集包含着不匹配的 doc),是因为这些超集的迭代是通过 nextDoc / advance 来操作的。 然后,有一个验证阶段,旨在通过 matchs 操作验证当前文档是否与实际匹配。 该设计的目的是确保我们在所有 approximations 之间达成一致后才开始运行代价较大的 posting list,这样理论上整体执行代价最小。 另外,值得注意的是,查询和过滤器之间的唯一区别是我们从不对过滤器调用 score()

为了更好的理解这些操作,让我实际给你们举一些例子:

Term queries

term 查询是 Elasticsearch 支持的最有效的查询:它们的匹配项是在倒排索引结构中预先计算的



  • cost(): 返回 doc freq,该 doc freq 编码在倒排索引中( 在创建 Weight 时就已从倒排文件中查到)。
  • advance(target): 使用 skip lists 跳转到大于或等于 target 的位置
  • nextDoc(): 从 the postings list 返回下一个 doc。
  • matches(): 总是返回 true.
  • matchCost(): 总是返回 0.
  • score(): 根据索引统计信息计算当前文档的分数。

Disjunctions (a OR b OR ...)

  • cost(): 返回子 clauses 的代价和。
  • advance(target): 在所有子 clauses 调用 advance(target) 并返回大于等于 target 的最小的值
  • nextDoc(): 在所有子 clauses 调用 nextDoc() ,返回应该迭代的下一个 doc(和 advance 操作类似)
  • matches(): 基于当前 doc id, 迭代所有子 clauses,只要有任何一个子 clausestrue 就返回 true,都不匹配返回 false
DisjunctionScorer.java 代码片段:

@Override
    public boolean matches() throws IOException {
      verifiedMatches = null;
      unverifiedMatches.clear();
  
      for (DisiWrapper w = subScorers.topList(); w != null; ) {
        DisiWrapper next = w.next;
      ..................
......................

  
      // verify subs that have an two-phase iterator
      // least-costly ones first
      while (unverifiedMatches.size() > 0) {
        DisiWrapper w = unverifiedMatches.pop();
        if (w.twoPhaseView.matches()) {
          w.next = null;
          verifiedMatches = w;
          return true;
        }
      }
  
      return false;
    }
  • matchCost(): 返回 sub clausesmatch cost 总和,以其 cost (clauses 可能匹配的文档数量)加权(因为与匹配少数文档的 clauses 相比,我们更可能在匹配多个文档的 clauses 上调用 match())。
if (hasApproximation == false) { // no sub scorer supports approximations
    twoPhase = null;
  } else {
    final float matchCost = sumMatchCost / sumApproxCost;
    twoPhase = new TwoPhase(approximation, matchCost);
  }
}
  • score(): 返回匹配当前文档的所有 sub clauses 的分数加和

因为求并集本质上是关于合并排序的迭代过程,所以 我们使用 heap 来提升效率

Conjunctions (a AND b AND ...)

  • cost():返回 sub clauses 中的最小代价
  • advance(target):
    • 在具有最小 cost() 值的 clause 上调用 advance(target),得到下一个候选的 C
    • 按照 cost() 值的升序继续迭代其它的 clause,并且在其上调用 advance(C),如果这些其都返回 C, 那么我们说明当前的 C 是一个真正匹配的 doc。如果返回了其它值,那么将这个值作为新的候选值,并像之前的步骤一样继续迭代其它 clause,直到找到下一个匹配。
  • nextDoc(): 除了初始化调用 nextDoc() 时选择在拥有最小的 cost() 值的 clause 上,其它和 advance(target) 调用一样
  • matches(): 按照 matchCost() 值升序迭代所有的 clause,只要出现一个不匹配就返回 false, 否则返回 true
  • matchCost(): Return the sum of the match costs of sub clauses.所有 sub clausesmatch cost 总和
  • score(): 返回匹配当前文档的所有 sub clauses 的分数加和

交替执行子句直到找到共同的匹配项,这有时被称为"leapfrog" (蛙跳)

Phrase queries

短语查询很有趣,词组查询本质上是一种求交集,在这里我们针对每个文档执行一些其他操作,以检查它们是否匹配。

  • cost(): 和求交集的含义一样。
  • advance(target): 和求交集的含义一样。
  • nextDoc(): 和求交集的含义一样。
  • matches(): 迭代当前文档的位置,直到在连续位置找到 term 为止,我们不需要进一步迭代。
  • matchCost(): 公式有点复杂,但是总之,它与短语中使用的 term 的平均词频成正比。平均词频即:它们在索引中的总出现次数除以包含这些 term 的文档总数。
  • score(): 保持继续迭代,以查找该短语在当前文档中出现的次数,并使用此短语频率作为分数计算的基础。

这也使您对过滤器为什么比查询性能更好的见解。在这种情况下,过滤器不仅可以跳过得分计算,而且还可以在找到一个匹配项后立即停止对位置进行迭代,而不必对所有位置进行计数。

回到执行顺序上

如果您读了上面的求交集如何执行的描述,则会发现 nextDoc()advance(target) 的执行顺序是基于 cost() 决定的,而 matches() 的执行顺序是基于 matchCost() 决定的。

因此,如果您搜索 the AND quick AND fox,我们将首先查看索引统计信息,以查找哪个 term 最稀有,然后对包含该 term 的文档进行迭代,并检查它们是否还包含其他 term

现在是一个更复杂的示例:假设您搜索 "the fox" AND "lazy dog",并且 term 具有以下索引统计信息:

Term Doc frequency Average term frequency
the 100 24
fox 10 5
lazy 40 3
dog 20 10

"the fox" 的代价为 min(100,10)=10,因此我们将在代价为 min(40, 20)=20"lazy dog" 之前执行其 approximation(求近似过程)。 但是,一旦我们在两个近似之间达成一致,即。 包含全部 4 个术语 the, fox, lazydog 的文档,然后我们将首先在““lazy dog””上调用“ matches()”,因为它具有 3+10=13 每个文档的总位置,而 "the fox"24+5=29 个位置出现。 如您所见,“哪个查询先运行”没有简单的答案!

结论

本文介绍了 Elasticsearch 查询的执行是如何工作的。倒排索引的 metadata 数据(比如 term 频率,文档频率)不仅可以用于文档打分阶段,也可以用于优化 query 的执行顺序。最后是一些常见的问题:

  • Q:我们编写的查询 DSL 中的 query/filter 顺序重要吗?
  • A:不重要。因为 DSL 具体的执行顺序,会由相应 query/filter 的 cost,匹配 cost 决定。
  • Q:filter 是在 query 之前还是只后执行?
  • A:不一定。可能是交替执行的。Conjunctions(交集查询,AND 查询)的执行顺序,会首先执行最小 cost 的部分(lead iteration),之后依次检查其它的 clauses 是否匹配。当所有的子查询都匹配后,才会计算分数。
  • Q:怎么知道那个 query/filter 最先执行
  • A:es 并没有提供这些信息。通过 profile API,可以获得 nextDoc/advancematches 方法调用次数的详细情况。Query nodes that have the higher counts have been run first(最高 count 数的 DSL 结点会最先执行?)。

英文原文: https://www.elastic.co/cn/blog/elasticsearch-query-execution-order


本文地址:https://www.6aiq.com/article/1597589414980
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出