TiDB 源碼閱讀系列文章（十三）索引範圍計算簡介

TiDB 源碼閱讀系列文章（十三）索引範圍計算簡介

來自專欄 TiDB 的後花園31 人贊了文章

作者：崔一丁

簡述

在資料庫中處理查詢請求時，如果可以儘早的將無關數據過濾掉，那麼後續的運算元就可以少做無用功，提升整個 SQL 的執行效率。過濾數據最常用的手段是使用索引，TiDB 的優化器也會盡量採用索引過濾的方式處理請求，利用索引有序的特點來提升查詢效率。比如當查詢條件為 a = 1 時，如果 a 這一列上有索引，我們就可以利用索引很快的把滿足 a = 1 的數據拿出來，而不需要逐行檢查 a 的值是否為 1。當然是否會選擇索引過濾也取決於代價估算。

索引分為單列索引和多列索引（組合索引），篩選條件也往往不會是簡單的一個等值條件，可能是非常複雜的條件組合。TiDB 是如何分析這些複雜條件，來得到這些條件在對應的索引上的邏輯區間範圍（range），就是本文要介紹的內容。

關於 TiDB 如何構建索引，如何存儲索引數據，希望讀者能夠有基本的了解（參考閱讀：三篇文章了解 TiDB 技術內幕 - 說計算 ）。

這裡是一個例子，展示這裡所說的索引範圍計算是做什麼的，建表語句和查詢語句如下：

CREATE TABLE t (a int primary key, b int, c int);

select * from t where ((a > 1 and a < 5 and b > 2) or (a > 8 and a < 10 and c > 3)) and d = 5;

計算索引邏輯區間範圍的流程如下：

從上圖可以看出，整個流程分為從 Filter 中抽取可用索引的表達式以及利用選出的表達式構造數據範圍兩個步驟，接下來分別描述。

抽取表達式

這個步驟是從 Filter 中將能夠用上索引的表達式選出來。由於單列索引和多列索引在處理邏輯上有很大的不同，所以會分單列索引和多列索引兩中情況進行講解。

單列索引

單列索引的情況相對來說比較簡單。很多滿足 Column op Constant 形式的簡單表達式都可以用來計算 range，單個表達式的判斷邏輯在 checker.go 的 conditionChecker 中。而對於包含了 AND 或者 OR 的複雜情況，我們可以按照下述規則進行處理：

1. AND 表達式無關的 filter 並不會影響其可以計算 range 的子項。所以直接捨去無關的表示即可。以流程圖中的一個子表達式 a > 1 and a < 5 and b > 2 為例，我們只要將 b > 2 扔掉，保留 a > 1 and a < 5 即可。
2. OR 表達式中，每個子項都要可以用來計算 range，如果有不可以計算 range 的子項，那麼這整個表達式都不可用來計算 range。以 a = 1 or b = 2為例，b = 2 這一子項不可以用來計算 a 的 range，所以這個表達式整體上無法計算 a 的 range。而如果是 a > 1 or ( a < 2 and b = 1)，根據 1 中的規則，第二個子項會留下 a < 2 的部分，可以用來計算 a 的 range，因此整個表達式會返回 a > 1 and a < 2 來供接下來計算 range 的部分處理。

這裡補充說明一點，TiDB 的主鍵在實現方式上限定了只有整數類型的單列主鍵會把主鍵值當做 RowID，然後編碼成 RowKey，和這行數據存儲在一起。其他類型的單列主鍵會作為普通的 unique key 看待，當查詢的列包含索引上沒有的列時，需要一次查索引 + 一次掃表。所以我們將這種整數類型作為主鍵的索引處理邏輯單獨抽取出來，其入口函數為 DetachCondsForTableRange 。其中對 AND 表達式和 OR 表達式的處理入口分別為 detachColumnCNFConditions 和 detachColumnDNFConditions。這兩個函數也用來處理其他類型的主鍵或者索引的的 range 計算。

多列索引

