2018年12月

数据库索引设计与优化-01

磁盘与CPU时间的基础假设

I/O时间
随机读 10ms (4KB或8KB的页)
顺序读 40MB/s

顺序扫描的CPU时间
检查一行记录 5µs
FETCH 100µs

不合适的索引

对于下面这个简单的SQL,仅有两个合理的访问路径

  1. 索引扫描(LNAME, FNAME)
  2. 全表扫描
select cno,fname from cust where lname = :lname and city = :city order by fname

假设表中总共有 1000000 条数据

对于第一种选择来说,数据库会根据谓词条件lname = :lname扫描索引片。对于索引片中的每一个索引行,数据库系统都必须回到表中校验city字段的值。由于表中的行是根据cno字段而不是lname字段来聚簇的,所以校验操作需要做一次磁盘的随机读。对于最普遍的姓氏来说,在不考虑city字段的过滤因子的情况下,获取完整的结果意味着,需比对10000个索引行和10000个表行。那么,这个过程会持续多久?

假设索引(lname,fname)的大小是1000000 100 byte ≈ 100MB,包括数据及分散的空闲空间。另外,再假设顺序读的速度是40MB/s。读取一个宽度为1%的索引片的,即1MB,需花费10ms + 1MB / 40MB/s,这显然是没有问题的,但是10000次随机读将花费10000 10ms,这使得这种方式太慢了。

对于第二种选择来说,只有第一个页需要随机读。如果表的大小为1000000 * 600 byte ≈ 600MB,包括分散的空闲空间,那么花费的I/O时间将会是10ms + 600MB / 40M/s ≈ 15s,仍旧很慢

第二种方案的CPU时间将会比第一种方案的CPU时间长的多,因为数据库管理系统必须对比1000000行而不是20000行,并且还需要对这些行进行排序。从另一个方面来说,由于是顺序读,CPU的时间可以与I/O时间交叠。在这个场景下,全表扫描比在不合适的索引上扫描要快,但是这还不够,需要一个更好的索引。

三星索引

前面讨论了一个非常不合适的索引,这里来讨论另一个极端,三星索引,即对于一个查询语句可能是最好的索引。如果使用了三星索引,一次查询通常只需要进行磁盘随机读及一次窄索引片的扫描。因此,其响应时间通常会比使用一个普通索引的响应时间少几个数量级。

  • 如果与一个查询相关的的索引行是相邻的,或者至少相距足够靠近的话,那么这个索引就可以被标记上第一颗星。这最小化了必须扫描的索引片的宽度
  • 如果索引行的顺序与查询语句的需求一致,则索引可以被标记上第二颗星。这排除了排序操作
  • 如果索引行包含查询语句的所有列,那么索引就可以被标记上第三颗星。这避免了访问表的操作:仅访问索引就可以了。

对于这三颗星,第三颗通常是最重要的。将一个列排除在索引之外可能会导致许多速度较慢的随机读。我们把包含第三颗星的索引名为对应查询语句的宽索引。

示例

DECLARE CURSOR41 CURSOR FOR
SELECT CNO,FNAME
FROM CUST
WHERE LNAME = :LNAME AND CITY = :CITY
ORDER BY FNAME

为了满足第一颗星(减少索引片的大小以减少需要扫描的数据行)

取出所有等值为此的列(WHERE COL = ...)。把这些列作为索引最开头的列,以任意顺序都可以。对于CURSOR41来说,三星索引可以以LNAME,CITY或者以CITY,LNAME开头。在这两种情况下,必须扫描的索引片宽度将被缩减至最窄。

为了满足第二颗星(避免排序,较少磁盘IO和内存使用)

将ORDER BY列加入到索引中。不要改变这些列的顺序,但是忽略那些在第一步中已经加入索引的列。例如如果CURSOR41在ORDER BY中有重复的列,如ORDER BY LNAME, FNAME或者是ORDER BY FNAME, CITY,只有FNAME需要在这步中被加入到索引中去。当FNAME时索引的第三列时,结果集中的记录无需排序就已经是以正确的顺序排列了。第一次读取操作将返回FNAME值最小的那一行。

