索引

1.索引基础

MySQL先在索引上按值进行查找,然后返回所有包含该值的数据行

索引可以包含一个或多个列的值。如果索引包含多个列,那么列的顺序也是十分重要的,因为MySQL只能高效地使用索引的最左前缀列。创建一个包含两个列的索引,和创建两个只包含一个列的索引是大不相同的,下面将详细介绍。

1.1索引的类型

在MySQL中,索引是在存储引擎层实现的而不是在服务器层实现的。所以,并没有统一的索引标准:不同的存储引擎的索引的工作方式并不一样,也不是所有的存储引擎都支持所有类型的索引。即使多个存储引擎支持同一类型的索引,其底层的实现也可能不同。

B-Tree索引

存储引擎以不同的方式使用B-Tree索引,性能也各有不同,各有优劣。例如MyISAM使用前缀压缩技术使得索引更小,但InnoDB则按照原始数据格式进行存储。再如,MyISAM索引通过数据的物理位置引用被索引的行,而InnoDB则根据主键引用被索引的行。

B-Tree对索引列是顺序组织的,所以很适合查找范围数据。例如,在一个基于文本域的索引树上,按字母顺序传递连续的值进行查找是非常合适的,所以想‘找出所有以I到K开头的名字’,这样的查找效率是很高的。

假设有如下数据表:

create table perple(
    last_name varchar(50) not null,
    first_name varchar(50) not null,
    dob date not null,
    gender enmu('m','f') not null,
    key(last_name,first_name,dob)
);

索引对多个值进行排序是create table语句中定义索引时列的顺序。

B-Tree索引适用于全键值、键值范围、键前缀查找。其中键前缀查找只适合于根据最左前缀的查找。前面所述的索引对如下类型的查询有效。

  1. 全值匹配:全值匹配指的是和索引中的所有列进行匹配
  2. 匹配最左前缀:指的是只是用索引中的前几列
  3. 匹配列前缀:只匹配某一列的值的开头部分
  4. 匹配范围值:例如前面提到的索引可用于查找姓在Allen和Barry之间的人,这里也只使用了索引的第一列。
  5. 精确匹配某一列并范围匹配另一列:前面提到的索引可可用于查找所有姓为Allen,并且名字是字母K开头的人,即第一列全匹配,第二列范围匹配。
  6. 只访问索引的查询:B-Tree通常支持“只访问索引的查询”,即查询只需要访问索引,而无需访问数据行。

因为索引树中的节点都是有序的,所以除了按值查找之外,索引还用于查询中的order by操作。

B-Tree索引的限制

  • 如果不是按照索引的最左列开始查找,则无法使用索引。
  • 不能跳过索引中的列。例如索引(a,b,c),但(a,c)只能使用到a列
  • 如果查询中有某个列的范围查找,则其右边所有列都无法使用索引优化查找。例如查询where last_name="Smith" and first_name like "J%" and dob = "1975-09-09"这个查询只能使用索引的前两列,以为这里like是一个范围条件。如果范围查询列值的数量有限,那么可以通过使用多个等于条件来替代范围条件。

哈希索引

哈希索引基于哈希表实现,只有精确匹配索引所有列的查询才有效。对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码。哈希索引将所有的哈希码存储在索引中,同时在哈希表中保存指向每个数据行的指针。

因为索引本身只需存储对应的哈希值,所以索引的结构十分紧凑,这让哈希索引的查找速度非常快,然而哈希索引也有它的限制:

  • 哈希索引只包含哈希值和行指针,而不存储字段值,所以不能使用索引中的值来避免读取行。不过访问内存的速度非常快,所以大部分情况这一点对性能的影响并不明显。
  • 哈希索引数据并不是按照索引值顺序存储的,所以也就无法用于排序。
  • 哈希索引也不支持部分索引列匹配查找,因为哈希索引始终是使用索引列的全部内容来计算哈希值的。
  • 哈希索引只支持等值比较查询,包括=、in、<=>,也不支持范围查询 例如<、>
  • 访问哈希索引的数据非常快,除非有很多哈希冲突(不同的索引列值有相同的哈希值)。当出现哈希冲突的时候,存储引擎必须遍历链表中的所有行指针,逐行进行比较,直到找到所有符合条件的行。
  • 如果哈希冲突很多的话,一些索引维护操作的代价也会提高。

自定义哈希索引

创建自定义哈希索引。如果存储隐形不支持哈希索引,可以模拟InnoDB一样创建哈希索引,这样可以享受一些哈希索引的便利,例如只需要很小的索引就可以为超长的键创建索引。

