MySQL 為一個表選擇讀取數(shù)據(jù)的方式，取決于這種方式的執(zhí)行成本。

如果 WHERE 條件能夠命中索引(包含主鍵索引、二級索引)，計算 WHERE 條件范圍內(nèi)的記錄數(shù)量，是計算使用索引執(zhí)行查詢的成本的關鍵指標。

本文我們就一起來看看這個關鍵指標是怎么計算的?

本文內(nèi)容基于 MySQL 8.0.29 源碼。

正文

1、整體概覽

一個 WHERE 條件范圍(例如 WHERE a >= 100 AND a <= 200)，就是一個掃描區(qū)間 [100,200]，掃描區(qū)間有起點和終點，本文中我們把掃描區(qū)間的起點叫作 左端點，終點叫作右端點。

計算 WHERE 條件范圍內(nèi)有多少條記錄，就是計算其對應的掃描區(qū)間有多少條記錄，整體來看，會經(jīng)過兩大步驟：

第 1 步，定位索引葉結(jié)點中掃描區(qū)間左端點、右端點對應的記錄。

這個過程是從根結(jié)點開始自上而下進行的。

經(jīng)過索引的每一層，會分別把該層中左端點、右端點記錄所在索引頁的頁號，保存到數(shù)組里，得到從根結(jié)點到葉結(jié)點中的左端點、右端點記錄經(jīng)過的索引頁的路徑。

左端點路徑保存在數(shù)組 path1 中，右端點路徑保存在數(shù)組 path2 中，如下圖所示：

以一個 3 層的 B-TREE 索引為例，來說明這個自上而下的定位過程：

定位索引葉結(jié)點中掃描區(qū)間左端點、右端點記錄，是獨立進行的，但是執(zhí)行流程完全一樣，所以放在一起介紹了。

首先，在根結(jié)點中，左端點、右端點記錄都在根結(jié)點范圍內(nèi)，path1[0]、path2[0] 中都會保存根結(jié)點的頁號。

左右端點對應的記錄，可能是根結(jié)點中的同一條記錄或不同記錄。

讀取根結(jié)點中左端點、右端點記錄指向的子結(jié)點的頁號。

然后，進入左端點、右端點記錄對應的內(nèi)結(jié)點，path1[1] 中保存左端點記錄所在內(nèi)結(jié)點的頁號，path2[1] 中保存右端點記錄所在內(nèi)結(jié)點的頁號。

左右端點對應的記錄，可能是不同內(nèi)結(jié)點中的記錄，也可能是相同內(nèi)結(jié)點中的同一條記錄或不同記錄。

讀取左端點、右端點在各自內(nèi)結(jié)點中對應的記錄指向的葉結(jié)點的頁號。

最后，進入左端點、右端點記錄對應的葉結(jié)點，path1[2] 中保存左端點記錄所在葉結(jié)點的頁號，path2[2] 中保存右端點記錄所在葉結(jié)點的頁號。

左右端點對應的記錄，可能是不同葉結(jié)點中的記錄，也可能是相同葉結(jié)點中的同一條記錄或不同記錄。

關于定位掃描區(qū)間左端點、右端點記錄的過程，上一篇文章中有詳細介紹，感興趣的小伙伴可以點擊這個鏈接閱讀：InnoDB B-TREE

索引怎么定位一條記錄?

第 2 步，計算掃描區(qū)間的記錄數(shù)量。

經(jīng)過第 1 步，得到了左右端兩個路徑數(shù)組，數(shù)組中保存著從根結(jié)點到葉結(jié)點，掃描區(qū)間左右端點所經(jīng)過的每一個索引頁的頁號。

計算掃描區(qū)間包含多少條記錄，最終是要計算葉結(jié)點所在的層級，掃描區(qū)間中包含的記錄數(shù)量。