为了满足第三颗星(避免没个索引对于的数据行都需要进行一次随机IO从聚集索引中读取剩余数据)

将查询语句中剩余的列加到索引中去,列在索引中添加的顺序对查询语句的性能没有影响,但是将易变的列放在最后能够降低更新的成本。现在索引中已包含了满足无需回表的访问路径所需的所有列。
最终三星索引将会是:
(LNAME,CITY,FNAME,CNO)或(CITY,LNAME,FNAME,CNO)
CURSOR41在以下三个方面是较为挑剔的:

  • WHERE条件不包含范围谓词(BETWEEN,>,>=等)
  • FROM语句只涉及单表
  • 所有谓词对于优化器来说都足够简单

范围谓词和三星索引

下面的SQL与之前的相同,只是显现顾客是在一个范围内

DECLARE CURSOR43 CURSOR FOR
SELECT CNO,FNAME
FROM CUST
WHERE LNAME BETWEEN :LNAME1 AND :LNAME2
AND
CITY = :CITY
ORDER BY FNAME

尝试为这个CURSOR设计一个三星索引。大部分的推论与CURSOR41相同,但是BETWEEN谓词=谓词替代后将会有很大的影响。我们将会以相反的顺序依次考虑三颗星。
首先最简单的行(虽然非常中烟),第三颗星。按照之前的描述,确保查询的所有列都在索引中就能满足第三颗星。这样就不需要访问表,那么同步读就不会造成问题。
添加ORDER BY列能使索引满足第二颗星,但是这个仅在将其放在BETWEEN谓词列LNAME之前才成立,如索引(CITY,FNAME,LNAME)。由于CITY的值只有1个(=谓词),所以使用这个索引可以使结果集以FNAME的顺序排序,而不需要额外的排序。但是如果ORDER BY字段加在BETWEEN谓词列LNAME后,如索引(CITY,LNAME,FNAME),那么索引行不是按FNAME顺序排列的,因而就需要进行排序操作。因此为了满足第二颗星,FNAME必须在BETWEEN谓词列LNAME的前面,若索引(FNAME)或索引(CITY,FNAME,...)。
再考虑第一颗星,如果CITY是索引的第一列,那么我们将会有一个相对窄的索引片需要扫描(MC=1),这取决于CITY的过滤因子。但是如果用索引(CITY,LNAME,...)的话,索引片会更窄,这样在有两个匹配列的情况下我们只需要访问真正需要的索引行。但是,为了做到这样,并从一个很窄的索引片中获益,其他列(如LNAME)就不能放在这两列之间。
所以我们的理想索引会有几颗星呢?首先他一定能有第三颗星,但是,正如我们刚才所说,我们只能有第一颗星或者第二颗星,而不能同时拥有两颗星。换句话说,我们只能二选一

  • 避免排序--拥有第二颗星
  • 拥有可能的最窄索引片,不仅将需要处理的索引行数降至最低,而且将后续处理量,特别是表中数据行的同步读较小到最少--拥有第一颗星

在这个例子中,BETWEEN谓词或者任何其他范围谓词的出现,意味着我们不能同时拥有第一颗星和第二颗星。也就是说我们不能拥有一个三星索引。
这就意味着需要在第一颗星和第二颗星中作出选择。通常这不是一个困难的选择,第一颗星一版比第二颗星重要,虽然并不总是这样。

让我们考虑一下索引(LNAME,CITY,...),LNAME是范围谓词,如前面看到的,这意味着LNAME是参与索引匹配过程的最后一个列。等值谓词CITY不会在匹配过程中被使用。这样做将会导致只有一个匹配列---索引片将会比使用索引(CITY,LNAME,...)更宽。

为查询语句设计最佳索引的算法