思路很简单:在B-Tree基础上创建一个伪哈希索引。这和真正的哈希索引不是一回事,因为还是使用的B-Tree进行查找,但是它使用哈希值而不是键本身进行索引查找,需要做的就是在查询的where子句中手动指定使用哈希函数。

下面是一个实例,例如需要存储大量URL,并需要根据URL进行查找。如果使用B-Tree来存储URL,存储的内容就会很大,因为URL本身都很长。正常情况下会有如下查询:

select id from url where url = 'http://www.mysql.com';

若删除原来URL列上的索引,而新增一个被索引的url_crc列,使用crc32做哈希,就可以使用下面的方式查询:

select id from url where url = 'http://www.mysql.com' and url_crc = crc32("http://www.mysql.com");

这样做的性能会非常高,因为MySQL优化器会使用这个选择性很高而体积很小的基于url_crc列的索引来完成查找。即使有多个记录相同的索引值,查找仍然很快,只需要根据哈希值做快速的整数比较就能找到索引条目,然后一一比较返回对应的行。

这样实现的缺陷就是需要维护哈希值。可以手动维护,也可以使用触发器实现。

要避免冲突问题,必须在where条件中带入哈希值和对应列值。如果不是想查询具体值,例如只是统计记录数(不精确的)则可以不带入列值,直接使用crc32的哈希值查询即可。

2.索引的优点

索引有如下三个优点:
1. 索引大大减少了服务器需要扫描的数据量
2. 索引可以帮助服务器避免排序和临时表
3. 索引可以将随机I/O变为顺序I/O(B-Tree索引,按照顺序存储数据,所以MySQL可以用来做order by和group by操作)

索引是最好的解决方案吗?

索引并不总是最好的工具。总的来说,只有当索引帮助存储引擎快速查找到记录带来的好处大于其带来的额外工作时,索引才是有效的。对于非常小的表,大部分情况下简单的全表扫描更高效。对于中到大型的表,索引就非常有效,但对于特大型的表,建立和使用索引的代价将随之增大。这种情况下,则需要一种技术可以直接区分出查询需要的一组数据,而不是一条记录一条记录的匹配。例如可以使用分区技术。

如果表的数据量特别大,可以建立一个元数据信息表,用来查询需要用到的某些特性。例如执行那些需要聚合多个应用分布在多个表的数据的查询,则需要记录“哪个用户的信息存储在哪个表中”的元数据,这样在查询时就可以忽略那些不包含指定用户信息的表。

3.高性能的索引策略

1.独立的列

如果查询中的列不是独立的,则MySQL不会使用索引。独立的列是指索引列不能使表达式的一部分,也不能是函数的参数。

例如下面这个查询不能使用actor_id列索引:

select actor_id from actor where actor_id + 1 = 5;

可以看出表达式其实等价于actor_id = 4 ,但是MySql无法自动解析这个方程式。这完全使用户行为,应该养成简化where条件的习惯,使用将索引列单独放在比较符号的一侧。

2.前缀索引和索引选择性

有时候需要索引很长的字符串,这样会让索引变得很慢。一个策略是前面提到的模拟哈希索引。但有时候这样还不够。还可以做些什么呢?

