3月29日 理解索引（2）反转键索引的误区

昨天我们回顾了索引的一些基础知识，今天我们需要了解一些索引优化相关的知识。首先我们从索引的分类来研究一下索引的主要种类以及各类索引在使用时的一些要点。

首先我们来看看最常见的B树索引，B树索引适用于几乎所有的场合，也是系统中使用最为广泛的索引形式。实际上我们所说的普通索引，反转键索引、降序索引、函数索引等都是B树结构的，其物理存储结构是完全相同的。与之相对应的位图索引是完全不同的存储结构，位图索引不是树状结构，没有枝节点，只有叶节点。对于B树索引的操作可以进行索引唯一性扫描、索引范围扫描、快速索引全扫描和索引全扫描，而对于位图索引的访问方式只有一种，就是索引全扫描。在使用位图索引的时候，只有对索引完全扫描一遍，才能找到所有的所需要的行。

从昨天的知识点我们知道，索引是一个树状的结构，组织形式是一颗扩展了的B树，和普通B树不同的是，这棵B树的所有叶节点上有一条双向链，称为叶节点链。这条双向链是根据索引键值的大小进行排序的。这条双向链的存在十分关键，这是实现索引范围扫描的最关键的技术。当进行索引范围扫描时，首先通过B树的定位算法，从根开始，找到范围扫描起始键值的位置，然后从这个位置开始，通过叶节点链按照升序或者降序的方式扫描相关的叶节点，直到找到超出范围扫描范围的键值为止。

最为普通的索引是按照键值升序排列的，索引树的右面的枝叶的键值总比左边的大。而如果我们设计了降序索引，那么情况正好倒过来，索引左面的枝叶的键值总比右面的大。

函数索引是一种特殊的B树索引，引入函数索引的目的是解决那些在使用过程中，必须在字段上做函数运算的情况。一般情况下，我们在编程时都会建议开发人员不要在WHERE条件中的表字段上使用函数，因为这样我们无法为其设计索引。不过事实上，我们无法杜绝这样的函数的存在。比如说，我们必须从某个人字段取第二和第三位进行比较：WHERE substr(id,2,3)='ID'，如果这样的查询条件放弃函数的话，程序员的处理将十分复杂。函数索引为这种情况提供了很好的帮助，如果这个查询条件使用索引效果较好的话，我们可以在ID字段上创建一个以函数substr(id,2,3）为键的B树索引。事实上，在绝大多数应用系统中,函数索引都是不可避免的，不过不幸的是，在我做过的优化项目中，我基本上没有看到过用户在使用这种索引。

接下来我们来讨论一下反转键索引（reverse key index），这是一种十分著名的索引，反转键索引是在存储键值的时候，先将键值进行翻转。比如'1234'存储在索引中的键值是'4321'。设计反转键索引的目的是解决索引的热块冲突问题。索引块出现热块冲突是在性能优化时经常会碰到的问题，比如一个主键是通过sequence生成的，那么主键索引就可能成为热块。这种情况下，如果我们确定针对主键的查询不存在或者很少有索引范围扫描，那么我们可以考虑使用反转键索引来解决主键的热块冲突问题。反转键索引解决索引热块冲突的原理很简单，就是通过键值的反转，打乱索引数据块中的数据组织，从而将热点数据分散到不同的索引数据块中。

不过除了解决热块冲突的问题外，DBA界还流传着反转键索引可以解决 like '%abc'无法随用索引的问题。粗想起来，还确实是这么回事，like '%abc'这样的条件，由于通配符在第一个字符，因此这样的查询条件，无法进行索引范围扫描，因此一般情况下使用全表扫描比较合适。不过在某些情况下，如果表十分巨大，这种全表扫描成本太高，如果能使用索引就好了。而反转键索引正好在存储键值的时候是反转过来的，1abc,2abc在索引键里的存储为abc1,abc2，这种情况下，做就可以通过范围扫描将符合条件的记录找出来吗？这个解释似乎是很合理，我也曾经被这个理论所蒙蔽过一段时间，直到有一天我自己做了一个实验，才发现问题远非那么简单。下面我们来回顾一下这个实验。首先我们创建测试表：

DROP TABLE TINDEX;

CREATE TABLE TINDEX as SELECT DISTINCT OBJECT_NAME,OBJECT_ID,OBJECT_TYPE,CREATED,STATUS,TEMPORARY,TIMESTAMP,'ABCDEFGHIJKLMNOPQRSTUVWXYZ1234456' abc 

from dba_objects;

INSERT INTO TINDEX SELECT DISTINCT OBJECT_NAME,OBJECT_ID,OBJECT_TYPE,CREATED,STATUS,TEMPORARY,TIMESTAMP,'ABCDEFGHIJKLMNOPQRSTUVWXYZ1234456' abc 

from dba_objects;

create index  idx_tindex_name on tindex(object_name ) reverse;

然后做一次表分析：

exec DBMS_STATS.GATHER_TABLE_STATS(ownname=>'scott', tabname=>'tindex', estimate_percent=>30, -

cascade=>true, degree=>2);

似乎一切都准备好了，下面我们来测试一下反转键索引是否真的能够解决like语句的问题：

SQL> set autotrace traceonly

select *  froM tindex where object_name like '%TINDEX';

SQL> 

Execution Plan

----------------------------------------------------------

Plan hash value: 2264840918

----------------------------------------------------------------------------

| Id  | Operation         | Name   | Rows  | Bytes | Cost (%CPU)| Time     |

----------------------------------------------------------------------------

|   0 | SELECT STATEMENT  |        |  5297 |   553K|   103   (3)| 00:00:01 |

|*  1 |  TABLE ACCESS FULL| TINDEX |  5297 |   553K|   103   (3)| 00:00:01 |

----------------------------------------------------------------------------

Predicate Information (identified by operation id):

---------------------------------------------------

   1 - filter("OBJECT_NAME" LIKE '%TINDEX')

Statistics

----------------------------------------------------------

          1  recursive calls

          0  db block gets

       1717  consistent gets

          0  physical reads

          0  redo size

        939  bytes sent via SQL*Net to client

        400  bytes received via SQL*Net from client

          2  SQL*Net roundtrips to/from client

          0  sorts (memory)

          0  sorts (disk)

          2  rows processed

似乎索引并没有被自动使用，我们使用hint强制索引看看：

SQL> select /*+ INDEX(TINDEX idx_tindex_name ) */ *  froM tindex where object_name like '%TINDEX';

Execution Plan

----------------------------------------------------------

Plan hash value: 2021627753

-----------------------------------------------------------------------------------------------

| Id  | Operation                   | Name            | Rows  | Bytes | Cost (%CPU)| Time     |

-----------------------------------------------------------------------------------------------

|   0 | SELECT STATEMENT            |                 |  5297 |   553K|  5548   (1)| 00:00:54 |

|   1 |  TABLE ACCESS BY INDEX ROWID| TINDEX          |  5297 |   553K|  5548   (1)| 00:00:54 |

|*  2 |   INDEX FULL SCAN           | IDX_TINDEX_NAME |  5287 |       |   520   (1)| 00:00:05 |

-----------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):

