数据库索引设计与优化09-其他评估事项

评估CPU时间(CQUBE)

可以简单的借鉴QUBE的方法来评估SQL执行的CPU时间(CQUBE),用RS代表排序的记录数 :
CPU时间 = 100μs x TR + 5μs x TS + 100μs x F + 10μs x RS

单次顺序访问的CPU时间

按照QUBE方法中的定义,一次顺序访问是指在顺序扫描过程中读取一条记录,然后使用非匹配谓词进行过滤(匹配谓词已被用于定义锁扫描片段的厚度)。当然,如果是全表或者全所有扫描,那么所有的谓词都是非匹配谓词。

单次顺序访问的CPU时间主要跟单条记录的长度有关,因为CPU时间主要耗费在数据页的处理上。另外,非匹配谓词的个数和复杂度是另一个主要因素,还有锁机制和压缩等其他因素。

在具体的平台上,评估单次顺序访问的CPU时间相对简单,接下来我们就展示三个具体测量的例子。

在第一个例子中有两个WHERE条件恒为非真的单表SELECT语句。两个语句的WHERE条件中都只有一个谓词,且谓词为非索引列。这样,优化器不得不为这两个SELECT语句选择使用全表扫描的方式。其中的CUST表有111000个4KB大小的数据页,共1000000条长度为400字节的记录。另外的INVOICE表有77000个数据页,共4000000条长度为80字节的记录。

表没有进行压缩,所有列都是固定长度,两个WHERE条件也足够简单。锁的粒度是数据页级别的,隔离级别是CS。一些额外的谓词,特别是复杂的谓词会增加CPU时间,另外,数据记录长度的增加,记录变长,使用压缩页同样会增加CPU时间。

使用一台旧的繁忙的服务器(单处理器100minps)所测得的运行时间如下:
全部扫描的SQL的CPU时间
CUST(1000000行,111000个4KB大小的页)2.5s,2.5μs每行
INVOICE(4000000行,770000个4KB大小的页)5s,1.25μs每行

假设记录数和页数是唯一的两个重要因素,那么我们可以计算出下面两个变量的系数 :
1000000X + 111000Y = 2.5s
4000000X + 77000Y = 5s

X = 每行的CPU时间 = 1μs
Y = 每页的CPU时间 = 13μs

X和Y的值清楚的表明了列的长度和个数对CPU时间的影响。

在第二个例子中采用了一个大型的繁忙的服务器(单处理器400mips);扫描一张有222000个4KB大小的页,共13000000行短记录的表,结果集同样是0。该表经过了压缩,而且记录是变长的,但条件谓词依然是简单谓词。

最终测得的CPU时间是9s,平均每行0.7μs。

在第三个例子中使用了一个小型的服务器(单处理器750MHz),扫描的CUST表有1000000行400字节的长记录,结果集共提取1078行记录,并进行排序操作。在WHERE条件中,有两个简单的谓词。最终测得的CPU时间是10.4s。

TS的CPU时间一共是10.4s - X,X代表1078行记录的FETCH和排序时间,利用默认的CPU系数进行计算 :
X = 1078 x 110μs ≈ 0.1s

于是,长记录的单次顺序访问的CPU时间就变成了10μs。

看起来5μs可以作为一个合理的系数值来使用,但是最好能在具体的平台上,使用长记录和短记录实测一下CPU时间。

单次随机访问的CPU时间

有以下几个原因会导致随机访问的CPU时间高于顺序访问的CPU时间

  1. 几乎每次随机读取都会引起数据页请求
  2. 如果数据页没有在缓冲池中,I/O相关的CPU时间会比较多。而由于顺序读取每次会读取多个数据页,所以平均每个数据页的I/O代价就相对较低。另外,平均每页的CPU成本能够平摊至许多顺序访问上。
  3. 由于随机访问是不可预测的,所以CPU无法将数据页预读到告诉CPU缓存中,从而可能会导致明显的内存等待。
  4. 按照QUBE的定义,一次对索引的随机访问忽略了访问非叶子页的成本,因为QUBE假定他们是位于缓冲池中的。然而,从计算CPU时间的角度上看,随机访问一个三层索引上的记录将引起三次数据页请求。这也是为什么索引上的随机访问会比表上的随机访问耗时更多。

