Storage indexes

The source notes for this track are currently maintained in Chinese.

预计阅读时间: 45 分钟 前置阅读: doc-06 (Segment 格式), doc-07 (Compaction) 下一次阅读: doc-09 (Catalog)

1. 索引体系概览

Doris 在存储层实现了 6 种内置索引, 每种针对不同的查询模式和列特征。

源码导航

2. ShortKey Index——前缀索引

原理

Doris 按建表时 ORDER BY 指定的列排序存储数据。ShortKey Index 是这些排序键的前缀位置索引。

CREATE TABLE t (dt DATE, city VARCHAR, user_id BIGINT, ...)
ORDER BY (dt, city)  → 数据按 (dt, city) 排序

ShortKey Index (内存中):
  Key "2026-07-01", "BJ" → offset in Segment = 0
  Key "2026-07-01", "SH" → offset in Segment = 4096
  Key "2026-07-02", "BJ" → offset in Segment = 8192
  Key "2026-07-02", "GZ" → offset in Segment = 12288
  ...

查询: WHERE dt='2026-07-02' AND city='BJ'
  → ShortKey 定位: 找 "2026-07-02", "BJ" → offset 8192
  → 读取: 从 offset 8192 开始读少量 Page

源码

限制

• 只能按 ORDER BY 列的前缀顺序使用 (最左前缀匹配)
• 如果查询跳过 ORDER BY 的第一列 → ShortKey 不生效
• 物理限制: ShortKey 有大小限制 (通常 36 bytes), 超出的 key 不索引

3. ZoneMap Index——Min/Max/Null 索引

原理

每个 Segment 的每个 Page 自动记录该 Page 中每列的 Min/Max/HasNull。查询时, 如果查询谓词 (如 a > 100) 与 Page 的 ZoneMap 无交集 (如该 Page 的 a_max = 50), 则跳过该 Page。

Segment Page 0 的 ZoneMap:
  dt: [min=2026-07-01, max=2026-07-03]
  city: [min="BJ", max="SH"]
  amount: [min=0, max=500]

查询: WHERE amount > 1000
  → ZoneMap[amount_max=500] < 1000 → 无交集 → SKIP 整个 Page
  这个 Page 的内部 4096 行完全不需要读

源码

局限

• ZoneMap 只能过滤范围谓词 (>, <, BETWEEN), 不能过滤等值
• 高基数列 (如 user_id) 的 Min/Max 往往跨越整个数据范围, ZoneMap 过滤率低

4. Ordinal Index——页级定位

原理

Ordinal Index 记录每列每个 Page 的起始 ordinal (行号)和文件 offset 的映射。

Column `amount` (Int64) — Ordinal Index:
  Page 0: ordinal [0, 4096) → file offset 1024
  Page 1: ordinal [4096, 8192) → file offset 524288
  Page 2: ordinal [8192, 12288) → file offset 1048576

查询: 需要 ordinal 5000 (第 5000 行)
  → Binary Search Ordinal Index → Page 1
  → 读取 offset 524288 → 解析 Page 1
  → 从 ordinal 5000-4096=904 开始读

源码

5. BloomFilter Index——高基数等值过滤

原理

用户在建表时可指定对某列创建 BloomFilter 索引。写入时为每个 Rowset 生成该列的 BloomFilter(包含所有值), 查询时快速判断一个值是否可能存在。

Rowset 0 的 city 列 BloomFilter:
  Hash space: 1024 bits
  Insert("BJ") → set bits [142, 389, 756]
  Insert("SH") → set bits [45, 678, 901]
  ...

查询: WHERE city='GZ'
  → Check BloomFilter: bits[45, 234, 890] → bit 45=1, bit 234=1, bit 890=0
  → NOT ALL bits set → 'GZ' 不在这个 Rowset 中 → SKIP

查询: WHERE city='BJ'
  → Check BloomFilter: bits[142, 389, 756] → 全部 set
  → 'BJ' 可能在这个 Rowset 中 → 读 Rowset 检查

参数

• fpp (False Positive Probability, 误报率): 默认 0.05 (5%)
• 空间 = -N * ln(fpp) / (ln 2)^2 bits (N = distinct values)
• FPP 越低 → 空间越大, 但过滤越准

源码

6. Bitmap Index——低基数列

原理

为列的每个 distinct value 创建独立的 Bitmap(每行 1 bit), 查询时用 Bitmap 的 AND/OR 快速定位符合条件的行。

city 列 (低基数: 3 distinct values):
  BJ → Bitmap:  1 0 1 0 0 1 0 0  (rows 0, 2, 5)
  SH → Bitmap:  0 1 0 1 0 0 1 1  (rows 1, 3, 6, 7)
  GZ → Bitmap:  0 0 0 0 1 0 0 0  (row 4)

查询: WHERE city IN ('BJ', 'SH')
  → Bitmap(BJ) OR Bitmap(SH) = 1 1 1 1 0 1 1 1
  → 读 rows {0,1,2,3,5,6,7}, 跳过 row 4

使用建议

• 列基数 < 1000 → Bitmap 非常有效 (紧凑, 快速)
• 列基数 > 10000 → Bitmap 空间膨胀, 不如 BloomFilter
• 适用于等值/IN 查询, 不适用于范围查询

源码

7. Inverted Index——全文搜索

原理

倒排索引: 对文本列分词(或 n-gram), 为每个 token 建立倒排列表(包含该 token 的所有行号), 查询时用倒排列表取交集。

comment 列 (文本):
  "hello world" → tokens: [hello, world] → {row 0}
  "hello doris" → tokens: [hello, doris] → {row 1}
  "doris is fast" → tokens: [doris, is, fast] → {row 2}

查询: WHERE comment MATCH 'doris'
  → Inverted Index: "doris" → rows {1, 2}
  → 只读这两行

源码

8. 索引过滤效能与存储开销

9. 索引过滤层次 (执行顺序)

查询: SELECT * FROM t WHERE dt='2026-07-08' AND city='BJ' AND comment MATCH 'doris'

1. PartitionPruning  (FE, 跳过不匹配的分区)
2. ShortKey          (BE, 定位到 [dt='2026-07-08', city='BJ'] 的 Segment 位置)
3. ZoneMap           (BE, 检查 Segment Page 的 dt_min/dt_max 是否有交集)
4. BloomFilter       (BE, 检查 city='BJ' 是否可能在该 Rowset)
5. Bitmap/Inverted   (BE, 用倒排索引定位 comment 中含 'doris' 的行位置)
6. DataPage Reading  (BE, 只读通过所有索引过滤后的行)

10. 常见问题 / 面试题

Q1: 什么列应该建 BloomFilter? 什么列应该建 Bitmap? A: BloomFilter → 高基数列 (user_id, order_id), 等值查询, 空间效率好。Bitmap → 低基数列 (status, city, gender), 等值/IN 查询, 速度快。规则: distinct < 1000 → Bitmap; distinct > 10000 → BloomFilter。

Q2: ShortKey 的设计为什么有 36 bytes 限制? A: ShortKey 是内存索引, 越大 → 每个 Segment 占用内存越多。36 bytes 限制保证了在极端场景下 (百万 Tablet) BE 内存可控, 且覆盖了大部分常见前缀(日期+城市+ID)的组合。

Q3: ZoneMap 如何决定一个 Page 是否需要读取? A: 编码后的值比较: (query_min <= page_max) AND (query_max >= page_min) → 有交集 → 读。如果 (query_min > page_max) 或 (query_max < page_min) → 无交集 → 跳过。

下一步

• 元数据: doc-09-catalog-journal.md——Catalog 如何管理这些索引的表定义