Mysql的最左前缀匹配原则(上)

vlambda
2020-10-15

Mysql的最左前缀匹配原则(上)

最左前缀在mysql的官方文档中称之为leftmost prefix，该原则适用于多列索引，想仅仅用三言两语来说清楚什么是最左前缀匹配原则不太现实，但是如果使用官方文档的一个例子来说明该原则，或许会好得多。

假如现在有一张表的创建语句如下：

CREATE TABLE test (
    id         INT NOT NULL,
    last_name  CHAR(30) NOT NULL,
    first_name CHAR(30) NOT NULL,
    PRIMARY KEY (id),
    INDEX name (last_name,first_name)
);

那么如下的sql可以命中name索引：

SELECT * FROM test WHERE last_name='Jones';
SELECT * FROM testWHERE last_name='Jones' AND first_name='John';
SELECT * FROM test WHERE last_name='Jones' AND (first_name='John' OR first_name='Jon');
SELECT * FROM test WHERE last_name='Jones' AND first_name >='M' AND first_name < 'N';

如下的sql无法命中name索引：

SELECT * FROM test WHERE first_name='John';
SELECT * FROM test WHERE last_name='Jones' OR first_name='John';

为什么前四个sql可以命中name索引，后两个sql却不行呢？因为name索引的定义是last_name在前，first_name在后，所以它的最左前缀有两个：last_name、last_name first_name（题外话：如果有一个索引的定义为idx(col1, col2, col3)，那么它的最多前缀有哪些呢？答案是有三个：col1、col1 col2、col1 col2 col3），前4个sql的where条件都是以最左前缀的顺序依次作为查询条件，后2个sql却不是。

此时此刻，或许你还有很多疑问，比如为什么上面第3条or查询可以命中索引但是第6条就不行呢？范围查询呢？是不是我严格按照任意一个最左前缀书写sql，就一定会命中相应的索引？想要搞清楚这些问题，死记硬背一些原则或许是不合适的，还是应该尝试从本质上来探究这些问题。我们知道，在InnoDB存储引擎中，任何一个索引的数据结构都是B+树，该B+树如何构建取决于索引是如何定义的，以例子中的INDEX name (last_name,first_name)为例，肯定是以last_name为主要排序对象，如果last_name相同，则按照first_name排序，假如我们有如下数据行：

id=1, last_name=aaa, first_name=dwf;
id=2, last_name=zzz, first_name=ytr;
id=3, last_name=mmm, first_name=edf;
id=4, last_name=bbb, first_name=abc;
id=5, last_name=zzz, first_name=abc;
id=6, last_name=qqq, first_name=gfd;
id=7, last_name=aaa, first_name=rfg;
id=8, last_name=zzz, first_name=sdd;
id=9, last_name=hhh, first_name=bgf;
id=10, last_name=aaa, first_name=abc;
id=11, last_name=zzz, first_name=bfd;
id=12, last_name=lll, first_name=cba;
id=13, last_name=aaa, first_name=bvf;
id=14, last_name=zzz, first_name=abd;
id=15, last_name=lll, first_name=sdd;
id=16, last_name=mmm, first_name=nbv;
id=17, last_name=zzz, first_name=trd;
id=18, last_name=aaa, first_name=oiu;

假设一个数据块可以存放3行数据，那么它的B+树结构大概如下（索引页上面的三个字母代表last_name，下面的代表first_name）：

下面来逐个分析上面6个sql。

1、SELECT * FROM test WHERE last_name='jones';

通过根索引页定位到第二层中间的索引页
通过第二层中间的索引页定位到第三层的第三个数据页（因为jones排序在lll的前面）
发现没有last_name='jones'，返回null

因此可以命中索引。

2、SELECT * FROM testWHERE last_name='Jones' AND first_name='John';

通过根索引页定位到第二层中间的索引页
通过第二层中间的索引页定位到第三层的第三个数据页（因为jones排序在lll的前面）
发现没有last_name='jones'和first_name='John';，返回null

因此可以命中索引。

3、SELECT * FROM test WHERE last_name='Jones' AND (first_name='John' OR first_name='Jon');

该sql语句可以改写成，SELECT * FROM test WHERE last_name='Jones' AND first_name='John' OR（last_name='Jones' and first_name='Jon')，本质上和第2条sql一样，所以也可以命中索引。

4、SELECT * FROM test WHERE last_name='Jones' AND first_name >='M' AND first_name < 'N';

无非就是根据last_name一步步通过根索引页定位到相关的数据页，再通过数据页的页目录找到first_name是这个范围的，因为last_name相同的情况下，first_name是按顺序存储在数据页中的，所以也可以命中索引。

5、SELECT * FROM test WHERE first_name='John';

因为B+树是先按照last_name再按照first_name的顺序构建的，如果上去就按照first_name去查找相应的数据页，结果显然是不准确的。根索引页的first_name：dwf、gfd、ytr看起来确实是有顺序的，但实际上这完全是一个巧合，其实从第二层的第一个索引页的first_name也可以看出来：dwf、abc显然是无序的。只有当last_name一样时，first_name才是有顺序的，可以看看第三层第五个和第六个数据页，last_name都是zzz，first_name是按照顺序排列的，这也是为什么第4个sql可以命中索引的原因。

6、SELECT * FROM test WHERE last_name='Jones' OR first_name='John';

其实看这个sql的前半部分SELECT * FROM test WHERE last_name='Jones'其实可以通过该索引轻易地找到last_name='Jones'对应的数据页，但是下一步如何定位first_name='John'的数据页呢？显然等值查找first_name是无法使用该索引的，那就只能遍历聚簇索引的数据页，既然都遍历聚簇索引的数据页了，那为什么还要使用该索引定位last_name='Jones'的数据页呢，直接在遍历的时候顺带判断一下last_name的值不就好了吗，反正整个数据页都会加载到buffer_pool，无非就是在内存中做一次比较，所以不会命中该索引。

最后的话：以上仅仅是自己对于mysql理解，难免会有很多错误，望批评指正。