计算单次随机访问的CPU时间的一个简单方法是,对比使用半宽或宽索引(以避免不必要的随机读取)前后的CPU时间差异。

另外一个方法是,消除掉低成本的操作(比如顺序访问和排序)。我们通过一个实例来描述这种方法 : 一个嵌套循环连接的SELECT查询语句,有813次对三层索引的随机访问,在一台100mips的机器上运行,各项指标如下 :
TR = 814(中等长度的索引行)
磁盘读 = 845(磁盘随机读取)
TS = 8130(较短长度的索引行)
F = 814
RS = 0
CPU时间 = 401ms

单次随机访问的CPU时间可以通过实测的TS系数及F系数计算得出 :
401ms - [(8130 x 1μs) + (814 x 50μs)] / 814 ≈ 434μs
转化为250mips的机器434μs/2.5 ≈ 173μs

这个CPU时间是在一个缓存命中率为0的测试环境得出的(数据库缓冲池和磁盘缓冲区都没有命中,即845次随机读取都来自磁盘)。在第一次测量完成后不接再次执行同样的事务时,消耗的CPU时间是165ms。在这个例子中,假设其他部分的CPU时间开销是48ms,那么单次随机访问的CPU时间就是 :
165ms - 48ms / 814 ≈ 144μs

在第一个例子中,平均一次随机读取的磁盘物理读个数是845/814 ≈ 1.04,而在第二次例子中完全没有磁盘I/O。这一结果验证了一条重要的原则 : 减少磁盘读缓存或者物理磁盘驱动器上的随机读取的CPU时间的一个重要因素。

根据经验,在当前的硬件条件下,单次随机访问的CPU时间通常在以下之一范围区间里 :
表访问 : 10~100μs
索引访问 : 20~300μs

影响随机访问CPU时间的最大因素还是CPU的高速缓存,如果大量的随机访问内存中的少了数据页,那么单次随机访问的CPU时间可能会小于10μs,实际上可能接近于顺序访问的耗时。

结论

单次随机访问的CPU时间100μs仍然可以用来进行快速评估。但是,按照之前的讨论,CPU时间会受到许多因素的影响,所以,当做出重要决定时(例如基于CPU时间来评估表的反范式化,或添加一个新索引等方案时),需要使用一个合理的时间范围进行评估。比如,对于一个大索引,其随机访问的CPU时间可以假设在100~300μs之间。

然而,在评估CPU时间的潜在收益时,这可能会导致问题。比如,如果一个涉及10000次随机访问的SQL语句消耗了600ms的CPU时间,但是消除9000次随机访问并不会减少900ms的CPU时间。我们需要评估600ms中有多少消耗在TR上。

单次FETCH调用的CPU时间

单次FETCH调用的CPU时间消耗(除去访问的时间)依赖于平台以及程序与DBMS的连接方式。在一个具有多层结构和拥有事务管理器的应用设计下,发送SQL语句到数据库管理系统(以及将结果集传输回来)的CPU时间大概是50μs~100μs。在其他不同的环境下,尤其是当SQL语句嵌入在数据库服务器上的批处理程序中时,单次FETCH操作的CPU时间大概在10μs~20μs之间。

由批处理程序发起的FETCH访问的代价会相对较低。在一些场景下,100μs这一默认系数可能是悲观的。如下述场景所测得的那样。

例如,在之前的例子中,在一台大型的繁忙的机器上(单核440mips)借助全表扫描,结果集为空,得到的TS的CPU时间是0.7μs。然后又执行了一次该SELECT语句,只是这次所有记录都满足条件。该查询涉及222000个4KB大小的页,共13000000条记录,且SELECT列表只包含一个列。测得的总CPU时间是115s,单次FETCH操作平均耗时808μs(115s/13000000≈8.8μs)。因此,单次FETCH操作的CPU时间就是8μs(808μs - 0.7μs)。这是一个下限值,如果查询的列比较多,那么CPU时间会相对更长。对于中型的服务器(单核250mips),只查询一个列的SELECT语句的单次FETCH调用的CPU时间下限约为(440mips/250mips)x8μs≈14μs。

