数据库索引设计与优化06-星型连接

介绍

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

假设事实表SALES有100万行记录,每行代表一条销售记录。4张维度表(DATE,1000行;STORE,10000行;CUST,1000000行;ITEM,100000行)。每行代表一条销售记录。4张维度表提供了每条销售记录的详细信息 : 哪家店的那件商品在何时销售给了哪位客户。为了更好的理解,我们使用SQL 9.1展示一个示例,这个示例简化了场景,只使用除客户信息表以外的三个维度表的信息(我们假设并不需要获取客户的信息)。
SQL 9.1

SELECT SUM(EUR)
FROM SALES, DATE, ITEM, STORE
WHERE ITEM.GROUP = 327
      AND
      DATE.WEEK = 327
      AND
      STORE.REGION = 101
      AND
      SALES.ITEMPK = ITEM.ITEMPK
      AND
      SALES.DATEPK = DATE.DATEPK
      AND
      SALES.STOREPK = STORE.STOREPK

这个星型连接很简单 : 某种商品在某个地区的周销售总额。ITEM表中包含产品码,DATE表中包含日期,STORE表中包含地区码。

在数据仓库环境中,星型模型(和星型连接)比较普遍,因为终端用户只需要一条简单的SELECT语句,就可以从n个维度的数据立方体中获取期望的结果集。

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

接下来将讨论影响连接性能的两个主要因素 : 所以设计和表访问顺序。随着讨论的展开,笛卡尔连接的概念将逐渐清晰起来。我们将首先讨论维度表的索引设计,然后讨论表的访问顺序,最后讨论事实表的索引设计。

维度表的索引设计

索引的顺序访问次数等于维度表的行数乘以匹配谓词的过滤因子(FF),比如

WHERE DOB BETWEEN :BDATE1 AND :BDATE2      FF = 10%
      AND
      SEX = :SEX                           FF = 50%

维度表CUST的这些本地谓词会产生0.1 x 1000000 = 100000次对索引(DOB, ...)的顺序访问,因为只有一个匹配列;根据QUBE规则,范围谓词DOB是最后有一个匹配列。根据QUBE算法,这一步将花费1s时间。

为了最大化任意WHERE条件的匹配数量,针对4个列DOB,SEX,A和B的查询大约需要4 x 3 x 2 x 1 = 24个宽索引。但事实是,通过对终端用户的调查或通过跟踪用户的查询语句,对于大多数的查询,我们有可能做到使用几个索引就为大部分查询实现多个匹配列。举个例子 : 一个用户可能对不同年龄段(FF = 10%)的不同性别的客户的销售情况感兴趣,那么索引(SEX, DOBM, A, B, CNO)就要优于其他所有,因为相同年龄段相同性别的用户,比如三十多岁的男性,在索引结构上是相邻的。按照QUBE算法,两个匹配列的过滤因子是0.05(不是0.1),所以扫描这个索引片段只需要0.5s。

表访问顺序的影响

表的访问顺序在星型连接中比在普通的表连接中更为重要。假设我们在从DATE维度表开始查询,在该表中通过给定的星期号,来确定属于这个星期的所有日期。在DATE表中,我们有跨度为三年的记录,每天对应一条记录。我们只对其中一个星期感兴趣,所以DATE表访问的过滤因子就是7/1000 = 0.7%---只需访问表中的7行数据。按常理判断,需要访问0.7%的的SALES表行,这意味着将进行7000000次的SALES表访问和索引访问(如果索引设计良好那就只需进行索引访问)

如果使用STORE或者ITEMS表作为驱动表,则相应的表或者索引访问的计数可能更为庞大,所以现在我们来考虑一下在访问事实表SALES之前访问所有维度表的可能性,如下所示,尽管每个维度表都有本地谓词,但维度表之间并没有关联谓词。

DATE(1000行,FF = 0.7%) -> STORE(10000行,FF = 10%) -> TEMP1(7000行) -> ITEM(100000行,FF = 1%) -> TEMP2(7000000行) -> SALES(1000000000行)

如果事实表作为星型连接中最内层的表,那么数据为这个查询必须建立一张包含所有的有效外键组合的中间表。这个中间表是三个维度表中满足本地谓词的主键的笛卡尔积,如果主键比较短,那么上述例子中的中间表大小可能不超过100MB,也许能够被直接保存在数据库的缓冲池中。

第一张临时表的行数将会是 : (0.7 x 1000) x (10% x 10000) = 7 x 1000 = 7000
第二张临时表的行数将会是 : 7000 x (1% x 100000) = 7000 x 1000 = 7000000

事实表的索引

创建完第二个中间临时表后,数据库系统将根据关联外键组合来读取所有与其匹配的事实表记录。一些情况下,一个组合键会对应多条事实表记录(例如一个商店在一天当中销售了多个同款商品),也可能没有关联事实表记录。所以,这里不能准确地估算事实表的记录访问次数,但该值可能高达百万。

我们需要设计一个良好的索引,它将选择性最好的列作为起始列,来满足用户对响应时间的要求。有两种理论上可行的扫描方法。

第一种,优化器选择扫描一个单一的索引片段,索引片段的大小取决于DATENO这一个匹配字段。选择这种方式的原因是我们需要扫描一个时间段的额数据,即某一周的七天,比如DATENO列的值从764到770。我们之前已经计算过这个索引片段包含0.7 x 1000000000 = 7000000条记录。

第二种,“聪明的”优化器可能会把分成多个子扫描,对于每一个日期(大约有1000000000 / 1000 = 1000000条记录),基于ITEMNO列将有1000个(100000的1%)子片段。所以,一个星期将有7000个不同的索引片段(两个匹配段),每个索引片段平均为1000000 / 100000 = 10条记录。在这一场景下,厚度为10行的7000个索引片意味着扫描70000条记录。

这两种方式的比较结果将是 :
1 MC 1 x 10ms + 7000000 x 0.01ms ≈ 70s
2 MC 7000 x 10ms + (7000 x 10 x 0.01)ms = 70s + 0.7s ≈ 71s

访问索引表时将通过宽索引进行排序,如果内存足够,那么这个操作将非常快。

在给定的过滤条件和假设的满足条件的事实表记录数下,zhiy7ao优化器选择了相同的访问路径,星型连接的响应时间很可能就是几分钟。这个时间估计包含了访问维度表,构建和读取两个中间表所花费的总时间。

如果只有4张维度表,我们可以使用任意一个维度表的外键组成的索引与事实表进行星型连接。然而,一张又有10亿条记录的表上的4个宽索引将非常大,4个索引的总磁盘空间需求大约为上百GB大小。

假设租用磁盘空间的费用是50美元/GB/月,那么4个索引每个月共需要12000美元,事实上,宽索引通常比事实表还大,原因有两个 :

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

然而,在性能问题上,最大的挑战还是过滤因子和匹配结果集大小的不可预知性。如果针对ITEM的查询覆盖了10%(而不是1%)的销售记录,那么临时表将会有7千万条记录,最终响应时间也将增长到不可接受的长度。如果事实表的结果集大小是1亿而不是1千万,那么即使索引行只分散在少数几个索引片上,大量对表的顺序访问也将大大增加响应时间。

汇总表

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

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

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

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

数据库索引设计与优化05-为表连接设计索引

为连接查询设计合适的索引比为单表设计索引更困难,因为表连接方式及表的访问顺序对索引影响很大。不过,前面锁讨论的索引设计方法仍然适用于连接查询,只是需要进行一些额外的考量。

在一个链接查询中有两类谓词 : 本地谓词和链接谓词。只用于访问一张表的谓词称为本地谓词,定义了表和表之间的连接关系的谓词称为连接谓词。大部分优化器是通过评估各种可行方案本地响应时间来决定采用哪种连接方式和表访问顺序的。尽管随着顺序读速度的提高,哈希连接和合并扫描连接变得越来越流行,但嵌套循环连接依旧是最常用的连接方式。在前台循环中,DBMS首先在外层表中找到一行满足本地谓词的记录,然后再从内层表中查找与这一行数据相对的记录,并检查其中哪些符合内层表的本地谓词条件,以此类推。

一个两表连接查询可以被两个单表的游标以及在程序中编写的嵌套循环代码代替。在这种方式中,表的访问顺序-哪张表在外层循环,是有程序员来决定的。若使用连接查询的方式,则表的访问顺序是由优化器来决定的,虽然这可能被提示或其他技巧重写。

链接谓词大部分是基于主键=外键这一条件。假设外键上有合适的索引(以外键 的列作为前导列的索引)并且结果集不是特别大,那么嵌套循环可能是最快的链接方式了,至少当所有的本地谓词均指向同一张表时是如此。

如果循环嵌套不合适,那么合并扫描或者哈希连接可能会更快。如果使用前者,在必要的情况下(在用本地谓词筛选之后),一张或多张表将会按一致的顺序进行排序,随后表或文件中符合条件的记录会被合并。哈希连接本质上是使用了哈希而非排序的一种合并扫描。使用这种方法时,所有表页被访问的次数都不会超过一次。

两个简单的表连接

例 8.1 CUST作为外层表

SELECT CNAME,CTYPE,INO,IEUR
FROM CUST, INVOICE
WHERE CUST.CNO = :CNO
AND CUST.CNO = INVOICE.CNO
WE WANT 20 ROWS PLEASE

这是一个从两个不同的表中获取数据的非常简单的例子,查询通过主键CNP索引访问主键列开始,所以在CUST表中将只访问一次记录便可获取两个列的值。

连接谓词显示客户号也被用来通过外键CNO索引访问INVOICE表,从而获取另外两个列的数据。每个客户平均会有20张发票(1000000行客户记录和20000000行发票记录),当然有些客户会有更多的发票。

我们假设在INVOICE表上的CNO索引不是聚簇索引。

按照QUBE方法计算,将得到一个非常不错的响应时间

索引 CNO      TR = 1    TS = 0
表   INVOICE  TR = 20
提取 20 * 0.1ms
LRT = 21 * 10ms + 20 * 0.1ms
    = 212ms

在这个连接查询中,CUST表无疑是外层表。where语句中包含了主键的谓词条件,所以DBMS就会知道只有一条记录是满足查询需求的,因此就只需对内层表进行一次简单的扫描,在INVOICE表上而没有本地谓词,所以该表必定内层表。

用两个单独的查询语句代替单个连接查询语句所需要进行的处理过程也是同样的。第一步,在CUST表上使用主键进行查询;第二步,在第二个SELECT语句中使用同一个客户号通过一个游标进行查询,获取20条记录。同理,QUBE的计算结果也是相同的(FETCH调用量除外)。

例 8.2 : INVOICE表作为外层表

SELECT CNAME, CTYPE, INO, IEUR
FROM CUST, INVOICE
WHERE IDATE = :IDATE
      AND
      CUST.CNO = INVOICE.CNO
WE WANT 20 ROWS PLEASE

这是又一个从两张不同的表查询数据的简单例子,在这个例子中,查询将从INVOICE表中date字段上的idate索引开始,因为查询语句从未提供有关客户的信息。假设我们只需要前20行发票数据,谓词需要提取出其中所需的两个列的数据以及每一个发票的客户号,然后才能通过CNO上的索引来访问CUST表,即现在的内层表。CUST表的访问像之前一样是通过主键索引进行的额,每张发票对应CUST表中的一行记录。

每一张表很可能会对应一个不同的客户,所以会有较大数量的随机读。因此这个查询的响应时间将比之前一个查询的响应时间长

索引 IDATE      TR = 1    TS = 20
表   INVOICE    TR = 20
表   CUST       TR = 20   TS = 0
索引 CUST       TR = 20   TS = 0
提取 20 * 0.1ms
LRT = 61 * 10ms + 20 * 0.01ms + 20 * 0.1ms
    = 612.2ms

同之前一样,哪张表是外层表,即起始点,是确定的。在CUST表上没有本地谓词,所以他是内层表。

当使用两个分开的查询代替单个连接语句时,处理过程也是同样的。第一步,通过INVOICE表的游标进行查询;第二步,通过第一步查询的客户号查询CUST表,从而获取对应列的数据。同样,QUBE解决是相同的(FETCH调用量除外)。

表访问顺序对索引设计的影响

在前面的两个例子中,本地谓词连同可用的索引现在使得我们在起始点方面别无他选。然而,许多人发现实际情况并不总是这样。接下来我们将通过一个案例来讨论其中一种不那么简单的情况。在案例研究的第一部分,我们将专注于讨论嵌套循环。当我们对其中设计的问题都比较熟悉,特别是对于这种连接方式相关的潜在问题熟悉后,我们会将案例研究的重点转移至合并扫描连接和哈希连接。最后我们将从索引设计的角度来比较这两种技术的优缺点。

案例研究

一家跨国公司拥有80万国内客户以及分布在其他100多个国家的20万客户。这100万客户的数据都存储在CUST表中。INVOICE中有2千万条记录。不论国内客户还是国外客户,平均每人都拥有20张发票。

现在需要一个新的查询,该查询需要通过INVOICE表上的IEUR列查出某个外国国家的高额发片,并将结果降序排列。用户输入包括一个发票总额的下限值和一个国家代码。

这个查询可以通过一个两表链接的SELECT语句来实现,还有一种实现方式是使用两个单表SELECT语句,并用程序实现表连接的逻辑。程序可以建立一个循环嵌套结果,例如程序A可以从表CUST开始(CUST表作为外层表),程序B可以将INVOICE表作为外层表。由于这个查询操作是一个内连接,因此我们能对连接方式进行选择,我们只关心那些至少有一张大额发票的客户。如果我们的查询需求是获取客户信息和他们的发票信息(如果存在),那么这将会是一个外连接,在这种情况下,程序就必须先访问CUST表了。

在接下来的分析中,程序A先访问CUST表(CUST作为外层表),程序B从表INVOICE开始访问(INVOICE表作为外层表)。程序C采用折中的方式,使用两表连接的SELECT语句。若选择此方案,则我们是把中的连接方式和表的访问顺序都交由优化器选择了。当然,表这一层面的决策,如索引的选择等,都是由优化器来做决定的。

程序A CUST表作为外层表

SQL 8.3

DECLARE CURSORC CURSOR FOR
SELECT CNO,CNAME,CTYPE
FROM CUST
WHERE CCTRY = :CCTRY

DECLARE CURSORI CURSOR FOR
SELECT INO, IEUR
FROM INVOICE
WHERE IEUR > :IEUR
      AND
      CNO = :CNO

OPEN CURSORC
     FETCH CURSORC      while CCTRY = :CCTRY
     OPEN CURSORI
           FETCH CURSORI      while IEUR > :IEUR
     CLOSE CURSORI
CLOSE CURSORC

用IEUR对结果集进行排序

程序B INVOICE表作为外层表

SQL 8.4

DECLARE CURSORI CURSOR FOR
SELECT CNO,INO,IEUR
FROM INVOICE
WHERE IEUR > :IEUR
ORDER BY IEUR DESC

OPEN CURSORI
      DO
            DETCH CURSORI      while IEUR > :IEUR
            SELECT CNAME, CTYPE
            FROM CUST
            WHERE CNO = :CNO
            AND
            CCTRY = :CCTRY
      DO END
CLOSE CURSORI

程序C : 由优化器选择外层表

SQL 8.5

DECLARE CURSORJ CURSOR FOR
SELECT CNAME, CTYPE, INO, IEUR
FROM CUST, INVOICE
WHERE IEUR > :IEUR
      AND
      CCTRY = :CCTRY
      AND
      CUST.CNO = INVOICE.CNO
ORDER BY IEUR DESC

OPEN CUSORJ
      FETCH CURSORJ while IEUR > :IEUR and CCTRY = :CCTRY
CLOSE CURSORJ

就像在SQL 8.1和SQL 8.2中的锁看到的那样,当只有一张表上有本地谓词时,从性能的角度来说,从有本地谓词的表开始查询是一个好主意。现在两张表上都有本地谓词,所以程序运行的快慢差别就不那么明显了,除非我们知道表上有哪些索引。

处于案例研究的目的,我们假设除了主键和外键索引外,唯一一个额外的索引在表CUST上(CCTRY字段,过滤因子为10%)。CCTRY代表国家的代码。这种情形下,大部分读者很可能都会选择程序A,因为看起来CUST表上有一个合适的索引,而INVOICE上却没有。

同往常一样,当我们开发一个新程序时,我们需要检查现有索引是否够用,包括在最差输入的情况下。若不够用,那么我们就需要设计更适合的索引,可能以设计和评估理想索引作为开始。

为了对这三个程序之间存在的实际性能差异有一个清晰的理解,我们来比较一下用QUBE对他们评估出的结果,从而了解在当前的索引条件下,这些程序将表现如何。

在评估中我们将使用最高的过滤因此,假设这代表了最差的情况 :
FF (CCTRY = :CCTRY) 最高过滤因子 10%
FF (IEUR > :IEUR) 最高过滤因子 0.1%

现有索引

程序A

第一步 : 通过非聚簇索引CCTRY访问表CUST表。

DBMS必须找到所有来自指定国家的客户。这可以通过一次全表扫描或者通过索引CCTRY来实现。当谓词CCTRY具有很高的过滤因子时,全表扫描会更快,当过滤因子较低时,索引扫描会更快。如果优化器为多次查询只做一次访问路径的选择,那么它会基于1%的过滤因子(通过1除以列CCTRY的不同值个数得出)而选择索引扫描。若优化器基于用户每次输入的实际值进行访问路径的选择,那么只要它知道正在的过滤因子值,他就会毫不犹豫的选择全表扫描。

索引 CCTRY TR = 1 TS = 10% * 1000000
表   CUST    TR = 100000 TS = 0
提取 10% * 1000000 = 10000 * 0.1ms
LRT TR = 100001 TS = 100000
    100001 * 10ms  100000 * 0.01ms
    1000s + 1s + 10s ≈ 1000s

根据QUBE方法,这一步为响应时间贡献了1000s!由于CCTRY索引不是聚簇索引,这使得CUST上的随机访问很高。