根据以上的讨论,理想的索引是一个三星索引。正如我们看到的,当存在范围谓词时,这是不可能实现的。我们不得不牺牲第二颗星来满足一个更窄的索引片(第一颗星),这样,最佳索引就只拥有两颗星。在这个例子中理想索引是不可实现的。将这层因素考虑在内,我们可以对所有情况创建最佳索引(也许不是理想索引)的过程公式化。创建出的索引将拥有三颗星或者两颗星。

首先设计一个索引片尽可能窄(第一颗星)的宽索引(第三颗星)。如果查询使用这个索引时不需要排序(第二颗星),那么这个索引就是三星索引。否则这个索引只能是二星索引,牺牲第二颗星。或者采用另一种选择,避免排序,牺牲第一颗星保留第二颗星。这两种二星索引中的一个将会是相应查询语句的最佳索引。

下面的内容阐述了为查询语句创建最佳索引的算法

候选A

  1. 取出对于优化器来说不过分复杂的等值谓词列。将这些列作为索引的前导列--以任意顺序指定皆可。
  2. 将选择性最好的范围谓词作为索引的下一个列,如果存在的话。最好的选择性是指对于最差的输入值有最低的过滤因子。只考虑对于优化器来说不过分复杂的范围谓词即可
  3. 以正确的顺序添加ORDER BY列(如果ORDER BY列有DESC的话,加上DESC)。忽略在第一步或第二步中已经添加的列。
  4. 以任意顺序将SELECT语句中其余的列添加至索引中(但是需要以不易变的列开始)

举例 : CURSOR43
候选A为(CITY,LNAME,FNAME,CNO)
由于FNAME在范围谓词列的后面,候选A引起了CURSOR43的一次排序操作。

候选B

如果候选A引起了所给查询语句的一次排序操作,那么还可以设计候选B。根据定义,对于候选B来说第二颗星比第一颗星更重要。

  1. 取出对于优化器来说不过分复杂的等值谓词列。将这些列作为索引的前导列--以任意顺序指定皆可。
  2. 以正确的顺序添加ORDER BY列(如果ORDER BY列有DESC的话,加上DESC)。忽略在第一步或第二步中已经添加的列。
  3. 以任意顺序将SELECT语句中其余的列添加至索引中(但是需要以不易变的列开始)

举例 : CURSOR43
候选B为(CITY,FNAME,LNAME,CNO)
现在我们有两个最佳索引的候选对象,一个有第一颗星,一个有第二颗星。为了判断哪一个是最佳索引

需要注意,到目前为止,我们所做的只是设计理想索引或是最佳索引。但是这是否是实际可行的,我们在这个阶段还不好说

SQL 4.4

DECLARE CURSOR44 CURSOR FOR
SELECT CNO,FNAME
FROM CUST
WHERE LNAME = :LNAME AND CITY = :CITY
ORDER BY FNAME
WE WANT 20 ROWS PLEASE

OPEN CURSOR CURSOR4
FETCH CURSOR CURSOR4 --- 最多20次
CLOSE CURSOR CURSOR4

现今排序速度很快--我们为什么还需要候选B

近几年来,排序速度已经提升了很多。现在大多数的排序过程都在内存中进行,用当前最快的处理器每排序50000行记录所耗费的时间只有0.5s,这对于一次事务操作来说也许是可接受的,但这对于CPU时间来说已经是一个比较大的开销了。
由于现在硬件条件下排序速度很快,所以如果一个程序取出结果集的所有行,那么候选A可能和候选B一样快,甚至比候选B更快。
然而,如果一个程序只需获取能够填满一个屏幕的数据量,如CURSOR44,那么候选B可能会比候选A快很多。正如第三章中讨论的,如果访问路径中没有排序,数据库管理系统只要一次一次地读取数据行就能对结果集进行物化。这也是为什么有些时候避免排序非常重要(通过采用候选B)。如果结果集很大,为了产生第一屏数据,二星索引候选A(需要进行排序)可能会话费非常长的时间。我们需要时刻记着,终端用户的一次错误输入可能会使结果集变得非常大。
如果访问路径中没有排序,使用CURSOR44的程序将会非常快(假设LNAME和CITY两列是索引中的前两列---不管顺序如何),即使结果集包含数以百万级的数据行。每个事务永远都不会使数据库管理系统物化大于20行的数据。

