0%

数据库索引设计与优化 笔记

本文整理自:《数据库索引设计与优化》 作者:Tapio Lahdenmaki,Michael Leach

出版时间:2015-06-01

概述

索引误区

误区1:索引层级不要超过5层

由于非叶子页通常都会留在内存或者读缓存中,所以通常索引任意一个叶子页的时间为10ms~20ms,这是固定的。所以,对索引层数的限制是没有什么意义的。

误区2:单表的索引数不要超过6个

我建议不要给表的索引数目设置上限。

保证所有的SQL语句都能够流畅运行是设计的底线。我们总能找到一种方法来达到这一点。如果为了达到这一点需要在表上创建10个索引,那么你就应该在表上建立10个索引。

误区3:不应该索引不稳定的列

索引行是按索引键的顺序存储的,所以当索引键中存一列被更新时,DBMS可能不得不把相应的行从旧的索引位置移到新的位置来保持这一顺序。这个新的位迓可能与旧的位置位于相同的叶子页上,在这种情况下,只有一个页会受到影响。然而,如果被修改的键是第一列或唯一的列,那么新的索引行可能必须被迁移到一个不同的叶子页上,即DBMS必须更新两个叶子页。三十年前,如果这个索引为一个4层索引,这也许需要6次磁盘随机读取:3次常规读取,即2次非叶子页读取和1次叶子页读取,加上新的位置所涉及的3次随机读取。当一次随机读取耗时30ms 时,迁移一个索引行可能会给该更新操作额外增加6 x 30ms =180ms 的响应时间。因此,不稳定的列很少被索引就不足为奇了。

现在,当四层索引中三个层级的非叶子页保留在内存中时,一次磁盘随机读取需要 l0 ms ,响应的时间变成了 2 x 10ms = 20ms 。此外,许多索引为多列索引,也称作复合或组合索引,它通常包含多列,以使得索引键值唯一。当不稳定的列为复合索引的尾列更新这个不稳定的列绝不会导致其迁移到新的叶子页。因此,在当前的磁盘条件下,更新一个不稳定的列只会对该更新操作增加10ms的响应时间。

在当前磁盘条件下,只有在更新频率多于10次/秒的情况下,不稳定列才可能成为问题。

创建索引的目的应该是在硬件容量限制的前提下保证所有的数据库调用运行的足够快。

系统化的索引设计

  • 找到由于索引不合适而导致运行太慢的查询语句
    最差输入:导致执行时间最长的变量值
  • 设计索引,使所有查询语句都运行的足够快
    表的维护(插入、更新、删除)也必须足够快

表和索引结构

DBMS 会意识到多个索引或表页需要被顺序地读取,且能识別出那些不在缓冲池中的页。随后,它将发出多页I/O请求,每次请求的页的数量由DBMS决定。只有那些不在缓冲池中的页会被从磁盘服务器上读取,因为那些已经在缓冲池中的页中可能包含了尚未被写人磁盘的更新数据。

SQL处理过程

谓词

WHERE子句由一个或者多个谓词(搜索参数)组成。

1
2
3
4
5
6
# SQL 3.1
WHERE SEX = 'M'
AND
(WEIGHT > 90
OR
HEIGHT > 190)

SQL 3.1中有三个简单谓词,它们是:

  • SEX = ‘M’
  • WEIGHT > 90
  • HEIGHT > 190

同样,它们也可以被认为是两个组合谓词:

  • WEIGHT > 90 OR HEIGHT > 190
  • SEX = ‘M’ AND ( WEIGHT > 90 OR HEIGHT > 190 )

谓词表达式是索引设计的主要入手点。如果一个索引能够满足SELECT查询语句的所有谓词表达式,那么优化器就很有可能建立起一个高效的访问路径。

核实确认访问路径(执行计划)

为SELETE语句创建理想的索引【重点】

