背景
在 IoTDB 中,聚合查询可以使用 GROUP BY
子句指定按照时间区间分段聚合。用户可以指定聚合的时间间隔和滑动步长,相关参数如下:
- 参数 1:整体的时间窗口。
- 参数 2(interval):划分时间轴的时间间隔参数(> 0)。
- 参数 3(slidingStep):滑动步长(可选,默认值与时间间隔相同)。
在之前的定义中,滑动步长必须大于等于时间间隔,现在拟支持滑动步长小于时间间隔的情况。
设计思路
根据时间间隔和滑动步长将整体的时间窗口划分成若干预聚合窗口,对预聚合窗口内的数据进行聚合(调用之前的接口即可)。将这些预聚合值维护在一个队列中,根据这些预聚合值求出每个聚合窗口的聚合值。
算法过程
预聚合窗口划分
若 interval >= slidingStep,预聚合窗口等于聚合窗口。
若 interval < slidingStep,预聚合窗口由各个聚合窗口的边界划分而成。
例:整体时间窗口为 [0, 32),数据如下,灰色单元格表示对应时间戳没有数据。
interval = slidingStep = 4,预聚合窗口即为聚合窗口。
interval = 4,slidingStep = 5,预聚合窗口即为聚合窗口。
interval = 4,slidingStep = 6,预聚合窗口即为聚合窗口。
interval = 4,slidingStep = 1,预聚合窗口大小为 1。
interval = 4,slidingStep = 2,预聚合窗口大小为 2。
interval = 4,slidingStep = 3,预聚合窗口大小为 3 -> 1 -> 2 -> 1 -> 2 -> ……
根据预聚合结果计算聚合值
对于不同的聚合函数,按照其特点有不同的处理方式,可以分为三组:
- SUM、COUNT、AVG:将当前聚合窗口内的预聚合值缓存在队列中,更新队列时同时更新聚合值。
- MAX_VALUE、MIN_VALUE、EXTREME:在上述算法的基础上,使用单调队列进行优化(LEETCODE-239)。
- 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。
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 = 2。每个预聚合窗口大小为 2。
下面演示各种聚合函数的计算过程:
实现细节
- 时间窗口管理: 为方便管理时间窗口,可以实现一个工具类
TimeRangeIterator
迭代预聚合窗口。 - 预聚合值计算:
- 不带值过滤:比较简单,每个预聚合窗口的聚合值计算可以直接调用
GroupByExecutor
接口的List<AggregateResult> calcResult(long curStartTime, long curEndTime)
得到。 - 带值过滤:考虑梳理出一个类似于不带值过滤的计算接口。
- 不带值过滤:比较简单,每个预聚合窗口的聚合值计算可以直接调用
- 预聚合值处理: 在
GroupByEngineDataSet
类中维护队列,完善nextWithoutConstraint()
的执行逻辑。 - 对于不同类型的聚合函数的处理: 实现数据结构
SlidingWindowAggrQueue
,根据聚合函数类型对队列进行不同策略的管理。 - 内存管理: 在最差情况下,队列中需要缓存窗口内全部的原始数据,对内存造成压力。这里参考 UFTF 框架 的内存管理 —— 实现
ElasticSerializableQueue
作为SlidingWindowAggrQueue
内缓存值的队列。 - 兼容现有 GROUP BY: interval >= slidingStep,预聚合窗口等于聚合窗口,每次无需缓存,直接返回预聚合结果即可。
- 兼容 UDAF: 在 UDAF 中,特别地,有返回一个窗口内全部原始数据的需求(如计算方差)。此时可以将预聚合窗口大小设置为 1,增加表示返回原始数据的聚合类型(如
original
),此时队列中保存的就是窗口内全部的原始数据。