本系列的内容主要翻译自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
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
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
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