乐趣区

关于java:SQL-窗口函数是什么涨见识了

jiezi

作者：Eric Fu\
链接：https://ericfu.me/sql-window-…

窗口函数（Window Function） 是 SQL2003 规范中定义的一项新个性，并在 SQL2011、SQL2016 中又加以欠缺，增加了若干处拓展。窗口函数不同于咱们相熟的一般函数和聚合函数，它为每行数据进行一次计算：输出多行（一个窗口）、返回一个值。在报表等剖析型查问中，窗口函数能优雅地表白某些需要，施展不可代替的作用。

本文首先介绍窗口函数的定义及根本语法，之后将介绍在 DBMS 和大数据系统中是如何实现高效计算窗口函数的，包含窗口函数的优化、执行以及并行执行。

什么是窗口函数？

窗口函数呈现在 SELECT 子句的表达式列表中，它最显著的特点就是 OVER 关键字。语法定义如下：

window_function (expression) OVER ([ PARTITION BY part_list]
   [ORDER BY order_list]
   [{ ROWS | RANGE} BETWEEN frame_start AND frame_end ] )

其中包含以下可选项：

  • PARTITION BY 示意将数据先按 part_list 进行分区
  • ORDER BY 示意将各个分区内的数据按 order_list 进行排序

最初一项示意 Frame 的定义，即：以后窗口蕴含哪些数据？

  • ROWS 抉择前后几行，例如 ROWS BETWEEN 3 PRECEDING AND 3 FOLLOWING 示意往前 3 行到往后 3 行，一共 7 行数据（或小于 7 行，如果碰到了边界）
  • RANGE 抉择数据范畴，例如 RANGE BETWEEN 3 PRECEDING AND 3 FOLLOWING 示意所有值在 c−3,c+3 这个范畴内的行，cc 为以后行的值

逻辑语义上说，一个窗口函数的计算“过程”如下：

  1. 按窗口定义，将所有输出数据分区、再排序（如果需要的话）
  2. 对每一行数据，计算它的 Frame 范畴
  3. 将 Frame 内的行汇合输出窗口函数，计算结果填入以后行

举个例子：

SELECT dealer_id, emp_name, sales,
       ROW_NUMBER() OVER (PARTITION BY dealer_id ORDER BY sales) AS rank,
       AVG(sales) OVER (PARTITION BY dealer_id) AS avgsales 
FROM sales

上述查问中，rank 列示意在以后经销商下，该雇员的销售排名；avgsales 示意以后经销商下所有雇员的均匀销售额。查问后果如下：

+------------+-----------------+--------+------+---------------+
| dealer_id  | emp_name        | sales  | rank | avgsales      |
+------------+-----------------+--------+------+---------------+
| 1          | Raphael Hull    | 8227   | 1    | 14356         |
| 1          | Jack Salazar    | 9710   | 2    | 14356         |
| 1          | Ferris Brown    | 19745  | 3    | 14356         |
| 1          | Noel Meyer      | 19745  | 4    | 14356         |
| 2          | Haviva Montoya  | 9308   | 1    | 13924         |
| 2          | Beverly Lang    | 16233  | 2    | 13924         |
| 2          | Kameko French   | 16233  | 3    | 13924         |
| 3          | May Stout       | 9308   | 1    | 12368         |
| 3          | Abel Kim        | 12369  | 2    | 12368         |
| 3          | Ursa George     | 15427  | 3    | 12368         |
+------------+-----------------+--------+------+---------------+

注：语法中每个局部都是可选的：

  • 如果不指定 PARTITION BY，则不对数据进行分区；换句话说，所有数据看作同一个分区
  • 如果不指定 ORDER BY，则不对各分区做排序，通常用于那些程序无关的窗口函数，例如 SUM()

  • 如果不指定 Frame 子句，则默认采纳以下的 Frame 定义：

    • 若不指定 ORDER BY，默认应用分区内所有行 RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
    • 若指定了 ORDER BY，默认应用分区内第一行到以后值 RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW

最初，窗口函数能够分为以下 3 类：

  • 聚合（Aggregate）：AVG(), COUNT(), MIN(), MAX(), SUM()…
  • 取值（Value）：FIRST_VALUE(), LAST_VALUE(), LEAD(), LAG()…
  • 排序（Ranking）：RANK(), DENSE_RANK(), ROW_NUMBER(), NTILE()…

受限于篇幅，本文不去探讨各个窗口函数的含意。

注：Frame 定义并非所有窗口函数都实用，比方 ROW_NUMBER()、RANK()、LEAD() 等。这些函数总是利用于整个分区，而非以后 Frame。

窗口函数 VS. 聚合函数

