轉(zhuǎn)自：http://hbasefly.com/2017/04/10/bigdata-join-2/

上文簡(jiǎn)要介紹了Join在大數(shù)據(jù)領(lǐng)域中的使用背景以及常用的幾種算法－broadcast hash join 唇聘、shuffle hash join以及sort merge join等，對(duì)每一種算法的核心應(yīng)用場(chǎng)景也做了相關(guān)介紹谎亩，這里再重點(diǎn)說(shuō)明一番：大表與小表進(jìn)行join會(huì)使用broadcast hash join夫凸，一旦小表稍微大點(diǎn)不再適合廣播分發(fā)就會(huì)選擇shuffle hash join，最后鸽扁，兩張大表的話無(wú)疑選擇sort merge join。

好了骡和，問(wèn)題來(lái)了，說(shuō)是這么一說(shuō)婆赠，但到底選擇哪種算法歸根結(jié)底是SQL執(zhí)行引擎干的事情，按照上文邏輯，SQL執(zhí)行引擎肯定要知道參與Join的兩表大小楣导，才能選擇最優(yōu)的算法嘍筒繁！那么斗膽問(wèn)一句，怎么知道兩表大信荤浴？衡量?jī)杀泶笮〉氖俏锢泶笮∵€是紀(jì)錄多少抑或兩者都有纹安？其實(shí)，這是另一門(mén)學(xué)問(wèn)－基于代價(jià)優(yōu)化（Cost Based?Optimization，簡(jiǎn)稱(chēng)CBO）窗怒，它不僅能夠解釋Join算法的選擇問(wèn)題，更重要的，它還能確定多表聯(lián)合Join場(chǎng)景下的Join順序問(wèn)題堪置。

是不是對(duì)CBO很期待呢宛逗？好吧替蔬，這里先刨個(gè)坑承桥，下一個(gè)話題我們?cè)倭摹Ｄ墙裉煲狞c(diǎn)什么呢屯掖？Join算法選擇、Join順序選擇確實(shí)對(duì)Join性能影響極大绍坝，但玖详，還有一個(gè)很重要的因素對(duì)Join的性能至關(guān)重要拗踢，那就是Join算法優(yōu)化券膀！無(wú)論是broadcast hash join蓄髓、shuffle hash join還是sort merge join，都是最基礎(chǔ)的join算法匾竿，有沒(méi)有什么優(yōu)化方案呢反璃？還真有，這就是今天要聊的主角－Runtime Filter（下文簡(jiǎn)稱(chēng)RF）

RF預(yù)備知識(shí)：bloom filter

RF說(shuō)白了是使用bloomfilter對(duì)參與join的表進(jìn)行過(guò)濾，減少實(shí)際參與join的數(shù)據(jù)量。為了下文詳細(xì)解釋整個(gè)流程，有必要先解釋一下bloomfilter這個(gè)數(shù)據(jù)結(jié)構(gòu)（對(duì)之熟悉的看官可以繞道）逢艘。Bloom Filter使用位數(shù)組來(lái)實(shí)現(xiàn)過(guò)濾娩怎，初始狀態(tài)下位數(shù)組每一位都為0，如下圖所示：

假如此時(shí)有一個(gè)集合S = {x1, x2, … xn}却桶，Bloom Filter使用k個(gè)獨(dú)立的hash函數(shù)，分別將集合中的每一個(gè)元素映射到｛1,…,m｝的范圍信粮。對(duì)于任何一個(gè)元素，被映射到的數(shù)字作為對(duì)應(yīng)的位數(shù)組的索引，該位會(huì)被置為1觉阅。比如元素x1被hash函數(shù)映射到數(shù)字8鲫尊，那么位數(shù)組的第8位就會(huì)被置為1。下圖中集合S只有兩個(gè)元素x和y，分別被3個(gè)hash函數(shù)進(jìn)行映射，映射到的位置分別為（0温技，3蜓堕，6）和（4慕淡，7，10），對(duì)應(yīng)的位會(huì)被置為1:

