《数据库索引设计与优化》 -- 读书笔记

DB Index Design and Optimization -- Reading Notes

Posted by decaywood on 2017-04-12
- 错误校对
DECLARE CURSOR41 CURSOR FOR
SELECT    CNO, FNAME
FROM      CUST
WHERE     LNAME = :LNAME
          AND
          CITY  = :CITY
ORDER BY  FNAME

星级是如何给定的

如果与一个查询相关的索引行是相邻的,或者相距足够靠近的话,那这个索引就可以被标记上第一颗星。这最小化了必须扫描的索引片的宽度。

如果索引行的顺序与查询语句的需求一致,则索引可以被标记上第二颗星,这排除了排序操作。

如果索引行包含查询语句的所有列,那么索引就可以被标记上第三颗星。这避免了访问表的操作:仅访问索引就可以了。

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

宽索引:宽索引是指一个至少满足第三颗星的索引。该索引包含了 SELECT 语句所涉及的所有列,因此能够使得查询只需访问索引而无需访问表。

在类似 CURSOR41 这样的简单场景下,一个三星索引的构造是很简单的。

为了满足第一颗星

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

为了满足第二颗星

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

为了满足第三颗星

将查询语句中剩余的列加到索引中去,列在索引中添加的顺序对查询语句的性能没有影响,但是将易变的列放在最后能降低更新的成本。现在,索引已包含了满足无须回表的访问路径所需的所有列。

最终三星索引将会是:(LNAME, CITY, FNAME, CNO) 或 (CITY, LNAME, FNAME, CNO)

CURSOR41 在以下方面是最为挑剔的:

  • WHERE 条件不包含范围谓词(BETWEEN、>、>=等)
  • FROM 语句只涉及单表
  • 所有谓词对于优化器来说都足够简单
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 的值只有一个(=谓词),所以使用这个索引可以使结果集以 FNAME 的顺序排列,而不需要额外的排序。但是如果 ORDER BY 字段加在 BETWEEN 谓词列 LNAME 后面,如索引 (CITY, LNAME, FNAME),那么索引行不是按 FNAME 顺序排列的,因而就需要进行排序操作。因此,为了满足第二颗星,FNAME 必须在 BETWEEN 谓词列 LNAME 前面,如索引 (FNAME, …) 或索引 (CITY, FNAME, …)。

再考虑第一颗星,如果 CITY 是索引的第一个列,那我们将会有一个相对较窄的索引片需要扫描(MC=1),这取决于 CITY 的过滤因子。但是如果用索引 (CITY, LNAME, …) 的话,索引片会更窄,这样在有两个匹配列的情况下我们只需要访问真正需要的索引行。但是,为了做到这样,并从一个很窄的索引片中获益,其他列(如 FNAME)就不能放在这两列之间。

所以我们的理想索引会有几颗星呢?首先它一定能有第三颗星,但是,正如我们刚才所说,我们只能有第一颗星或者第二颗星,而不能同时拥有两者!换句话说,我们只能二选一:

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

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

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

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

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

候选 A

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

举例:CURSOR43

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

候选 B

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

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

举例:CURSOR43

候选 B 为 (CITY, FNAME, LNAME, CNO)。

现在我们有两个最佳索引的候选对象,一个有第一颗星,一个有第二颗星。为了判断哪一个是最佳索引,我们可以按照 QUBE(下文会提到)来估算哪个候选对象将会提供对于这个查询语句更快的访问路径。有一点需要注意的是,到目前为止,我们所做的只是设计理想索引或是最佳索引。但是这是否是实际可行的,我们在这个阶段还不好说。

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

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

近几年来,排序速度已经提升了很多。现在大多数的排序过程都在内存中进行,用当下最快的处理器每排序一行花费的 CPU 时间大约在10us左右。因此,排序50000行记录所耗费的时间只有0.5s,对于一次事务操作来说也许是可接受的,但这对于 CPU 时间来说已经是一个比较大的开销了。

由于现在的硬件条件下排序速度很快,所以如果一个程序取出结果集的所有行,那么候选 A 可能和候选 B 一样快,甚至比候选 B 更快,对于程序员来说,这是最方便的解决方案。许多环境都提供灵活的命令来浏览结果集。

