超越 Filter Rewrite：OpenSearch Doc Value Skip Index 如何让聚合查询快 28 倍

原文：https://opensearch.org/blog/beyond-filter-rewrite-how-doc-value-skip-indexes-accelerate-aggregations-in-opensearch/ 作者：Ankit Jain, Asim Mahmood (AWS/OpenSearch 团队)

前言

在之前的博客中，我们介绍了如何通过 Filter Rewrite 和多范围遍历技术，利用 Lucene 的 BKD 树实现高达 100 倍的日期直方图聚合性能提升。这些技术效果显著，但有一个根本限制：要求查询过滤字段和聚合字段必须是同一个，且无法支持复杂的子聚合逻辑。当过滤字段和聚合字段不同时，或者子聚合需要逐文档计算时，查询引擎只能退回到逐个扫描文档的传统方式。

本文将介绍如何通过 Lucene 10 的 Doc Value Skip Index 克服这些限制，即使过滤字段和聚合字段不相关，也能实现最高 28 倍 的聚合性能提升。

Filter Rewrite 的局限性

Filter Rewrite 将日期直方图聚合转换为一系列范围过滤器，然后使用 Lucene 的 BKD 树（Points 索引）来统计每个桶的文档数量，无需访问单个文档值。多范围遍历进一步优化了这一点，通过单次有序遍历处理所有桶。

这两种技术都依赖一个关键假设：查询中用于过滤的字段就是被聚合的字段。

问题场景

考虑以下查询，它在 trip_distance 上过滤，但在 dropoff_datetime 上聚合：

{
  "size": 0,
  "query": {
    "range": {
      "trip_distance": {
        "gte": 0,
        "lte": 20
      }
    }
  },
  "aggs": {
    "dropoffs_over_time": {
      "date_histogram": {
        "field": "dropoff_datetime",
        "calendar_interval": "month"
      }
    }
  }
}

由于 trip_distance 和 dropoff_datetime 是不同的字段，trip_distance 的 BKD 树无法提供 dropoff_datetime 值在各桶中分布的信息。引擎无法将聚合重写为对聚合字段的范围过滤器，只能退回到传统方法：遍历每个匹配的文档，获取其 dropoff_datetime 文档值，然后放入正确的桶中。

同样，当子聚合需要逐文档计算时（例如计算每个时间桶内的平均值），Filter Rewrite 也无能为力，因为它只提供文档计数，无法访问单个字段值。

这些并非边缘情况。在实际分析查询中，很多场景是在一个维度上过滤，在另一个维度上聚合，子聚合在仪表板和报表中也很常见。我们需要一种更通用的方法。

Doc Value Skip Index：聚合引擎的新工具

从 Lucene 10.0 开始，一种新的索引结构可用：数值文档值上的可选 Skip Index，在 PR #13449 中引入，并在 PR #13563 中增加了多级支持。该结构通过 DocValuesSkipper 抽象暴露，为本文描述的优化提供了基础。

什么是 Skip Index？

在计算机科学中，跳表（Skip List）是一种概率数据结构，通过在有序数据上分层多个级别的链表，使用随机化决定哪些元素出现在更高层，从而提供期望 O(log n) 的搜索时间。

Lucene 的 Doc Value Skip Index 借用了多级概念，但完全是确定性的。它不使用随机化，而是在段创建时将文档划分为固定大小的区间，并在编译时构建摘要级别的层次结构。没有随机性：该结构完全由文档计数和配置的区间大小决定。

类比理解：就像书的目录。不需要逐页扫描来找到所需内容，先查看章标题，然后是节标题，最后缩小到具体页面。Skip Index 的工作原理相同：它让聚合引擎在决定是否检查单个值之前，先检查大块文档的摘要元数据。

Lucene 如何实现 Skip Index

Lucene 的实现使用最多 4 层（level 0-3）的层次结构。基础层（level 0）以 4,096 个文档为区间进行摘要。每个后续层聚合下一层的 8 个区间（2^3 的偏移），如下表所示：