使用这一想当然的访问路径所需的时间太多了。在过滤因子为10%的情况下,100000次随机读(约为17min)显然是不可接受的。即使过滤因此变为1%,也需要10000次随机读(1.7min)。而另一种方法,全表扫描,只需要
1 10ms + 1000000 0.01ms = 10ms + 10000ms ≈ 10s

当过滤因子为0.1%时,索引扫描需要1000次随机读,与全表扫描消耗的时间一致。当然,这是因为在QUBE方法中,一次随机访问所需时间是一次顺序访问的1000倍。在过滤因子大于0.1%的情况下,一次全表扫描查询比一次非宽非聚簇的索引扫描要快得多。然而,在得出类似这样的笼统的结论时,我们需要非常小心,因为我们的结论完全能是基于QUBE的数字假设而得出的。我们还需要考虑到表扫描在CPU时间上的耗费会高很多。无论如何,我们应该意识到,在过滤因子很低的情况下,进行非宽非聚簇索引的扫描比表扫描更好。

连同数据提取的时间成本一起,这一步的LRT将会是20s。

第二步 : 通过聚簇索引CNO访问INVOICE表

当从CUST表找出意味来自指定国家的客户后,该客户的所有发票都必须被检查以找到大额发票。由于INVOICE表上的CNO索引是聚簇索引,所以同表行一样,这些记录在索引上是相邻的(平均每位客户20行)。对于类似CUST和INVOICE这样互相关联的大表,拥有一致聚簇方式是非常重要的,对一位能代表平均情况的用户而言,需要进行21次索引访问和20次表访问才能找到所有大额发票,但是只有第一次索引访问和表访问是随机访问。如果处理了100000位客户(最差输入 : 10%的客户),那么访问次数将如下所示。需要注意,程序从DETCH CURSORC传递至OPEN CURSORI的客户号是不连续的,每一次都将导致一次索引随机访问和表随机访问。

索引 CNO      TR = 100000      TS = 100000 * 20
表   INVOICE  TR = 100000      TS = 100000 * 19
提取 100000 * 0.1ms

LRT           TR = 200000      TS = 3900000
              200000 * 10ms    3900000 * 0.01ms
              2000000ms + 39000ms ≈ 2050s

根据QUBE算法,这一步骤的开销成本是第一步的两倍多,所以第一步的表扫描与此次内层表的处理成本相比就显得微不足道了。

第三步 : 结果集排序

在最差的输入情况下,结果集将包含0.1 0.001 20000000 = 2000行大额发票数据。这些结果必须按照发票总额(IEUR)的降序排列。排序操作将会是最后增加的一步操作,可能会使用到临时表。根据我们的估算,这一排序的CPU时间大约是北航0.01ms,2000行将会是0.02s。QUBE方法假设排序时间被提取操作的时间所囊括了,因为他非常肖以至于可以忽略不计。

本地响应时间

在最差输入下,这一访问路径的本地响应时间由以下三部分组成
20s + 2050s + 0s = 2070s ≈ 35min

为了等待第一屏,用户要等待半个多小时!即便你告诉用户在输入国家号码后应该去休息一下,但由于磁盘流量剧增,可能使随机读在半小时内上升至200000次之多,这可能会导致其他正在使用的用户处于明显的排队状态。

程序B : INVOICE表作为外层表

第一步 : INVOICE表全表扫描

INVOICE表有20000000行,要把每一行都检查一遍需要20000001次访问,其中包含了文件末尾标志的访问。只有第一次的随机访问。

表      INVOICE      TR = 1      TS = 20000000
提取    20000 * 0.1ms
                     1 * 10ms + 20000000 * 0.01ms + 2s ≈ 202s

第二步 : 通过聚簇索引CNO来读取大额发票所对应的CUST表行

用我们假定的最差情况下的过滤因子,INVOICE表中有0.001 * 20000000 = 20000张都是大额的。因此,DBMS将通过CNO索引来读取20000行CUST表记录。其中只有10%是符合我们要查找的国家的,即只有2000行是符合条件的,而大部分不符合的记录都将被抛弃。

索引      INVOICE      TR = 20000      TS = 0
表        INVOICE      TR = 20000      TS = 0
提取    2000 * 0.1ms
                     20000 * 10ms + 19999 * 0.01ms + 200ms ≈ 400s

第3步 : 对结果集排序

在第一步中从CURSORI中渠道的20000条数据必须按照发票总额IEUR进行降序排列。排序20000条记录所花费的时间(约200ms)是可以忽略的,同样假设这部分开销非FETCH的开销所囊括了。

本地响应时间
在最差输入的情况下,采用这种访问路径的本地响应时间是以下三个部分的总和
200s + 400s + 0s = 600s = 10min

可以发现程序B比程序A快很多,即便是在当前的索引的条件下-IEUR上面没有索引!怎么会如此呢?这里有如下两个原因。

  1. 在当前的硬件条件下,顺序读是非常快的 : 一张有20000000行记录的表可能在大约3min内就能被全部扫描一遍了(基于QUBE的假定数字)。
  2. 由于谓词IEUR < :IEUR的最大过滤因子仅为0.1%,因此使用程序B时对内层表的随机访问次数比程序A是要少。

程序C :由优化器选择外层表

这是一个结余前面两者之前的程序。由优化器来评估谓词IEUR > :IEUR和CCTRY = :CCTRY的过滤因子,然后再相应的选择表的访问顺序。

对优化器而言,IEUR > :IEUR并不是一个易于评估的谓词,因为优化器并不知道用户对主机变量:IEUR将会输入的值的范围。优化器可能会用一个默认值,如33%或55%。接下来如果他选择嵌套循环的方式,那就是选择了与程序A一样的访问路径,即CUST为外层表。这可能导致在最差输入下,本地响应时间长达35min而不是10min。

除了对外层表的选择以外,程序A,程序B与程序C的QUBE评估结果的唯一区别就是FETCH调用的次数 :
程序A 200000 * 0.1ms = 20s
程序B 40000 * 0.1ms = 4s
程序C 2000 * 0.1ms = 0.2s

从整体耗时上看,这一收益非常小。当然,在其他场景下吗,这一收益可能是显著的。

结论 : 现有索引

很显然,现有索引对于最差输入情况并不够用。我们现在应当考虑设计最合适的索引了,我们以设计和评估理想索引最为开始

理想索引

程序A : CUST表作为外层表

CURSORC的候选索引A是(CCTRY,CNO,CNAME,CTYPR),他是一个三星索引。CURSORI的候选A(CNO,IEUR DESC,INO)也是一个三星索引。当然CNO来自CURSORC。现在我们有了一个基于列CNO和列IEUR的比较窄的索引片。由于这两个索引都是三星索引,所以就不必考虑索引B了。严格来说,对于程序A而言,CURSORI并不需要IEUR在理想索引中做降序排列。但为了简化程序A与程序B的比较,我们仍将假设IEUR是一个降序的列。

第一步 : 从所有(CCTRY, CNO, CNAME, CTYPE)上读取索引片(CCTRY = :CCTRY)

由于CCTRY的过滤因子为10%,所以索引片包含0.1*1000000的索引行。由于我们使用了一个三星索引,所以不需要对表进行访问。

现在这一步中的两个主要开销变成了索引的扫描和数据的提取调用。索引的扫描已经做到了尽可能窄,因而数据提取调用成为了更关键的一个开销,大量的提取调用将耗费10s!

索引      CCTRY, CNO, CNAME, CTYPE     TR = 1      TS = 100000
提取      100000 * 0.1
LRT                                    1 * 10ms + 100000 * 0.01 + 100000 * 0.1ms ≈ 11s
第二步 : 对于每一个CNO,通过索引(CNO,IEUR DESC,INO)来读取所有大额发票

现在每一个CNO对于的索引片由列CNO和IEUR来定义,当一个客户没有大额发票时,DBMS是需要对于执行一次随机访问即可。如果索引的第一行是大额发票,那么DBMS需要继续读取下一行,如此继续。由此,随机访问的次数是100000次(一个具体的CCTRY值对应的客户数量),顺序读的次数是2000次(一个国家对应的大额发票的数量)。

索引      CCTRY, CNO, CNAME, CTYPE     TR = 100000      TS = 100000 * 0.1% * 20
提取      2000 * 0.1ms
LRT                                    100000 * 10ms + 2000 * 0.01 + 2000 * 0.1ms ≈ 1000s
本地响应时间

像以前一样,我们忽略排序的开销,本地响应时间为
11s + 1000s ≈ 17min

我们必须承认一个很重要的事实,即在这个案例中,理想索引所带来的好处被最小化了,因为有大量对内层表索引的随机访问。

程序B : INVOICE表作为外层表

程序B的理想索引和程序A的理想索引是不同的,因为现在用于访问两张表的信息发生了变化。CURRSORI的候选索引A现在变成了(IEUR DESC, INO,CNO)。客户表的候选索引A是(CCTRY, CNO, CNAME, CTYPE)。CNO字段来自CURSORI。他们都是三星索引,因此不需要考虑索引B了。

第一步 : 从索引(IEUR DESC, INO, CNO)上读取IEUR > :IEUR对应的索引片

该索引片包含0.001 * 20000000 = 20000索引行。因此,DBMS需要进行一次随机访问和20000次顺序访问。现在,这一步的主要开销变成了数据提取的处理。开销不会像程序A中的开销那么大,但依旧有2s之多。索引按照所要求的顺序提供结果集,因此无须再进行排序操作。

索引      IEUR DESC, INO, CNO     TR = 1      TS = 20000
提取      20000 * 0.1ms
LRT                              1 * 10ms + 20000 * 0.01ms + 20000 * 0.1ms ≈ 2s
第二步 : 对每张大额发票读取一个索引行(CCTRY, CNO, CNAME, CTYPE)

由于查询的客户号不是连续的,所以DBMS需要做20000次随机访问。其中只有10%的记录符合所指定的国家

索引      CCTRY, CNO, CNAME, CTYPE     TR = 20000      TS = 0
提取      2000 * 0.1ms
LRT                                    20000 * 10ms + 0 * 0.01ms + 2000 * 0.1ms ≈ 200s

本地响应时间
2s + 200s = 202s

从程序A的17min到现在的3.5min是一个巨大缩减,但不幸的是,我们还是要强调与程序A中相同的一点 : 使用理想索引的好处被最小化了,因为存在大量的对内层表的随机访问。

程序C : 由优化器选择外层表

在使用理想索引的情况下,根据我们在评估程序A和程序B得出的结论,如果优化器选择了嵌套循环的连接方式,那么表INVOICE应当作为外层表。

SQL的链接方式和程序的链接方式对比

人民常说使用SQL比使用多游标更高效,这是真的吗?
决定这一推测的最关键的因素是访问路径的选择,也就是连接方式和表访问顺序。程序有时可能会选择比优化器更好的访问路径,有时则不会。最终的访问路径应该是相同的,就像程序B和程序C一样。磁盘I/O的数量也应当是一样的,唯一不同的就是SQL调用的次数。上文中的数字清楚的显示了再这一方面使用链接查询更好。由于程序A和B中存在大量随机I/O,CPU时间相对总的消耗时间占比很低。然而,在有些情况下,CPU时间在本地响应时间中占据了最主要的部分,在这种情况下,使用连接游标的程序将比使用多个单游标的程序快得多。

结论 : 理想索引

虽然使用三星索引后,最差输入的本地响应时间从35min减少到了3.5min,但这一响应时间依旧太长了。下一步必须考虑更改程序,以使它只产生一屏数据,比如每个事务20行记录。请注意,我们迄今为止值关注了嵌套循环连接,我们目前得出的结论很可能会受到一些尚未进行讨论的因素影响。

理想索引,每事务物化一屏结果

程序B+ : 物化单屏事务

我们很容易修改程序B,使它只发起20次数据调用。只需要做到 :

  • 确保访问路径不需要进行排序操作。
  • 修改程序,使其对所发起的调用次数进行计数
  • 将位置信息保存在一张辅助表中,一是下一个事务从改点继续执行。

SQL 8.11

DECLARE CURSORI CURSOR FOR
SELECT CNO,INO,IEUR
FROM INVOICE
WHERE IEUR > :IEUR
ORDER BY IEUR DESC, INO
WE WANT 20 ROWS PLEASE

OPEN CURSORI
      DO
            FETCH CURSORI      max 20 items
            SELECT CNAME,CTYPE
            FROM
            WHERE CNO = :CNO
                  AND
                  CCTRY = :CCTRY
      DO END
CLOSE CURSORI

SAVE / INSERT IEUR, INO  the values of the last line displayed to the user

SQL 8.12

DECLARE CURSORI1 CURSOR FOR
SELECT CNO,INO,IEUR
FROM INVOICE
WHERE IEUR = :IEURLAST
      AND
      INO > :INOLAST
      AND
      IEUR > :IEUR
ORDER BY IEUR DESC, INO
WE WANT 20 ROWS PLEASE

DECLARE CURSORI2 CURSOR FOR
SELECT CNO,INO,IEUR
FROM INVOICE
WHERE IEUR < IEURLAST
      AND
      IEUR > :IEUR
ORDER BY IEUR DESC, INO
WE WANT 20 ROWS PLEASE

READ IEURLAST, INOLAST

OPEN CURSORI1
      DO
            FETCH CURSORI1        max 20 items
            SELECT CNAME, CTYPE
            FROM CUST
            WHERE CNO = :CNO
                  AND
                  CCTRY = :CCTRY
      DO END
CLOSE CURSORI1

OPEN CURSORI2
      DO
            FETCH CURSORI2        until 20 result rows
            SELECT CNAME,CTYPE
            FROM CUST
            WHERE CNO = :CNO
                  AND
                  CCTRY = :CCTRY
      DO END
CLOSE CURSORI2

SAVE / INSERT IEUR, INO the values of the last line displayed to the user

首个事务所需的SQL变更如上所示,请关注其中的20ROWS PLEASE语句和SAVE语句所保存的值。另外,CURESORI游标中发票编号被加到了ORDER BY语句上,因为这对于定位起点是必须的。

当需要请求下一屏数据时,程序必须从所保存的值处开始执行。让我们将这两个值命名为IEURLAST和INOLAST。候选事务所需的SLQ变更如SQL 8.12所示。很可能存在两张或更多的发票拥有相同的总额(IEUR)。因此,程序必须打开一个游标CURSORI1用于查询哪些总额与IEURLAST相等但仍未被展示的发票记录。当该值所对应的所有记录都被提取后,第一个游标被关闭,同时第二个游标CURSORI2被打开,用于查询下一批大额发票记录。

现在,在使用理想索引的情况下,建立一屏数据需要耗费多少时间?让我们再次假设查询对应最大的过滤因子分别为10%和0.1%。

第一步 : 从索引(IEUR DESC, INO, CNO)上查询20张大额发票

响应时间与通过游标CURSORI1和CURSORI2查找到多少行无关。程序无论使用哪个游标,都将扫描一个有200行数据的索引片,因为若过滤因子FF(CCTRY = :CCTRY)为10%,那么平均每10张发票中有一张是来自该特定国家的。这一步骤大约需要进行20 / 0.1 = 200次数据访问,其中只有第一次是随机访问。

索引 IEUR DESC, INO, CNO      TR = 1      TS = 199
提取 200 * 0.1ms
LRT                           TR = 1      TS = 199
                              1 * 10ms     199 * 0.01
                              10ms + 2ms + 20ms = 32ms

第二步 : 对每一笔大额发票读取一个索引行(CCTRY, CNO, CNAME, CTYPE)

由于客户编号不是连续的,所以DBMS必须进行20次随机访问。

索引 CCTRY, CNO, CNAME, CTYPE      TR = 200      TS = 0
提取 20 * 0.1ms
LRT                                TR = 200      TS = 0
                                   200 * 10ms    0 * 0.01
                                   2000ms + 2ms + 0ms ≈ 2s

本地响应时间
32ms + 2s ≈ 2s

结论 : 使用理想索引且每个事务返回一屏数据

在最高过滤因子的情况下,本地响应时间是2s,这是比较能接受的。

理想索引,每事务物化一屏结果集且遇到FF缺陷

以上的评估是在最大过滤因子(10%和0.1%)的情况下做出的。但这不是最差输入情况,因为这个案例符合过滤因子(FF)缺陷的标准。当该特定国家只包含19张大额发票的情况时才是最差的情况。在这种情况下,整个包含大额发片的索引片都必须被扫描,并且每张发票所对应的CCTRY值都需要被校验。于是谓词CCTRY = :CCTRY的过滤因子变成了0.1%。此时用程序B+来构建单屏结果集的响应时间又是多少呢?

程序B+ : 每个事务物化一屏数据

第一步 : 从索引(IEUR DESC, INO, CNO)上找到所有的大额发票

为了找到某特定国家的所有大额发票,若所有满足条件的数据能在一屏中显示,那么DBMS就必须扫描整个包含大额发票的索引片。让我们吧这种情况作为最坏情况的假设,结果集只需要一屏即可显示完整。

索引 IEUR DESC, INO, CNO           TR = 1      TS = 20000000 * 0.1%
提取 20000 * 0.1ms
LRT                                TR = 1      TS = 0
                                   1 * 10ms    20000 * 0.01
                                   10ms + 200ms + 2000ms ≈ 2s

现在我们时区了限制结果集大小的优势,不过幸运的是损失并不是太大。

第二步 : 对每张大额发票读取一个索引行(CCTRY, CNO, CNAME, CTYPE)

因为每一张大额发票都必须被检查,所以该步骤需要对索引进行大量的随机访问。

索引 CCTRY, CNO, CNAME, CTYPE           TR = 20000      TS = 0
提取 2000 * 0.1ms
LRT                                     TR = 20000      TS = 0
                                        20000 * 10ms    20000 * 0.01
                                        200s + 200ms ≈ 200s

本地响应时间
2s + 200s ≈ 3.5min

结论 : 使用理想索引,每个事务物化一屏结果集且遇到FF缺陷