很多调优人员(尽管没经验)认为,如果一个SQL语句使用了索引,那这个 SQL就是被很好地优化过的,我对此感到很惊讶。你应该总是问自己,”这是不是可用的最好的索引?” 或 “再添加另外一个索引能否提升响应性能?”,又或者 “全表扫描会不会更快地返回结果?”

三星索引

三星索引:查询语句的理想索引。

1
2
3
4
5
6
7
DECLARE CURSOR41 CURSOR FOR
SELECT CNO, FNAME
FROM CUST
WHERE LNAME = :LNAME
AND
CITY = :CITY
ORDER BY FNAME

星级是如何给定的

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

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

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

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

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

为了满足第一颗星
首先取出所有等值谓词的列(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 语句只涉及单表
  • 所有谓词对于优化器来说都足够简单

范围谓词与三星索引

1
2
3
4
5
6
7
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)就不能放在这两列之间。

MC:match column(匹配列)

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

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

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

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

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

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

为查询语句创建最佳索引的算法

候选 A

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

举例:CURSOR43

候选 A 为 (CITY, LNAME, FNAME, NCNO)。

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

候选 B

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

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

举例:CURSOR43

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

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

前瞻性的索引设计

基本概念

访问

根据定义,DBMS读取一个索引行或一个表行的成本称为一次访问 : 索引访问或表访问。如果DBMS扫描索引或表的一个片段(被读取的行在物理上是彼此相邻的),那么第一行的读取即为一次随机访问。对于后续行的读取,每行都是一次顺序访问。在当前的硬件条件下,顺序访问的成本比随机访问的成本低得多。一次索引访问的成本与一次表访问的成本基本上是相同的。

读取一组连续的索引行

物理上彼此相邻是什么意思?

索引上的所有行都通过指针链接在一起,链接的先后顺序由索引的键值严格定义。当几个索引行的键值相同时,就根据索引行存储的指针值进行链接。在传统的索引设计(从某个角度看,是理想化的)中,链表从LP1(叶子页1)开始,随后链接LP2,以此类推。这样(假设每个磁道可以放12个叶子页,当前的硬件通常可以容纳更多),叶子页就组成了一个连续的文件,LP1至LP12存储在磁盘柱面的第一个磁道,LP13至LP24存储在下一个磁道,如此继续,当第一个柱面存满后,下一组LP就会被存储在下一个柱面的首个磁道上。换句话说,就是叶子页之间没有其他页。

现在,读取一个连续的索引行(即一个索引片,或者包含了单个键值或者一个范围的键值所对应的索引行)就非常快了。一次磁盘旋转会将多个叶子页读取进内存中,而且只有在磁盘指针移到下一个柱面时才需要进行一次短暂的寻址、

不过,这个完美的顺序还是会被打破的,至少有以下三个影响因素 :

  1. 如果一个叶子页没有足够的空间存储新插入的索引行,那么叶子页就必须被分裂。之后链表仍会按照正确的顺序链接索引行,但是这与底层的物理存储顺序就不再一致了,一些按道理应该是顺序的访问就变成随机访问了。不过索引的充足可以再次恢复最理想的顺序。
  2. 意向不到的数据增长可能会填满原本连续的空间(区或类似的概念)。操作系统于是就会寻找另外有一个连续的空间,并将它连接到原来空间的后面。这时候从第一个区跨到第二个区访问就会产生一次随机访问,不过这种情况影响不大。
    3.RAID 5条带会将前几个叶子页存储在一个驱动器上,将后面的叶子页存放在另外的驱动器上。这就会产生额外的随机读,但实际上条带的积极作用要大过随机读带来的性能恶化,一个智能的磁盘服务器可以将后续的叶子页并行的从多个驱动器上读取至磁盘缓存中,从而大大降低了单个叶子页的I/O时间。此外,在RAID 5条带策略下,一个被频繁访问的索引的不太可能导致某一个磁盘负载过高,因为I/O请求会被均匀低分布到RAID 5阵列内的多个磁盘驱动器。

