蘭 海，韓 珂，申 礫，崔 秋，彭煜瑋*

（1.武漢大學(xué)計算機學(xué)院，武漢610072；2.北京平凱星辰科技發(fā)展有限公司，北京100096）

0 引言

在大數(shù)據(jù)時代，各個公司需要更高的數(shù)據(jù)處理和分析能力，保證迅速地做出商業(yè)決策以及用戶響應(yīng)，數(shù)據(jù)處理引擎因而成為了各個公司的核心系統(tǒng)。隨著數(shù)據(jù)持續(xù)增多、處理性能要求提升、處理場景和類型的多元化，對數(shù)據(jù)處理引擎提出各方面的挑戰(zhàn)［1］，因此，在傳統(tǒng)關(guān)系數(shù)據(jù)庫外，發(fā)展出了NoSQL［2-3］、NewSQL［4-6］、流式處理［7-9］等各類數(shù)據(jù)處理引擎。其中，TiDB［10］是受Google 的F1［11］以及Spanner［12］系統(tǒng)啟發(fā)的一款開源分布式混合事務(wù)分析處理（Hybrid Transaction/Analytical Processing，HTAP）數(shù)據(jù)庫，結(jié)合傳統(tǒng)關(guān)系數(shù)據(jù)庫管理系統(tǒng)（Relational Database Management System，RDMS）和NoSQL 的特性，兼容MySQL 語法，支持無限水平擴展，具有強一致性和高可用性。TiDB 現(xiàn)在逐漸被許多商業(yè)公司在業(yè)務(wù)系統(tǒng)中使用。

當(dāng)前TiDB 的優(yōu)化器對大部分查詢請求都能生成性能極佳的物理計劃，但仍有不足之處。下面通過舉例來描述其中之一，同時也是本文中要解決的問題。假設(shè)有表1 所示的模式。

查詢“SELECT*FROM t1 WHERE a1＜1 OR a2＞10”發(fā)送給TiDB，當(dāng)前TiDB 優(yōu)化器生成的物理計劃為在t1 表上的全表掃描。假定t1 表上有100 萬個元組，且滿足條件“a1＜1”和“a2＞10”的元組各僅有一個。使用全表掃描需要訪問100 萬個元組。如果利用索引“i1”（后文以i1（a）表示名為i1 建立在列a 上的索引）獲取滿足條件“a1＜1”的元組，利用索引“i2”獲取滿足條件“a2＞10”的元組，然后將兩個結(jié)果進行并操作，即得到結(jié)果。在這種執(zhí)行方式中僅需要訪問4 個元組，其中兩個為數(shù)據(jù)元組，兩個為索引元組（TiDB 中索引非樹狀結(jié)構(gòu)，索引掃描沒有中間節(jié)點訪問的開銷）。同樣的環(huán)境下，后者性能提升明顯。

表1 模式信息Tab.1 Mode information

從上述例子可知，當(dāng)約束條件涉及多個索引屬性時，首先利用單個索引獲取結(jié)果，然后將結(jié)果進行并（條件為析取范式（Disjunctive Normal Form，DNF））或者交（條件為和取范式（Conjunctive Normal Form，CNF））操作以獲取最終數(shù)據(jù)元組的方案優(yōu)于用全表掃描或單個索引掃描的執(zhí)行方式。

本文研究在TiDB 中利用多個索引提供更優(yōu)的數(shù)據(jù)訪問方案。將利用多個索引進行數(shù)據(jù)訪問的路徑稱為MultiIndexPath，具體根據(jù)約束條件類型又分為MultiIndexOrPath以及MultiIndexAndPath。

在TiDB 上增加MultiIndexPath 的支持并不容易，存在如下難點：第一，如何將路徑生成算法與TiDB 系統(tǒng)融合，以生成可能的MultiIndexPath。第二，索引選擇。如果表上的一個約束條件有多個可使用索引，如何選擇其中一個。第三，代價模型。由于TiDB 將計算與存儲分離，兩者通過遠端程序調(diào)用（Remote Procedure Call，RPC）進行通信以及數(shù)據(jù)傳輸，增加了網(wǎng)絡(luò)開銷；同時，TiDB 運用大量并行執(zhí)行技術(shù)，增加了代價模型的建模難度。

