轉載自OceanBase公眾號《OceanBase1.0 窗口函數簡介》

窗口函數是什麼

• 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的窗口函數才剛上路，還有很多東西要做，優化無止境