MySQL选择一个表读取数据的方式，取决于这种方式的执行成本。如果WHERE条件可以命中索引（包括主键索引和二级索引），那么计算WHERE条件范围内的记录数是计算使用索引执行查询的成本的一个关键指标。在这篇文章中，我们来看看这个关键指标是如何计算的。本文内容基于MySQL8.0.29源码。Text1.Overalloverview一个WHERE条件范围（例如WHEREa>=100ANDa<=200）是一个扫描区间[100,200]。扫描间隔具有起点和终点。在本文中，我们将扫描区间的起点称为左端点，该端点称为右端点。计算WHERE条件范围内有多少条记录，就是计算对应的扫描区间内有多少条记录。总体来说，会经历两个步骤：第一步，在record对应的索引的叶子节点中定位扫描区间的左端点和右端点。这个过程是从根节点自上而下进行的。在索引的每一层之后，数组中会保存该层左右端点记录所在索引页的页码，叶中的根节点到左右端点记录的距离将获得节点。索引页的路径。左端点路径存放在数组path1中，右端点路径存放在数组path2中，如下图所示：以一个3层的B-TREE索引为例说明这个自上而下的定位过程:定位索引叶子节点中间扫描区间的左端点和右端点的记录是独立执行的，但是执行过程是完全一样的，所以一起介绍。首先，在根节点中，左端点和右端点的记录都在根节点的范围内，path1[0]和path2[0]都会保存根节点的页码。左右端点对应的记录在根节点中可以是相同的记录，也可以是不同的记录。读取根节点中左端点和右端点记录指向的子节点的页码。然后，进入左端点和右端点记录对应的内节点，将左端点记录所在内节点的页码保存在path1[1]中，保存右端点记录所在内节点的页码端点记录位于path2[1]中。左右端点对应的记录可以是不同内节点的记录，也可以是同一内节点的相同记录或不同记录。读取每个内节点中左端点和右端点对应的记录指向的叶节点的页码。最后输入左端点和右端点记录对应的叶节点，将左端点记录所在叶节点的页码保存在path1[2]中，保存右端点记录所在叶节点的页码记录位于path2[2]。左右端点对应的记录可以是不同叶子节点中的记录，也可以是同一叶子节点中的相同记录或不同记录。定位扫描区间左右端点的过程在上一篇文章中有详细介绍。感兴趣的朋友可以点击此链接阅读：InnoDBB-TREE索引是如何定位一条记录的？第2步，计算扫描间隔记录数。第一步后得到左右两端的两个路径数组，数组中存储了从根节点到叶节点经过扫描区间左右端点的每个索引页的页码。计算扫描区间包含的记录数，最后计算出叶子节点的层级和扫描区间包含的记录数。由于叶子节点的层级，扫描区间内的记录可能分散在很多很多连续的叶子节点中。将扫描区间内的所有叶子节点的记录都一个一个读取是不现实的。这就需要叶节点的上层节点的帮助。上层节点的记录数就是其管辖范围内的叶节点数。但是叶子节点的上层节点所在的层级也可能有很多很多的节点在同一层级，那么就需要使用更高层级的节点，这样才能一层一层往上推，最终可能需要读取根节点有多少个子节点。正是因为计算扫描间隔包含多少条记录可能需要依赖上层节点。在源码的实现中，这个过程也是从根节点自上而下进行的。自上而下的过程是遍历左端点和右端点路径数组，计算从左端点记录到右端点记录每一层包含的记录数，最后到达叶子节点所在层级得到扫描间隔记录数。源码的实现是自上而下进行的，但是文章不能这样写，否则会陷入代码细节，写的时候很难看懂。下面介绍根据扫描区间左端点和右端点在叶节点中的不同位置计算扫描区间记录数的过程。请保持愉快的心情阅读，可能会更容易理解^_^2。场景分析我们在不同的场景中进行介绍，以便更好地理解。但是，不同的场景会涉及到一些又臭又长的定义，需要反复描述。在更好理解的基础上，我们也应该尽量保持内容的简洁。为此，这里列出了一些需要重复描述的定义，并用较短的描述代替，以简化内容。左索引页的记录数，在左端点记录所在的索引页中，从左端点记录的下一条记录到上界伪记录的上一条记录这一范围内的记录数当前索引页。右索引页的记录数，当前索引页中infimum伪记录的下一条记录到右端点记录所在索引页上右端点记录的上一条记录之间的记录数位于。左右端点之间的记录数，除左端点记录和右端点记录外，扫描区间内的其他用户记录数，即不包括所有索引页中的infimum和supremum伪记录.(1)同一记录扫描间隔的左端点和右端点记录为叶节点中的同一条记录。区间内除了左右端点记录外没有其他记录，左右端点之间的记录数=0。但这并不意味着扫描区间内的记录数为0。因为，扫描区间的记录数=左右端点之间的记录数+左端点记录+右端点记录。处理左右端点记录的计数逻辑，得到扫描间隔记录数。这个计算过程是所有场景共有的，将在第2节末尾单独一节介绍，这里不再赘述。(2)同一叶节点不同记录扫描区间的左端点和右端点记录是同一叶节点不同记录，计算逻辑比较简单。左右端点之间的记录数=右端点记录之前的记录数-左端点记录之前的记录数。左右端点记录前的记录数是指在它们所在的索引页中左右端点记录前面的记录数，如下图所示：(3)左端点相邻叶节点中的记录扫描间隔，右端点记录为相邻叶节点中的记录，计算逻辑还是比较简单的。左右端点之间的记录数=左索引页的记录数+右索引页的记录数。(4)扫描区间的左端点和右端点相隔小于等于9个叶子节点的索引页，其他索引页之间相隔，计算逻辑稍微有点复杂。左右端点之间的记录数=左索引页的记录数+中间索引页的用户记录数之和+右索引页的记录数。上述公式中，中间索引页用户记录条数之和的计算逻辑为：从扫描区间左端记录所在索引页的下一个索引页开始，从每个索引页的头信息PAGE_N_RECS中读取索引页中的用户记录数，累加求和，直到扫描区间右端点记录所在索引页的前一个索引页。PAGE_N_RECS中不包含Infimum、supremum伪记录。(5)计算扫描区间内记录数的逻辑，在前面章节介绍的间隔9个以上叶子节点的场景下计算准确。本节介绍的场景是：扫描区间左右端点的记录所在的索引页，中间有9个以上的索引页，如下图所示：本场景中，InnoDB不会读取扫描区间内的所有索引页，而是只读取索引页前面部分的用户记录数，并据此估算扫描区间内的用户记录数。估计过程如下：第一步，从记录所在扫描区间的左端点开始，索引页的下一个索引页开始，连续读取9个索引页中的用户记录数并累加.从索引页的头信息PAGE_N_RECS中读取每个索引页中的用户记录数，不包括infimum和supremum伪记录。第二步，将第一步得到的9个索引页的用户记录数+左索引页的记录数+右索引页的记录数之和，得到计算结果，InnoDB将此结果作为10个索引页上的用户记录数的总和。步骤3，将步骤2得到的10个索引页的用户记录数之和除以10，将计算结果作为扫描区间内每个索引页的平均用户记录数。第4步，将第3步得到的平均用户记录数*左右端点之间的索引页数（如下图），区间索引页中用户记录数的总和为获得。通过上层2.1~2.5节的计算逻辑得到左右端点记录之间的索引页数。第五步，左右端点之间的记录数=第四步得到的左右端点记录之间的索引页用户记录数之和+左索引页记录数+右索引页上的记录数。前面提到，在预估场景下，InnoDB会用10个索引页的用户记录数之和来计算每个索引的平均用户记录数。为什么本节的标题是左右端点之间的距离大于9个索引页？因为InnoDB将左索引页的记录数和右索引页的记录数加起来就是一个索引页的用户记录数，再加上扫描区间从左端开始的用户记录数之和从该点记录所在的下一个索引页读取的9个索引页中的用户记录数为10个索引页中的用户记录数。(6)处理左右端点记录的计数逻辑前面提到，扫描区间内的记录数=左右端点之间的记录数+左端点记录(0或1)+右端点记录(0或1).这是所有场景共有的逻辑，这里单独一节介绍。如果扫描区间的左端点是闭区间（比如WHEREa>=100），则需要将左端点的记录计入扫描区间的记录数中。上式中，左端点记录在括号中取0。否则，将不会被计算在内。上式中，左端点记录括号内取1。如果扫描区间的右端点是闭区间（比如WHEREa<=200），则需要将右端点的记录计入扫描区间的记录数中。上式中，右端点记录在括号中取0。否则，将不会被计算在内。上式中，右端点记录取括号中的1。然后，获取扫描间隔内的记录数。不过别担心，这可能还不是最终结果。(7)修正扫描区间记录数经过2.6节左右端点记录的计数逻辑处理，得到扫描区间记录数。如果扫描区间左右端点的记录所在的索引页之间有9个以上的索引页（即估计场景），在计算出扫描区间的记录数后，进行一系列修正需要做这个号码。首先，InnoDB认为估计的记录数会小于实际的记录数，所以会将前面计算的扫描区间内的记录数乘以2，得到扫描区间内被修正的记录数，即，修正记录数=扫描区间记录数*2。然后，InnoDB不会让估计的记录数大于表中记录数的一半。如果扫描区间内纠正的记录数超过表记录数的一半，则设置纠正记录数为表记录数的一半。最后修改的记录数就是扫描区间内的记录数，也就是最终的结果。(8)小结上一节介绍了按场景计算扫描区间内记录数的过程。为了使文章尽可能简洁，将处理左右端点记录的计数逻辑（2.6节）和修正后的扫描区间记录数（2.7节）独立分为两节，有点散。本小节用流程图总结一下前面的计算过程，如下：3.小结第2节从定位索引叶子节点中扫描区间的左端点和右端点对应的记录开始，介绍计算扫描间隔的次数记录了整个过程。第3节介绍了根据索引叶节点中左右端点记录的位置计算五种场景下扫描区间记录数的详细过程。通过五个场景计算出左右端点之间的记录数后，对左右端点记录进行计数逻辑处理，得到扫描区间内的记录数。对于精确的计算场景，这是最终结果。对于预估场景，需要对扫描区间内的记录数进行一系列修正，得到预估场景下的最终结果。本文转载自微信公众号“一树一溪”，可通过以下二维码关注。转载本文请联系艺书艺熙公众号。
