本系列的内容主要翻译自Postgresql官方博客,为了便于理解,对于其中部分涉及到的知识,我在查阅相关资料的基础上做了补充。

原文: Indexes in PostgreSQL — 5(GiST)

系列文章索引

在先前的文章中,我们讨论了PostgreSQL的索引引擎访问方法接口,和两个方法问方法:哈希索引B树索引。这篇文章,我们将讨论Gist索引。

GiST

GiST是“generalized search tree(广义搜索树)”的缩写。这是一个平衡的搜索树,和前面讨论的”b-tree”类似。

它们有什么不同呢?”btree”索引和比较语义严格有关:支持“大于”、“小于”、“等于”操作符就是它全部的能力了(但是非常有用)。然后,许多现在的数据库存储一些没有比较意义的数据类型:地理数据、文本文档以及图像。

GiST索引方法可以处理这些数据类型。它允许定义一个将任意类型的数据分布在平衡树上的规则,和定义一来让部分操作符能够使用的方法。例如,GiST索引可以“容纳”R-tree树来支持空间数据的相对位置运算符(在左侧、在右侧、包含等等),或者“容纳”RD-tree来支持相交和包含操作符。

由于PostgreSQL的拓展性,可以在数据库中从头开始创建一个新的访问方法:为此,必须实现和索引引擎相关的接口。但是不仅需要考虑好索引的逻辑,还需要实现将数据结构映射到页、高效的实现锁机制以及支持预写日志(WAL)。所有的这些都需要开发者具有很高的技能水平和很多的人力。GiST通过接管一些底层的问题并提供自己的接口来简化任务:即那些和技术无关而和应用领域相关的功能。从这个意义上来说,我们可以把GiST看作是构建新的访问方法的框架。

Gist是一个索引框架,可以通过实现这个框架来支持任意的数据类型以及对应的任意操作符。PostgreSQL中内置了一些实现,来支持空间地理对象等对象。

结构

GiST是一个由节点页面组成的高度平衡树。节点中由若干个索引行组成。

叶子节点中的每一行,通常情况下,包含了一些谓词(布尔表达式)和一个指向表行(TID)的引用。索引的数据必须满足这些谓语。

内部节点中的每一行包含了一个谓语和指向下一个节点的引用,所有子树上被索引的数据都必须满足这个谓语。换句话说,内部节点的谓语涵盖了所有子节点行的谓语。GiST这一重要的特定取代了B树的简单排序。

在GiST树中搜索使用专门的一致性函数”consistent”)-由接口定义的一个函数,用来支持操作符族中的其支持的操作符。

一致性函数究竟是什么?因为Gist不像Btree那样具有大于、小于之类的严格语义,对操作符的支持也更加灵活,即可以支持任何功能的操作符,比如包含、相交、在左侧、在右侧等等。具体怎么做呢?在B-tree中提到了策略编号,在B树访问方法中,策略编号对应的操作符的功能是提前规定好的,例如1对于小于、2对应小于等于。但是在Gist访问方法中,并没有规定哪个策略编号对应什么样的功能,是一种更加灵活的方式:可以在操作符类中随意定义一个策略编号对应一个操作符(这告诉了索引引擎这个操作符是支持索引的),然后索引引擎在条件中遇到这个操作符的话,就会通过一致性函数来调用这个操作符对应的函数。具体怎么调用呢,我们看一下一致性函数的参数列表(internal, data_type, smallint, oid, internal),第一个参数是索引树上的值,第二个data_type就是条件谓词(索引字段 操作符 表达式)中的表达式,第三个smallint类型的参数是条件谓词(索引字段 操作符 表达式)中操作符在操作符类中对应的策略编号,最后一个internal则是recheck标记。也就是说,索引引擎在树上搜索的时候,会把当前搜索的值和表达式以及操作符对应的策略编号传递给我们自定义的一致性函数,然后我们自定义的一致性函数在内部就可以根据传递来的策略编号来调用此操作符对应的函数。下面是一个一致性函数的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Datum my_consistent(PG_FUNCTION_ARGS)
{
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
Datum query = PG_GETARG_DATUM(1);
uint16_t strategy = PG_GETARG_UINT16(2);

bool *recheck = (bool *) PG_GETARG_POINTER(4);
*recheck = false;

Datum retval;
if(strategy == 0){ // 假设策略编号0代表的函数功能是 在左侧
retval= DirectFunctionCall2(on_left, key, query); //DirectFunctionCall2的作用是调用函数,并传递需要的参数
}else if(strategy == 1){
retval = DirectFunctionCall2(on_right, key, query);
}
return retval;

}

一致性函数会在索引的每一行上调用,来判断这一行上的谓词是否和搜索的谓词(“索引字段 操作符 表达式”)一致。对于内部节点的行,这个函数实际上决定是否需要下降到子树,对于叶节点的行,这个函数决定索引的数据是否匹配谓词。

搜索从根节点开始,一致性函数负责去找出进入到哪些子节点是有意义的,哪些没有意义。然后会在每一个进入的子节点上重复这个算法。如果到了叶节点,一致性算法选择的行会作为结果的一部分返回。

