窗口函数（WindowFunction）是SQL2003标准中定义的新特性，在SQL2011和SQL2016中得到了改进，增加了几个扩展。窗口函数不同于我们熟悉的普通函数和聚合函数。他们对每一行数据执行一次计算：输入多行（一个窗口），并返回一个值。在报表等分析查询中，窗口函数可以优雅地表达某些需求，发挥着不可替代的作用。本文首先介绍了窗函数的定义和基本语法，然后介绍了如何在DBMS和大数据系统中实现窗函数的高效计算，包括窗函数的优化、执行和并行执行。什么是窗口函数？窗口函数出现在SELECT子句的表达式列表中，它们最显着的特点是OVER关键字。语法定义如下：window_function(expression)OVER([PARTITIONBYpart_list][ORDERBYorder_list][{ROWS|RANGE}BETWEENframe_startANDframe_end])包括以下选项：每个分区中的数据按order_list排序图1窗口函数基本概念最后一项代表Frame的定义，即：当前窗口包含哪些数据？ROWS选取前后几行，比如ROWSBETWEEN3PRECEDINGAND3FOLLOWING表示从前面3行到后面3行，一共7行数据（或者少于7行，如果碰到边界）RANGE选择数据范围，如RANGEBETWEEN3PRECEDINGAND3FOLLOWING表示所有值在[c?3,c+3][c?3,c+3]范围内的行，cc为值当前行的。Figure2.RowswindowandRangewindow逻辑语义说，一个窗口函数的计算“过程”如下：根据窗口的定义，对所有输入数据进行分区和重新排序（如果需要的话）对于每一行数据，计算其Frame范围将Frame中设置的行输入到窗口函数中，并填入计算结果以当前行为例：SELECTdealer_id,emp_name,sales,ROW_NUMBER()OVER(PARTITIONBYdealer_idORDERBYsales)ASrank,AVG(sales)OVER(PARTITIONBYdealer_id)ASavgsalesFROMsales上述查询中，rank列表示该员工在当前经销商下的销售排名；avgsales表示当前经销商下所有员工的平均销售额。查询结果如下：+------------+----------------+--------+-----+------------+|dealer_id|emp_name|sales|rank|avgsales|+------------+-----------------+--------+------+------------+|1|RaphaelHull|8227|1|14356||1|JackSalazar|9710|2|14356||1|FerrisBrown|19745|3|1??4356||1|NoelMeyer|19745|4|14356||2|HavivaMontoya|9308|1|13924||2|BeverlyLang|16233|2|13924||2|KamekoFrench|16233|3|13924||3|MayStout|9308|1|12368||3|AbelKim|12369|2|12368||3|UrsaGeorge|15427|3|12368|+------------+----------------+--------+------+--------------+注意：语法的每一部分都是可选的：如果不指定PARTITIONBY，则不对数据进行分区；换句话说，所有的数据都被当作同一个分区，如果没有指定ORDERBY，分区将不会被排序，这通常用于与顺序无关的窗口函数，如SUM()。如果未指定Frame子句，则默认使用以下Frame定义：如果未指定ORDERBY，则默认使用分区中的所有行RANGEBETWEENUNBOUNDEDPRECEDINGANDUNBOUNDEDFOLLOWING如果指定ORDERBY，则使用第一行在分区中默认为当前值RANGEBETWEENUNBOUNDEDPRECEDINGANDCURRENTROW最后，窗口函数可以分为以下三类：聚合（Aggregate）：AVG()、COUNT()、MIN()、MAX()、SUM()...值（值）：FIRST_VALUE(),LAST_VALUE(),LEAD(),LAG()...Ranking:RANK(),DENSE_RANK(),ROW_NUMBER(),NTILE()...限于篇幅，本文不再讨论各个窗口函数的含义，关注公众号Java技术栈，后台回复：面试，可以拿到我整理的MySQL系列面试题及答案，很全。注意：Frame定义并不适用于所有窗口函数，如ROW_NUMBER()、RANK()、LEAD()等，这些函数始终适用于整个分区，而不适用于当前Frame。窗函数VS。聚合函数从聚合的意义上说，似乎windowfunction和GroupBy聚合函数都可以做同样的事情。但这就是相似之处结束的地方！这里的主要区别在于窗口函数仅将结果附加到当前结果，它不会修改任何现有的行或列。GroupBy的做法则完全不同：它只为每个Group保留一行聚合结果。可能有读者会问，添加窗口函数后，返回结果的顺序明显变了。这不算修改吗？因为SQL和关系代数都是在multi-set的基础上定义的，结果集本身是没有顺序的，ORDERBY只是结果最终呈现的顺序。另一方面，就逻辑语义而言，SELECT语句的各个部分可以被视为按以下顺序“执行”：图3.SQL各个部分的逻辑执行顺序注意窗口的评估函数只在ORDERBY之前，大部分SQL之后。这也呼应了窗函数只追加不修改的语义——此时结果集已经确定，然后再据此计算窗函数。别再select*了，我给你12个查询技巧，推荐你看看。窗口函数的执行经典的窗口函数执行分为两步：排序和函数求值。图4.窗口函数的执行过程通常分为排序和求值两个步骤。窗口定义中的PARTITIONBY和ORDERBY都可以轻松完成排序。例如，对于窗口PARTITIONBYa,bORDERBYc,d，我们可以按(a,b,c,d)(a,b,c,d)或(b,a,c,d)(b,a,c,d)排序，则数据排列如图1。接下来考虑：如何处理Frame？对于整个分区的Frame（比如RANGEBETWEENUNBOUNDEDPRECEDINGANDUNBOUNDEDFOLLOWING），整个分区只需要计算一次，没什么好说的；对于逐渐增长的Frame（比如RANGEBETWEENUNBOUNDEDPRECEDINGANDCURRENTROW），可以使用Aggregator来维护累加，这也很容易实现；滑动Frames（比如ROWSBETWEEN3PRECEDINGAND3FOLLOWING）相对困难。一个经典的做法是要求Aggregator不仅支持加法还支持移除（Removable），这可能比你想象的要复杂，比如考虑MAX()的实现。窗函数的优化对于窗函数，优化器能做的优化是有限的。为了文字的完整性，这里还是做一个简单的说明。通常，我们先从Project中提取窗口函数，使其成为一个独立的算子，称为Window。图5.窗口函数的优化过程有时，一个SELECT语句包含多个窗口函数，它们的窗口定义（OVER子句）可能相同也可能不同。显然，对于同一个窗口，没有必要再做分区和排序，我们可以将它们组合成一个Window算子。对于不同的窗口，最简单的，我们可以把它们都分成不同的窗口，如上图所示。实际执行时，需要先对每个Window进行排序，代价不小。是否可以使用一种排序来计算多个窗口函数？在某些情况下这是可能的。比如本文例子中的两个窗口函数：...ROW_NUMBER()OVER(PARTITIONBYdealer_idORDERBYsales)ASrank,AVG(sales)OVER(PARTITIONBYdealer_id)ASavgsales...虽然这两个窗口不完全一样，AVG(sales)不关心分区内的顺序，完全可以复用ROW_NUMBER()的窗口。窗口函数的并行执行大多数现代DBMS都支持并行执行。对于窗口函数，由于分区之间的计算是完全无关的，我们可以很容易地将每个分区分配给不同的节点（线程）来实现分区间的并行。但是，如果窗口函数只有一个全局分区（没有PARTITIONBY子句），或者分区数量太少而无法充分并行化怎么办？我们上面提到的RemovableAggregator技术显然不能再用了。它依赖于单个聚合器的内部状态，很难有效地并行化。这篇TUM论文提出使用线段树（SegmentTree）来实现高效的分区内并行。线段树是一种N叉树数据结构，每个节点包含当前节点下的一部分聚合结果。下图是使用二叉线段树计算SUM()的示例。比如下图中第三行的1212代表叶子节点5+75+7的聚合结果；而上面的2525代表叶子节点5+7+3+105+7+3+10的聚合结果。图6.使用线段树计算给定范围的总和。假设当前Frame为第2到第8行，即需要计算7+3+10+...+47+3+10+...+4个区间之和。有了线段树，我们可以直接用7+13+207+13+20（图中红色字体）来计算聚合结果。可以在O(nlogn)O(nlog?n)时间内构建线段树，在O(logn)O(log?n)时间内查询任意区间的聚合结果。更棒的是，不仅多线程查询可以互不干扰，线段树的构建过程也可以很好的并行化。最后关注公众号Java技术栈，后台回复：面试，可以拿到我整理的MySQL系列面试题及答案，很全。