这一情况不免有点让人失望,当结果集能在一屏中显示时,即使采用改进的程序B+,响应时间任由3.5min。这和先前的多屏结果集中第一屏的响应时间形成了鲜明的对比,之前的响应时间仅为2s。现在,理想索引的收益又被内层表索引上的大量TR最小化了,之前遇到的情况又来困扰我们了

程序C+ : 每个事务物化一屏数据

为了使程序C的每个事务只物化一屏数据,我们需要对程序进行修改。这与之前对程序B+所做的修改相同。SQL 8.13所示的程序生成了第一屏的数据。本地响应时间会和程序B+一样,在高过滤因子的情况下表现良好,在低过滤因子的最差情况下变现非常糟糕。后者通过减少FETCH调用次数节省下了一些时间,但由此带来的收益很小。

SQL 8.13

DECLARE CURSORJ CURSOR FOR
SELECT CNAME, CTYPE, INO, IEUR
FROM CUST, INVOICE
WHERE IEUR > :IEUR
      AND
      CCTRY = :CCTRY
      AND
      CUST.CNO = INVOIVE.CNO
ORDER BY IEUR DESC, INO
WE WANT 20 ROWS PLEASE

OPEN CURSORJ
      FETCH CURSORJ while IEUR > :IEUR AND CCTRY = :CCTRY, max 20
CLOSE CURSORJ

SAVE / INSERT IEUR, INO      the values of the last line displayed to user

基本连接问题

这个简单的案例表明,即使最优访问路径使用理想索引,也有可能产生不可接受的响应时间。主要问题在于潜在的对内层表(或索引)的大量随机访问。包含至少一张大额发票的客户的索引片在索引(CCTRY, CNO, CNAME, CTYPE)上都是不连续的。

在前面,我们引入了基本问题BQ : 是否存在或者计划设计一个索引,使它包含所有被WHERE子句引用的列。

在单表的SELECT查询中应用BQ方法是很简单直接的。而对于一个连接查询,为了运用BQ方法,必须先将其分解成几个单表游标。这是一个相对更复杂的过程,将在后面讨论。

当然,BQ背后的原理其实就是,保证只有知道表中的行是必须被访问时,采取访问该表,也许是通过使用索引过滤的方式。我们可以将这个论断扩展到嵌套循环链接中,也就是仅当我们确认内层表(或者索引)的数据是我们需要的数据时,我们采取访问它。我们的基本连接问题BJQ于是变为了 : 是否有 一个已经存在的或者计划添加的索引,包含了所有本地谓词对应的列?这里是指包含了设计的所有表的本地谓词。

于是,能够消除对内层表或者索引的大量随机访问的唯一方法就是,依照这一原则添加冗余的列,是一张表上包含所有的本地谓词。本例中,需要往INVOICE表上添加一个CCTRY列,用INVOICE.CCTRY = :CCTRY代替CCTRY = :CCTRY。现在就可以创建一个包含所有本地谓词的索引了。

在一个连接查询被写完或者被生成之后,试试必要的反范式化,同时创建用来维护冗余表的触发器(INVOICE表的CCTRY列),从而尽早的应用BJQ是一个好主意。

现在,我们的事务无论在什么样的输入下都将运行的非常快了,因为再也不会对索引(CCTRY, CNO, CNAME, CTYPE)有多于20次的随机访问了。

索引 CCTRY, IEUR DESC, INO, CNO      TR = 1      TS = 19
索引 CCTRY, CNO, CNAME, CTYPE        TR = 20
提取 20 * 0.1ms
LRT                                  TR = 21     TS = 19
                                     21 * 10ms   19 * 0.01ms
                                     210ms + 0.2ms + 2ms ≈ 0.2s

给INVOICE表及其索引添加字段CCTRY可能需要180MB(1.5 40000000 3字节)的磁盘空间,如果一个客户移居到了另一个国家(这样的概率极低),那么一个表行和一个索引行就必须被更新。平均每位用户20行大额发票可能意味着对表的20次随机访问和对索引的40次随机访问,共耗费60 * 10ms = 0.6s。

循环嵌套连接

类型程序A程序B
现有索引35min10min
理想索引17min3.5min
理想索引,理想程序(+),多屏结果数据 2s
理想索引,理想程序(+),多屏结果数据(FF缺陷) 3.5min
BJQ理想索引,理想程序(+),单屏结果数据(FF缺陷) 0.2s

预测表的访问顺序

我们可以看到使用嵌套循环的连接方式时,表的访问顺序可能会对性能产生巨大的影响,索引类似。而在未确定表的最佳访问顺序之前,是无法设计理想索引的。

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

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

经验法则忽略了以下因素

  1. 排序。在我们的案例中,ORDER BY IEUR DESC所带来的排序只能通过把INVOICE表作为外层表来避免。而INVOICE表正巧含有最低数量的本地行,但是显然,情况并不总会如此。
  2. 很小的表。非常小的表及其索引可能长期存在于数据库的缓冲池中,至少在一个连接查询中,没有页会被读取多次。在这样的表和索引上进行随机读取所耗费的时间小于0.1ms,至少在页被第一次读取之后是这样的。所以,当这样的表不是外层表时,对其大量的随机读取也不会称为问题。
  3. 聚簇比例。索引中行的顺序和表中行的顺序的关联性(对于聚簇索引而言,该关联性在表重组后为100%),可能会影响对最佳访问顺序的选择,当然,除非索引是宽索引。

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

为什么在基于本地行数量的经验法则中使用最大的过滤因子。这样做只是因为把过滤因子陷阱的情况考虑进来,那么评估过程就太耗时了。如果有一个可选方法避免排序,且程序不能在一个事务中读取所有的行,那么这种简化无疑增加了不恰当建议的风险。但无论如何,基于假设的访问顺序进行索引设计有可能能够提供足够的性能,即使该访问顺序不是最优的。

当我们为一个连接查询设计索引的时候,我们该从哪里开始?理论上讲,我们应该为所有有可能的访问路径设计最好的索引,然后让优化器去选择。然后,我们再删除无用的索引和索引列。然而这样太耗时间了,尤其是在连接涉及的表多余两张时。另外,优化器所做的选择仍然会依赖于输入的值。基于优化器的索引设计工具解决了第一个问题,但没有解决第二个。他们的方案的质量取决于对过滤因子的假设,而这转而又依赖于谓词中绑定变量的输入值。

幸运的是,在大部分情况下,经验法则能够给出令人满意的结果。而且通常情况下,由于最佳的表访问顺序非常明显,我们甚至无需计算本地行的数量。

关键在于,在为连接查询设计索引的时候,要把所假设的连接方法和表访问顺序记录下来。然后,我们就能设计索引了,就像是已经编写好了使用单游标来取代连接游标程序一样。一种常见的错误是在没有涉及连接方式和表访问顺序的确定的访问路径假设情况下进行索引设计。仅仅在连接谓词和本地谓词上有索引是不够的,这往往会导致一些冗余的索引。另外,在一个嵌套循环连接中,内层表通常需要有好的宽索引且以连接谓词列作为前导列。

合并扫描连接和哈希连接

当我们分析用例学习中程序A和程序B的时候,我们发现,对内层表的大量随机访问导致使用理想索引带来的好处非常有限。合并扫描连接和哈希连接的一个主要好处就是能够避免这个问题。

合并扫描连接

执行过程如下

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

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

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

在通过案例对比嵌套循环连接和合并扫描连接之前,我们先通过一个简单的例子来看看合并扫描连接具体要执行哪些步骤,以及我们如何使用QUBE方法来计算本地响应时间。

SQL 8.14

DECLARE CURSOR81 CURSOR FOR
SELECT CNAME, CTYPE, INO, IEUR
FROM CUST, INVOICE
WHERE CUST.CTYPE = :CTYPE
      AND
      IDATE > :IDATE
      AND
      CUST.CNO = INVOICE.CNO

现在,内层表和外层表选择变得不那么重要了,尽管术语仍在被使用。每一个本地谓词都一次被用来生成包含所需行的临时表。所使用的两个谓词的过滤因子都是0.1%,对这些访问使用QUBE方法分析如下。

第一步 : 通过非聚簇索引扫描CUST表

索引 CCTRY          TR = 1      TS = 1000
表   CUST           TR = 1000   TR = 0
提取 1000 * 0.1ms
LRT                 TR = 1001   TS = 1000
                                     1001 * 10ms   1000 * 0.01ms
                                     10010ms + 10ms + 100ms ≈ 10s

第二步 : 通过非聚簇索引IDATE访问INVOICE表

索引 IDATE          TR = 1      TS = 20000
表   CUST           TR = 20000  TS = 0
提取 20000 * 0.1ms
LRT                 TR = 20001   TS = 20000
                                     20001 * 10ms   20000 * 0.01ms
                                     200010ms + 200ms + 2000ms ≈ 200s

第三步 : 合并和FETCH结果行

在读取行的过程中,所需要的行会被拷贝到两张临时表中。这一过程的开销很容易被一开始的访问过程所吸收。两张临时表都不是按照连接列的顺序排序的,因此将不得不对其进行排序。排序的成本依旧是每行0.01ms。最终两张表将被合并,时间成本同样是每行0.01ms。因此

为CUST表和INVOICE表
创建临时表         0ms
对客户数据排序     1000 * 0.01ms = 0.01s
对发票数据排序     20000 * 0.01ms = 0.2s
合并              (1000 + 20000) * 0.01ms ≈ 0.2s
提取              1000 * 20 = 20000 * 0.1ms = 2s (不明白这里的1000*20是怎算的,暂且当做每个用户平均20条INVOICE)

本地响应时间
10s + 200s + 2s ≈ 3.5min

哈希连接

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

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

根据QUBE,无论采用合并扫描还是哈希连接的方式,最初的表或索引扫描都是相同的,任何从哈希计算中获得的时间收益都很难量化,因此,为了避免不必要的复杂性,我们将使用在合并扫描中所用的方法来计算哈希连接的开销。

因此,在将来我们没必要区分合并扫描连接和哈希连接,除非你希望在最后一步(使用散列过程)中节省时间。后续我们将使用术语MS/HJ来指代这两者中的任何一个过程。

现在,我们回到案例学习,并重新考虑一下程序C

程序C : 由优化器选择MS/HJ(在现有索引条件下)

SQL 8.15

DECLARE CURSORJ CURSOR FOR
SELECT CNAME, CTYPE, INO, IEUR
FROM CUST, INVOICE
WHERE IEUR > :IEUR
      AND
      CCTRY = = :CCTRY
      AND
      CUST.CNO = INVOICE.CNO
ORDER BY IEUR DESC

OPEN CURSORJ
      FETCH CURSORJ      while IEUR > :IEUR and CCTRY = :CCTRY
CLOSE CURSORJ

CUST : 1000000行数据
INVOICE : 20000000行数据
FF (CCTRY = :CCTRY) = 10%
每个用户20张发票

第一步 : 全表扫描CUST表

表   CUST           TR = 1        TS = 1000000
LRT                 TR = 1        TS = 1000000
                                  1 * 10ms   1000000 * 0.01ms
                                  10ms + 10000ms ≈ 20s

第二步 : 全表扫描INVOICE表

表   INVOICE           TR = 1        TS = 20000000
LRT                    TR = 1        TS = 20000000
                                     1 * 10ms   20000000 * 0.01ms
                                     10ms + 200000ms ≈ 200s

第三步 : 进行合并/哈希操作并FETCH结果行

首先,必须对从第一步中得到的100000行结果数据按CNO进行排序。同样,也必须对第2步中得到的20000行结果数据按CNO进行排序。然后,再将这两个排好序的的表进行合并。在排序合并的过程中,在每一行结果数据上所花费的时间成本大致是0.01ms :
排序和合并/哈希 2(100000 + 20000) * 0.01ms ≈ 2.4s
提取 2000 * 0.1ms = 0.2s (这个2000又是怎么来的,我去。。。,暂且理解为 : 200000(第二步得到的结果集) x 10%(CCTRY字段的过滤因子))

结论 : 在现有索引条件下进行MS/HJ

在现有索引条件下,使用MS/HJ所花费的时间仅为嵌套循环查询的三分之一,当然,在最差输入的情况下这还不够快。同往常一样,现在我们可以开始考虑设计最佳索引了,也许该从设计和评估理想索引开始。

理想索引

SQL 8.15

DECLARE CURSORJ CURSOR FOR
SELECT CNAME, CTYPE, INO, IEUR
FROM CUST, INVOICE
WHERE IEUR > :IEUR
      AND
      CCTRY = = :CCTRY
      AND
      CUST.CNO = INVOICE.CNO
ORDER BY IEUR DESC

OPEN CURSORJ
      FETCH CURSORJ      while IEUR > :IEUR and CCTRY = :CCTRY
CLOSE CURSORJ

对于CUST表的索引访问过程而言,理想索引候选A为(CCTRY,CNO,CNAME,CTYPE)。这是一个三星索引,这一访问路径保证了结果行是按连接字段排序的,因此结果行不需要再进行排序。对于INVOICE表的访问的候选索引A为(IEUR DESC, CNO, INO)。这个索引只有两颗星,因为范围谓词意味着无法按CNO字段的顺序提供结果行。候选索引B是(CNO,IEUR DESC,INO),但如此一来,整张INVOICE表都将参与合并/哈希过程了,这将导致对如此大量的索引行(FF为0.1%)扫描1000次。严格来说,在理想索引上,IEUR列并不是必须按降序排列的。与之前提到的原因相同,我们还是假定该列在索引上是一个降序键。

第一步 : 访问索引(CCTRY, CNO, CNAME, CTYPE)

索引   CCTRY, CNO, CNAME, CTYPE           TR = 1        TS = 100000
LRT                                       TR = 1        TS = 100000
                                          1 * 10ms   100000 * 0.01ms
                                          10ms + 1s ≈ 1s

第二步 : 访问索引(IEUR DESC, CNO, INO)

索引   IEUR DESC, CNO, INO           TR = 1        TS = 20000
LRT                                  TR = 1        TS = 20000
                                     1 * 10ms   20000 * 0.01ms
                                          10ms + 200s ≈ 0.2s

第三步 : 进行合并/哈希合并并FETCH结果行

若第一步和第二步需要将结果集按CNO的顺序进行排序,那么第三步的时间成本将会是前两步扫描时间的两倍。
排序及合并/哈希 2 x (100000 + 20000) * 0.01ms ≈ 2.4s

然而,外层扫描的确是按所要求的的顺序提供的结果行,因此,最终的成本被大大降低了
排序及合并/哈希 2 x (20000) * 0.01ms ≈ 0.4s
提取 2000 x 0.1ms = 0.2s

注意,正是因为第一列CCTRY是等值谓词才能降低这一成本,若第一列为范围谓词,则索引扫描将无法按CNO的顺序访问行。

本地响应时间

在最差输入情况下,此访问路径的本地响应时间是这三者的总和
1s + 0.2s + 0.6s = 1.8s

结论 : 在理想索引条件下采用MS/HJ

我们将合并扫描的结果也添加到了嵌套循环的对比结果中

类型程序A程序B/C NLJ程序C MS/HJ
理想索引35min10min3.5min
理想索引17min3.5min1.8s
理想索引,理想程序(+),多屏结果数据-2s-
理想索引,理想程序(+),单屏结果数据(FF缺陷)-3.5min-
BJQ理想索引,理想程序(+),单屏结果数据(FF缺陷)-0.2s-

结果很清楚的显示,在理想索引条件下使用MS/HJ是最好的访问路径,他不需要我们将策略改为只显示一屏数据或使用BJQ方法。采用这一方式能获得很好性能的原因有两个

  1. 它避免了我们在前台循环连接中遇到的大问题---对内层表或其索引的随机访问。
  2. 在当前硬件条件下,顺序访问的速度已经非常快了。

尽管性能有了巨大提升,单近2s的响应时间对于一个在线查询而言也许仍旧有点高。若响应时间不可接受,那么就需要设计一个满足BJQ的嵌套循环连接了。

前台循环连接 VS. MS/HJ及理想索引

嵌套循环连接 VS. MS/HJ

若合适的索引已经存在且结果集不是特别大,则我们比较倾向于选择嵌套循环连接(NLJ)这一技术。当然,所谓的“合适的索引”是指相应的半宽索引,宽索引或理想索引,我们对此已经非常熟悉了。然而,如我们所见,即便是这些设计得相当完美的索引也有可能无法提供好的性能表现,对于内层表(或索引)的大量随机访问会导致大问题。在过去,为了解决这一问题,我们不得不限制结果集的数量,或者运用基础连接问题(NJQ)来保证所有本地谓词都指向同一张表,但也有可能这两者都无法令人满意。

硬件对于顺序访问的性能和对随机访问的性能不是一个量级的。按照QUBE中的TS = 0.01ms和TR = 10ms来看,随机访问一行所花费的时间用于顺序访问可以访问1000行。

这一点导致,如今优化器更倾向于选择顺序扫描(相对于随机访问)。

当然,如何访问一张表或一个索引,已经应该使用哪一种连接技术,这些是优化器的工作,但是,这些问题同样也会对索引设计过程造成影响,因此,我们需要意识到这一点。

循环嵌套连接 VS. 理想索引

不同类型连接的理想索引不会差别太大。NLJ中外层表上的理想索引与MS/HJ中表上的索引是相同的---一个能够提供窄索引片的宽索引。唯一的区别可能存在于NLJ中的内层表上。连接列应当是索引的一部分,且索引最好是宽索引,从而使其能够提供一个非常窄的索引片且不会引入过多的TR。

另外,若使用MS,如果访问路径已按连接的顺序提供表行,那么对外层表的排序可能就不需要了,因此,连接谓词应当包含在索引中,放在任一等值谓词后面。无需创建,排序并访问工作文件,由此锁节省的时间也许会相当可观。

我们知道,在HJ中较小的结果集会被保存在一张临时表中,根据连接列进行哈希。随后外层表(或索引片)被扫描,并对每个满足本地谓词的记录进行哈希计算,与临时表中的记录做匹配。

连接两张以上的表

