利用有序高效實施交并差集合運算

 看起來很簡單的集合運算放在大數據的場景下，如果還想獲得高性能就需要充分了解數據特征和計算特征才能設計出高效算法。充分利用序運算就是一種好辦法！

交并差是常見的集合運算，SQL 中對應的 intersect/union/minus 計算也很簡單。不過當數據量較大時，這類集合運算性能往往偏低，尤其當參與計算的數據量超過內存容量時，性能表現會十分糟糕。

       本文專門針對這種情況下的高性能計算（HPC）需求，討論如何使用集算器 SPL 語言通過有序計算思路顯著提高大數據量下交并差三類集合運算的性能。下面討論中使用了一個實際用戶在數據庫選型時的評測用例：數據基于數據庫的 2 個表，共計 105 億行數據，執行相關運算后，以輸出第一批 500 條記錄所用時間來衡量哪個數據庫性能更優。

測試環境

數據描述

數據情況

索引

樣例數據

a1-a52 列值：

2018-01-07 00:00:00,8888888888,MQJqxnXMLM,ccTTCC7755,aaa******8,ppppaaaavv,gggggttttt,MQJqxnXMLM,ccTTCC7755,aaa******8,ppppaaaavv,gggggttttt,MQJqxnXMLM,ccTTCC7755,aaa******8,ppppaaaavv,gggggttttt,MQJqxnXMLM,ccTTCC7755,aaa******8,ppppaaaavv,gggggttttt,MQJqxnXMLM,ccTTCC7755,aaa******8,ppppaaaavv,gggggttttt,MQJqxnXMLM,ccTTCC7755,aaa******8,ppppaaaavv,gggggttttt,MQJqxnXMLM,ccTTCC7755,aaa******8,ppppaaaavv,gggggttttt,MQJqxnXMLM,ccTTCC7755,aaa******8,ppppaaaavv,gggggttttt,MQJqxnXMLM,ccTTCC7755,aaa******8,ppppaaaavv,gggggttttt,MQJqxnXMLM,ccTTCC7755,aaa******8,ppppaaaavv,gggggttttt

2018-01-07 00:00:00,4444444444,dv@bi-lyMF,qqoovv22ww,)))777FFF4,jjjjIIIIVV,aaaaaRRRRR,dv@bi-lyMF,qqoovv22ww,)))777FFF4,jjjjIIIIVV,aaaaaRRRRR,dv@bi-lyMF,qqoovv22ww,)))777FFF4,jjjjIIIIVV,aaaaaRRRRR,dv@bi-lyMF,qqoovv22ww,)))777FFF4,jjjjIIIIVV,aaaaaRRRRR,dv@bi-lyMF,qqoovv22ww,)))777FFF4,jjjjIIIIVV,aaaaaRRRRR,dv@bi-lyMF,qqoovv22ww,)))777FFF4,jjjjIIIIVV,aaaaaRRRRR,dv@bi-lyMF,qqoovv22ww,)))777FFF4,jjjjIIIIVV,aaaaaRRRRR,dv@bi-lyMF,qqoovv22ww,)))777FFF4,jjjjIIIIVV,aaaaaRRRRR,dv@bi-lyMF,qqoovv22ww,)))777FFF4,jjjjIIIIVV,aaaaaRRRRR,dv@bi-lyMF,qqoovv22ww,)))777FFF4,jjjjIIIIVV,aaaaaRRRRR

2018-01-07 00:00:00,9999999999,bxk3J/2YDd,ppvv**--88,uuuNNNBBBA,BBBBhhhhjj,_____PPPPP,bxk3J/2YDd,ppvv**--88,uuuNNNBBBA,BBBBhhhhjj,_____PPPPP,bxk3J/2YDd,ppvv**--88,uuuNNNBBBA,BBBBhhhhjj,_____PPPPP,bxk3J/2YDd,ppvv**--88,uuuNNNBBBA,BBBBhhhhjj,_____PPPPP,bxk3J/2YDd,ppvv**--88,uuuNNNBBBA,BBBBhhhhjj,_____PPPPP,bxk3J/2YDd,ppvv**--88,uuuNNNBBBA,BBBBhhhhjj,_____PPPPP,bxk3J/2YDd,ppvv**--88,uuuNNNBBBA,BBBBhhhhjj,_____PPPPP,bxk3J/2YDd,ppvv**--88,uuuNNNBBBA,BBBBhhhhjj,_____PPPPP,bxk3J/2YDd,ppvv**--88,uuuNNNBBBA,BBBBhhhhjj,_____PPPPP,bxk3J/2YDd,ppvv**--88,uuuNNNBBBA,BBBBhhhhjj,_____PPPPP

測試用例

l  交集（intersect）

select * from A, B where a1>'2018-01-07 02:14:43' and a1 < '2018-01-07 04:14:43' and a3=b1 or a7 = b2

intersect

select * from A, B where a1>'2018-01-07 12:14:43' and a1 < '2018-01-07 14:14:43' and a3=b1 or a7=b2

l  并集（union）

select * from A, B where a1>'2018-01-07 02:14:43' and a1 < '2018-01-07 04:14:43' and a3=b1 or a7 = b2

union

select * from A, B where a1>'2018-01-07 12:14:43' and a1 < '2018-01-07 14:14:43' and a3=b1 or a7=b2