現(xiàn)在假如要判斷另一個(gè)元素是否是在此集合中浪汪，只需要被這3個(gè)hash函數(shù)進(jìn)行映射，查看對(duì)應(yīng)的位置是否有0存在，如果有的話，表示此元素肯定不存在于這個(gè)集合，否則有可能存在。下圖所示就表示z肯定不在集合｛x题造，y｝中：

RF算法理論

為了更好地說(shuō)明整個(gè)過(guò)程，這里使用一個(gè)SQL示例對(duì)RF算法進(jìn)行完整講解揽思，SQL：select item.name, order.* from order , item where order.item_id = item.id and item.category = ‘book’鲤屡，其中order為訂單表堰汉，item為商品表戳葵，兩張表根據(jù)商品id字段進(jìn)行join，該SQL意為取出商品類(lèi)別為書(shū)籍的所有訂單詳情。假設(shè)商品類(lèi)型為書(shū)籍的商品并不多，join算法因此確定為broadcast hash join。整個(gè)流程如下圖所示：

Step 1：將item表的join字段（item.id）經(jīng)過(guò)多個(gè)hash函數(shù)映射處理為一個(gè)bloomfilter（如果對(duì)bloomfilter不了解惯吕，自行g(shù)oogle）

Step 2：將映射好的bloomfilter分別廣播到order表的所有partition上堡距，準(zhǔn)備進(jìn)行過(guò)濾

Step 3：以Partition2為例易稠，存儲(chǔ)進(jìn)程（比如DataNode進(jìn)程）將order表中join列（order.item_id）數(shù)據(jù)一條一條讀出來(lái)衬吆，使用bloomfilter進(jìn)行過(guò)濾冒嫡。淘汰該訂單數(shù)據(jù)不是書(shū)籍相關(guān)商品的訂單蟀架，這條數(shù)據(jù)直接跳過(guò)捌省；否則該條訂單數(shù)據(jù)有可能是待檢索訂單色徘，將該行數(shù)據(jù)全部掃描出來(lái)斤寂。

Step 4：將所有未被bloomfilter過(guò)濾掉的訂單數(shù)據(jù)溪猿，通過(guò)本地socket通信發(fā)送到計(jì)算進(jìn)程（impalad）依痊。

Step 5：再將所有書(shū)籍商品數(shù)據(jù)廣播到所有Partition節(jié)點(diǎn)與step4所得訂單數(shù)據(jù)進(jìn)行真正的hashjoin操作性宏，得到最終的選擇結(jié)果

RF算法分析

上面通過(guò)一個(gè)SQL示例簡(jiǎn)單演示了整個(gè)RF算法在broadcast hash join中的操作流程菩佑，根據(jù)流程對(duì)該算法進(jìn)行一下理論層次分析：

