本作品采用知識共享署名-非商業性使用-相同方式共享 4.0 國際許可協議進行許可。

本作品 (李兆龍 博文, 由 李兆龍 創作)，由 李兆龍 確認，轉載請注明版權。

引言

過年回家這件事在摯友的勸導下，在不回去和一直呆在家之間選擇了提前回深圳，從絕大多數方面看這絕對可以算是最近一段時間內做的最正確的決策之一，最直觀的結果就是擁有了完整三天個人假期，可以徹徹底底的放松下，提前進入下2025H1的項目攻堅狀態，把自己的心態拉回來。

過年期間并不算全部都是頹廢的生活，除去闔家團圓的傳統劇情，更具現實意義的是在摯友的推薦和自我興趣驅使下讀完了《親密關系》《惡意》《黃仁勛：英偉達之芯》《廊橋遺夢》，還有一本尚在 todo list 內的《信》，其實對于閱讀這件事情我一直很功利，這也是為什么之前只有在交通工具上時我才會讀非技術書，平時的大把時間也都是在讀領域相關的paper，但是慢慢的發覺，僅有領域知識是遠遠不夠解答所有的困惑的。

回到假期，深圳的三天除了正常的鍛煉，看朋友發給我的自媒體資料這兩個必做項之外，我一直想，在有限的剩余時間是輸入，輸出還是躺著？

輸出有三個選擇：

1. 我非常想寫《黃仁勛：英偉達之芯》這本書的書評，雖然傳記類文章存在部分魔幻色彩，但是Jensen的經歷毋庸置疑是傳奇的，而且NVIDIA的崛起之路不夸張的講能讓一個癡迷技術的理工人看到顱內高潮，相比之下《騰訊傳》就顯得無趣多了。
2. 我最近在做時序數據庫的MPP（Massively Parallel Processing），免不了需要去適配Exchange算子，也確實沒研究過其他的實現，但Velox中的實現的異步方式確實讓人耳目一新，其實現基于ExchangeQueue，ExchangeClient，ExchangeSources三個類，新的實現只需要繼承ExchangeSources就好，這里是絕對值得輸出的，且目前網上這里的資料是零。
3. Presto的HBO，也就是本文，這篇paper年前就看完了，我其實看絕大多數paper不會寫文章，但這篇文章揭示了一個現象，其與我的工作有一些想法上的聯系，即越細的監控粒度能夠帶來更多的可能性，如果能持續下壓性能和成本，這就是絕對符合公司（部門）戰略的事情，而且我最近也在負責優化器部分的重構，HBO的思路有可能在做部分修改后應用到X-Stor來。長久以來看慣了很多軟文的宏大敘事，但其實絕大多數人做的事情就是沒有顛覆性價值，摳出一點意義已經是值得投入以年計的時間了，這雖然讓人有時覺得沮喪，無力且壓抑，但是耐心沉淀對于個人來講也是必要的，畢竟Jensen也曾在AMD打工。

輸入有兩個選擇：

1. 把新年檔的哪吒，唐探，封神看下，事實上已經快忘了我上次在影院看電影是多少年前了
2. 還有兩本書想看

躺著：

1. 思考當下生活的核心矛盾點，思考未來想做好的事情，思考我真正想要的東西是什么

正如現在看到的這樣，最終的決策是選擇輸出HBO，如果文章寫完還有點剩下的時間，那就去深圳灣人才公園水池旁邊的草坪上躺著看星星。

Motivation

Presto的Cardinality Estimator依賴于如下統計信息，粒度為partition級別:

1. Overall cardinality of the partition
2. Column statitstics including
   1. Average size
   2. Number of distinct values
   3. Number of null values
   4. Range(min/max) for the values

傳統的CBO（Cost Based Optimizer）通常依靠離線過程收集有關輸入數據的統計信息，文章開篇點出CBO存在復雜查詢下Cardinality Estimation不準確的情況，進而導致查詢計劃的選擇無法達到最優，具體的，存在如下問題：

1. 需要在查詢前執行分析
2. 做出了很多Simplifying Assumptions，比如data uniformity， independence of filters and columns，在復雜表達式下通常無法準確預估Selectivity
3. 使用更復雜的統計信息，比如multi-column和join histograms，但是需要額外的空間和時間，且很難處理，絕大多數系統沒有實現

LBO（Learning Based Optimizer）也是最近幾年比較火爆的一個方向，其最大的優勢是克服了傳統CBO的很多Simplifying Assumptions，但是也有如下缺點：