假设有三张表
INVOICE : 20000000行记录,FF(0.1%),NLR = 20000
INVOICE_ITEM : 50000000行记录,NLR = 1000
ITEM : 100000行记录,FF(1%),NLR = 50000000
INVOICE与INVOICE_ITEM用INO字段关联
INVOICE_ITEM与ITEM用ITEMNO关联

当连接涉及的表多余两张时,有些连接可能并不是基于常规列(如主键及外键)进行连接的,这并不罕见。表INVOICE和表ITEM只能通过笛卡尔连接的方式进行连接,这意味着创建一张包含这两张表中所有本地行组合的临时表。在假设过滤因子条件下,临时表中交会由20000 x 1000 = 20000000行(本地谓词没有在图中展示)。由于这是一个代价较高的过程,根据NLR(本地行的数量)所得出的表访问顺序---ITEM, INVOICE, INVOICE_ITEM---可能并不是效率最高的。

唯一可能避免笛卡尔连接的方法。所有的访问操作都仅需要访问索引。

为表访问顺序(INVOICE, INVOICE_ITEM, ITEM)所设计的索引提供了一个比原方案更好的访问路径。然而,根据QUBE,70000次随机访问将花费70000 x 10ms = 700s。若这无法令人满意,那么就必须将这些谓词拷贝至INVOICE_ITEM表上。于是,当有一个包含所有谓词列的索引时,随机访问次数可能减少至1000---这是另一个说明了BJQ重要性的例子。

MS/HJ还能提供更好的性能支持吗?INVOICE_ITEM表上没有本地谓词,因此若使用MS/HJ,第一步需要进行50000000次顺序访问,根据QUBE,这将耗费50000000 x 0.01ms = 500s。

现在似乎采用这种方式更好 : 首先使用嵌套循环的方式连接方式链接ITEM表和INVOICE_ITEM表,然后在使用MS/HJ的方式连接中间结果集和INVOICE表。于是,INVOICE表上的理想索引将变为由(IEUR...)作为前导列了。

第一步 : 连接ITEM表和INVOICE_ITEM表(NL)

索引(ITEMT, ...) TR = 1 TS = 0.01 x 100000 = 1000
索引(ITEMNO, ...) TR = 1000 TS = 0.01 x 50000000 = 500000
LRT = 1001 x 10ms + 501000 x 0.01ms ≈ 15s
中间结果集包含500000行

第二步 : 连接中间结果集和INVOICE表(MS/HJ)

中间结果集 TR = 1 TS = 500000
索引(IEUR...) TR = 1 TS = 0.001 x 20000000 = 20000

LRT = 2 x 10ms + 520000 x 0.01ms ≈ 5s
由于使用的是合并扫描的方式,所以必须对520000行进行排序和合并
2 x 520000 x 0.01ms ≈ 10s

哈希连接可能更快,因为20000行这一较小的结果集能保存在内存中。

本地响应时间

在这些索引条件下,合并扫描的总响应时间为30s,哈希连接的总响应时间在20s ~ 30s之间---相较嵌套循环(12min),这是一个很大的改善。

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

模糊的索引设计

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

根据假定的访问路径创建索引能够增加优化器选择这一访问路径的可能性。在理想索引条件下,如果另一个访问路径能够有更好的性能表现,那么保持原有假定并为其设计索引,比不基于任何假设地随机设计索引更有可能时间段的响应时间。

优化器可能选择错误的表访问路径

一个涉及多张表的SELECT语句比一个仅涉及一张表的语句有更多的可选访问路径。由于优化器错误的过滤因子估算导致的错误访问顺序及错误的链接方法并不罕见。另外,对于单表SELECT,访问路径可能对于大多数平均输入是最优的,而对于最差输入是性能较差的。但对于连接查询,不合适的访问路径通常会导致巨大的影响。不过幸运的是,现今已经有很多方法可以协助优化器进行访问路径选择了---比如通过使用提示。

乐观的表设计

本章一直在讨论的程序更小时一个数据仓库的查询,而实际上,由两张大表上的本地谓词导致此类问题在操作型应用中也很普遍。在最差输入下,即使是最佳访问路径,所耗费的时间也太长了。对于这类问题,索引设计者,应用程序开发组及优化器可能都没有错。甚至将该连接转换为两个游标都无法解决这类问题,而且CPU的时间可能还会因此上涨,因为SQL调用的次数变多了。这类问题可能应当归咎于那些坚信表中不应该有冗余数据的专家。无论在设计表还是编写连接语句时都应该时时刻刻想到基础连接问题。关于冗余数据带来的问题将在后面讨论。

为子查询设计索引

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

为UNION语句设计索引

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

对于表设计的思考

前面提到,许多数据库专家认为在表中有冗余数据总是不合适的。我们还看到,在设计表时需要牢记哪些与BJQ相关的问题。现在来讨论一下会影响SQL性能的表设计问题。

冗余数据

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

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

向下反范式化

在我们的案例研究中,我们引入向下反范式化来消除大量对内层表(CUST表)索引的TR。该列CCTRY添加至INVOICE表是一个看起来不错的方案。

由此带来的额外存储成本是较低的,而且当一个顾客搬去另一个国家时,更新INVOICE表的CCTRY列也不是一个大问题。如果一个客户的INVOICE表行是互相临近的(索引(CNO)是聚簇索引),那么这一更新将涉及一次随机表访问,以及几次索引访问,用于移动索引(CCTRY, IEUR, INO, CNO)上的一些行。当然,如果一个大客户有1000张发票,那么这不会经常发生(大客户不会经常搬去其他国家),所以这也许是可以接收的。不过,总体而言,当我们考虑引入向下反范式化时,需要预测一下冗余字段(在我们的例子中是CCTRY)更新时可能会导致最差情况下的索引随机访问次数。

向上反范式化

假设案例中的排序需求为ORDER BY CNAME, CNO而非ORDER BY IEUR DESC。此时,若将CUST表作为嵌套循环的外层表便能避免一次排序了。于是,这一访问路径就有可能使一个只做20次FETCH的事务(只提取一屏数据)变得很快了。然而,如果没有对数据进行冗余,假设在这一百万客户中只有0.1%的客户有至少一张大额发票,那么为了再INVOICE上找到一行满足条件的记录,就可能涉及到1000次索引随机访问---根据QUBE,只需要花费10s。于是,我们需要考虑向上反范式化。以减少为了判断客户是否有大额发票而进行的无用随机访问次数。

最直接的方法是在CUST表上添加一个新的列CLARGE,并在SQL上添加相应的谓词条件,若CLARGE = 1,则该客户拥有至少一张大额发票。显然,这是一个笨拙的方法,原因有二 :

  1. 当对INVOICE表的数据进行删除或插入操作时,维护CLARGE列的工作并不简单。
  2. 修改CLARGE的定义将带来大规模的批处理任务。

我们可以往CUST表上添加CTOTAL_IEUR列,即每个客户的发票总额,并在SQL上添加响应的谓词条件。这一方式能避免上述的两个问题,但同时也 引入了更高的维护代价 : INVOICE表每次INSERT及DELETE操作都将引入两次随机访问,一次是对于CUST表的,另一次是对于包含CTOTAL_IEUR列的索引的。这一方案能够给避免一部分对INVOICE表上索引的无用访问,即那些发票总额小于等于:IEUR的客户;而对于那些发票总额大于:IEUR的客户,他们可能有一张或多张大额发票,但也可能只有一些小额发票。

我们还可以向CUST表添加CMAX_IEUR列,即每个客户的发票中最大的IEUR值,这样可以完全消除对INVOICE表的索引的无用访问。维护成本在这一方案中也将有所降低,因为只有那些会影响CMAX_IEUR值的发票的插入,删除操作才会导致该列的更新。再次需要注意的是,对CUST表上索引的访问还是无法避免的,因为需要获取该客户最大的IEUR值。

最佳方案是添加CHWM_IEUR列,一个高水位标记,一个客户最佳拥有过的最大额的IEUR,但不一定仍然拥有。在此,我们尝试在维护的成本和收益之间达到一种平衡。CHWH_IEUR不一定要非常精确,但他需要足够大,大到能帮助我们找到所有的大额发票。而如果他的值过高,那么INVOICE表的索引就会被不必要的访问多次。频繁地更新CHWM_IEUR值将导致高昂的成本,所以对于删除操作而言,只需要通过一个CHWM_IEUR的更新程序,定期对高水位标记进行更新即可。对于插入操作而言,仅当客户的新发票的IEUR值大于其余发票时,CHWM_IEUR列才需要被更新,要完成这一过程,只需在每次INVOICE表INSERT时,对CUST表上的索引进行一次随机访问以比较CHWM_IEUR的值即可。

当更新完所有的高水位标记后,平均每次FETCH操作将需要对第一个索引进行1000次顺序访问,再对第二个索引只进行一次访问,通常是随机访问。于是,对于一个只提取20行的事务而言,根据QUBE算法,响应时间应为 :
20 x 10ms + 20000 x 0.01ms + 20 x 0.1ms ≈ 0.4s

反范式化的成本

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

嵌套循环连接和MS/HJ VS. 反范式化

许多数据库专家不愿意将冗余列添加至事务型表上,这是可以理解的。反范式化不仅仅是查询速度和更新速度之间的一个权衡,在某种程度上,他还是性能和数据完整性之间的一个权衡,即使在使用触发器来维护冗余数据的情况下。然而,当嵌套循环引入了过多的随机访问,且MS/HJ耗费了过多的CPU时间时,反范式化可能成为唯一的选择。尽管如此,在决定采用这一极端的方案之前,我们必须确保所有能够避免这一方案的方法都已经考虑过了。这意味着我们需要确保考虑过为NLJ或MS/HJ设计最佳的宽索引,且将所有可能导致问题的索引保留在内存中;购买更多的内存来缓存索引,或购买能提供更快顺序读取速度的磁盘,这可能会将使用反范式化的临界值抬得更高。

这毫无疑问是一个艰难的权衡。我们不希望给大家一个印象,即非BJQ的查询通常能够通过更快的顺序扫描来解决。在我们的案例研究中,性能数据可能的确反映出这种情况,但在实际生活中,数据表通常更大,通常包含1亿行以上的数据,且伴有很高的事务频率,另外,CPU时间也是一个非常重要的考量点。

无意识的表设计

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

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

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

考虑一个根据某CNO值来查询一些基础字段和公司相关字段的语句。若至少有一张CUST表,那么可以通过一次随机访问来做到;若有多张表,那么至少也要进行两次随机访问。二者的差别可能不止这些,考虑SQL 8.18中所示的查询 :
SQL 8.18

SELECT FNAME, CNO
FROM CUST
WHERE LNAME = :LNAME
      AND
      CITY = :CITY
ORDER BY FNAME

索引(CITY, LNAME)可能无法提供足够的性能表现,不过我们知道如何仅通过在索引上添加列来使查询变得很快。但是如果是两张表进行连接,且是非BJQ连接。我们已经知道将导致什么 : 要么导致大量对内层表(或索引)的无用随机访问,要么由于使用MS/HJ而导致高CPU时间(可能还有排序)。又或者,我们可能需要引入向下反范式化,例如,通过将CITY字段拷贝至CUST_PRIVATE表。

在决定拆分一张表之前,需要先权衡以下受益。CUST表所需的磁盘空间为1.5 x 1000000行 x 1000字节/行 = 1.5GB。若磁盘空间每月的成本为50美元每GB,那么拆分CUST表所节省的存储成本将小于每月75美元。

有时创建一张独立的表,如CUST_DEATH,是由于一些程序只对死亡数据感兴趣。处理这样一张表会非常快,但这同样可以通过在CUST表上设计一个好的索引来实现。

通常来说,一个数据库包含太多的表仅仅是因为这样看起来很合理,或者仅仅是简单的把对象转换为表而没有进行任何性能上的考虑。一旦应用投入生产,这类错误就很难被纠正了。

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

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

练习

练习1

SQL

SELECT A2, B1, B2
FROM A, B
WHERE A1 = :A1
      AND
      B1 > :B1
      AND
      A.AK = B.AK

相关信息

表A : 10000000行记录
表B : 50000000行记录
表A有索引(AK),该索引为聚集索引
表B有索引(BK)
表B有索引(AK)
表A字段A1的过滤因子为 1%
表B字段B1的过滤因子为 0.001%

8.1 评估所示连接的响应时间,过滤因子使用给定的值

现状

嵌套循环连接
表A作为内层表
第一步 : 全表扫描A
表   A              TR = 1   TS = 10000000
提取 100000 * 0.1ms
LRT                 TR = 1   TS = 1000
                    1 * 10ms   10000000* 0.01ms
                    10ms + 100s + 10s ≈ 110s
第二步 : 通过索引访问B

平均A表一条记录对应5条B表的记录

索引 AK             TR = 100000      TS = 5 x 100000
表   B              TR = 100000      TS = 5 x 100000
提取 500 * 0.1ms
LRT                 TR = 200000      TS = 1000000
                    200000 * 10ms    1000000 * 0.01ms
                    2000s + 10s + 50ms ≈ 2010s
响应时间

110s + 2010s = 2120s

表B作为内层表
第一步 : 全表扫描B
表   B              TR = 1   TS = 50000000
提取 500 * 0.1ms
LRT                 TR = 1   TS = 50000000
                    1 * 10ms   50000000 * 0.01ms
                    10ms + 500s + 50ms ≈ 500s
第二步 : 全表扫描A

B表一条记录对应1条B表的记录

索引 AK             TR = 500         TS = 0
表   B              TR = 500         TS = 0
提取 500 * 0.1ms
LRT                 TR = 1000        TS = 0
                    1000 * 10ms      0 * 0.01ms
                    10s + 0s + 50ms ≈ 10s
响应时间

500s + 10s = 510s

合并扫扫描连接(MS/HJ)
第一步 : 全表扫描A
表   A              TR = 1   TS = 10000000
LRT                 TR = 1   TS = 1000
                    1 * 10ms   10000000* 0.01ms
                    10ms + 100s ≈ 110s
第二步 : 读取B表记录
表   B               TR = 1           TS = 50000000
LRT                  TR = 1           TS = 50000000
                     1 * 10ms  50000000 * 0.01ms
                     10ms + 500s ≈ 500s
第三步 : 合并和FETCH结果行

对A表排序 100000 x 0.01ms = 1s
对B表排序 500 x 0.01ms = 5ms
合并 (500 + 100000) * 0.01 ≈ 1s
提取 500 x 0.1ms = 50ms

本地响应时间

使用全表扫描 : 110s + 500s = 610s

8.2 在不添加冗余字段的情况下,为该连接设计最佳索引并评估响应时间。

优化后最佳索引

使用合并扫描连接的最佳索引如下

表A添加索引(A1, AK, A2)
表B添加索引(B1, AK, B2)

第一步 : 使用索引(A1, AK, A2)扫描A表
索引   A1, AK, A2    TR = 1   TS = 100000
LRT                  TR = 1   TS = 100000
                     1 * 10ms   100000 * 0.01ms
                     10ms + 1s ≈ 1s
第二步 : 使用索引(B1, AK, B2)扫描B表
表   B1, AK, B2      TR = 1           TS = 500
LRT                  TR = 1           TS = 500
                     1 * 10ms  500 * 0.01ms
                     10ms + 5ms ≈ 15ms
第三步 : 合并和FETCH结果行

对A表排序 0 x 0.01ms = 0s,无需排序
对B表排序 0 x 0.01ms = 0ms,无需排序
合并 (500 + 100000) * 0.01 ≈ 1s
提取 500 x 0.1ms = 50ms

本地响应时间

1s + 15ms + 1s ≈ 2s

使用嵌套循环连接的最佳索引如下

B表添加索引 B1, B2, AK
表B作为内层表

第一步 : 索引扫描B
索引   B1, B2, AK    TR = 1   TS = 500
提取   500 * 0.1ms
LRT                 TR = 1   TS = 500
                    1 * 10ms   500 * 0.01ms
                    10ms + 5ms + 50ms ≈ 0.5s
第二步 : 全表扫描A

B表一条记录对应1条B表的记录

索引 AK             TR = 500         TS = 0
表   B              TR = 500         TS = 0
提取 500 * 0.1ms
LRT                 TR = 1000        TS = 0
                    1000 * 10ms      0 * 0.01ms
                    10s + 0s + 50ms ≈ 10s
响应时间

0.5s + 10s = 10.5s

练习2

表CUST : 1000000行记录
表C1 : 1000行记录
表C2 : 10000行记录
表C3 : 3000行记录
CNO为表CUST的主键索引,且为聚簇索引
C1PK为表CUST的索引,且为表C1的主键索引,且为C1的聚簇索引
C2PK为表CUST的索引,且为表C2的主键索引,且为C2的聚簇索引
C3PK为表CUST的索引,且为表C3的主键索引,且为C3的聚簇索引

8.3 CUST表中有三个指向代码表的外键。评估在嵌套循环和最佳表访问顺序下,下面四张表连接的本地响应时间

第一步 : 全表扫描CUST

表     CUST            TR = 1     TS = 1000000
提取   1000000 * 0.1ms
LRT                    TR = 1     TS = 1000000
                       1 * 10ms   1000000 * 0.01ms
                       10ms + 10s + 100s ≈ 110s

第二步 : 索引扫描C1

索引 C1PK             TR = 1000000         TS = 0
表   C1               TR = 1000000         TS = 0
提取 1000000 * 0.1ms
LRT                 TR = 1000        TS = 0
                    2000000 * 10ms      0 * 0.01ms
                    20000s + 0s + 100s ≈ 20100s

第三步 : 索引扫描C2

索引 C2PK             TR = 1000000         TS = 0
表   C2               TR = 1000000         TS = 0
提取 1000000 * 0.1ms
LRT                 TR = 1000        TS = 0
                    2000000 * 10ms      0 * 0.01ms
                    20000s + 0s + 100s ≈ 20100s

第四步 : 索引扫描C3

索引 C3PK             TR = 1000000         TS = 0
表   C3               TR = 1000000         TS = 0
提取 1000000 * 0.1ms
LRT                   TR = 1000        TS = 0
                      2000000 * 10ms      0 * 0.01ms
                      20000s + 0s + 100s ≈ 20100s

