Postgres_index

Postgres Index Introduction

在Postgres中, 索引是特殊的加速数据访问的数据对象,是一个独立的数据结构,所有的索引都可以被删除或者是重建,不同的索引类型(access methods)之间存在, 但是都是将一个键与表行相关连,每行的标志服是TID(Tuple id), 也就是说我们可以通过key扫描索引的方式来获取数据,而不用扫描整个表,以此来加速对数据的访问。但是需要了解的是,在数据库层面,维护索引也是一笔开销,当涉及到相关操作(insert, update , delete)数据的时候,都需要同步更新对应的索引信息,以保证跟实际数据状态一致,未建立索引的字段,不是导致索引更新.

1: Index scan(索引扫描)

在使用索引扫描的时候,索引引擎先根据access method获取对于搜索条件的TID(Tuples ID, page + page_offset), 然后根据TID访问指定的表行(Index only scan 直接返回数据, 而不是TID),根据MVCC的相关原则,返回对应的数据结果
示例:

1
2
3
4
5
6
postgres=#create table test_table(a integer, b integer);
postgres=#create index on test_table(a);
postgres=#insert into test_table(1, 2);
postgres=#insert into test_table(1, 3);
postgres=#analyze test_table;
postgres=#explain (costs off) select * from test_table where a = 1;
1
2
3
4
5
          QUERY PLAN          
-------------------------------
Index Scan using test_table_a_idx on test_table
Index Cond: (a = 1)
(2 rows)

2: bitmap scan(bitmap 索引扫描)

在进行索引扫描是,查询结果包含少量的值是(在同一page中),直接用Index scan就可以解决,但是随着返回数据行的增加, 返回的结果中会包含多条同一page中的数据时,Optimizer(优化器会根据数据量来确定扫描方法)此时则会切换到bitmap scan, bitmap scan本质上返回的是page页面(存在一条或者是多条符合查询条件的row的page), 然后再page里面进行顺序扫描确定符合查询条件的row
postgres为查询动态创建bitmap, 其中的每一位代表着一个page,为1的page表示在此page中存在符合查询条件的row(多个查询条件直接用bitmap1 & bitmap2 (and操作),来确定page),
e.g.
test_table中有x索引y索引
查询语句: select * from test_table where x = 1 and y = 1
根据x=1生成bitmap1, 根据y=1生成bitmap2,
bitmap3 = bitmap1 & bitmap2
01110011 10101110 00100010
直接扫描bitmap3中每位为1所代表的的page即可

1
postgres=#explain select * from test_table where a=1 and b=2
1
2
3
4
5
6
7
Bitmap Heap Scan on test_table  (cost=8.73..12.74 rows=1 width=8)
Recheck Cond: ((b = 2) AND (a = 1))
-> BitmapAnd (cost=8.73..8.73 rows=1 width=0)
-> Bitmap Index Scan on b_idx (cost=0.00..4.24 rows=11 width=0)
Index Cond: (b = 2)
-> Bitmap Index Scan on a_idx (cost=0.00..4.24 rows=11 width=0)
Index Cond: (a = 1)

3:Seq scan(顺序扫描)

在搜索条件无法使用索引时或者扫描结果包含在很多page中, Optimizer就会采用Seq scan的方式来进行顺序扫描, 对表中所有的page进行顺序扫描(根据存储介质的不同,可配置seq/random).

4: Covering index

Postgres中索引是不直接保存数据内容的,只保存数据所在的Tuple信息,使用Covering index直接能获取到当前事务中可见的行版本,免去了MVCC可见性检查,postgres内部维护了可见性视图,并以此来确定查询是否可以直接使用Covering index直接获取到可见版本的Tuple而不必按照Index scan需要进行MVCC的可见性判断

5: Indexes on expressions(表达式索引)

在查询中,倘若需要对字段进行函数处理然后判断(表达式判断), 在没有创建表达式索引时,则无法正常使用索引

1
2
3
4
5
6
postgres=# explain select * from test_table where abs(a)=1 ---以abs(a)为查询条件, a字段存在索引, Seq scan
postgres=# create index on test_table(abs(b));

postgres=# analyze t;

postgres=# explain (costs off) select * from t where lower(b) = 'a'; --- Index scan

6: HOT(Heap only Tuple)

清除索引的冗余项,允许重复使用被删除或者是被废除的更新Tuples,而不用全面Vacuum,允许执行单页Vacuum, 但是本Tuple是无法直接通过索引访问到的。
没有HOT的时候,更新链的每一行都需要维护一条索引,即使是所有的索引列都相同,有了HOT之后,新的Tuples放在同一page中,所有的索引项共享父项索引
先前的版本用HEAP_HOT_UPDATED标志,无索引引用的版本用HEAP_ONLY_TUPLE来标志,并且根据MVCC将c_ctid指向最新的版本
e.g. :
索引指向1
lp [1] [2]
1被标志HEAP_HOT_UPDATED, 2被标志成HOT,即没有索引直接指向该tuple,并且被标志成HEAP_ONLY_TUPLE,尽管在索引中并未直接指向2,但是仍然可以通过链式查找的方法, 当标志位为HEAP_HOT_UPDATED
则会继续向下查找其子tuple,postgres限制HOT链位于同一page中,所以该查找也不需要额外的page提取.
如果该row继续被更新
lp [1] [2] [3]
则直接将[1] -> [3]即可维持通过索引间接查询

7: CREATE INDEX CONCURRENTLY(并发创建index)

并发创建索引时候,先标记该索引条目为”尚未准备好插入”, 提交的时候该事务会等待所有操作表的事务结束,确保新的HOT更新不会更改到新的索引k-v, 在等待操作表事务完成之后,
利用新snapshot来为所有有效的tuple建立索引,然后将索引标记为可插入但不可读取,并且等待打开表的所有交易完成,并且获取第二个相关的snapshot来验证索引,确定缺失的tuple并插入index中,
等待验证snapshot的事务之前的所有所有事务都完成(确保不会有事务查询到不一致的索引), 然后标记索引可查询

8: DROP INDEX CONCURRENTLY

并发删除索引,在并发删除索引时候(ShareUpdateExclusiveLock),首先标记该索引为无效,但是不会影响到在当前事务运行之前的事务,仅仅对当前事务之后事务有效,在等待查询中的事务运行完成之后,
清除未使用/不活跃的对象,然后等待可能更新该索引的事务完成,最后彻底删除该索引.

9: 索引类型

HASH

k-v结构,不支持有序查找,对key重复率较低的字段查询效率较高

BTree

B树是平衡树,所有的叶子节点跟节点都分开,每个节点内有序,节点之间有有序,并且节点之间双向连接,不必每次查找都返回到根节点,很好的支持有序查找,区间查找,并且查找时间稳定
参考结构

btree

GiST

由节点和page组成的平衡树, 适合多维度的数据搜索

Other type

Ref:

[1] Postgres source code: postgres/src/backend/access/heap/README.HOT
[2] https://postgrespro.com/blog/pgsql/3994098