搜索时深度优先的:算法首先尝试到达叶节点。这样在可能的情况下尽早的返回第一个结果。(或许用户只对几个值而不是全部值感兴趣)。

让我们再次强调一下,一致性函数不需要和“大于”、“小于”、“等于”操作符有关系。一致性函数的语义可能是完全不同的,因此不能假定索引以某种顺序返回值。

我们不会讨论GiST中插入值和删除值的算法:这些操作需要更多的接口函数。然而有一个重要的点:当一个值被插入索引的时候,这个值在树中的位置会被选择为一个尽可能少的拓展父节点的行的谓词的位置(理想情况下是不拓展)。但是当一个值被删除的时候,其父节点的行的谓词不会被减少。父节点谓词减少只会在这样的情况下发生:一个页面分裂成了两个(当一个页面没有足够的空间去插入一个新的索引)或者索引被重新构建(通过REINDEX或者VACUUM FULL)。因此,Gist的效率对于频繁变化的数据会随着时间的推移而降低。

下面,我们将会讲到一些数据类型的列子和GiST有用的属性

  • 点(或者其它空间实体)和搜索最相邻的对象
  • 区间和排除约束
  • 全文搜索

用作点(Point)的R-tree

我们将通过平面上的点的示例来说明上述的内容(我们也可以为其它空间实体构建相似的索引)。常规的B树不适合这种数据类型,因为在点上没有定义比较操作符。

R-tree的想法是把平面分割成矩形,这些矩形覆盖了所有被索引的点。一个索引行存储一个矩形,谓词像这样定义:“寻找的点在给定的矩形内”

R-tree的根节点有几个最大的矩形组成(可能相交)。子节点是一些父节点中小的矩形,覆盖了所有的索引点。

理论上,叶子节点必须包含被索引的点,但是又因为所有索引行上的数据类型必须相同,因此,叶子节点上存储的也是矩形,但是“收缩”成了一个点。

为了可视化这种结构,我们提供了包含3个层级的R树的图片。这些点是飞机的坐标。

第一级:可以看到有两个很大的矩形

第二级:大的矩形被分割成了小的区域

第三级: 每个矩形包含了可以放进一个索引页数量的点。

现在我们先考虑一个非常简单的“一层”例子

1
2
3
4
5
6
7
create table points(p point);

insert into points(p) values
(point '(1,1)'), (point '(3,2)'), (point '(6,3)'),
(point '(5,5)'), (point '(7,8)'), (point '(8,6)');

create index on points using gist(p);

随着拆分,索引的结构看起来如下图所示:

这个索引可以被使用来加速这样的查询,例如:“找到包含在一个给定矩形中的所有点”。这个条件可以被写成这样:p <@ box ‘(2,1),(6,3)’ (“points_ops”族中的操作符<@意思是包含在)

1
2
3
set enable_seqscan = off;

explain(costs off) select * from points where p <@ box '(2,1),(7,4)';
1
2
3
4
5
                  QUERY PLAN                  
----------------------------------------------
Index Only Scan using points_p_idx on points
Index Cond: (p <@ '(7,4),(2,1)'::box)
(2 rows)

操作符(索引字段 <@ 表达式,索引字段是一个点,表达式是一个矩形)的一致性函数这样被定义。对于一个内部行,如果其矩形和表达式定义的矩形相交,就返回”yes”。对于叶子行,如果这个点(一个收缩的矩形)被表达式定义的矩形包括就返回”yes”。

搜索首先从根节点开始。矩形(2,1)-(7,4)和(1,1)-(6,3)相交,但是不和(5,5)-(8,8)相交,因此,不需要下降到第二个子树上。

在到达叶节点以后,我们遍历这个节点包含的三个值,并返回其中的(3,2)和(6,3)作为结果。

1
select * from points where p <@ box '(2,1),(7,4)';
1
2
3
4
5
   p   
-------
(3,2)
(6,3)
(2 rows)
内部

不幸的是,没有像“pageinspect”这样的可以查看GiST索引的拓展。但是有一个没有包含在发行版中的拓展”gevel”,点击这里查看安装文档

如果上面的都做好了,就会有三个有用的函数。首先,我们可以得到一些分析:

1
select * from gist_stat('airports_coordinates_idx');
1
2
3
4
5
6
7
8
9
10
11
12
13
                gist_stat                
------------------------------------------
Number of levels: 4 +
Number of pages: 690 +
Number of leaf pages: 625 +
Number of tuples: 7873 +
Number of invalid tuples: 0 +
Number of leaf tuples: 7184 +
Total size of tuples: 354692 bytes +
Total size of leaf tuples: 323596 bytes +
Total size of index: 5652480 bytes+

(1 row)

从上面的信息可以看出 索引的大小是690个页,一共有四级:根节点和两个内部节点,第四级是叶子节点。

实际上,8000个点的索引会比这个小很多。这里为了看的更清楚一点,创建索引的时候指定了10%的填充因子(fillfactor)。

