TPC-H可以說是世界上最為流行的OLAP workload的benchmark程式，無論你看什麼樣的論文或技術文章，隻要是和query processing相關的，大多會在evaluation時使用TPC-H作為評估工具。而如果你從事query optimization/query execution的工作，則怎麼都會和TPC-H打上交道，即使是TP型的資料庫系統。
TPC-H是用來評估線上分析處理的基準程式，主要模拟了一個供應商和采購商之間的交易行為，其中包含針對8張表的22條分析型查詢。
- Power 單并發測試，單線程執行22條Query+ RF（INSERT + DELETE）
- Throughput多并發測試，N個查詢線程+ 1個insert/delete 線程
而綜合的打分是
這篇paper很有趣也很有幫助，它并不詳盡的描述某個技術，而且深入的分析了TPC-H的query中，可能存在的性能優化點和對應的優化思路。
它的基本思想是，作為一種流行且優秀的benchmark工具，它不僅可以用來作為對query processing系統的橫向比較工具，更應該在benchmark中隐含一些具有技術挑戰的點，為了具有更好的性能成績，各路廠商會使用不同的解決方案去攻克這些點，而這也從側面引領了技術發展的潮流。TPC-H在這方面起到了很好的表率作用。
Choke points
paper中把這種技術挑戰點很形象的稱為choke point，并對它們進行了分類，對每個CP都提供了一定的解決思路，除了論文中提到的，我也會簡要描述下PolarDB繼承于MySQL的現狀以及SQL團隊針對其中一些作出的改進。
CP一共分為6大類，共48個，如下圖彙總：
上圖中不同顔色的方框代表不同choke point對于每條query的影響程度，越深影響越大。
Aggregation Performance
TPCH中有大量的group by + aggregation運算，如Q1,Q13這些query，直接就是挑戰聚集的計算性能。
CP1.1 Ordered Aggregation
一般的聚集實作是通過hash aggregation，但如果group key數量較多時，hash table可能會比較大，超過各個level的cpu cache，這樣cache + TLB的頻繁miss，會比較大的影響lookup性能。如果group key進一步增多，無法放入記憶體中，這時就需要spill to disk, spilling hash aggregation和hash join類似，也是先用一個hash func，拆分到若幹file中，在每個file内各自做聚集計算。
這樣的效果可能不如做ordered aggregation好，而且如果輸入到group的資料已經按group key有序（更一般的，隻要具有相同的group key的tuple相鄰即可），則ordered aggregation效果則會更好。
具體選擇哪種方式，和可用的硬體資源 + query本身特性相關，而且為了準确評估優劣，group by的cardinality + cost需要較為準确的估算。
CP1.2 Interesting Order
為了能夠使用Ordered Aggregation，可以利用查詢中的有序性，這種有序性可能來自2種
- 通過clustered index掃描産生的key order，被後續的算子保留進而傳遞到上層
- 算子執行産生的新的order （比如hash join的probe側的順序，nested loop join的外表順序）
針對以上2點，MySQL是支援hash/ordered 兩種方式的aggregation計算的，但很可惜，這并不是由代價決定的，而是一系列寫死的複雜判斷邏輯。概略來說，如果group by列能夠簡單計算且僅依賴于join序列上第一個table，則可以嘗試利用join table的有序索引（如果存在）或對其輸出做filesort排序，來實作ordered aggregation，否則使用hash aggregation。這是由于MySQL重度依賴nested loop join且沒有sort merge join的天然特性，是以其對interesting order的利用都是始于第一個table。
CP1.3 Small Group-By Keys
在做hash aggregation時，如果group by key的NDV很小，可以用一個較小範圍的整數值來覆寫，這樣可以使用一個連續數組來計算aggregaion而不是hash table，連續數組cache locality要好很多，可以大幅提升性能，但這有一個基本前提：需要能較為準确的估算group key NDV。
相信除了SQL Server/DB2這種牛掰的商業資料庫（尤其是SQL Server，其Cardinality Estimation無疑是業界第一的），能對各類group by的NDV做較為精準估計的應該很少，但我們可以在滿足特定條件時作出準确估計，進而利于應用這種優化。
例如MySQL，在group by key上有index時，是可以針對key prefix有較為準确的NDV估計的（density vector)，此外8.0 histogram的引入也增加了cardinality估計的準确性，但社群版本中，histogram并不支援自動更新，嚴重限制了其實用性。
PolarDB在這方面已經做了很多工作，不僅對histogram進行了增強，也支援了自動更新，此外增加了算法支援利用index + histogram + filter進行單表group by NDV的估計，能夠給出較為精确的結果，基于此去改造group by keys的數組實作，是較為簡單的。
CP1.4 Dependent Group-By Keys
利用functional dependency，可以消除備援group by key，例如Q10中，原始存在大量的group by列，基于c_custkey是主鍵這個條件reduce掉customer表其它列，減少分組時做比較的cpu開銷也節省了記憶體。類似的推導還有：
以上#xx 表示xx表的主鍵
MySQL自身對group by/order by已經做了一定的優化，例如去掉常量的key，以及基于MySQL const table/JT_EQ_REF推導出的常量group key，以及基于主鍵的備援key消除。但自身缺乏一套系統的推導functional dependency并基于FD做reduction的架構，這是很值得擴充的一個基礎架構。
Join Performance
join無疑是SQL query中對性能最為重要的operator，對于join order的選擇，可以說是失之毫厘謬以千裡。是以有很多可以優化的點，相關的論文也數不勝數，這裡提到了幾點。
CP2.1 Large Joins
這裡是指資料量較大的join，常見的join算法有hash-based/index-based, index-based可能會有二次回表的開銷，引發較多随機IO，但如果資料都在記憶體就還好。
TPCH中最大的兩個表Order + Lineitem表的join，可以通過兩種方式來調優
- 通過cluster index，在NL join時，增加一些資料的Locality
- 通過table partitioning，并發做local join，在MPP系統中盡量減少網絡資料發送。
由于曆史原因，MySQL對于join的處理是重度依賴nest loop的，8.0之前甚至沒有hash join，現在也沒有sort merge join，它專為nest loop join實作了2種優化：
- block nest loop join (BNL) ，為了減少内表的重複掃描次數，在外表擷取一個block資料(緩存在記憶體buffer）時，才掃一次内表完成一批join。
- batch key access (BKA) ，原理與BNL相同，但内表上是index lookup，是以除了外表緩存一批，還會在與内表join後，把内表的primary key再緩存下來進行排序，進而把内表回表的random IO轉變sequential IO，提升性能。
基于以上2個優化，可以看到對于TPCH這種star schema，如果有外鍵索引，MySQL速度還是相對不錯的，否則就非常糟糕。
8.0後，MySQL引入了hash join，但社群版本存在很多的局限性
- hash join的選用完全是基于規則，将優化器選擇的BNL硬替換為hash join，是以如果有index，則完全不考慮hash join，即使其執行更優。
- 無index時，由于join ordering的選擇不準确，導緻在build側存在大量中間結果資料，出現很多磁盤交換。
- 單線程執行
為此PolarDB針對性做了很多工作，例如
- 為hash join建立代價模型，可以基于代價更加準确的在index NLJ和hash join之間選擇
- 利用有效的histogram提升join cardinality估計的準确度，選擇更優join order
- 基于共享build hash table的形态，實作了non-partitioned parallel hash join
上圖給出了前兩項優化後對社群版本在TPC-H SF10上一些query的性能對比，由于社群不支援并行處理，就沒再比較parallel hash join的提升了。
CP2.2 Sparse Foreign Key Joins
在TPCH中，大多數的join都是主外鍵join，而且在主表上，對主鍵都有一定的過濾條件，這樣就導緻在外鍵去match時，一般是Join不上。是以可以利用bloom filter，在build hash table時建立bloom filter并傳遞給probe側。Bloom filter一般較小，可以保持在CPU cache中，是以過濾效率比hash table要好很多。
此外，Bloom filter應該盡可能下推到probe側，最好推到存儲層，在scan時盡早避免後續的CPU計算，在MPP系統中，可以在傳輸probe資料前，先傳遞bloom filter來減少資料傳輸。
針對這個優化，MySQL不存在這個問題，因為如果有主外鍵，它是一定是要nest loop join的，但值得一提的事，PolarDB的hash join實作了基于bloom filter的預過濾功能。
- CP2.3 Rich Join Order Optimization
在多表join時，應該盡可能枚舉所有可能的join方式，來選取最優order，例如利用DPccp/DPhyp這種基于join graph的高效enumeration算法
MySQL基于greedy search的join ordering算法是比較弱的，隻能支援線性的left-deep tree，所能支援的表數量較少，而且一旦大于一定門檻值就引入greedy政策，是以社群在8.0.2x版本中開始引入新的hypergraph優化器，目前還是WIP，估計在9.0才能GA。
針對這方面，PolarDB也在做一些工作，例如在一定情況下引入bush join的選項并基于cost與left-deep tree做比較，目前也是WIP。
CP2.4 Late Projection
這是針對列存特有的優化，可以在table scan時，對于早期算子不使用的列不去scan出來，但這裡會有個trade-off，因為随着plan tree的上升，tuple的資料傾向于越來越稀疏，是以scan會越來越離散，無法利用順序IO/Prefetch IO的優勢。
是以晚物化比較理想的場景是，當需要最後擷取時，所涉及的tuple數量較少，比如有聚集，或者有Top-N的場景。或者是在join時隻擷取join key列，當match上時才把其餘的column讀取出來，由于列資料本身是按照row group來拆分的，每個row group内的一批資料形成一個block，是以可能跳過很多block，避免做IO/decompression的開銷。
Data Access Locality
CP3.1 Columnar Locality
這時列存的天然優勢，緊湊的資料布局有益于cache locality，并且可以做壓縮來減少IO開銷，利用向量化技術以及基于SIMD指令集的計算原語，實作高效的算子内并行，提升算子執行效率。
Oracle最近也推出了其雲上的Heatwave service(RAPID)，本質就是一個分布式的in-memory column store，利用了Oracle一些特殊的硬體優化技術配合列存的向量化+壓縮态計算來實作高性能計算，以及利用in-memory的binlog快速同步來支援一緻性讀取，不過這方面的資料還很少。
CP3.2 Physical Locality by Key
通過聚簇索引提供資料通路的局部性，尤其對于datetime這類的列，在TPCH中，很多datetime的列都是具有相關性的。
可以利用這種相關性，把基于某個日期列的range條件，傳遞到其他相關的日期列。
- clustered index，如果資料是按照日期組織的，那麼兩表的join 大體上會比較有序的（兩個join key，有一定時序上的語義的關聯性，比如發貨 -> 收貨)，但是優化器必須可以識别這種相關性。
- table partitioning，通過range partition，可以比較好的做partition pruning，在做主外鍵join時，可以在外鍵表上，對每個partition，針對每個對應的主鍵表，維護一個pruning bitmap，進而加速join過程，這些pruning bitmap可以在做主外鍵限制檢查時進行更新。
CP3.3 Detecting Correlation
這是cardinality estimation的老大難問題了，這裡包含2個子問題：
- 如何捕獲2列之間的相關性 -> 目标列是什麼？
- 如何量化衡量2列間的相關性 -> 如何描述相關性？
針對第一個問題，一般會采用query feekback的方案，也就是在初始時，并不假定其相關性，然後在query實際執行中，利用feedback機制擷取實時的準确統計資訊來發現原始的假設并不成立。類似的方案有很多，例如Oracle的adaptive statistics ，DB2的LEO ，HANA的Statisticum 。。。不過基本前提都一樣，就是要有完備的實時采集和feedback機制。
針對第二個問題，商業資料庫系統處理的比較完善，例如Oracle的多元histogram/column group zonemap，SQL Server的expression statistics等，不過多元histogram的維護成本是很高的，是以針對多列的簡單組合統計資訊是更常見的方案，MySQL隻有基于index prefix的density vector這種機制來記錄多列組合的NDV。
query feedback loop是非常重要的，PolarDB目前已經實作了部分基礎設施和架構，不過目前主要還是用于histogram的自動更新和plan management的演進，後續會不斷擴充來支援更多功能元件。
Expression Calculation
CP4.1a Arithmetic Operator Performance
對于decimal類型的存儲，如果轉換為double，會損失精度，如果轉為字元串則效率太低。常見的方式是通過 * 10xx倍後，将小數轉換為整數，在TPCH的規則中，最大的decimal整數也隻需要42-bit，用64bit整數可以儲存+計算，但這樣對于256bit SIMD寄存器效率太低了，是以可以考慮根據不同資料列的取值範圍，采用不同的bit位數來存儲，進而盡可能提升SIMD的使用率。
當然，這是一種針對TPCH資料特性的特殊優化，并不具有普适性。
MySQL使用一個資料結構my_decimal來表示decimal資料，其中包含一個9位元組的buffer和三個int數值，分别描述整數部分長度/小數部分長度/buffer有效長度。其計算涉及到精度變換，類型cast等，計算效率很低。我們在PolarDB中也實驗性的測試了使用64bit整數來簡化其計算的方案，在純數值計算上産生了很大的性能提升，但由于沒有通用性，最終沒有采用。
CP4.1b Overflow Handling
對數值的計算結果做溢出檢查成本是比較高的，因為會使用if - else分支，破壞CPU流水線。一種樂觀方案是可以根據資料的類型，range的範圍和可能的計算方式，提前預測其不會overflow，就可以避免這種檢查了，至少TPCH中可以利用這種優化。
CP4.1c Compressed Execution
列存一般都具有壓縮機制，比如可以利用RLE編碼，直接在壓縮态計算全量的聚集函數(不能帶group by key)，再針對結果進行解碼。或者利用dictionary編碼，基于dict index做謂詞過濾，這時隻涉及整數的比較，可以更高效的利用SIMD。
CP4.1d Interpreter Overhead
對于expression tree，由于其複雜的分支遞歸結構，做解析執行的成本很高，可以通過JIT / Vectorize 來提升效率。
向量化或編譯執行是2個非常大的話題，無論學術界還是産業界都有廣泛的應用，各自适用于不同的場景 。
不過大體來看，TP型的系統更偏向于編譯執行（如Postgres / OceanBase / SQL Server...)，因為行存的格式應用向量化或批量計算一般無法産生顯著效果（cache locality不好），但TP workload經常具有高度類似性的query，使得高昂的compilation成本可以被均攤掉。而AP系統則由于是列存，更适合于使用向量化的計算（Vectorwise / HANA / ClickHouse ...)。當然還有像CMU Peleton這樣的系統，嘗試将2者結合起來 。
在這方面，PolarDB列存已經支援了向量化的資料列計算，并有了完備的基于SIMD instruction的計算原語，不過編譯執行目前還沒有嘗試。
CP4.2a Common Subexpression Elimination
比如投影列中的AVG -> SUM / COUNT ,那麼可以把重複的聚集操作去掉。
這是MySQL比較薄弱的一方面，在其優化邏輯中，經常會插入更多的用于最終結果計算的額外表達式，但這些表達式可能與已有表達式重疊，但它沒有精細的區分與處理，PolarDB中之前還修複過一個bug：對于已計算完成的标量子查詢，會在後續執行中再次反複計算。
CP4.2b Join-Dependent Expression Filter Pushdown
對于比較複雜的邏輯表達式condition，可以盡量拆分成和單表相關的多個條件的AND，進而各自推到單表上執行。
相對來說，這算是MySQL的一個強項。在make_join_select()函數中完成了對where condition的拆分和下推到盡可能底層的算子中，由于MySQL對于表達式的優化還算全面，支援多輪的常量折疊/等值傳遞/等價性推導，也包括針對二級索引列下推到存儲層的index condition pushdown等。
CP4.2c Large IN Clause
在TPCH中有一些IN表達式，但涉及的值并不多，這時可以轉換為 (xx or xx … )的形式。此外在很多分析場景中，自動生成的IN-list會有大量的value，這時可以将list構造為一個hash table，通過semi-join probe的方式來提升過濾效率。
MySQL對于IN的優化是，如果可以使用index，則用index進行range scan，否則使用table scan，是以并沒有這種hash table probe的能力。之前線上上也多次碰到使用者有大量IN表達式的需求，隻能通過顯示建立臨時表，走semi-join的方式來改寫SQL，還是比較尴尬。。。
是以這是一個很值得做的優化。不過需要有cost based transformation的能力，我們正在做這方面的工作。
CP4.2d Evaluation Order in Conjunctions and Disjunctions
在優化階段，可以根據不同子條件的選擇率，盡量将選擇性好的子條件放在前面計算，進而盡早過濾。但選擇率估計可能不準确，而且很多資料的選擇率本身也是随着執行不斷變化的。是以很多系統都可以在執行中，動态根據監控到的選擇率改變各個子條件的evaluation順序。這屬于adaptive query execution的一個功能，目前PolarDB還沒有這樣的能力，不過可以想見，一旦有了比較完善的運作期監控+回報機制，實作這個功能難度不算大。
CP4.3b Raw String Matching Performance
X86指令集中擴充了SSE4.2的原語，能夠在一個SIMD的指令中對16byte的字元串做比較。這可以很大提升字元串比較的效率（相對strcmp）。但一般謂詞的比較，在大多數情況下都會很早的不比對而退出，是以使用SIMD沒有很好的效果，但如果是group key的比較，則命中率會高很多，更适用于SIMD。
Correlated Subqueries
TPCH中的相關子查詢都可以被展開，轉換為多種形式的join (outer join/anti join/semi join）。
CP5.1 Flattening Subqueries
TPCH中很多條查詢都具有相關子查詢的construct。
相關子查詢的解相關是query transformation中最為常見的一種，如果無法很好的優化，則可能導緻嚴重的性能問題。這個問題在MPP的環境下則更為嚴重，相關性語義會導緻大量的資料傳輸，無法高效并行執行複雜query。
是以比較成熟的優化器都有一套完整的子查詢處理機制，例如Oracle針對subquery unnesting有多種不同的方案(基于window function/基于derived table/子查詢展開。。。），SQL Server則基于apply算子實作了一套完整的子查詢解相關的等價變換。
長時間以來，MySQL對于相關子查詢的處理是比較弱的。在8.0之前，隻能支援IN -> semi-join的轉換，或者IN -> EXIST的轉換，進入8.0之後，開始支援EXIST -> IN -> semi-join的變換，而且開始能夠支援NOT EXIST的語義（但無法支援null aware anti-join)。不過這些變換隻是應用于SPJ子查詢。最近幾個版本中，為了支援RAPID MPP engine，其優化器開始支援帶有group by + aggregation的相關子查詢 -> derived table的轉換，不過也僅此而已。
PolarDB在這方面也做了不少的工作，包括參考Oracle做基于window function的子查詢解關聯，以及IN -> derived table的變換等，而且目前我們正在實作cost based query transformation，解決MySQL長期以來完全基于heuristic rules的變換政策。
CP5.2 Moving Predicates into a Subquery
這裡是指像Q2/Q17/Q20這樣的查詢，在條件中使用相關子查詢的聚集結果作為外層的過濾條件，這裡還有個明顯的特點，外層查詢subsume了内層子查詢（包含了相同的表和條件，且具有更多）。是以可以通過下推部分表+條件到子查詢中的方式，來完成提前的過濾，PolarDB中實作了這個優化。
- CP5.3 Overlap between Outer- and Subquery
對于query中外層qb與内層qb是subsume的情況 （外層包含内層的join tables + join 條件），在5.2中已經提到下推條件到子查詢中，其實可以通過下推相關表+相關條件的方式，使整體變為一個非相關的derived table，這時内外側common的部分隻需要在derived table物化時計算一次，避免了昂貴的重複計算。
Parallelism and Concurrency
CP6.1 Query Plan Parallelization
随着現代硬體環境的變化，多核+大記憶體的配置變得越來越常見。對于多核上的查詢并行，無論是從query optimization 還是 query execution，都是一項很有挑戰性的工作。當然成熟的資料庫系統（尤其是商業資料庫）一般具有parallel execution的能力，開源的Postgres也有簡單的基于parallel access table的并行計算能力。
不過很可惜，MySQL是沒有這個能力的，這源于它醜陋的THD緊耦合設計與複雜混亂的優化/執行結構。PolarDB的并行執行可以說是其提升分析查詢能力的一項大殺器，對比AWS aurora基于smart storage的并行政策，PolarDB具有更大的靈活性和複雜算子的支援能力。而對比華為TaurusDB，感覺它還處于開發的初級階段，PolarDB在功能上的成熟度和擴充性上已經遠遠的領先了對手。
PolarDB的并行執行也經曆了從簡單的并行表掃描 -> 複雜的多stage plan的演進，由于本人是做并行plan優化的，是以後續也會專門寫一篇文章來介紹PolarDB的并行計算功能。
CP6.2 Workload Management
并行執行并不是無損的，理論上隻要查詢中有需要多個worker共享的資源，就會限制并行度的擴充，而且worker執行也是有資源消耗的。可以想見，随着并行度的不斷增大，查詢的執行時間不會無限成比例縮短，早晚會進入瓶頸。是以如果并發load很大時，最理想的方式反而是每個query串行執行互不幹擾，這樣可最大化利用機器資源。
是以如何控制并行執行的資源占用是一個重要的問題，例如Oracle通過producer-consumer的排程+中間結果緩存機制，確定同一時間隻有2組worker線程在運作，其cpu資源占用最大為2 * dop。SQL Server由于有強大的系統控制能力，其底層實作了SQLVM封裝層，将對系統資源的占用完全封裝起來，它可以利用精确的CPU執行排程能力來細粒度控制worker的資源占用，確定不會溢出。而Greenplum就比較粗犷了，由于是multi-process模型，直接利用cgroup對資源占用進行控制。
PolarDB同樣面臨這個問題，目前我們關注的主要是cpu + memory兩個方面：
- 對于memory，在執行一個parallel query時，會粗粒度的累計其占用的記憶體資源情況，後續在做并行優化時，會判斷系統記憶體占用是否已過高，如果是則fallback到串行。
- 對于cpu，由于MySQL是沒有細粒度的搶占排程能力的，是以并行優化器會基于不同stage算子的具體執行方式，通過調整stage dop的方式，粗粒度的限制query整體的cpu占用情況。雖然不能做到SQL Server那樣的精細控制，但也可以保證不會溢出。
CP6.3 Result Re-use
可以對執行的中間結果/最終結果進行緩存，供其他query複用，是否做緩存取決于3方面的因素：
- query result size
- query result擷取的cost
- query result複用的頻繁程度
MySQL在5.7中引入過query cache，但由于其效果不好被廢棄掉了，PolarDB重新基于這個patch做了大量改進工作，包括：
- 适配PolarDB的上下文
- 解決其在并發場景下争搶嚴重的設計缺陷，優化并發通路性能
- 改善失效機制
- 降低memory footprint
- 改善其可應用條件，提高适用性
- 修複若幹bug...
總結
本文基于原paper描述了query optimization或者query execution中一些重要的優化點，以及MySQL的現狀和PolarDB做的一些工作。未提及的内容其實還有很多很多，看完paper後結合自身的工作，最大感受就是資料庫的查詢優化是一項複雜的工作，既需要系統性的規劃，又需要一點一滴的持續改進，最終會是量變産生質變。
這麼多的技術方案，這麼多的paper，哪些是我們應該去重點發力的呢？個人的淺見是，一些必要的基礎架構是不可少的，例如statistics + cardinality estimation，functional dependency，physical property，query transformation(cost based?)，cost-based join ordering，query feedback loop，execution scheduling。有了這些後再在其中不斷加入新功能，客戶導向是個不錯的選擇，以滿足客戶需求為目标，在解決客戶問題的過程中不斷打磨自身的能力，即可以讓系統貼近實際不偏離航道，又可以帶給上下遊團隊足夠的成就感。