然而,如果一个程序只需获取能够填充满一个屏幕的数据量,如 CURSOR44,那么候选 B 可能会比候选 A 快很多。如果访问路径没有排序的话,数据库管理系统只要一次次地读取数据行就能对结果集进行物化。这也是为什么有些时候避免排序非常重要(通过采取候选 B)。如果结果集很大的话,为了产生第一屏的数据,二星索引候选 A(需要进行排序)可能会花费非常长的时间。我们需要时刻记着,终端用户的一次错误输入可能会使得结果集变得非常大。

如果访问路径没有排序的话,使用 CURSOR44 的程序将会非常快(假设LNAME 和 CITY 两列是索引中的前两列 — 不管顺序如何),即使结果集包含数以百万级的数据行。每个事务永远都不会使数据库管理系统物化大于20行的数据。我们后面会讨论如何实现高效查找接下来的20行结果数据。

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

为每一个查询设计最佳索引过程是很简单的(除非已经存在相同的索引了)。这个设计过程,也就是上文所说的两种候选方案算法,是机械式的,只要给出下面这些内容就可以自动完成整个过程:

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

在这种最简单的过程中,当前存在的索引信息只是用来避免生成重复的索引。删除重复索引实际上是可以提升插入速度的,且删除后不会使得查询速度明显下降。在为查询语句设计了一个最佳索引后,去看一下已经存在的索引是很有必要的。有可能某一个已经存在的索引几乎和理想索引差不多好用,特别是打算在这个已有索引的最后添加一些列的情况下。当分析一个已存在的索引对一个新的查询语句有多大作用时,需要记住,多余的索引分为三种:完全多余的索引,近乎多余的索引,以及可能多余的索引。

完全多余的索引

许多年前,如果查询包含 WHERE A = :A AND B =:B 而另外一个查询包含 WHERE B =:B AND A = :A 的话,数据库管理系统就会创建两个索引:(A, B) 和 (B, A)。如果没有查询包含 A 列或者 B 列上的范围谓词的话,那么这两个索引中的一个就是完全多余的。

近乎多余的索引

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

假设索引行的大小从原先的50字节增长为200字节,那么扫描10000行索引片并从中取出1000个索引项会多花费多少时间?CPU 时间增长不多,但是 IO 时间是和需要访问的页数成比例的。

两种情况下都是1000次 FETCH 调用和10000个索引行
CPU 时间 = 1000 * 0.1 ms + 10000 * 0.005 ms = 150 ms
4KB 大小的叶子叶的数量(4列) 1.5 为空闲空间系数
1.5 * 10000 * 50 / 4000 ≈ 200 (顺序读时间 20 ms)
4KB 大小的叶子叶的数量(14列) 1.5 为空闲空间系数
1.5 * 10000 * 200 / 4000 ≈ 800 (顺序读时间 80 ms)

由于顺序读的处理过程使得响应时间还是受 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) 要好:

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

这两个优势都受需要在索引片上扫描的行数的影响。两个索引的差异可以简单地使用快速上限估算法(QUBE)进行估算。估算结果往往会显示,新的索引是不需要的,在现有索引后面加上新的列对于新的 SELECT 语句就已经足够了。

新增一个索引的代价

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

响应时间:

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

磁盘负载:

被修改过的叶子页是迟早会被写到磁盘上去的。由于数据库的写是异步的,所以这些写不会影响到事物的响应时间。但是,这些写会增加磁盘负载。如果一张表的插入频率较高的话,磁盘负载可能会变成主要的问题,限制了表上索引的数量。由于删除操作和插入操作所带来的磁盘负载是相同的,所以大量的删除任务是另外一个重要的考虑事项。更新操作只会影响到列值被修改了的索引。

磁盘空间:

随着索引的变大,磁盘空间、缓冲池或者磁盘缓存也随之增大,否则非叶子页的IO量会增加。

一些建议

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

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

前瞻性的索引设计

发现不合适的索引

一旦一个应用的明细方案确定下来,我们就应当确认当前的索引对新的应用来说是否合适。为了完成这个工作,我们将考虑两种简单、快速并且可行的方法:

  • 基本问题法(Basic Question,BQ)
  • 快速上限估算法(Quick Upper-Bound Estimate,QUBE)