对于最坏情况下有 2^31 - 1（约 21 亿）个文档的索引，Skip Index 层次结构在 level 0 约有 524,288 个条目，level 1 有 65,536 个，level 2 有 8,192 个，level 3 有 1,024 个。因此，搜索空间从数十亿个文档减少到仅需几千次元数据检查。

每个区间条目非常紧凑（仅 29 字节），编码以下元数据：

• 级别数（1 字节）：该条目包含在多少个级别中
• 最小值和最大值（16 字节）：该区间内字段值的范围
• 最小和最大文档 ID（8 字节）：该区间的文档 ID 边界
• 文档计数（4 字节）：该区间内的文档数量

这些元数据使聚合引擎能够对每个区间做出三种决策：

1. 如果区间的最小/最大值完全在当前聚合桶之外，跳过整个区间
2. 如果区间的最小/最大值完全在单个桶内，批量计数所有文档，无需单独检查
3. 如果区间跨越多个桶，退回到逐个处理文档

遍历从最高可用级别开始，仅在需要时下降，类似于之前优化中 BKD 树遍历跳过整个子树的方式。关键区别在于该结构操作的是文档值而非 Points 索引，因此无论查询过滤哪个字段都有效。

Skip Index 如何解决 Filter Rewrite 的局限性

回顾我们确定的两个主要限制：

1. 不相关字段：Filter Rewrite 要求过滤字段和聚合字段相同
2. 复杂子聚合：Filter Rewrite 只提供计数；无法支持桶内的逐文档计算

Skip Index 解决了这两个限制，因为它直接操作聚合字段的文档值，独立于匹配文档集的产生方式。查询引擎首先评估查询（使用适合过滤字段的索引）以产生一组匹配的文档 ID。然后，在聚合期间，它查询聚合字段的 Skip Index，以确定这些匹配文档的块是否可以跳过或批量计数。

这种解耦是关键洞察。Skip Index 不关心文档集是否被过滤过，它只需要知道聚合字段的值在每个区间内的分布情况。

示例

例如，考虑一个在 process.name 上过滤（词项过滤器）并在 @timestamp 上聚合（按天分桶的日期直方图）的查询：

GET /logs-*/_search
{
  "query": {
    "bool": {
      "must": [
        {
          "range": {
            "@timestamp": {
              "gte": "2024-01-01",
              "lte": "2024-01-31"
            }
          }
        },
        {
          "term": {
            "process.name": "systemd"
          }
        }
      ]
    }
  },
  "aggs": {
    "daily_counts": {
      "date_histogram": {
        "field": "@timestamp",
        "calendar_interval": "day"
      }
    }
  }
}

没有 Skip Index 时，@timestamp 上的范围查询可能受益于 Filter Rewrite，但 process.name 上的词项过滤器阻止了查询被重写。引擎必须遍历匹配两个条件的每个文档，并单独检索每个 @timestamp 值。

启用 @timestamp 的 Skip Index 后，聚合引擎可以在收集期间查询 Skip Index。当它遇到一个区间，其中最小和最大 @timestamp 值都落在同一个日桶内时，它会批量计数该区间中所有匹配的文档，无需查找单个值。这可以将总查找次数减少约 85%。

使用 Popcount 高效计数

批量计数步骤有一个值得探讨的细节。当 Skip Index 表明区间内的所有值都落在单个桶内时，我们知道批量计数是可能的；然而，我们不能直接使用区间的文档计数。Skip Index 覆盖段中的所有文档，但查询产生的 DocIdSetIterator 只代表匹配查询过滤器的文档子集。我们需要计算该过滤子集中有多少文档落在 Skip Index 区间内。

一种方法是逐个遍历迭代器，边遍历边计数。但这违背了跳过的大部分目的。相反，我们使用硬件级优化：popcount（人口计数）CPU 指令，它可以在单次操作中计算机器字中设置位的数量。

当查询引擎产生 DocIdSetIterator 时，它通常在内部将匹配文档集表示为位集，其中每个位对应一个文档 ID，如果文档匹配查询则设置为 1。要计算 Skip Index 区间内有多少匹配文档，我们提取该位集的相关部分（对应区间内最小/最大文档 ID 范围内的位），并对这些字应用 popcount。这给出了区间内的精确匹配文档数，无需逐个遍历。

