《高并发Oracle数据库系统的架构与设计》一2.2 索引与排序

本节书摘来自华章出版社《高并发oracle数据库系统的架构与设计》一书中的第2章，第2.2节，作者 侯松，更多章节内容可以访问云栖社区“华章计算机”公众号查看

通过2.1节的介绍，我们知道了索引扫描是可以优化排序的，索引扫描输出的结果是有序排列的（索引快速全扫描除外），为什么会这样呢，难道索引输出的时候自动做了一次排序吗？其实不是的，应该说索引本身就是一种有序排列的数据结构。索引在建立条目的时候，就已经将其按照索引列的顺序进行顺序存储，这和表的存储结构是不一样的。

之所以将排序这个话题单拿出来讲，主要是为了说明一个排序的道理。很多人可能有意无意地忽略了sql语句中的排序这块，其实很多时候，避免排序可以大大提升sql语句的性能，这是非常重要的一点。不论作为开发者还是管理者，都需要时刻保持对排序的敏感。很多时候，临时表空间使用率超限，查询速度太慢都可能是因为排序太多，pga内存排序区装不下，不得不放到临时表空间去排序，临时表空间是磁盘排序，在速度上和内存排序是无法比拟的。

本节将围绕索引这种有序结构与排序优化展开介绍，让读者充分了解到索引对优化排序的作用。

我们已经了解到b树索引是一种典型的树形结构，其包含的组件主要是：

根节点：只有一个根节点，是位于树的最顶端的分支节点；

分支节点：存储指针指向索引里其他的分支节点或者叶节点；

叶子节点：存储索引条目（包括索引条目头信息、索引键值长度、索引键值，以及rowid相关信息）直接指向表里的数据行。

下面通过一张示意图来描述一下这种内部结构，如图2-7所示，就分支节点块（包括根节点块）来说，其所包含的索引条目都是按照顺序排列的（默认是asc升序排列，也可以在创建索引时指定为desc降序排列）。每个索引条目均由两个字段组成，第一个字段表示当前该分支节点块下所指向的叶节点块中所包含的开始键值（对升序排序的索引来说，就是最小键值），第二个字段为指向叶节点块地址的指针。在一个分支节点块中所能容纳的记录行数由数据块大小以及索引键值的长度决定。在本例中，对于根节点块来说，包含三个指针，分别为（1 b1）、（100 b2）、（200 b3），它们指向三个分支节点块。其中的1、100和200分别表示这三个分支节点块所指向的开始键值，而b1、b2和b3则表示所指向的三个分支节点块的地址。

对于叶子节点块来说，其所包含的索引条目与分支节点一样，都是按照顺序排列的。每个索引条目也包含两个字段。第一个字段表示索引的键值，对于单列索引来说是一个值，而对于复合索引来说则是多个值组合在一起的。第二个字段表示该键值所对应的数据行的rowid，该rowid是数据行在表里的物理地址。

当有新的索引键值插入的时候，索引会判断新键值的排序位置。如果新键值大于目前索引存储的最大值，则会将新键值插入到最右侧的叶节点块（l8）上，如果新键值为198，则会将其插入到节点块l6上。如果对应叶节点块已满，则会分裂出新的叶节点块，分支节点块满了，同样会分裂出新块。

索引这个特点是不同于表的，dml操作过程中，对索引维护成本是比较大的，所以我们需要定期地去分析索引的结构，保证其高效支持查询的能力。

在使用索引优化查询的过程中，一方面是通过索引扫描快速定位返回行的rowid，另一方面则是利用索引的有序结构避免一些不必要的排序操作。

下面我们将结合2.1节中介绍的五种索引扫描方式来讨论一下使用索引扫描输出结果集的排序问题吧。

索引唯一扫描：这种扫描方式，输出的结果集只有一个记录行，就不存在排序的问题；

索引范围扫描：该方式是索引排序最典型的应用，其输出结果集都是有序的（升序输出还是降序输出取决于索引创建时的参数，默认为升序）；

索引全扫描：这个方式可以看做是全范围的扫描，其效果和索引范围扫描是一样的；

索引快速全扫描：从字面上来看，和索引全扫描非常相像，但两者是完全不同的两种方式，快速全扫描的输出结果集是不排序的，如果where子句中要求order by，则需要额外的排序开销；

索引跳跃扫描：可以视作是分拆成多个逻辑子索引后的index combine扫描，对于逻辑子索引的扫描即为索引范围扫描或者索引全扫描。

下面我们通过几个实例对比来具体分析一下几个比较典型的扫描方式的排序情况：索引范围扫描、索引快速全扫描、索引跳跃扫描。

1.?索引范围扫描排序

首先，要创建一个测试表，2.1节的alex_t01表都是顺序插入的连续性数据，这对于排序的识别有些困难，我们重新创建一个表alex_t02，修改b列和c列的数据为随机数插入。具体步骤和sql语句如下所示：

