資料庫核心那些事 | 8倍加速HTAP長尾請求 解密PolarDB IMCI行列融合

01 背景

事務處理(OLTP)和分析處理(OLAP)混合的工作負載在目前的業務系統中變得越來越常見。由于實時、易運維等需求，一些業務系統會采用HTAP資料庫來代替原有的OLTP-ETL-OLAP架構，這種所謂的HTAP資料庫，可以在一套資料庫系統中，同時較為高效地處理TP請求和AP請求。

然而，由于TP請求和AP請求的通路模式截然不同，高效處理兩種請求依賴于不同的存儲格式和計算模式。是以，一類HTAP資料庫會存儲兩種不同格式的資料，并在處理不同的請求時選擇不同的模式對相應資料進行計算。

阿裡雲瑤池旗下的雲原生資料庫PolarDB也采用了這樣的方式來處理混合型的工作負載，開啟記憶體列存索引（In-Memory Column Index，以下簡稱IMCI）功能的隻讀節點（RO）會額外維護一份列式索引，并在處理AP請求時采用向量化的方式對列式資料進行計算（列式計算）。而在處理TP請求時依然采用MySQL原有的one-tuple-at-a-time的方式對行式索引的InnoDB資料進行計算（行式計算），列式索引和行式索引都通過實體複制鍊路回放讀寫節點（RW）的寫入。在這套系統中，處理兩種請求的存儲、執行器、優化器都彼此獨立，TP請求和AP請求在執行路徑上完全分離，一條SQL語句要麼選擇列式計算，或者選擇行式計算。

02 長尾請求問題

從使用者的工作負載中，我們觀察到，對于混合負載中大部分的請求，“行列分離”的計算方式已經能夠以最優的計劃執行，然而對于少部分請求，列式計算和行式計算都不是最優的：

1. 在大寬表上，對少數列上通過where或join的條件進行過濾，或求top k，最後對篩選出的行，輸出所有列的明細。在這樣的查詢中，table scan或join隻涉及很少的列，通過列式計算的方式是最優的，但是project需要擷取所有列，列式索引會産生讀放大，通過行式計算利用InnoDB主索引查詢明細是最優的。
2. 執行計劃的一個片段是兩張大表join(t1 join t2)，t1表上where條件的過濾比例很高，且有InnoDB索引，t2表上的join條件沒有InnoDB索引，且join條件隻涉及少數列。在這樣的查詢中，通過行式計算走InnoDB索引查詢t1表，再通過列式計算掃描t2表進行hash join是最優的。（當然此情況下，列式索引上t1表的data skipping足夠準确，也可以使用純列式計算。）
3. 仍然是2中的場景，差別是t2表上的join條件有InnoDB索引，此時t1 join t2這個執行片段通過純行式計算進行index join是最優的，然而，執行計劃的其餘片段可能通過列式計算的方式是最優的。

為了更高效地處理混合負載中的這部分長尾請求，我們在IMCI的優化器和執行器中，基于兩個不同索引，設計并實作了“行列融合”執行架構。本文将介紹雲原生資料庫PolarDB在“行列融合”執行架構的基礎元件（優化器的代價模型，執行器的多引擎通路，存儲引擎的日志回放和事務處理）設計，以及針對上述第一種類型的請求所設計的HybridProject算子。通過基礎元件，我們可以較為容易的實作HybridIndexScan和HybridIndexJoin來處理上述剩下兩種類型的請求。

03 主要挑戰

在一個“行列分離”的系統中實作“行列融合”執行，主要挑戰來自三個方面：

1. 優化器代價估計：MySQL優化器和IMCI優化器的代價模型不同，如果直接以MySQL的代價模型計算行式執行片段的代價，再加上以IMCI的代價模型計算列式執行片段的代價，并不能得到整個執行計劃的可比較的代價。需要設定統一的CPU和IO代價機關，再根據行列計算的不同算法複雜度和行列索引不同的統計資訊計算出可比較的代價。

2. 執行器通路不同索引：一套執行器需要同時通路InnoDB和列式索引。MySQL執行器對于一個SQL請求是以單線程的模式執行的，通路InnoDB相關的interface和context也是面向單線程實作的，而IMCI執行器是以單leader+多worker的模式處理一個SQL請求的，那麼如果在worker中通路InnoDB就需要一些額外處理。

3. 行列索引實作強一緻讀：列式索引和InnoDB回放RW寫入的過程是異步的，兩個不同索引的回放redo log的位點可能不一緻，并且InnoDB通過基于lsn的read view判斷資料可見性，而列式索引通過類似LSM存儲引擎的sequence判斷資料可見性。在異步回放下，行列索引隻能實作最終一緻讀，而“行列融合”的行式執行片段和列式執行片段可見資料不一緻會導緻執行結果的錯誤。

04 行列融合基礎元件

4.1 優化器的代價模型

上述三種類型的長尾請求在“行列分離”的執行架構下會基于代價被看作AP請求由IMCI執行，是以我們選擇基于IMCI的優化器，引入對行式執行片段的代價估計，進而使這些長尾請求能夠選擇“行列融合”的執行計劃。

在引入行式執行代價估計的過程中，我們遵循如下兩個原則：

1. 對于一個執行片段，相對高估其使用行式執行的代價，相對低估其使用列式執行的代價。因為長尾請求原本會選擇純列式執行，這樣的代價估計可以保證當一個長尾請求選擇“行列融合”的執行計劃時，一定不會比原本的執行計劃更差。
2. 隻參考MySQL優化器的代價常量之間的比例。MySQL優化器的代價常量如上圖所示，和IMCI的代價常量具有不同的數量級，是以我們無法直接使用它們的絕對值，但可以參考它們之間的比例關系。