DocIdSetIterator 还支持批量收集接口：收集器可以接收文档 ID 流，而不是重复调用 nextDoc()。当流中的所有文档 ID 都落在同一个桶内时（由 Skip Index 确定），整个流可以在一次操作中收集。初步基准测试显示，这种方法在 Skip Index 收益的基础上可额外带来最高 3 倍 的提升。

有序数据：Skip Index 的最佳场景

当文档按聚合字段排序时，Skip Index 发挥最佳性能。数据有序时，连续文档具有相似或单调递增的值，意味着每个 4,096 文档区间内的最小/最大范围较窄。窄范围更有可能完全落在单个聚合桶内，最大化批量计数的机会。

对于时序工作负载（日志分析、指标和可观测性），时间戳字段是自然的选择。大多数时序数据大致按时间顺序到达，OpenSearch 中的数据流保持这种顺序。

确保数据保持有序

仅仅有时间戳字段并不能保证数据在段合并和文档添加时保持有序。有两种方法可以保持排序：

1. Index Sort（推荐）：配置显式的索引排序设置，确保无论段如何合并，数据都保持排序：

{
  "settings": {
    "index.sort.field": "@timestamp",
    "index.sort.order": "desc"
  }
}

这保证所有段保持时间戳顺序，提供一致的 Skip Index 性能。

2. Log Merge Policy：或者，使用保留传入文档顺序的合并策略。log_byte_size 合并策略倾向于保持时序数据典型的仅追加工作负载的时间顺序。

当数据无序时，Skip Index 仍然可以正常工作，但提供较少的跳过和批量计数机会，因为每个区间的最小/最大范围可能跨越多个桶。

启用 Skip Index

Skip Index 可以根据 OpenSearch 版本自动启用或通过手动配置启用。

按版本的默认行为

手动配置

要在其他数值字段上启用 Skip Index，请在字段映射中添加 skip_list 参数：

PUT /my-index
{
  "mappings": {
    "properties": {
      "custom_timestamp": {
        "type": "date",
        "skip_list": true
      },
      "price": {
        "type": "long",
        "skip_list": true
      }
    }
  }
}

性能测试结果

我们使用 OpenSearch Benchmark 和 http_logs 及 big5 数据集测量了性能。结果显示了显著改进，特别是对于 Filter Rewrite 之前无法帮助的查询。

日期直方图性能（http_logs 工作负载）

基于 PR #19130 使用 http_logs 数据集的测试：

第一个操作展示了 Skip Index 在纯计数聚合与不相关过滤器上的全部优势。第二个操作包含子聚合（指标），改进较小，因为逐文档指标计算仍然需要指标字段的单个值查找。

日期直方图查询的吞吐量提高了 21%，对索引性能没有可测量的影响。

自动日期直方图性能（big5 工作负载）

OpenSearch 3.4 将 Skip Index 优化扩展到自动日期直方图聚合。基于 PR #20057 使用 big5 数据集的测试：

这些结果结合了范围查询的 Filter Rewrite 优化和自动日期直方图的 Skip Index，展示了两种技术如何互补。

索引大小影响

Skip Index 引入的存储开销极小：

由于这种极小的开销，OpenSearch 默认只在 @timestamp 字段上启用 Skip Index，在不显著增加存储成本的情况下提供针对性收益。

总结

Doc Value Skip Index 是 OpenSearch 聚合引擎的重要进步，解决了 Filter Rewrite 的根本限制。通过在文档值上构建多级摘要结构，它实现了：

• 不相关字段的聚合优化：过滤字段和聚合字段可以不同
• 子聚合支持：即使需要逐文档计算也能受益
• 最高 28 倍性能提升：在合适的场景下
• 极低存储开销：仅增加约 0.1%-1% 的存储

对于时序数据和分析工作负载，这是一个值得启用的强大优化。

原文作者：Ankit Jain（Amazon OpenSearch Service 软件工程师，Apache Lucene 和 OpenSearch 活跃维护者）、Asim Mahmood（AWS 高级软件工程师）