SQL優化器原理 - Auto Hash Join

這是maxcompute有關sql優化器原理的系列文章之一。我們會陸續推出sql優化器有關優化規則和架構的其他文章。添加釘釘群“關系代數優化技術”（群号11719083）可以擷取最新文章釋出動态(二維碼在文章末尾)。

本文主要描述maxcompute優化器實作的auto hash join的功能。

在maxcompute中，join操作符的實作算法之一名為"hash join"，其實作原理是，把小表的資料全部讀入記憶體中，并拷貝多份分發到大表資料所在機器，在 map 階段直接掃描大表資料與記憶體中的小表資料進行比對。hash join執行方式效率很高，但是要求小表資料足夠小以便放到記憶體中，假如小表資料太大，則任務在執行過程中會報outofmemory錯誤。

在mapcompute中，可以使用mapjoin關鍵字來實作hash join，如下所示：

但是這種通過使用hint的方式還是不夠智能。另外對于query複雜的情況，使用者很可能因為無法确定join的某一路資料量大小而放棄使用mapjoin。在最新的maxcompute sql 2.0中，基于代價的優化器（cost based optimizer，cbo）包含了一個自動優化join為hash join的優化規則。

在cbo中會對所有的operator的cost進行估計，這個cost包含rowcount、cpu、記憶體等等。有了各個operator的cost，就能估計其對應輸出資料量的大小,公式可以簡單的認為是：<code>data_size = rowcount * averagerowsize</code>。有了datasize之後，就可以很容易知道這個任務是否适合使用hashjoin，其判定方法就是計算各個parent operator的data size之和是否小于某個門檻值。假如估算出的data size在門檻值範圍之内，則會産生一個包含hashjoin的計劃。同時對于join，cbo也會産生一個普通的包含mergejoin的計劃，最後在這兩個計劃中選擇cost最小的作為最優計劃。

簡單說來，在cbo中是否選擇hashjoin作為最優計劃的步驟有兩個：

step1：估算join的輸入資料量大小，判定是否産生一個包含hashjoin的計劃

step2：對比hashjoin、mergejoin相關計劃的cost，選擇cost最小的計劃作為最優計劃

舉例，對如下sql進行優化：

上述sql在cbo中會翻譯生成如下operator tree:

從上可以看到，join的parent operator有兩個：

其中id為1的project其輸出記錄數是4行，且其輸出列隻有1列（bad_tpch_customer表中有5列），估算其輸出資料量，認為其适合使用hashjoin，是以其産生的計劃中包含兩種：

計劃1：hashjoin

計劃2：mergejoin

比較上述兩個計劃的cost，明顯計劃1的cost更小，是以選擇包含hashjoin的計劃1作為最優計劃。

autohashjoin的一個很大的好處是能讓使用者免參與的進行這個優化，同時對于一些複雜的query也更有可能使用hashjoin。但是，因為cbo無法完美估計資料量，會出現誤判進而導緻任務oom的情況。針對這種情況，maxcompute也進行了相應的調整，對于cbo誤判導緻hashjoin oom的任務會關閉hashjoin rule來重試。

目前cbo中使用hashjoin的門檻值比較保守，預設是25mb。主要原因是cbo對于資料量的估計有偏差，無法完美估計資料量，而估計不準的原因有兩個：

資料是壓縮存儲的，cbo拿到的statistics不準

cbo的估計算法有偏差

這兩個問題也是cbo緻力解決的問題。