Jindo SQL性能優(yōu)化實例分析

本文小編為大家詳細介紹“Jindo SQL性能優(yōu)化實例分析”，內(nèi)容詳細，步驟清晰，細節(jié)處理妥當(dāng)，希望這篇“Jindo SQL性能優(yōu)化實例分析”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學(xué)習(xí)新知識吧。

背景介紹

TPC-DS 測試集采用星型和雪花型等多維數(shù)據(jù)模型，包含 7 張事實表和 17 張維度表，以 store channel 為例，事實表和維度表的關(guān)聯(lián)關(guān)系如下所示：

分析 TPC-DS 全部 99 個查詢語句不難發(fā)現(xiàn)，絕大部分語句的過濾條件都不是直接作用于事實表，而是通過過濾維度表并將結(jié)果集與事實表 join 來間接完成。因此，優(yōu)化器很難直接利用事實表索引來減少數(shù)據(jù)掃描量。如何利用好查詢執(zhí)行時的維度表過濾信息，并將這些信息下推至存儲層來完成事實表的過濾，對于性能提升至關(guān)重要。

在 2019 年的打榜測試中，我們基于 Spark SQL Catalyst Optimizer 開發(fā)的 RuntimeFilter 優(yōu)化 對于 10TB 數(shù)據(jù) 99 query 的整體性能達到 35% 左右的提升。簡單來說，RuntimeFilter 包括兩點核心優(yōu)化：

1. 動態(tài)分區(qū)裁剪：事實表以日期列（date_sk）為分區(qū)列建表，當(dāng)事實表與 date_dim 表 join 時，optimizer 在運行時收集 date_dim 過濾結(jié)果集的所有 date_sk 取值，并在掃描事實表前過濾掉所有未命中的分區(qū)文件。

2. 非分區(qū)列動態(tài)過濾：當(dāng)事實表與維度表的 join 列為非分區(qū)列時，optimizer 動態(tài)構(gòu)建和收集維度表結(jié)果集中 join 列的 Min-Max Range 或 BloomFilter，并在掃描事實表時下推至存儲層，利用存儲層索引（如 Parquet、ORCFile 的 zone map 索引）來減少掃描數(shù)據(jù)量。

問題分析

為了進一步挖掘 RuntimeFilter 優(yōu)化的潛力，我們選取了部分執(zhí)行時間較長的 query 進行了細致的性能剖析。這些 query 均包含大于一個事實表和多個維度表的復(fù)雜 join。在分析了 RuntimeFilter 對各個 query 的性能提升效果后，我們發(fā)現(xiàn)：

1. 動態(tài)分區(qū)裁剪的性能提升效果明顯，但很難有進一步的優(yōu)化空間

2. 非分區(qū)列動態(tài)過濾對整體提升貢獻相比分區(qū)裁剪小很多，主要是因為很多下推至存儲層的過濾條件并沒有達到索引掃描的效果

聰明的同學(xué)應(yīng)該已經(jīng)發(fā)現(xiàn)，只有 date_dim 這一張維度表和分區(qū)列相關(guān)，那么所有與其它維度表的 join 查詢從 RuntimeFilter 優(yōu)化中受益都較為有限。對于這種情況，我們做了進一步的拆解分析：

1. 絕大部分 join 列均為維度表的自增主鍵，且與過濾條件沒有相關(guān)性，因此結(jié)果集取值常常均勻稀疏地散布在該列的整個取值空間中

2. 對于事實表，考慮最常見的 Zone Map 索引方式，由于 load 階段沒有針對非分區(qū)列做任何聚集操作（Clustering），每個 zone 的取值一般也稀疏分散在各個列的值域中。

3. 相比 BloomFilter，Min-Max Range 的構(gòu)建開銷和索引查詢開銷要低得多，但由于信息粒度太粗，索引過濾命中的效果也會差很多

綜合以上幾點考慮，一種可能的優(yōu)化方向是在 load 階段按照 join 列對事實表進行 Z-Order 排序。但是這種方式會顯著增加 load 階段執(zhí)行時間，有可能導(dǎo)致 TPC-DS 評測總分反而下降。同時，由于建表階段優(yōu)化的復(fù)雜性，實際生產(chǎn)環(huán)境的推廣使用也會比較受限。

RuntimeFilter Plus