忽略上述情况,我们仍然假设,如果两个索引行在链表上彼此相邻(或者在唯一索引中,相同键值的行指针意味着彼此相邻),那么我们就认为这两行在物理上也相邻。这就意味着QUBE认为所有的索引都有最理想的顺序。

读取一组连续的表行

读取一组连续的表行有如下两种情况:

  1. 全表扫描
    从TP1(表页1)开始,读取该页上所有的记录,然后再访问TP2,一次类推。按照记录在表页中存储的顺序进行读取,没有其他特殊的顺序。
  2. 聚簇索引扫描
    读取索引片上第一个索引行,然后获取相应的表行,再访问第二个索引行,以此类推。如果索引行与对应的表行记录顺序完全一致(聚簇率为100%),那么除了第一次之外的所有表访问就都是顺序访问。表记录的链接方式跟索引不一样。单个表页中记录的顺序无关紧要,只要访问的下一个表记录在同一个表页或者相邻的下一个表页内就可以了。

同索引一样,存储表的传统方式也是将所有表页保留在一个连续的空间内。引起顺序杂乱或碎片化的因素也和索引中的相似,但又两个地方不同:

  1. 如果往表中插入的记录在聚簇索引所定义的主页中装不下,则通常不会移动现有的行,而是会将新插入的记录存储到离主页尽可能近的表页中。对第二个页的随机I/O会使聚簇索引扫描变得更慢,但是如果这条记录离主页很近,这些额外的开销就可以被避免,因为顺预读功能会一次性将多个表页装载到数据库缓存中。即使顺序预读功能没有使用,也只有当该页在数据库缓存被覆盖的情况下才会发生额外的随机I/O。
  2. 一条记录被更新后,可能因为表行过长导致其无法再存储于当前的表页中。这是DBMA就必须将该行记录迁移至另外一个表页中,同时在原有的表页中存储指向新表页的指针。当该行被访问时,会引入额外的随机访问。
    表可以通过重组来还原行记录的顺序,从而减少不必要的随机访问。

计算访问次数

随机访问

我们首先思考一下磁盘读与访问的区别。一次磁盘读所访问的对象是一个页,而一次访问的访问对象则是一行。一次随机磁盘读会将一整页(通常会包含很多行)读取至数据库的缓冲池中,但是根据定义,前后两次随机读不太可能会访问到同一个页。

使用满足需求的成本最低的索引还是所能达到的最有索引

当有多个等值谓词作为匹配列时,我们需要考虑这些列在索引上的先后顺序。经常变化的列应当尽可能的排在后面。

更改现有索引列的顺序和在现有索引列之间添加新列同样危险。在这两种情况下,现有的select的执行速度都可能会急剧下降,因为匹配列减少了,或者引入了排序(导致过早产生结果集)

半宽索引(最大化索引过滤)

在现有索引的末端添加缺少的谓词列可以消除大量的随机访问,因为这样能引入索引过滤过程。

影响索引设计过程的因素

I/O时间估算:

  • 随机读取 10ms(页的大小为4KB或8KB)
  • 顺序读取 40MB/s

这些数据是假定系统使用当前硬件并在一个合理的负载下运行时的值。一些系统可能运行的更慢或处理超负荷状态。

困难谓词

大体上,假设一个谓词的判定结果为false,而这时如果不检查其他谓词就不能确定地将一行记录排除在外,那么这类谓词对优化器而言就是太过困难的。

过滤因子隐患

当以下三个条件同时满足时,这种过滤因子隐患可能会产生 :

  • 访问路径中没有排序
  • 第一屏结果一建立就回应
  • 不是所有的谓词字段都参与定义带扫描的索引片–换句话说就是,不是所有的字段都是匹配字段。

被动式索引设计

