第 25 期：有序分組

我們知道，SQL 延用了數學上的無序集合概念，是以 SQL 的分組并不關注過待分組集合中成員的次序。我們在前面讨論過的等值分組和非等值分組，也都沒有關注過這個問題，分組規則都是建立在成員取值本身上。但如果我們要拓展 SQL，以有序集合為考慮對象時，那就必須考慮成員次序對分組的影響了，而且，現實業務中有大量的有序分組應用場景。

1. 序号分組

   一個簡單的例子：将一個班的學生平均分成三份（假定人數能被 3 整除）。按我們在前面所說的分組定義，這也可以看成是一種分組，但這個運算在 SQL 中卻很難寫出來，因為分組依據和成員取值沒有關系。

如果使用我們在前面講有序周遊文法時的 #符号，這個問題就很容易解決了。

A.group( (#-1)*3\A.len() )   // 按序号分成前1/3，中1/3，後1/3

A.group( (#-1)%3 )             // 還可以按序号每三個中取一個構成分組子集

用 SQL 實作這個運算就麻煩很多，需要先用子查詢造出一個序号，然後再執行類似的分組規則。

上面這個例子中其實還沒有真正關注成員的次序，隻是說明了序号的作用，待分組集合的成員是其它次序時也可以得到可用的結果。

我們再看更多例子。

處理文本日志時，有些日志的基本機關不是 1 行，而可能是 3 行，即每個事件總是寫出 3 行文本，這并不是多罕見的情況。對付這種日志時，就需要把文本每 3 行拆成一個分組子集，然後針對每個分組再進行詳細的分析處理。這時要正确的分組運算就必須依賴于待分組集合中成員（文本日志的行）的次序了。

入學考試之後，把學生按成績排序蛇行分拆成兩個班，即名次 1,4,5,8,…在一個，而 2,3,6,7,…在另一個班，這樣能保證兩個班的平均名次是相同的。這個分組也可以用序号做出來：

A.sort@z(score).group(#%4<2)

這裡用的分組值不再是常見的普通數值，而是一個布爾量，相當于按“真“值和“假”值分成兩個組，真值對應第一個班，假值對應另一個班。本質上講，這還是個等值分組，隻是用到的分組值可以是任意泛型。

顯然，這個分組的正确性也嚴重依賴于待分組內建的成員次序。

順便說一句，這又是一個隻關注分組子集而不關心聚合值的例子。

按序号分組在很多情況下就是用序号來計算出分組依據，然後就變成普通的等值分組了。那麼有沒有不能簡單地轉換成等值分組的情況呢？

1. 值變化分組

   有一組嬰兒出生記錄，是按出生次序排序的，我們現在關心連續出生的同性别嬰兒數量超過 5 的有多少批？

簡單想，這就是先 GROUP，計算每組 COUNT 值，然後數出有幾個大于 5 的。後兩步很簡單，問題是怎麼 GROUP？

直接按嬰兒性别分組當然是不對的，必須考慮次序，依次掃描記錄，當嬰兒性别發生變化時則産生一個新組。這種分組顯然沒法直接用等值分組做出來了。

我們可以提供一個有序分組方法來實作這種分組：當考察值發生變化時就産生一個新的分組。

A.group@o(gender).count(~.len()>5)   // @o選項表示分組值變化時将産生新分組。

用 SQL 就麻煩很多，需要先造成中間标志和變量來生成組的序号，大概是這樣

SELECT COUNT() FROM (SELECT ChangeNumber FROM (SELECT SUM(ChangeFlag) OVER (ORDER BY birthday) ChangeNumber FROM (SELECT CASE WHEN gender=LAG(gender) OVER ( ORDER BY birthday) THEN 0 ELSE 1 END ChangeFlag FROM A)) GROUP ChangeNumber HAVING COUNT()>5)

這樣的 SQL，看懂都不是很容易的。而且必須借助 birthday 這種字段來形成次序，而前述的有序分組寫法在原資料有序時根本用不着這個資訊。

這種場景同樣可能出現在文本分析中。每個使用者的事件日志可能多行，而且行數不确定，但寫日志時會在每個行開始處寫上使用者号。這樣我們可以按這個使用者号進行有序分組，它變化時就說明是另一個使用者的事件了。

即使是普通的等值分組，如果事先知道原集合對分組字段有序，也可以使用這種方案來實施，這将獲得更高的性能，比資料庫常用的 HASH 分組方案要快得多，而且特别适合大資料周遊的情況。

1. 條件變化分組

   再看一個著名的問題：一支股票最長連續上漲了多少天？

這個問題當然可以直接周遊去解決，不過我們現在用分組的思路來處理，至少在 SQL 體系下隻能這麼做（嚴格些說，這是目前找到的最簡單可行的辦法）。

将股票收盤價按日期排序，然後将連續上漲的日期分到同一組，這樣隻要考慮哪一組成員數最多即可。更明确地說，就是當某天上漲了，就把這一天和前一天分到一個組中，某天下跌了，則産生一個新組。

用 SQL 實作這個思路，同樣需要用中間标志和變量來生成組序号：

SELECT MAX(ContinuousDays) FROM (SELECT COUNT(*) ContinuousDays FROM (SELECT SUM(RisingFlag) OVER (ORDER BY TradingDate ) NoRisingDays FROM (SELECT TradingDate, CASE WHEN ClosingPrice>LAG(ClosingPrice) OVER (ORDER BY TradingDate THEN 0 ELSE 1 END) RisingFlag

FROM A)) GROUP BY NoRisingDays)

如果有專門的有序分組方法以及以前說過的有序周遊文法，這個運算就很簡單了：

A.sort(TradingDate).group@i(ClosingPrice與 SQL 不同，雖然實作思路完全一樣，但寫出來是分步的，而不是一個多層嵌套語句，書寫和了解都要容易得多。

同樣地，這種場景也會在文本分析中有用。不确定行數的日志中，有時會在事件分始時寫一個标志串，當掃描到這個标志串的時候就産生一個新的分組，有序分析的條件可設定為目前掃描行和指定文字相同，這樣就能保證同一事件的日志資訊在同一個組中。

後兩種有序分組的情況，理論上當然也可以轉換成等值分組來處理（用 SQL 就要這麼做，這也能從另一個側面說明 SQL 運算體系的完備性），但确實是相當麻煩的，是以我們一般不把它再當成等值分組來處理了。

到目前為止的分組讨論，都是假定待分組集合已經準備好，其成員可以被随機通路到。但如果資料量巨大而不能全部讀入時，如果繼續做這種假定，會導緻頻繁的外存交換而性能極差，這時需要再設計以流方式邊讀入邊分組并且邊聚合的運算體系。事實上日志分析中更常見的是這種情況，這些問題我們将再撰文研究，但基本方法思路仍然離不開上面這些内容。

作者：279400248

連結：

http://c.raqsoft.com.cn/article/1533869653839

來源：乾學院

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。