数据库索引笔记

Aug 4, 2018 10:18 · 2460 words · 5 minute read 数据库

表和索引的物理结构

表和索引行都存储在页中。页的大小一般为4KB/8KB,页的大小决定了一个页可以存放多少个索引行、表行。

对于一个唯一索引(如主键索引),一个索引行等同叶子页中的一个索引条目,字段的值从表中复制到索引上,并加上一个指向表中记录的指针。

聚集索引和辅助索引

  • 聚集索引:按照每张表的主键构造一颗B+树,同时叶子节点中存放的即为整张表的记录数据。
  • 辅助索引:叶子结点存放的是索引数据以及主键索引值。由于检索数据时,总是先获取到书签值(主键值),再返回查询,因此辅助索引也被称之为二级索引。
  • 覆盖索引:一个查询语句的执行只需要从辅助索引中就可以得到查询记录,而不需要查询聚集索引中的记录。

索引与匹配列/过滤列

存在索引

(A, B, C, D)

查询

WHERE A = :A
	AND B > :B
	AND C = :C

从开头到结尾依次检查索引列:

  1. WHERE子句中是否至少拥有一个足够简单的谓词与之对应,如果有,那么这个列就是匹配列,如果没有,那么这个列和后面的索引都是非匹配列。
  2. 如果该谓词是一个范围谓词,那么剩余的索引列都是非匹配列。
  3. 对于最后一个匹配列之后的索引列,如果拥有一个足够简单的谓词与之对应,那么该列为过滤列。

举例:A为等值谓词且为一个匹配列,因为B是范围谓词,所以C为非匹配列,但作为过滤列。

过滤因子

过滤因子=结果集的数量/表行的数量

最大过滤因子=最大结果集的数量/表行的数量

最大过滤因子表示了最差情况下的过滤因子,因此更具有代表性。

组合谓词的过滤因子

举例:

CITY = :CITY AND LNAME = :LNAME

如果CITY有500个不同的值,LNAME有10000个不同的纸,组合谓词的过滤因子就是1/500 x 1/10000

组合谓词的过滤因子:谓词的最大过滤因子 x 谓词的最大过滤因子。

过滤因子决定了索引片的厚度。

选择率

选择率公式

选择率 = 100 x (某个键值对应的行数)/表的总记录数

举例:

如果CUST表有1,000,000行记录,列CITY为HELSINKI的行数为200,000行,那么HELSINKI的选择率为20%。

不合适的索引

QUERY

SELECT	CNO, FNAME
FROM	CUST
WHERE	LNAME = :LNAME
		AND
		CITY = :CITY
ORDER BY FNAME
  1. 索引扫描(LNAME,FNAME)
  2. 全表扫描

对于第一个选择,对于索引片中每一个索引行,都需要回表检查CITY的值,由于表中的行识根据CNO而不是LNAME字段来聚簇的,所以每个校验操作需要做一次硬盘的随机读。

假如顺序读的速度为40MB/s,一次随机读需要花费10ms,索引(LNAME,FNAME)大小为100MB,10,000次随机读将花费10,000 x 10ms = 100s,读取一个宽度为1%的索引片(1MB)需要花费在IO的时间是10ms + 1MB/40MB/s = 35ms。

对于全表扫描,表的大小为600MB,只有第一个页需要随机读,花费在IO的时间则是10ms + 600MB/40MB/s = 15s。

因此对于不适合的索引,查询效率可能比全表扫描更低。

三星索引

  • 第一颗星:取出所有等值谓词的列(WHERE COL=…)作为索引的最开头,任意顺序都可以。在这种情况下,索引片的宽度被缩减到最窄。
  • 第二颗星:将ORDER BY列加入到索引中,不要改变这些列的顺序,但是忽略那些在第一步中已经加入索引的列。
  • 第三颗星:将查询语句剩余的列加入到索引中去,列在索引中添加的顺序对查询语句的性能没有影响。

举例:

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

满足第三颗星:确保查询语句中的所有列都在索引中。