被动式的方法与莱特兄弟创造守架飞机的经历非常相似。本质上就是把查询放在一起,推下悬崖,然后看他能否起飞。换句话说,就是为应用设计一个没有索引的原型,然后开始运行一些查询。又或者,创建原始索引集,然后通过运行应用来看那些索引被用到,那些没有被用到。即使是一个小型的数据库系统,运行速度慢的查询也会被很快凸显出来。

被动式调优的方法也被用来理解和调优一个性能没有满足预期的已有应用。

对结果集排序

除了全表扫描和全索引扫描,结果集的排序就是最有用的警示信号了。引起排序的原因可能有以下两种:

  • 没有可使查询语句避免排序的索引。
  • 优化器所选择的访问路径包含了一次多余的排序。

有很多数据库顾问将排序视为敌人。我们认为,哪些强调随机I/O带来致命影响的顾问更值得信任。

成本估算

一些数据库管理系统的EXPLAIN功能显示了优化器对所选访问路径的本地响应时间的估算,或至少显示了对CPU时间的估算。

不幸的是,以下两个严重问题限制了使用成本估算方法的价值:

  • 优化器所做出的的本地响应时间估算可能与实际相差很大
  • 当谓词使用绑定变量时(显然这是很普遍的),优化器对过滤因子的估算是基于平均输入值的,或更差情况下,基于默认值。为了获取更有价值的最差情况估值,EXPLAIN中的绑定变量必须用最差情况下的输入值来代替。这是一个需要应用知识的累人操作。

为表连接设计索引

预测表的访问顺序

在大部分情况下,可以使用以下经验法则来预测最佳的表访问顺序 : 将包含最低数量本地行的表作为外层表。

本地行的数量是指最大过滤因子过滤本地谓词之后所剩余的行数。

经验法则忽略了以下因素:

  1. 排序。
  2. 很小的表。非常小的表及其索引可能长期存在于数据库的缓冲池中,至少在一个连接查询中,没有页会被读取多次。在这样的表和索引上进行随机读取所耗费的时间小于0.1ms,至少在页被第一次读取之后是这样的。所以,当这样的表不是外层表时,对其大量的随机读取也不会称为问题。
  3. 聚簇比例。索引中行的顺序和表中行的顺序的关联性(对于聚簇索引而言,该关联性在表重组后为100%),可能会影响对最佳访问顺序的选择,当然,除非索引是宽索引。

最好的基于成本的优化器在进行路径选择时会把这些因素考虑进来。因此,他找出的访问顺序可能比我们基于本地行的数量的经验所得出的结果更优。

合并扫描连接和哈希连接

合并扫描连接

执行过程如下

  • 执行表或索引扫描以找出满足本地谓词的所有行。
  • 随后可能会进行排序,如果这些扫描未按所要求的顺序提供结果集。
  • 对前两者生成的临时表进行合并。

在以下情况下,合并扫描会比嵌套循环快。

  1. 用于连接的字段上没有可用的索引。在这种情况下,若使用嵌套循环,那么内层表可能需要被扫描很多次。在实际情况中,用于连接的列上面没有索引的情况很少见,因为大部分连接谓词都是基于“主键等于外键”这一条件的。
  2. 结果表很大。在这种情况下,若使用嵌套循环连接,可能会导致相同的页被不断的重复访问。
  3. 连接查询中不止一张表的过滤因子很低。如我们所见,嵌套循环可能导致对内层表(或者内层表索引)的大量随机访问。

例如:

1
2
3
4
5
6
7
8
DECLARE CURSOR81 CURSOR FOR
SELECT CNAME, CTYPE, INO, IEUR
FROM CUST, INVOICE
WHERE CUST.CTYPE = :CTYPE
AND
IDATE > :IDATE
AND
CUST.CNO = INVOICE.CNO

哈希连接

哈希连接本质上是用哈希算法代替排序算法的合并扫描连接。首先,对较小的结果集用哈希算法计算其连接字段,并将其保存在一个临时表中;然后,再扫描其他的表(或索引片),并通过(计算得到的)哈希值将满足本地谓词条件的每一行记录与临时表中相应的行进行匹配。