針對以上難點，本文首先基于TiDB 現(xiàn)有的優(yōu)化器機制實現(xiàn)了MultiIndexPath 的生成算法。其次，當(dāng)有多個索引可選時，采用啟發(fā)式方法，進行索引選擇，后文通過實驗證明了該方法的有效性。第三，在充分考慮了網(wǎng)絡(luò)以及并行等因素后，給出了MultiIndexPath 的代價模型。最后，在TiDB 的執(zhí)行架構(gòu)基礎(chǔ)上，實現(xiàn)了物理計劃的執(zhí)行框架；并進一步結(jié)合TiDB架構(gòu)特點，提出了一種Pipeline模式的執(zhí)行算法。

1 相關(guān)研究

單機關(guān)系型數(shù)據(jù)庫針對上述問題已經(jīng)能生成利用多個索引的物理計劃，但在實現(xiàn)方案上均有所不同。

MySQL 提供了IndexMerge［13］。當(dāng)前MySQL 支持三種方式利用多個索引：Intersection（交）、Union（并）以及Sort_union（排序并）。交、并操作需要每個索引返回的表元組按照Rowid 排序，然后將從不同索引獲取的表元組利用歸并操作得到最終結(jié)果。

PostgreSQL 中用Bitmap Index Scan 以及Bitmap（位圖）操作［14］來實現(xiàn)多個索引的使用：首先利用Bitmap Index Scan 構(gòu)建每個索引要訪問的物理頁的位圖，然后利用位圖的交或者并確定最終要訪問的頁，最后訪問頁并從中取得滿足條件的元組。

商業(yè)數(shù)據(jù)庫DB2 中，首先利用單個索引獲取滿足索引條件的Rowid，然后再將這些不同的Rowid 集合執(zhí)行交或者并操作獲取最終Rowid 集合，最后將利用這些Rowid 進行數(shù)據(jù)獲取。商業(yè)數(shù)據(jù)庫Oracle 中有多個方式利用多個索引，如IndexJoin 以及Bitmap Merge。其中IndexJoin 將不同索引返回的結(jié)果根據(jù)Rowid 來進行Join，然后返回。Bitmap Merge 則利用Oracle 中的Bitmap 索引，通過Bitmap 的交或者并位操作來獲取最終滿足結(jié)果的Bitmap，再將Bitmap 變?yōu)镽owid，通過Rowid 獲取最終的表數(shù)據(jù)。對商業(yè)數(shù)據(jù)SQL Sever 中or 的情況，首先通過多個IndexSeek 獲取滿足條件的索引元組，再利用Sort+Concatenation 或者MergeJoin+Aggregate。對于and 情況也是利用類似的方式。

2 TiDB的數(shù)據(jù)獲取

TiDB 主要包括三個核心部件：TiDB Server、PD Server 和TiKV Server［15］。其中：TiDB Server 是計算層，負責(zé)SQL語句的執(zhí)行；TiKV Server 是存儲層，為TiDB 提供了分布式存儲；PD Server 負責(zé)集群管理，包括集群相關(guān)的元數(shù)據(jù)存儲、全局事務(wù)的管理以及TiKV集群的負載均衡。

以表1 中模式為例，如果查詢?yōu)椤癝ELECT*FROM t1 WHERE a1＜2 AND a3=3”，該查詢語句有兩種可能的表上數(shù)據(jù)訪問方式：全表掃描和索引掃描。

2.1 全表掃描

TiDB Server 通過PD 了解表上數(shù)據(jù)分布位置后，將全表掃描計劃以及過濾條件“a1＜2 AND a3=3”發(fā)給對應(yīng)的TiKV。TiKV 對表t1上的元組逐一掃描并判斷是否滿足條件，將滿足條件的元組返回給TiDB Server，最后由TiDB Sever 返回給用戶。

2.2 索引掃描

TiDB 的索引掃描包含兩種：Index-only 掃描以及一般索引掃描。Index-only 掃描適合于查詢目標列被索引覆蓋的場景。一般索引掃描先用索引獲取滿足條件的元組Rowid，然后利用Rowid去獲取對應(yīng)的表數(shù)據(jù)。

3 整體框架與代價模型

為能在TiDB 中利用多個索引協(xié)同完成查詢，本文提出了一種新的訪問路徑：MultiIndexPath。

3.1 整體流程

TiDB 中構(gòu)建邏輯計劃時，將生成一個全表掃描路徑以及所有可能的索引掃描路徑。MultiIndexPath 的生成位于邏輯優(yōu)化結(jié)束后、物理優(yōu)化開始前。在此過程中，優(yōu)化器會根據(jù)表上的條件以及索引信息生成可能的MultiIndexPath 加入備選路徑中。進行物理優(yōu)化時，對每個MultiIndexPath 備選路徑根據(jù)4.2 小節(jié)中的代價模型估算代價，最終選中代價最低的物理計劃（記為MultiIndexPlan）。