响应时间

20100s * 3 + 110s = 60410s

8.4 假设SQL 8.19在一个批处理任务中会被执行一百万次。我们需要改进索引吗?调优的空间由多大?有其他方法可以用来提升该SELECT语句的性能吗?

SQL 8.19

SELECT CNAME, C1TEXT, C2TEXT, C3TEXT
FROM CUST, C1, C2, C3
WHERE CUST.CNO = :CNO
      AND
      CUST.C1PK = C1.C1PK
      AND
      CUST.C2PK = C2.C2PK
      AND
      CUST.C3PK = C1.C3PK

可以加如下索引进行优化
CUST表加索引(CNO, CNAME)
C1表加索引(C1PK, C1TEXT)
C2表加索引(C2PK, C2TEXT)
C3表加索引(C3PK, C3TEXT)

优化前和优化后的QUBE如下,优化前为80ms,优化后为40ms,预计可以可以为这个查询

优化前QUBE

第一步 : 扫描CUST表索引(CNO)
索引    CNO, CNAME        TR = 1     TS = 0
表                        TR = 1     TS = 0
提取    1 * 0.1ms
LRT                       TR = 2     TS = 0
                          2 * 10ms   0 * 0.01ms
                          20ms + 0s + 0.1ms ≈ 20ms
第二步 : 扫描C1表索引(C1PK)
索引 C1PK             TR = 1         TS = 0
表                    TR = 1         TS = 0
提取 1 * 0.1ms
LRT                  TR = 2        TS = 0
                     2 * 10ms      0 * 0.01ms
                     10ms + 0s + 0.1s ≈ 20ms
第三步 : 扫描C2表索引(C2PK)
索引 C2PK             TR = 1         TS = 0
表                    TR = 1         TS = 0
提取 1 * 0.1ms
LRT                  TR = 1        TS = 0
                     2 * 10ms      0 * 0.01ms
                     10ms + 0s + 0.1s ≈ 20ms
第四步 : 扫描C3表索引(C3PK)
索引 C3PK             TR = 1         TS = 0
表                    TR = 1         TS = 0
提取 1 * 0.1ms
LRT                  TR = 1        TS = 0
                     2 * 10ms      0 * 0.01ms
                     10ms + 0s + 0.1s ≈ 20ms
响应时间

20ms * 4 = 80ms

优化后QUBE

第一步 : 扫描CUST表索引(CNO, CNAME)
索引    CNO, CNAME        TR = 1     TS = 0
提取    1 * 0.1ms
LRT                       TR = 1     TS = 0
                          1 * 10ms   0 * 0.01ms
                          10ms + 0s + 0.1ms ≈ 10ms
第二步 : 扫描C1表索引(C1PK, C1TEXT)
索引 C1PK             TR = 1         TS = 0
提取 1 * 0.1ms
LRT                  TR = 1        TS = 0
                     1 * 10ms      0 * 0.01ms
                     10ms + 0s + 0.1s ≈ 10ms
第三步 : 扫描C2表索引(C2PK, C2TEXT)
索引 C2PK             TR = 1         TS = 0
提取 1 * 0.1ms
LRT                  TR = 1        TS = 0
                     1 * 10ms      0 * 0.01ms
                     10ms + 0s + 0.1s ≈ 10ms
第四步 : 扫描C3表索引(C3PK, C3TEXT)
索引 C3PK             TR = 1         TS = 0
提取 1 * 0.1ms
LRT                  TR = 1        TS = 0
                     1 * 10ms      0 * 0.01ms
                     10ms + 0s + 0.1s ≈ 10ms
响应时间

10ms * 4 = 40ms

使用反范式法优化

可以把C1,C2,C3的C1TEXT,C2TEXT,C3TEXT字段复制一份到CUST表中,QUBE如下

使用反范式法且不增加索引的QUBE
扫描CUST表索引(CNO)
索引    CNO               TR = 1     TS = 0
表                        TR = 1     TS = 0
提取    1 * 0.1ms
LRT                       TR = 2     TS = 0
                          2 * 10ms   0 * 0.01ms
                          20ms + 0s + 0.1ms ≈ 20ms

###### 响应时间
20ms

##### 使用反范式法且增加索引的QUBE
###### 扫描CUST表索引(CNO, CNAME, C1TEXT, C2TEXT, C3TEXT)

索引 CNO, CNAME, C1TEXT, C2TEXT, C3TEXT TR = 1 TS = 0
提取 1 * 0.1ms
LRT TR = 1 TS = 0

                                              1 * 10ms   0 * 0.01ms
                                              10ms + 0s + 0.1ms ≈ 10ms
响应时间

10ms

数据库索引设计与优化04-被动式索引设计

到目前为止,我们讨论的都是相对简单的SQL语句。在我们讨论如关联查询,子查询,合并查询,星型查询和多索引访问时,有必要先讨论一下如何监视SQL,并从被动式响应的角度考虑索引设计中需要考虑的问题。

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

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

在产品投入大规模使用后才对应用的大部分索引进行调优工作,就像是将一个载满乘客的大型客机推下悬崖。这可能会有一个好的结果,但是数据库员工必须做好快速响应的准备。如果没有人在应用开发阶段关注索引设计的话,一些程序可能会在应用投入后变得非常慢。

我们将会讨论在应用投入生产环境后的最初几天需要用到的性能工具和技术。这些工具和技术对于之后能够轻松地调优也是有用的,以在用户觉察之前发现性能问题,或者至少在问题变得令人无法忍受之前发现他们。在这种场景下,我们实际上是主动的而非被动的。

explain描述了所选择的访问路径

识别可疑的访问路径是相当容易的,尤其是当explain的输出结果被存储在表中的情况下,因为这使得获取解决过变得容易。这就是为什么对于优化器选择了可以访问路径的SQL,分析过程通常从索引优化开始。通过explain能够快读发现以下这些性能警示信号。

全表扫描或全索引扫描

对结果集排序

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

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

对于第一种情况,可以通过优化索引来避免,第二种后面再讨论。

通常,排序是没有害处的。例如,某应用可能有以前个不同的查询语句,其中几百个在他们的访问路径中都有一次排序,这几百个语句中的90%可能都有非常出色的性能,排序对其响应时间值贡献了很不明显的一部分。因此,大量错误的警告可能会使这种检查方法有些无用。

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

成本估算

一些数据库管理系统的explain功能显示了优化器对所选访问路径的本地响应时间的估算,或至少显示了对CPU时间的估算。有些产品,如SQL Server 2000,显示了对访问路径中每一步的CPU及I/O时间估值。在一个简单的场景中,可能会有如下几步 :

  1. 检索并读取索引行
  2. 对指针进行排序
  3. 检索并读取表行
  4. 对结果进行排序

经验显示,过分的依赖优化器的成本估算是危险的。毕竟优化器生成成本估算仅仅是为了选择最快的访问路径。优化器生成的估值有时会给出错误的警示信号,而且还不会显示所有的警示信号,但这是一个用起来简单且快速的工具,他使得早期检查称为可能。因此,哪些成本估值异常高的SQL语句--可能是一个新应用中估值最高的前20个语句,应该一一检查一下,很可能不合适的索引使用或优化器问题就能被发现。

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

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

explain是分析优化器问题的一个不可或缺的工具。因为这正是存在的理由,而不仅仅被用于索引设计。就像机场安检人员不仅是在机场检查可疑乘客。

问题制造者和问题受害者

一个涵盖一周中高峰时段的尖刺报告可能包含100多个不同领域模块的数千个尖刺。在应用开发者的些许帮助下,一个数据库专家也许每周分析并修复5-10个模块。由于程序变更或不同用户输入,下一周的尖刺报告可能会显示新的问题模块。为了高效地利用有限的时间,仔细地对所分析的模块排定优先级是很重要的,事务的响应时间及执行频率并不是唯一的评定标准。

我们首先要区分的是问题制造者和受害者。如果一个事务独占了资源(也许是因为使用了不合适的索引),那么会对其他事务造成明显的负面影响,进而导致这些事务也与独占资源的事务一同出现在异常报告中。

问题制造者所使用的资源会被包含进服务时间,而问题受害者会因为需要等待这些资源而受到影响,即排队时间受影响。着手优化的合理方式是考虑如何解决问题制造者导致的问题,而非受害者的问题

有优化空间的问题制造者和无优化空间的问题制造者

在决定将注意力从受害者转移到问题制造者上之后,我们需要区分的第二项就是有优化空间的问题制造者和无优化空间的问题制造者。不过我们可能没有时间去分析所有的问题制造者。有优化空间的问题制造者是指哪些能够通过改进所有来获得大幅性能提升的事务。

有优化空间的问题制造者有两个特征

  1. 磁盘服务时间长。
  2. 磁盘度大多是是对表页的读取。

若在同步读上耗费的时间占了本地响应时间的绝大部分,且有超过100个表页是从磁盘服务器上读取的,那么索引改进很可能会带来不错的效果。同样,如果对于索引页的同步读大于100次也不是一个好消息。

为了减少对索引的随机读次数,可以减少所需访问的索引数量,也可以减少所需访问的表的数量,这可以通过向表添加冗余字段的方式实现。这些改变并不比创建一个新的索引或像现有索引列上添加列更容易或更可控。

关机随机访问有一个例外,就是对一个厚索引片扫描可能会由于叶子页的分裂而变慢。这个文件很容易解决也相对容易避免,将在后面介绍。

有优化空间的问题制造者

分析有优化空间的问题制造者通常会读取许多表页。我们知道有三种读取表页的方式 :

  1. 事务中的随机读(同步读 : SR)
  2. 跳跃式顺序读
  3. 顺序读(顺序预读)

通过分析见此报告,我们能够腿短出有优化空间的问题制造者主要是有用这三种方式中的那种方式读取表页的。

同步读(方式1)不与CPU的时间重叠,应用程序会停下来,等待锁清秋的页从磁盘服务器返回。尖刺报告会将该事务同步读取的页数连同这些同步读的平均等待时间一起显示出来。

异步读(方式2和方式3)是预读取,他的I/O时间与程序所花费的CPU时间是重叠的。在数据库管理系统向磁盘服务器请求后几页的同时,程序任然在处理数据库缓冲池中的页。程序可能会遇到没有页可供处理的情况,也可能不会遇到。如果发生了这种情况,那么这个等待时间会被记录进预读等待的计数器中。如果程序从未与发哦需要等待预读取页的情况,那么CPU时间便决定了程序的性能。于是,在这种情况下,预读等待的值为0.顺序扫描所花费的时间一部分被记录进SQL的CPU时间,一部分被记录进其他等待(对于任何CPU排队来说)。

在当前硬件下,以跳跃式顺序读的方式访问表页时,响应时间可能还是取决于本地响应时间中最主要的组成部分,因为这意味着包含满足条件的页彼此相隔很远。

而以顺序读方式访问表页时,在当前硬件条件下,CPU或I/O时间的主导地位基本各占一半,有时访问每页所花费的CPU时间比I/O时间长一些,有时又短一些。QUBE算法假设,I/O时间与CPU时间中较大者的上线为0.01ms每行。如果I/O时间决定了顺序读的时间,那么顺序扫描所花费的时间就等于尖刺报告中CPU时间与预读等待部分的总和。

许多程序使用上述方式中的两种或三种来访问表页。此时理解尖刺报告就没有那么简单了,不过主要的方法通常也不是那么难推理。访问的表页总数也许能够帮助我们理解报告。访问的表页总数除了同步读次数外,还包括了通过预读读取的页数(方式2和方式3)和缓冲池的命中数(在数据库缓存终止找到的表页数量)。

调优的潜在空间

在投入大量时间分析一个异常事务之前,值得花时间先去评估一下在索引优化之后本地响应时间能降低多少。调优的潜在空间就是指可实现的降低值的上限。

随机读

只读事务的调优潜在空间等同于读取的表页数和同步读的平均时长的乘积。如果通过使用宽索引避免全部表页的读取,那么本地响应时间就能减少以这个量。

跳跃式顺序读

在上述例子中,有些优化器可能会选择跳跃式顺序读。那么数据库管理系统将首先从所有满足条件的索引行中获取指针,然后再根据表页号对指针进行排序。此时,数据库管理系统就有了所有表页排序后的列表,每个表页都至少包含一条符合条件的记录。只有到这时,数据库管理系统才会开始访问表。在这种方式下,访问每个表页的I/O时间自然相对较短,尤其是当一些满足条件的行恰好都在同一个磁轨上时。另外,I/O时间将会与CPU时间重叠,因为数据库管理系统有条件进行预读了。相比同步读,这种方式所节省的时间是非常不确定的,具体取决于读取的页之间的平均距离以及条带的实现方式。这种方式的调优潜在空间即为当前预读等待的值。

顺序读

顺序扫描的响应时间通常取决于CPU时间。

这类问题,我们需要找到一个更窄的索引段或表段的访问路径,以达到调优的目的。

无优化空间的问题制造者

通常来说,对有大量SQL调用(如10000多次)的事务来说,如果CPU时间是本地响应时间的主要组成部分,那么这些事务是很难被优化的。

对于此类事务,调优潜在空间即为能够去除的SQL调用次数乘以每次SQL调用的基本CPU时间(如0.1ms)。

受害者

调用级别的一次监视

假设我们执行了一次高峰时段的跟踪,且基于该时间段内耗费时间的长短生成了最差SQL调用列表。现在,我们将着手处理单次调用而非均值。进一步假设我们所使用的工具对每次调用只提供了4个重要测算,他们是 : 耗费时间(ET),CPU时间(CPU),从磁盘读取的页数(READS)及数据库页的请求数(PR)。数据库页请求在DB2中被称为读取页,在SQL Server中被称为逻辑读,在Oracle中被称为读取或LIO。为了保持所有事物尽可能简单,我们使用一个能反映所有这些含义的简单术语-页请求(PR)。

术语

子集1(包含子集2和子集3) : ET > 200ms 慢查询
子集2(包含子集3) : ET/PR < 10ms 有可能的问题制造者
子集3 : PR / F < 5 有优化空间的问题制造者

从耗费时间(ET)最长的SQL调用开始,为了通过访问路径调优的方式改进响应时间,我们同样应该试着回答之前在LRT级别讨论过的两个问题。

首先,该SQL调用看起来是不是问题制造者?换句话说,过长的耗费时间是不是由于服务时间过长导致的?有几个方法可以回答这个问题。较高的CPU时间或较高的READS值都意味着较长的服务时间,但是,实际上,PR似乎是服务时间最有用的指示器,因为它与CPU和READS都相关,而且在很大程度上是经得起反复校验的,它不受系统负载或预热的影响。

为了识别那些可能是问题制造者的SQL调用,我们应该忽略那些PR值低的调用。如果一个查询耗费了1s且发送了少于100次页请求,那么它可能就是一个受害者。在可能情况下,每次页请求都会造成一次随机读,如果磁盘排队不过分的话,这将花去100 10ms = 1s。而在实际情况中,许多页请求在数据库缓冲池中就会被满足,另一些则会在磁盘服务器的读缓存中被满足。请记住,报告的PR值包含了非叶子索引页,另外,许多页请求是顺序的,100个页请求的期望I/O时间远比1s短得多,CPU时间的期望值也是如此。总而言之,如果一个包含100次页请求的SQL调用被测得的耗费时间是1s,那么可能它所耗费的排队时间(磁盘驱动排队,CPU排队,锁等待或其他等待)比服务时间长。通常,如果一个慢查询所耗费的时间比“页请求数 10ms”,那么这个查询很可能就是受害者。它属于子集1,但不属于子集2。

子集2是可能的问题制造者,它包含了哪些ET/PR时间不是很长的SQL调用,他们不是很可能的或者明显的受害者。然而,子集2可能也包含了许多受害者,比如进行顺序操作的SQL调用(在每页上所耗费的服务时间较短)会由于过度的CPU排序时间而变得比较慢。如果我们像对待LRT级别的尖刺报告那样关注所有的锁等待或磁盘,CPU排队时间,那么我们是能够过滤掉这些受害者中的绝大部分的。但实际情况是我们只有4个值,所以很不幸,子集2可能会很大。这也是为什么第二个问题很重要 : 该SQL调用是不是一个有优化空间的问题制造者?

为了找出有优化空间的问题制造者,即子集3,我们需要判断结果集的行数。如果读取(F)的数量包含在了异常报告中(或者该值很容易被取得),那么我们可以把它作为结果行数的近似值。如果PR / F 大于5,那么这个查询很可能是一个优化空间的问题制造者,因为在好的访问路径下,对每张表的一次典型读取只需一或两次以内的页请求。造成PR / F大于5的原因很可能是有大量无用的随机访问,即许多行被访问后就被丢弃掉了。

子集3包含了由于没有半宽索引而引起大量随机读的查询,这些是优化回报率最高的调用。子集3同样包含一些有好的访问路径SQL调用(如使用宽索引对一个级联进行count查询),但子集中的绝大部分查询可能都存在有趣的访问路径问题。

这些查询应该首先用Basic Question方法分析一下。这样可能立刻揭露出不合适的索引。紧接着下一步是explain一下这些sql调用,看优化器选择了什么路径。这样可能会揭露出一个优化器问题,如一个负复杂谓词(匹配列太少)或者一个较差的过滤因此估算,进而导致错误的索引选择或错误的表访问顺序。

CPU和READS值提供了对访问路径的有效指示器。例如,如果CPU接近ET,那么处理过程大部分是顺序的;如果CPU很低,ET/READS通常与每页的平均I/O时间接近;如果该值明显小于1ms,那么大部分的I/O是顺序的;如果该值为几毫秒,那么大部分I/O可能是随机的。这可能对执行计划所提供的信息进行补充。另外,任何高CPU值的SQL调用(如大于500ms),都可以被认为是一个有趣的问题制造者。

分析过子集3中排在前几位的调用(至少有一次很长ET的调用和那些经常很慢的调用)后,我们再看一下可能的问题制造者子集2中最慢且调用最频繁的SQL调用。我们可能会找到这样的查询 : 即使使用了半宽索引却仍旧很慢,但能够通过一个宽索引大大提高性能的查询。