每排序一行的平均CPU时间

在内存充足且没有引起磁盘I/O的情况下,排序操作的CPU时间基本和记录数呈线性关系。平台相关的系数很容易测试 : 首先执行一条对至少10000行记录排序的SELECT语句,一段时间后,在执行同样一条没有ORDER BY的SQL语句。平均排序一行的CPU时间是10μs。

CPU评估举例

在许多决策支持过程中,具备CPU需求的评估能力是有用的。

宽索引还是理想索引

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

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

宽索引和最佳索引的QUBE如下。
宽索引 : 结果集为空

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

最佳索引 : 20行结果记录(1屏)

索引 LNAME, CITY, FNAME, CNO      TR = 1      TS = 20
提取 20 x 0.1ms
LRT                               TR = 1      TS = 20
                                  1 x 10ms    20 x 0.01ms
                                  10ms + 0.2ms + 2ms = 110ms

现在来评估一下宽索引和理想索引的CQUBE值 :
宽索引 100μs x 1 + 5μs x 10000 + 100μs x 0 + 10μs x 0 ≈ 50ms
最佳索引 100μs x 1 + 5μs x 20 + 100μs x 20 + 10μs x 0 ≈ 2ms

从CPU的角度我们可以清楚的看到,使用我们之前得出的CPU系数,理想索引比宽索引的收益要高25倍。下图展示了所有索引的LRT和CPU指标。

索引LRT(最差输入下)CPU(最差输入下)
LNAME, FNAME100s1s
LNAME, FNAME, CITY0.2s54ms
LNAME, FNAME, CITY, CNO0.1s50ms
LNAME, CITY, FNAME, CNO0.01s2ms

增加一个索引,对于CUST表的插入和删除只会增加几毫秒的CPU时间(一次随机访问以及写相关的CPU时间)

嵌套循环(及反范式化)还是MS/HJ

在前面的连接查询的例子中,最终有两种可选方案 :

  1. 使用嵌套循环式的BJQ连接(使用反范式化)。
  2. 使用理想索引进行合并扫描(MS)或哈希连接(无反范式化)。

第二种方案的性能表现很好 : 在最差输入条件情况下,即返回1000行结果集的情况下,耗时为1.8s。但这个方案的唯一问题就是CPU时间。毕竟,扫描两个索引片,需要120000次随机访问以及对20000 + 100000行记录的合并排序或哈希连接。所以,在确定选择第二个方案之前,还需要慎重评估一下CPU的时间。

与之形成对比的是,用第一种方案获取一屏结果集的CPU时间非常短,且无排序 :
TR = 1 + 20 = 21, TS = 20 + 0 = 20, F = 20

所以,CPU时间 = 21 x 100μs + 20 x 5μs + 20 x 100μs ≈ 4ms(每屏结果集)。

方案2(使用合并扫描)

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

TR = 1 TR = 100000
CPU时间 = 100μs x 1 + 5μs x 100000 ≈ 500ms

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

TR = 1 TR = 20000
CPU时间 = 100μs x 1 + 5μs x 20000 ≈ 100ms

第三步 : 合并排序并FETCH结果行

将CUST作为外层扫描使得结果行按照所需的顺序排列。因此,最终的CPU时间如下。
排序及合并的CPU时间为 : 2 x 20000 x 0.01ms = 0.4s
提取的CPU时间为 : 2000 x 0.1ms = 0.2s

CPU时间

在最差输入下,这一访问路径下的CPU时间是上述三部分的总和 :
0.5s + 0.1s + 0.6s = 1.2s

方案2(使用哈希连接)

在这种方式下,第一步和第二步与合并扫描的前两步一样---CPU时间 = 00.5s + 0.1s = 0.6s

