Page History

## 背景

在 IoTDB 中，聚合查询可以使用 `GROUP BY` 子句指定按照时间区间分段聚合。用户可以指定聚合的时间间隔和滑动步长，相关参数如下：

- 参数 1：整体的时间窗口。
- 参数 2（interval）：划分时间轴的时间间隔参数（> 0）。
- 参数 3（slidingStep）：滑动步长（可选，默认值与时间间隔相同）。

![img](https://user-images.githubusercontent.com/16079446/69109512-f808bc80-0ab2-11ea-9e4d-b2b2f58fb474.png)

在之前的定义中，滑动步长必须大于等于时间间隔，现在拟支持滑动步长小于时间间隔的情况。

## 设计思路

根据时间间隔和滑动步长将整体的时间窗口划分成若干**预聚合窗口**，对预聚合窗口内的数据进行聚合（调用之前的接口即可）。将这些预聚合值维护在一个队列中，根据这些预聚合值求出每个**聚合窗口**的聚合值。

## 算法过程

### 预聚合窗口划分

若 interval >= slidingStep，预聚合窗口等于聚合窗口。

若 interval < slidingStep，预聚合窗口由各个聚合窗口的边界划分而成。

例：整体时间窗口为 [0, 32)，数据如下，灰色单元格表示对应时间戳没有数据。

![image-20220228143336135](C:\Users\喵辉\AppData\Roaming\Typora\typora-user-images\image-20220228143336135.png)

- interval = slidingStep = 4，预聚合窗口即为聚合窗口。

  ![image-20220228143654660](C:\Users\喵辉\AppData\Roaming\Typora\typora-user-images\image-20220228143654660.png)

- interval = 4，slidingStep = 5，预聚合窗口即为聚合窗口。

  ![image-20220228145814578](C:\Users\喵辉\AppData\Roaming\Typora\typora-user-images\image-20220228145814578.png)

- interval = 4，slidingStep = 6，预聚合窗口即为聚合窗口。

  ![image-20220228145828123](C:\Users\喵辉\AppData\Roaming\Typora\typora-user-images\image-20220228145828123.png)

- interval = 4，slidingStep = 1，预聚合窗口大小为 1。

  ![image-20220228144929175](C:\Users\喵辉\AppData\Roaming\Typora\typora-user-images\image-20220228144929175.png)

- interval = 4，slidingStep = 2，预聚合窗口大小为 2。

  ![image-20220228144946158](C:\Users\喵辉\AppData\Roaming\Typora\typora-user-images\image-20220228144946158.png)

- interval = 4，slidingStep = 3，预聚合窗口大小为 3 -> 1 -> 2 -> 1 -> 2 -> ……

  ![image-20220301100725363](C:\Users\喵辉\AppData\Roaming\Typora\typora-user-images\image-20220301100725363.png)

### 根据预聚合结果计算聚合值

对于不同的聚合函数，按照其特点有不同的处理方式，可以分为三组：

- SUM、COUNT、AVG：将当前聚合窗口内的预聚合值缓存在队列中，更新队列时同时更新聚合值。
- MAX_VALUE、MIN_VALUE、EXTREME：在上述算法的基础上，使用单调队列进行优化（[LEETCODE-239](https://leetcode-cn.com/problems/sliding-window-maximum/solution/)）。
- FIRST_VALUE、LAST_VALUE、MAX_TIME、MIN_TIME：顺序遍历时，LAST_VALUE 和 MAX_TIME 的聚合值总出现在右边界的预聚合值，因此中间结果无需缓存。反之，逆序遍历时，FIRST_VALUE 和 MIN_TIME 的预聚合值无需缓存。

时间复杂度：O(n + m)，m 为预聚合窗口的数量。

空间复杂度：Q(k)，k 为每个聚合窗口中预聚合窗口的数量。

例：整体时间窗口为 [0, 32)，序列 `root.sg1.d1.s1` 的数据情况如下，灰色单元格表示对应时间戳没有数据，临近相同颜色的单元格表示来自同一个 BatchData。

![image-20220228150140717](C:\Users\喵辉\AppData\Roaming\Typora\typora-user-images\image-20220228150140717.png)

**CASE**: 执行：`SELECT sum(s1), max_value(s1), last_value(s1), min_time(s1) FROM root.sg1.d1 GROUP BY ([0,32),8ms,2ms)`

解析 SQL 后得到参数，startTime = 0，endTime = 32，interval = 8，slidingStep = 6。每个预聚合窗口大小为 2。

下面演示各种聚合函数的计算过程：

![image-20220301110719894](C:\Users\喵辉\AppData\Roaming\Typora\typora-user-images\image-20220301110719894.png)

![image-20220301134034431](C:\Users\喵辉\AppData\Roaming\Typora\typora-user-images\image-20220301134034431.png)

## 实现细节

- **时间窗口管理：** 为方便管理时间窗口，可以实现一个工具类 `TimeRangeIterator` 迭代预聚合窗口。
- **预聚合值计算：**
  - 不带值过滤：比较简单，每个预聚合窗口的聚合值计算可以直接调用 `GroupByExecutor` 接口的 `List<AggregateResult> calcResult(long curStartTime, long curEndTime)` 得到。
  - 带值过滤：考虑梳理出一个类似于不带值过滤的计算接口。
- **预聚合值处理：** 在 `GroupByEngineDataSet` 类中维护队列，完善 `nextWithoutConstraint()` 的执行逻辑。
- **对于不同类型的聚合函数的处理：** 实现数据结构 `SlidingWindowAggrQueue`，根据聚合函数类型对队列进行不同策略的管理。
- **内存管理：** 在最差情况下，队列中需要缓存窗口内全部的原始数据，对内存造成压力。这里参考 [UFTF 框架](https://cwiki.apache.org/confluence/pages/viewpage.action?pageId=165220355) 的内存管理 —— 实现 `ElasticSerializableQueue` 作为 `SlidingWindowAggrQueue` 内缓存值的队列。
- **兼容现有 GROUP BY：** interval >= slidingStep，预聚合窗口等于聚合窗口，每次无需缓存，直接返回预聚合结果即可。
- **兼容 UDAF：** 在 UDAF 中，特别地，有返回一个窗口内全部原始数据的需求（如计算方差）。此时可以将预聚合窗口大小设置为 1，增加表示返回原始数据的聚合类型（如 `original`），此时队列中保存的就是窗口内全部的原始数据。