需要为所有查询语句都设计理想索引吗?

为每一个查询设计最佳索引的过程是简单的。这个设计过程就是上文所说的两种候选方案算法,是机械式的,只要给出下面这些内容就可以自动完成整个过程

  1. 查询语句
  2. 数据库统计信息(行数,页数,列值分布等)
  3. 对于一个简单谓词或组合谓词最差情况下的过滤因子
  4. 已经存在的索引

在这种简单的过程中,当前存在的索引信息只是用来避免生成重复的索引。有时一个表的索引可以删除掉一些多余的索引以提高插入速度,前提是删除后不会使查询速度明显下降。

在为一个查询语句设计了一个最佳索引后,去看一下已存在的索引是很有必要的。有可能某一个已经存在的索引几乎和理想索引差不多好用,特别是打算在这个已有索引的最后添加一些列的情况下。

当分析一个已经存在的索引对一个新查询语句由多大用处时,需要记住,多余的索引分为三种:完全多余索引,近乎多余索引,以及可能多余的索引。

完全多余索引

如果一个查询包含WHERE A= :A AND B= :B而另一个查询包含WHERE B = :B AND A = :A,数据库管理系统就会创建两个索引:(A,B)和(B,A)。如果没有查询包含A列或者B列上的范围谓词的话,那么这两个索引中的一个就是完全多余的。我们不需要两本电话簿,一个根据LNAME,FNAME排序而另一本根据FNAME,LNAME排序(如果姓氏和名字都已知)。这个时候需要规范SQL语句。

近乎多余的索引

假设索引(LNAME,CITY,FNAME,CNO)已经存在。为一个新的查询语句设计的理想索引包含了以这个索引的4列开头的14个列。那么,在创建了新的索引之后,原来的索引是不是应该删除呢?一些DBA可能会犹豫要不要这样做,因为这个已经存在的索引是唯一索引。但是,这个索引并不是主键索引也不是候选索引,只是恰好这个索引包含了主键列CNO。把其他列加到这个索引上不会有完整性问题。如果数据库管理系统支持非键值索引列,或者有约束来保证唯一性,数据列甚至可以加到主键索引或者任何键值必须唯一的索引上。这样一来,问题就成了一个纯粹的性能问题:一个原本使用4列索引的查询现在使用新的14列索引,速度是否会明显变慢?

假设索引行的大小从原先的50字节增长为200字节,那么扫描10000行索引片并从中取出1000个索引项会花费多少时间?CPU时间增长不多,但是I/O时间是和需要访问的页数成比例的。
CPU时间 = 1000 0.1ms + 10000 0.005ms = 150ms (两种情况下都是1000次FETCH调用和10000个索引行)
4KB大小的叶子页的数量(4列) 1.5 10000 50 / 4000 约等于 200
4KB大小的叶子页的数量(14列) 1.5 10000 200 / 4000 约等于 800
1.5位空闲空间系数

顺序读时间(4列) = 200 * 0.1ms = 20ms
顺序读时间(14列) = 800 * 0.1ms = 80ms

由于顺序读的处理过程是的响应时间还是受CPU时间的限制,所以查询语句使用这两个索引的响应时间没有明显不同。在新的14列索引创建之后,现存的4列索引就变成多余的了

可能多余的索引

一个普遍的常客是这样的 : 一个新的查询语句的理想索引是(A,B,C,D,E,F),而表上已经存在的索引是(A,B,F,C)。那么如果把已经存在的索引替换成(A,B,F,C,D,E),新的索引是不是就多余了?换句话说如果把D和E两列加到现有的索引上是的访问路径仅限于索引,这样对于新的查询语句是否就已经足够了?
理想索引可能在两方面比索引(A,B,F,C,D,E)要好

  1. 可能使得查询有更多的匹配列
  2. 可能可以避免排序

