數(shù)據(jù)結(jié)構(gòu)
IN 和 EXISTS 是 SQL 中常見的復(fù)雜條件，在將 SQL（存儲(chǔ)過程）轉(zhuǎn)換成庫外計(jì)算獲取高性能時(shí)也會(huì)面對(duì)這些問題。本文將以 TPC-H 定義的模型為基礎(chǔ)活孩，介紹如何用集算器的語法實(shí)現(xiàn) IN、EXISTS 并做優(yōu)化。
TPC-H 是 TPC 事務(wù)處理性能委員會(huì)制定的用于 OLAP 數(shù)據(jù)庫管理系統(tǒng)的測(cè)試標(biāo)準(zhǔn)顶伞，模擬真實(shí)商業(yè)應(yīng)用環(huán)境，以評(píng)估商業(yè)分析中決策支持系統(tǒng)的性能剑梳。TPC-H 模型定義了 8 張表唆貌，表結(jié)構(gòu)和表關(guān)系如下圖：
IN 常數(shù)集合
SQL 示例（1）：
select
P_SIZE, P_TYPE, P_BRAND, count(1) as P_COUNT
from
PART
where
P_SIZE in (2, 3, 8, 15, 17, 25, 27, 28, 30, 38, 41, 44, 45)
and P_TYPE in ('SMALL BRUSHED NICKEL', 'SMALL POLISHED STEEL')
and P_BRAND not in ('Brand#12', 'Brand#13')
group by
P_SIZE, P_TYPE, P_BRAND
優(yōu)化思路：
如果常數(shù)集合元素?cái)?shù)少于 3 個(gè)則可以翻譯成 (f == v1 || f == v2) 這種樣式，NOT IN 對(duì)應(yīng)的就是（f != v1 && f != v2）垢乙。較多的時(shí)候可以在外層把常數(shù)集合定義成序列锨咙，然后用 A.contain(f)來判斷字段是否在序列中，經(jīng)驗(yàn)表明元素個(gè)數(shù)超過 10 個(gè)時(shí)二分查找會(huì)明顯快于順序查找追逮，如果要用二分查找則需要先把序列排序酪刀，然后用 A.contain@b(f)來進(jìn)行有序查找，NOT IN 對(duì)應(yīng)的就是! A.contain(f)钮孵。注意一定要把序列定義在循環(huán)函數(shù)外骂倘，否則會(huì)被多次執(zhí)行。
如果常數(shù)集合元素?cái)?shù)量特別多可以用連接過濾巴席，具體請(qǐng)參照下圖代碼历涝。
集算器實(shí)現(xiàn)：
如果 A1 的元素?cái)?shù)量特別多，則可以使用哈希連接的方法來過濾漾唉，把第 3 行代碼替換如下：
IN子查詢
子查詢選出字段是主鍵
SQL 示例（2）：
select
PS_SUPPKEY, count(1) as S_COUNT
from
PARTSUPP
where
PS_PARTKEY in (
select
P_PARTKEY
from
PART
where
P_NAME like 'bisque%%'
)
group by
PS_SUPPKEY
優(yōu)化思路：
子查詢過濾后讀入內(nèi)存荧库，然后外層表與先讀入的內(nèi)存表（子查詢）做哈希連接進(jìn)行過濾。集算器提供了 switch@i()赵刑、join@i() 兩個(gè)函數(shù)用來做哈希連接過濾分衫，switch 是外鍵式連接，用來把外鍵字段變成指引字段般此，這樣就可以通過外鍵字段直接引用指向表的字段丐箩，join 函數(shù)不會(huì)改變外鍵字段的值摇邦，可用于只過濾。
集算器實(shí)現(xiàn)：
子查詢選出字段不是主鍵
SQL 示例（3）：
select
O_ORDERPRIORITY, count(*) as O_COUNT
from
ORDERS
where
O_ORDERDATE >= date '1995-10-01'
and O_ORDERDATE < date '1995-10-01' + interval '3' month
and O_ORDERKEY in (
select
L_ORDERKEY
from
LINEITEM
where
L_COMMITDATE< L_RECEIPTDATE
)
group by
O_ORDERPRIORITY
優(yōu)化思路：
子查詢過濾后按關(guān)聯(lián)字段去重讀入內(nèi)存屎勘，然后就變成類似于主鍵的情況了施籍，可以繼續(xù)用上面說的 switch@i()、join@i() 兩個(gè)函數(shù)用來做哈希連接過濾概漱。
集算器實(shí)現(xiàn)：
子查詢結(jié)果集存放不下
SQL 示例（3）：
select
O_ORDERPRIORITY, count(*) as O_COUNT
from
ORDERS
where
O_ORDERDATE >= date '1995-10-01'
and O_ORDERDATE < date '1995-10-01' + interval '3' month
and O_ORDERKEY in (
select
L_ORDERKEY
from
LINEITEM
where
L_COMMITDATE< L_RECEIPTDATE
)
group by
O_ORDERPRIORITY
優(yōu)化思路：
IN 子查詢相當(dāng)于對(duì)子查詢結(jié)果集去重然后跟外層表做內(nèi)連接丑慎，而做連接效率較好的就是哈希連接和有序歸并連接，所以這個(gè)問題就變成了怎么把 IN 翻譯成高效的連接瓤摧，下面我們來分析在不同的數(shù)據(jù)分布下如何把 IN 轉(zhuǎn)成連接竿裂。
(1) 外層表數(shù)據(jù)量比較小可以裝入內(nèi)存：
先讀入外層表，如果外層表關(guān)聯(lián)字段不是邏輯主鍵則去重照弥，再拿上一步算出來的關(guān)聯(lián)字段的值對(duì)子查詢做哈希連接過濾腻异，最后拿算出來的子查詢關(guān)聯(lián)字段的值對(duì)外層表做哈希連接過濾。
(2) 外層表和內(nèi)層表按關(guān)聯(lián)字段有序：
此時(shí)可以利用函數(shù) joinx() 來做有序游標(biāo)的歸并連接这揣，如果內(nèi)層表關(guān)聯(lián)字段不是邏輯主鍵則需要先去重悔常。此例中的 ORDERS 表和 LINEITEM 表是按照 ORDERKEY 同序存放，可以利用此方法來做優(yōu)化给赞。
(3) 內(nèi)層表是大維表并且按主鍵有序存放：
集算器提供了針對(duì)有序大維表文件做連接的函數(shù) A.joinx机打，其它方法跟內(nèi)存能放下時(shí)的處理類似在此不再描述。
集算器實(shí)現(xiàn)（1）：
集算器實(shí)現(xiàn)（2）：
EXISTS 等值條件
此章節(jié)的優(yōu)化思路和 IN 子查詢的優(yōu)化思路是相同的片迅，事實(shí)上這種 EXISTS 也都可以用 IN 寫出來（或者倒過來残邀，把 IN 用 EXISTS 寫出來）。
子查詢關(guān)聯(lián)字段是主鍵
SQL 示例（4）：
select
PS_SUPPKEY, count(1) as S_COUNT
from
PARTSUPP
where
exists (
select
*
from
PART
where
P_PARTKEY = PS_PARTKEY
and P_NAME like 'bisque%%'
)
group by
PS_SUPPKEY
優(yōu)化思路：
子查詢過濾后讀入內(nèi)存柑蛇，然后外層表與先讀入的內(nèi)存表（子查詢）做哈希連接進(jìn)行過濾芥挣。集算器提供了 switch@i()、join@i() 兩個(gè)函數(shù)用來做哈希連接過濾耻台，switch 是外鍵式連接九秀，用來把外鍵字段變成指引字段，這樣就可以通過外鍵字段直接引用指向表的字段粘我，join 函數(shù)不會(huì)改變外鍵字段的值鼓蜒，可用于只過濾。
集算器實(shí)現(xiàn)：
子查詢關(guān)聯(lián)字段不是主鍵
SQL 示例（5）：
select
O_ORDERPRIORITY, count(*) as O_COUNT
from
ORDERS
where
O_ORDERDATE >= date '1995-10-01'
and O_ORDERDATE < date '1995-10-01' + interval '3' month
and exists (
select
*
from
LINEITEM
where
L_ORDERKEY = O_ORDERKEY
and L_COMMITDATE < L_RECEIPTDATE
)
group by
O_ORDERPRIORITY
優(yōu)化思路：
子查詢過濾后按關(guān)聯(lián)字段去重讀入內(nèi)存征字，然后就變成類似于主鍵的情況了都弹，可以繼續(xù)用上面說的 switch@i()、join@i() 兩個(gè)函數(shù)用來做哈希連接過濾匙姜。
集算器實(shí)現(xiàn)：
子查詢結(jié)果集存放不下
SQL 示例（5）：
select
O_ORDERPRIORITY, count(*) as O_COUNT
from
ORDERS
where
O_ORDERDATE >= date '1995-10-01'
and O_ORDERDATE < date '1995-10-01' + interval '3' month
and exists (
select
*
from
LINEITEM
where
L_ORDERKEY = O_ORDERKEY
and L_COMMITDATE < L_RECEIPTDATE
)
group by
O_ORDERPRIORITY
優(yōu)化思路：
等值 EXISTS 相當(dāng)于對(duì)內(nèi)部表關(guān)聯(lián)字段去重然后跟外層表做內(nèi)連接畅厢，而做連接效率較好的就是哈希連接和有序歸并連接，所以這個(gè)問題就變成了怎么把 EXISTS 翻譯成高效的連接氮昧，下面我們來分析在不同的數(shù)據(jù)分布下如何把 EXISTS 轉(zhuǎn)成連接框杜。
1浦楣、外層表數(shù)據(jù)量比較小可以裝入內(nèi)存：
先讀入外層表，如果外層表關(guān)聯(lián)字段不是邏輯主鍵則去重咪辱，再拿上一步算出來的關(guān)聯(lián)字段的值對(duì)子查詢做哈希連接過濾关噪，最后拿算出來的子查詢關(guān)聯(lián)字段的值對(duì)外層表做哈希連接過濾依啰。
2祈争、外層表和內(nèi)層表按關(guān)聯(lián)字段有序：
此時(shí)可以利用函數(shù) joinx() 來做有序游標(biāo)的歸并連接企锌，如果內(nèi)層表關(guān)聯(lián)字段不是邏輯主鍵則需要先去重。此例中的 ORDERS 表和 LINEITEM 表是按照 ORDERKEY 同序存放专筷，可以利用此方法來做優(yōu)化弱贼。
3、內(nèi)層表是大維表并且按主鍵有序存放：
集算器提供了針對(duì)有序大維表文件做連接的函數(shù) A.joinx磷蛹，其它方法跟內(nèi)存能放下時(shí)的處理類似在此不再描述吮旅。
集算器實(shí)現(xiàn)（1）：
集算器實(shí)現(xiàn)（2）：
EXISTS 非等值條件
同表關(guān)聯(lián)
SQL 示例（6）：
select
L_SUPPKEY, count(*) as numwait
from
LINEITEM L1,
where
L1.L_RECEIPTDATE > L1.L_COMMITDATE
and exists (
select
*
from
LINEITEM L2
where
L2.L_ORDERKEY = L1.L_ORDERKEY
and L2.L_SUPPKEY <> L1.L_SUPPKEY
)
and not exists (
select
*
from
LINEITEM L3
where
L3.L_ORDERKEY = L1.L_ORDERKEY
and L3.L_SUPPKEY <> L1.L_SUPPKEY
and L3.L_RECEIPTDATE > L3.L_COMMITDATE
)
group by
L_SUPPKEY
優(yōu)化思路：
我們先來看一下 LINEITEM 表的數(shù)據(jù)特點(diǎn)，LINEITEM 表的主鍵是 L_ORDERKEY味咳、L_LINENUMBER庇勃，一個(gè)訂單對(duì)應(yīng) LINEITEM 里的多條記錄，這些記錄的 L_ORDERKEY 是相同的并且在數(shù)據(jù)文件中是相鄰的莺葫。知道這些信息后再來分析上面的 SQL，其條件是為了找出有多個(gè)供應(yīng)商供貨并且有且僅有一個(gè)供應(yīng)商沒有按時(shí)交貨的訂單枪眉，因?yàn)閿?shù)據(jù)是按訂單順序存放的捺檬，這樣我們就可以按訂單有序分組，然后循環(huán)每組訂單判斷是否有沒按時(shí)交貨的訂單項(xiàng)贸铜，是否有多個(gè)供貨商堡纬，并且是不是只有一個(gè)供應(yīng)商沒有按時(shí)交貨。
集算器實(shí)現(xiàn)：
總結(jié)
在沒有空值的時(shí)候帶子查詢的 IN 都可以用 EXISTS 描述蒿秦，同一個(gè)查詢需求用 IN 描述和用 EXISTS 描述翻譯成的集算器代碼是相同的烤镐，所以我們只要弄清楚 EXISTS 怎么翻譯和優(yōu)化就知道 IN 怎么處理了。
等值 exist 本質(zhì)上是做連接棍鳖，兩個(gè)表做連接效率較好的兩種方式是哈希連接和有序歸并連接炮叶，對(duì)于翻譯 select *** from A where exists (select *** from B where ***) 樣式的 SQL，我們首先要弄清楚下列信息：
（1）關(guān)聯(lián)字段是否是各表的主鍵或者邏輯主鍵
（2）A渡处、B 表的規(guī)模镜悉，執(zhí)行其它過濾條件后是否能載入內(nèi)存
（3）如果沒有某個(gè)表能裝入內(nèi)存則要考察兩個(gè)表是否按關(guān)聯(lián)字段有序
如果有一個(gè)表能載入內(nèi)存則可以選用哈希連接的方式來實(shí)現(xiàn)，相關(guān)的集算器函數(shù)有兩個(gè) cs.switch()医瘫、cs.join()侣肄，這兩個(gè)函數(shù)有兩個(gè)可用的選項(xiàng) @i、@d 分別對(duì)應(yīng) exists 和 not exists醇份，參數(shù)里的表要求按關(guān)聯(lián)字段值唯一稼锅，如果不是邏輯主鍵則要先去重吼具，可用 A.groups()去重。如果兩個(gè)表都很大不能載入內(nèi)存則要考察兩個(gè)表是否按關(guān)聯(lián)字段有序矩距，如果無序可以用 cs.sortx() 排序拗盒，對(duì)于有序的兩個(gè)表就可以用 joinx() 來做連接了。
非等值運(yùn)算則要分析其中的運(yùn)算邏輯看能否轉(zhuǎn)成分組后再計(jì)算剩晴，如果不能則只能使用嵌套循環(huán)連接的方式了锣咒，對(duì)應(yīng)的函數(shù)是 xjoin()。
知道這些信息并熟練掌握集算器相關(guān)的幾個(gè)函數(shù)后我們就能夠?qū)懗龈咝У拇a赞弥。