第三步 : 使用哈希函数进行匹配并FETCH结果集

优化器优先选择为来自INVOICE表的20000行短记录建立哈希表,表大小可能是20000 x 30字节 = 0.6MB。在生成环境中,该哈希表可以一次性全部缓存在内存当中,但不太可能全部缓存在只有1MB大小的CPU缓存中。

建立好哈希表后,开始扫描CUST表的索引片段。扫描的匹配过程需要随机访问哈希表100000次,单次访问的CPU时间依赖于CPU缓存缓存的命中率。若给定的是一个1MB大小的CPU缓存,那么我们假设单次哈希表访问的CPU时间是1μsμs ~ 50μs,于是,100000次哈希表访问的CPU时间就是
100000 x (1...50μs) = 0.1s ... 5s

最后,提取结果集,提取操作的CPU时间为 :
2000 x 0.1ms = 0.2s

如果哈希连接成本比较高,由于合并排序连接的CPU时间估值为0.4s,那么优化器很可能会选择使用合并扫描。在必要情况下,可以使用相应的MERGE提示来指定该访问路径。

CPU时间

在最差输入条件下,使用这一访问路径的CPU时间是上述三部分的总和,至少为 :
0.5s + 0.1s + 0.3s = 0.9s

结论

第一种方案需要大约4ms的CPU时间来提取一屏结果集,第二种方案需要1s的CPU时间来提取整个结果集(1000条记录,50屏)。对于比较小的结果集,合并扫描的CPU时间是0.6s(扫描,排序,合并20000条INVOICE索引记录),而哈希连接的CPU时间则是0.2s(扫描20000条INVOICE索引记录)。

所以,如果SELECT语句执行的不是非常频繁,第二种方案很可能是可接受的。在极端情况下,可以创建两个游标,一个使用合并连接(针对大结果集),一个使用哈希连接(针对小结果集),从而用最小的代价避免表的反范式改造。

数据库索引设计与优化08-索引和索引重组

B树索引的物理结构

在前面,索引被描述为一个表,该表包含了其所属表的列的子集,连同指向表行的指针一起。我们假设DBMS可以直接定位带匹配列所定义的索引片的第一行,然后继续扫描,知道发现一行不满足匹配列条件的索引行时停止。之前都是假设一个索引行对于一个表行,即使是索引不唯一的时候也是如此。而且,索引行总是以索引列所定义的顺序来显示的。当通过计算访问次数来评估索引时,在脑海中有这么一个假设是非常重要的。不过B树索引的真实物理结果并不是如此。

索引行被存储在索引的叶子页上。典型的索引页的大小为4KB或8KB。索引行的长度一般为索引列的总长度外加约10个字节的控制信息。如果索引行的长度为200字节,并且索引为唯一索引,那么一个8KB的叶子页大约可以存放40个索引行。如果是非唯一索引,每个索引键值后可能会有多个指针,在许多DBMS产品中,这些指针会以其值的顺序来存储。这样即使同一个索引键值对应100万条记录,DBMS也能够快速的找到那个需要删除的指针。

DBMS如何查找索引行

SQL 11.1

SELECT COLX
FROM TABLE
WHERE COLI = 12

假设优化器决定使用索引COLI来执行SQL 11.1。

DBMS首先通过内部系统表找到指向根页的指针,在读取根页之后,DBMS需要读取第二个叶子页来查找与键值12相关联的指针。

一次随机读取会从磁盘上读取一个页。如果系统表中那些用于定位根页的表页已经在数据库缓冲池中,那么这个查询可能需要进行三次随机读 : 一次根页,一次叶子页及一次表页。然而,在当前的硬件条件下,非叶子页很可能已经被缓存在数据库缓冲池中,或者至少在磁盘的读缓存中,因为它们经常被频繁的访问。所以,很有了可能只会产生两次随机读,改查询的的同步I/O时间约为2 x 10ms = 20ms,在当前的处理器条件下,CPU时间相对小得多,所以该查询的还是很可能就在20ms左右。