若结果行集已在索引中满足了所要求的顺序,那么合并扫描的速度将更快。若合并扫描需要进行排序,那么哈希连接的速度可能更快,尤其是当其中一个行集能够全部留在内存中时(对一个哈希表进行一次随机访问所花费的CPU时间,通常会比排序和合并一行所花费的时间少)。如果两个行集很大,那么哈希表会根据可用内存的大小对哈希表进行分区(同一时间内存中只有一个分区),而另外一个行集会被扫描多次。

为什么连接的性能表现较差

模糊的索引设计

“在连接字段上建索引”是最古老的索引建议之一。事实上,这是基于建议的一个扩展 : “为主键创建一个索引,并且为每一个外键创建一个由此外键作为前导列的索引”。在连接谓词上建索引使得嵌套循环称为一个可行的方案,但包含连接谓词列并不一定能够提供完全可接受的响应时间。连接谓词列上的索引和本地谓词上的索引通常都需要是宽索引。而且,不同的表访问顺序可能导致完全不同的索引需求。

为子查询设计索引

从性能的角度看,子查询与连接十分相似。实际上,现今的优化器通常会在进行访问路径的选择之前,先将子查询重写为一个连接。若优化器没有进行重写,那么子查询的类型本身可能就决定了表访问顺序。内外层无关联的子查询通常会从最内层的SELECT开始执行。结果集被保存在一张临时表中,等待下一个SELECT的访问。内外层有关联的子查询通常会从最内层的SELECT开始执行。无论是何种情况,同连接一样,应当基于能够形成最快访问路径的表访问顺序进行索引设计。若最佳的表访问顺序未被选中,那么程序开发人员可能需要对语句进行重写,在某些情况下还可能要使用连接。

为UNION语句设计索引

通过UNION或UNION ALL连接的SELECT语句是逐个分别进行优化和指向的。因此,应该为每个独立的SELECT设计合适的索引。需要注意一点,带ORDER BY的UNION可能会导致提前物化。

对于表设计的思考

冗余数据

有两种通过冗余数据优化连接速度的方法:

  1. 将某列拷贝至依赖表(向下反范式法)。
  2. 将汇总数据添加至父表(向上反范式法)。

向下反范式化

不过,总体而言,当我们考虑引入向下反范式化时,需要预测一下冗余字段更新时可能会导致最差情况下的索引随机访问次数。

反范式化的成本

考虑性能时最令人关注的通常是,为了更新表及索引上的冗余字段锁带来的I/O时间。在向下反范式化中,这可能需要移动大量的索引行,从而导致一个简单的UPDATE运行的很慢。向上反范式化不太可能因为一次简单的更新操作而引发I/O剧增。不过INSERT,UPDATE和DELETE可能导致父表及其索引上的一些额外I/O。在极端情况下,如每秒10次以上的INSERT或UPDATE,由这些I/O带来的磁盘负载可能会成为问题。

嵌套循环连接和合并扫描连接/哈希连接 VS 反范式化

许多数据库专家不愿意将冗余列添加至事务型表上,这是可以理解的。反范式化不仅仅是查询速度和更新速度之间的一个权衡,在某种程度上,他还是性能和数据完整性之间的一个权衡,即使在使用触发器来维护冗余数据的情况下。然而,当嵌套循环引入了过多的随机访问,且MS/HJ耗费了过多的CPU时间时,反范式化可能成为唯一的选择。尽管如此,在决定采用这一极端的方案之前,我们必须确保所有能够避免这一方案的方法都已经考虑过了。

无意识的表设计

从性能的角度看,我们非常难以理解为何有那么多的数据库中存在具有1 : 1或1: C(C = 有条件的;即0或1)关系的表。

