数据库索引优化

作者 | 杨碧佳

后端攻城狮， 关注算法和中间件，喜欢探索各种技术。

引言：

我们常常会在工作中用到索引，因为我们觉得在大量的数据下，索引会让数据库查询变得更快，但是我们往往不知道，我们的索引还可以进行进一步的优化，让查询速度变得更快。本文会从一些基础理论讲起，提供一种近乎程式化建立索引的方法。

一、 索引相关定义

物理结构

表和索引都被存储在页中，页的大小一般为 4KB 或者 8KB。

当表和索引被加载或重组时，每个页会留出一定比例的空闲空间，以满足向其添加新的表行或索引行的需求。DBMS 的缓冲池和 I/O 活动都是基于 页 的。

每个 DBMS 都会根据对象类型（表或索引）及页的大小拥有多个缓冲池。每一个缓冲池都足够大，可能存放成千上万的页。缓冲池管理器将尽力确保经常使用的数据被保存在池中，可以避免一些不必要的磁盘 I/O。

这一策略的有效性对于 SQL 语句的性能表现至关重要。

谓词

简单谓词和复杂谓词

WHERE 字句中的每个条件称为一个谓词。

过滤因子

描述了谓词的选择性，即表中满足 谓词条件的记录行数 所占的 比例 。

多个匹配谓词组合成的 组合谓词的过滤因子 （由单个谓词的过滤因子乘积得到）越小越好，可以减少索引结果集的行数，增加查询效率。最差的过滤因子代表了索引查询响应的最长时间，我们一般使用最差的过滤因子来衡量组合谓词的可行性。

过滤因子（FF）= 结果集的数量 / 表行的数量
平均过滤因子 = 1 / 不同列值的数量

索引片及匹配列

第一个索引列定义一个 索引片 ，如果 WHERE 字句中有第二个列，而这个列也在索引上，从而使得这两个列能够一同定义一个更窄的 索引片 ，这两个列叫做 匹配列 ，定义的索引片叫窄索引。

这样不仅显著减少了索引的处理量，更是减少了对标进行同步读的次数。

索引过滤及过滤列

并不是所有的索引列都可参与索引片的定义。

所有的匹配列参与匹配过程 —— 定义索引片。

过滤列参与了索引片的过滤过程，无法参与匹配过程，只能使索引片更厚，因为范围谓词定义的索引片中有很多无用数据，加长了索引扫描时间。

如何判断一个谓词能否参与匹配和过滤呢？

• 范围谓词后面的列都是非匹配列，如果非匹配列足够简单则为**过滤列**

• WHERE 子句中从左至右有一个足够简单的谓词与之对应，该列则称为**匹配列**

二、 三星索引

三星索引是对于一个查询语句可能最好的索引。通过三星索引，一次查询通常只需一次随机读（从磁盘读取到缓冲池）及一次窄索引的扫描。

SELECT CNO, FNAME
FROM    CUST
WHERE  LNAME BETWEEN :LNAME1 AND :LNAME2
          AND
          CITY = :CITY
          ORDER BY FNAME

星级评定

• 索引中包含 WHERE 子句中所用到的所有列，查询相关的索引行是相邻的，标记上第一颗星。

这 最小化了必须扫描的索引片的宽度 。索引过滤可以确保回表访问只发生在所有查询条件都满足的时候。

构造 一星 索引满足条件：取出所有等值谓词的列（WHERE COL = …）作为索引最开头的列（任意顺序），我们将会有一个较窄的索引片，后面如果跟上范围谓词，将会使索引片更窄，范围谓词和等值谓词间就不能有其他索引列。

(CITY, LNAME, FNAME, …)

- 索引行的顺序与查询语句一致，标记上第二颗星。

这排除了 排序 操作。

构造 二星 索引满足条件：将 ORDER BY 的列放入索引中（不改变顺序，除去第一颗星加入的索引列）,这些列放在等值谓词前后都可以（因为这些列的索引可以使结果集以其顺序排列，而不需要额外排序），等值谓词值只有一个，也不会影响排序结果；但一定要放在范围谓词之前，范围谓词按顺序扫描后就变成了范围谓词的顺序，ORDER BY后的列就要进行排序操作。

(CITY, FNAME, LNAME, …)

• 索引行包含了查询语句中的所有列，标记上第三颗星。

这样列值都在索引中，不需要访问表，同步读也不会出现问题。

构造 三星 索引满足条件：将查询语句中剩余的列加到索引中去，列在索引中添加的顺序对查询语句的性能没有影响，但是将易变的列放在最后能够降低更新的成本。

(CITY, FNAME, LNAME, CNO)