MultiIndexPlan 有兩種可能的執(zhí)行方案：1）利用索引掃描得到實際元組，對各個索引得到的實際元組執(zhí)行并或者交操作；2）利用索引獲取表上數(shù)據(jù)的Rowid，然后對Rowid 進行交并操作，再根據(jù)結(jié)果獲取對應(yīng)的表數(shù)據(jù)。

本文基于以下幾點考慮選擇了后一種方案：1）第一種方案需要獲取表元組的Rowid 值執(zhí)行交并，增加了一次對元組的解析操作；2）由于TiDB Server 利用RPC 從TiKV 獲取實際元組，重復(fù)元組會耗費額外的網(wǎng)絡(luò)帶寬；3）TiDB 中索引掃描的流程是從TiKV 先獲取Rowid，然后通過Rowid 取表數(shù)據(jù)，這種執(zhí)行模式為第二種方案提供了實現(xiàn)基礎(chǔ)。

MultiIndexPlan的執(zhí)行如圖1所示。其中涉及到三類協(xié)程（routine）：

1）IndexWorker：每個索引對應(yīng)一個，執(zhí)行索引掃描，獲取滿足條件的Rowid；

2）AndOrWorker：對返回的Rowid 集合進行交并得到最終的Rowid集；

3）TableWorker：根據(jù)AndOrWorker得到的Rowid集，獲取表元組。

圖1 MultiIndexPlan執(zhí)行框架Fig.1 MultiIndexPlan execution framework

3.2 代價模型

MultiIndexPlan 的代價包括：索引掃描代價、Rowid 傳輸代價、表數(shù)據(jù)掃描代價、過濾條件計算代價、表元組傳輸代價以及執(zhí)行交并操作的代價。代價模型中用到的符號說明見表2。

表2 代價模型的符號說明Tab.2 Symbol description of cost model

在3.1 節(jié)中描述的本文所采用的執(zhí)行模型中，多個IndexWorker 并 行 進 行Rowid 掃 描，得 到 的Rowid 由AndOrWorker 處理，最初增加并行度能夠提高性能，但過高的并行度會讓AndOrWorker 成為瓶頸，無法帶來性能提升。因此本文的代價模型中仍然按串行執(zhí)行的方式計算代價：

4 路徑生成算法

路徑生成分為兩個階段：第一階段生成所有可能的MultiIndexOrPath；第 二 階 段 生 成 所 有 可 能 的MultiIndexAndPath。

4.1 MultiIndexOrPath 生成

MultiIndexOrPath 生成算法如算法1 所示，輸入需要訪問的表上的索引集合Is 以及條件數(shù)組PCs，輸出為所有可能的備選MultiIndexOrPath（記為CP）。

算法1 GenMultiIndexOrPaths。

算法依次處理條件數(shù)組的每一項，對每一個數(shù)組元素cond，首先檢查該條件是否由OR 連接的表達式：如果不是則取數(shù)組的下一個條件進行處理（見算法第4）行）；如果是OR連接表達式，則將其展開。例如“（（a1＞1 OR a2＜10）OR a3=5）”，將展開為［a1＞1，a2＜10，a3=5］。如果a1＞1、a2＜10、a3=5都能夠利用索引來進行數(shù)據(jù)獲取，從它們?nèi)呔湍軌虻玫揭粋€MultiIndexOrPath 備選路徑。如果展開項中有一個不能利用索引，則該cond 不能生成MultiIndexOrPath（見算法12）～15）行）。

每個子表達式可能有多個可用索引，當(dāng)前采用啟發(fā)式規(guī)則選擇其中一個索引：1）優(yōu)先選擇覆蓋更多表達式中屬性的索引；2）優(yōu)先選擇索引列數(shù)目最多的索引；3）如果通過上述兩條規(guī)則都無法確定，則隨機選擇一個索引。當(dāng)單個索引掃描路徑生成后，生成最終的MultiIndexOrPath（見算法19）行）。

4.2 MultiIndexAndPath 生成

MultiIndexAndPath 生成算法如算法2 所示，輸入為索引信息Is、條件數(shù)組PCs 以及已經(jīng)被用于生成MultiIndexOrPath的條件數(shù)組UCs。生成MultiIndexAndPath至少要兩個AND連接的條件，若條件數(shù)組中除去已用于MultiIndexOrPath 生成的條件少于兩個，則無法生成MultiIndexAndPath，直接返回（算法1）、2）行）。