由于葉結(jié)點所在的層級，掃描區(qū)間中的記錄可能會分散在很多很多個連續(xù)的葉結(jié)點中，挨個讀取掃描區(qū)間中的所有葉結(jié)點的記錄數(shù)量是不現(xiàn)實的，這就需要借助葉結(jié)點的上層結(jié)點了。

上層結(jié)點中的記錄數(shù)量就是其管轄范圍內(nèi)的葉結(jié)點的數(shù)量。

然而，葉結(jié)點的上層結(jié)點所在的層級，也可能有很多很多的同級結(jié)點，那又需要借助更上一層結(jié)點，這樣逐層往上推，最終可能需要讀取根結(jié)點有多少個子結(jié)點。

正是因為計算掃描區(qū)間包含多少條記錄，可能需要依賴上層結(jié)點，在源碼的實現(xiàn)中，這個過程也是從根結(jié)點自上而下進行的。

自上而下進行的過程，就是遍歷左端點、右端點路徑數(shù)組，計算每一層從左端點記錄到右端點記錄這個區(qū)間內(nèi)包含的記錄數(shù)量，最終到達葉結(jié)點所在的層級，得到掃描區(qū)間的記錄數(shù)量。

源碼的實現(xiàn)自上而下進行，文章卻不能這么寫，否則陷入代碼細節(jié)，寫出來也很晦澀難懂。

接下來，我們根據(jù)掃描區(qū)間左端點、右端點記錄在葉結(jié)點中的不同位置，分場景介紹計算掃描區(qū)間的記錄數(shù)量的過程，請大家保持愉悅的心情看下去，可能會更容易看懂

^_^

2、 場景分析

我們分場景進行介紹是為了更好理解，但是，不同場景下都會涉及到一些又臭又長并且需要重復描述的定義。

在更好理解的基礎上，我們也要盡量保持內(nèi)容的簡潔，為此，把一些需要重復描述的定義在這里列出來，并用短一點的描述來代替，以簡化內(nèi)容。

左索引頁記錄數(shù)，左端點記錄所在的索引頁中，從左端點記錄的下一條記錄開始，直到當前索引頁中的 supremum

偽記錄的上一條記錄為止，這個范圍內(nèi)的記錄數(shù)量。

右索引頁記錄數(shù)，右端點記錄所在的索引頁中，從當前索引頁中的 infimum偽記錄的下一條記錄開始，直到右端點記錄的上一條記錄為止，這個范圍內(nèi)的記錄數(shù)量。

左右端點之間記錄數(shù)，除了左端點記錄、右端點記錄之外，掃描區(qū)間中的其它用戶記錄的數(shù)量，也就是說，所有索引頁中的 infimum、supremum

偽記錄都不包含在內(nèi)。

（1） 同一條記錄

掃描區(qū)間左端點、右端點記錄是葉結(jié)點中的同一條記錄，除去左右端點記錄之外，區(qū)間之內(nèi)沒有其它記錄，左右端點之間記錄數(shù) = 0。

但是，這并不意味著掃描區(qū)間的記錄數(shù)量就為 0。

因為，掃描區(qū)間的記錄數(shù)量 = 左右端點之間的記錄數(shù) + 左端點記錄 + 右端點記錄。

處理左右端點記錄的計數(shù)邏輯，然后得到掃描區(qū)間記錄數(shù)量，這個計算過程是所有場景共用的，會在第 2 節(jié)的結(jié)尾處單獨用一個小節(jié)來介紹，這里先按下不表。

（2）同一個葉結(jié)點中的不同記錄

掃描區(qū)間左端點、右端點記錄是同一個葉結(jié)點中的不同記錄，計算邏輯也比較簡單。

左右端點之間記錄數(shù) = 右端點記錄之前的記錄數(shù)量 - 左端點記錄之前的記錄數(shù)量。

左右端點記錄之前的記錄數(shù)量，指的是它們共同所在的索引頁中，左右端點記錄各自前面有多少條記錄，如下圖所示：