---------------------------------------------------

   2 - filter("OBJECT_NAME" LIKE '%TINDEX')

Statistics

----------------------------------------------------------

          1  recursive calls

          0  db block gets

        520  consistent gets

          0  physical reads

          0  redo size

        939  bytes sent via SQL*Net to client

        400  bytes received via SQL*Net from client

          2  SQL*Net roundtrips to/from client

          0  sorts (memory)

          0  sorts (disk)

          2  rows processed

虽然使用了索引，但是扫描方式是全索引扫描，而不是我们期待的索引范围扫描。看样子反转键索引并不能解决这个问题，我以前是被忽悠了。于是我继续做实验：

SQL> create index idx_tindex_func on tindex(reverse(object_name));

Index created.

SQL> exec DBMS_STATS.GATHER_TABLE_STATS(ownname=>'scott', tabname=>'tindex', estimate_percent=>30, -

> cascade=>true, degree=>2);

PL/SQL procedure successfully completed.

SQL> select *  froM tindex where reverse(object_name) like 'XEDNIT%';

Execution Plan

----------------------------------------------------------

Plan hash value: 1286384425

-----------------------------------------------------------------------------------------------

| Id  | Operation                   | Name            | Rows  | Bytes | Cost (%CPU)| Time     |

-----------------------------------------------------------------------------------------------

|   0 | SELECT STATEMENT            |                 |     4 |   436 |     7   (0)| 00:00:01 |

|   1 |  TABLE ACCESS BY INDEX ROWID| TINDEX          |     4 |   436 |     7   (0)| 00:00:01 |

|*  2 |   INDEX RANGE SCAN          | IDX_TINDEX_FUNC |     4 |       |     3   (0)| 00:00:01 |

-----------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):

---------------------------------------------------

   2 - access(REVERSE("OBJECT_NAME") LIKE 'XEDNIT%')

       filter(REVERSE("OBJECT_NAME") LIKE 'XEDNIT%')

Statistics

----------------------------------------------------------

          1  recursive calls

          0  db block gets

          6  consistent gets

          0  physical reads

          0  redo size

        939  bytes sent via SQL*Net to client

        400  bytes received via SQL*Net from client

          2  SQL*Net roundtrips to/from client

          0  sorts (memory)

          0  sorts (disk)

          2  rows processed

这才是我们所需要的效果，通过reverse函数，然后将%TINDEX反转为XEDNIT%，才真正的解决了这个问题，这个SQL的开销是原SQL的几百分之一。实际上这种解决方案只能在修改应用的前提下实现，不如使用反转键索引这么简单，而且用途广泛。不过我们也终于通过实验纠正了一个错误的，流传甚广的误解。我在网上通过google查阅了大量的关于此话题的英文资料，终于明白了这个误解的来源，最初的时候，网上确实有一篇文章，介绍使用reverse函数解决这个问题，后来这篇文章在被转载的时候

SELECT * 

FROM customer

WHERE Cust_Name LIKE '%Vilas%'

修改为：

SELECT * 

FROM customer

WHERE reverse(Cust_Name) LIKE '%saliV%';

被错误的写成了：

SELECT * 

FROM customer

WHERE Cust_Name LIKE '%saliV%';

以此版本为蓝本，终于引发了通过反转键索引优化like操作这个错误的观点。由此可见，网络上的知识，不经过自己验证就全盘吸收是多么危险。

不过以Oracle反转键索引的存储结构，确实具备对Like条件做范围扫描的基础，只不过这样的扫描，和以往Oracle提供的任何一种索引扫描技术都不相同，是一种全新的索引扫描方式。也许在Oracle 12或者13里，真的会出现类似的功能呢，Oracle的美工新版本给人带来的惊喜一直都是出乎大多数人的意外的。