Elasticsearch 查询重写规则：通配符扫描性能提升 2.3 倍

Lucene 查询重写规则使 Elasticsearch 列式存储模式下的两个字符串扫描查询速度分别提升了 2.3 倍和 1.6 倍。这两条规则都在运行时识别出特定的查询模式，并替换为更高效的实现。对于像 *google* 这样的通配符查询，这意味着使用子字符串搜索替代自动机。对于 SearchPhrase != '' 这样的过滤器，则可以跳过 Zstd 解压缩，因为它只需要获取位于偏移量数组中的字符串长度。

列式模式是 Elasticsearch 针对分析场景优化的列式存储模式，专为扫描密集型工作负载（如日志分析）而构建。在此模式下，关键字字段默认不会建立倒排索引，因此词项查询和通配符查询会扫描 doc values。DocValuesSkippers（区域映射）已经能够减少扫描触及的数据量，但这些重写规则进一步降低了剩余数据的处理成本。

Lucene 查询重写机制的工作原理

在 Lucene 中，每个查询都可以选择实现一个 rewrite 方法，该方法返回另一个查询。这个方法返回一个语义相同但实现方式不同的查询。查询引擎会反复调用 rewrite 方法，直到返回的查询不再变化。这个最终的查询才是实际被评估的查询。重要的是，rewrite 方法可以查看实际的查询参数，并基于这些参数特化实现。

例如，在查询字符串字段是否包含值 "foo" 的查询中，rewrite 方法知道我们正在搜索的词项是 "foo"。理论上，rewrite 可以将通用的查询类替换为特定于 "foo" 的查询类。例如，原始的 ScanningBinaryDocValuesTermQuery 查询类可以被替换为 FooQuery。当然，这个规则可能没什么帮助，但它展示了通过重写规则可以达到的特化程度。

数据库系统中的重写规则与查询优化

有必要将重写规则置于数据库系统的大背景下进行讨论。Lucene 和 Elasticsearch 并非首个使用转换规则来优化查询的系统。大多数（也许是所有）数据库系统在查询优化过程中都会使用某种规则系统。最具影响力的重写规则系统来自 IBM 的 Starburst 数据库。该系统的核心贡献在于其可扩展性；例如，可以添加新的数据类型和存储方法，同时（对我们来说最重要的是）添加优化器重写规则。

每条规则包含两个部分：

1. 条件函数： 一个谓词，用于判断当前规则是否适用于当前查询图。
2. 动作函数： 将查询计划重写为更优形式的转换。

规则引擎会应用匹配的规则，直到满足停止条件。

尽管 Lucene 的 rewrite 方法表面上与这些条件和动作函数不同，但它实现了相同的目标。它检查是否满足某些条件，如果满足，则通过返回一个新查询来应用重写。如果条件不满足，rewrite 返回 this，即用自身替换查询，表示不应用该规则。

为什么这些规则存在于 Lucene 中，而非 ES|QL 查询优化器

实际上，Elasticsearch 在 Elasticsearch 查询语言 (ES|QL) 优化器中包含了一个独立的重写规则系统。该优化器在查询的高层结构上运作；例如，进行谓词下推以避免对将被过滤掉的文档进行不必要的计算。然而，在 Lucene 中保留规则系统仍然非常有用。由于 Lucene 充当 ES|QL（以及传统的 _search）查询的存储层，因此在 Lucene 中表达利用物理数据格式的重写，比在更高层次的优化器中更容易。

通配符查询的重写规则：更简单的代码，无需自动机

通配符查询支持 ? 和 * 运算符，分别匹配任意单个字符或任意多个字符。这些运算符可以在通配符查询中出现任意多次。与正则表达式类似，为了判断一个字符串是否匹配通配符查询，我们根据查询字符串构建一个自动机，然后使用字符串字节在自动机中进行状态转换。这相对较快，但如果需要为每个文档都执行此操作，延迟会显著增加。

但也许我们并不总是需要运行自动机。考虑一个像 *foo* 这样的查询。如果您正在编写一个简单的查询引擎来查找字符串列表中的匹配字符串，您会如何实现它？几乎所有编程语言都内置了您需要的工具：一个在给定字符串中查找子字符串的方法。这个函数不需要复杂的自动机；它可能只包含几个 for 循环。

