探索 GreptimeDB 中的索引技术：优化大规模时序数据查询性能

MinMax 索引基于一个简单的原理：记录每组数据中的最大值和最小值。当查询条件超出这些极值时，该组数据可以被直接排除，避免不必要的扫描。

在 GreptimeDB 的存储结构中，MinMax 索引被应用于两个层次：首先是 Region 级别，这里记录了每个文件的 Timestamp 列的最小值和最大值；其次是文件级别，这里记录了每个 Row Group[^2] 内所有列的最小值和最大值。

当查询条件包含对 Timestamp 的具体要求时，Region 级别的 MinMax 索引能有效地帮助排除不符合时间条件的文件。在文件扫描过程中，文件级的 MinMax 索引可以迅速地判断并跳过那些不满足条件的 Row Group，极大地减少了需要进一步检查的数据行数量。这种策略在实际应用中已被证明能够满足大多数时序数据查询的需求，尤其是当 Tag 列的排序得到恰当安排时，对首个 Tag 列和 Timestamp 列的查询过滤表现出色。

尽管 MinMax 索引在多个场景中表现良好，但仍存在一些局限性：

1. 过滤粒度相对较粗：即使只有极少数数据行满足查询条件，存储引擎还是需要读取整个 Row Group，也就是说，需要处理 102400 行数据。降低 Row Group 的容量可以调细过滤粒度，从而改善这一局面，但这种做法会增加 Row Group 的数量，对元数据管理造成额外压力。

2. 索引过滤能力有限：MinMax 索引在处理排列有序的数据行时，主要优化效果集中在首列。从第二列开始，列值越来越不规则，MinMax 索引的过滤效果逐渐减弱。

为了解决这些问题，GreptimeDB 在 0.7 版本中引入了一种新的索引结构——倒排索引，以弥补 MinMax 索引的不足。

[^2] Row Group：在 GreptimeDB 中，数据文件被划分为称为 Row Group 的结构单元，每个 Row Group 包含 102400 行。

设计文档：

https://github.com/GreptimeTeam/greptimedb/blob/main/docs/rfcs/2023-11-03-inverted-index.md

通过采用倒排索引，GreptimeDB 的存储引擎在减少扫表工作量方面取得了显著进展，特别是在特定查询场景下，查询性能有时能够提升数倍。倒排索引的优势主要体现在两方面：

1. 索引信息更精确：倒排索引为每个 Tag 列记录了该列值在文件中的分布位置；

2. 过滤粒度更细：倒排索引的分布单位是更小的 Segment，其默认大小仅为 1024 行。

相较于 MinMax 索引，倒排索引提供了更细粒度和更高精度的数据过滤能力。我们先看一个应用不同索引带来的性能差异对比，然后介绍倒排索引的实现细节。

本节通过对无索引、MinMax 索引与倒排索引三种状态下的性能展开对比，聚焦于 TSBS single-groupby-5-8-1 场景，下图展示不同索引策略在扫描行数、扫描 Row Group 数量及平均响应时间方面的表现差异。

（图 2：不同索引类型的性能对比）

通过这个图表，我们可以直观地看到不同索引策略的性能差异，其中倒排索引表现最好。

05

倒排索引的详细实现

具体来说，GreptimeDB 的倒排索引是在文件级别建立的，它为文件中的每个 Tag 列构建了独立的索引，从而能够高效地处理针对任意 Tag 列的查询。相较于只在第一个 Tag 列显示显著过滤效果的 MinMax 索引，倒排索引显著扩展了索引的适用范围。此外，倒排索引采用了 FST (Finite State Transducer)^[1] 技术，这是一种将键映射到值的高效数据结构，广泛用于索引构建以实现快速数据检索。FST 支持单点查询、范围查询、正则表达式搜索和模糊搜索等多种操作，使得倒排索引在处理复杂查询时表现出强大能力，并在多种查询场景中展现明显性能优势。

与以 Row Group 为过滤单位的 MinMax 索引不同，倒排索引采用了可调整大小的 Segment，索引粒度的选择直接影响过滤效果和索引存储成本。在控制索引存储成本的前提下，GreptimeDB 将 Segment 大小设置为 1024 行，这一粒度是 Row Group 的百分之一，使得在大多数情况下，倒排索引的查询性能优于 MinMax 索引。

在实际实现中，存储引擎为数据文件中的各个 Tag 列分别构建了从 Tag 列值到 Segment 编号列表的映射。这些映射使用 FST 数据结构，其中列值作为键，而 Segment 编号列表则以位图形式存储作为值。执行查询时，存储引擎通过查询条件搜索 FST，获取 Segment 编号列表，随后仅读取相应的 Segment，极大地减少了需要扫描的数据量。

06

未来展望

组合索引

为了提高涉及多列查询的性能，GreptimeDB 将探索组合倒排索引。这种索引将多个 Tag 列的值合并为一个复合键，从而提供更精确的数据过滤。尽管这会增加构建和存储的成本，但通过按需构建索引，即仅针对频繁使用的列组合创建索引，可以有效控制资源消耗。

全文索引

GreptimeDB 计划引入针对特定列的全文索引，以提供日志场景的查询能力。用户将能够执行基于关键字的搜索，快速定位到日志中的特定条目。

Reference:

[1] https://en.wikipedia.org/wiki/Finite-state_transducer

---

关于 Greptime

Greptime 格睿科技专注于为物联网（如智慧能源、智能汽车等）及可观测等产生大量时序数据的领域提供实时、高效的数据存储和分析服务，帮助客户挖掘数据的深层价值。目前主要有以下三款产品：

GreptimeDB 是一款用 Rust 语言编写的开源时序数据库，具有云原生、无限水平扩展、高性能和融合分析等特点，帮助企业实时读写、处理和分析时序数据的同时，降低长期存储的成本。我们提供 GreptimeDB 企业版，支持更多企业特性和定制化服务，如有需要欢迎联系我们：15310923206（同微信）。

GreptimeCloud 是一款全托管的云上数据库即服务（DBaaS）解决方案，基于开源时序数据库 GreptimeDB 打造，能够高效支持可观测、物联网、金融等领域的应用。用户可以通过内置的可观测性解决方案 GreptimeAI 全面掌握 LLM 应用的成本、性能、流量和安全等情况。

车云一体解决方案 是一款深入车企实际业务场景的时序数据库解决方案，解决了企业车辆数据呈几何倍数增长后的实际业务痛点。多模态车端数据库结合云端 GreptimeDB 企业版帮助车企极大降低流量、计算和存储成本，并帮助提升数据实时性和业务洞察能力。

GreptimeDB 作为开源项目，欢迎对时序数据库、Rust 语言等内容感兴趣的同学们参与贡献和讨论。第一次参与项目的同学推荐先从带有 good first issue 标签的 issue 入手，期待在开源社群里遇见你！扫码添加小助手备注“技术交流群”立即加入讨论吧~

Star us on GitHub Now: 

https://github.com/GreptimeTeam/greptimedb

官网：https://greptime.cn/

文档：https://docs.greptime.cn/

Twitter: https://twitter.com/Greptime

Slack: https://greptime.com/slack

LinkedIn: https://www.linkedin.com/company/greptime/

点击下方链接🔗关注 GreptimeDB，了解更多技术干货👇

往期精彩文章：

👇 点击下方阅读原文，立即体验 GreptimeDB！