RF本質(zhì)：通過(guò)謂詞（?bloomfilter）下推瞧哟，在存儲(chǔ)層通過(guò)bloomfilter對(duì)數(shù)據(jù)進(jìn)行過(guò)濾陨亡，可以從三個(gè)方面實(shí)現(xiàn)對(duì)Join的優(yōu)化遮糖。其一赛不，如果可以跳過(guò)很多記錄，就可以減少了數(shù)據(jù)IO掃描次數(shù)畴椰。這點(diǎn)需要重點(diǎn)解釋一下帚戳，許多朋友會(huì)有這樣的疑問(wèn)：既然需要把數(shù)據(jù)掃描出來(lái)使用BloomFilter進(jìn)行過(guò)濾，為什么還會(huì)減少I(mǎi)O掃描次數(shù)呢？這里需要關(guān)注一個(gè)事實(shí)：大多數(shù)表存儲(chǔ)行為都是列存确徙，列之間獨(dú)立存儲(chǔ)较鼓，掃描過(guò)濾只需要掃描join列數(shù)據(jù)（而不是所有列），如果某一列被過(guò)濾掉了万矾，其他對(duì)應(yīng)的同一行的列就不需要掃描了，這樣減少I(mǎi)O掃描次數(shù)漫玄。其二，減少了數(shù)據(jù)從存儲(chǔ)層通過(guò)socket(甚至TPC）發(fā)送到計(jì)算層的開(kāi)銷(xiāo)，其三，減少了最終hash join執(zhí)行的開(kāi)銷(xiāo)世舰。

RF代價(jià)：對(duì)照未使用RF的Broadcast Hash Join來(lái)看，前者主要增加了bloomfilter的生成、廣播以及大表根據(jù)bloomfilter進(jìn)行過(guò)濾這三個(gè)開(kāi)銷(xiāo)荡短。通常情況下弯院，這幾個(gè)步驟在小表較小的情況下代價(jià)并不大头岔，基本可以忽略娩鹉。

RF優(yōu)化效果：基本取決于bloomfilter的過(guò)濾效果受楼，如果大量數(shù)據(jù)被過(guò)濾掉了，那么join的性能就會(huì)得到極大提升捐祠；否則性能提升就會(huì)有限率拒。

RF實(shí)現(xiàn)：和常見(jiàn)的謂詞下推（’=‘，’>’靴寂，’<‘等）一樣剖踊，RF實(shí)現(xiàn)需要在計(jì)算層以及存儲(chǔ)層分別進(jìn)行相關(guān)邏輯實(shí)現(xiàn)梆造，計(jì)算層要構(gòu)造bloomfilter并將bloomfilter下傳到存儲(chǔ)層罕模，存儲(chǔ)層要實(shí)現(xiàn)使用該bloomfilter對(duì)指定數(shù)據(jù)進(jìn)行過(guò)濾祸轮。

RF效果驗(yàn)證

事實(shí)上，RF這個(gè)東東的優(yōu)化效果是在組內(nèi)同事何大神做impala on parquet以及impala on kudu的基準(zhǔn)對(duì)比測(cè)試的時(shí)候分析發(fā)現(xiàn)的侥钳。實(shí)際測(cè)試中适袜，impala on parquet 比之impala on kudu性能有明顯優(yōu)勢(shì)，目測(cè)至少10倍性能提升舷夺。同一SQL解析引擎苦酱，不同存儲(chǔ)引擎售貌，性能竟然天壤之別！為了分析具體原因疫萤，同事就使用impala的執(zhí)行計(jì)劃分析工具對(duì)兩者的執(zhí)行計(jì)劃分別進(jìn)行了分析颂跨，才透過(guò)蛛絲馬跡發(fā)現(xiàn)前者使用了RF，而后者并沒(méi)有（當(dāng)然可能還有其他因素扯饶，但RF肯定是原因之一）恒削。

簡(jiǎn)單復(fù)盤(pán)一下這次測(cè)試吧，基準(zhǔn)測(cè)試使用TPCDS測(cè)試尾序，數(shù)據(jù)規(guī)模為1T钓丰，本文使用測(cè)試過(guò)程中的一個(gè)典型SQL（Q40）作為示例對(duì)RF的神奇功效進(jìn)行回放演示。下圖是Q40的對(duì)比性能每币，直觀上來(lái)看RF可以直接帶來(lái)40x的性能提升携丁，40倍哎，這到底是怎么做到的脯爪？

先來(lái)簡(jiǎn)單看看Q40的SQL語(yǔ)句则北，如下所示，看起來(lái)比較復(fù)雜痕慢，核心涉及到3個(gè)表（catalog_sales join date_dim 尚揣、catalog_sales join warehouse 、catalog_sales join item）的join操作：

select??

???w_state

??,i_item_id

??,sum(case?when?(cast(d_date?as?date)?<?cast?(‘1998-04-08’?as?date))?

????????????????then?cs_sales_price?–?coalesce(cr_refunded_cash,0)?else?0?end)?as?sales_before

??,sum(case?when?(cast(d_date?as?date)?>=?cast?(‘1998-04-08’?as?date))?

????????????????then?cs_sales_price?–?coalesce(cr_refunded_cash,0)?else?0?end)?as?sales_after

?from

???catalog_sales?left?outer?join?catalog_returns?on

???????(catalog_sales.cs_order_number?=?catalog_returns.cr_order_number?

????????and?catalog_sales.cs_item_sk?=?catalog_returns.cr_item_sk)

??,warehouse?

??,item

??,date_dim

?where

?????i_current_price?between?0.99?and?1.49

?and?item.i_item_sk??????????=?catalog_sales.cs_item_sk

?and?catalog_sales.cs_warehouse_sk????=?warehouse.w_warehouse_sk?

?and?catalog_sales.cs_sold_date_sk????=?date_dim.d_date_sk

?and?date_dim.d_date?between?‘1998-03-09’?and?‘1998-05-08’

?group?by

????w_state,i_item_id

?order?by?w_state,i_item_id

limit?100;

典型的星型結(jié)構(gòu)掖举，其中catalog_sales是事實(shí)表快骗，其他表為緯度表。本次分析選擇其中catalog_sales join item這個(gè)緯度的join塔次。因?yàn)閷?duì)比測(cè)試中兩者的SQL解析引擎都是使用impala方篮，所以SQL執(zhí)行計(jì)劃基本都相同。在此基礎(chǔ)上励负，來(lái)看看執(zhí)行計(jì)劃中單個(gè)執(zhí)行節(jié)點(diǎn)在執(zhí)行catalog_sales join item操作時(shí)由先到后的主要階段耗時(shí)藕溅，其中只貼出來(lái)重要耗時(shí)階段（Q40中Join算法為shuffle hash join，與上文所舉broadcast hash join示例略有不同继榆，不過(guò)不影響結(jié)論）：

