本文为《数据库索引设计与优化》一书的笔记。该书也在《高性能MySQL》一书正文章节中得到强烈推荐。

关系型数据库系统是现代企业IT架构中的经典组成部分。传统关系型数据库，例如Oracle、MySQL、PostgreSQL都是将数据存储在硬盘上。将目标数据从硬盘，特别是性能较弱的机械硬盘，中更高效率地读取出来，是业界的持续努力的方向。

数据库系统都是将数据以文件的形式存储在硬盘上。

两点事实：

  1. 无论读写，数据库系统始终以两种方式与硬盘打交道：随机IO和顺序IO。
  2. 无论是机械硬盘还是固态硬盘，随机IO的延迟总是大于顺序IO延迟。

索引结构便是通过尽量减少随机IO的频次，从而降低查询的整体延迟。

三星索引

对于多谓词查询，一个宽列索引有比多个单列索引有更好的优势。因为：

  1. 每读取一条索引文件，就意味着一次随机IO
  2. 宽列索引通过过滤先导列，可以减少后续列的处理范围
  3. 如果查询结果列也在索引上，那就无需再查表了：
    • 如果从聚簇索引读取表，那就是一次随机IO + 若干顺序IO
    • 如果从非聚簇索引读取表， 那以为着读取每一表行都是一次随机IO

一个理想的“三星”宽列索引应当具备以下条件：

  • 第1颗星：查询谓词的相关列应该在索引上是相邻的，或者足够近的。保证了一次索引扫描，可以覆盖到足够的列值。这要求，所有等值谓词的列都是索引的先导列
  • 第2颗星：索引行的顺序和查询的期望顺序是一致的。从而避免行的重排序。这要求，范围谓词的列排在其后
  • 第3颗星：索引行包含了查询的所有列。从而避免读取表。这要求，所有查询结果列排在最后。其中，容易变更的列更为靠后

查询谓词的列应该将最能缩小扫描范围的列放在最前。

可以看出，给定一条索引，对于不同的查询语句，该索引的评价可能是不同，比如有时是三星级，有时是两星级。当数据库系统需要处理很多查询请求的时候，为每一种查询都创建一条三星级索引，会导致数据写入时需要更新很多索引，造成性能问题。因此，对于某些相似的查询，就有可能需要共享同一条索引。

基本问题法BQ

在创建查询的时候，可以先检查：是否存在一条索引能够包含所有谓词涉及的列，也即至少满足第1颗星。这种索引也称为半宽索引。

半宽索引至少能够保证过滤的效率。

快速上限预估法QUBE

快速上限预估法，对数据库的IO操作的CPU耗时给出了一组预估：

  • 随机寻址：10ms
  • 顺序读取每一行：0.01ms
  • 一次数据库Fetch操作：0.1ms

然后细致的考察索引和表在参与查询的过程中，随机IO和顺序IO的发生次数，从而得到对整个查询的耗时预估。

这个方法让我们可以对不同索引结构的效果进行量化分析对比，从而在理论上对不同的索引设计方案有一个初步筛选。

当然，这本书成书于2005年。当年，机械硬盘是服务器的主流选择。而如今，全固态硬盘服务器，云计算服务器比比皆是。这组预估数据条件其实是需要根实际情况来更新的。(fio工具可以分析硬盘的性能)

多表关联

关系型数据库的优势之一是可以将数据依范式组织，从而便于满足未来灵活变动的查询需求。关系型数据库对于多表关联查询，大致有三类处理方式：

  • 嵌套循环关联 Nested Loop Join
  • 合并关联 Merge Join
  • 哈希关联 Hash Join

嵌套循环关联，意味在每在外层表得到一条匹配数据，就即刻在内层表继续查找符合条件的列。这往往导致，在内层表中发生大量的随机IO。

而合并/哈希关联允许，内外层表分别过滤出结果表之后，再完成关联条件的比较。区别在于，如果内外结果表的顺序和查询目标一致，那便无需重排序，直接应用合并算法，得到关联结果。如果顺序不一致，哈希连接可以对结果表分区，然后逐区（每次内存中包含一个区）查询另一个结果表中的匹配行。

显而易见，合并/哈希关联能够减少内层表的随机IO，从而改善查询的整体延迟表现。根据QUBE分析，这个改善往往是巨大的。

总结

这本书为索引结果的设计给出一个量化分析框架，非常值得反复研读。

这本书的大量例子基于DB2和SQL Server等商业数据库。如果要应用于MySQL或者PostgreSQL这些更常见的开源关系型数据库系统上，还需要对具体数据库系统的实现细节有足够清晰的认识。