資料庫：SQL 視窗函數知識介紹

視窗函數（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

  進行排序

Figure 1. 視窗函數的基本概念

最後一項表示 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][c−3,c+3] 這個範圍内的行，cc 為目前行的值

Figure 2. Rows 視窗和 Range 視窗

邏輯語義上說，一個視窗函數的計算“過程”如下：

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()

  ...

受限于篇幅，本文不去探讨各個視窗函數的含義。關注公衆号Java技術棧，在背景回複：面試，可以擷取我整理的 MySQL 系列面試題和答案，非常齊全。

注：Frame 定義并非所有視窗函數都适用，比如

ROW_NUMBER()

、

RANK()

、

LEAD()

等。這些函數總是應用于整個分區，而非目前 Frame。

視窗函數 VS. 聚合函數

從聚合這個意義上出發，似乎視窗函數和 Group By 聚合函數都能做到同樣的事情。但是，它們之間的相似點也僅限于此了！這其中的關鍵差別在于：視窗函數僅僅隻會将結果附加到目前的結果上，它不會對已有的行或列做任何修改。而 Group By 的做法完全不同：對于各個 Group 它僅僅會保留一行聚合結果。

有的讀者可能會問，加了視窗函數之後傳回結果的順序明顯發生了變化，這不算一種修改嗎？因為 SQL 及關系代數都是以 multi-set 為基礎定義的，結果集本身并沒有順序可言，

ORDER BY

僅僅是最終呈現結果的順序。

另一方面，從邏輯語義上說，SELECT 語句的各個部分可以看作是按以下順序“執行”的：

Figure 3. SQL 各部分的邏輯執行順序

注意到視窗函數的求值僅僅位于

ORDER BY

之前，而位于 SQL 的絕大部分之後。這也和視窗函數隻附加、不修改的語義是呼應的——結果集在此時已經确定好了，再依此計算視窗函數。

視窗函數的執行

視窗函數經典的執行方式分為排序和函數求值這 2 步。

Figure 4. 一個視窗函數的執行過程，通常分為排序和求值 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。

Figure 5. 視窗函數的優化過程

有時候，一個 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 的聚合結果。

Figure 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) 時間内查詢任意區間的聚合結果。更棒的是，不僅查詢可以多線程并發互不幹擾，而且線段樹的構造過程也能被很好地并行起來。

References

1. http://www.vldb.org/pvldb/vol8/p1058-leis.pdf
2. http://vldb.org/pvldb/vol5/p1244_yucao_vldb2012.pdf
3. https://drill.apache.org/docs/sql-window-functions-introduction/)
4. https://modern-sql.com/blog/2019-02/postgresql-11
5. https://www.red-gate.com/simple-talk/sql/learn-sql-server/window-functions-in-sql-server/

複制