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 窗口
邏輯語義上說，一個窗口函數的計算“過程”如下：
- 按窗口定義，將所有輸入數據分區、再排序（如果需要的話）
- 對每一行數據，計算它的 Frame 范圍
- 將 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 的絕大部分之后。這也和窗口函數只附加、不修改的語義是呼應的——結果集在此時已經確定好了，再依此計算窗口函數。別再 select * 了，送你 12 個查詢技巧，推薦看下。
窗口函數的執行
窗口函數經典的執行方式分為排序和函數求值這 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(nlogn) 時間內構造，并能在 O(logn)O(logn) 時間內查詢任意區間的聚合結果。更棒的是，不僅查詢可以多線程并發互不干擾，而且線段樹的構造過程也能被很好地并行起來。
最后，關注公眾號Java技術棧，在后臺回復：面試，可以獲取我整理的 MySQL 系列面試題和答案，非常齊全。
