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

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

本文我們就一起來看看這個(gè)關(guān)鍵指標(biāo)是怎么計(jì)算的?

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

正文

1、整體概覽

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

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

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

這個(gè)過程是從根結(jié)點(diǎn)開始自上而下進(jìn)行的。

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

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

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

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

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

左右端點(diǎn)對(duì)應(yīng)的記錄，可能是根結(jié)點(diǎn)中的同一條記錄或不同記錄。

讀取根結(jié)點(diǎn)中左端點(diǎn)、右端點(diǎn)記錄指向的子結(jié)點(diǎn)的頁號(hào)。

然后，進(jìn)入左端點(diǎn)、右端點(diǎn)記錄對(duì)應(yīng)的內(nèi)結(jié)點(diǎn)，path1[1] 中保存左端點(diǎn)記錄所在內(nèi)結(jié)點(diǎn)的頁號(hào)，path2[1] 中保存右端點(diǎn)記錄所在內(nèi)結(jié)點(diǎn)的頁號(hào)。

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

讀取左端點(diǎn)、右端點(diǎn)在各自內(nèi)結(jié)點(diǎn)中對(duì)應(yīng)的記錄指向的葉結(jié)點(diǎn)的頁號(hào)。

最后，進(jìn)入左端點(diǎn)、右端點(diǎn)記錄對(duì)應(yīng)的葉結(jié)點(diǎn)，path1[2] 中保存左端點(diǎn)記錄所在葉結(jié)點(diǎn)的頁號(hào)，path2[2] 中保存右端點(diǎn)記錄所在葉結(jié)點(diǎn)的頁號(hào)。

左右端點(diǎn)對(duì)應(yīng)的記錄，可能是不同葉結(jié)點(diǎn)中的記錄，也可能是相同葉結(jié)點(diǎn)中的同一條記錄或不同記錄。

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

索引怎么定位一條記錄?

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

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

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

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

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

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

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

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

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

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

^_^

2、 場景分析

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

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

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

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

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

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

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

（1） 同一條記錄

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

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

因?yàn)椋瑨呙鑵^(qū)間的記錄數(shù)量 = 左右端點(diǎn)之間的記錄數(shù) + 左端點(diǎn)記錄 + 右端點(diǎn)記錄。

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

（2）同一個(gè)葉結(jié)點(diǎn)中的不同記錄

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

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

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

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

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

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

（4）相隔小于等于 9 個(gè)葉結(jié)點(diǎn)

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

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

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

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

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

（5）相隔大于 9 個(gè)葉結(jié)點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

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

為什么本小節(jié)的標(biāo)題是左右端點(diǎn)之間相隔大于 9 個(gè)索引頁?

因?yàn)?InnoDB 把左索引頁記錄數(shù)、右索引頁記錄數(shù)加起來當(dāng)作一個(gè)索引頁的用戶記錄數(shù)量，再加上從掃描區(qū)間左端點(diǎn)記錄所在索引頁的下一個(gè)索引頁開始讀取的 9

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

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

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

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

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

0。

否則不計(jì)入，上面算式中，左端點(diǎn)記錄括號(hào)內(nèi)取 1。

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

0。

否則不計(jì)入，上面算式中，右端點(diǎn)記錄括號(hào)內(nèi)取 1。

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

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

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

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

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

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

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

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

然后，InnoDB

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

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

（8）小結(jié)

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

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

三、 總結(jié)

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

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

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

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

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

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