多列索引的情況較單列索引而言會複雜一些，因為在處理 OR 表達式中列與列之間的關係需要考慮更多情況。TiDB 中為了簡化 ranger 的邏輯，目前只考慮下列情況：

1. AND 表達式中，只有當之前的列均為點查的情況下，才會考慮下一個列。
   e.g. 對於索引 (a, b, c)，有條件 a > 1 and b = 1，那麼會被選中的只有 a > 1。對於條件 a in (1, 2, 3) and b > 1，兩個條件均會被選到用來計算 range。
   由於非點查的部分只會涉及到一個列，所以可以直接復用 detachColumnCNFConditions。
2. OR 表達式中，每個子項會視為 AND 表達式分開考慮。與單列索引的情況一樣，如果其中一個子項無法用來計算索引，那麼該 OR 表達式便完全無法計算索引。

多列索引處理的入口函數為 DetachCondAndBuildRangeForIndex，AND 表達式和 OR 表達式的處理入口分別為 detachCNFCondAndBuildRangeForIndex 和 detachDNFCondAndBuildRangeForIndex。（由於多列索引對 range 的處理相對單列索引而言會複雜一些，所以沒有拆分為 DetachCondition 和 BuildRange 兩部分，而是由 DetachCondAndBuildRangeForIndex 處理。）

由於邏輯進行到了簡化，因此目前 TiDB 的 ranger 存在無法正確處理的情況。比如：

• a = 1 and (b = 1 or b = 2) and c > 1。對於這個式子，當 (a, b ,c) 為索引時，如上述所言，由於 (b = 1 or b = 2) 形式上是 OR 表達式的情況，而非點查。所以會在 b 列停止，不會考慮 c > 1 的情況。所以目前為了兼容 TiDB 的邏輯，遇到這種情況盡量改寫為 a = 1 and b in (1, 2) and c > 1 的形式。

• 類似的如 ((a = 1 and b = 1) or (a = 2 and b = 2)) and c = 1 形式的式子，前段 OR 表達式實際上為點查的行為，但是由於是 OR 連接起來的式子，所以在 TiDB 的邏輯中作為範圍查詢處理，因此 c = 1 不會作為索引的計算條件處理。而這時改寫為 (a, b) in ((1, 1), (2, 2)) and c = 1 的形式也不會使 c = 1 選入索引計算的條件，原因是多列 in 的函數會被 TiDB 改寫為 OR 連接的形式，所以 ((a = 1 and b = 1) or (a = 2 and b = 2)) 和 (a, b) in ((1, 1), (2, 2)) 在 TiDB 中是完全一致的行為。針對這種情況，目前的辦法只有將這些條件都放入 OR 的子項中，針對這裡用到的例子，那就是要改寫為 ((a = 1 and b = 1 and c = 1) or (a = 2 and b = 2 and c = 1))。

計算邏輯區間

這一步驟中，利用上一步抽取出來的表達式估算出數據的邏輯區間範圍，後續會根據這個邏輯區間以及數據編碼方式構造物理區間進行數據訪問。我們仍然分為單列索引和多列索引兩個情況來介紹。

單列索引

這種情況下，輸入的表達式為 Column op Constant 形式的簡單表達式由 OR 以及 AND 連接而成。我們對每一個具體的操作符，都設計了一段對應的計算 range 的邏輯，當遇到 AND 或者 OR 時，會對兩個區間求交或者求並。在 point.go 中有一個 builder 的結構體用來處理上述邏輯。

在這個階段我們記錄 range 時用 rangePoint 的結構來存儲 range。

// Point is the end point of range interval.type point struct { value types.Datum excl bool // exclude start bool}

每個 point 代表區間的一個端點，其中的 excl 表示端點為開區間的端點還是閉區間的端點。start 表示這個端點是左端點還是右端點。