为何要建四张表而非只建一张CUST表?只要关系永远不会变成1 : M,那么灵活性就不会成为问题。在本例中,客户要么是公司,要么是个人,且不会有客户死亡两次!

将这四张表合成一张部分字段为空的表(对于每一行,要么公司相关的字段为空,要么个人相关的字段为空;同样,所有活着的客户的死亡相关的字段为空),这是存储空间和性能(随机访问的次数)之间的权衡。为空的数据并不违反范式。

在不考虑硬件性能的情况下设计表可能会有如下问题 :

  • 即便是在最佳索引条件下,随机访问的次数仍可能会很高。
  • 复杂连接可能使得索引设计变得非常困难。
  • 优化器可能对复杂连接做出错误的访问路径选择。

星型连接

介绍

星型连接与普通连接的差别主要有两个方面:

  1. 如下图所示,位于星型结构中心位置的表称为事实表,它的数据量远大于它周围的表—维度表
  2. 最佳的访问路径通常是包含维度表的笛卡尔积,这意味着他们没有相同的冗余列,满足本地谓词的维度表数据行都会参与连接。

SALES 销售记录
STORE 出售的店铺
ITEM 出售的商品
DATE 出售的时间
CUST 出售的客户

在星型连接中,事实表的数据量通过都比较大。在这种情况下,至少依据经验法则,事实表应该作为嵌套循环连接方式中最内层的表。一般情况下未读表都没有共同的列,所以这种链接顺序意味着是笛卡尔连接。

事实表的索引

事实上,宽索引通常比事实表还大,原因有两个 :

  1. 表通常都进行了压缩处理,而索引没有。
  2. 新增一条记录通常都追加到表的尾部,因此事实表并不需要分散的空闲空间。但插入到索引(除了聚簇索引)上的位置是随机的。为了避免频繁的索引重组,在当前硬件条件下,通常10亿行的表将花费几个小时,大多数的索引在叶子节点上都需要留出足够的空闲空间,可能为30% ~ 40%。

汇总表

即使是在理想索引的情况下,一些针对10亿条记录的事实表进行的查询也会导致大量的I/O访问。提高这类查询的性能的唯一方式就是使用汇总表(查询表)。这类表是反范式化的事实表。如果表不是特别大(比如只包含几百万行数据),那么这是一个比较可行的方案,因为反模式化查询只需针对汇总表,而不需要多表关联。

如果频繁查询每周的销售情况,那么可以针对每周的消费记录建立一张汇总表。比较好的汇总表设计是根据周,商品,商店汇总一条记录。汇总表根据周和商品进行汇总后,数据量可以大幅度减少。在这种情况下,查询的响应时间可能降低到不到1秒钟。

汇总表上的索引通常会比较小,他唯一的显示因素就是刷新此表所需的时间。如同所有新鲜事物一样,汇总表的方案也会带来新的问题。

  1. 如果用户的查询需求多样,汇总表的设计会比索引的设计更困难,不过,已经有一些工具基于查询日志来协助汇总表的设计。
  2. 如果优化器不能选择正确的汇总表,那么汇总表的意义就不大;我们不能指望用户来指定查询使用某个合适的汇总表。最好的优化器已经在试着访问合适的表了,虽然SELECT语句实际上查询的是事实表。如果优化器不具备这个能力,或者它的正确率不够高,那么可能就不得不强制指定每个用户只能访问一个汇总表。用户不得不自己选择要使用的汇总表。优化器能自动识别的汇总表通常被称为自动汇总表或物化视图。

多索引访问

简介

许多数据库管理系统支持从一张表的多个索引处收集制作,或是从单个索引的几个索引片收集,然后比较这些指针集并访问满足WHERE语句中所有谓词条件的数据行。这一能力被称为多索引访问,或被称为索引与(索引交集)和索引或(索引并集)。

多索引访问的思想是:对表中数据分别使用各个索引,最后将满足条件的进行交集或并集操作。