基于上述分析，我們認為依賴過濾條件下推至存儲層這一方式很難再提升查詢性能，嘗試往其它方向進行探索：

1. 不依賴存儲層索引

2. 不僅優(yōu)化事實表與維度表 join

最終我們提煉兩個新的運行時過濾優(yōu)化點：維度表過濾廣播和事實表 join 動態(tài)過濾，并在原版 RuntimeFilter 優(yōu)化的基礎(chǔ)上進行了擴展實現(xiàn)。

維度表過濾廣播

其針對的場景如下圖所示：

當(dāng)事實表（lineorder）連續(xù)與多個維度表過濾結(jié)果做 multi-join 時，可將所有維度表的過濾信息下推至 join 之前。該方法與我們的 RuntimeFilter 的主要不同在于下推時考慮了完整的 multi-join tree 而不是局部 binary-join tree。其優(yōu)化效果是即使 join ordering 為 bad case，無用的事實表數(shù)據(jù)也能夠被盡早過濾掉，即讓查詢執(zhí)行更加 robust。

我們參考論文算法實現(xiàn)了第一版過濾下推規(guī)則，但并沒有達到預(yù)期的性能提升，主要原因在于：

1. Spark CBO Join-Reorder 結(jié)合我們的遺傳算法優(yōu)化，已經(jīng)達到了接近最優(yōu)的 join ordering 效果

2. 前置的 LIP filters 執(zhí)行性能并沒有明顯優(yōu)于 Spark BroadcastHashJoin 算子

基于過濾條件可以傳遞至復(fù)雜 multi-join tree 的任意節(jié)點這一思想去發(fā)散思考，我們發(fā)現(xiàn)，當(dāng) multi-join tree 中存在多個事實表時，可將維度表過濾條件廣播至所有的事實表 scan，從而減少后續(xù)事實表 SortMergeJoin 等耗時算子執(zhí)行時所需處理的數(shù)據(jù)量。以一個簡化版的 query 64 為例：

with cs_ui as(select cs_item_sk,sum(cs_ext_list_price) as salefrom catalog_sales,catalog_returnswhere cs_item_sk = cr_item_skand cs_order_number = cr_order_numbergroup by cs_item_sk)select i_product_name product_name,i_item_sk item_sk,sum(ss_wholesale_cost) s1from store_sales,store_returns,cs_ui,itemwhere ss_item_sk = i_item_sk andss_item_sk = sr_item_sk andss_ticket_number = sr_ticket_number andss_item_sk = cs_ui.cs_item_sk andi_color in ('almond','indian','sienna','blue','floral','rosy') andi_current_price between 19 and 19 + 10 andi_current_price between 19 + 1 and 19 + 15group by i_product_name,i_item_sk

該查詢的 plan tree 如下圖所示：

考慮未實現(xiàn)維度表過濾廣播的執(zhí)行流程，store_sales 數(shù)據(jù)經(jīng)過 RuntimeFilter 和 BroadcastHashJoin 算子進行過濾，但由于過濾后數(shù)據(jù)仍然較大，后續(xù)的所有 join 都需要走昂貴的 SortMergeJoin 算子。但如果將 LIP filter 下推至 4 張事實表的 scan 算子（無需下推至存儲層），不僅減少了 join 數(shù)據(jù)量，也減少了 catalog_sales 和 catalog_returns 表 join 后的 group-by aggregation 數(shù)據(jù)量 。

LIP 實現(xiàn)

在 optimizer 層，我們在原版 RuntimeFilter 的 SyntheticJoinPredicate 規(guī)則后插入 PropagateDynamicValueFilter 規(guī)則，將合成的動態(tài)謂詞廣播至所有合法的 join 子樹中；同時結(jié)合原有的謂詞下推邏輯，保證動態(tài)謂詞最終傳播到所有相關(guān)的 scan 算子上。在算子層，LIP filters 的底層實現(xiàn)可以是 HashMap 或 BloomFilter，針對 TPC-DS 的數(shù)據(jù)特性，我們選擇 BitMap 作為廣播過濾條件的底層實現(xiàn)。由于 BitMap 本身是精確的（Exact Filter），可以結(jié)合主外鍵約束信息進一步做 semi-join 消除優(yōu)化。基于主外鍵約束的優(yōu)化規(guī)則將在系列后續(xù)文章做詳細介紹。