基本问题法(BQ)

对于每个 SELECT 语句,以下问题的答案都必须按照下述步骤来考虑。

是否有一个已经存在的或者计划中的索引包含了 WHERE 子句所引用的所有列(一个半宽索引)?

  • 如果不是,那么我们应当首先考虑将缺少的谓词列加到一个现有的索引上去。这将产生一个半宽索引,尽管索引的等值匹配过程并不令人满意(一星),但是索引过滤可以确保回表访问发生在所有查询条件都满足的时候。
  • 如果这还没有达到足够的性能,那么下一个选择就是将所有涉及的列加到索引上,以使访问路径只需要访问索引。这将产生一个避免所有表访问的宽索引。
  • 如果 SELECT 仍然很慢,就应当使用前面介绍的两个候选索引算法来设计新的索引。根据定义,这将是所能实现的最佳索引。

如何确定第一个方案(半宽索引)或第二个(宽索引)方案能否让 SELECT 在最差输入的情况下仍然运行得足够快?如果可以访问生产库或类似的测试库,我们可以每次创建一个索引,用最差输入来测试响应时间。为了确保测得的响应时间接近于在正常生产库上运行的性能表现,我们必须把缓冲池考虑进来,并观察每个事务的缓冲池命中率。测试的第一个事务很可能在缓冲池中没有发现相应的缓存页,所以最差输入下的磁盘读的指标会比正常环境要高。此外,第一个访问索引的事务必须要等待文件被打开。而另一方面,如果变量输入值保持不变,那么第二个访问该索引的事务将很可能会获得100%的缓冲池命中率(没有磁盘读)。为了获得具有代表性的响应时间,每个索引方案都应在进行过预热事物之后再开始测试,可以通过传入一些典型的输入值(但不是最差情况的值)来打开文件,并将大部分非叶子索引页加载到数据库缓冲池中。这样,使用最差输入值的事务就会有一个比较有代表性的响应时间了,至少我们已经把 CPU 和磁盘读的服务时间考虑进来了。

如果模拟测试和 QUBE 方法都没有实施,那么我们就应当选择使用宽索引方案,并在应用切换到生产环境后立即启用异常报告来发现那些连宽索引都无法满足性能要求的场景。如果必要的话,我们需要为那些运行缓慢的查询设计我们所能达到的最佳(新的)索引。

注意

对于 BQ 的一个肯定的回答并不能保证足够的性能。记住,BQ 的目的只是确保我们至少可以通过索引过滤来最小化对表的访问 — 除此之外没有其他作用。举个例子,假设有一个 SELECT,谓词是 WHERE B = :B AND C = :C,唯一有用的索引是 (A, B, C)。这个索引的确包含了该 SELECT 的所有的谓词列,因此用 BQ 方法检查这个 SELECT 并不会产生告警。然而,这个查询的访问路径将会是全索引扫描 — 如果该表有超过100000条记录,那么查询将运行得非常慢。索引过滤本身并不意味着这个索引有三颗星中的任何一颗星。

然而,根据我们的经验,许多发布后才发现的索引问题都是可以通过 BQ 方法来提早发现的。将 BQ 方法应用到单表查询上是很容易的。但对于连接查询,我们就必须现在脑海中将其拆分成多个单表游标,然后再应用 BQ 方法。这是一个相当复杂的过程。

快速上限估算法(QUBE)

在最初的评估阶段(当前索引是否让 SELECT 足够快?),QUBE比 BQ更耗时,但它能揭示所有与索引或者表设计相关的性能问题 — 假设对每个谓词所用的最差过滤因子都非常接近于实际的最差情况过滤因子值。根据定义,QUBE方法是悲观的(上限),它有时会有告警误报,但它不会像 BQ 那祥漏掉发现某些问题。QUBE 的目的是在一个非常早的阶段(程序在设计、编写或者完成的时候)将潜在的慢访问路径问题暴露出来。为了能在实际项目中使用.任何语句级别的预测公式都必须足够简单,这样才能将评估过程的额外开销保持在一个可以接受的程度。(待续…)