Persistent Index for Segmented Aggregations (PISA)

一、总体设计

1. 设计背景

（1）目前仅使用数据文件中预聚合信息加速聚合查询在文件增多时较为耗时；

（2）乱序数据会破坏预聚合信息的有效性，从而需要读取原始数据，使得查询速度变慢。

2. 设计阶段

（1）本阶段设计：默认分区关闭，即仅有1个分区，每一个序列有一个PISA索引 —— 每个序列有一个索引管理器。

（2）下阶段设计：开启分区后，索引建立在分区内部，不跨分区；每一个序列，每一个分区有一个PISA索引 —— 每个分区、每个序列各有一个索引管理器。

3. 设计目标

（1）使用线段树结构，对于树中的内部节点，不存储节点所覆盖的时间范围的最早或最晚时间戳，而是通过定义节点号和叶子号，避免从磁盘读取不必要的数据，减少聚合查询延迟。

（2）考虑时间序列数据库的应用场景，充分利用顺序数据和乱序数据的特点，在任意时间范围内获取准确的聚合结果，减少乱序数据对于查询速度的干扰。

二、索引的构建

1. 构建时间

（1）memtable flush落盘时，触发索引的构建。每写好一个叶子节点（达到配置或计算的窗口时间长度），就将该节点交给索引管理器。

未写入该叶子结点的“尾巴数据”缓存到内存里，下一个memtable来的时候合并。

（2）用户配置：用户可以配置窗口时间长度t = t_e - t_s

* 注意：开启分区后，用户需要配置“叶子结点个数”（要求为以2为底的幂，如16 = 2⁴），窗口时间长度通过计算得到，假设1个分区为1周（604,800s），则每个窗口长度为37,800s。

2. 构建步骤