PostgreSQL 技术内幕（七）索引扫描

索引概述

数据库索引，是将一个表的某些字段的数据进行重新组织的数据库对象。通过使用索引，可以大大加速数据库的一些操作，其背后的思想也很简单朴素：空间换时间。

数据库中的索引，可以类比为一本书的目录，当我们在书中查询某信息的时候，借助目录，可以快速定位到对应的章节，从而避免了从整本书中去翻阅，加速了查找的过程。

索引分类

Postgres 中常见的索引大致有下面的这几种，其中 BTree 索引是使用最广泛的，也是创建索引时默认的选项。

索引扫描的例子

下面通过一个例子来体会索引对表扫描的性能的影响。我们首先创建一个测试表，例如叫 articles，并向其中插入一些测试的数据。

CREATE TABLE articles (  id SERIAL8 NOT NULL PRIMARY KEY,  a text,  b text,  c text);INSERT INTO articles(a, b, c)SELECTmd5(random()::text),md5(random()::text),md5(random()::text)from (  SELECT * FROM generate_series(1,1000000) AS id) AS x;

我们从这个表中查询一条数据，例如查找 a = '65c966eb2be73daf418c126df8dc33b5' 的数据，其查询计划如下：

可以看到这里使用了顺序扫描（Seq Scan），并且代价（Cost）是 22450。如果我们给字段 a 加上一个索引（默认是 BTree），create index on articles (a)，然后再执行这个 sql 语句，其查询计划如下：

可以看到这里使用到了索引扫描（Index Scan），并且代价是 8，相较于顺序扫描的 22450，查询的代价大大降低了，查询的性能由此得到了大幅的提升。

扫描方法

顺序扫描

当对无索引的字段进行查询，或者判断到查询将返回大多数数据时，查询优化器将会使用顺序扫描方法。还是以之前的 articles 表为例，这里我们查询了 id > 100 的数据，包含了大部分该表中的数据，所以尽管 id 列上有索引，但还是会使用顺序扫描。

索引扫描

如果判断到查询将会命中非常少量的数据时，查询优化器将会选择索引扫描方法，上面的例子已经有对应的展示了。下面是一个扫描索引范围的例子，可以看到命中数据占表数据的少量，选择索引扫描是最高效的。

位图索引扫描

尽管索引扫描的数据量一般较少，但是这个扫描需要随机 IO 操作，因此对比顺序扫描使用的顺序 IO 操作，它的代价并不总是更小。所以在命中适中数据（少量与多数之间），顺序扫描和索引扫描各自都有缺陷。针对这种情况，一般可以采用位图索引扫描，其原理是将需要访问的页面有序化，将随机 IO 转为顺序 IO。

大致操作步骤如下：

• 使用索引扫描到满足条件的所有 TID

• 用 TID 列表按照页面的访问顺序构建一个位图

• 读取数据记录时，同一个页面只需要读取一次

下图描述了 Postgres 中几种表数据扫描的方式，查询优化器会根据计算的代价选择最优的扫描方法。

索引物理存储

postgres 中的索引是一种二级索引，即在物理存储上，索引数据和对应的表数据是分离开的。每个特定的索引对象都存储为了一张独立的关系表，并且都能够在 pg_class 系统表中查询到。

以 BTree 为例，其大致的结构如下：

B+ 树的大致特点：

• 树层级更少：每个内部节点不再存储数据，因此能存储的键值会更多，于是导致树的层级更少且查询数据也更快（减少了随机 IO）。

• 查询速度更稳定：因为所有数据都存在叶子节点上，因此每次查找的次数（树的高度次随机 IO 操作）都相同，查询速度也要更稳定。

• 遍历查询更方便：B+Tree 的叶子节点数据构成了一个有序链表，在遍历查询时，首先定位第一个键值的位置，然后沿着链表即可访问到全部数据。

BTree 中的每一个节点在物理结构上存储为一个 page，page 的结构和 heap 表的类似，如下：

以 BTree 为例，索引中的内容可以理解为一个由键值到数据元组 TID 的映射，其中 TID 由一个块号和偏移组成。

索引创建

当用户使用 create index on table (col) 语句后，将会经过语法解析、权限检查等阶段，然后建立索引关系，更新系统元数据，最后使用表中的数据构建一个完整的 B-Tree 索引。

主要的函数调用路径如下：

ProcessUtility() Utility语句的处理入口DefineIndex() 定义一个索引（异常判断，准备index_create()的输入参数）index_create() 创建一个索引（建立关系文件并更新系统表数据）index_build() 构建索引的外层接口bt_build() B-Tree的索引构建逻辑

以 BTree 为例，使用表中的数据来构建 B-Tree 索引总体分为两步，一是将表中的数据排序，二是根据有序的数据元组，遍历自底向上构建整个 BTree。

这里主要是会针对不同的索引类型，调用不同的 ambuild 方法，其中 BTree 对应的方法是 btbuild，下图是索引相关接口的访问关系，不同的索引访问方法通过 IndexAM 进行抽象，供上层执行器调用。

索引扫描

索引扫描在执行器中的三个步骤分别是

• ExecInitIndexScan

• ExecIndexScan

• ExecEndIndexScan

ExecInitIndexScan

主要负责初始化索引扫描的状态结构体 IndexScanState 核心任务是将索引扫描的过滤条件转换为各种类型的扫描键 ScanKey。

• ScanKey 主要存储了索引列的信息，操作函数以及待比较的函数，ScanKey 描述了一个完整的过滤条件，并用于索引扫描

• 但如果过滤条件是一个复杂的表达式，引入了 iss_RuntimeKeys 来处理

IndexScanState 的主要字段：

Init 阶段主要关注的是 ExecIndexBuildScanKeys 方法，此方法的作用是将扫描过滤条件转化为各种类型的扫描键 ScanKey。

索引的过滤条件分为了以下五种情况：

• 常数或普通运算，直接存入 ScanKey

• 非常数的值表达式运算，此时执行器节点无法在初始阶段得到表达式的结果，需要暂时存入 iss_RuntimeKeys

• RowCompareExpr，比如过滤条件是“（indexkey1，indexkey2）> （1，2）”，表示多个过滤条件的组合，遍历所有的子过滤条件，分别存入 iss_ScanKeys 或者 iss_RuntimeKeys

• ScalarArrayOpExpr，比如过滤条件是“indexkey1 = ANY（1,10,20）”，如果索引支持处理基于数组的搜索，分别将常数存入 ScanKey 或者 RuntimeKey，如果不支持数组搜索，例如 Hash、GIN、Gist 索引，则将过滤条件存入 arrayKeys

• NullTest，索引键是否为 NULL，例如_"indexkey IS NULL/IS NOT NULL"，设置 ScanKey 对应的值即可_

ExecIndexScan

负责基于索引读取元组，并返回给执行器上层节点。函数 IndexNext 不断进行索引扫描，读取元组，并将元组封装进 TupleTableSlot 传递给上层节点。

• 此函数的主要参数是 IndexScanDesc，保存了 scan 过程中的状态信息

• 通过 xs_heap_continue 判断是否在 HOT 链上，如果是的话不做任何操作

• 否则调用 index_getnext_tid 返回一个 TID

  在 pg_am 表中查找 amgettuple 对应的内层接口函数

  调用这个函数（例如 BTree 中的 btgettuple），根据具体的索引实现返回一个 TID 调用 index_fetch_heap 获取实际的元组 ExecEndIndexScan

  主要负责清理工作，释放计算 RuntimeKey 的内存上下文，并关闭相关的索引表和数据表。