應(yīng)用該優(yōu)化后，query 64 執(zhí)行時間由 177 秒降低至 63 秒，加速比達到 2.8 倍。

事實表 Join 動態(tài)過濾

使用 BloomFilter 來優(yōu)化大表 join 是一種常見的查詢優(yōu)化技術(shù)，比如在論文《Building a Hybrid Warehouse: Efficient Joins between Data Storedin HDFS and Enterprise Warehouse》https://researcher.watson.ibm.com/researcher/files/us-ytian/published_tods.pdf 中提出對 join 兩表交替應(yīng)用 BloomFilter 的 zig-zag join 方法，降低分布式 join 中的數(shù)據(jù)傳輸總量。對于 TPC-DS 測試集，以 query 93 為例，store_sales 與 store_returns join 后的結(jié)果集大小遠小于 store_sales 原始數(shù)據(jù)量，非常適合應(yīng)用這一優(yōu)化。

BloomFilter 的構(gòu)建和應(yīng)用都存在較高的計算開銷，對于 selectivity 較大的join，盲目使用這一優(yōu)化可能反而導(dǎo)致性能回退。基于靜態(tài) stats 的 join selectivity 估算往往誤差，Spark 現(xiàn)有的 CBO 優(yōu)化規(guī)則難以勝任魯棒的 BloomFilter join 優(yōu)化決策。因此，我們基于 Spark Adaptive Execution（AE） 運行時重優(yōu)化機制來實現(xiàn)動態(tài)的 BloomFilter join 優(yōu)化規(guī)則。AE 的基本原理是在查詢作業(yè)的每個 stage 執(zhí)行完成后，允許優(yōu)化器根據(jù)運行時采集的 stage stats 信息重新調(diào)整后續(xù)的物理執(zhí)行計劃。目前主要支持三種優(yōu)化：
（1）reduce stage 并發(fā)度調(diào)整；
（2）針對 skew 情況的 shuffle 數(shù)據(jù)均衡分布；
（3）SortMergeJoin 轉(zhuǎn)換為 BroadcastHashJoin

基于 AE 的優(yōu)化規(guī)則流程如下：

1. 根據(jù)靜態(tài) stats 判斷 join 的一端的 size 是否可能適合構(gòu)建 BloomFilter（ build side），如果是，則 build side 和 stream side 的 scan stage 會依次串行提交執(zhí)行；否則這兩個 stage 將并行執(zhí)行。

2. 在 build side 的 scan stage 執(zhí)行完成后，AE 根據(jù)運行時收集的 size 和 join 列 histogram 進行代價估算，并決定最終走 BroadcastHashJoin、BloomFilter-SortMergeJoinJoin 還是原本的 SortMergeJoin。

3. 當(dāng)物理執(zhí)行計劃為 BloomFilter-SortMergeJoinJoin，優(yōu)化器會插入一個新的作業(yè)并行掃描 build side 的 shuffle 數(shù)據(jù)來構(gòu)建 BloomFilter，并下推至 stream side 的 scan stage 中。

BloomFilter 算子實現(xiàn)

為了減少 BloomFilter 帶來的額外開銷，我們重新實現(xiàn)了高效的 BuildBloomFiler 和 Native-InBloomFilter 的算子。在構(gòu)建階段，使用 RDD aggregate 來合并各個數(shù)據(jù)分片的 BloomFiler 會導(dǎo)致 driver 成為數(shù)據(jù)傳輸和 bitmap 合并計算的性能瓶頸；使用 RDD treeAggregate 實現(xiàn)并行分層合并顯著降低了整體的構(gòu)建延遲。在過濾階段，Native-InBloomFilter 的算子會被推入 scan 算子中合并執(zhí)行。該算子直接訪問 Spark 列式讀取內(nèi)存格式，按批量數(shù)據(jù)來調(diào)用 SIMD 優(yōu)化的 native 函數(shù)，降低 CPU 執(zhí)行開銷；同時，我們將原版算法替換為 Blocked BloomFilter 算法實現(xiàn)，該算法通過犧牲少量的 bitmap 存儲空間來換取訪存時更低的 CPU cache miss 率。

應(yīng)用該優(yōu)化后，query 93 執(zhí)行時間由 225 秒降低至 50 秒，加速比達到 4.5 倍。

讀到這里，這篇“Jindo SQL性能優(yōu)化實例分析”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領(lǐng)會，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。