当然，我们不能用这个函数来实现任意的通配符查询，但我们也不需要这样做。规则重写系统并非为通用形式而设计。它用于实现特殊情况，并且可以看到具体的查询。它知道我们正在查找 *foo*，并意识到这种特殊情况不需要重量级的自动机机制。对于任何以 * 开头和结尾，中间包含某些词项的查询，它都可以做同样的事情。

下面的伪代码展示了这个模式。顶部是通用的 WildcardQuery。它有两个值得注意的字段：查询字符串（例如，*foo*）以及为该查询构建的自动机。matches 方法通过使用字段值来评估自动机的状态转换，从而检查给定的 docId 的字段值是否匹配。更有趣的是，它的 rewrite 方法会检查查询是否匹配我们的特殊情况。我们使用一个正则表达式来检查查询字符串是否以 * 开头，至少包含一次非 * 字符，然后以 * 结尾。如果是，我们将返回一个 ContainsQuery 作为特殊情况，并传入内部的查询字符串（因为它不关心 *）。然后，ContainsQuery 只需执行一个简单的 contains 检查，看词项字节是否存在于值字节中的某个位置。

class WildcardQuery(query, automaton, docValues):
    boolean matches(docId):
        value = docValues.loadValue(docId)
        return automaton.matches(value)

    Query rewrite():
        if query matches r"^\*[^*]+\*$":
            return ContainsQuery(query[1:-1], docValues)
        return self

class ContainsQuery(term, docValues):
    boolean matches(docId):
        value = docValues.loadValue(docId)
        return value.contains(term)

在 ClickBench Q20 上对通配符重写进行基准测试

通配符重写很简单，但它真的有效吗？是的，我们可以使用 ClickBench 基准测试，其中包含多个此类形式的查询。查询 20 (Q20) 是 FROM hits | WHERE URL LIKE "*google*" | STATS count = COUNT(*)。这正是此规则匹配的查询模式：对通配符查询 *google* 进行字符串匹配。由于查询只是计数，我们可以清楚地看到这项技术的效果。事实证明，它非常有效。在没有过滤器缓存的情况下，Q20 的热查询时间中位数延迟提升了 1.75 倍。本文中的所有基准测试均在 Intel Core i9-13900H 上运行。

为子字符串搜索添加 SIMD：从 1.75 倍提升到 2.3 倍

但我们能做得更好吗？是的，切换到简单的 contains 检查开辟了新的可能性。我们可以不用两个 for 循环，而是将标量逻辑替换为单指令多数据流（SIMD）逻辑。Elasticsearch 使用 Panama vector API（请参阅我们关于 Elasticsearch 中 SIMD 的文章），这使得我们可以在 SIMD 中实现 contains 检查。这对于较长的字符串尤其有效，因为它们可以利用宽 SIMD 寄存器；对于长度低于 24 个字符的字符串，我们仍然使用标量方法。通过这一改动，我们又获得了 1.32 倍的提升，相对于基于自动机的方法，总加速比达到了 2.3 倍。

空字符串的重写规则：更少的数据，无需解压缩

基于 Lucene 的规则的一个优点是它们处于底层，能够贴合数据格式。这条规则就是如此，它适用于字符串数据。

列式存储如何编码字符串数据

在 Elasticsearch 的标准模式下，字符串值按文档存储；这是一种行主序格式。但在列式模式下，数据自然按列主序格式存储。一列字符串数据被存储为多个块。每个块包含许多字符串值，并由一个整数偏移量数组和一个（Zstd 压缩的）字符串字节 blob 组成。对于索引 i 处的字符串，offsets[i] 指向解压缩后的字节 blob 中该字符串起始位置的偏移量。因此，字符串 i 的长度可以通过 offset[i+1] - offsets[i] 计算得出。（末尾有一个虚拟的额外偏移量，以便我们可以轻松计算最后一个字符串的长度）。下图展示了包含字符串 'Feta'、'Asiago'、''、'Stilton' 和 'Brie' 的块是如何编码的。

包含偏移量数组和字节 blob 的列式存储块，空字符串显示为两个相等的偏移量

为什么词项查询必须解压缩块

