内容简介:作者 | 杨碧佳后端攻城狮,
作者 | 杨碧佳
后端攻城狮, 关注算法和中间件,喜欢探索各种技术。
引言:
我们常常会在工作中用到索引,因为我们觉得在大量的数据下,索引会让数据库查询变得更快,但是我们往往不知道,我们的索引还可以进行进一步的优化,让查询速度变得更快。本文会从一些基础理论讲起,提供一种近乎程式化建立索引的方法。
一、 索引相关定义
物理结构
表和索引都被存储在页中,页的大小一般为 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
-
取出等值谓词作为起始列,任意顺序
-
以正确顺序添加 ORDER BY 列,有 DESC 则加上,忽略 1 步中已经添加的列
-
以任意顺序将 SELECT 语句中其余的列添加至索引中,不易变的列放在前面
eg.
(CITY, FNAME, LNAME, CNO)
-
Method A : 如果一个程序取出结果集的所有行,那么 A 可能和 B 一样快,甚至更快。
增加了排序操作,主要看数据排序时间的占 CPU 开销多少。数据量大的时候先减少索引片的厚度,再进行排序,后续的操作会在更小的数据量下进行,时间开销自然变小。
-
Method B : 如果一个程序只需获取能够填充满一个屏幕的数据量,比如只取查询语句结果数据的前 20 条数据,那么B可能会比A快很多。
访问过程中没有排序的话,数据库管理系统只要一次一次地读取数据行就行了。
三、 合适设计理想索引
并不是所有的查询语句都需要设计理想的最佳索引。
根据上面说的,为每个查询设计最佳索引的过程是机械式的,只要给出以下内容就可以自动完成整个过程:
-
查询语句
-
数据库统计信息(行数,页数,列值分布等等)
-
对于每一个简单谓词或组合谓词最差情况下的过滤因子
-
已经存在的索引(只是避免生成重复索引)
多余的索引
我们为查询语句设计了一个最佳索引后,去看一下已经存在的索引是很有必要的,我们不可能会完全按照机械式的方式去创建索引。有可能某一个已经存在的索引几乎和理想索引差不多好用,特别是打算在这个已有索引的最后添加一些列的情况下。
当分析一个已经存在的索引对一个新的查询有多大用处,是否真的需要新建理想索引时,可以从这三种多余索引来看,考虑一种新的折中的索引方式:
-
完全多余的索引
一个查询包含 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 个不同的查询,且为每一个索引都设计了最佳索引的话,那么即使没有重复索引,该表上最终也可能有非常多的索引。这样一来表的插入,更新和删除操作就会变得很慢。我们一般从三个方面来讨论,建立一个新的索引要付出的代价。
1. 响应时间
当我们向表中添加一行数据,它必须在每一个索引上都添加相应的行,在一个索引上添加一行耗时 10ms (从磁盘读取一个叶子页),在 10 个索引上每个索引添加 20 行就耗时 1.8s (主键索引维护在同一个索引页)。
所以从响应时间的角度来看,在一个拥有许多索引的大表上进行事务操作,可能是无法忍受的。
2. 磁盘负载
由于数据库的异步写不会影响到事务响应时间,但是这些写会增加磁盘负载。在缓冲区中被修改过的页是会迟早被写到磁盘上去的,当一张表插入或更新频率较高,缓冲区空闲空间变少或脏页过多,会使得从缓冲区写回磁盘的操作也会变频繁,这时带来的磁盘压力也会变大。而且当索引较多时,向表中插入或更新多行数据也会同时更新多个索引页上的行,磁盘繁忙时间会很久。
从磁盘负载的角度来看,一个插入频度较低的表,能够容忍在表上建许多索引,索引数量取决于插入事务对响应时间的要求。如果磁盘负载是问题,较明显的解决办法是 尝试合并索引 。显然,一个有 10 个列的索引比两个各有 6 个列的索引所引起的磁盘负载要小。
3. 磁盘空间
如果一张表中有 1000 万行以上的数据,多个索引的磁盘空间成本可能会成为一个问题。即使我们不考虑磁盘空间的成本问题,随着索引变大,缓冲池或磁盘缓存也应随之增大,否则存在磁盘上会使非叶子页的 I/O 量会增加,所以非叶子页的内存开销也不少。
结语:
虽然三星索引可以让我们建立一个确定的索引组织方式,但我们并不能完全依赖它,这只是一个方法论,对我们建立索引的实践起到指导作用。就比如可能会因为实际应用环境的数据的特殊性,而产生一种并非三星索引的特殊的索引排序方式,它会有更高的性能,所以我们在建立索引的过程中,对索引产生的性能优化进行一个大概的预估也是重要的一步。
全文完
以下文章您可能也会感兴趣:
我们正在招聘 Java 工程师,欢迎有兴趣的同学投递简历到 rd-hr@xingren.com 。
杏仁技术站
长按左侧二维码关注我们,这里有一群热血青年期待着与您相会。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。