侧边栏壁纸
  • 累计撰写 244 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论
隐藏侧边栏

全值匹配查询时索引的使用与最左前缀原则的底层原理

kaixindeken
2021-05-03 / 0 评论 / 0 点赞 / 78 阅读 / 4,990 字

初始化数据表

CREATE TABLE `demo` (
  `a` int(10) unsigned NOT NULL,
  `b` int(10) unsigned NOT NULL,
  `c` int(10) unsigned NOT NULL,
  PRIMARY KEY (`a`),
  KEY `b_c` (`b`, `c`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

可以看到,这张表设置了两个索引,分别是主键索引 a 和联合索引 b_c,通过之间介绍的 B+ 索引树创建原理,我们不难得知只有 SQL 查询条件包含 a 或 b 时才会命中索引,如果查询条件仅包含 c 的话是不会使用任何索引的。

另外 a 列对应的索引是聚簇索引,进行数据表查询时不存在回表操作,而 b_c 是二级索引,不过由于这个二级索引里面正好包含 a、b、c 所有列的值,所以进行查询时也不存在回表操作。可如果数据表多出了一个 d 列,且查询字段里面包含 d 列,则需要通过主键字段值去聚簇索引回表获取所有数据:

CREATE TABLE `demo` (
  `a` int(10) unsigned NOT NULL,
  `b` int(10) unsigned NOT NULL,
  `c` int(10) unsigned NOT NULL,
  `d` varchar(32) NOT NULL,
  PRIMARY KEY (`a`),
  KEY `b_c` (`b`, `c`),
  KEY (`d`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

为了系统介绍不同类型查询语句的索引使用,我们接下来的介绍里默认 demo 表包含 d 列。

填充数据时对应的存储过程代码如下:

delimiter ;;
create procedure insertdata()
begin
  declare i int;  
  declare s varchar(32);
  set i=1;  
  while(i<=1000000)do
      set s=md5(i);
      insert into demo values(i, i, i, s);    
      set i=i+1;  
  end while;
end;;
delimiter ;
call insertdata();

这里我们将 i 的值通过 md5 算法进行哈希计算后存储到 d 列中。

数据表填充完成后,对应的索引数据也就维护好了,我们可以先感受下没有使用索引与使用索引的查询性能对比:

1.jpeg

这三个索引对应的底层 B+ 树叶子节点单个数据页数据结构如下所示(假设每个用户记录数据页存放了 100 条记录):

1.png

在每个叶子节点数据页中,索引数据记录默认都是按照索引值升序排列的,这样一来就可以通过二分查找快速定位到指定索引值对应的数据信息,如果该索引是二级索引的话,比如上面的 b_c 和 d 索引,要获取完整数据记录,需要到聚簇索引回表获取,对于联合索引而言,会按照联合索引设置的字段顺序依次排序,比如这里的 b_c 联合索引,会先按照 b 列值排序,如果 b 列值相同,再按照 c 列值升序排序。

全值匹配

索引的命中

所谓全值匹配指的是形如下面这种 SQL 查询语句:

SELECT * FROM `demo` WHERE a = 1;

SELECT * FROM `demo` WHERE b = 100 AND c = 1000;

SELECT * FROM `demo` WHERE d = 'f899139df5e1059396431415e770c6dd';

在这种类型的查询语句中,如何命中索引非常简单直白,只要查询条件对应的列包含了索引列,就可以使用索引进行查询,所以上面三个查询语句都可以使用索引。而如果查询条件不包含索引列,或者没有命中,比如下面这个查询语句:

SELECT * FROM `demo` WHERE c = 1000;

就不会使用索引而是通过全表扫描,当扫描到的行对应 c 列值等于 1000,将其放入结果集,然后继续扫描,直到数据表最后一行,最后将所有符合条件的结果集返回。

讲到这里,我们也可以简单分析下唯一索引与普通索引的性能对比,由于唯一索引全表只包含一行符合条件的记录,所以定位到索引值后可以立即返回查询结果,而普通索引需要将满足条件的查询结果都返回,这里可能包含多条记录,不过既然是索引,那就都已经做好了排序,因此符合条件的多条记录是扎堆在一起的,只需要通过简单的位移操作即可返回所有满足条件的结果集,除非满足条件的记录特别多,否则,两者的性能差异微乎其微,但是唯一索引在插入或者更新数据时需要额外的开销,所以一般情况下将索引设置为普通索引即可,然后把去重逻辑放到业务代码层实现。

这里有些人可能会疑惑,c 列不是已经维护到 b_c 联合索引了吗,确实,但是通过前面分析的 B+ 树底层数据结构,应该可以看到,位于第二顺位排序的 c 列是无法应用二分查找进行定位的,不管是目录项还是叶子节点的搜索都是如此。

联合索引的优势和最左前缀原则

那设置联合索引的意义何在呢?

通过简单分析应该不难理解,如果在已知 b 列值的情况下,再去过滤 c 列值就可以应用二分查找进行非常高效的查询了,所以联合索引非常适用于如下 SQL 查询语句:

SELECT * FROM `demo` WHERE b = 100 AND c = 1000;

另外,通过上述分析,显然对于查询条件只包含联合索引第一个列值的 SQL 语句,也可以应用索引:

SELECT * FROM `demo` WHERE b = 100;

注:如果联合索引包含更多列,比如 (b, c, x),查询条件仅包含 b 和 x 的话,那么对于 x 列的过滤也无法应用索引,原因和上面分析的一样,只有同时包含 b、c、x 或者 b、c 或者 b 的情况下才能命中索引。

所以,在业务逻辑主要包含上述两种查询语句的情况下,使用联合索引可以避免额外设置的 c 索引,减少不必要的索引维护成本,并且如果查询字段只包含主键和索引字段的情况下,也可以避免回表操作:

SELECT a, b, c FROM `demo` WHERE b = 100 AND c = 1000;

最后,对于联合索引的使用,查询条件不区分索引列的先后顺序,比如如下这条 SQL 语句,也会命中联合索引:

SELECT * FROM `demo` WHERE c = 1000 AND b = 100;

这是因为在 InnoDB 存储引擎之上的 MySQL Server 层,有一个优化器对 SQL 语句进行优化,从而生成最优的执行计划,我们可以使用 explain 语句查看联合索引的几种查询语句执行计划:

1.jpeg

对于以上 SQL 查询,只有联合索引的最左侧字段才能应用索引的限制,被称之为最左前缀原则,有些地方也将其称作最左匹配原则。

字符串模糊查询

除了联合索引之外,最左前缀原则在数据库的字符串查询场景中也有体现,比如在模糊查询中,只有形如 WHERE d LIKE xxx% 这样的查询条件才能应用设置在 d 列上的索引:

1.jpeg

其实细想一下背后的原因,字符串列值的排序和联合索引很像:从第一个字符开始比较,如果第一个字符相同,再看第二个,依次类推。。。把这里的字符对应联合索引中的列值,可不就是一个模子刻出来的嘛!

也就是说,对于应用了索引的字符串列而言,前 N 个字符都是排序好的,这也是为什么通过 'xxx%' 可以使用索引,而 %xxx 不行的原因,就好比 WHERE b = ? 可以使用索引,而 WHERE c = ? 不行。当然,如果你的业务逻辑需要匹配的是 %xxx 后缀,比如域名、邮箱字段,可以将字符串逆序存放到数据库,这样,就可以使用 xxx% 使用索引进行匹配了。

字符串前缀索引

此外,我们可以为字符串列设置指定长度的前缀索引,以便缩短索引长度,提高查询效率,降低空间成本:

CREATE TABLE `demo` (
  `a` int(10) unsigned NOT NULL,
  `b` int(10) unsigned NOT NULL,
  `c` int(10) unsigned NOT NULL,
  `d` varchar(32) NOT NULL,
  PRIMARY KEY (`a`),
  KEY `b_c` (`b`, `c`),
  KEY `d` (d(6))
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

这里我们通过 d(6) 为 d 列的前 6 个字符创建索引,这样一来,初始化数据后,在 d 索引树的叶子节点中,索引值就是 d 列值的前 6 个字符,而不是完整的 d 列值:

1.png

这个使用,使用 d 字段作为查询条件,依然可以使用 d 这个索引,此时索引长度变成了 26,而不是之前的 130:

1.jpeg

和使用完整的字符串值作为索引不同,使用索引前缀进行查询的时候,以上面这个查询语句为例,会先从索引树中找到与 a9b7ba 索引值匹配的记录,然后去主键索引回表查询完整记录对应的 d 字段值,是否等于 a9b7ba70783b617e9998dc4dd82eb3c5,如果相等则将其放到结果集,否则丢弃,这里需要注意的是,不同 d 字段值前 6 个字符可能完全一样,这种情况下,会在 d 索引中继续查找下一条记录看索引值是否等于 a9b7ba,以此类推,直到下一个索引值不为 a9b7ba,将结果集返回。所以,只要字符串前缀辨识度足够高的话,完全可以以更低的维护成本,更高的查询效率通过前缀索引的方式设置字符串类型字段的列索引。

至于这个前缀长度如何设置,可以先通过如下语句查询该字段有多少条相同记录:

SELECT COUNT(DISTINCT `d`) AS len FROM `demo`;

和使用完整的字符串值作为索引不同,使用索引前缀进行查询的时候,以上面这个查询语句为例,会先从索引树中找到与 a9b7ba 索引值匹配的记录,然后去主键索引回表查询完整记录对应的 d 字段值,是否等于 a9b7ba70783b617e9998dc4dd82eb3c5,如果相等则将其放到结果集,否则丢弃,这里需要注意的是,不同 d 字段值前 6 个字符可能完全一样,这种情况下,会在 d 索引中继续查找下一条记录看索引值是否等于 a9b7ba,以此类推,直到下一个索引值不为 a9b7ba,将结果集返回。所以,只要字符串前缀辨识度足够高的话,完全可以以更低的维护成本,更高的查询效率通过前缀索引的方式设置字符串类型字段的列索引。

至于这个前缀长度如何设置,可以先通过如下语句查询该字段有多少条相同记录:

SELECT COUNT(DISTINCT `d`) AS len FROM `demo`;

1.jpeg

如果太多字段值相同不建议使用前缀索引,接下来可以进一步通过如下 SQL 语句获取该字段指定长度前缀有多少条相同记录:

SELECT COUNT(DISTINCT LEFT(`d`,4)) AS len4 FROM `demo`;
SELECT COUNT(DISTINCT LEFT(`d`,5)) AS len5 FROM `demo`;
SELECT COUNT(DISTINCT LEFT(`d`,6)) AS len6 FROM `demo`;
SELECT COUNT(DISTINCT LEFT(`d`,7)) AS len7 FROM `demo`;
SELECT COUNT(DISTINCT LEFT(`d`,8)) AS len8 FROM `demo`;

1.jpeg

直到找到满足需求的前缀长度,当然,你可以选择接受一定程度的损失,比如 3%,那么将前缀长度设置为 6 即可,如果是 1%,则设置索引长度前缀为 7,如果是 0,则设置前缀长度为 11:

1.jpeg

不过没有必要,8 以上都已经非常小了。饶是如此,索引长度也远远低于字符串原本的长度 32。

0

评论区