根据直播内容整理而成,录播地址:https://www.bilibili.com/video/BV13a4y1T7jd
数据库索引,是将一个表的某些字段的数据进行重新组织的数据库对象,通过使用索引,可以大大加速数据库的一些操作,其背后的思想也很简单朴素:空间换时间。
数据库中的索引,可以类比为一本书的目录,当我们在书中查询某信息的时候,借助目录,可以快速定位到对应的章节,从而避免了从整本书中去翻阅,加速了查找的过程。
Postgres 中常见的索引大致有下面的这几种,其中 BTree 索引是使用最广泛的,也是创建索引时默认的选项。
索引类型 | 索引名称 | 说明 |
---|---|---|
btree | B+树索引 | B+ 树实现的索引类型,具有丰富的索引特性(多值、排序、聚簇等),增、删、改操作性能稳定,应用广泛,是默认的索引类型。 |
hash | 哈希索引 | Hash 索引基于哈希表结构,适用于等值比较查询。Hash 索引的查询速度非常快,但是不支持范围查询和排序操作。 |
gin | 通用倒排索引 | 可以用于支持各种文本类型的查询。它适用于文本搜索、数组、范围查询等场景。GIN 索引在查询过程中会对匹配的值进行聚合,因此查询速度较快,但索引的更新和插入速度较慢。 |
gist | 通用搜索树索引 | GiST 索引是一种通用的空间索引,用于支持空间查询和范围查询。GiST 索引可以处理点、线、多边形等复杂的空间数据类型,因此适用于地理信息系统(GIS)等场景。GiST 索引的查询速度较快,但索引的更新和插入速度较慢。 |
下面通过一个例子来体会索引对表扫描的性能的影响。我们首先创建一个测试表,例如叫 articles,并向其中插入一些测试的数据。
CREATE TABLE articles (
id SERIAL8 NOT NULL PRIMARY KEY,
a text,
b text,
c text
);
INSERT INTO articles(a, b, c)
SELECT
md5(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。大致操作步骤如下
下图描述了 Postgres 中几种表数据扫描的方式,查询优化器会根据计算的代价选择最优的扫描方法。
postgres 中的索引是一种二级索引,即在物理存储上,索引数据和对应的表数据是分离开的。每个特定的索引对象都存储为了一张独立的关系表,并且都能够在 pg_class 系统表中查询到。以 BTree 为例,其大致的结构如下:B+ 树的大致特点:
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的索引构建逻辑
ProcessUtility | 数据库Utility语句的统一处理入口,对于创建索引,转发给DefineIndex函数来继续处理 |
---|---|
DefineIndex | 主要功能是执行各类权限和异常情况判断,并初始化index_create函数所需要的各个参数 |
index_create | 主要功能是建立索引关系和系统表记录 |
index_build | 创建索引的外围接口,主要调用 index 对应的 ambuild 函数 |
btbuild | BTree 索引的构建逻辑 |
以 BTree 为例,使用表中的数据来构建 B-Tree 索引总体分为两步,一是将表中的数据排序,二是根据有序的数据元组,遍历自底向上构建整个 BTree。
这里主要是会针对不同的索引类型,调用不同的 ambuild 方法,其中 BTree 对应的方法是 btbuild,下图是索引相关接口的访问关系,不同的索引访问方法通过 IndexAM 进行抽象,供上层执行器调用。
索引扫描在执行器中的三个步骤分别是
主要负责初始化索引扫描的状态结构体 IndexScanState 核心任务是将索引扫描的过滤条件转换为各种类型的扫描键 ScanKey。
IndexScanState 的主要字段:
类型 | 字段 | 描述 |
---|---|---|
List* | indexqualorig | 索引过滤条件 |
ScanKeyData | iss_ScanKeys | Qual 的右操作符为常量 |
IndexRuntimeKeyInfo | iss_RuntimeKeys | 如果 Qual 的右操作符不是常量,需要在执行的过程中动态计算表达式的值,则将表达式信息存到 IndexRuntimeKey 中 |
Init 阶段主要关注的是 ExecIndexBuildScanKeys 方法,此方法的作用是将扫描过滤条件转化为各种类型的扫描键 ScanKey。
索引的过滤条件分为了以下五种情况:
负责基于索引读取元组,并返回给执行器上层节点。函数 IndexNext 不断进行索引扫描,读取元组,并将元组封装进 TupleTableSlot 传递给上层节点。
主要负责清理工作,释放计算 RuntimeKey 的内存上下文,并关闭相关索引表和数据表。