builder 中每個 buildFromXXX 的方法都是計算一個具體函數的 range 的方法。比如 buildFromIn 便是處理 in 函數 的方法。可以看到它首先對 in 函數的值列表的每個值都構造了一個 rangPoint 的單點區間，然後對這些區間放在一個 slice 中做排序以及去重。最終將去重後的結果輸出。

在 pointer.go 中還包含其他各類的函數的處理，具體可以翻閱源代碼。

除了對具體函數的處理外，pointer.go 中還有區間交和區間並的操作。intersection 和 union 分別代表區間交和區間並。兩個函數的邏輯均通過 merge 方法進行處理，通過傳入一個 flag 來區分。merge 函數做了如下兩個假設：

• a, b 兩個區間均已經做過去重
• 單個區間序列內部不會有重疊的部分

merge 函數使用 inRangeCount 來記錄當前位置被 a, b 兩個區間序列覆蓋的情況。區間求並的情況時，只要 a, b 兩個區間序列中有一個區間序列覆蓋便可以作為解輸出，被兩個區間同時覆蓋的端點必然是屬於一個更大的區間的內部不需要輸出。所以當 inRangeCount 為 1 時，即為需要輸出的區間端點。

當區間求交時，需要兩個序列都覆蓋到才是可以輸出的端點，所以當 inRangeCount 為 2 時，即為需要輸出的區間端點。

在得到最後的區間端點序列後，由 points2TableRanges 轉化為對外暴露的 range 結構，由 BuildTableRange 輸出到 plan package。

// NewRange represents a range generated in physical plan building phase.type NewRange struct { LowVal []types.Datum HighVal []types.Datum LowExclude bool // Low value is exclusive. HighExclude bool // High value is exclusive.}

在現在的 TiDB 中，單列索引和多列索引使用了相同的 range 結構，所以這裡的端點值為 slice 的形式。

多列索引

對於多列索引，當其為 AND 表達式時，根據前述我們可以知道，其形式必為索引前綴列上的等值條件再加上關於前綴之後一個列的複雜條件組成。所以我們只需要按順序處理點查的等值條件部分，將點查的區間依次 append 到 NewRange 中的 LowVal 和 HighVal 兩個 Slice 中即可（appendPoints2Ranges）。處理到最後一列時，將之前的 NewRange 按最後非點查列所計算得到的區間個數拷貝一下，再依次 append 即可。具體代碼可見 buildCNFIndexRange。

對於 OR 表達式的情況，由於此時 range 已經無法轉回 point 的結構。所以這裡重新實現了一下區間並的操作。實現的形式便是比較常見的將區間按左端點排序，在依次掃過區間的同時，記錄當前所有重疊過的區間的最右右端點來進行做區間並的演算法。區間並的具體的實現可見 unionRanges 方法。

Future Plan

• 目前 TiDB 對單列索引的處理在邏輯上已經非常完備，在實際表現上可能由於沒有對部分函數實現計算 range 的邏輯而有遺漏。這部分會根據情況進行優化。
• 如上文提到的，目前 TiDB 為了簡化 ranger 的邏輯，對多列索引做了一些假設。未來會嘗試去掉或者弱化這些假設，或者在前期對 SQL 進行更充分的改寫使得 SQL 不會觸發這些假設，來提供更加強大的功能，免於手動 rewrite 的麻煩。
• 目前 TiDB 對簡單式子的形式的檢查限定在了 Column op Constant 的形式。所以諸如 from_unixtime(timestamp_col) op datetime_constant 形式的條件是無法計算索引的，也需要手動 rewrite 為 timestamp_col op timestamp_constant 才可以使用到索引。這部分也會考慮進行改進以提升用戶體驗。

TiDB 源碼閱讀系列文章：

（十二）統計信息（上）

（十一）Index Lookup Join

（十）Chunk 和執行框架簡介

（九）Hash Join

（八）基於代價的優化

（七）基於規則的優化

（六）Select 語句概覽

（五）TiDB SQL Parser 的實現

（四）Insert 語句概覽

（三）SQL 的一生

（二）初識 TiDB 源碼

（一）序

推薦閱讀：