当时用更好的索引或者调整优化器的方式优化了一些SQL调用后,应该生成一个新的异常报告。索引的改善可能会帮助许多SQL调用,问题制造者及受害者,但是也有可能在新生成的问题列表中出现一些新的访问路径问题-主要是由于系统负载的改变,或者有时是由于索引的改变(幸运的是这并不经常发生)。

按照ET值排序,我们从上往下依次处理列表中的问题,那么要往下处理到第几个问题才能停下来呢?在一个操作系统中,响应时间极少超过1s。那么理想情况下,我们应该检查任何响应时间大于200ms的SQL调用。不幸的是,在实际生活中,我们可能永远做不到如此。有太多的SQL调用需要处理,而可用的时间太少了!

数据库索引设计与优化03-影响索引设计过程的因素

I/O时间估算的验证

在前面我们引入了以下I/O时间 :
随机读取 10ms(页的大小为4KB或8KB)
顺序读取 40MB/s

这些数据是假定系统使用当前硬件并在一个合理的负载下运行时的值。一些系统可能运行的更慢或处理超负荷状态,所以,进行下面这些检验可能是有用的。为此,我们需要建一张表,该表有100万行记录,每行记录的平均长度为400字节。根据假定的顺序I/O时间计算,以顺序I/O读取400字节长度的行所花费的时间为 400byte / 40MB/s = 0.01ms。

于是,进行如下扫描所消耗的时长便是确定的(括号中的数据库是根据在前面使用的估算数据来预测的)

  • 由一个所有行都不满足条件的select查询引起一次全表扫描(1 10ms + 1000000 0.01ms ≈ 10s)
  • 一次涉及1000次fetch调用的索引扫描,使用如(lname,fname)这样的索引,导致1000行索引片扫描和1000次对表的同步读(1000 0.01ms + 1000 10ms = 10ms + 10s ≈ 10s)。

我们有必要以这样的方式进行测量,即保证在程序刚开始的时候,查询所需要的页不在内存或者读缓存中。如果系统运行的相当繁忙,那么两次测量之间间隔几个小时可能就达到这一目的了。

如果测量出的时间比预计的时间长很多,那么便需要明确造成这一后果的主要原因 : 磁盘设备或路径较慢?还是磁盘超负载运行?

无论这些测出的数字是乐观或悲观,作为相对性能指标,他们是有用的。

多个窄索引片

通常情况下,我们为一个select语句设计一个索引(而不是反过来),但有时候为了让数据库管理系统能够以最高效的方式使用一个已经存在的索引,对一个SQL语句进行重新设计也是可取的。因为优化器并不知道一切!

在where子句包含两个范围谓词时,一个完美的优化器能够构造出一个由多个窄索引片组成的访问路径。如下

select cno, fname
from cust
where lname between :lname1 and :lname2
      and
      city between :city1 and :city2
order by fname

因为一个范围谓词是索引匹配过程中的最后一个匹配字段,所以让数据库管理系统读取多个窄索引片(有lname和city共同定义)需要额外的程序逻辑。谓词条件lname between :lname1 and :lname2必须被修改为lname = :lname。这可以通过一个触发器维护的辅助表来完成,该表包含客户表中lname列的所有不同的值。当用户输入字符串JO时,程序便从辅助表中每次读取一个满足条件的lname,并用每个lname值打开下面的sql。

select cno, fname
from cust
where lname = :lname
      and
      city between :city1 and :city2
order by fname

现在,即使是一个没有完美优化器的数据库管理系统也将会从索引(lname, city, fname, cno)中读取多个窄片。响应时间将取决于索引片的数量以及每一个索引片中的行数。

使用如下假设对比这两种选择

  • cust表中有100万行记录
  • lname最坏情况下的过滤因子为1%
  • city最坏情况下的过滤因子为10%

被第一条sql扫描的索引片由10000行索引记录组成(MC = 1;1000000的1%为10000),其中只有10%的city值(1000行)是满足需要的。

同时假设此索引片中有50个不同的lname值,用第二个sql优化过的程序将会读取50个索引片(平均每个索引片由20行记录),这1000行中的每一行都是满足查询条件的city。

根据QUBE(鉴于只是单纯的做比较,我们忽略fetch所带来的时间开销,两个游标的时间开销为)
cursor 1 1 * 10ms + 10000 * 0.01 ≈ 0.1s
cursor 2 50 * (1 * 10ms + 20 * 0.01) ≈ 0.5s

这有些让人吃惊,但却是合理的。顺序处理的确有时比跳跃处理要来得高效,原因是每一次跳跃都可能以为着一次随机访问。当数字不同时,用优化后的sql有可能会快很多。

为了证明最后说的观点,我们来考虑一个场景。该场景有一张更大的表(100000000行记录),且第一个索引列拥有较高的过滤因子。如下

select cno, fname
from cust
where lname between :lname1 and :lname2      FF max 10%
and
city between :city1 and city2      FF max 0.01%
order by fname

结果集的大小将会是0.01% 10% 100000000 = 1000行。假设有 一个索引(lname, city, fname, cno)且lname在1000行结果集中有50个不同的值。现在,简单程序(两个between)的时间花费估算结果(一个宽索引片)为
1 * 10ms + 10000000 * 0.01ms ≈ 100s
然而复杂程序(50个索引片)的估算结果仍旧为
50 * (1 * 10ms + 20 * 0.01ms) ≈ 0.5s

简单就是没(和安全)

使用辅助表来保存lname不同值的解决方案是一个典型的将数据完整性和性能进行折中的例子。理论上,使用一个触发器来维护辅助表是没有数据完整性的风险的。然而,触发器是应用程序,是程序就不会是完美的。当 alan jones的记录从客户端删除且表中还有另一个jones的记录时,是否能完全确定触发器不会同时把jones的记录从辅助表中删除呢?只有当量化估算不这样做性能就无法接受时,我们才考虑采用这样的调整手段。有时,这样的调整方式反而会对性能产生负面影响。

困难谓词

定义 : 如果一个谓词字段不能参与定义索引片,即它无法成为一个匹配谓词,那么我们就说它对优化器而言太困难了。

like谓词

数据库管理系统可能因为like谓词不参与匹配过程而扫描整个索引,那么访问路径将会变得很慢。

所以,只有在已知优化器不会造成问题的前提下,才应该使用谓词like

or操作符和布尔谓词

即使是简单的谓词,如果他们与其他谓词之间为or操作,那么对于优化器而言他们也可能是困难的。这样的谓词只有在多索引访问下才有可能参与定义一个索引片。

下面的例子将明确这一点。假设在table上有一个索引(A, B)
SQL 6.4 A

select A, B, C
FROM TABLE
WHERE A > :A
      AND
      B > :B

SQL 6.4 B

select A, B, C
FROM TABLE
WHERE A > :A
      OR
      B > :B

在SQL 6.4 A中,单个索引片将会别扫描,由谓词A > :A定义,因为他是个范围谓词,所以他是唯一的一个匹配字段。B字段因为索引筛选将会在此次扫描中被检查,如果谓词B > :B不满足条件,则索引条目将会被忽略。

在SQL 6.4 B中,由于OR操作符的存在,数据库管理系统不能只读这一个索引片,因为即使不满足谓词A > :A,谓词B > :B的条件也可能会满足。可行的替代方案有全索引扫描,全表扫描,以及多索引访问(如果存在另一个以字段B开始的索引的话)。

在这个例子中,我们不能责怪优化器。有时候一个拥有复杂where子句的游标可能被拆分为多个带有简单where子句的游标来避免此类问题。大体上,假设一个谓词的判定结果为false,而这时如果不检查其他谓词就不能确定地将一行记录排除在外,那么这类谓词对优化器而言就是太过困难的。在SQL 6.4 B中,仅仅因为不满足谓词A > :A或仅仅因为不满足谓词B >:B是无法排除一行记录的。在SQL 6.4 A中,如果一行记录不满足谓词A > :A,那么该条记录就可以被排除而不必检查它是否满足谓词B > :B。

这样的谓词被称为非布尔谓词(non-Boolean term)或被称为非BT谓词(non-BT)。如果像SQL 6.4 A那样在where子句中只有AND操作符,那么所有简单谓词都是BT谓词,就是好的谓词,因为只要任何一个简单谓词被判定为不满足条件,那么这一行就可以被排除。

总结

除非访问路径是一个多索引扫描,否则只有BT谓词可以参与定义索引片。

我们来考虑一个定义身材高大的男人的where子句
SQL 6.5

where sex = M
      and
      (weight > 90 or height > 190)

只有一个简单谓词sex='M'是BT谓词。如果weight谓词判定为false,hright谓词的判定结果可能为true也可能相反。这两个谓词都无法仅通过自己的判定结果来排除一行记录。

这就是为什么我们在用理想索引设计方法来设计候选索引A和B时提出了这样的结论 : 只将那些对优化器而言足够简单的谓词添加至索引上。对于SQL 6.5而言,在设计方法的第一步中,只有SEX字段可以被用到。

in谓词

谓词col in (:hv1, :hv2 ...)可能会给优化器制造一些麻烦。例如,在DB2 for z/OS V7中,只有一个IN谓词能够被用来做匹配,即能够参与定义索引片,不过参与匹配的IN谓词中的字段不一定是最后一个匹配字段。因此,当理想索引A被选中时,选择性最高的IN谓词的字段应当在第一步就包含进索引。SQL 6.6提供了一个例子。
SQL 6.6

SELECT A, B, C, D, E
FROM TX
WHERE A = :A
      AND
      B IN (:B1, :B2, :B3)      FF = 0...10%
      AND
      C > 1
      AND
      E IN (:E1, :E2, :E3)      FF = 0...1%

下面的候选A中的数字对应于我们在前面描述的步骤

候选A

  1. 挑选出字段A和E作为索引的起始字段
  2. 加上字段C
  3. 无字段
  4. 加上字段B和D

候选索引A为(A, E, C, B, D)或者以下变化形式中的任何一个

  • (A, E, C, D, B)
  • (E, A, C, D, B)
  • (E, A, C, B, D)

对于SQL 6.6而言,所有这些候选索引都满足MC = 3。数据库管理系统读三个索引片(A, E1, C),(A, :E2, C)和(A, :E3, C),而无需使用其他任何特殊的方式。字段B的IN谓词将参与筛选过程。如果需要有4个匹配字段(即9个索引片),那么我们很可能需要把SELECT语句拆分成三个,每个拆分出的语句只有IN谓词字段列表中的一个字段。第一个SELECT语句包含谓词B = :B1,第二个为B = :B2,第三个为B = :B3。这三个select语句可以通过一个union all再结合为一个游标。对这个游标进行explain将显示三次MC = 4。

候选B

IN谓词的字段不应该在第一步就被选择出来,否则这将破坏结果集的顺序要求,从而必须进行一次排序操作了。

过滤因子隐患

贯穿本书,我们关注于最糟糕的场景,这些场景都是在输入值对应于最大过滤因子时出现的。然而,情况并不总是如此,如下
SQL 6.7

SELECT B
FROM TABLE
WHERE A = :A      FF = 1%
      AND 
      C > :C      FF = 0...10%
ORDER BY B
WE WANT 20 ROWS PLEASE

在这个语句中,只要程序获取了20行记录,屏幕将会把数据展示给用户,而不管整个结果集的大小是多少。

为了解释过滤因子对性能的隐式影响,我们来比较一下过滤因此处理两种极端情况下的QUBE结果。第一种极端情况下提供可能的最小结果集,即0行记录;第二种则提供很大的结果集(1000行记录)。这两种场景下使用都使用索引(A,B,C)。两种场景下,匹配字段A都拥有相同的过滤因子,结果集的大小完全取决于字段C。

先考虑下第二种场景,通常我们认为这将带来最糟糕的性能。一次索引匹配扫描(1 MC,只需要扫描索引而无需访问表)将访问一个包含20 * 10行记录的索引片,因为必须扫描10个索引行才能提供出结果集中的一行记录(字段C的FF为10%)

索引      (A, B, C)            TR = 1      TS = 200
表        TABLE                TR = 0      TS = 0
提取      20 * 0.1ms
LRT                            TR = 1      TS = 200
                               1 * 10ms    200 * 0.01ms
                               10ms + 2ms + 20 * 0.1ms ≈ 14ms

在第一种场景下,没有记录满足字段C的谓词条件,所以过滤因子为0%。当然,数据库管理系统必须扫描索引行中的每一行,即1000000的1%才会知道这种情况。

索引      (A, B, C)            TR = 1      TS = 10000
表        TABLE                TR = 0      TS = 0
提取      0 * 0.1ms
LRT                            TR = 1      TS = 10000
                               1 * 10ms    10000 * 0.01ms
                               10ms + 100ms + 0 * 0.1ms ≈ 110ms

很明显,对于整个事务而言,最差场景是结果集为空的场景,或者额需要扫描整个索引片才能得出结果集的场景。更糟糕的是,如果这个案例不能做到值扫描索引或者对应的索引不是聚簇索引,那么就需要进行额外的10000次随机读取,而这将消耗近两分钟时间,结果却是发现没有一行满足条件的数据。

如果索引匹配扫描过程中扫描的是一个更厚的索引片,比如字段A的过滤因子为20%,那么即便只需要扫描一个索引,LRT也将达到2s(200000 * 0.01ms)!当查询结果只需要一屏幕的数据时,满足第一颗星(最小化待扫描的索引片厚度)比满足第二颗星(避免排序)更为重要。

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

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

这个例子满足了所有这三个条件

  • 访问路径中没有排序,因为字段B(Order By字段)紧接在等值谓词字段A后面,并且字段A是索引的第一个字段。
  • 第一屏结果一建立就响应
  • 一个谓词字段(字段C)不参与定义待扫描的索引片

我们应该充分理解这三个条件背后的逻辑

  • 如果条件1和条件2不为真,那么完整的结果集表总是会被数据库管理系统或应用程序(通过进行FETCH操作来物化)。
  • 如果条件3不为真,就不存在索引过滤(因为所有的谓词字段都是匹配字段),索引片中每一个索引行都是满足条件的。即使结果集为空,数据库管理系统也只需要通过一次访问就能判断出这一情况。

过滤因子隐患的例子

在这个例子中,用户在开始查询前首先在一个弹出窗口中选择姓(lname)和城市(city),随后打开SQL 6.8。我们之前分析这个例子时需要的是整个结果集,而在这个例子中,程序发起的FETCH调用不会超过20次,也许刚好够填满一个屏幕。下一个查询事务将显示接下来的20条结果。以此类推。这种方式使程序变得复杂,但当结果集很大时,这种方式提升了第一屏结果的响应速度。和之前一样,我们将最大的过滤因子假设为1%(lname)及10%(city)。
SQL 6.8

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

表上有三个索引 : (CNO)(聚簇索引),(PNO),(LNAME, FNAME)

是否有一个已经存在的或者计划创建的索引,包含了where子句中涉及的字段(一个半宽索引)?

如果我们决定使用索引(LNAME, FNAME),那么问题将严重到何种程度?最糟情况下的QUBE结果将回答这个问题。

当数据库管理系统选择索引(LNAME, FNAME)时,结果行是按照所要求的顺序获取的(ORDER BY FNAME),也就不需要进行排序操作。因此,数据库管理系统不会做早期的物化 : OPEN CURSOR不会引起表访问,不过FETCH操作将会同时对索引和表进行访问,其中的一些FETCH操作会返回结果行,而另外大部分的FETCH操作则不会。

最先发生的两次访问(一次对索引,一次对表)产生了一行结果行记录,因为第一个JONES生活在LONDON。在第一次FETCH调用满足后程序便发起了第二次FETCH调用。下一个JONES并不生活在LONDON,所以没有产生结果行,于是会继续进行更多的对索引及表的访问,知道生活在LONDON的JONES被找到以满足FETCH调用。因为只有10%的用户生活在LONDON,所以平均一个FETCH调用需要检查10个JONES条目--10次索引访问及10次表访问才能将一行记录加入到结果表中。

索引      LNAME, FNAME            TR = 1      TS = 199
表        CUST                    TR = 200    TS = 0
提取      20 * 0.1ms
LRT                               TR = 200      TS = 199
                                  200 * 10ms    199 * 0.01ms
                                  2s + 1.99ms + 20 * 0.1ms ≈ 2s

根据QUBE得出的本地响应时间是2s,也许还是可以接受的。但这就是最糟糕的情况了么?假定过滤因子CITY = :CITY为10%,LANME = :LNAME为1%已经是最大值了。然而,在这个例子中,产生最大结果集的过滤因子值并不是最糟糕的情况,本例是过滤因子陷阱的另一个例子。过滤因子陷阱的三个条件都适用于索引(LNAME, FNAME)进行处理这个游标

  • 访问路径上没有排序
  • 第一屏结果一建立就返回结果
  • 不是所有谓词都参与了定义待扫描的索引片。

因此,为了创建一条“不存在符合条件的用户”的消息,所花费的时间比返回一个大结果集的第一页数据所花费的时间更长。

让我们考虑一种极端的情况,数据库管理系统必须扫描一个最大的索引片,但最终只产生了一个空的结果集。一个城市中,没有任何一个客户的姓是常见的姓,此时数据库管理系统仍旧必须扫描整个索引片,并对每一个索引进行相应表行的检查。

索引      LNAME, FNAME            TR = 1          TS = 1000000 * 1%
表        CUST                    TR = 10000      TS = 0
提取      0 * 0.1ms
LRT                               TR = 10001      TS = 10000
                                  10001 * 10ms    10000 * 0.01ms
                                  100s + 100ms + 0 * 0.1ms ≈ 100s

将近2分钟而不是2秒钟!索引必须要改善,此时我们将再一次面对那个难题 : 是选择刚好够用的最低成本的改造,还是设计一个最佳索引,又或是设计一个折中的方案?

最佳索引

(LNAME, CITY, FNAME, CNO)