索引和索引重组

DBMS如何查找索引行

在当前的硬件条件下,非叶子页很可能已经被缓存在数据库缓冲池中,或者至少在磁盘的读缓存中,因为它们经常被频繁的访问。

插入一行会发生什么?

如果一张表有一个聚簇索引,那么DBMS会根据聚簇索引的键值尝试将插入的记录放在它所属的表页(主页)中。如果这行记录在主页里放不下,或者当前页被锁住,那么DBMS将会检查邻近的页。在最坏的情况下,新的行会被插入到标的最坏一页。依赖于DBMS和表的类型,已经插入的行通常都不会被移动,否则这将意味着更新表上已经建立的所有索引上的相关指针。当有许多表行未能存在在主页中时,如果表行的顺序很重要,则需要对这个表进行重组—对于那些涉及多张大表的大规模批处理任务而言,通常需要这么做。

当往表中插入一条记录时,DBMS会尝试将索引行添加至其索引建所属的叶子页上,但是该索引页可能没有足够的空闲空间来存放这个索引行,在这种情况下,DBMS将会分裂该叶子页。其中一半的行将被移动到一个新的叶子页上,并尽可能地靠近被分裂的页,但是在最坏的情况下,这个索引页可能会被放置在索引的末尾。除了在每个叶子页上预留部分比例的空闲空间外,也许可以在索引被创建或重组时,每n个页面预留一个空页—当索引分裂无法避免时,这会是一个不错的办法。

当一个索引有一个不断增长的键值时,新行将被添加到索引页的最后,索引页可能永远也不会进行分裂,这样的索引可能不需要任何空闲空间。

叶子页的分裂严重吗?

分裂一个索引页只需一次额外的同步读,约10ms。除了两个叶子页以外,DBMS通常还必须更新一个非叶子页,而它很可能已经在内存或者读缓存中了。

在叶子页分裂后,查询任何一条索引行的速度很可能同之前一样快。在最坏情况下,一次分裂会创建一个新的索引层级,但是如果不是从磁盘读取非叶子页的话,这只会增加很少的CPU时间。

然而,叶子页的分裂会导致一个索引片变得更慢。目前为止,我们在所有的场景中都假设串联索引行的链指针总是指向同一页或者下一页,这些页可能已被DBMS预读取。在索引被创建或者重组后,这种假设是接近真实情况的,但是索引片上的每处叶子页分裂都可能会增加额外的两次随机访问—一次是为了查找索引行被移动至的索引页,一次是为了返回到扫描的原始位置。其中第一次随机访问很可能会导致一次磁盘的随机读取(10ms)。

什么时候应该对索引进行重组?

插入模式

索引重组是为了恢复索引行正确的物理位置,他对于索引片扫描和全索引扫描的性能而言很重要。因为插入模式的不同,增加的索引行可能会以无序的方式来创建。我们需要记住,更新一个列意味着需要删除旧的索引行,并增加一个新的索引行,新索引行的位置由新的索引键值来确定。

下文对三种基本插入模式的讨论基于如下假设

  1. 索引是唯一索引。
  2. 被删除的索引行锁腾出的空间在重组之前可以被新的索引行重用。

新索引行被添加至索引的尾部(永远递增的键)

假设插入了一个索引行,其索引键值比任何已经存在的索引键值都要大,则DBMS就不会分类最后的叶子页,那么就不需要空闲的空间或者进行索引重组了。然而,如果在索引前面的索引行被定期地删除,那么为了回收空闲的空间,索引可能不得不进行重组(一个“爬行”的索引)。

随机插入模式

我们稍后将会看到,尽管考虑了空闲空间和重组,对于不同的索引行长度(短,中,长)的处理也是不同的。越长的索引行越难处理,越短的越好处理。

有一个重要的例外场景 : 如果索引行是变长的,那么就需要有空闲的空间去适应任何索引行的增长。

索引重组的代价