可以看出，我们的理想索引一定能有第三颗星，但只能有第一颗或者第二颗星。因为第一颗星（等值谓词+范围谓词+其他索引列）和第二颗星的索引排列方式冲突（等值谓词+orderby列+范围谓词和其他索引列 or orderby列+等值谓词+范围谓词和其他索引列），所以只能选择一个。

设计最佳索引

Method A

1. 取出等值谓词作为起始列，任意顺序

2. 将选择性最好的范围谓词作为下一个列，只考虑不过分复杂的范围谓词

3. 以正确顺序添加 ORDER BY 列，有 DESC 则加上，忽略 1 和 2 步中已经添加的列

4. 以任意顺序将 SELECT 语句中其余的列添加至索引中，不易变的列放在前面

eg.

(CITY, LNAME, FNAME, CNO)

Method B

1. 取出等值谓词作为起始列，任意顺序

2. 以正确顺序添加 ORDER BY 列，有 DESC 则加上，忽略 1 步中已经添加的列

3. 以任意顺序将 SELECT 语句中其余的列添加至索引中，不易变的列放在前面

eg.

(CITY, FNAME, LNAME, CNO)

• Method A : 如果一个程序取出结果集的所有行，那么 A 可能和 B 一样快，甚至更快。

增加了排序操作，主要看数据排序时间的占 CPU 开销多少。数据量大的时候先减少索引片的厚度，再进行排序，后续的操作会在更小的数据量下进行，时间开销自然变小。

• Method B : 如果一个程序只需获取能够填充满一个屏幕的数据量，比如只取查询语句结果数据的前 20 条数据，那么B可能会比A快很多。

访问过程中没有排序的话，数据库管理系统只要一次一次地读取数据行就行了。

三、 合适设计理想索引

并不是所有的查询语句都需要设计理想的最佳索引。

根据上面说的，为每个查询设计最佳索引的过程是机械式的，只要给出以下内容就可以自动完成整个过程：

1. 查询语句

2. 数据库统计信息（行数，页数，列值分布等等）

3. 对于每一个简单谓词或组合谓词最差情况下的过滤因子

4. 已经存在的索引（只是避免生成重复索引）

多余的索引

我们为查询语句设计了一个最佳索引后，去看一下已经存在的索引是很有必要的，我们不可能会完全按照机械式的方式去创建索引。有可能某一个已经存在的索引几乎和理想索引差不多好用，特别是打算在这个已有索引的最后添加一些列的情况下。

当分析一个已经存在的索引对一个新的查询有多大用处，是否真的需要新建理想索引时，可以从这三种多余索引来看，考虑一种新的折中的索引方式：

• 完全多余的索引

一个查询包含 WHERE A = :A AND B = :B，另一个查询包含 WHERE B = :B AND A = :A ，那么生成 (A, B) 和 (B, A) 两个索引，如果没有其他查询语句包含A列或B列上的范围谓词的话，那么这两个索引其中一个就是完全多余的。甚至我们能够去质问业务为什么要设计这样的SQL。

• 近乎多余的索引

假设已经存在索引 (CITY, LNAME, FNAME, CNO) ，如果有一个新的查询语句包含现在的 4 个索引列，后面还多跟了 10 个其他的列，那么在创建了新的索引后，原来的索引应该被删除。

例如，由于使用 14 个列的索引，从中取出 4 个列的数据，CPU时间增长不多，由于顺序读的处理过程主要也是受CPU时间的限制，在性能上不会有很大的影响。

• 可能多余的索引

一个新的查询语句的设计理想索引是 (A, B, C, D, E, F)，而表上已存在的索引是 (A, B, F, C)，一般会在已经存在的索引后加上新增的两列D和E，成为 (A, B, F, C, D, E)。

理想索引可能有两方面优势：使查询拥有更多匹配列和避免排序。但这两个优势都受需要在索引片上扫描的行数的影响，往往新的索引是不需要的，在现有索引后加上新的列就足够了。

建新索引的代价

如果一个表上有 100 个不同的查询，且为每一个索引都设计了最佳索引的话，那么即使没有重复索引，该表上最终也可能有非常多的索引。这样一来表的插入，更新和删除操作就会变得很慢。我们一般从三个方面来讨论，建立一个新的索引要付出的代价。

全文完

以下文章您可能也会感兴趣：

• 缓存的那些事

• Java 并发编程 -- 线程池源码实战

• Lombok Builder 构建器做了哪些事情？

• WePY 2.0 新特性

• SSL证书的自动化管理

• 了解一下第三方登录

• 分布式 ID 生成策略

• 单元测试的实践之路

• 可线性化检查：与 NP 完全问题做斗争

• Java 类型系统从入门到放弃

我们正在招聘 Java 工程师，欢迎有兴趣的同学投递简历到 rd-hr@xingren.com 。