前瞻性的索引设计

发现不合适的索引

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

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是最差输入下的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是最差输入下的QUBE值，I = 插入，D = 删除，U = 更新

何时使用QUBE

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

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

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