什么是填充因子。填充因子的范围是10到100,在创建表和索引的时候都可以指定填充因子,其作用是指定对页的填充程度。对于表来说,当填充因子设置为50的时候,那么插入操作只会把表页填充到50%,然后每页上的剩余空间将保留用于放置更新的行。这就让UPDATE操作可以把更新的行版本和原来的行放在同一个页面上,从而提高更新的效率,即不需要再去找别的页面了。对于索引来说,当填充因子设置为50的时候,那么创建期间和向右侧拓展索引期间,叶页也只会填充到50%。如果填充满的话,大量的更新操作会造成索引的频繁拆分,进而影响索引的效率。设置的比较小的话,更新操作会填充页中的剩余部分,不会造成频繁的拆分索引。参考资料1参考资料2

然后,我们来看索引树的输出

1
select * from gist_tree('airports_coordinates_idx');
1
2
3
4
5
6
7
8
9
10
                                       gist_tree                                              
-----------------------------------------------------------------------------------------
0(l:0) blk: 0 numTuple: 5 free: 7928b(2.84%) rightlink:4294967295 (InvalidBlockNumber) +
1(l:1) blk: 335 numTuple: 15 free: 7488b(8.24%) rightlink:220 (OK) +
1(l:2) blk: 128 numTuple: 9 free: 7752b(5.00%) rightlink:49 (OK) +
1(l:3) blk: 57 numTuple: 12 free: 7620b(6.62%) rightlink:35 (OK) +
2(l:3) blk: 62 numTuple: 9 free: 7752b(5.00%) rightlink:57 (OK) +
3(l:3) blk: 72 numTuple: 7 free: 7840b(3.92%) rightlink:23 (OK) +
4(l:3) blk: 115 numTuple: 17 free: 7400b(9.31%) rightlink:33 (OK) +
...

最后,我们我们可以输出存储在索引行中的数据。注意以下细微差别:必须要将函数返回的结果强制转换为我们需要的类型。在这种情况下,数据类型是”BOX”。例如,下面是最顶层的5行数据

1
select level, a from gist_print('airports_coordinates_idx') as t(level int, valid bool, a box) where level = 1;
1
2
3
4
5
6
7
8
 level |                                   a                                  
-------+-----------------------------------------------------------------------
1 | (47.663586,80.803207),(-39.2938003540039,-90)
1 | (179.951004028,15.6700000762939),(15.2428998947144,-77.9634017944336)
1 | (177.740997314453,73.5178070068359),(15.0664,10.57970047)
1 | (-77.3191986083984,79.9946975708),(-179.876998901,-43.810001373291)
1 | (-39.864200592041,82.5177993774),(-81.254096984863,-64.2382965088)
(5 rows)

用于搜索和排序的运算符

前面讨论的操作符符(例如谓词p <@ box ‘(2,1),(7,4)’中的<@)可以被称为搜索操作符,因为它们在查询中都是被指定为搜索条件

还有另外一种类型的操作符:排序操作符。它们被用来指定在ORDER BY子句中的排序顺序,而不是传统的指定列名。下面是一个这样查询的例子。

1
select * from points order by p <-> point'(4,7)' limit 2;
1
2
3
4
5
   p   
-------
(5,5)
(7,8)
(2 rows)

这里的表达式 p <-> point ‘(4,7)’ 使用的是排序操作符<->,用来表示一个到另外一个的距离。这个查询的意思就是返回距离点(4,7)最近的两个点。这样的搜索被称为k-NN (最近邻居搜索)。为了支持这种类型的搜索,访问方法必须定义一个额外的距离函数,距离操作符也必须被包括在对应的操作符类中。下面的查询显示了运算符和它们的类型(“s”:搜索,”o”:排序)。

1
2
3
4
5
6
7
8
select amop.amopopr::regoperator, amop.amoppurpose, amop.amopstrategy
from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop
where opc.opcname = 'point_ops'
and opf.oid = opc.opcfamily
and am.oid = opf.opfmethod
and amop.amopfamily = opc.opcfamily
and am.amname = 'gist'
and amop.amoplefttype = opc.opcintype;
1
2
3
4
5
6
7
8
9
10
11
12
      amopopr      | amoppurpose | amopstrategy 
-------------------+-------------+--------------
<<(point,point) | s | 1 strictly left
>>(point,point) | s | 5 strictly right
~=(point,point) | s | 6 coincides
<^(point,point) | s | 10 strictly below
>^(point,point) | s | 11 strictly below
<->(point,point) | o | 15 distance
<@(point,box) | s | 28 contained in rectangle
<@(point,polygon) | s | 48 contained in rectangle
<@(point,circle) | s | 68 contained in circle
(9 rows)

这里显示了策略的数量,并解释了它们的含义。很明显,这里的策略比”btree”的要多,其中只有一部分被点使用。对于其它数据类型,也可以定义不同的策略。

