Postgres 索引那些事

Postgres内部提供了很多种索引的方式,满足不同的索引需求。

传统索引方式(B-Tree)

说到传统,B-Tree索引当仁不让,它也是postgres里的默认索引方式。B-Tree的中文名字是二叉平衡树,每个叶子结点的深度都是一样的,特点是允许在O(logn)的时间内对所存储的内容进行搜索、顺序访问、插入及删除。

B-Tree索引对于唯一值的索引来说是相当之理想的(比如id序号这类数据),它存储的是一对对的键值和指针,指针指向被索引数据所在的heap上的位置。

这里说下什么是heap。Heap(或者叫heap文件,用来区分同名不同义的数据结构heap)存储着postgres表里的所有数据(外部表除外)。heap里边的数据是无序的,这让数据库在向里面添加数据的时候不必考虑排序的问题。

目前postgres支持的索引中,只有B-Tree索引能够提供有序的查询结果(也就是支持Order by和Limit),支持高并发场景(并行scan),支持merge join和包含index scan的nested loop操作。

B-Tree是非常基本且古老的索引,但不代表它功能单一。

有时我们需要更多的功能,比如:表达式

看下这个例子:

CREATE TABLE customer (name) AS SELECT 'cust' || i
FROM generate_series(1, 1000) AS g(i);

CREATE INDEX i_customer_name ON customer (name);

/*看一下直接对B-Tree索引列做fitler的plan*/
EXPLAIN SELECT * FROM customer WHERE name = 'cust999'; 
   		 QUERY PLAN
------------------------------------------------------ 
Index Only Scan using i_customer_name on customer ...
    Index Cond: (name = 'cust999'::text)
/* 没问题!使用了Index!另外,Index Only Scan的意思是,所有想要的column都在index里已经有了*/

/* 如果对B-Tree索引列在查询时增加一个表达式操作呢?*/
EXPLAIN SELECT * FROM customer WHERE lower(name) = 'cust999'; 
   		 QUERY PLAN
--------------------------------------------------------- 
Seq Scan on customer (cost=0.00..20.00 rows=5 width=7)
    Filter: (lower(name) = 'cust999'::text)
/* 又变回Seq Scan了!😩 */

Postgres提供了表达式索引,你可以用表的一列或者多列组成的表达式,创建一个索引。

CREATE INDEX i_customer_lower ON customer (lower(name));
EXPLAIN SELECT * FROM customer WHERE lower(name) = 'cust999';
   		  QUERY PLAN
--------------------------------------------------------------- 
Bitmap Heap Scan on customer (cost=4.32..9.66 rows=5 width=7)
    Recheck Cond: (lower(name) = 'cust999'::text) 
    -> Bitmap Index Scan on i_customer_lower ...
   	 Index Cond: (lower(name) = 'cust999'::text)

等一下,这个Bitmap Index Scan又是什么意思?

Postgres做涉及到索引的扫描的时候,会先在索引上扫描一遍,得出符合条件的row/block的list,再拿着这个list到表上做真正的取数据操作。但如果一张表上的查询涉及多个索引呢?每个索引都这么来一次岂不是很浪费时间?

Bitmap Index Scan就能很好解决这个问题。多个索引都扫描完毕后,符合每个索引过滤条件的row/block会用同一个bitmap来记录,然后只需要用这个bitmap一次性去heap表上取出数据就好。值得一提的是,Postgres优化器会自动做出是否要使用Bitmap Index Scan的判断,不需要任何人工干预。

下图是bitmap index的示意图:

部分索引

当一个表很大的时候,为每一行都建索引是很耗存储空间的。如果常用的数据只有一小部分的话,完全可以只为这部分数据建立索引,省时省力省空间。

  • 省时:当做Insert和Update操作的时候,额外开销更小!
  • 省力:热数据索引扫描更快!
  • 省空间:索引再也不用耗费大量磁盘了!

让我们看下怎么建立一个部分索引

