Parquet 页面索引（Page Index）

本文档描述了 Parquet 文件页脚中的列索引（Column Index）页面格式。这些页面包含数据页（DataPages）的统计信息，并可用于在扫描有序或无序列数据时跳过不相关的页面，从而提高查询效率。

问题描述

在先前的 Parquet 格式版本中，统计信息（Statistics）存储在 ColumnMetaData（用于 ColumnChunk）和 DataPageHeader（用于单个页面）中。在读取数据时，读取器需要解析数据页的页头（Page Header），以判断该页面是否可以被跳过。这意味着读取器必须访问列中的所有页面，从而导致大量不必要的数据读取。

目标

提升范围扫描（Range Scan）和点查询（Point Lookup）的 I/O 效率，使其能够直接访问符合条件的页面：
- 在基于排序列的单行查找中，每个检索的列最多只需要读取一个数据页。
- 对于基于排序列的范围扫描，仅需读取包含相关数据的精确数据页。
- 其他选择性扫描也应具备 I/O 高效性。例如，对于一个非排序列上的高度选择性谓词（Selective Predicate），对于其他需要检索的列，只需访问包含匹配行的数据页。
无额外解码开销，适用于无选择性谓词（Selective Predicate）的扫描，例如整行组（Row Group）扫描。如果读取器确定不需要索引数据，则不会产生额外的 I/O 负担。
优化排序列索引页的存储空间，仅存储页面之间的边界值，以减少存储占用。

非目标

不支持 类似于 二级索引（Secondary Index） 的功能，即不提供针对非排序数据的按键值排序的索引结构。

技术方案

在 Row Group 的元数据中增加两种新的列级结构： 1. ColumnIndex（列索引）： * 允许基于列值导航到数据页，以定位满足查询谓词的页面。 2. OffsetIndex（偏移索引）： * 允许基于行索引（Row Index）导航，以便检索符合 ColumnIndex 条件的匹配行的值。 * 当某一列的某些行被跳过时，其他列的对应行也需要被跳过，因此同一 Row Group 中的 OffsetIndex 会一起存储。

这些索引结构与 Row Group 分开存储，靠近文件页脚（Footer），这样读取器在 非选择性扫描 时，无需承担额外的 I/O 读取和反序列化开销。索引结构的存储位置和长度会记录在 ColumnChunk 中。

页面索引布局

设计要点

边界优化：
- 无需记录第一页的下界（Lower Bound）和最后一页的上界（Upper Bound），因为行组级别的统计信息已经提供了这些值。
- 但为了保持一致性，仍然存储这些边界值，其开销可以忽略不计。
存储优化：
- 每个数据页存储 min_values（最小值）和 max_values（最大值）。这些值可以是页面内实际的最小和最大值，也可以是更紧凑的代理值。例如： text 实际值："Blart Versenwald III" 索引存储：min_values[i] = "B" max_values[i] = "C"
- 这样，写入器可以截断过长的值，并强制对索引结构的大小施加合理的上限。
避免重复统计计算：
- 支持 ColumnIndex 的读取器不应再使用 数据页级别的统计信息。
- 唯一需要在写入 ColumnIndex 时仍然写入数据页统计信息的情况，是为了兼容旧版读取器（不推荐）。

数据查找优化

有序列（Ordered Columns）
- 读取器可通过 二分查找（Binary Search） 在 min_values 和 max_values 中快速定位匹配的数据页。
无序列（Unordered Columns）
- 读取器需要顺序扫描（Sequential Scan） min_values 和 max_values 以找到匹配的数据页。
范围扫描（Range Scan）优化
- 该方法可以扩展为返回行范围、数据页索引及数据页偏移量，以便在每一列中扫描特定范围的数据。
- 读取器可以为每个列初始化扫描器，并直接跳转到扫描的起始行，从而减少不必要的读取。

索引计算依据

min_values 和 max_values 是基于 FileMetaData 结构体中的 column_orders 字段计算的，该字段定义了列的排序方式（升序、降序或未排序）。