为索引的元素调用的距离函数必须计算出从表达式中定义的值到给定的元素的距离。对于一个叶子元素来说,这只是到索引值的距离。对于内部元素来说,这个函数必须返回到子叶子节点的最小距离。由于遍历所有的子行非常昂贵,这个函数允许乐观的低估距离,但是会增加搜索的代价。然而,绝对不能高估距离,这会影响索引的工作。

距离函数可以返回任何一种可以排序的数据类型的值(为了排序值,PostgreSQL将使用”btree”访问方法的排序语义)

对于平面上的点,(x1,y1) 、(x2,y2)两点之间的距离等于横轴坐标轴差和纵轴坐标轴差的平方和的平方根。从点到边界的距离可以被认为这个点到此矩形的最小距离。如果这个点在矩形内,则这个距离是0。计算这个点很容易,不需要去遍历子点,而且这个距离肯定不会大于到任意一个子点的距离。

让我们来看一下上面查询的搜索算法。

搜索从根节点开始。这个节点包括两个矩形。到 (1,1)-(6,3)的距离是4,到(5,5)-(8,8)是1.0。

子点按照距离增加的顺序遍历,这样,我们首先下降到距离最近的节点的子节点,并计算到子节点中每个点的距离。

这些信息足够去返回最开始的两个点(5,5)和(7,8)。既然我们知道到位于(1,1)-(6,3)中的点的距离为4.0甚至更大,因此我们不需要下降到第一个子节点去搜索。但是如果我们想要找到第三个点呢?

1
select * from points order by p  <-> point '(4,7)' limit 3;
1
2
3
4
5
6
   p  
-------
(5,5)
(7,8)
(8,6)
(3 rows)

尽管第二个子节点包含了这些所有的点,但是我们还是需要查看第一个子节点。因为到(8,6)的距离是4.1,这个比到(1,1)-(6,3)的距离小(4.0<4.1),说明(1,1)-(6,3)的子节点中可能包含更小的点。

对于内部行来说,这个例子说明了对距离函数的要求。因为低估了到第二行的距离(实际为4.5),因此降低了搜索的效率(算法不必要的去检查了额外的节点),但是没有破坏算法的正确性。

直到最近,GiST还是唯一能够处理排序运算符的访问方法

2019年3月,PostgreSQL12中为SP-GiST添加了k-NN的支持。B-tree的补丁仍然在开发中。

用于区间(intervals)的R树

另外使用GiST访问方法的例子是intervals索引,例如时间区间(tsrange)。和上面不同的是内部节点不是外包矩形而是外包区间,

我们来看一个简单的例子。我们出租一个小屋,并且把出租的区间存在表里。

1
2
3
4
5
6
7
8
create table reservations(during tsrange);

insert into reservations(during) values
('[2016-12-30, 2017-01-09)'),
('[2017-02-23, 2017-02-27)'),
('[2017-04-29, 2017-05-02)');

create index on reservations using gist(during);

下面的查询可以使用索引来加速,例如

1
select * from reservations where during && '[2017-01-01, 2017-04-01)';
1
2
3
4
5
                    during                     
-----------------------------------------------
["2016-12-30 00:00:00","2017-01-09 00:00:00")
["2017-02-23 00:00:00","2017-02-27 00:00:00")
(2 rows)
1
explain (costs off) select * from reservations where during && '[2017-01-01, 2017-04-01)';
1
2
3
4
5
                                     QUERY PLAN                                     
------------------------------------------------------------------------------------
Index Only Scan using reservations_during_idx on reservations
Index Cond: (during && '["2017-01-01 00:00:00","2017-04-01 00:00:00")'::tsrange)
(2 rows)

因为测试的数据量比较小,需要设置 set enable_seqscan = off

&& 操作符表示的是两个区间存在交集。因此查询需要返回所有和查询的区间存在相交的区间。对于这样的操作符,一致性函数需要确定给定的区间是否和内部或者叶子节点中的行相交。

但是请注意,返回的结构并没有特定的顺序。尽管区间也支持比较操作符,我们也可以对区间使用btree索引。但是对于上面使用了GiST这个例子而言,是没有排序的效果的(因为也没有指定Order By)。

1
2
3
4
5
6
7
8
select amop.amopopr::regoperator, amop.amoppurpose, amop.amopstrategy
from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop
where opc.opcname = 'range_ops'
and opf.oid = opc.opcfamily
and am.oid = opf.opfmethod
and amop.amopfamily = opc.opcfamily
and am.amname = 'gist'
and amop.amoplefttype = opc.opcintype;
1
2
3
4
5
6
7
8
9
10
11
12
13
         amopopr         | amoppurpose | amopstrategy
-------------------------+-------------+--------------
@>(anyrange,anyelement) | s | 16 contains element
<<(anyrange,anyrange) | s | 1 strictly left
&<(anyrange,anyrange) | s | 2 not beyond right boundary
&&(anyrange,anyrange) | s | 3 intersects
&>(anyrange,anyrange) | s | 4 not beyond left boundary
>>(anyrange,anyrange) | s | 5 strictly right
-|-(anyrange,anyrange) | s | 6 adjacent
@>(anyrange,anyrange) | s | 7 contains interval
<@(anyrange,anyrange) | s | 8 contained in interval
=(anyrange,anyrange) | s | 18 equals
(10 rows)