这两个优势都受需要在索引片上扫描的行数的影响。两个索引的差异可以入本章所述转换成毫秒值进行比较,或者更简单一些,通过后面讨论的快速上线估算法(QUBE)进行估算。估算结果往往会显示,新的索引是不需要的,在现有的索引后面加上新的列对于新的SELECT语句就已经足够了

新增一个索引的代价

如果表上有100个不同的查询,且为每一个查询语句都设计了最佳索引的话,那么即使没有重复的索引,该表上最终也可能有非常多的索引,这样一来表的插入,更新和删除操作就会变得很慢。

响应时间

当数据库管理系统向表中添加一行时,他必须在每一个索引上都添加响应的行。在当前的硬件条件下,在一个索引上添加一行,插入操作所花费的时间就增加10ms,因为必须从磁盘上读取一个叶子页。当一个事务向一张有10个索引的表里插入1行数据时,索引的维护就会使响应时间增加10*10ms = 100ms,这可能是可以接受的。然而,如果一个事务向一张有10个索引的表里插入20行数据的话,索引的维护就会需要181次随机读,即耗费1.8s。这个估算基于的前提假设是,新的索引行会把表上其中一个索引(一直增大的键值上的索引)添加到同一个叶子页上,而会把其余9个索引添加到20个不同的叶子页上。从响应时间的角度来看,在一个有10个索引的大表上进行大的事务操作(每个事务中有许多插入或删除操作)可能是无法忍受的。另外,从磁盘负载的角度来看,要在一个大表上进行每秒多余于10行的插入操作可能不容许表上有10个索引。

磁盘负载

被修改过的叶子页是迟早会被写到磁盘上去的。由于数据库的写是异步的,所以这些写不会影响到事务的响应时间。但是,这些会在增加磁盘负载。RAID 5会放大这种影响,因为每一次页的随机更新都会引来两个磁盘的访问。每一次访问都会耗费12ms,因为整个Raid条带都需要被读取和写回:一次寻道(4ms)和两次旋转(24ms)。因此,向磁盘写一个被修改的也带来的整体磁盘繁忙度的增加为24ms。RAID 10(条带化和镜像)相应的增量为26ms = 12ms。

如果一张表的插入频率较高的话,磁盘负载可能会变成主要的问题,限制了表上索引的数量。由于删除操作和插入操作锁带来的磁盘负载是相同的,所以大量的删除任务是另外一个重要的考虑事项。更新操作只会影响到列值被修改了的索引。

假设一个RAID 5磁盘服务器有128块盘,16块空闲盘。数据库(表和索引或者他们的分区)被条带化到这些活动盘上。读缓存为64GB,写缓存为2GB。

在TRANS表中,新插入的行保存在表及其聚簇索引的末尾。在页被写到磁盘之前,许多行会被写到这个页上,所以这些操作不会造成大量的磁盘读和写。会带来问题的是4个索引上的随机插入操作,每一个新的索引行可能都会导致一次磁盘读和磁盘写,每秒插入20行,即每秒一共80次随机写(4*20)。

先忽略读缓存和写缓存。在最差的情况下,4个索引造成的磁盘繁忙度为80*(6ms + 24ms)=2400ms,相应的次磁盘负载为2400ms/s=2.4=240%,如果这4个索引是在112块磁盘上做条带,他们对于平均磁盘负载的贡献是240%/120≈2%。根据平均排队时间将会是3ms。由此,增加2%的磁盘复杂度是可以忍受且不明显的。

