窗口函数是什么

• Oracle称为分析函数，PostgreSQL也叫窗口函数，还有一种叫法称之为开窗函数

• Oracle对窗口函数的定义为：窗口函数与聚集函数类似，计算总是基于一组行的集合，不同的是，聚集函数一组只能返回一行，而窗口函数每组可以返回多行！对于组内的每一行，可以想象成有一个滑动窗口，组内每一行都基于自己的滑动窗口作相应的逻辑计算，并且窗口既可以是基于物理行的偏移，也可以是基于逻辑值的偏移。更多细节可以阅读Oracle官方文档：https://docs.oracle.com/cd/E11882_01/server.112/e41084/functions004.htm#SQLRF06174

• 语法：
  Select function（expr）over (partition by expr1,expr2… order by expr3,expr4… 
rows between 1 preceding and 2 following) from tbl;
  这条sql的语义为：将tbl表按expr1等一系列表达式分组，组内按expr3，expr4等一系列表达式排序，之后定义每一行的滑动窗口为往上偏移1行，往下偏移2行，最后每一行基于自己的滑动窗口计算function（expr）的值。

• 简单示例：
  Select c1,c2,c3, sum（c3）over (partition by c1 order by c2 rows
between 1 preceding and 2 following) from tbl;
  
  完整查询结果：
  
  如果能看懂每一行sum值是怎么来的，说明你对窗口函数的理解已经到达85.34574%了

窗口函数怎么用

• 从上面的例子中也可以看出，分区键 + 排序键 + 窗口共同定义了滑动窗口，基于这个滑动窗口 + 自定义函数， 我们可以做很多单条SQL难以实现的功能。对于某些场景，如果没有窗口函数，SQL写起来会很头疼，一般都是采用“曲线救国”的方式规避，比如：

• 一条带子查询或join的复杂sql

• 一条sql + 业务代码手动过滤计算

• 多条sql
  

• 这里我先以OceanBase内部Schema模块在发内部SQL请求的痛点举例
  OceanBase的表格Schema是多版本的，DDL变更统一记录到一张__all_table_history表中，主键是tenant_id, table_id, schema_version, 每张表的一个版本的Schema对应一条记录 ， 有一个需求是获取所有表最大版本的Schema
  直观上SQL可以这么写:
  select * from __all_table_history where (tenant_id, table_id, schema_version) in
(select tenant_id, table_id, max(schema_version) from __all_table_history 
group by tenant_id, table_id);
  这条SQL可以实现需求，但问题在于，由于OceanBase当时的版本对子查询的in优化还不够，外层的查询并不会走索引
  所以在当时SQL引擎优化并不充分的历史条件下，内部SQL是这么写的：
  select * from __all_table_history order by tenant_id, table_id, schema_version desc; 
  是的，然后惨绝人寰的在内核代码里每张表只取第一次出现的记录，也就是手动过滤多余的数据！
  有了窗口函数，现在可以这么干了：
  select tenant_id,table_id,schema_version from
(select __all_table_history.*, row_number() over (partition by tenant_id, table_id 
order by schema_version desc) as rn from __all_table_history) a where a.rn = 1;
  把a.rn = 1换成 a.rn <= n就可以求前n个版本的Schema了，非常方便！

• 以下例子可能场景比较奇怪，但不妨碍我们感受窗口函数的强大
  create table score_tbl(class int, student int, score number, 
primary key(class, student)); 
  求每个学生班里分数与自己分数最接近的前后各一位同学包括自己一共三个人的总分
  select sum(score) over (partition by class, order by score desc 
rows between 1 preceding and 1 following) from score_tbl;
  rows属于物理偏移, 所有行的虚拟窗口大小是固定的, 还存在一种逻辑偏移range, range实际上是逻辑偏移, 即按value进行偏移, 这种模式下, 不同行的滑动窗口大小实际是不同的, 有了range，就可以求解更复杂的问题，比如：
  求每个学生班里分数与其分差在10分以内的同学(包含自己)的总分
  select sum(score) over (order by score desc range 
between 10 preceding and 10 following) from score_tbl;
  求每个学生班里分数比自己高10~20分的同学的总分
  select sum(score) over (order by score desc range
between 20 preceding and 10 preceding) from score_tbl; 
  只需要把sum函数换成其他函数就可以实现其它语义，如平均数，中位数, 方差...

OceanBase的窗口函数

• 初衷
  某业务中有如下用法：
  Select * from (Select c1, c2, c3, row_number() over(partition by c1, c2 order by c4) as rn from table) a where a.rn = 1;
  子查询里就用到了窗口函数。本着尽量不让业务修改代码的原则，OceanBase肯定是要全面兼容这种高级SQL用法的。