步骤1　创建表alex_t02，及主键索引和普通索引：

步骤2　初始化数据，随机插入10万行数据：

步骤3　收集表和索引的统计信息及直方图信息：

不进行排序操作，先来对比一下全表扫描和索引扫描的输出结果。如下例所示，可以看到，索引扫描输出的结果是有序的（对c列采用默认的升序排列），全表扫描则是无序的（其结果的顺序为数据实际入库的顺序）。

如果需要全表扫描的输出与索引扫描一致，就需要进行一次额外的排序（order by c）操作。如下所示，在sql语句执行的统计信息中多了一次内存排序操作：

如果我们使用的是索引范围扫描的话，即使我们添加了order by子句，声明需要排序操作，但是cbo优化器也会忽略掉这个要求，在执行后的统计信息中也没有出现任何排序，如下所示：

在索引扫描取数的时候，对索引列进行order by是没有必要的（索引快速全扫描除外）。

2.?索引跳跃扫描排序

前面介绍过索引跳跃扫描其实是将复合索引打散成逻辑上的子索引，再进行扫描。基于这个原理，我们可以想象到，子索引和子索引之间的关系是按照复合索引的前导列的顺序有序组织的，子索引内部则是按照子索引的键值的顺序有序组织的。各个子索引对应输出的子结果集也具有同样的顺序关系。

在下面的例子中，order by子句要求的排序方式为（a，b），这和复合索引的默认顺序是一致的，所以子结果集直接输出即可，不必额外的排序，最终看到的统计信息中的排序次数为0。

如果order by子句要求的排序方式和复合索引结构的默认顺序不一致呢？如下例所示，b列的数据是随机生成的，本是无序的。在各个子结果集内部，由于索引有序结构的关系，b列是有序排列的，但在各个子结果集之间比较，b列则是无序的。比如：子结果集（a=0）中可能存在b={1,2,3,4}，子结果集（a=1）中可能存在b={1,3,5,6}，如果按照复合索引的默认顺序（order by a, b）输出则是b={1,2,3,4,1,3,5,6}，如果按照子索引键值顺序（order by b）输出，则是b={1,1,2,3,3,4,5,6}，后者的输出意味着需要一次额外的排序。

3.?索引快速全扫描排序

现在我们知道了对于复合索引来说，order by子句要求排序的列正好在复合索引键上是可以避免不必要的排序的，但是这里也有一个例外，就是索引快速全扫描的情况。前面提到该扫描方式是不支持排序输出的，如果指明order by的话，会需要额外的排序操作，而且此排序的cost开销非常大，如下例所示：

细心的读者可能已经注意到，上例中添加了hint关键字强制执行计划，而且执行计划中的cost开销是比较大的，如果去掉hint呢？结果如下：

从执行计划中可以看到，快速全扫描被全扫描代替了，cost开销反而降低了。一般情况下，快速全扫描的效率是要比全扫描高的，此时cbo为什么反而选择全扫描的方式呢？原因就出在排序上。

对于大结果集的输出，尽量避免不必要的排序，如果能用索引排序进行优化，也请尽量使用。

看到这里，有的读者可能会问到，我们一直都是在说升序的情况，如果要求降序查询呢，情况是否会不一样呢？是的，会不一样。我们接下来将围绕这个索引降序的话题来说一说。

我们可以从单列索引和复合索引两个维度来进行阐述。当然，在阐述之前，先介绍一个新的概念，就是“降序索引”。

1.?降序索引

什么是降序索引呢？其实降序索引也是b树索引，只是将通常意义上的b树索引中的存储方式从升序变成了降序，如果应用场景中经常会出现降序排序的查询，建立一个降序b树索引不失为一个很好的选择。

默认情况下建立的b树索引均为升序（asc）索引，语句如下：

如果需要建立降序（desc）索引，只需要在索引列后注明“desc”关键字，语句如下：

2.?单列索引的降序

对于单列索引来说，进行升序查询的时候，其实就是按照从左到右的顺序逐一扫描索引的叶节点块。这个动作是否可以反过来进行呢，从右到左地去扫描？答案是肯定的，这样就是降序查询的优化了，即使我们建索引的时候是按照升序来建的，cbo优化器也可以自动进行降序查询优化。

下面是一个降序查询的例子，在升序索引上的扫描，不论是升序查询，还是降序查询，都没有额外的排序操作，而且cbo计算出来的cost开销也是一致的。

同理可知，如果我们建立的是降序索引，cbo优化器也会自动对升序查询进行优化，同样不会有额外的cost开销。但是，降序索引上的升序扫描会被识别为降序操作。

所以，对于单列索引来说，没有必要刻意创建降序索引，默认的升序索引是可以支持降序查询的，并且自动优化，不会产生额外的cost开销。

3.?复合索引的降序

如果说升序索引上进行降序查询可以自动优化，那还需要降序索引干什么呢？它的作用主要表现在复合索引的应用上。