基于上述原則，我們采用如下設計：

1. 在IMCI優化器中，InnoDB的io_block_read_cost和列式索引的pack io cost相同。雖然InnoDB一個page是16KB，而列式索引的pack是65536行，比16KB更大，但基于第一個原則，且考慮PolarFS并發下發請求和條帶打散粒度，我們設定相同的io代價常量。
2. 基于第二個原則，memory_block_read_cost和row_evaluate_cost保持相同比例。基于第一個原則，且考慮向量化執行，row_evaluate_cost要比IMCI的cpu常量要大。

根據上述可比較的代價常量，我們就可以基于MySQL和IMCI各自的算法和統計資訊，計算出“行列融合”執行計劃的可比較代價。

4.2 執行器的多引擎通路

IMCI優化器對長尾請求選擇“行列融合”的執行計劃後，我們通過在IMCI執行器中引入新的Hybrid算子來計算行式執行片段。

新的Hybrid算子需要在IMCI執行器中通路InnoDB，我們參考MySQL的Server層的實作，通過TABLE對象中的handler來和存儲引擎互動。從上圖的執行流程可見，雖然Prepare階段已經Open Table，但相關對象和接口都是面向MySQL單線程執行實作的，是以在IMCI執行器的worker中，需要再次Open Table，并克隆或引用相關對象。這部分主要難度在于相容MySQL邏輯的工程複雜度。

4.3 存儲引擎的日志回放和事務處理

兩個不同索引異步回放的流程如上圖黃色部分所示，其中InnoDB在回放完成後會更新latest read view，而列式索引在回放完成後會更新列式索引的last commit seq。回放流程每隔一段redo（包含若幹條redo log entry）運作一次，一段redo内InnoDB事務和IMCI事務的送出情況是一緻的，是以一段redo在兩個不同索引上都回放完成後，基于更新的latest read view和last commit seq在兩個不同索引上的資料可見性是一緻的，我們稱上述read view和commit seq為“對應的”。如果查詢使用“對應的”read view和commit seq來判斷資料可見性，就能實作強一緻讀。

然而，行列索引的回放流程是異步的，由于回放速度的差異，任意時刻latest read view和last commit seq可能不是“對應的”，這種情況下我們需要找到最近更新的“對應的”read view和commit seq。

為此，我們在異步回放流程中引入上圖藍色部分所示流程：

1. 對于一段redo，InnoDB在更新latest read view後，會在列式索引的Log Queue中添加一個包含目前latest read view的dummy日志對象。
2. 列式索引單線程順序處理Log Queue，先推送正常日志對象到回放子產品，并計算該次回放完成後更新的commit seq。接下來處理dummy日志對象，将該commit seq設定到對應的read view上。
3. 因為在處理dummy日志對象時，之前的正常日志對象可能還沒全部完成回放，是以設定到read view上的commit seq在列式索引上可能尚未生效，回放完成後這個read view和“對應的”commit seq才可以被使用。

引入該流程後，“行列融合”查詢會在尚未被purge的read view中，尋找一個“對應的”commit seq已經生效的read view來判斷資料可見性。

05 HybridProject

通過上述基礎元件，我們引入了HybridProject來處理第一種長尾case。HybridProject通過primary key從InnoDB的主索引擷取完整的行，進行相關表達式的計算後輸出。除基礎元件提供的能力外，HybridProject需要執行計劃中它的孩子算子輸出primary key資料，可以通過兩種方式實作：

1. 優化器支援列裁剪，通過列裁剪使HybridProject的孩子算子隻輸出primary key資料。
2. 強制HybridProject的孩子算子為ComputeScalar，其餘執行片段采用延遲物化（如果其餘片段采用直接物化，則無需選擇“行列融合”的執行計劃），ComputeScalar根據延遲物化的執行片段輸入的row id，從列式索引上擷取primary key輸出。

由于目前IMCI優化器還不支援列裁剪，我們采用第二種方式實作。

06 性能驗證

我們在ClickHouse官方提供的OnTime資料集上，驗證了“行列融合”執行架構和HybridProject的效果。（點選 OnTime | ClickHouse Docs 檢視資料）

OnTime資料集的表包含110列，是一個典型的大寬表。我們通過如下SQL模拟第一種類型的長尾請求：

select * from ontime order by ArrTime limit 1000;           

三種執行計劃均為冷啟動查詢，實驗結果如下：

由實驗結果可見，對于混合型工作負載中的長尾請求，通過“行列融合”執行架構和Hybrid算子，PolarDB可以實作最優的性能，相對于純列式執行或純行式執行都有數量級的提升。

07 總結

“行列融合”執行架構可以選擇更優的執行計劃來處理混合型工作負載中的長尾請求。我們未來将基于此架構引入HybridIndexScan和HybridIndexJoin算子，全面提升長尾請求的性能。

如有關于文中提及技術及實踐相關的問題和咨詢，請發郵件至：[email protected]。

作者簡介

餘南龍（花名：顧紳），來自阿裡雲瑤池資料庫 - PolarDB新型存儲引擎組，從事PolarDB列存索引（In Memory Column Index，IMCI）的研發工作。

推薦閱讀

客戶說｜ERP服務商萬裡牛引入雲原生資料庫PolarDB，助力電商SaaS系統增效降本

資料庫核心那些事｜PolarDB HTAP如何實作行列混存（IMCI）查詢優化？

進階幹貨｜一文剖析PolarDB列存索引（IMCI）如何實作極緻TopK查詢性能？