• 目前已兼容的点
  

• 支持完整的partition by, order by语义

• 支持完整的rows窗口语法

• 支持row_number, max函数

• 实现难点
  实际上，实现窗口函数的主要工作在于窗口框架，只要执行层抽象出滑动窗口，函数的计算其实非常套路。语法上， 窗口的定义非常灵活，从Oracle的语法图就可见一斑：
  

  以上造成窗口的定义是很复杂的，即如果我们把窗口抽象成upper与lower，待计算的行current_row，upper, lower, current_row三者之间可以是任意的位置关系，因此可以有3！= 6种排列组合，最初实现时发现，复杂度大不说，理解难度也非常大，如果尽可能在语法语义层抽象，将大大减少实现难度。

• 窗口类型有两大类rows及range

• 边界类型有三大类，unbounded, current row, value interval

• 边界还可以指定方向， preceding，following

• 可以只指定上边界，而不指定下边界

• 可以指定无效窗口，即上边界实际位置低于下边界，此时语义上是所有行返回NULL

• 即使窗口有效，但窗口覆盖下并不存在实际rows的情况，比如边界行的preceding窗口，此时语义是该行返回NULL

• 窗口甚至可以不指定，此时语义等价于rows between unbounded preceding and unbounded following
  

• 特别重要的一点是，上边界可以是following，下边界可以是preceding，我们在实现初期踩过坑，当时认为语法上一定是between xx preceding and xxx following，实际上可以随意交换，这是没有仔细调研oracle导致的血的教训
  

• OceanBase的实现思路

• 添加一个window function物理算子

• 为了解决分组排序问题，window function会为孩子算子添加一个sort节点，排序键为（partition expr_list, order expr_list）的联合键

• 记录窗口类型rows/range，边界类型unbounded/current row/value，及方向preceding/following

• 对于只定义了上边界的语法树，强行补全下边界，边界类型定义为 unbounded following

• 为了执行层处理的方便，物理算子会自己生成一个内部窗口，不管用户指定的窗口是否合法，这个内部窗口一定是合法的，解析器和优化器会保证其upper一定大于lower，即上边界一定大于下边界，若SQL窗口合法，则内部窗口与SQL一致，反之，内部窗口会定义成rows between current row and current row, 这个约束会大大减少执行层各种状态跳转的判断。 需要注意的是，内部窗口只是为了减少状态判断与切换引入的，它只用来决定输出一行数据以及释放一行数据的时机，数据计算由SQL实际窗口决定。

• 执行层处理逻辑：
  由于已按分区键排序键做了排序，因此只要下一行与上一行分区键不等即是新的paritition

• 下界决定何时输出一行, 每从下层算子取出一行就判断是否是新的分区，如果是就将上一个分区的缓存行一一计算并输出；如果不是，就判断当前行能否输出，能则输出，不能则继续从下层算子取数据

• 上界决定何时free一行，每输出一行就更新上边界，此时上边界之前的行资源都可以释放掉
  

• 几种不同窗口的执行计划：
  create table score_tbl(class int, student int, score number, 
primary key(class, student));
  合法窗口：
  explain select max(score) over (partition by class order by score 
rows between 1 preceding and 2 following) from score_tbl;
  
  非法窗口：
  explain select max(score) over (partition by class order by score 
rows between 1 preceding and 2 preceding) from score_tbl;
  
  只定义了窗口上边界：
  explain select max(score) over (partition by class order by score 
rows 1 preceding) from score_tbl;
  
  未显式定义窗口：
  explain select max(score) over (partition by class order by score) from score_tbl;
  

近期or将来支持的

• Range窗口的全面支持。OceanBase在解析器优化器层均已支持range窗口，执行层支持下即可。

• 多窗口函数并行计算。这是针对一条SQL同时含多个窗口函数的场景, 理论上算子嵌套即可解决问题，但如果窗口是兼容的（即分区键排序键窗口一致或部分一致）， 显然可以放到一个算子做并行计算，目前OceanBase已经在执行层支持该优化，优化器暂时没有放开。

• Sort算子按需分配。如果分区键+排序键的序正好是底层算子的序或前缀，实际上我们是不需要分配这个sort节点的。

• 算子下压，利用分布式节点并行计算。如果分区键+排序键的序与分区的序一致，则可以利用OceanBase的分布式架构做分区节点间的并行计算。

• Range + 时间类型interval的支持。

小结

OceanBase的窗口函数才刚上路，还有很多东西要做，优化无止境