索引      LNAME, CITY, FNAME, CNO            TR = 1          TS = 20
表        CUST                               TR = 0          TS = 0
提取      20 * 0.1ms
LRT                                          TR = 1          TS = 20
                                             1 * 10ms        20 * 0.01ms
                                             10ms + 0.2ms + 20 * 0.1ms ≈ 12ms

以上对应的是在最糟糕场景下使用候选A索引的情况 : 至少有20行结果记录。在使用理想索引的情况下,当整个结果集无法显示在一个屏幕时,建立一个有20行记录的结果表需要21次索引访问。使用索引(LNAME, FNAME)与使用索引(LNAME, CITY, FNAME, CNO)的最糟输入相应时间相差约4个数量级。

如果结果集表为空,那么使用这个三星索引只需要一次索引访问就可以判定出来。从定义上能看出,三星索引不满足陷阱发生条件列表中的第三条。

然而不幸的是,一个三星索引意味着额外增加一个索引,因为在现有的索引中,LNAME和FNAME之间增加一个CITY字段可能会对现有程序造成负面影响。

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

在现有索引(LNAME, FNAME)的最后增加谓词字段CITY可以消除绝大多数的表访问,因为在这个简单的场景中,优化器可以进行索引过滤,仅当CITY值符合条件时才读取表行。

索引(LNAME, FNAME, CITY)能够通过BQ测试 : 所有的谓词都在索引中。然而,他仅仅是一星索引。符合条件的的索引行在物理上并不挨在一起(MC仅为1),并且索引不是宽索引。那这个廉价的解决方案是否能提供可接受的响应时间呢?

现在是会用这个索引的游标落入了过滤因子缺陷的范畴。因此我们必须估算使用索引(LNAME, FNAME, CITY)时过滤因子的极限值。其中一个过滤因子将导致这种访问路径下最糟糕的性能。

最大结果集(例如1000行)

FF (LANE = :LNAME) = 1%
FF (CITY = :CITY) = 10%
FF (LANE = :LNAME and CITY = :CITY) = 0.1%

因为CITY的过滤因子为10%,所以每10个索引行满足一次谓词判定CITY = :CITY。所以为了找出一行满足条件的结果记录,平均需要访问10次索引。

索引      LNAME, FNAME, CITY                 TR = 1          TS = 200
表        CUST                               TR = 20          TS = 0
提取      20 * 0.1ms
LRT                                          TR = 1          TS = 200
                                             21 * 10ms        200 * 0.01ms
                                             210ms + 2ms + 20 * 0.1ms ≈ 214ms

空结果集

FF (LANE = :LNAME) = 1%
FF (CITY = :CITY) = 0%
FF (LANE = :LNAME and CITY = :CITY) = 1%

索引      LNAME, FNAME, CITY                 TR = 1           TS = 10000
表        CUST                               TR = 0           TS = 0
提取      0 * 0.1ms
LRT                                          TR = 1          TS = 10000
                                             1 * 10ms        10000 * 0.01ms
                                             10ms + 100ms + 0 * 0.1ms ≈ 110ms

宽索引(只需访问索引)

向上述半宽再添加一个字段,使得索引变宽 : (LNAME, FNAME, CITY, CNO)

最大结果集(例如1000行)

索引      LNAME, FNAME, CITY, CNO                 TR = 1          TS = 200
表        CUST                                    TR = 0          TS = 0
提取      20 * 0.1ms
LRT                                               TR = 1          TS = 200
                                                  1 * 10ms        200 * 0.01ms
                                                  10ms + 2ms + 20 * 0.1ms ≈ 14ms

空结果集

索引      LNAME, FNAME, CITY, CNO                 TR = 1           TS = 10000
表        CUST                                    TR = 0           TS = 0
提取      0 * 0.1ms
LRT                                               TR = 1          TS = 10000
                                                  1 * 10ms        10000 * 0.01ms
                                                  10ms + 100ms + 0 * 0.1ms ≈ 110ms

在空的结果集的场景下,本地响应时间保持在0.1s。从一个多屏结果集中产生一个屏幕结果集的事务现在变得非常快,因为不再需要对表进行20次TR了。

总结

  1. 性能最差的场景取决于使用的索引

    • 对于原始索引而言,在结果集为空时性能最差(最常见的LNAME减伤最不常见的CITY)
    • 对于半宽索引而言,虽然我们的例子中是结果集表最大时性能最差,但性能最差的场景可能是这两者(结果集为空和结果集表最大)中的任何一个,这取决于表访问和索引片扫描的相对成本。(根据QUEB)20次TR所耗费的是时间(200ms)等于20000次TS所耗费的时间(200ms)。若每屏的行数减少,或索引片更厚,那么结果集为空就可能称为性能最差的场景。
    • 对于宽索引而言,结果集为空时性能最差。
    • 对于三星索引而言,结果集最大时性能最差(结果集为空时只需要进行一次索引访问)。
  2. 原始索引在结果集为空时(而不是结果集最大时)称为一个灾难。这是因为它需要进行大量的表访问来校验CITY字段。
  3. 半宽索引及宽索引都能提供还不错的性能,即使是在结果集为空的情况。两个索引都避免了不必要的表访问,并且索引片扫描的代价也相对较小。随着由字段LNAME定义的索引片的数据增长,本地响应时间的增长也相对缓慢。如果一个公司拥有很多来自South Korea的顾客,那么有一天LEE的索引片可能包含100000索引行。在结果集这么大的情况下,这两个索引依旧能够提供比较不错的响应时间;最差的输入值所带来的响应时间将会是1s(100000*0.01ms)。
  4. 相比使用半宽索引,宽索引的优势在于避免了前20行结果的表访问。
  5. 尽管使用三星索引可能会得到一些好处,尤其是在结果集为空的情况下,但这一好处并不明显,并且会引入由于添加了一个新索引而产生的额外负载。
  6. 如果在LEE的索引片变得非常厚,一个三星索引可能更适合。不过存在一个上限,大约是100000次TS,这时扫描索引片将耗费太长时间以致我们需要创建一个新的索引。对于本例而言这个新的索引就是三星索引。

对于本次分析中我们所考量的各种索引的总结如下所示。

类型索引LRT维护
现有索引LNAME,FNAME100s-
半宽索引LNAME, FNAME, CITY0.2sU CITY + 10-20ms
宽索引LNAME, FNAME, CITY, CNO0.1sU CITY + 10-20ms
三星索引LNAME, CITY, FNAME, CNO0.01sI/D + 10ms U + 10-20ms

在之前的例子中,我们一直心照不宣地假定结果集为空的情况是导致性能最糟糕的场景。然而,我们应该意识到,一个几乎为空的结果集将导致更糟糕的性能,因为在使用半宽的索引的情况下,这将引起不超过20次的表访问。

练习

架设一张表,表中有10000000条记录,表上有索引(A)和(C),(A)为聚集索引
SQL 语句如下,在当前的索引条件下,这个sql执行需要花费一分钟。

SELECT C,E,F
FROM TABLE
WHERE B = :B
      AND
      C > :C
      AND
      D = 1
ORDER BY C

练习 6.1

用两种方案设计最佳的可能索引 : (1)不增加额外的第三个索引,(2)增加第三个索引
假设C的过滤因子为X,结果的行数为Y,则QUBE结果如下,可以看出,主要是回表产生的随机读很多,想办法把这部分消除掉,就能有很大提升

索引      C                 TR = 1                         TS = 10000000 * x
表        CUST              TR = 10000000 * x + 1          TS = 0
提取      Y * 0.1ms
LRT                         TR = 10000000 * x + 2          TS = 10000000 * x
                            (10000000 * x + 2) * 10ms        10000000 * x * 0.01ms
                            (10000000 * x + 2) * 10ms + 10000000 * x * 0.01ms + Y * 0.1ms ≈ 60000ms

(1)不增加额外的第三个索引

增加一个宽索引,相对于原索引,将会减少 100000000 * x + 10 毫秒,随着X(C的过滤因子)的不同,减少的时间会变化,过滤因子越大,优化的百分比越高。

索引      C, B, D, E, F                 TR = 1          TS = 10000000 * x
表        CUST                          TR = 0          TS = 0
提取      Y * 0.1ms
LRT                                     TR = 1          TS = 10000000 * x
                                        1 * 10ms        10000000 * x * 0.01ms
                                        1 * 10ms + 10000000 * x * 0.01ms + Y * 0.1ms ≈ ?
(2)增加第三个索引

增加一个三星索引, 假设B和D的过滤因子分别为Z,H,相对于原索引,随着B,D,C字段的过滤因子的不同,较少的时间会变化,过滤因子越大,优化的百分比越高

索引      B, D, C, E, F                 TR = 1          TS = 10000000 * x * Z * H
表        CUST                          TR = 0          TS = 0
提取      Y * 0.1ms
LRT                                     TR = 1          TS = 10000000 * x * Z * H
                                        1 * 10ms        10000000 * x * Z * H * 0.01ms
                                        1 * 10ms + 10000000 * x * Z * H * 0.01ms + Y * 0.1ms ≈ ?

练习 6.2

假设1s是我们可接受的执行时间,并且我们不愿增加一个新索引。对于上一题中的第一个方案,你需要了解哪些信息来语句它所能带来的性能提升?
需要了解C的过滤因子和符合筛选条件的记录的总条数

数据库索引设计与优化02-BE与QUBE

前瞻性的索引设计

发现不合适的索引

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

  1. 基本问题法(Basic Question, BQ)
  2. 快速上线估算法(Quick Upper-Bound Estimate, QUBE)

基本问题法(BQ)

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

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

如何确认第一个方案(半宽索引)或第二个(宽索引)方案能否让select在最差输入下仍然运行的足够快?

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

实际上,使用第二种方法,QUBE来评估索引方案将不会那么乏味。

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

注意

对于BQ的一个肯定的回答并不能保证足够的性能。记住,BQ的目的是确保我们至少可以通过索引过滤来最小化对表的访问,除此之外没有其他作用。

举个例子,假设有一个select,谓词是where b = :b and c = :c,唯一有用的索引是(A, B, C)。这个索引包含了该select的所有谓词列,因此BQ方法检查这个select并不会产生告警。然而这个查询的访问路径将会是全表扫描。如果该表有超过100000条记录,那么查询将运行的非常慢。索引过滤本身并不意味着这个索引有三颗星中的任何一颗。

快速上限估算法(QUBE)

这个快速估算法输出的结果是本地响应时间(LRT),即在数据库服务器中的耗时。在单层环境(指发出SQL调用的应用与数据库部署在同一台机器上)中,一个传统事务的LRT是指用户和数据库服务器之间一次交互的响应时间,不包括所有的网络延迟。在多层环境(客户端/服务器)中。各层之间的通信时间也被排除在外。批量任务的LRT是指执行任务耗时。任何任务队列中的排队时间也被排除在外。

服务时间

在简单的场景下(I/O时间和CPU时间不重叠),服务时间等于CPU时间加上排除了磁盘驱动排队的随机读时间。如果没有资源竞争,则本地响应时间等于服务时间。

排队时间

在一个常规的多用户环境中,程序的并发会导致对所需资源的各种竞争,因此这些并发的程序不得不排队开获取这些资源。以下资源在LRT的范畴内 :

  • CPU排队时间(所有处理器都忙着处理更高优先级的任务)
  • 磁盘驱动器排队(包含请求页的驱动器处于繁忙状态)
  • 锁等待(请求的表或行被锁定在一个不兼容的级别)
  • 多道编程的级别,线程数或其他方面已经达到上限(这些都是为了防止资源过载而设计的系统值)

QUBE会忽略除磁盘驱动排队以外的其他所有类型的排队,以提供一个简单的评估过程,用于评估那些对性能影响特别大的方面。

在排除上述因素后,我们得到的是一个非常简单的估算过程,仅需两个输入变量,TR和TS,必要时还有第三个输入变量,F。这些就可以将SQL的处理及I/O成本考虑进来了,并且他们是影响索引设计的主要因素。如果是使用QUBE来比较多个可选访问路径之间的性能差异,由于FETCH调用的次数是相同的,所以可以忽略FETCH调用次数带来的影响。如果是使用QUBE来确定响应时间,那就需要包含FETCH调用的次数。

比较值
LRT = TR * 10ms + TS * 0.01ms

绝对值
LRT = TR * 10ms + TS * 0.01ms + F * 0.1ms

LRT = 本地响应时间
TR = 随机访问的数量
TS = 顺序访问的数量
F = 有效FETCH的数量

基本概念

访问

根据定义,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就必须将该行记录迁移至另外一个表页中,同时在原有的表页中存储指向新表页的指针。当该行被访问时,会引入额外的随机访问。

表可以通过重组来还原行记录的顺序,从而减少不必要的随机访问。因此,如果行记录存储在同一个页或者相邻的页当中,QUBE就认为他们在物理上彼此相邻。换句话说,QUBE假设所有的表,所有都是以最理想的顺序组织的。

之前我们做过一些最差场景的的假设,在这种假设下,QUBE足够简单,能够快速且方便的使用。同样的原因,我们也有必要做一些乐观的假设。尽管存在上述问题,根据QUBE的定义,扫描索引或表的一个片段只需进行一次随机访问。数据库专家们需要对重组的必要性进行监控,以保证我们所做的这些乐观假设都是合理的。

计算访问次数

既然访问对于QUBE而言如此重要,我们现在就解释下如何确定索引及表的访问次数,包括随机访问和顺序访问。

随机访问

我们首先思考一下磁盘读与访问的区别。一次磁盘读所访问的对象是一个页,而一次访问的访问对象则是一行。一次随机磁盘读会将一整页(通常会包含很多行)读取至数据库的缓冲池中,但是根据定义,前后两次随机读不太可能会访问到同一个页。因此,QUBE中单次随机访问所消耗的时间与一次磁盘随机读的平均耗时是一样的,都是10ms。虽然随机读是同步的,但是由于现在的处理器速度非常快,所以在估算单次随机访问开销时可以忽略CPU时间,这一CPU时间通常小于0.1ms。

顺序访问

一次顺序访问是指读取物理上连续的下一行,这一行要么存储在同一页中,要么在下一页中。由于顺序读的CPU时间与I/O时间是重叠的(DBMS和磁盘控制器通常会预读一些页),因此顺序访问的消耗时间就是两者中较大的那个。在QUBE中,一次顺序读所消耗的时间是0.01ms。

当计算访问次数时,为了简单起见,我们会遵循以下规则:

  1. 忽略索引的非叶子节点。我们假定他们都在数据库的缓冲池中,或者至少在磁盘服务器的读缓存中。
  2. 假设DBMS能够直接定位到索引片的第一行(忽略为了定位索引行的位置而使用二分查找或者其他技术所耗费的时间)。
  3. 忽略跳跃使顺序读所节省的任何时间。这可能是一个很悲观的假设。
  4. 假设所有的索引和表都处于理想的组织顺序。如上所述,这可能是个很乐观的假设,除非表和索引都被很好的监控着。

当计算索引访问次数时,可以将索引看成一个微表,他的行数与其指向的表包含的行数相同,且按照索引键值排列。

当计算表访问次数时,我们假设表行在表页中是按理想顺序排序的,这个顺序依赖于表的组织方式。我们可以假设一次全表扫描(N行数据)将需要一次随机访问和N-1次顺序访问。

FETCH处理

被接受的行的数量可以通过FETCH调用的次数来确定(除非多行FETCH可用),这些行将经历更多的处理程序。TS不包含这个额外的处理过程。现在,我们需要将第三个输入变量,LRT组成中的F考虑进来。F的成本比TS大一个数量级,而另一方面,他比TR的成本要小很多。

如果QUBE被用来比较可选的访问路径,比如比较全表扫描与使用特定索引,那么F参数是无关紧要的,因为他的值在两种情况下相等,我们只需要考虑TR和TS。但如果使用QUBE来确定LRT,F参数就可能会比较重要,这取决于FETCH调用的次数。

在处理被接受了的行时,可能会涉及排序操作,排序的整体开销通常与FETCH的行数成正比。大多数情况下,相对于在所接受的行上进行其他处理过程,排序的开销非常小,所以他被隐藏在F的开销内。然后有些场景却不是这样,这个将会在后面讨论。除了这些例外场景外,我们都假定排序开销包含在F参数中。

请注意,在计算FETCH调用次数时,为了避免混淆,我们将忽略“判断没有更多符合条件的行”的那次调用,这纯粹是为了简化计算。例如,一张有10000条计算的表上的一个过滤因子为1%,期望的返回行数是100,那么我们就假设F为100而不是101.

主要访问路径的QUBE示例

示例5.1 : 主键索引访问

SELECT CNO,LNAME,FNAME
FROM
WHERE CNO=:CNO

通过主键索引读取一个表行需要随机访问一次表和随机访问一次索引。

索引 CNO         TR = 1
表   CUST        TR = 1
提取 1 * 0.1ms
LRT        TR = 2
           2 * 10ms + 0.1ms ≈ 20ms

示例5.2 : 聚簇索引访问

SELECT CNO,LNAME,FNAME
FROM CUST
WHERE ZIP = :ZIP AND LNAME = :LNAME
ORDER BY FNAME

假设区号为(ZIP)30103的地区内有1000位名为Joneses的客户,通过这个二星索引的两个匹配列访问了一个薄的索引片。这里不需要排序,因为索引已经提供了所需的顺序。

扫描1000行的索引片需要多长时间?首先,需要进行一次随机访问来找到索引片上的第一条符合条件的索引行,然后DBMS继续向前读取,知道找到列ZIP和LNAME与输入值不匹配的行为止。包括访问的最后一个不匹配的行,索引的访问数是1000。因此,根据QUBE,扫描索引片需要1 10ms + 1000 0.01ms = 20ms。

因为列CNO不在索引中,所以必须从表中读取该列。由于索引是聚簇的,而且我们假设表中的1000行是相邻的,于是扫描表片段的成本将会是1 10ms + 999 0.01ms ≈ 20ms。此外,还有FETCH调用的时间,根据QUBE,总的响应时间为140ms。由于顺序访问的成本非常低,因此表的访问成本是非常低的。最大的开销来自DETCH调用的过程。