当数据库需要读取一个索引片时,如上述他会先读取第一个索引行。第一个索引行有一个指针指向下一个索引行,DBMS会一致沿着这个指针链访问,直到遇到一个不满足匹配谓词的索引行为止。所有的索引行都通过索引值链在一起。

在SQL 11.2中,SELECT语句所要查找的是LNAME以字符串“JO”开始,且CITY以字符串“LO”开始的记录。在这一场景下,DBMS会首先在键值JO后追加字母“A”至最大长度,如JOAA...AAA,尝试用该值在索引(LNAME, CITY)上找到一行记录。
SQL 11.2

DECLARE CURSOR112 CURSOR FOR
SELECT CNO, FNAME
FROM CUST
WHERE LNAME BETWEEN :LNAME1 AND :LNAME2
      AND
      CITY BETWEEN :CITY1 AND :CITY2
ORDER BY FNAME

当找到该键值在索引上的位置后,DBMS随之通过链表读取后续的索引行,直至一个不以“JO”开始的索引行为止。

插入一行会发生什么

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

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

叶子页的分裂验证吗

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

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

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

假设我们需要扫描100000个索引行,根据QUBE,这将花费
1 x 10ms + 100000 x 0.01ms ≈ 1s

当每个叶子页包含20个索引行(不存在叶子页分裂)时,DBMS必须读取5000个叶子页。如果这些是相邻的,并且顺序读的速度为0.1ms每页(40MB/s,页大小为4KB),那么I/O时间为 :
10ms + 5000 x 0.1ms = 510ms

如果1%的叶子页发生过分裂,扫描100000个索引行可能需要进行50次随机I/O(5000的1%)。即便是这样很小比例的分裂,I/O时间也增加了一倍 :
51 x 10ms + 5000 x 0.1ms = 1010ms

在叶子页分裂后,计算索引片扫描的I/O时间的通用公式为
(1 + (LPSR x A/B)) x ORIG

LPSR : 叶子页的分裂比率(分裂的数量/叶子页的数量)
A : 单次随机读的I/O的时间
B : 单次顺序读的I/O的时间
ORIG : 无叶子页分裂时的I/O时间

这个公式基于两个假设 :

  1. 顺序I/O时间为NLP x B(访问第一个子叶的随机I/O忽略不计)
  2. 随机I/O时间为LPSR x NLP x A(每个叶子页分裂涉及一次随机I/O)

随着A/B的增加,叶子页分类比例的预警阈值在不断降低。当A/B = 100(假设)时,若LPSR达到1%,那么I/O时间就翻倍了。

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

插入模式

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

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

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

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

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

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

随机插入模式

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

索引页大小索引类型索引大小
4KB< 80字节
8KB< 160字节
4KB中等80 ~ 200字节
8KB中等160 ~ 400字节
4KB> 200字节
8KB> 400字节

短索引行的选择捷径

当索引行比较短时,为一个随机插入情况的索引选择P值是相对简单的。
基本建议 : P = 10%,当索引已经增长超过5%时重组索引
略。。。

数据库索引设计与优化07-多索引访问

简介

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

索引与

假设表TX上有索引A和索引B,如何使用如下的索引的来完成SQL 10.1的查询

SELECT B, C
FROM TX
WHERE A = :A
      AND
      B BETWEEN :B1 AND :B2
ORDER BY B

在高昂的磁盘空间成本导致宽索引不太普遍时,索引与是很重要的。对与必须在A和索引B之前作出选择,而后读取表行以校验其余谓词条件的场景,该特性提供了另一种替代方案。如下

  • 从索引片①和索引片②上手机所有满足响应谓词条件的索引行指针
  • 按页号的顺序对两个指针集合进行排序③
  • 合并这两个已排序的指针集合③
  • 只针对那些同时满足两个WHERE子句的结果行进行表访问④
    每个结果行进行一次表访问;这些表访问将会比传统随机读的方式访问得更快,因为指针已经按照页号进行了排序,所以对表页的扫描将通过跳跃式顺序读的方式完成。