ALTER TABLE customer ADD COLUMN state CHAR(2);
UPDATE customer SET state = 'AZ' WHERE name LIKE 'cust9__';
CREATE INDEX i_customer_state_az ON customer (state) WHERE state = 'AZ';
/* 一个WHERE语句,只对state = AZ的行进行索引 */

EXPLAIN SELECT * FROM customer WHERE state = 'PA';
   	 QUERY PLAN 
---------------------------------------------------------- 
Seq Scan on customer (cost=0.00..17.50 rows=5 width=19) 
    Filter: (state = 'PA'::bpchar)
/* 当要查询的数据不在部分索引的范围内时,仍然使用Seq Scan */

EXPLAIN SELECT * FROM customer WHERE state = 'AZ';
   	 QUERY PLAN 
---------------------------------------------------------------------------- 
Bitmap Heap Scan on customer (cost=4.18..9.51 rows=5 width=19)
    Recheck Cond: (state = 'AZ'::bpchar)
    -> Bitmap Index Scan on i_customer_state_az ... 
   	 Index Cond: (state = 'AZ'::bpchar)
/* 当要查询的数据和部分索引一致时,索引就可以被用上了! */

Postgres这种带条件部分的索引,在mysql里仍不支持[ref]。如果想在mysql中创建一个类似上面例子的索引,你需要依据原表创建一个辅助表,并增加3个triggers(update/insert/delete),当对原表有满足“条件”的数据变动时,相应操作也会由trigger在辅助表上触发。然后,对辅助表创建索引。相比postgres,mysql的方式不仅耗时耗空间,对用户来说操作也非常不友好。

非传统索引方式

除了被作为默认索引的B-Tree,Postgres还以插件的方式提供了好几种“新型索引”,用于满足各式各样的应用场景。下面我们逐个认识一下。

BRIN (Block-Range Index)

名字里有个range,顾名思义,这种索引存储的是heap表内每个block中数据的最大值和最小值。

BRIN索引有什么作用和特点呢?

  • 首先,如果一整个block里的数据都非常大或者非常小,不在我们查询的条件范围内,就可以将整个block排除出扫描范围。这种索引对那些分布是有序的数据非常有用,比如insert-only table的id或timestamp列。
  • 其次,因为只存储最大值和最小值,BRIN带来的空间消耗极小。另外,更新数据的时候,索引带来的额外操作只有比较操作,也是相当高效的。
  • BRIN对于含有多个列的索引是比较合适的选择。

但是,因为索引里存储的信息非常少,查找数据的时候消耗的时间也会很长,当查询的数据范围和一个block的范围值有重叠时,就需要对这个block进行scan,如果有重叠的block很多,其实跟全表扫描的差别也不大了。

GIN (Generalized Inverted Index)

  • 尤其适用于有很多key或value的数据的索引,比如说文档、JSON、整型数组等等。
  • 尤其适用于重复数据很多的场景,这点和B-Tree正好相反。
  • 支持一条索引里存在多个key。而B-Tree每条索引里只能有一个key。比如新插入一条数据“foo bar”,GIN会拆分出两个key:“foo” 和 “bar”。

GIN索引内部数据结构整体上类似于B-Tree。不同的是,叶子结点上存储的不是一个TID,而是很多TID的集合,这是GIN为了存储重复数据做的优化。GIN的叶子结点的数据有三种可能:

  1. 当只有一个TID的时候,和B-Tree一样。
  2. 当有很多TID的时候,那么存储的是一个列表(posting list)。
  3. 当有非常非常多的TID的时候,叶子结点存储的是一个指针,这个指针指向另一棵树(Posting Tree)的根结点。而Posting Tree里面存储了所有符合这一个entry的TIDs(以page为存储单元)。

GIN树结构示意图:

GIN索引的Fast Updates特性:

GIN额外维护着一个列表,当有新的数据进入索引,不会直接进入索引树,而是会先暂存在这个列表里。当然,每个对索引的搜索也都会额外的对这个列表进行扫描。

当做vacuum操作的时候,会把这个列表里的数据插入到索引树上。不过,如果这个列表已经太大了,postgres不会傻傻等待用户进行vacuum,会果断地将它里面的内容插入GIN索引树。