經(jīng)過(guò)對(duì)兩種場(chǎng)景執(zhí)行計(jì)劃的解析巾表，可以基本驗(yàn)證上文所做的基本理論結(jié)果：

1. 確認(rèn)經(jīng)過(guò)RF之后大表的數(shù)據(jù)量得到大量濾除，只剩下少量數(shù)據(jù)參與最終的HashJoin略吨。參見(jiàn)第二行大表scan掃描結(jié)果集币，未使用rf的返回結(jié)果有7千萬(wàn)行＋紀(jì)錄，而經(jīng)過(guò)RF過(guò)濾之后滿足條件的只有3w＋紀(jì)錄翠忠。3萬(wàn)相比7千萬(wàn)鞠苟，性能優(yōu)化效果自然不言而喻。

2. 經(jīng)過(guò)RF濾除之后，少量數(shù)據(jù)經(jīng)過(guò)網(wǎng)絡(luò)從存儲(chǔ)進(jìn)程加載到計(jì)算進(jìn)程內(nèi)存的網(wǎng)絡(luò)耗時(shí)大量減少当娱。參見(jiàn)第三行“數(shù)據(jù)加載到計(jì)算進(jìn)程內(nèi)存”吃既，前者耗時(shí)15s，后者耗時(shí)僅僅11ms趾访。主要耗時(shí)分為兩部分态秧，其中數(shù)據(jù)序列化時(shí)間占到2/3－10s左右，數(shù)據(jù)經(jīng)過(guò)RPC傳輸時(shí)間占另外1/3 －5s左右扼鞋。

3. 最后申鱼，經(jīng)過(guò)RF濾除之后，參與到最終Hash Join的數(shù)據(jù)量大幅減少云头，Hash Join耗時(shí)前者是19s捐友，后者是21ms左右。主要耗時(shí)在于大表Probe Time溃槐，前者消耗了17s左右匣砖，而后者僅需6ms。

說(shuō)好的謂詞下推呢昏滴？

講真猴鲫，剛開(kāi)始接觸RF的時(shí)候覺(jué)得這簡(jiǎn)直是一個(gè)實(shí)實(shí)在在的神器，崇拜之情溢于言表谣殊。然而拂共，經(jīng)過(guò)一段時(shí)間的探索消化，直至把這篇文章寫(xiě)完姻几，也就是此時(shí)此刻宜狐，忽然覺(jué)得它并不高深莫測(cè)，說(shuō)白了就是一個(gè)謂詞下推蛇捌，不同的是這里的謂詞稍微奇怪一點(diǎn)抚恒，是一個(gè)bloomfilter而已。