那么这一访问路径与单个组合索引相比哪个更好?相比多索引访问我们更倾向于后者,因为使用后者对索引的访问次数更少。即便如此,优化器仍然可能会选择跳跃式顺序读的方式,如果这么做看起来性能不错的话。当然,对该查询来说,一个宽索引(A,B,C)是更高效的方案。

在现今的操作型应用中,索引并不是一种普遍的访问路径。如果通过EXPLAIN发现了索引与,则应当考虑使用一个宽索引将其替代,因为使用上述机制进行索引与操作有三个严重的缺陷 :

  1. 当一个简单谓词有一个较高的过滤因子时,顺序访问的量可能会过多
  2. 即便多个索引片都是从一个符合查询排序的索引上读取的,ORDER BY子句仍会引起一次排序,因为对指针集的排序操作破坏了从索引继承而来的原始顺序。
  3. 如果从索引片上仅仅手机指向表行的指针,那么一个只需要访问索引的访问路径是无法实现的。这一数据库管理系统的实现相关的问题将在后面讨论。

假设有一张表CUST,表上有三个单列索引(SEX, WEIGHT, HEIGHT),表上总共有100万行数据,SQL 10.2如下。如果优化器决定从这三个索引上收集匹配的指针,那么数据库管理系统就必须访问50万的SEX索引行。并且,针对每一位身材高大的男士都将进行一次表访问。若数据库管理系统依照上述的方式进行多索引访问,那么即使SEX索引变宽也无法避免表访问。
SQL 10.2

SELECT LNAME, FNAME, CNO
FROM CUST
WHERE SEX = 'M'
      AND
      (WEIGHT > 90 OR HEIGHT > 190)
ORDER BY LNAME, FNAME

与查询表一同使用索引与

如果应用系统会对一个表生成SELECT语句,且这些SELECT语句带有许多不同且不可预测的WHERE子句,那么此时索引与是一个很有用的功能。

查询表是对查询进行了优化了的事实数据表。他们在表的行数不是特别多的时候是可行的,比如几百万行数据。正是由于对查询进行了优化,所以不再需要进行表连接,所有查询语句所需的列都在一个表中了。

多索引访问和事实数据表

也许在一个大的事实数据表上创建多个窄索引,主键索引及外键索引的方案看起来不错。这样将会比宽索引耗费更少的磁盘空间。然而,如果该表有10亿行数据,那么基于B树索引的多索引扫描,两桶大量的指针扫描和排序一起,在当前的硬件条件下可能会运行的太慢。

用位图索引进行多索引访问

略...

索引或

索引或是比索引与更重要的一个特性。
在多索引访问功能被引入作为优化器的一部分之前,对于SQL 10.3中所示的SELECT语句,优化器将会选择哪种访问路径呢?如果该表有一个单列索引A和一个单列索引B,那么优化器只有一个合理的选择,即全部扫描,因为这两个谓词都是非布尔的,数据库管理系统并不能因为其中一个谓词被检查出不满足条件而排除该行。
SQL 10.3

SELECT B, C
FROM TX                          1000000 rows
WHERE A = :A                     FF = 0...0.01%
      OR
      B BETWEEN :B1 AND :B2      FF = 0...0.05%

即使使用一个宽索引(A, B, C)也不会有太大的帮助,因为数据库管理系统必须扫描整个索引,这涉及一百万次的顺序访问。

在使用索引或时,会进行如下操作

  • 采集两个指针集①和②---100次顺序访问A,500次顺序访问B,在最差输入条件下合计共600次访问。
  • 对指针进行排序③---非常快。
  • 去除重复的指针③---非常快。
  • 读取满足条件的表行④---在最差输入下且没有重复指针的情况下,共600次随机访问,100 x 10ms = 6s;相较之下,全索引扫描花费的时长为 1000000 x 0.01ms = 10s

在快速EXPLAIN复查的过程中,我们应当对SELECT语句进行多索引访问检查;不合适的索引或者有害的OR可能会被识别出来,这些识别出的问题必须用UNION来替代,或者对游标进行拆分。

索引连接

略。。。

数据库索引设计与优化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