不过由于区间(interval)支持B树,我们在查询的时候可以指定order by来指定返回的结果按照指定的顺序返回。这是因为PostgreSQL在执行Order by的时候,会自动使用Btree中定义的比较语义。换言之,如果一个数据类型不支持Btree索引,它就不支持Order by子句。详情点击这个查看官方说明

我们可以验证一下本篇文章中提到的两种数据类型 point 和 interval

1
2
3
4
5
select distinct am.amname from pg_opclass opc, pg_opfamily opf, pg_am am
where opc.opcname = 'range_ops'
and opf.oid = opc.opcfamily
and am.oid = opf.opfmethod;

1
2
3
4
5
6
7
 amname 
--------
btree
gist
hash
spgist
(4 rows)
1
2
3
4
5
select distinct am.amname from pg_opclass opc, pg_opfamily opf, pg_am am
where opc.opcname = 'point_ops'
and opf.oid = opc.opcfamily
and am.oid = opf.opfmethod;

1
2
3
4
 amname 
--------
gist
(1 row)

从上面结果中可以看出 interval支持btree,而point不支持btree

1
select * from reservations where during && '[2017-01-01, 2017-04-01)' order by during desc
1
2
3
4
5
                    during                     
-----------------------------------------------
["2017-02-23 00:00:00","2017-02-27 00:00:00")
["2016-12-30 00:00:00","2017-01-09 00:00:00")
(2 rows)
1
select * from points where p <@ box '(2,1),(7,4)' order by p;
1
2
3
4
ERROR:  could not identify an ordering operator for type point
LINE 1: ...elect * from points where p <@ box '(2,1),(7,4)' order by p;
^
HINT: Use an explicit ordering operator or modify the query

内部

我们同样使用gevel来查看内部结构。只需要换一下数据类型就可以了

1
select level, a from gist_print('reservations_during_idx') as t(level int, valid bool, a tsrange);
1
2
3
4
5
6
 level |                       a                      
-------+-----------------------------------------------
1 | ["2016-12-30 00:00:00","2017-01-09 00:00:00")
1 | ["2017-02-23 00:00:00","2017-02-27 00:00:00")
1 | ["2017-04-29 00:00:00","2017-05-02 00:00:00")
(3 rows)

排除约束

GiST可以用来支持排除约束

排除约束可以确定任何两个表行中的特定字段在对选择的操作符不会彼此对应。例如,如果是”equals“操作符,这就是唯一约束:对于指定的字段,可以确保这个字段不会重复。

排序约束是被索引支持的,就像唯一约束一样。我们可以选择任意的操作符,只要满足下面的条件:

  1. 索引方法”can_exclude”属性支持(例如 “btree”、GiST、SP-GiST支持,而GIN不支持)
  2. 操作符是可交换的,即 (a 操作符 b) 和 (b 操作符 a)是等价的

下面是一些操作符的可以用的策略列表(请记住,操作符可以是不同的名字,并且不一定被所有的数据类型支持)

  • 对于 “Btree”
    • “equals” =
  • 对于GiST和SP-GiST:
    • “相交” &&
    • ”近似相等“ ~=
    • ”相邻“ -|-

请注意,我们可以在排除约束的时候使用equals操作符,但是这是不合理的,因为,unique约束更加有效。这也是为什么在B-tree中我们没有讲排除约束的原因

下面我们提供一个例子,这个例子中,使用了&&排他约束,即不允许插入相交的数据

1
alter table reservations add exclude using gist(during with &&);

创建了排他约束后,我们增加一行数据

1
insert into reservations(during) values ('[2017-06-10, 2017-06-13)');

然后,我们在尝试插入一条和这条数据相交的数据,就会出错

1
2
ERROR:  conflicting key value violates exclusion constraint "reservations_during_excl"
DETAIL: Key (during)=(["2017-05-15 00:00:00","2017-06-15 00:00:00")) conflicts with existing key (during)=(["2017-06-10 00:00:00","2017-06-13 00:00:00")).

btree_gist拓展

让我们考虑一种更复杂的情况。我们的业务扩大了,我们有好几间小屋可以出租了

1
alter table reservations add house_no integer default 1;

由于不同小屋的出租区间是可以相交的,因此我们需要更改一下前面的排除约束,把小屋的编号也要考虑进去。问题在于,数值类型不支持GiST索引

1
alter table reservations add exclude using gist(during with &&, house_no with =);
1
2
ERROR:  data type integer has no default operator class for access method "gist"
HINT: You must specify an operator class for the index or define a default operator class for the data type.

在这种情况下,”btree_gist“拓展就很有用了。GiST既然可以支持任何操作符,那么我们为什么不教它支持”更大“、”更小“和”相等“操作符呢?

1
2
3
create extension btree_gist;

alter table reservations add exclude using gist(during with &&, house_no with =);
1
ALTER TABLE