l  差集（minus）

select * from A, B where a1>'2018-01-07 02:14:43' and a1 < '2018-01-07 04:14:43' and a3=b1 or a7 = b2

minus

select * from A, B where a1>'2018-01-07 12:14:43' and a1 < '2018-01-07 14:14:43' and a3=b1 or a7=b2

用例分析

       分析上述 SQL 可以發現，此計算場景為大數據量的多對多集合運算。查詢條件的前半段（a1>'2018-01-07 02:14:43' and a1 < '2018-01-07 04:14:43' and a3=b1）是 A 表 2 個小時內的數據與 B 表進行多對多關聯；而后半段（or a7 = b2）則是 A 表全量數據和 B 表進行多對多關聯。因此，這個用例主要考察的是大表 A 和小表 B 多對多關聯后的集合運算性能。

       實測時，該 SQL 使用 MPP 數據庫得不到查詢結果（運行時間超過 1 小時），因為數據量很大，內存無法容納全部數據，從而造成數據庫在運算時頻繁進行磁盤交互，導致整體性能極低。

       按照我們一貫的思路，要實施高性能計算必須設計符合數據特征和計算特征的算法，而不是簡單地使用通用的算法。這里，為了避免過多的磁盤交互（這也是大數據規模計算的首要考慮目標），最好只遍歷一次 A 表就能完成計算。觀察數據可以發現，A 表包含時間字段（a1），而且在時間字段（a1）和關聯字段（a3、a7）上均建有索引，同樣 B 表的兩個字段（b1、b2）也建有索引，這樣，我們就可以設計出這樣的算法：

1)       根據 A 表數據生成的特點，逐秒讀取 A 表數據（每秒 24000 條）；

2)       針對每秒的數據循環處理，根據過濾條件逐條與 B 表關聯，返回關聯后結果；

3)       對兩部分數據，即用于交并差的兩個集合進行集合運算。

通過以上三步就可以完成全部計算，而整個過程中對 A 表只遍歷了 2 次（分別得到用于交并差的兩個集合）。當然，整個過程中由于數據量太大，集算器將通過延遲游標的方式進行歸并，游標歸并時數據需要事先排序，所以在 1)和 2) 步之間還需要對每秒的 24000 條數據按照關聯字段和其他字段排序，會產生一些額外的開銷。下面是具體的集算器 SPL 腳本。

SPL 實現

       這里分主子兩個程序，主程序調用子程序分別獲得交 / 并 / 差運算的兩個集合并進行集合運算，子程序則根據參數計算集合，也就是說用例中的交并差三類計算可以使用同一個子程序腳本。

子程序腳本（case1_cursor.dfx）

A1：在 otherCols 中記錄 A 表 52 個字段中除參與運算的 a1,a3,a7 外其他所有字段名稱，用于生成 SQL 查詢

A2：連接數據庫

A3：SQL 語句串，用于根據條件查詢 A 表所有列數據

A4：查詢 B 表數據，針對 b1，b2 進行分組計數（以便在后續計算中減少比較次數），并按 b1，b2 排序（用于后續有序歸并）

A5：按照 5 天時間內的秒數進行循環

B5：每次循環中在起始時間（2018-01-07 00:00:00）上加相應的秒數，查詢那一秒產生的數據（24000 條）

B6：按照關聯字段以及其他字段排序

B7：循環處理一秒內的每條 A 表數據

C7：根據單條 A 表數據，在 B 表中查找符合條件的記錄

C8：返回計算后包含 A 表和 B 表所有字段值的結果集，這里使用了 A.news() 函數，用來計算得到序表 / 排列的字段值合并生成的新序表 / 排列，具體用法請參考http://doc.raqsoft.com.cn/esproc/func/news.html

主程序腳本

交集（intersect）

A1，A2：通過 cursor()函數調用子程序腳本，并傳入 2 個時間段參數；cursor() 函數原理請參考： 《百萬級分組大報表開發與呈現》

A3：根據子程序返回的游標序列進行歸并，使用 @i 選項完成交集運算

A4：從游標中取出 500 條記錄，并關閉游標（@x 選項）

并集（union）

A3：使用 @u 選項完成并集計算，其他 SPL 腳本完全相同

差集（minus）

A3：使用 @d 選項完成并集計算，其他 SPL 腳本完全相同

性能表現

下表對集算器 SPL 和數據庫 SQL 分別輸出第一個 500 條結果集的時間進行了比較：

顯然，交集和并集計算的性能得到了極大的提升。

為什么差集運算很慢？

差集運算依然很慢的原因是由數據特征所決定的。由于多對多關聯后重復記錄較多，要計算出符合條件的差集仍舊要遍歷完 A 表（而另外兩個計算獲得 500 條結果集就可以不再遍歷了），因此性能主要消耗在 IO 取數上。

總結

高性能算法需要根據數據和計算特征進行針對性設計，這要求程序猿首先能夠想出高性能算法，然后以不太復雜的手段加以實現，否則就沒有可行性了。

對于 SQL 體系來說，由于其封閉性原因，一些高效算法可能即使能設計出來也很難，甚至無法實現。而集算器 SPL 則極大地改善了這個問題，使用者可以在設計出高性能算法后，基于 SPL 體系快速實現。