现在我们了解了列式格式，让我们回到查询优化。首先，考虑针对查询 foo 的词项查询。我们正在查找给定字符串字段与字符串 foo 精确匹配的文档。那么，我们如何对上述格式的字符串列实现这一点呢？算法很简单：

docId = 0
for chunk in chunks:
    bytes = zstd_decompress(chunk.bytes)
    for i in range(len(chunk.offsets) - 1):
        value = bytes[chunk.offsets[i] : chunk.offsets[i+1]]
        if value == term:
            yield docId
        docId++

瓶颈在于 Zstd 解压缩步骤。但我们对此无能为力；如果我们要检查字节，就必须解压缩这些块。但要记住，我们并不是要优化通用情况，而是在寻找特殊情况。（实际上，你不是仅仅凭空想出特殊情况。这些优化来自于首先运行一个有用的查询，意识到它可以更快，然后寻找改进它的方法。）

将空字符串查询重写为长度检查

我们发现值得改进的一个特殊情况是针对词项 "" 的查询。诚然，这是一个有点傻的词项，但空字符串无处不在。由于它们很少有用，我们通常会用 term != "" 这样的查询将其过滤掉。幸运的是，这是一个我们可以优化的查询。

考虑上述针对空字符串词项的算法。if value == term 这行代码有点奇怪；我们在问“这个值是否等于空字符串？” 我们可以这样做，但没有字节可以比较，因此检查过程如下：

1. 我们只需要知道该值的长度是否为 0。
2. 如果我们只需要长度，就不需要在解压缩后的块中查找该值。
3. 如果我们从不查找值，我们就完全不需要从块中获取任何字节。
4. 如果我们不需要来自块的任何字节，我们就无需解压缩它。

我们所需要的只是长度，而长度存在于偏移量数组中。它也是压缩的，但使用的是廉价的整数压缩，而不是 Zstd，后者要快得多。

有了这个认识，我们可以重写空字符串词项查询。我们需要的新操作是 docValues.loadLength(docId)，它直接从偏移量数组读取，而不触及压缩后的字节。经过前面的例子，这应该看起来很熟悉。最有趣的部分是 TermEqualsQuery.rewrite；它找到了空字符串的特殊情况，并将查询替换为只检查长度的更简单版本。

class TermEqualsQuery(term, docValues):
    boolean matches(docId):
        value = docValues.loadValue(docId)  # 需要 Zstd 解压缩
        return value == term

    Query rewrite():
        if term == "":
            return LengthEqualsQuery(0, docValues)
        return self

class LengthEqualsQuery(queryLen, docValues):
    boolean matches(docId):
        length = docValues.loadLength(docId)  # 仅从偏移量数组读取
        return length == queryLen

对空字符串重写进行基准测试：性能提升 1.6 倍

现在我们来看看效果如何。没有任何纯扫描的 ClickBench 查询像 Q20 之于前一个规则那样直接使用此规则，因此我们自己创建一个。考虑查询：FROM hits | WHERE SearchPhrase != '' | STATS count(*)。在这个查询上，我们看到了 1.6 倍的加速，对于一个相当简单的改动来说，这是一个很大的提升。更好的是，ES|QL 可以直接利用 loadLength。任何 ES|QL 访问字符串的 BYTE_LENGTH 而不需要字符串本身的情况，该请求都会使用这种专门的长度加载方式来避免不必要的解压缩。

一个好的查询重写规则应具备的特征

这里介绍的两条规则遵循相同的模式：识别出查询是一个特殊情况，然后将其替换为更廉价的实现。但它们降低成本的方式不同。

底层的模式值得注意：找到一个性能有待提升的查询，找到一个可以优化的特殊情况，并替换为更便宜的实现。困难的部分在于找到能揭示这些优化机会的查询，然后识别出这些特殊情况。实际的修复通常相对简单，正如这里的两条规则所示。我们在列式模式上的工作提供了许多机会来运行有趣的查询并寻找这类收益。

这也是规则系统可扩展性如此重要的原因。这些规则无法从一开始就构建到数据库中；它们是通过增量发现的过程找到的。Lucene 的重写系统使这变得可行。随着列式模式不断发展以处理新的工作负载，像这样的规则将会不断涌现。