现在我们仍然无法预定第一间小屋的已经预定日期的相交日期

1
insert into reservations(during, house_no) values ('[2017-05-15, 2017-06-15)', 1);
1
2
3
ERROR:  conflicting key value violates exclusion constraint "reservations_during_house_no_excl"
DETAIL: Key (during, house_no)=(["2017-05-15 00:00:00","2017-06-15 00:00:00"), 1) conflicts with existing key (during, house_no)=(["2017-06-10 00:00:00","2017-06-13 00:00:00"), 1).

但是我们可以预定另外一间小屋的

1
insert into reservations(during, house_no) values ('[2017-05-15, 2017-06-15)', 2);

注意,尽管GiST也可以实现”更大“、”更小“、”相等“等比较操作符,但是这个是B树擅长的东西。因此,只有在十分有需要使用GiST的时候,才值得使用这种技术。

针对全文检索使用的RD-tree

关于全文检索

我们先介绍一下PostgreSQL的全文检索(如果你已经知道了的话,可以跳过这个章节)

全文检索的目的是从文档中搜索那些匹配查询的文档(如果有很多匹配的文档,那么找到最合适的文档也很重要。但是这里我们不会讲到这一点)。

对于搜索目的,一个文档被转换为一个特殊类型”tsvector”,其中包含了”词条“和它们在文档中的位置。词条是被转换的适合用来搜索的词。例如,单词通常被转换为小写,词尾也被截断(即复数形式的es或者被动形式的ed)。

1
select to_tsvector('There was a crooked man, and he walked a crooked mile');
1
2
3
4
               to_tsvector               
-----------------------------------------
'crook':4,10 'man':5 'mile':11 'walk':8
(1 row)

我们可以看到有一些词语( “there”, “was”, “a”, “and”, “he”,这些词语也叫做stop words)被丢弃了,因为它们出现的太频繁,搜索它们没有意义。这些转换是可以配置的,但是那是另外一说了。

搜索条件是另外一种类型”tsquery”。大概来说,查询条件是由几个词条用”&”、”|”、”!”等连接词连接起来的。我们也可以使用括号来表示优先级。

1
select to_tsquery('man & (walking | running)');
1
2
3
4
 to_tsquery         
----------------------------
'man' & ( 'walk' | 'run' )
(1 row)

全文搜索只有一种操作符”@@”可以使用

1
select to_tsvector('There was a crooked man, and he walked a crooked mile') @@ to_tsquery('man & (walking | running)');
1
2
3
4
 ?column? 
----------
t
(1 row)
1
select to_tsvector('There was a crooked man, and he walked a crooked mile') @@ to_tsquery('man & (going | running)');
1
2
3
4
 ?column?
----------
f
(1 row)

这些信息已经足够我们讲这一篇的内容了。在GIN索引中我们将会更加深入的讲全文检索。

RD-trees

对于全文检索来说,首先,表中需要存储一个”tsvector”类型的字段(避免每次搜索都需要执行代价昂贵的转换),其次,这一行需要建立一个索引。一个有用的索引就是GiST。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
create table ts(doc text, doc_tsv tsvector);

create index on ts using gist(doc_tsv);

insert into ts(doc) values
('Can a sheet slitter slit sheets?'),
('How many sheets could a sheet slitter slit?'),
('I slit a sheet, a sheet I slit.'),
('Upon a slitted sheet I sit.'),
('Whoever slit the sheets is a good sheet slitter.'),
('I am a sheet slitter.'),
('I slit sheets.'),
('I am the sleekest sheet slitter that ever slit sheets.'),
('She slits the sheet she sits on.');

update ts set doc_tsv = to_tsvector(doc);

当然,在最后一步,把这一过程由触发器来做更加合适。

1
select * from ts;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
-[ RECORD 1 ]----------------------------------------------------
doc | Can a sheet slitter slit sheets?
doc_tsv | 'sheet':3,6 'slit':5 'slitter':4
-[ RECORD 2 ]----------------------------------------------------
doc | How many sheets could a sheet slitter slit?
doc_tsv | 'could':4 'mani':2 'sheet':3,6 'slit':8 'slitter':7
-[ RECORD 3 ]----------------------------------------------------
doc | I slit a sheet, a sheet I slit.
doc_tsv | 'sheet':4,6 'slit':2,8
-[ RECORD 4 ]----------------------------------------------------
doc | Upon a slitted sheet I sit.
doc_tsv | 'sheet':4 'sit':6 'slit':3 'upon':1
-[ RECORD 5 ]----------------------------------------------------
doc | Whoever slit the sheets is a good sheet slitter.
doc_tsv | 'good':7 'sheet':4,8 'slit':2 'slitter':9 'whoever':1
-[ RECORD 6 ]----------------------------------------------------
doc | I am a sheet slitter.
doc_tsv | 'sheet':4 'slitter':5
-[ RECORD 7 ]----------------------------------------------------
doc | I slit sheets.
doc_tsv | 'sheet':3 'slit':2
-[ RECORD 8 ]----------------------------------------------------
doc | I am the sleekest sheet slitter that ever slit sheets.
doc_tsv | 'ever':8 'sheet':5,10 'sleekest':4 'slit':9 'slitter':6
-[ RECORD 9 ]----------------------------------------------------
doc | She slits the sheet she sits on.
doc_tsv | 'sheet':4 'sit':6 'slit':2

