数据库索引设计与优化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上面没有索引！怎么会如此呢？这里有如下两个原因。
- 在当前的硬件条件下，顺序读是非常快的 : 一张有20000000行记录的表可能在大约3min内就能被全部扫描一遍了(基于QUBE的假定数字)。
- 由于谓词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 userSQL 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 |
|---|---|---|
| 现有索引 | 35min | 10min |
| 理想索引 | 17min | 3.5min |
| 理想索引，理想程序(+),多屏结果数据 | 2s | |
| 理想索引，理想程序(+),多屏结果数据(FF缺陷) | 3.5min | |
| BJQ理想索引，理想程序(+)，单屏结果数据(FF缺陷) | 0.2s |
预测表的访问顺序
我们可以看到使用嵌套循环的连接方式时，表的访问顺序可能会对性能产生巨大的影响，索引类似。而在未确定表的最佳访问顺序之前，是无法设计理想索引的。
在大部分情况下，可以使用以下经验法则来预测最佳的表访问顺序 :
将包含最低数量本地行的表作为外层表。
本地行的数量是指最大过滤因子过滤本地谓词之后所剩余的行数。
经验法则忽略了以下因素
- 排序。在我们的案例中，ORDER BY IEUR DESC所带来的排序只能通过把INVOICE表作为外层表来避免。而INVOICE表正巧含有最低数量的本地行，但是显然，情况并不总会如此。
- 很小的表。非常小的表及其索引可能长期存在于数据库的缓冲池中，至少在一个连接查询中，没有页会被读取多次。在这样的表和索引上进行随机读取所耗费的时间小于0.1ms，至少在页被第一次读取之后是这样的。所以，当这样的表不是外层表时，对其大量的随机读取也不会称为问题。
- 聚簇比例。索引中行的顺序和表中行的顺序的关联性(对于聚簇索引而言，该关联性在表重组后为100%)，可能会影响对最佳访问顺序的选择，当然，除非索引是宽索引。
最好的基于成本的优化器在进行路径选择时会把这些因素考虑进来。因此，他找出的访问顺序可能比我们基于本地行的数量的经验所得出的结果更优。
为什么在基于本地行数量的经验法则中使用最大的过滤因子。这样做只是因为把过滤因子陷阱的情况考虑进来，那么评估过程就太耗时了。如果有一个可选方法避免排序，且程序不能在一个事务中读取所有的行，那么这种简化无疑增加了不恰当建议的风险。但无论如何，基于假设的访问顺序进行索引设计有可能能够提供足够的性能，即使该访问顺序不是最优的。
当我们为一个连接查询设计索引的时候，我们该从哪里开始?理论上讲，我们应该为所有有可能的访问路径设计最好的索引，然后让优化器去选择。然后，我们再删除无用的索引和索引列。然而这样太耗时间了，尤其是在连接涉及的表多余两张时。另外，优化器所做的选择仍然会依赖于输入的值。基于优化器的索引设计工具解决了第一个问题，但没有解决第二个。他们的方案的质量取决于对过滤因子的假设，而这转而又依赖于谓词中绑定变量的输入值。
幸运的是，在大部分情况下，经验法则能够给出令人满意的结果。而且通常情况下，由于最佳的表访问顺序非常明显，我们甚至无需计算本地行的数量。
关键在于，在为连接查询设计索引的时候，要把所假设的连接方法和表访问顺序记录下来。然后，我们就能设计索引了，就像是已经编写好了使用单游标来取代连接游标程序一样。一种常见的错误是在没有涉及连接方式和表访问顺序的确定的访问路径假设情况下进行索引设计。仅仅在连接谓词和本地谓词上有索引是不够的，这往往会导致一些冗余的索引。另外，在一个嵌套循环连接中，内层表通常需要有好的宽索引且以连接谓词列作为前导列。
合并扫描连接和哈希连接
当我们分析用例学习中程序A和程序B的时候，我们发现，对内层表的大量随机访问导致使用理想索引带来的好处非常有限。合并扫描连接和哈希连接的一个主要好处就是能够避免这个问题。
合并扫描连接
执行过程如下
- 执行表或索引扫描以找出满足本地谓词的所有行
- 随后可能会进行排序，如果这些扫描未按所要求的顺序提供结果集。
- 对前两者生成的临时表进行合并
在以下情况下，合并扫描会比嵌套循环快。
- 用于连接的字段上没有可用的索引。在这种情况下，若使用嵌套循环，那么内层表可能需要被扫描很多次。在实际情况中，用于连接的列上面没有索引的情况很少见，因为大部分连接谓词都是基于“主键等于外键”这一条件的，就像我们的案例中的一样，CUST.CNO = INVOICE.CNO。
- 结果表很大。在这种情况下，若使用嵌套循环连接，可能会导致相同的页被不断的重复访问。
- 连接查询中不止一张表的过滤因子很低。如我们所见，嵌套循环可能导致对内层表(或者内层表索引)的大量随机访问。
在通过案例对比嵌套循环连接和合并扫描连接之前，我们先通过一个简单的例子来看看合并扫描连接具体要执行哪些步骤，以及我们如何使用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 CURSORJCUST : 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 |
|---|---|---|---|
| 理想索引 | 35min | 10min | 3.5min |
| 理想索引 | 17min | 3.5min | 1.8s |
| 理想索引，理想程序(+)，多屏结果数据 | - | 2s | - |
| 理想索引，理想程序(+)，单屏结果数据(FF缺陷) | - | 3.5min | - |
| BJQ理想索引，理想程序(+)，单屏结果数据(FF缺陷) | - | 0.2s | - |
结果很清楚的显示，在理想索引条件下使用MS/HJ是最好的访问路径，他不需要我们将策略改为只显示一屏数据或使用BJQ方法。采用这一方式能获得很好性能的原因有两个
- 它避免了我们在前台循环连接中遇到的大问题---对内层表或其索引的随机访问。
- 在当前硬件条件下，顺序访问的速度已经非常快了。
尽管性能有了巨大提升，单近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性能的表设计问题。
冗余数据
有两种通过冗余数据优化连接速度的方法
- 将某列拷贝至依赖表(向下反范式法)。
- 将汇总数据添加至父表(向上反范式法)。
向下反范式化
在我们的案例研究中，我们引入向下反范式化来消除大量对内层表(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，则该客户拥有至少一张大额发票。显然，这是一个笨拙的方法，原因有二 :
- 当对INVOICE表的数据进行删除或插入操作时，维护CLARGE列的工作并不简单。
- 修改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
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