（3）相鄰葉結(jié)點中的記錄

掃描區(qū)間左端點、右端點記錄是相鄰葉結(jié)點中的記錄，計算邏輯依然比較簡單。

左右端點之間記錄數(shù) = 左索引頁記錄數(shù) + 右索引頁記錄數(shù)。

（4）相隔小于等于 9 個葉結(jié)點

掃描區(qū)間左端點、右端點記錄所在的索引頁，中間隔著其它索引頁，計算邏輯開始變得有一點點復雜了。

左右端點之間記錄數(shù) = 左索引頁記錄數(shù) + 中間索引頁用戶記錄數(shù)之和 + 右索引頁記錄數(shù)。

上面算式中，中間索引頁用戶記錄數(shù)之和計算邏輯如下：

從掃描區(qū)間左端點記錄所在索引頁的下一個索引頁開始，從每個索引頁的頭信息 PAGE_N_RECS中讀取索引頁中的用戶記錄數(shù)量并累加求和，直到掃描區(qū)間右端點記錄所在索引頁的上一個索引頁為止。

PAGE_N_RECS 中不包含 infimum、supremum 偽記錄。

（5）相隔大于 9 個葉結(jié)點

前面幾個小節(jié)介紹的場景，計算掃描區(qū)間記錄數(shù)量的邏輯，都是精確計算。

本小節(jié)介紹的場景是：掃描區(qū)間左端點、右端點記錄所在的索引頁，中間隔著大于 9 個索引頁，如下圖所示：

此場景下，InnoDB不會讀取掃描區(qū)間內(nèi)所有索引頁中的用戶記錄數(shù)量，而是只讀取前面一部分索引頁中的用戶記錄數(shù)量，并據(jù)此估算出掃描區(qū)間內(nèi)的用戶記錄數(shù)量，估算過程是這樣的：

第 1 步，從掃描區(qū)間左端點記錄所在索引頁的下一個索引頁開始，連續(xù)讀取 9 個索引頁中的用戶記錄數(shù)量并累加求和。

每個索引頁中的用戶記錄數(shù)量都是從索引頁的頭信息 PAGE_N_RECS 中讀取，不包含 infimum、supremum 偽記錄。

第 2 步，第 1 步得到的 9 個索引頁的用戶記錄數(shù)量之和 + 左索引頁記錄數(shù) + 右索引頁記錄數(shù)，得到計算結(jié)果，InnoDB 把這個結(jié)果當作 10

個索引頁的用戶記錄數(shù)量之和。

第 3 步，第 2 步得到的10 個索引頁的用戶記錄數(shù)量之和，除以 10，得到的計算結(jié)果，作為掃描區(qū)間范圍內(nèi)每個索引頁的平均用戶記錄數(shù)。

第 4 步，第 3 步得到的平均用戶記錄數(shù) * 左右端點之間間隔的索引頁數(shù)(如下圖所示)，得到間隔索引頁的用戶記錄數(shù)量之和。

左右端點記錄之間的索引頁數(shù)，就是對上一層級進行 2.1 ~ 2.5 小節(jié)的計算邏輯得到。

第 5 步，左右端點之間記錄數(shù) = 第 4 步得到的左右端點記錄之間間隔索引頁的用戶記錄數(shù)量之和 + 左索引頁記錄數(shù) + 右索引頁記錄數(shù)。

前面說了在估算場景下，InnoDB 會用 10 個索引頁中的用戶記錄數(shù)量之和計算每個索引的平均用戶記錄數(shù)。

為什么本小節(jié)的標題是左右端點之間相隔大于 9 個索引頁?

因為 InnoDB 把左索引頁記錄數(shù)、右索引頁記錄數(shù)加起來當作一個索引頁的用戶記錄數(shù)量，再加上從掃描區(qū)間左端點記錄所在索引頁的下一個索引頁開始讀取的 9