怎么组织索引呢?不能直接使用R树,因为没有办法为文档类型定义一个边界。但是可以对此方法来做一些修改来使其能够应用到集合上,即所谓的RD-tree。在这里,一个集合被理解为是一个词组的集合,但是一般情况下,一个集合可以被表示为任意的东西。

RD树的一个思想是用边界集来代表一个边界矩形,即一个包含子集中所有元素的集合。

一个重要的问题出现了,怎么在索引行中表示集合。一个最直接的想法是列举集合中的所有元素。如下图所示

针对这个例子,用来获取满足doc_tsv @@ to_tsquery(‘sit’)条件的记录,我们可以下沉到那些只包含”sit”词组的节点。

这种表示方法有一个很明显的问题。一个文档中的词组的数量可以非常的大,因此索引行可以会有一个非常的尺寸来达到Toast模式,这会让索引变得低效。即使每个文档词组都很少,这些词组集合的合集也会非常大:越接近根节点的索引行越大。

这种表示方法对于别的数据类型可能有效,但是不适合全文索引。全文索引使用了另外一种更加紧凑的解决方案-被称之为签名树。使用过Bloom过滤器的人很熟悉这个。

每一个词组都可以表示成这样一个签名:其中一个比特位是1其余为都是0的定长的比特串。其中1的位置取决于这个词组的哈希运算的值。

文档的签名是文档中所有词组的签名OR计算的和。

让我们假设词组的签名如下

1
2
3
4
5
6
7
8
9
10
11
could    1000000
ever 0001000
good 0000010
mani 0000100
sheet 0000100
sleekest 0100000
sit 0010000
slit 0001000
slitter 0000001
upon 0000010
whoever 0010000

上面假设签名的长度是7,而词组的数量是11,因此不可避免的会出现哈希碰撞,即两个词组的签名是一致的。

则根据词组的签名,可以计算出文档的签名如下:

1
2
3
4
5
6
7
8
9
Can a sheet slitter slit sheets?                       0001101
How many sheets could a sheet slitter slit? 1001101
I slit a sheet, a sheet I slit. 0001100
Upon a slitted sheet I sit. 0011110
Whoever slit the sheets is a good sheet slitter. 0011111
I am a sheet slitter. 0000101
I slit sheets. 0001100
I am the sleekest sheet slitter that ever slit sheets. 0101101
She slits the sheet she sits on. 0011100

索引树可以被表示为如下形式

这种方法的优点很明显:索引行都具有相同的小尺寸,因此索引是很紧凑的。但是负面影响也很明显:牺牲了准确度。

让我们看一下同样的条件 doc_tsv @@ to_tsquery(‘sit’)。先计算出sit的签名为 0010000,一致性函数必须返回签名中包含这个比特位的所有节点。

比起前面的图,可以看出黄色的节点更多了,这意味着在搜索的过程中更多的节点被检索了,其中包含了一些假阳性(将不符合要求的节点判定为符合要求的节点)的无效节点。在这里,我们也检索到了”whoever”词组,因为这个词组和”sit”词组都有同样的签名。重要的是,这种匹配下不会发生假阴性(将符合要求的节点判定为不符合要求的节点),这意味着,不会错过需要的值。

初次之外,即使是不同的文档也会出现相同的签名。在我们的例子中,就有这样的例子。“I slit a sheet, a sheet I slit”和“I slit sheets”的签名都是0001100。即使叶子索引行中没有存储”tsvector”的值,仍有可能出现假阳性(被错误的命中)。

当然,这种情况下,索引方法可以要求索引引擎去表中重新检查结构,因此对于使用者来说看不到这种假阳性的数据。但是搜索的性能会受到影响。

事实上,在当前的实现中,签名的长度是124个字节而不是例子中的7位,因此上面的例子的出现的问题将会大大的减少。但是在现实中,被索引的文档也会更多。为了有效的减少假阳性的数量,索引的实现变的有些取巧:被索引的”tsvector”如果不是非常大的话(一页的1/16,如果是8KB页的话,则是半kb),”tsvector”将会取代签名,被存储在索引行中。

例子

为了去看在实际数据中索引是如何工作的,我们用打包的”pgsql-hackers”邮件做示例。这个例子中使用的版本包含了带有发送日期、主题、作者和文本的356125条信息

1
fts=# select * from mail_messages order by sent limit 1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
-[ RECORD 1 ]------------------------------------------------------------------------
id | 1572389
parent_id | 1562808
sent | 1997-06-24 11:31:09
subject | Re: [HACKERS] Array bug is still there....
author | "Thomas G. Lockhart" <Thomas.Lockhart@jpl.nasa.gov>
body_plain | Andrew Martin wrote: +
| > Just run the regression tests on 6.1 and as I suspected the array bug +
| > is still there. The regression test passes because the expected output+
| > has been fixed to the *wrong* output. +
| +
| OK, I think I understand the current array behavior, which is apparently+
| different than the behavior for v1.0x. +
...