但有意思的是,虽然它叫Fast Updates,但这个特性会让搜索变慢,因为每次搜索都要增加一次额外的列表扫描操作,所以很多用户会把这个特性关掉。

GIN索引的gin_fuzzy_search_limit

GIN索引适用于有大量重复关键字的全文索引,但是,当一个关键字出现次数太多时,返回结果也会很大,太大的结果集对用户是没有实际意义的,而且读取并排序这么多的数据会耗费很长时间。

GIN提供了一个配置项gin_fuzzy_search_limit来控制这种情况下返回结果集的上限。如果这个值非0,那么查询只会返回不超过设置值的一个子结果集,而且是随机的。根据经验,这个值设定为5000-20000比较好。

GIST (Generalized Search Tree)

GIST的数据结构仍然是树,但不再是B-Tree了。

支持地理坐标、range类型(比如ip范围)、hstore(key/value对)、整型数组、pg_trgm。

GIST和range

问题(见上图示意):假设表中有一列是range类型的数据,给出一个range范围,找出表中所有和它有重叠部分的数据。

如果是B-Tree,可以按照range的最大值或最小值进行排序,但仍然避免不了每次查询都要做扫描。GIST的做法,是将范围差不多的数据聚集在一起,形成一个个的“clusters”,每个cluster的最大值和最小值都在根结点上记录,这样就可以按照每个cluster的整体范围,排除掉那些根本不可能有重叠的cluster,大大降低了扫描成本。

GIST树的结构:

索引cluster存储在page上,根结点保存了每个page内部的最小值和最大值。给出查询范围后,只需要先扫描根结点,找出所有可能有范围重叠的page,再对这些page进行相应的扫描即可。

GIST对存储的key的顺序没有严格要求,而且每个key都可以在整棵树上任何一个page上存储,只要能把根结点的相应page的最大值最小值相应更新好就ok。但是,如果使用随机存储的话,最后根结点里每个page的范围就会差不多,性能会变得非常差(几乎等同于全表扫描)。所以,如何选择对key分组的函数就至关重要。另外当一个page增长过大之后,需要用picksplit函数来对page分割,这个函数的好坏对性能也有很大影响。

GIST的用途
  • GIS (geographic information system)
  • 寻找bounding box的顶点
  • 找到最近的n个邻居
  • 全文检索
  • 整型数组

一句话总结:GIST适合上层结点的范围能“包含”下层结点的类型。

SP-GIST (Space-Partitioned Generalized Search Tree)

虽然和GIST名字相似,但却是完全不同的索引类型,不是平衡树,各个叶子节点的深度可以不同。GIST各个cluster之间是可以有范围重叠的,但是SP-GIST不允许重叠

举个例子:

这是一个网址数据索引的例子,父节点是各个子节点的共有前缀,一个完整的键值在SP-GIST的树上只存一次,每一部分分别存储在从根结点到该键值叶子节点的路径上。

另外一个常见的使用场景是索引坐标点:将空间分割成不重叠的块,每个子节点再将父节点的空间细分。但是如果是空间里的形状,就无法使用SP-GIST来索引了,因为形状可能有重叠。

索引小知识

  • 你不能删除索引里的一条数据,只能通过vacuum操作将索引里无用的信息删掉。
  • Index Only Scan并不理会每一条数据是否是可见的,它只会如实把找到的一切符合条件的数据信息返回,可见性的控制是上层程序需要做的事。

什么时候你应该建立索引?

当seq_scan耗时很长的时候!

Explain一下你常用的查询,如果seq_scan的cost很高,可以考虑建立索引。但是相应的,如果一个索引的idx scan很少被用到,就要考虑这个索引是不是还应该继续存在了。毕竟,维护一个索引是耗时耗空间的事情。

如何选择使用哪种索引?

当然,数据类型是第一个考虑要素。在此之外,还可以从以下几点考虑:

  • 索引建立的时间
  • 索引存储空间
  • 数据更新时索引带来的额外开销
  • 访问速度

发表评论

电子邮件地址不会被公开。 必填项已用*标注