Apache Spark 2.2最近引入了進階的基于成本的優化器架構用于收集并均衡不同的列資料的統計工作 (例如., 基（cardinality）、唯一值的數量、空值、最大最小值、平均/最大長度，等等）來改進查詢類作業的執行計劃。均衡這些作業幫助Spark在選取最優查詢計劃時做出更好決定。這些優化的例子包括在做hash-join時選擇正确的一方建hash，選擇正确的join類型（廣播hash join和全洗牌hash-join）或調整多路join的順序，等等）
在該部落格中，我們将深入講解Spark的基于成本的優化器（CBO）并讨論Spark是如何收集并存儲這些資料、優化查詢，并在壓力測試查詢中展示所帶來的性能影響。
在Spark2.2核心，Catalyst優化器是一個統一的庫，用于将查詢計劃表示成多顆樹并依次使用多個優化規則來變換他們。大部門優化規則都基于啟發式，例如，他們隻負責查詢的結構且不關心要處理資料的屬性，這樣嚴重限制了他們的可用性。讓我們用一個簡單的例子來示範。考慮以下的查詢，該查詢過濾大小為500GB的t1表并與另一張大小為20GB的t2表做join操作。Spark使用hash join，即選擇小的join關系作為建構hash表的一方并選擇大的join關系作為探測方。由于t2表比t1表小, Apache Spark 2.1 将會選擇右方作為建構hash表的一方而不是對其進行過濾操作（在這個案例中就是會過濾出t1表的大部分資料）。選擇錯誤那方做建構hash表經常會導緻系統由于記憶體限制的原因去放棄快速hash join而使用排序-歸并 join（sort-merge join）。
而Apache Spark 2.2卻不這麼做,它會收集每個操作的統計資訊 并發現左方在過濾後大小隻有100MB (1 百萬條紀錄) ，而過濾右方會有20GB (1億條紀錄)。有了兩側正确的表大小/基的資訊，Spark 2.2會選擇左方為建構方，這種選擇會極大加快查詢速度。
為了改進查詢執行計劃的品質，我們使用詳細的統計資訊加強了Spark SQL優化器。從詳細的統計資訊中，我們傳播統計資訊到别的操作子（因為我們從下往上周遊查詢樹）。傳播結束，我們可以估計每個資料庫操作子的輸出記錄數和輸出紀錄的大小，這樣就可以得到一個高效的查詢計劃。
CBO依賴細節化的統計資訊來優化查詢計劃。要收集這些統計資訊，使用者可以使用以下這些新的SQL指令：
上面的 SQL 語句可以收集表級的統計資訊，例如記錄數、表大小（機關是byte）。這裡需要注意的是ANALYZE, COMPUTE, and STATISTICS都是保留的關鍵字，他們已特定的列名為入參，在metastore中儲存表級的統計資訊。
需要注意的是在ANALYZE 語句中沒必要指定表的每個列-隻要指定那些在過濾/join條件或group by等中涉及的列
下表列出了所收集的統計資訊的類型，包括數字類型、日期、時間戳和字元串、二進制資料類型
由于CBO是以後續方式周遊Spark的邏輯計劃樹，我們可以自底向上地把這些統計資訊傳播到其他操作子。雖然我們要評估的統計資訊及對應開銷的操作子有很多，我們将講解兩個最複雜且有趣的操作子FILTER 和JOIN的評估統計資訊的流程。
過濾條件是配置在SQL SELECT語句中的WHERE 子句的謂語表達式。謂語可以是包含了邏輯操作子AND、OR、NOT且包含了多個條件的複雜的邏輯表達式 。單個條件通常包含比較操作子，例如=, <, <=, >, >= or <=>。是以，根據全部過濾表達式來估計選擇是非常複雜的。
我們來示範對包含多個條件邏輯表達式的複雜邏輯表達式做過濾選擇 的一些計算。
對于邏輯表達式AND，他的過濾選擇是左條件的選擇乘以右條件選擇，例如fs(a AND b) = fs(a) * fs (b)。
對于邏輯表達式OR，他的過濾選擇是左條件的選擇加上右條件選擇并減去左條件中邏輯表達式AND的選擇，例如 fs (a OR b) = fs (a) + fs (b) - fs (a AND b) = fs (a) + fs (b) – (fs (a) * fs (b))
對于邏輯表達式NOT，他的過濾因子是1.0 減去原表達式的選擇，例如 fs (NOT a) = 1.0 - fs (a)
現在我們看下可能有多個操作子的單個邏輯條件例如 =, <, <=, >, >= or <=>。對于單個操作符作為列，另一個操作符為字元串的情況，我們先計算等于 (=) 和小于 (<) 算子的過濾選擇。其他的比較操作符也是類似。
等于操作符 (=) :我們檢查條件中的字元串常量值是否落在列的目前最小值和最大值的區間内 。這步是必要的，因為如果先使用之前的條件可能會導緻區間改變。如果常量值落在區間外，那麼過濾選擇就是 0.0。否則，就是去重後值的反轉（注意：不包含額外的柱狀圖資訊，我們僅僅估計列值的統一分布）。後面釋出的版本将會均衡柱狀圖來優化估計的準确性。
小于操作符 (<) :檢查條件中的字元串常量值落在哪個區間。如果比目前列值的最小值還小，那麼過濾選擇就是 0.0(如果大于最大值，選擇即為1.0)。否則，我們基于可用的資訊計算過濾因子。如果沒有柱狀圖，就傳播并把過濾選擇設定為: (常量值– 最小值) / (最大值 – 最小值)。另外，如果有柱狀圖，在計算過濾選擇時就會加上在目前列最小值和常量值之間的柱狀圖桶密度 。同時，注意在條件右邊的常量值此時變成了該列的最大值。
我們已經讨論了過濾選擇， 現在讨論join的輸出基。在計算二路join的輸出基之前，我們需要先有雙方孩子節點的輸出基 。每個join端的基都不會超過原表記錄數的基。更準确的說，是在執行join操作子之前，執行所有操作後得到的有效紀錄數。在此，我們偏好計算下內連接配接（inner join）操作的基因為它經常用于演化出其他join類型的基。我們計算下在 A.k = B.k 條件下A join B 的記錄數 ，即
num(A IJ B) = num(A)*num(B)/max(distinct(A.k),distinct(B.k))
num(A) 是join操作上一步操作執行後表A的有效記錄數, distinct是join列 k唯一值的數量。
如下所示，通過計算内連接配接基，我們可以大概演化出其他join類型的基:
左外連接配接（Left-Outer Join）: num(A LOJ B) = max(num(A IJ B),num(A)) 是指内連接配接輸出基和左外連接配接端A的基之間較大的值。這是因為我們需要把外端的每條紀錄計入，雖然他們沒有出現在join輸出紀錄内。
Right-Outer Join: num(A ROJ B) = max(num(A IJ B),num(B))
Full-Outer Join: num(A FOJ B) = num(A LOJ B) + num(A ROJ B) - num(A IJ B)
現在我們已經有了資料統計的中間結果，讓我們讨論下如何使用這個資訊來選擇最佳的查詢計劃。早先我們解釋了在hash join操作中根據精确的基和統計資訊選擇建構方。
同樣，根據确定的基和join操作的前置所有操作的大小估計，我們可以更好的估計join測的大小來決定該測是否符合廣播的條件。
大部分資料庫優化器将CPU和I/O計入考慮因素，分開考慮成本來估計總共的操作開銷。在Spark中，我們用簡單的公式估計join操作的成本：
公式的第一部分對應CPU成本粗略值，第二部分對應IO。一顆join樹的成本是所有中間join成本的總和。
我們使用非侵入式方法把這些基于成本的優化加入到Spark，通過加入全局配置spark.sql.cbo.enabled來開關這個特性。在Spark 2.2, 這個參數預設是false 。短期内有意設定該特性預設為關閉，因為的Spark被上千家公司用于生産環境，預設開啟該特性可能會導緻生産環境壓力變大進而導緻不良後果。
在四個節點 (單台配置：Huawei FusionServer RH2288 , 40 核和384 GB 記憶體) 的叢集用TPC-DS來測試Apache Spark 2.2查詢性能。在四個節點的叢集運作測試查詢性能的語句并設比例因子為1000（大概1TB資料）。收集全部24張表（總共245列）的統計資訊大概要14分鐘。
在校驗端到端的結果前，我們先看一條查詢語句TPC-DS(Q25; 如下所示)來更好了解基于成本的join排序帶來的威力。這句查詢語句包括三張事實表: store_sales (29 億行紀錄), store_returns (2.88 億行紀錄) 和catalog_sales (14.4 億行紀錄). 同時也包括三張次元表: date_dim(7.3萬行紀錄), store (1K 行紀錄) 和 item (300K 行紀錄).
<a></a>
我們先看下沒使用基于成本優化的Q25的join樹(如下)。一般這種樹也叫做左線性樹。這裡, join #1 和 #2 是大的事實表與事實表join，join了3張事實表store_sales, store_returns, 和catalog_sales，并産生大的中間結果表。這兩個join都以shuffle join的方式執行并會産生大的輸出，其中join #1輸出了1.99億行紀錄。總之，關閉CBO,查詢花費了241秒。
另一方面，用了CBO,Spark建立了優化方案可以減小中間結果（如下）。在該案例中，Spark建立了濃密樹而不是左-深度樹。在CBO規則下,Spark 先join 的是事實表對應的次元表 (在嘗試直接join事實表前)。避免大表join意味着避免了大開銷的shuffle。在這次查詢中，中間結果大小縮小到原來的1/6（相比之前）。最後，Q25隻花了71秒，性能提升了3.4倍。
現在我們對性能提升的原因有了直覺感受，我們再看下端到端的TPC-DS查詢結果。下表展示了使用CBO或沒使用CBO下所有TPC-DS查詢花費的:
首先，要注意的是一半TPC-DS性能查詢沒有性能的改變。這是因為使用或沒使用CBO的查詢計劃沒有不同 (例如，即使沒有CBO, Spark’s Catalyst 優化器的柱狀圖也可以優化這些查詢。剩下的查詢性能都有提升，最有意思的其中16個查詢，CBO對查詢計劃進行巨大改變并帶來了超過30%的性能提升（如下）總的來說，我們觀察的圖示說明16個查詢大概加速了2.2倍，其中Q72 加速最大，達到了8倍。
回顧前文，該部落格展示了Apache Spark 2.2新的CBO不同的高光層面的。我們讨論了統計資訊收集架構的細節、過濾和join時的基傳播、CBO開啟（選擇建構方和多路重排序）以及TPC-DS查詢性能的提升。
我們對已經取得的進展感到十分興奮并希望你們喜歡這些改進。我們希望你們能在Apache Spark 2.2中嘗試新的CBO!
原理就是較小的關系更容易放到記憶體
<=> 表示‘安全的空值相等’ ，如果兩邊的結果都是null就傳回true，如果隻有一邊是null就傳回false
P. Griffiths Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, T. G. Price, “Access Path Selection in a Relational Database Management System”, Proceedings of ACM SIGMOD conference, 1979
weight（權值）是調優參數，可以通過配置 spark.sql.cbo.joinReorder.card.weight (預設是0.7)
本文轉自shishanyuan部落格園部落格，原文連結： http://www.cnblogs.com/shishanyuan/p/8453587.html ，如需轉載請自行聯系原作者