满足第二颗星:添加ORDER BY列,但只有FNAME(ORDER BY列)放在BETWEEN谓词列LNAME之前才成立,如索引(CITY,FNAME,LNAME),因为CITY是等值谓词,所以结果以FNAME的顺序排列,不需要额外排序,但如果FNAMELNAME后面,如(CITY,LNAME,FNAME),则需要进行排序操作。

满足第一颗星:等值谓词CITY作为索引的最开头,列的过滤因子越低,索引片越窄。如果使用索引(CITY,LNAME)的话,索引片会更窄,但为了这样FNAME就不能放在这两列之间。

因此这里无法同时满足第一颗星与第二颗星,只能二选一:

  • 避免排序—-拥有第二颗星。(CITY,FNAME,LNAME,CNO)
  • 拥有更窄的索引片—-拥有第一颗星。(CITY,LNAME,FNAME,CNO)

评估索引

基本问题法(BQ):

是否有一个已存在的或者计划中的索引包含了WHERE子句所应用的所有列(一个半宽索引)?

  • 如果答案为否,首先应考虑将缺少的谓词加到一个现有的索引上去,尽管索引等值匹配过程不令人满意(一星),但可索引过滤后有效降低需要回表访问的数量。
  • 将所有涉及的列都加到索引上,这产生一个宽索引,避免回表访问。

快速上限估算法(QUBE):

LRT = 服务时间 + 排队时间 = 本地响应时间

TR = 随机访问的数量

TS = 顺序访问的数量

F = 有效FETCH的数量

举例:

假如一次随机读花费10ms,一次顺序读花费0.01ms。

聚簇索引访问:

SELECT	CNO, LNAME, FNAME
FROM	CUST
WHERE	ZIP = :ZIP
		AND
		LNAME = :LNAME
ORDER BY FNAME

索引列为(ZIP,LNAME,FNAME)

假如ZIP=30103的地区有1000位名为Joneses的客户:

索引	ZIP, LNAME, FNAME	TR = 1		TS = 1000
表	    CUST				TR = 1	    TS = 999
提取 1000 x 0.1 ms

LRT			TR = 2	  	TS = 1999
			2 x 10 ms   1999 x 0.01 ms
			20 ms + 20 ms + 100 ms = 140 ms

非聚簇索引访问:

索引	ZIP, LNAME, FNAME	TR = 1		TS = 1000
表	    CUST				TR = 1000   TS = 0
提取 1000 x 0.1 ms

LRT				TR = 1001	  	 TS = 1000
				1001 x 10 ms   1000 x 0.01 ms
				10 s + 10 ms + 100 ms = 10s

添加聚簇列CNO使索引变成三星索引:

索引	ZIP, LNAME, FNAME, CNO	TR = 1		TS = 1000
表	CUST					 TR = 0   	 TS = 0
提取 1000 x 0.1 ms

LRT				TR = 1	  	 TS = 1000
				1 x 10 ms    1000 x 0.01 ms
				10 ms + 10 ms + 100 ms = 120ms

对于查询:

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

QUBE分析如下:

三星索引:

索引 CITY, LNAME, FNAME, CNO	TR = 1		TS = 1% x 10% x 1000000
提取 1000 x 0.1 ms

LRT				TR = 1	  	 TS = 1000
				1 x 10 ms    1000 x 0.01 ms
				10 ms + 10 ms + 100 ms = 120ms

半宽索引

索引 CITY, LNAME, FNAME, CNO	TR = 1		      TS = 1% x 1000000
表   CUST					 	TR = 10% x 10000  TS = 0
提取 1000 x 0.1 ms

LRT				TR = 1001	  	 TS = 10000
				1001 x 10 ms     10000 x 0.01 ms
				10 s + 0.1 s + 0.1 s = 10s

宽索引

索引 LNAME, FNAME, CITY, CNO	TR = 1		      TS = 1% x 1000000
表   CUST					    TR = 0			  TS = 0
提取 1000 x 0.1 ms

LRT				TR = 1	  	 TS = 10000
				1 x 10 ms    10000 x 0.01 ms
				10 ms + 0.1 s + 0.1 s = 0.2s

分页查询的优化

  • 覆盖索引
  • 通过索引消除排序
SELECT * FROM table inner join (select pk from table order by created desc limit N) as t using(pk);