关于postgresql: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 的内存上下文，并敞开相干索引表和数据表。