增加和填充tsvector列,并且在此列上创建索引。这里我们将三个值(subject、author、text)增加到一个向量中来表明文档中不一定只有一个字段,可以是包含多个字段的。

1
2
3
4
fts=# alter table mail_messages add column tsv tsvector;

fts=# update mail_messages
set tsv = to_tsvector(subject||' '||author||' '||body_plain);
1
2
3
4
NOTICE:  word is too long to be indexed
DETAIL: Words longer than 2047 characters are ignored.
...
UPDATE 356125
1
fts=# create index on mail_messages using gist(tsv); 

正如看到的,有一部分的词因为太大了被丢弃了。但是索引最终被创建了,并且可以在后面的搜索查询中使用到。

1
2
fts=# explain (analyze, costs off)
select * from mail_messages where tsv @@ to_tsquery('magic & value');
1
2
3
4
5
6
7
8
9
                        QUERY PLAN
----------------------------------------------------------
Index Scan using mail_messages_tsv_idx on mail_messages
(actual time=0.998..416.335 rows=898 loops=1)
Index Cond: (tsv @@ to_tsquery('magic & value'::text))
Rows Removed by Index Recheck: 7859
Planning time: 0.203 ms
Execution time: 416.492 ms
(5 rows)

可以看到有898行记录匹配查询条件,索引方法通过recheck过滤掉了7859条记录。这表明降低准确度对效率产生了负面影响。

内部

为了分析索引中的内容,我们将再次使用”gevel”拓展:

1
2
3
fts=# select level, a
from gist_print('mail_messages_tsv_idx') as t(level int, valid bool, a gtsvector)
where a is not null;
1
2
3
4
5
6
7
8
9
10
 level |               a              
-------+-------------------------------
1 | 992 true bits, 0 false bits
2 | 988 true bits, 4 false bits
3 | 573 true bits, 419 false bits
4 | 65 unique words
4 | 107 unique words
4 | 64 unique words
4 | 42 unique words
...

在索引行中被存储的的”gtsvector”实际上是签名,也可能是”tsvector”。如果是tsvector的话,则会输出其包含的词库的数量,否则就输出签名中真假位的数量。

很明显,在根节点中,签名退化为 “全一”,也就是说,这个索引节点变得没有用,不具备选择性。(还有一个几乎是没有用的,只有四个false位)。

属性

让我们看看GiST访问方法的属性

1
2
3
4
5
select a.amname, p.name, pg_indexam_has_property(a.oid,p.name)
from pg_am a,
unnest(array['can_order','can_unique','can_multi_col','can_exclude']) p(name)
where a.amname = 'gist'
order by a.amname;
1
2
3
4
5
6
 amname |     name      | pg_indexam_has_property
--------+---------------+-------------------------
gist | can_order | f
gist | can_unique | f
gist | can_multi_col | t
gist | can_exclude | t

Gist不支持排序和唯一约束。但是索引可以建立在多个列上,并且用于排除约束。

下列的索引属性是可以用的

1
2
3
4
5
6
     name      | pg_index_has_property
---------------+-----------------------
clusterable | t
index_scan | t
bitmap_scan | t
backward_scan | f

而最有趣的属性是列的属性。有些属性是独立于操作符类的。

1
2
3
4
5
6
7
8
9
        name        | pg_index_column_has_property
--------------------+------------------------------
asc | f
desc | f
nulls_first | f
nulls_last | f
orderable | f
search_array | f
search_nulls | t

(不支持排序;索引不能用来搜索一个数组;支持NULL)。

对于剩余的两个属性,”distance_orderable” 和 “returnable”,将取决于使用的操作符类。例如,对于点:

1
2
3
4
        name        | pg_index_column_has_property
--------------------+------------------------------
distance_orderable | t
returnable | t

第一个属性说明距离操作符是可以用来搜索最近的邻居的。第二个属性说明索引可以用来使用index-only扫描。虽然叶子索引行存储的是矩形而不是一个点,但是访问方法仍然可以返回所需要的东西。

对于 间隔(intervals) 类型

1
2
3
4
        name        | pg_index_column_has_property
--------------------+------------------------------
distance_orderable | f
returnable | t

间隔类型没有定义距离函数,因此不能搜索最近的邻居。

对于全文搜索

1
2
3
        name        | pg_index_column_has_property
--------------------+------------------------------
distance_orderable | f

因为叶子行可以指包含签名而不包含数据本身,因此不支持仅索引扫描。这个损失是微小的,一般来说并不会对tsvector感兴趣。

其它数据类型

最后,我们将提到除了上面讨论的几种类型以外的支持GiST的数据类型

在标准类型中,有一个为了IP地址使用的inet。剩下的类型都是通过数据库插件来支持的。