索引 ZIP,LNAME,FNAME TR = 1      TS = 1000
表   CUST = 1                    TS = 999
提取 1000 * 0.1ms

LRT     TR = 2      TS = 1999
        2 * 10ms    1999 * 0.01ms
        20ms + 20ms + 100ms = 140ms
        20ms + 20ms + 1000 * 0.1ms
        20ms + 20ms + 100ms = 140ms

示例5.3 : 非聚簇的索引访问

SELECT CNO,LNAME,FNAME
FROM CUST
WHERE ZIP = :ZIP AND LNAME = :LNAME
ORDER BY FNAME

如果表的记录不是通过聚簇索引访问的,那么表的1000次访问就会变成随机访问。

索引      ZIP,LNAME,FNAME      TR = 1      TS = 1000
表        CUST                 TR = 1000   TS = 0
提取      1000 * 0.1ms
LRT                            TR = 1001   TS = 1000
                               1001 * 10ms 1000 * 0.1ms
                               10s + 10ms + 1009 * 0.1ms ≈ 10s

在这种情况下,将列CNO加到索引中让索引称为三星索引会是个好方案,因为这样能使响应时间从10s降低至0.1s

索引      ZIP,LNAME,FNAME      TR = 1      TS = 1000
表        CUST                 TR = 0      TS = 0
提取      1000 * 0.1ms
LRT                            TR = 11   TS = 1000
                               1 * 10ms 1000 * 0.1ms
                               10ms + 10ms + 1009 * 0.1ms ≈ 120ms

示例 5.4 : 使用聚簇索引进行跳跃式顺序表访问

SELECT STREET, NUMBER, ZIP, BORN
FROM CUST
WHERE LNAME = 'JONES' AND FNAME = 'ADAM' AND CITY = 'LONDON'
ORDER BY BORN

5.4的查询将使用聚簇索引(LNAME,FNAME,BORN,CITY)。在这一索引条件下,要找到住在伦敦的所有名为Adam Joneses的客户,需要多少次随机访问和顺序访问呢?
假设LNAME和FNAME匹配之后的索引片大小为5

索引      LNAME,FNAME,BORN,CITY      TR = 1      TS = 4
表        CUST                       TR = 2      TS = 0
提取      2 * 0.1ms
LRT                                  TR = 3      TS = 4
                                     3 * 10ms    4 * 0.1ms
                                     40ms + 0.4ms + 2 * 0.1ms ≈ 30.4ms

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

实例1

我们已经通过一些例子展示了如何运用QUBE来方便的评估一些比较重要的访问方式,现在我们将展示如何使用这两种技术(BQ和QUBE)来完成整个索引设计过程。

假设有一张表,结构如下

create table `cust`(
`cno` varchar(8) primary key,
`pno` varchar(8) not null default '',
`fname` varchar(8) not null default '',
`lname` varchar(8) not null default '',
`city` varchar(8) not null default '',
key `idx_pno`(`pno`),
key `idx_lname_fname`(`lname`, `fname`)
)

再假设下其他的条件

  1. 表中有100万记录
  2. idx_lname_fname是唯一合适的索引
  3. 谓词lname = :lname的最大过滤因子是1%
  4. 谓词city = :city的最大过滤因子是10%
  5. 结果集最多包含10000条记录(1000000 1% 10%)
  6. 表中的记录按照cno列的大小顺序存储,主键索引cno是聚簇索引,或者表经常按照cno进行排序重组。

sql语句如下

select cno,fname
from cust
where lname = :lname and city = :city
order by fname
该事务的基本问题

是否有一个现有的或者计划中的索引包含了where子句中所涉及的所有列?

换句话说,我们是否现在或者即将有一个半宽索引?答案显示是没有,至少从现有的索引情况看是这样。这并不一定意味着存在问题,性能还是有可能令人满意的。但至少这是一个警示信号,我们应该去思考是否真的存在问题,如果是并且我们决定忽略它,那么它会变得多严重?我们是否需要将那些不在索引中的谓词列加到索引中?这样做将给BQ一个肯定的答案,但我们应该牢记这仍然不能确保良好的性能。

对事务上限的快速估算

当DBMS选择使用索引idx_lname_fname时,结果行是按照所请求的顺序(order by fname)被获取的,既不需要排序。因此,DBMS将不会进行早期物化 : OPEN CURSOR动作不会产生对表或索引的访问,而是在每次FETCH的时候访问索引和表,其中的一些访问会将记录行返回给FETCH,另一些(大部分)则不会。整个过程将引起一次所有扫描,匹配列只有一个,该列的过滤因子是1%。根据QUBE

索引      LNAME,FNAME      TR = 1      TS = 9999
表        CUST             TR = 10000   TS = 0
提取      1000 * 0.1ms
LRT                        TR = 10001  TS = 9999
                           10001 * 10ms    9999 * 0.1ms
                           100s + 1s + 1000 * 0.1ms ≈ 101.1s

很明显,这里有一个很明显的问题,即数据库必须读取10000条不相邻的表记录。这需要耗费很长时间,将近2分钟。

QUBE是一个对上限的估算法 : 结果100s意味着本地响应时间最多会达到100s。真实的LRT可能比这个值小,特别是当内存和缓冲池的大小对数据库来说非常充足时。这种情况下,许多随机访问将不再需要从磁盘驱动器上读取,随机访问的平均响应时间也可能比10ms低。不管怎么说,这不是一个错误的告警,对表的访问次数太高了。

由于QUBE是一个非常粗略的工时,因此在结果中显示多于一位的有效数字是具有误导性的,尽管为了清除起见我们会这么做。在真实的报告中,应该这样阐述结论 : 根据快速估算,被提议的索引能将最差情况的响应时间从2min降至1s。

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

设计索引并不只是单纯的为了最小化磁盘I/O的总量,而是为了设法让所有程序都运行的足够快,同时还能做到不使用过量的磁盘存储,内存和读缓存,且不使磁盘超载。

我们甚至可以将这种决策以数字的方式来表达,比如这样问 : 将一个每月运行50000次的事务的响应时间从2s~10s降低至0.1s~0.5s,同时节省1000秒的CPU运算时间,为达到这样的目的每个月支付10美元是否值得?

通过BQ,QUBE(或者其他方法),我们已经发现了这样一个事实 : 改SQL会由于没有合适的索引执行的非常慢。现在,我们面临一个困难的问题 : 我们应该给这个语句设计一个所能达到的最优索引,还是为期设计一个成本最低的满足性能要求的索引?又或是介于两者之间的某种索引?我们并没有一个硬性公式去解答这个问题。

该事务的最佳索引

使用前面描述的算法可以得到两个三星索引
(lname, city, fname, cno)或(city, lname, fname, cno)
这两个索引都有三颗星,因为他们会扫描一个非常薄的索引片,order by列跟在匹配列之后,从而避免了排序;此外,此查询只需要访问索引而无需回表。

索引      lname, city, fname, cno      TR = 1      TS = 999
表        CUST                         TR = 0      TS = 0
提取      1000 * 0.1ms
LRT                                    TR = 1      TS = 999
                                       1 * 10ms    999 * 0.01ms
                                       10ms + 10ms + 1000 * 0.1ms ≈ 120ms

在性能方面,这两个索引并没有什么区别,他们都极大的降低了成本。不幸的实际,三星索引将意味着额外增加一个索引,因为列(city)添加到现有索引的lname和fname之间可能会对现有的程序造成不利的影响。这就是为什么我们可以考虑一下开销更低的可选方案。

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

将谓词列city加至现有索引(lname,fname)的末端,可以消除大部分的表访问,因为会引入索引过滤过程。表中的行只有在确定包含所请求的city值的情况下才会被访问。

该索引(lname, fname, city)是满足BQ的,所有谓词列都在索引中。然而,他只有一颗星,所请求的索引行不是连续的,当然,他也不是宽索引。但是这种开销很低的方案是否满足需求了呢?

索引      lname, fname, city      TR = 1      TS = 9999
表        CUST                    TR = 1000   TS = 0
提取      1000 * 0.1ms
LRT                               TR = 1001   TS = 9999
                                  1001 * 10ms 9999 * 0.01ms
                                  10s + 100ms + 1000 * 0.1ms ≈ 10.2s

借助于这个半宽索引,LRT由原来的近2min降低到了10s,这是一个巨大的进步,但还不够(别忘了最佳索引下的运行时间仅为120ms)。我们仍有太多成本很高的TR,我们需要一个宽索引,已取得更好的性能。

宽索引(只需访问索引)

将一个列添加到半宽索引上,将使改索引变为一个宽索引 : (lname, fname, city, cno)。现在,我们有了两颗星,第二颗和第三颗,同时LRT变为了1s。

索引      lname, fname, city, cno      TR = 1      TS = 9999
表        CUST                         TR = 0      TS = 0
提取      1000 * 0.1ms
LRT                                    TR = 1      TS = 9999
                                       1 * 10ms 9999 * 0.01ms
                                       10ms + 100ms + 1000 * 0.1ms ≈ 210ms

下图提供了各种索引的性能比较,最后一列显示的是由此引起的额外的维护成本。需要注意的是,三星所以将是一个新的索引。对于这些成本提醒如下两点事项 :

  1. 插入和删除意味着修改一个叶子页。如果该子叶不在缓冲池或者读缓存中,那么整个叶子页就必须从磁盘驱动器上读取,无论锁添加或删除的索引行的长度是多少,这都将耗费10ms的时间
  2. 更新city列会导致响应时间增加10ms或20ms,具体的值取决于是否需要将索引行迁移至另一个叶子页。通过将cust列作为最后一个索引列的方式可以避免这一移动。
类型索引LRT维护成本
现有索引lname,fname100s-
半宽索引lname,fname,city10sU city + 10 - 20ms
现有索引lname,fname,city,cno0.2sU city + 10 - 20ms
现有索引lname,city,fname,cno0.1sI/D + 10ms U + 10 - 20ms

LRT是最差输入下的QUBE值,I = 插入,D = 删除,U = 更新

重要说明

在这个阶段,我们需要将所有变更的维护成本也考虑进来。比如,在将索引升级为宽索引时,理论上是将cno添加至索引的末尾,但实际上,将它放在city列的前面会更好,即(lname, fname, cno, city)。对于这个select而言,由于city列参与的是索引过滤过程,所以他的位置并不会对运行结果造成影响。

同样,当有多个等值谓词作为匹配列时,我们需要考虑这些列在索引上的先后顺序。经常变化的列应当尽可能的排在后面(相对于lname,用户更改地址的可能性更大,因此lname,city可能是比较适合的顺序)。另一方面,我们需要考虑新索引对于其他select的帮助有多大。在本例中,我们已经有一个lname开头的索引了,因此从这个角度看,city,lanme可能更合适。显然,我们需要在这两者之间进行权衡,对于这个案例而言。后者可能更重要,因为city并不是一个频繁更新的列

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

实例2

范围事务的BQ即QUBE

假设有一张表,结构如下

create table `cust`(
`cno` varchar(8) primary key,
`pno` varchar(8) not null default '',
`fname` varchar(8) not null default '',
`lname` varchar(8) not null default '',
`city` varchar(8) not null default '',
key `idx_pno`(`pno`),
key `idx_city`(`city`),
key `idx_lname_fname`(`lname`, `fname`)
)

再假设下其他的条件

  1. 表中有100万记录
  2. idx_lname_fname是唯一合适的索引
  3. 谓词lname = :lname的最大过滤因子是10%
  4. 谓词city = :city的最大过滤因子是10%
  5. 结果集最多包含10000条记录(1000000 10% 10%)
  6. 表中的记录按照cno列的大小顺序存储,主键索引cno是聚簇索引,或者表经常按照cno进行排序重组。

sql语句如下

select cno,fname
from cust
where city = :city and lname between :lname1 and :lname2
order by fname

idx_city与idx_lname_fname都不是半宽索引,所以两者都不满足BQ。QUBE的结果显示出二者的性能都非常差,无论使用哪个索引其结果都是相同的 : 两个索引的匹配扫描过程都只能使用1个MC,都需要进行排序

索引      lname, fname或city            TR = 1      TS = 99999
表        CUST                         TR = 100000      TS = 0
提取      10000 * 0.1ms
LRT                                    TR = 100001      TS = 9999
                                       100001 * 10ms 99999 * 0.01ms
                                       1000s + 1s + 10000 * 0.1ms ≈ 1002s
该事务的最佳索引

最佳索引很容易得到,候选方案A是
(city, lname, fname, cno)
该索引只有两颗星,因为需要排序(order by跟在范围谓词列的后面)。因此,候选方案B一定是(city,fname,lname,cno),他也只有两颗星,不过他具有的是第二颗星而不是第一颗。通过QUBE很容易判断出哪一个才是最佳索引。

候选索引A
索引      city, lname, fname, cno            TR = 1      TS = 9999
表        CUST                               TR = 0      TS = 0
提取      10000 * 0.1ms
LRT                                          TR = 1      TS = 9999
                                             1 * 10ms 9999 * 0.01ms
                                             10ms + 100ms + 10000 * 0.1ms ≈ 1110ms
候选索引B
索引      city, fname, lname, cno            TR = 1      TS = 99999
表        CUST                               TR = 0      TS = 0
提取      10000 * 0.1ms
LRT                                          TR = 1      TS = 99999
                                             1 * 10ms    99999 * 0.01ms
                                             10ms + 1000ms + 10000 * 0.1ms ≈ 2010ms

最佳索引显然是A,(city, lname, fname, cno),LRT为1s,但即使是最佳索引,事务的性能也一般。

我们早先提出过,如果只是为了比较不同的访问路径,fetch的处理可以被忽略,因为它在所有的情况下均是相同的。但是这么做之后,在决定选取哪个索引时要小心一点。例如,在这个案例中,如果忽略fetch的处理,那么候选方案A的成本仅为候选方案B成本的1/10,而实际的优势比例要小得多。

在这个例子中,候选方案A所需要的排序成本与候选方案B所节省的1秒相比是微不足道的,如前所述,事实上排序成本已经被包含在fetch的开销中了。候选方案B的问题在于我们使用的索引片更厚(10%),从而产生了大量的TS。

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

在两个现有索引的末端添加缺少的谓词列可以消除大量的随机访问,因为这样能引入索引过滤过程。只有在确定索引行中同时包含所需city和lname值时,表中的行才会被访问。

在现有索引的基础上,我们可以使用两个半宽索引
(city, lname)或(lname, fname, city)
我们再一次使用QUBE来判断那个是最好的。

索引      city, lname            TR = 1      TS = 9999
表        CUST                   TR = 10000      TS = 0
提取      10000 * 0.1ms
LRT                              TR = 10001      TS = 999
                                 10001 * 10ms 9999 * 0.01ms
                                 100s + 100ms + 10000 * 0.1ms ≈ 101s
索引      lname, fname, city            TR = 1      TS = 99999
表        CUST                          TR = 10000  TS = 0
提取      10000 * 0.1ms
LRT                                    TR = 10001   TS = 99999
                                       10001 * 10ms 99999 * 0.01ms
                                       100s + 1s + 10000 * 0.1ms ≈ 1002s

虽然第二个索引会有一个更厚的索引片,但这个因素在很大程度上被大量的表访问掩盖了(尽管已经通过过滤的方式将表访问的次数大大减少了)。看来我们需要设计一个宽索引来消除对表的10000次TR了。

宽索引(只需访问索引)

我们在上面评估的第一个宽索引上再多加两个列,在第二个索引上再多加一个列,两者就都变成了宽索引 : (city, lname, fname, cno)或(lname, fname, city, cno)

索引      city, lname, fname, cno            TR = 1      TS = 9999
表        CUST                               TR = 0      TS = 0
提取      10000 * 0.1ms
LRT                                          TR = 10001  TS = 999
                                             1 * 10ms 9999 * 0.01ms
                                             10ms + 100ms + 10000 * 0.1ms ≈ 1.11s
索引      lname, fname, city, cno            TR = 1      TS = 99999
表        CUST                               TR = 0      TS = 0
提取      10000 * 0.1ms
LRT                                          TR = 11     TS = 99999
                                             10001 * 10ms 99999 * 0.01ms
                                             10ms + 1s + 10000 * 0.1ms ≈ 2.01s

现在表的访问已经消除了,两个索引的LRT之间的区别就变得很明显了。第一个索引满足了第一颗星,即提供了一个薄的索引片,因为它所基于的原始索引只包含city列,这是在select中唯一的等值条件。正因为如此,我们才能将它升级为最佳索引,首先添加between谓词列(使其变为半宽索引,但仍不够),然后再添加select中引用的其他列(使其变为宽索引)。

类型索引LRT维护成本
现有索引lname或city17min-
半宽索引city, lname101sU lname + 10 - 20ms
半宽索引lname, fname, city102sU city + 10 - 20ms
宽索引city, lname, fname, cno1sU L & FNAME + 10 - 20ms
宽索引lname, fname, city, cno2sU city + 10 - 20ms
三星索引city, lname, fname, cno17minU L & FNAME + 10 - 20ms
三星索引city, fname, lname, cno17minU L & FNAME + 10 - 20ms

LRT是最差输入下的QUBE值,I = 插入,D = 删除,U = 更新

何时使用QUBE

理想情况下,QUBE应当在新方案的设计过程中使用。如果在当前或者计划设计的索引条件下最差输入的本地响应时间过长,比如大于2s,那么就应当考虑进行索引优化了。

尽管批处理任务的告警阈值视具体的任务而定,但检查一下所有批处理程序相邻提交点之间的最大时间间隔是很重要的,这个值也许应当小于1s或2s,否则该批处理任务有可能会导致事务池和其他批处理任务中的大量锁等待。

QUBE甚至可以在设计程序之前就开始使用,只需要简单地知道数据库一定会处理的最差输入场景即可。例如,读取表中10行不相邻的记录,像B表重增加2行相邻的记录,等等。事实上,直到估算结果令人满意时再开始设计程序是非常明智的做法。有时,我们可能还必须设计较为复杂的程序结构以满足性能的要求。