从 聚合 这个意义上登程，仿佛窗口函数和 Group By 聚合函数都能做到同样的事件。然而，它们之间的类似点也仅限于此了！这其中的要害区别在于：窗口函数仅仅只会将后果附加到以后的后果上，它不会对已有的行或列做任何批改。而 Group By 的做法齐全不同：对于各个 Group 它仅仅会保留一行聚合后果。

有的读者可能会问，加了窗口函数之后返回后果的程序显著产生了变动，这不算一种批改吗？因为 SQL 及关系代数都是以 multi-set 为根底定义的，后果集自身并没有程序可言，ORDER BY 仅仅是最终出现后果的程序。

另一方面，从逻辑语义上说，SELECT 语句的各个局部能够看作是按以下程序“执行”的：

留神到窗口函数的求值仅仅位于 ORDER BY 之前，而位于 SQL 的绝大部分之后。这也和窗口函数 只附加、不批改 的语义是响应的——后果集在此时曾经确定好了，再依此计算窗口函数。

窗口函数的执行

窗口函数经典的执行形式分为 排序 和函数求值 这 2 步。

窗口定义中的 PARTITION BY 和 ORDER BY 都很容易通过排序实现。例如，对于窗口 PARTITION BY a, b ORDER BY c, d，咱们能够对输出数据按 (a,b,c,d)(a,b,c,d) 或 (b,a,c,d)(b,a,c,d) 做排序，之后数据就排列成 Figure 1 中那样了。

接下来思考：如何解决 Frame？

  • 对于整个分区的 Frame（例如 RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING），只有对整个分区计算一次即可，没什么好说的；
  • 对于逐步增长的 Frame（例如 RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW），能够用 Aggregator 保护累加的状态，这也很容易实现；
  • 对于滑动的 Frame（例如 ROWS BETWEEN 3 PRECEDING AND 3 FOLLOWING）绝对艰难一些。一种经典的做法是要求 Aggregator 不仅反对减少还反对删除（Removable），这可能比你想的要更简单，例如思考下 MAX() 的实现。

窗口函数的优化

对于窗口函数，优化器能做的优化无限。这里为了行文的完整性，依然做一个简要的阐明。

通常，咱们首先会把窗口函数从 Project 中抽取进去，成为一个独立的算子称之为 Window。

有时候，一个 SELECT 语句中蕴含多个窗口函数，它们的窗口定义（OVER 子句）可能雷同、也可能不同。显然，对于雷同的窗口，齐全没必要再做一次分区和排序，咱们能够将它们合并成一个 Window 算子。

对于不同的窗口，最奢侈地，咱们能够将其全副分成不同的 Window，如上图所示。理论执行时，每个 Window 都须要先做一次排序，代价不小。

那是否可能利用一次排序计算多个窗口函数呢？某些状况下，这是可能的。例如本文例子中的 2 个窗口函数：

... ROW_NUMBER() OVER (PARTITION BY dealer_id ORDER BY sales) AS rank,
    AVG(sales) OVER (PARTITION BY dealer_id) AS avgsales ...

尽管这 2 个窗口并非完全一致，然而 AVG(sales) 不关怀分区内的程序，齐全能够复用 ROW_NUMBER() 的窗口。

窗口函数的并行执行

古代 DBMS 大多反对并行执行。对于窗口函数，因为各个分区之间的计算齐全不相干，咱们能够很容易地将各个分区分派给不同的节点（线程），从而达到 分区间并行。

然而，如果窗口函数只有一个全局分区（无 PARTITION BY 子句），或者分区数量很少、不足以充沛并行时，怎么办呢？上文中咱们提到的 Removable Aggregator 的技术显然无奈持续应用了，它依赖于单个 Aggregator 的外部状态，很难无效地并行起来。

TUM 的这篇论文中提出应用 线段树 （Segment Tree）实现高效的 分区内并行。线段树是一个 N 叉树数据结构，每个节点蕴含以后节点下的局部聚合后果。

下图是一个应用二叉线段树计算 SUM() 的例子。例如下图中第三行的 1212，示意叶节点 5+75+7 的聚合后果；而它上方的 2525 示意叶节点 5+7+3+105+7+3+10 的聚合后果。

假如以后 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 系列面试题和答案，十分齐全。

References

  1. http://www.vldb.org/pvldb/vol…
  2. http://vldb.org/pvldb/vol5/p1…
  3. https://drill.apache.org/docs…
  4. https://modern-sql.com/blog/2…
  5. https://www.red-gate.com/simp…

近期热文举荐：

1.600+ 道 Java 面试题及答案整顿(2021 最新版)

2. 终于靠开源我的项目弄到 IntelliJ IDEA 激活码了，真香！

3. 阿里 Mock 工具正式开源，干掉市面上所有 Mock 工具！

4.Spring Cloud 2020.0.0 正式公布，全新颠覆性版本！

5.《Java 开发手册（嵩山版）》最新公布，速速下载！

感觉不错，别忘了顺手点赞 + 转发哦！

退出移动版