一个索引可以以多种方式进行重组:

  1. 全索引扫描(随机访问且无须排序,或者顺序访问并排序)。
  2. 全表扫描(类似 CREATE INDEX; 顺序访问及一次排序)。

由索引重组产生的锁等待依赖于具体的数据库和选项。如果使用的是简易的工具,那么当表或者索引正在被扫描吋,整个表可能被加上一个S锁(更新操作会被阻塞)。如果工具能在扫描期间将更新操作保存下来,并在排序前将它们应用到数据行上,那么锁等待的时间将会缩短很多。

有些时候,大的索引可能不得不在不合适的时间被重组。在最坏情况下,锁的问题可能会导致频繁的重组无法实现。在这种情况下 , 一些易变的索引可能必需被强制缓存在内存中(将其固定在内存中)。

数据库管理系统相关的索引限制

索引列的数量

能够复制到索引上的列的个数上限在16至64之间。并非每个人都将这视为一个问题。 Gulutzan 和 Pelzer提出了一个出人意料的
建议,如下:

针对所有数据库管理系统的总体建议为:在一个复合索引中最多使用5列。虽然你能够确定数据库管理系统至少能够支持16列,但是5列是一些专家所认为的合理上限。

索引列的总长度

复制到索引的列的总长度存在一个上限,该上限的值取决于数据库管理系统。随着宽索引变得越来越流行,这一上限在数据库筲理系统的新版本中在变大。

单表索引数量上限

在单表索引数量限制方面,许多数据库产品要么没有上限,要么上限太高以至于无关紧要。

索引大小上限

典型的索引大小上限为几GB,而且这一上限正在持续增大。就像大表一样,大索引通常是分区的,这样能够使执行维护程序的成本最小化,并且能将索引分散到多个磁盘驱动器或RAID组上。

索引锁定

从更新的时间点到提交的时间点内,如果数据库管理系统给一个索引页或者一个索引页的一部分(如一个子页)加了锁,那么该索引页或子页很能会成为瓶颈,因为插入操作将会变为顺序的。例如,SQL Server 2000就是这样做的,但如果上锁的粒度仅为一行,那么这不可能会成一个问题。

在DB2数据库的z/OS版本中,使用闩锁来保证索引页的物理完幣性。当用闩锁对一个缓冲池中的页加锁时,实际上是在数据库缓冲池中进行了一次置位操作,当释放闩锁时再进行重置。一个页只有在读取或修改时才会被加上闩锁,在当前的处理器条件下耗费时间不到一微秒。而数据完幣性是通过对索引行所指向的表页或表行加上普通锁来保证的(仅对数据上锁)。当程序修改一个表行或表页。这些锁一直不会释放,直至修改被提交。

数据库索引选项

索引键决定了这一索引行在索引结构中的位置。当索引键被修改后,DBMS会删除原来的索引行,并将其插入到新的位置上。在最差情况下,索引行会被移动到其他的叶子页上。

其他评估事项

宽索引还是理想索引

单纯从响应时间来看,理想的索引并非具有完全的优势,我们给出了如下结论 :

虽然三星索引有一定的优势,尤其是在结果集为空的情况下,但是这个优势并不也别明显,而且会带来与新增索引相关的额外开销。

组织索引设计过程

简介

在大公司里,一个合理的折中方案是聘用50/50的专家,他们会将50%的时间用来应用程序开发,另外50%的时间用于协助同事进行索引评估及其他性能问题的处理(比如根据EXPLAIN的输出内容解决某个优化器问题)。经验显示,为每5至10位应用开发者配一名50/50专家的方式效果很好。

索引设计需要同事掌握技术技能以及应用系统知识。相比让数据库专家熟悉应用系统的细节而言,教会开发人员索引技能是更容易的。


PDF书籍下载地址:
https://github.com/jiankunking/books-recommendation/tree/master/Database

欢迎关注我的其它发布渠道