如果剩下的條件多于兩個，首先將已經(jīng)生成MultiIndexOrPath 的條件加入tableFilters 數(shù)組中，其次從條件數(shù)組中移除它們（算法4）、5）行）。針對新得到的條件數(shù)組的每一個條件表達式，生成所有可能的索引路徑。如果無法生成索引路徑，則將該條件加入tableFilters 數(shù)組中，然后進行下一個條件的處理。如果有多個索引路徑生成，則基于啟發(fā)式規(guī)則選擇一個索引路徑返回（算法6）～12）行）。當(dāng)處理完所有條件后，得到的索引路徑多于2 個則生成MultiIndexAndPath（算法13）～16）行）。

算法2 GenMultiIndexAndPaths。

5 執(zhí)行優(yōu)化

在MultiIndexPlan 執(zhí)行過程中，需要通過索引獲取Rowid并作交并操作，再根據(jù)結(jié)果Rowid 去獲取實際的數(shù)據(jù)。在作交并操作時，可通過有序集的歸并或者使用位圖方式來實現(xiàn)。兩個方法分別在許多數(shù)據(jù)庫都被采用，具體見第2 章描述。獲取所有Rowid 建立位圖或者獲取所有Rowid 后進行排序再歸并的操作不能以Pipeline 模式執(zhí)行。盡管上述兩種執(zhí)行方式將對表上元組的隨機掃描變成順序掃描，在以傳統(tǒng)磁盤為介質(zhì)的環(huán)境中可以大幅度提升性能；同時各自都保證了集合操作結(jié)果的正確性。TiDB 的數(shù)據(jù)存儲層中的數(shù)據(jù)獲取方式與第2章中描述的數(shù)據(jù)庫有所不同。在TiDB 中，數(shù)據(jù)存儲管理由TiKV 完成，在最底層由RocksDB 進行數(shù)據(jù)存儲。RocksDB 對外提供的數(shù)據(jù)獲取接口包括了prefixseek、get以及next方式。

如果數(shù)據(jù)連續(xù)性比較好，則第一個數(shù)據(jù)用prefixseek 獲取，剩余的數(shù)據(jù)用next 獲取是效率更高的方法。如果數(shù)據(jù)連續(xù)性不好，用一個prefixseek 加多個next 的方式性能會比用多個prefixseek 的方式更差。例如，要從1 000 000 行中返回100行，平均每行之間相隔10 000 個Rowid，如果第二個數(shù)據(jù)采用next 的方式來獲取，則需要先執(zhí)行9 999 個無用的next。如果第二個數(shù)據(jù)采用prefixseek 的方式獲取，則只需要一個prefixseek 操作。兩種方式的代價比約為9 999×1∶8（單次prefixseek 和next 的 耗 時 比 約 為8∶1）。此 外，采 用 一 個prefixseek 加多個next的執(zhí)行方式還需要額外對所有Rowid 進行排序的代價，而且這是一個斷流點。

綜合以上分析以及TiDB 在Rowid 上的天然不連續(xù)性，本文認為一個prefixseek 加多個next 的數(shù)據(jù)獲取方式不適合于MultiIndexPlan 的執(zhí)行，所以，本文提出對任意序的Rowid均能以Pipeline模式進行表元組獲取的執(zhí)行方式。

對于MultiIndexOrPath，采用一個集合來記錄當(dāng)前已經(jīng)發(fā)送給TableWorker 的Rowid，每當(dāng)索引（無論哪個索引）返回一個新的Rowid，先檢查其是否在集合中：如果存在（表示該Rowid 已經(jīng)被訪問過），則跳過該Rowid；如果不存在，將其加入集合中，并將該Rowid 發(fā)送給TableWorker 進行表上元組獲取。

對于MultIndexAndPath，以圖2 所示的例子說明算法原理。對每個索引增加一個集合，用于記錄當(dāng)前該索引已經(jīng)返回，但是還沒有進行表上數(shù)據(jù)獲取的Rowid。在這個例子中記為set1 以及set2。假設(shè)上面的“ix1”和“ix2”索引交替返回Rowid。如果一個新的Rowid 從索引“ix1”返回，首先檢查該Rowid 是否在set2 中，如果存在，從set2 中刪除該Rowid，并發(fā)送給TableWorker；如果沒有在set2中，將其加入到set1中。同理對“ix2”返回的索引也是類似的處理流程。用表3來描述上例的處理流程。

圖2 MultiIndexAnd執(zhí)行示例Fig.2 Example of MultiIndexAnd execution

表3 MultiIndexPlan執(zhí)行流程示例Tab.3 Example of MultiIndexPlan execution process