提到謂詞下推络拌，這里再引申一下下俭驮。以前經(jīng)常滿大街聽(tīng)到謂詞下推，然而對(duì)謂詞下推卻總感覺(jué)懵懵懂懂春贸，并不明白的很真切混萝。經(jīng)過(guò)RF的洗禮，現(xiàn)在確信有了更進(jìn)一步的理解祥诽。這里拿出來(lái)和大家交流交流譬圣。個(gè)人認(rèn)為謂詞下推有兩個(gè)層面的理解：

其一是邏輯執(zhí)行計(jì)劃優(yōu)化層面的說(shuō)法瓮恭，比如SQL語(yǔ)句：select * from order ,item where item.id = order.item_id and item.category =?‘book’雄坪，正常情況語(yǔ)法解析之后應(yīng)該是先執(zhí)行Join操作，再執(zhí)行Filter操作。通過(guò)謂詞下推维哈，可以將Filter操作下推到Join操作之前執(zhí)行绳姨。即將where item.category =?‘book’下推到 item.id = order.item_id之前先行執(zhí)行。

其二是真正實(shí)現(xiàn)層面的說(shuō)法阔挠，謂詞下推是將過(guò)濾條件從計(jì)算進(jìn)程下推到存儲(chǔ)進(jìn)程先行執(zhí)行飘庄，注意這里有兩種類(lèi)型進(jìn)程：計(jì)算進(jìn)程以及存儲(chǔ)進(jìn)程。計(jì)算與存儲(chǔ)分離思想购撼，這在大數(shù)據(jù)領(lǐng)域相當(dāng)常見(jiàn)跪削，比如最常見(jiàn)的計(jì)算進(jìn)程有SparkSQL、Hive迂求、impala等碾盐，負(fù)責(zé)SQL解析優(yōu)化、數(shù)據(jù)計(jì)算聚合等揩局，存儲(chǔ)進(jìn)程有HDFS（DataNode）毫玖、Kudu、HBase凌盯，負(fù)責(zé)數(shù)據(jù)存儲(chǔ)付枫。正常情況下應(yīng)該是將所有數(shù)據(jù)從存儲(chǔ)進(jìn)程加載到計(jì)算進(jìn)程，再進(jìn)行過(guò)濾計(jì)算驰怎。謂詞下推是說(shuō)將一些過(guò)濾條件下推到存儲(chǔ)進(jìn)程阐滩，直接讓存儲(chǔ)進(jìn)程將數(shù)據(jù)過(guò)濾掉。這樣的好處顯而易見(jiàn)砸西，過(guò)濾的越早叶眉，數(shù)據(jù)量越少，序列化開(kāi)銷(xiāo)芹枷、網(wǎng)絡(luò)開(kāi)銷(xiāo)衅疙、計(jì)算開(kāi)銷(xiāo)這一系列都會(huì)減少，性能自然會(huì)提高鸳慈。

寫(xiě)到這里饱溢，忽然意識(shí)到筆者在上文出現(xiàn)了一個(gè)很?chē)?yán)重的認(rèn)知錯(cuò)誤：RF機(jī)制并不僅僅是一個(gè)簡(jiǎn)單的謂詞下推，它的精髓在于提出了一個(gè)重要的謂詞－bloomfilter走芋。當(dāng)前對(duì)RF支持的系統(tǒng)并不多绩郎，筆者只知道目前唯有Impala on Parquet進(jìn)行了支持。Impala on Kudu雖說(shuō)Impala支持翁逞，但Kudu并不支持肋杖。SparkSQL on Parqeut中雖有存儲(chǔ)系統(tǒng)支持，無(wú)奈計(jì)算引擎－SparkSQL目前還不支持挖函。

本文主要介紹了一種類(lèi)似于semi-join的優(yōu)化方法状植，對(duì)優(yōu)化細(xì)節(jié)進(jìn)行了深入地探討，并結(jié)合分析過(guò)程對(duì)謂詞下推技術(shù)談了談自己的理解。下篇文章將會(huì)為看官帶來(lái)基于代價(jià)優(yōu)化（CBO）相關(guān)的議題津畸，期待哦～