1. 訓練和改進模型需要大量的投入
2. 可解釋性差

HBO（History Based Optimizer） 在 Operator Node 級別統計 Query Execution Statistics，并使用這些數據來預測相似查詢的未來性能。HBO基于一種假設，即用戶查詢雖然復雜，但本質上是重復性的，一般使用使用模版生成相同結構的查詢，這會造成查詢計劃基本一致，進而可以通過簡易的方法找到之前的統計信息，然后用來執行精確的估計，這種假設從我們的經驗來看是對的。

HBO解決了之前無法解決的問題：

1. Accuracy：在實際執行運行期間記錄統計數據，并在運算符級別進行跟蹤，消除了使用基礎表統計數據引入的較大估計誤差。
2. Automation：每次查詢運行時，歷史記錄都由輕量級進程跟蹤，從而避免了采樣開銷或模型訓練。
3. Adaptiveness：對基礎數據分布的更改會自動反映在跟蹤的歷史記錄中，并用于未來的優化。
4. Explicability：用戶和 DBA 可以查看估計數據的來源以及它與實際值的差距。

Architecture

Presto CBO可以為簡單查詢生成準確的估計，但隨著查詢變得越來越復雜，誤差幅度會呈指數級增長。

HBO希望做到的約束如下：

1. Estimates need to be accurate：解決復雜查詢下的基數估計不準的問題
2. Accommodate changes to both data and queries：數據和查詢不是靜態的，但是一般也不會短時間存在巨大波動，HBO要能適應數據變化
3. Minimal overhead to query processing：輕量級統計，無需大量計算
4. Ease of use and operation：可調試性，且用戶易于使用
5. Seamless integration with classic methods for deriving cost：HBO不可用回退至CBO

HBO的思路非常簡單，有幾個不那么難的難點需要解決：

1. 查詢模版雖然不變，但是其中參數和查詢條件數量存在變化
2. 統一查詢模版的查詢計劃可能存在差異，因為可能被不同的優化策略該寫過
3. 搜索類似查詢計劃的開銷很大，畢竟每個查詢都會有數據存儲，且在執行之前都會做統計信息獲取

這些難點可以用三個工程方法解決：

1. 模版歸一化，具體的操作是Canonicalizing Table scans，Canonicalizing plan nodes，Pruning constants
2. 將stat-equav的計劃存儲在一起
3. 哈希

簡單來說整個HBO可以分為以下幾個步驟：

1. 對plan nodes歸一化，并且找到stat-equav的plan nodes
2. worker執行完plan后，把統計信息交給Coordinator
3. Coordinator負責將plan及其stats-equav plan nodes統計信息寫入到redis 里面
4. 未來查詢的時候，同樣可以根據歸一化的plan node去redis里面拿統計信息

肉眼可見的簡單，但是也伴隨著極大的工程化落地工作量

HBO Scenario

目前有如下場景用到了HBO：

1. Join reordering：HBO可以準確的拿到之前join算子的準確數據，自然可以選擇最優的連接順序
2. Join distribution type：拿到join算子的準確數據，即不同表的真實數據輸入，自然可以選擇最優的join方法
3. Partial aggregations：通過aggregation算子的輸入大小就知道是否需要做二級aggregations了
4. Skew mitigation：可以知道算子級別準確的null數量，而不是基于假設的估算，這樣就可以判斷是否應用優化規則
5. Scaled writers：write多文件小，write小寫入性能不足，通過歷史記錄選擇相對較優的write數量

Experiments

簡單查詢CBO已經足夠，復雜查詢HBO可以帶來更優的查詢策略

因為選擇了更優的執行計劃，性能提升很明顯

在presto的場景下，10%的查詢有2.5x的性能提升，中位數為1-1.2x的性能提升，但是也有10%有8%的性能下降

HBO的開銷論文中提到占整個查詢的0.5%左右，大概幾毫秒，大多數是網絡開銷。

結束語

在我們的場景中查詢簡單，且查詢場景多為交互式，對時延要求高，雖然加個幾毫秒問題也不是特別大，但是目前除了Partial aggregations沒有看到其他很好的使用場景，也許可以先研究下presto中150多種優化策略具體有哪些使我們能用的比較重要。

參考:

1. How Good Are Query Optimizers, Really? vldb2015
2. Presto’s History-based Query Optimizer 論文筆記
3. How Good Are Query Optimizers, Really?論文筆記
4. 數據庫分布式Join類型及意義Broadcast Join、Shuffle Join 和 Colocate Join