使用读缓存和写缓存能多大程度上减轻磁盘负载?
64GB的读缓存和4个索引的大小(1.2GB)相比较似乎很大,但是如果访问模式是完全随机的,当插入频率是20行每秒时,对于每一个索引上75000个叶子页中的任何一个叶子页,对同一个叶子页的相邻两次访问的时间间隔是基本平均的,间隔时间为75000*50ms=3750s≈1h,如果读缓存的的平均时间是30分钟,那么就不会有很多的读命中缓存。如果写缓存的保留时间比读缓存的保留时间短,比如10分钟,那读缓存的作用会更小:只有当一个叶子页在10分钟内被更新1次以上,才能通过写缓存节省一次磁盘写。因此这个4个索引导致的平均磁盘繁忙度几乎依然是2%。如果访问模式不是随机的,缓存将会节省更多磁盘负载上的开销。每小时更新次数多余10次的叶子页能在读缓存和写缓存中长时间保留。

RAID 10,镜像并条带但是没有校验位,能将每个被修改也锁带来的次破案繁忙度从24ms降至12ms,但是这样需要增加磁盘数量。有256块盘的RAID 5基本上也能带来相同的效果。

从这个例子中可以引申出一个经验法则,其中指示符L表示一个表上的索引对RAID 5下磁盘平均负载平均负载的贡献 : L = N * I / D
其中 N = 随机插入设计的索引数量
I = 插入频率(表每秒插入的行数)
D = 磁盘数量(空闲盘除外)

如果L < 1,那么磁盘负载的增加不构成问题;负载增量很可能低于2%
如果L再1和10之间,那么负载的增加可能会比较明显
如果L>10,那么磁盘负载很可能会构成问题,除非缓存命中率很高。

在上面例子中, L = 4 * 20 / 112 = 0.7

如果磁盘负载是一个问题,较明显的解决办法是尝试合并索引。一个有10个列的索引比两个各有6个列的索引锁引起的磁盘负载要小。

磁盘空间

如果表中有一千万行以上的数据,索引磁盘空间成本可能会成为一个问题。外购硬件的价格主要取决于两个因素 : 花费的CPU时间和分配的磁盘空间。

举个例子,有人建议表上创建一个每行包含400字节用户数据的索引,我们是否需要考虑磁盘空间?
这个索引(去除RAID带来的额外开销)需要1.5 10000000 400byte ≈ 6GB 左右的磁盘空间。不过如果将这些列添加到现有索引上并不能提供可接受的响应时间,磁盘空间可能不是问题的关键。

随着索引变大,缓冲池或磁盘缓存也应该随之增大,否则非子叶的I/O量会增加,这一点也会增加开销。

一些建议

即使在目前磁盘空间成本较低的情况下,机械式的为每一个查询设计最佳索引也是不明智的,因为索引的维护可能会使得一些程序太慢或者使磁盘负载超负荷(这会影响所有程序)。最佳索引(根据两个候选索引的方法设计或者使用索引工具设计)是一个好的开端,但是,在决定为一个新的查询创建理想索引前需要先考虑下三种多余索引。

即使可能为每一个查询设计最佳索引,但在实际中更常见的情况是,只对那些由于不合适的索引而导致速度太慢(通过估算或通过测量)的查询语句进行索引设计。

练习

为4.5中的查询语句设计候选索引A和候选索引B。

SELECT A,B,D,E
FROM ORDERITEM
WHERE B BETWEEN :B1 AND :B2 (FF = 1...10%)
AND
C = 1 (FF = 2%)
AND
E > 0 (FF = 50%)
AND 
F = :F (FF = 0.1...1%)
ORDER BY A,B,C,F
WE WANT 20 ROWS PLEASE

候选索引A

对每一个候选索引,计算在最差情况下一个事务必须访问的索引行数。ORDERITEM表有100000000行。
候选索引A

  1. 提取出简单谓词(C, F)
  2. 从范围谓词中提取出过滤因子最低的(C, F, B)
  3. 把select中的字段放到索引中(C, F, B, A, D, E)
    扫描的索引行 100000000 (2% 1% * 10) = 2000

候选索引B
没有想到...