通常可以索引开始的部分字符,这样可以大大节约索引空间。从而提高索引效率。但也会降低索引的选择性。索引的选择性指不重复的索引值(也称为基数cardinality)和数据库表的记录总数(#T)的比值,范围从1/#T到1之间。索引的选择性越高则查询效率越快,因为选择性高德索引可以让MySQL在查找时过滤掉更多的行。唯一索引的选择性是1,这是最好的索引选择性,性能也是最好的。

一般情况下某个列的前缀的选择性也是足够高的,足以满足查询性能。对于blob、text、或者更长的varchar类型的列,必须使用前缀索引,因为MySQL不允许索引这些列的完整长度。

诀窍在于选择足够长的前缀以保证较高的选择性,同时又不能太长(以便节约空间)。前缀应该足够长,以使得前缀索引的选择性接近于索引整个列。换句话说,前缀的基数应该接近于完整列的基数。

为了决定前缀的合适长度,需要找到最常见的值的列表,然后和最常见的前缀列表进行比较。

首先找到最常见的城市列表:

select count(*) as cnt, city from city_demo group by city order by cnt desc limit 10;
cnt city
65 London
49 Hironshima
48 Pak Kret
48 Yaound
47 Tel Aviv-Jaffa
47 Shimogo
45 Cabuyao
45 Callao
45 Bislig

注意到,上面每个值都出现了45~65次,现在查找到最频繁出现的城市前缀,先从3个前缀字母开始:

select count(*) cnt, left(city, 3) from city_demo group by pref order by cnt desc limit 10;
cnt city
483 San
195 Cha
177 Tan
167 Sou
163 al-
163 Sal
146 Shi
136 Hal
130 Val
120 Bat

每个前缀都比原来的城市出现的次数更多,因此唯一前缀比唯一城市要少得多。然后增加前缀长度,知道这个前缀的选择性接近完整列的选择性。经过试验后发现前缀长度为7时比较合适:

select count(*) cnt, left(city, 7) from city_demo group by pref order by cnt desc limit 10;
cnt city
70 Santiag
68 San Fel
65 London
61 Valle d
49 Hironshi
48 Teboksa
48 Pak Kre
48 Yaound
47 Tel Avi
47 Shimoga

计算合适的前缀长度的另外一个办法就是计算完整列的选择性,并使前缀的选择性接近于完整列的选择性。下面是如何计算完整列的选择性:

select count(distinct city)/count(*) as rate from city_demo;
rate
0.0312

通常来说,这个例子如果前缀的选择性能够接近于0.031,基本上就可用了。可以在一个查询中针对不同前缀长度进行计算,这对于大表非常有用。下面给出了如何在同一个查询中计算不同前缀长度的选择性:

seelct count(distinct left(city,3))/count(*) as sel3,
       count(distinct left(city,4))/count(*) as sel4,
       count(distinct left(city,5))/count(*) as sel5,
       count(distinct left(city,6))/count(*) as sel6,
       count(distinct left(city,7))/count(*) as sel7 from city_demo;
sel3 sel4 sel5 sel6 sel7
0.0239 0.0293 0.0305 0.0309 0.0310

查询显示当前前缀长度达到7的时候,再增加前缀长度,选择性提升的幅度已经很小了。

只看平均选择性是不够的,也有例外情况,需要考虑最坏情况写的选择性。平均选择性会让你认为前缀长度为4或者5的索引已经足够了,但如果数据分布很不均匀,可能会有陷阱。如果观察前缀为4的最长出现城市的次数,可以看到明显不均匀:

select count(*) as cnt, left(city, 4) as pref from city_demo group by perf order by cnt limit 5;
cnt pref
205 San
200 Sant
135 Sout
104 Chan
91 Toul

如果前缀是4个字节,则最常出现的前缀的出现次数比最长出现的城市的出现次数要大得多。即这些值的选择性比平均选择性要低。

在上面的示例中,已经找到了合适的前缀长度,下面演示如何创建前缀索引:

alter table city_demo add key(city(7));

前缀索引是一种能使索引更小、更快的有效方法。但也有其缺点:MySQL无法使用前缀索引进行order by和group by,也无法使用前缀索引做覆盖扫描。

一个常见的场景是针对很长的16进制唯一ID使用前缀索引。

有时候后缀索引也有用途(例如,找到某个域名的所以电子邮件地址)。MySQL不支持反向索引。但是可以把字符串反转后存储。并基于此建立前缀索引。

3.多列索引

在多个列上建立独立的单列索引大部分情况下并不能提高MySQL的查询性能。MySQL在5.0和更高版本中引入了一种叫“索引合并”的策略,一定程度上可以使用表上的多个单列索引来定位指定的行。更早版本的MySQL只能使用其中某一个单列索引,然而这种情况下没有哪一个独立的单列索引是非常有效的。例如,表file_actor在字段film_id和actor_id上各有一个单列索引。但对于下面这个查询where条件,这两个单列索引都不是好的选择:

select film_id,actor_id from film_atcor where actor_id = 1 or film_id = 1;

在老的MySQL中,MySQL会使用全表扫描。除非改写成如下的两个查询union的方式:

select film_id, actor_id from film_actor where actor_id = 1
union all
select film_id, actor_id from film_actor where actor_id != 1 and film_id = 1;

但在MySQL5.0和更高版本中,查询能够同时使用这两个单列索引进行扫描,并将结果进行合并。这种算法有三种变种:1.OR条件的联合(union),2.AND条件的相交(intersection),3.组合前两种情况的联合及相交。下面的查询就是使用了两个索引扫描的联合,通过explain中的extra列可以看到这点:

explain select film_id,actor_id from film_atcor where actor_id = 1 or film_id = 1;

id:1
select_type:SIMPLE
type:index_merge
possible_keys:PRIMARY,idx_fk_film_id
key:PRIMARY,idx_fk_film_id
key_len:2,2
ref:NULL
rows:29
Extra:Using union(PRIMARY, idx_fk_film_id);Using where

MySQL会使用这类技术优化复杂查询,所以在某些语句的Extra列中还可以看到嵌套操作。

索引合并策略有时候是一种优化的结果,但实际上更多时候说明了表上的索引建的很糟糕:

  • 当出现服务器对多个索引做相交操作时(通常有多个AND条件),通常意味着需要一个包含所有相关列的多列索引,而不是多个独立的单列索引。
  • 当服务器需要对多个索引做联合操作时(通常有多个OR条件),通常需要耗费大量CPU或内存资源在算法的缓存、排序和合并操作上。特别是当其中有些索引的选择性能不高,需要合并扫描返回的大量数据的时候。
  • 更重要的是,优化器不会把这些计算到“查询成本”中,优化器只关心随机页面读取。这会使查询的成本被低估,导致该执行计划还不如直接走全表扫描。这样做不但会消耗更多的CPU和内存资源,还可能影响查询的并发性。但如果是单独运行这样的查询则往往会忽略对并发性的影响。通常来说,还不如像在MySQL4.1或者更早的一样,将查询改写成union的方式往往更好。

如果在explain中看到有索引合并,应该好好检查一下查询和表的结构,看是不是已经是最优的。也可以通过参数optimizer_switch来关闭索引合并功能,也可以使用ignore index提示让优化器忽略掉某些索引。

4.选择合适的索引列顺序

在一个多列B-Tree索引中,索引列的顺序意味着索引首先按照最左列进行排序,其次是第二列。所以索引可以按照升序或者降序进行扫描。以满足精确符合顺序的order by,group by和distinct等子句的需求。

对于如何选择索引的列顺序有一个经验法则:选择性最高的列放到索引最前列。这个建议在某些场景下是有帮助的,但通常不如避免随机IO和排序那么重要,考虑问题要全面。

当不需要考虑排序和分组时,将选择性最高的列放在前面通常是很好的。这时候索引的作用只是用于优化where条件的查找。在这种情况下,这样设计的索引确实能够最快的过滤出需要的行,对于where子句中只是使用了索引部分前缀列的查询来说选择性也更高。然而,性能不只是依赖于所有索引列的选择性(整体基数),也和查询条件的具体值有关,也就是和值的分布有关。这和前面介绍的选择前缀的长度需要考虑的地方一样。可能需要根据运行频率最高的查询来调整索引列的顺序,让这种情况下索引的选择性最高。

以下面得查询为例:

select * from payment where staff_id = 2 and customer_id = 584;

是应该建立一个(staff_id,customer_id)索引还是应该点到以下顺序?可以泡一下查询来确定在这个表中值的分布情况,并确定哪个列的选择性更高。先用下面的查询预测一下,看看各个where天骄的分支对应的数据基数有多大:

select sum(staff_id = 2),sum(customer_id = 584) from payment\G

sum(staff_id = 2):7992

sum(customer_id = 584):30

根据前面的经验法则,应该将索引列customer_id放到前面,因为对应条件值customer_id数量更小。再来看看customer_id的条件值,对应的staff_id列的选择性如何:

select sum(staff_id = 2) from payment where customer_id = 584\G

sum(staff_id = 2):17

这样做有一个地方需要注意,查询的结构非常依赖于选定的具体值。如果按上述办法优化,可能对其他一些条件值的查询不公平,服务器的整体性能可能变得更糟,或者其他的查询的运行变得不如预期。

如果是从诸如pt-query-digest这样的工具的报告中提取‘最差’查询,那么按照上述犯法选定的索引顺序往往是非常高效的。如果没有类似的具体查询来运行,那么最好还是按照经验法则来做,因为经验法则考虑的是全局基数和选择性,而不是某个具体查询:

select count(distince staff_id)/count(*) as staff_id_selectivity,
       count(distince customer_id)/count(*) as customer_id_selectivity,
       count(*)
from payment\G

staff_id_selectivity:0.0001
customer_id_selectivity:0.0373
count(*):16049

customer_id的选择性更高,所以将其作为索引列的第一列:

alter table payment add key(customer_id, staff_id);

5.聚簇索引

聚簇索引并不是一种单独的索引类型,而是一种数据存储方式。具体的细节依赖于其实现方式。但InnoDB的聚簇索引实际上在同一个结构中保存了B-Tree索引和数据行。

当表有聚簇索引时,它的数据行实际上存放在索引的叶子页中,数据‘聚簇’标识数据行和相邻的键值紧凑的存储在一起。因为无法同时把数据行存储在两个不同的地方,所以一个表只能有一个聚簇索引。