關(guān)于存儲Rowid 集合的數(shù)據(jù)結(jié)構(gòu)，本文首先采用Bitmap來實現(xiàn)。實際測試也表明該方案執(zhí)行效率很高，但是TiDB 中的Rowid 為int64，所以可能會存儲264-1 個位，這會使得Bitmap 的尺寸超過內(nèi)存容量。本文最終選擇普通的Hashmap方式實現(xiàn)，效率仍舊可以得到保證，對內(nèi)存的占用也較低。

6 實驗與結(jié)果分析

將本文方法在TiDB 3.0 版本中進行了實現(xiàn)，并通過多方面的實驗驗證了其效果，接下來就對實驗的方法和結(jié)果進行介紹。

6.1 實驗環(huán)境

采用4 臺服務(wù)器組成集群，每臺機器處理器為Intel i7-7700，內(nèi)存16 GB，存儲為256 GB 的SSD；服務(wù)器之間通過千兆網(wǎng)連接；其中3 臺服務(wù)器用于TiKV 集群，另一臺服務(wù)器上搭建PD和TiDB Server。

實驗中用到的數(shù)據(jù)如表4所示，由2個人工生成的數(shù)據(jù)集構(gòu)成。在數(shù)據(jù)集的每個列上均建有索引。查詢語句模板如表5所示。

表4 數(shù)據(jù)集描述Tab.4 Description of datasets

表5 SQL語句模板Tab.5 Statement templates of SQL

6.2 結(jié)果及分析

本實驗主要驗證下面幾個方面：1）添加多索引掃描方式后，針對本文所考慮的場景，查詢性能相比未添加該方式是否有性能提升；2）驗證在生成路徑時的啟發(fā)式規(guī)則的正確性。

6.2.1 性能提升

第一個實驗修改＄1與＄2的值，使得模板DNF 語句的選擇率從0.1%到80%。圖3 展示了優(yōu)化前、后TiDB 對DNF 語句的響應(yīng)時間變化情況。在選擇率低于60%的情況下，多索引訪問的方式優(yōu)于TiDB 原來的執(zhí)行方式，并且在選擇率低于8%時，有數(shù)量級的性能提升。原來TiDB 的全表掃描，執(zhí)行時間與表上數(shù)據(jù)元組數(shù)量相關(guān)，因而隨著表上數(shù)據(jù)量增多，這種性能提升會更加地明顯。當(dāng)選擇率高于4%時，會看到優(yōu)化后的響應(yīng)時間會隨著選擇率成倍增長而對應(yīng)地倍增，主要原因是隨著選擇率增加，結(jié)果元組增多，而網(wǎng)絡(luò)開銷與結(jié)果元組的數(shù)目成正比，因而網(wǎng)絡(luò)開銷增大，并占主要部分。

圖3 DNF測試Fig.3 Test of DNF

第二個實驗修改＄1 和＄2 的值，使得每個索引的選擇率從1%到50%。圖4 展示了優(yōu)化前、后TiDB 對CNF 語句的響應(yīng)時間變化情況。其中，CNF-1 語句的查詢結(jié)果為空，CNF-2語句的查詢結(jié)果非空。上述選擇率是指單個索引上的選擇率。實驗結(jié)果表明，對于兩種查詢語句，多索引的訪問方式都略優(yōu)于原TiDB的掃描方式。

圖4 CNF 測試Fig.4 Test of CNF

6.2.2 啟發(fā)式索引選擇方式

按4.2.1 節(jié)所述，適合一個條件的索引有多個時，將依照啟發(fā)式規(guī)則選擇索引，方便后面能夠進行多個索引掃描的合并，減少并行。圖5 以及圖6 分別表示在DNF 條件以及CNF條件下，優(yōu)化后不同的并行度對響應(yīng)時間的影響。從圖5 和圖6 中看出，在誤差允許范圍內(nèi)，隨著并行度的增加，性能并沒有得到相應(yīng)的提升，其原因是隨著并行度的增加，耗費了更多的物理資源，如處理器、網(wǎng)絡(luò)帶寬等，抵消了性能收益。

圖5 DNF并行度測試Fig.5 Test of parallelism degree of DNF

圖6 CNF并行度測試Fig.6 Test of parallelism degree of CNF

7 結(jié)語

在約束條件含有多個索引屬性時，TiDB 不能利用多個索引提供更好的物理計劃。為了解決該問題，本文首先在TiDB中設(shè)計并實現(xiàn)了MultiIndexPath 的生成算法，并提出了一種Pipeline 模式的MultiIndexPlan 執(zhí)行算法。實驗結(jié)果表明在本文所考慮的場景中，利用多個索引的數(shù)據(jù)訪問有明顯的性能提升。