個索引頁中的用戶記錄數(shù)量之和，就是 10 個索引頁的用戶記錄數(shù)量了。

（6） 處理左右端點記錄的計數(shù)邏輯

前面提到過，掃描區(qū)間的記錄數(shù)量 = 左右端點之間記錄數(shù) + 左端點記錄(0 或 1) + 右端點記錄(0 或 1)。

這是所有場景共用的邏輯，在這里單獨用一小節(jié)來介紹。

如果掃描區(qū)間左端點是閉區(qū)間(例如 WHERE a >= 100)，則左端點記錄需要計入掃描區(qū)間的記錄數(shù)量，上面算式中，左端點記錄括號內(nèi)取

0。

否則不計入，上面算式中，左端點記錄括號內(nèi)取 1。

如果掃描區(qū)間右端點是閉區(qū)間(例如 WHERE a <= 200)，則右端點記錄需要計入掃描區(qū)間的記錄數(shù)量，上面算式中，右端點記錄括號內(nèi)取

0。

否則不計入，上面算式中，右端點記錄括號內(nèi)取 1。

然后，就得到了掃描區(qū)間的記錄數(shù)量。

不過，別著急，這有可能還不是最終結(jié)果。

（7） 修正掃描區(qū)間記錄數(shù)量

經(jīng)過 2.6 小節(jié)中左右端點記錄的計數(shù)邏輯處理，已經(jīng)得到了掃描區(qū)間的記錄數(shù)量。

如果掃描區(qū)間左端點、右端點記錄所在的索引頁，中間隔著大于 9

個索引頁(也就是估算場景)，計算得到掃描區(qū)間的記錄數(shù)量之后，還需要對這個數(shù)量進行一系列修正。

首先，InnoDB 認為估算的記錄數(shù)量都會比實際數(shù)量少，所以，會對前面計算得到的掃描區(qū)間記錄數(shù)量乘以 2，得到掃描區(qū)間的修正記錄數(shù)量，即修正記錄數(shù)量 =

掃描區(qū)間的記錄數(shù)量 * 2。

然后，InnoDB

不會讓估算記錄數(shù)量大于表中記錄數(shù)量的一半，如果掃描區(qū)間的修正記錄數(shù)量超過表中記錄數(shù)量的一半，就把修正記錄數(shù)量設置為表中記錄數(shù)量的一半。

最后，修改記錄數(shù)量就是掃描區(qū)間的記錄數(shù)量，這才是最終結(jié)果。

（8）小結(jié)

前面分場景介紹計算掃描區(qū)間的記錄數(shù)量的過程，為了保持文章盡量簡潔，把處理左右端點記錄的計數(shù)邏輯(2.6 小節(jié))、修正掃描區(qū)間記錄數(shù)量(2.7小節(jié))獨立成為兩個小節(jié)，有一點零散。

本小節(jié)以一張流程圖來對前面的計算過程進行總結(jié)，如下：

三、 總結(jié)

第 2 節(jié) 以定位索引葉結(jié)點中掃描區(qū)間左端點、右端點對應的記錄開始，介紹了計算掃描區(qū)間記錄數(shù)量的整體過程。

第 3 節(jié) 根據(jù)索引葉結(jié)點中，左右端點記錄所在位置的不同，分 5 種場景介紹了計算掃描區(qū)間記錄數(shù)量的詳細過程。

經(jīng)過 5 種場景計算得到左右端點之間記錄數(shù)之后，再進行左右端點記錄的計數(shù)邏輯處理，得到掃描區(qū)間的記錄數(shù)量。

對于精確計算場景，這就是最終的結(jié)果了。

對于估算場景，還需要對掃描區(qū)間的記錄數(shù)量進行一系列修正，才能得到估算場景下的最終結(jié)果。

本文轉(zhuǎn)載自微信公眾號「一樹一溪」，可以通過以下二維碼關注。轉(zhuǎn)載本文請聯(lián)系一樹一溪公眾號。