我们通过几个例子来分析一下其应用场景，先清理掉之前的索引，在(b, c)列上创建一个复合索引。sql语句如下所示：

此时，在(b, c)列上进行(b asc, c asc)的排序操作，很显然是不会有额外排序的，复合索引两个索引列都是升序组织起来的。示例如下：

将排序条件修改一下，(b desc, c asc)，b列降序，c列升序。先来想象一下，此刻b列需要降序，cbo优化器可以自动优化，让b列的从大到小地读，也就是叶节点块从右往左地扫描，这没有问题。但不幸的是，c列则需要从左往右地扫描，这就发生矛盾了。解决矛盾的方式就是额外进行一次排序，示例如下所示：

我们说一切应从适合应用场景出发，如果应用场景中，经常要求(b desc, c asc)的排序方式，那我们就应该创建一个如下的降序索引：

新的索引创建完成，再来执行一下上面的两个sql语句看看。此时的情况完全反过来了，(b desc, c asc)没有额外排序，而(b asc, c asc)有了。

此处，我们不妨再引申一下。现在的索引顺序是(b desc, c asc)，如果sql语句要求的排序输出的方式变为(b asc, c desc)呢？如果你能像刚才一样想象一下，就不难得到答案。此时，b列和c列都是要求从右往左地扫描索引叶节点块，cbo优化器可以通过index range scan descending的方式优化执行计划，其过程不会有额外的排序和cost开销。示例如下所示：

降序索引在日常工作中，尤其是做报表和大数据分析应用的sql语句，应该能发挥比较积极和重要的作用。index range scan descending的扫描优化方式也不能忽略，这种优化方式对于index full scan同样适用。

降序索引和降序扫描在索引的排序应用中有积极的意义。根据实际应用情况，选择合适的索引组织形式，往往可以事半功倍的。

前面的章节中，我们提到count()的聚合查询可以利用索引扫描来规避回表取数的动作，而且索引扫描过程也可以选择index fast full scan的高效方式。现在，我们再来说说另一种聚合查询min()与max()。这个和索引有关系吗，能用到索引进行优化吗？也许有读者会说：“是的，但索引列必须要有not null的约束，或者在查询过程中过滤掉null。”这个回答是值得鼓励和肯定的。但是，另一个问题出来了，它能用到哪种索引扫描方式呢？像count()一样，index fast full scan吗？min()与max()是依赖于顺序的，能接受不排序的输出吗？

下面的例子告诉我们，在主键索引列上的min()与max()，是可以用到索引快速全扫描的，而且cost下降比较明显，达到了优化的目的。

我们说主键索引的键值具有唯一性，而且顺序排列，这固然能用到index fast full scan，而如果是有重复性的非唯一索引呢？就只能走index full scan了，甚至可能会因为cost太高，而选择走全表扫描。

不知道有没有读者还沉浸在我们之前的想象中呢？如果有，相信你已经想象到了更好的优化方法。我们都知道索引的树形结构，各层节点块都是有序排列的，默认升序的情况下，从左到右即是从小到大，min()就是最左叶节点块，max()则是最右叶节点块。想象完成，通过实例来验证一下吧。

从下面的例子可以看到，执行计划变成了索引全扫描的方式，但是多了(min/max)的字样。这是cbo优化器对索引全扫描的一个优化，其间蕴藏着一个stopkey的机制，简单来说，就是扫描到需要的东西就退出，不继续扫描了。执行计划中index full scan (min/max)的cost开销只有2，较之index fast full scan更优。

细心的读者应该注意到了，上面的sql语句只做了min()，并没有同时取min()与max()，同时取的话，是什么效果呢？下面的例子告诉我们，仍然会走index fast full scan。原因很简单，索引扫描只能是单向的扫描，要么从左到右，要么从右到左，现在是需要同时返回min()和max()，如果stopkey在取到min()退出，就取不到max()，反之亦然。所以，index full scan (min/max)就未被使用。

但事实上，从cost计算来看，即使单独取一次min()，再单独取一次max()，开销之和都较索引快速全扫描要小。我们可以把sql语句改写如下：

min()与max()通常是最常用的高频sql写法之一，特别是在一些计费系统和报表系统的应用中，这样的写法比比皆是。希望读者能充分利用index full scan (min/max)这一蕴藏stopkey机制的特性来提高查询性能，甚至可以通过改写sql，将原本用不到该特性的查询利用上，其间尽量保证该列为not null。

再多说一句关于stopkey特性的应用，在top-n的查询或者分页查询中，它的作用是不容小觑的。示例如下所示：

综上所述，索引的扫描和快速取数往往是大家建索引的目的，甚至有的时候会被认为是唯一的目的，而忽略掉了索引对排序的意义，因此丢失了原本应该更优的性能。通过本节的介绍，希望能对读者有所启示，能够更全面地了解和思考索引的设计和使用。