PostgreSQL中的索引介绍-六（GiST）

开源软件联盟PostgreSQL分会 2019-11-22

4662

翻译：尚凯

审核：魏波

Egor Rogov

俄罗斯Postgres Professional公司数据库专家

之前我们讨论了PostgreSQL 索引引擎和访问方法的接口，以及两种访问方法：哈希索引和B-tree。本篇将讨论GiST索引。

Gist

GiST是“广义搜索树”的缩写。这是一个平衡的搜索树，就像前面讨论的“ b-tree”一样。

有什么区别？«btree»索引与比较语义是严格联系在一起的：支持«greater»，«less»和«equal»运算符（但非常强大！）。但是，现代数据库存储的数据类型对这些操作符毫无意义：譬如地理数据，文本文档，图像等。

GiST索引方法可以帮助我们处理这些数据类型。它允许定义规则来将任意类型的数据分布到一个平衡的树中，并且允许定义一个方法使用此表示形式来让某些运算符访问。例如，对于空间数据，GiST索引可以«accommodate» “容纳” R树，以支持相对位置运算符（位于左侧，右侧，包含等），而对于树形图，RD树可以支持相交或包含运算符。

由于可扩展性，可以在PostgreSQL中从头开始创建一种全新的方法：为此，必须实现与索引引擎的接口。但是，这不仅需要预先考虑索引逻辑，还需要对数据结构映射到页面，锁的有效实现以及对预写日志的支持。所有这些都需要具备高水平技能的开发人员和大量的人力投入。GiST通过接管低级问题并提供自己的界面来简化任务：几个与技术无关的函数，而与应用程序领域有关。从这个意义上讲，我们可以将GiST视为构建新访问方法的框架。

结构

GiST是由节点页面组成的高度平衡树。节点由索引行组成。

通常，叶节点的每一行(leafrow)都包含一些谓词（布尔表达式）和对表行（TID）的引用。索引数据(key)必须符合此谓词。

内部节点的每一行(internalrow)还包含一个谓词和对子节点的引用，并且子树的所有索引数据都必须满足此谓词。换句话说，内部行的谓词包括所有子行的谓词。GiST索引的这一重要特征取代了 B-tree的简单排序。

在GiST树中搜索使用专门的一致性函数（«consistent»）—由接口定义并以其自己的方式实现的函数之一，适用于每个受支持的操作符族。

为索引行调用一致性函数，并确定该行的谓词是否与搜索谓词一致（指定为“ 索引字段运算符表达式 ”）。对于内部行，此函数确定是否需要下降到相应的子树，而对于叶行，此函数确定索引的数据是否满足谓词。

搜索从根节点开始，就像普通的树搜索一样。一致性函数允许找出有意义的子节点（可能有多个）可以输入，而哪些子节点不需要输入。然后对找到的每个子节点重复该算法。如果节点是叶子节点，则一致性函数选择的行将作为结果之一返回。

搜索是深度优先的：算法首先尝试到达一个叶子节点。这样可以尽可能快地返回第一个结果（如果用户只对几个结果感兴趣，而不对所有结果感兴趣，那么这一点可能很重要）。

让我们再次注意，一致性函数与«greater», «less», 或«equal» 运算符无关。一致性函数的语义可能完全不同，因此，假定索引不以特定顺序返回值。

我们不会讨论GiST中值的插入和删除算法：其他一些接口函数执行这些操作。然而，有一点很重要。将新值插入索引后，将选择该值在树中的位置，以便尽可能少地扩展其父行的谓词（理想情况下完全不扩展）。但是，当删除一个值时，父行的谓词不再减少。仅在以下情况下会发生这种情况：将页面分为两部分（当页面没有足够的空间来插入新的索引行时），或者从头开始重新创建索引（使用REINDEX或VACUUM FULL命令）。因此，GiST索引用于频繁更改数据的效率会随着时间的推移而降低。

此外，我们将考虑一些针对各种数据类型和GiST有用属性的索引示例：

（1）点（和其他几何实体）和邻近搜索。

（2）区间和排除约束。

（3）全文搜索。

点的R树

我们将通过一个平面中的点的索引示例来说明上述内容（我们还可以为其他几何实体建立类似的索引）。常规的B-tree不适合这种数据类型的数据，因为没有为点定义比较运算符。

R-tree的想法是将平面拆分为矩形，这些矩形总共覆盖所有索引的点。索引行存储一个矩形，可以这样定义谓词：“所寻找的点位于给定的矩形内”。

R-tree的根将包含几个最大的矩形（可能相交）。子节点将包含较小尺寸的矩形，这些矩形嵌入到父节点中，并且覆盖所有基础点。

从理论上讲，叶节点必须包含要索引的点，但是所有索引行中的数据类型必须相同，因此，再次存储矩形，但是将«collapsed» “折叠”成点。

为了可视化这种结构，我们提供了R-tree的三个层次的图像。点是机场的坐标（类似于演示数据库的“ airports”表中的坐标，但提供了来自openflights.org的更多数据）。

一级：两个大的相交的可见矩形。

第二级：将大矩形分割成较小的区域。

第三级：每个矩形包含的点数最多可以容纳一个索引页。

现在让我们考虑一个非常简单的“一级”示例：

postgres=# create table points(p point);
postgres=# insert into points(p) values
  (point '(1,1)'), (point '(3,2)'), (point '(6,3)'),
  (point '(5,5)'), (point '(7,8)'), (point '(8,6)');


postgres=# create index on points using gist(p);

通过这种拆分，索引结构将如下所示：

创建的索引可用于加快以下查询的速度，例如：“查找给定矩形中包含的所有点”。可以将这种情况形式化如下：p <@ box '(2,1),(6,3)'（来自«points_ops»运算符族的运算符<@意思是“包含在”）：

postgres=# set enable_seqscan = off;
postgres=# explain(costs off) select * from points where p <@ box '(2,1),(7,4)';
                  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）。

postgres=# select * from points where p <@ box '(2,1),(7,4)';
   p  
-------
 (3,2)
 (6,3)
(2 rows)

内部

不幸的是，通常“pageinspect”不允许查看GiST索引。但是还有另一种方法：«gevel»扩展。它不包括在标准安装中，因此请参阅安装说明（http://www.sai.msu.su/~megera/wiki/Gevel）。

如果一切顺利，将为您提供三个功能。

首先，我们可以获得一些统计信息：

postgres=# select * from gist_stat('airports_coordinates_idx');
                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页，并且该索引包含四个级别：上图显示了根级别和两个内部级别，而第四级是叶子。

实际上，八千个点的索引会小很多：此处创建时使用10％的填充因子来创建。

其次，我们可以输出索引树：

postgres=# select * from gist_tree('airports_coordinates_idx');
                                       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»（边界矩形）。例如，注意顶层的五行：

postgres=# select level, a from gist_print('airports_coordinates_idx')
  as t(level int, valid bool, a box) where level = 1;
 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子句中排序顺序的规范，而不是列名的常规规范。以下是此类查询的示例：

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

p <-> point '(4,7)'这是一个使用排序运算符<->的表达式，它表示从一个参数到另一个参数的距离。查询的意思是返回最接近点（4,7）的两个点。这样的搜索称为k-NN-k近邻搜索。

为了支持此类查询，访问方法必须定义一个附加的距离函数，并且必须在适当的运算符类（例如，用于点的«points_ops»类）中包括排序运算符。以下查询显示了运算符及其类型（«s»—搜索和«o»—排序）：

postgres=# 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;




      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 above
 <->(point,point)  | o           |           15  distance
 <@(point,box)     | s           |           28  contained in rectangle
 <@(point,polygon) | s           |           48  contained in polygon
 <@(point,circle)  | s           |           68  contained in circle
(9 rows)

还显示了策略的数量，并解释了其含义。显然，比“ btree”策略要多得多，只有部分策略支持点。可以为其他数据类型定义不同的策略。

距离函数是为索引元素调用的，它必须根据表达式（“ 索引字段排序运算符”表达式）定义的值来计算到给定元素距离（考虑运算符的语义）。对于叶子元素，这只是到索引值的距离。对于内部元素，该函数必须返回到叶子元素的最小距离。因为遍历所有子行代价非常大，允许该函数乐观地低估距离，但代价是降低搜索效率，但是，绝不允许该函数高估距离，因为这会破坏索引的工作。

distance函数可以返回任何可排序类型的值（对于排序值，PostgreSQL将使用来自«btree»访问方法的适当运算符族的比较语义，如前所述）。

对于平面中的点，距离可以用一种非常普通的方式来解释：(x1,y1) <-> (x2,y2)等于横坐标和纵坐标的差的平方之和的平方根。从点到边界矩形的距离被认为是从点到该矩形的最小距离；如果点位于矩形内，则为零。无需遍历子点即可轻松计算该值，并且该值肯定不大于到任何子点的距离。

让我们考虑以上查询的搜索算法。

搜索从根节点开始。该节点包含两个边界矩形。到（1,1）-（6,3）的距离是4.0，到（5,5）-（8,8）的距离是1.0。

按照增加距离的顺序遍历子节点。这样，我们首先下降到最近的子节点并计算到这些点的距离（我们将在图中显示数字以提高可见性）：

该信息足以返回前两个点（5,5）和（7,8）。由于我们知道到矩形（1,1）-（6,3）内的点的距离为4.0或更大，因此我们不必下降到第一个子节点。

但是，如果我们需要找到前三个点呢？

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

尽管第二个子节点包含所有这些点，但是如果不查看第一个子节点，我们将无法返回（8,6），因为该节点可以包含更近的点（因为4.0 <4.1）。

对于内部行，此示例阐明了对距离函数的要求。通过为第二行选择较小的距离（4.0而不是实际的4.5），我们降低了效率（算法不必要地开始检查额外的节点），但并未破坏算法的正确性。

直到最近，GiST还是唯一能够处理排序运算符的访问方法。但是情况发生了变化：RUM访问方法（将进一步讨论）已经加入了这组方法，有用的经典B-tree也不太可能加入它们：我们的同事Nikita Glukhov开发的补丁正在由社区讨论。

R树的区间

使用GiST访问方法的另一个示例是区间的索引，例如时间区间（“ tsrange”类型）。不同的是，内部节点将包含边界区间，而不是边界矩形。

让我们考虑一个简单的例子。我们将出租一间小屋并将预订时间区间存储在一张表中：

postgres=# create table reservations(during tsrange);
postgres=# insert into reservations(during) values
('[2016-12-30, 2017-01-09)'),
('[2017-02-23, 2017-02-27)'),
('[2017-04-29, 2017-05-02)');
postgres=# create index on reservations using gist(during);

例如，可以使用索引来加速以下查询：

postgres=# select * from reservations where during && '[2017-01-01, 2017-04-01)';
                    during                    
-----------------------------------------------
 ["2016-12-30 00:00:00","2017-01-08 00:00:00")
 ["2017-02-23 00:00:00","2017-02-26 00:00:00")
(2 rows)
postgres=# explain (costs off) select * from reservations where during && '[2017-01-01, 2017-04-01)';
                                     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)

&&区间运算符表示交集；因此，查询必须返回与给定区间相交的所有区间。对于这种运算符，一致性函数确定给定的区间是与内部行还是叶行中的值相交。

请注意，尽管为区间定义了比较运算符，但这不是以一定顺序获取区间。我们可以为区间使用«btree»索引，但是在这种情况下，我们将必须在不支持以下操作的情况下进行操作：

postgres=# 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;




         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)

内部

我们可以使用相同的«gevel»扩展查看内部。需要记住在对gist_print的调用中更改数据类型：

postgres=# select level, a from gist_print('reservations_during_idx')
as t(level int, valid bool, a tsrange);
 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索引可用于支持排除约束（EXCLUDE）。

排除约束确保任何两个表行的给定字段在某些运算符方面都不会彼此“对应”。如果选择“等于”运算符，我们将确切地获得唯一约束：任意两行的给定字段彼此不相等。

索引和唯一性约束均支持排除约束。我们可以选择任何一个运算符，以便：

1. 索引方法-«can_exclude»属性（例如，«btree»，GiST或SP-GiST，但不包含GIN）支持该方法。

2. 它是可交换的，即满足条件：a运算符b = b运算符a。

这是合适的策略和操作符示例列表（操作符可以具有不同的名称，并且不适用于所有数据类型）：

· 对于“ btree”：

· “等于” =

· 对于GiST和SP-GiST：

· “交集” &&

· “并存” ~=

· “邻接” -|-

请注意，我们可以在排除约束中使用相等运算符，但这是不切实际的：唯一约束将更加有效。这就是为什么我们在讨论B树时没有触及排除约束的原因。

让我们提供一个使用排除约束的示例。不保留相交的区间。

postgres=# alter table reservations add exclude using gist(during with &&);

创建排除约束后，我们可以添加行：

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

但是尝试在表中插入相交的区间会导致错误：

postgres=# insert into reservations(during) values ('[2017-05-15, 2017-06-15)');
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»扩展

让问题复杂化。我们扩展了自己的小业务，并打算出租几栋小屋：

postgres=# alter table reservations add house_no integer default 1;

我们需要更改排除约束，以便考虑房屋门牌号。但是，GiST不支持整数的相等运算：

postgres=# alter table reservations drop constraint reservations_during_excl;


postgres=# alter table reservations add exclude using gist(during with &&, house_no with =);
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 ”扩展名会有所帮助，它添加了对B树固有操作的GiST支持。GiST最终可以支持任何运算符，那么为什么我们不应该使它支持“更大”，“更少”和“相等”运算符呢？

postgres=# create extension btree_gist;
postgres=# alter table reservations add exclude using gist(during with &&, house_no with =);

现在我们仍然无法在同一日期预订第一座小屋：

postgres=# insert into reservations(during, house_no) values ('[2017-05-15, 2017-06-15)', 1);
ERROR: conflicting key value violates exclusion constraint "reservations_during_house_no_excl"

但是，我们可以保留第二个：

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

但是请注意，尽管GiST可以以某种方式支持«greater», «less»和«equal»运算符，但B-tree在这方面做得更好。因此，仅在本质上需要GiST索引的情况下才值得使用此技术，就像我们的示例一样。

用于全文搜索的RD树

让我们从对PostgreSQL全文搜索的简单介绍开始（如果您知道的话，可以跳过本节）。

全文搜索的任务是从文档集中选择与搜索查询匹配的那些文档。（如果有很多匹配的文档，那么找到最佳的匹配很重要，但是在这里我们不做讨论了。）

出于搜索目的，文档被转换为专门的类型“ tsvector”，其中包含词素（lexemes）及其在文档中的位置。词素（lexemes）是转换为适合搜索形式的单词。例如，单词通常会转换为小写字母，并且变量的结尾会被截断：

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

我们还可以看到，某些单词（称为停止单词）被完全丢弃（«there», «was», «a», «and», «he»），因为它们可能出现得太频繁，搜索它们没有意义。当然，所有这些转换都可以配置，但这是另一回事。

搜索查询用另一种类型表示：«tsquery»。大致上，一个查询由一个或几个连接词连接的词素组成：«and»&，«or»|，«not»！..我们也可以使用括号来阐明操作优先级。

postgres=# select to_tsquery('man & (walking | running)');
         to_tsquery         
----------------------------
 'man' & ( 'walk' | 'run' )
(1 row)

全文搜索仅使用一个匹配运算符@@

postgres=# select to_tsvector('There was a crooked man, and he walked a crooked mile') @@ to_tsquery('man & (walking | running)');
 ?column?
----------
 t
(1 row)




postgres=# select to_tsvector('There was a crooked man, and he walked a crooked mile') @@ to_tsquery('man & (going | running)');
 ?column?
----------
 f
(1 row)

目前该信息已足够。在下一篇介绍GIN索引的文章中，我们将对全文搜索进行更深入的研究。

RD树

为了快速进行全文搜索，首先，该表需要存储一列“ tsvector”类型的列（以避免每次搜索时都进行昂贵的转换），其次，必须在此列上建立索引。GiST是一种可能的访问方法。

postgres=# create table ts(doc text, doc_tsv tsvector);
postgres=# create index on ts using gist(doc_tsv);
postgres=# 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.');
postgres=# update ts set doc_tsv = to_tsvector(doc);

当然，将触发器委托给最后一步（将文档转换为“ tsvector”）很方便。

postgres=# select * from ts;
-[ 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树（RD代表“Russian Doll”）。在这种情况下，集合被理解为词素集合，但是通常，集合可以是任何集合。

RD树的一个思想是用边界集（即包含子集的所有元素的集）替换边界矩形。

一个重要的问题是如何在索引行中表示集合。最直接的方法就是枚举集合中的所有元素。如下所示：

例如，对于按条件访问，doc_tsv @@ to_tsquery('sit')我们只能下降到包含«sit»词素的那些节点：

这种表示存在明显的问题。文档中的词素数量可能非常大，因此索引行会非常大，并进入TOAST中，从而使索引的效率大大降低。即使每个文档只有很少的唯一词素，集合的并集仍然可能非常大：根目录越高，索引行就越大。

有时会使用这样的表示形式，但针对其他数据类型。全文搜索使用另一个更紧凑的解决方案-签名树。所有处理Bloom过滤器的人都非常熟悉它的思路。

每个词素都可以用其签名表示：一定长度的位串，其中除一位以外的所有位均为零。该位的位置由所述词位的散列函数的值来确定（我们之前讨论的散列函数内部）。

文档签名是所有文档词素的按位或按位的签名。

让我们假设以下词素签名：

could    1000000
ever     0001000
good     0000010
mani     0000100
sheet    0000100
sleekest 0100000
sit      0010000
slit     0001000
slitter  0000001
upon     0000010
whoever  0010000

然后，文档签名如下：

Can a sheet slitterslit sheets?                      0001101
How many sheets could asheet slitter slit?            1001101
I slit a sheet, a sheetI slit.                        0001100
Upon a slitted sheet Isit.                            0011110
Whoever slit the sheetsis a good sheet slitter.       0011111
I am a sheetslitter.                                 0000101
I slit sheets.                                        0001100
I am the sleekest sheetslitter that ever slit sheets. 0101101
She slits the sheet shesits on.                       0011100

索引树可以表示如下：

这种方法的优点显而易见：索引行的大小相等，并且这样的索引很紧凑。但缺点也很明显：为了紧凑而牺牲了准确性。

让我们考虑相同的条件doc_tsv @@ to_tsquery('sit')。让我们以与文档相同的方式计算搜索查询的签名：本例中为0010000。一致性函数必须返回其签名至少包含查询签名一位的所有子节点：

与上图比较：我们可以看到树变成了黄色，这意味着出现误报，并且在搜索过程中经过了过多的节点。在这里，我们选择了“ whoever”语素，但不幸的是，其签名与“sit”语素的签名相同。重要的是，模式中不会出现误报，也就是说，我们确保不要错过所需的值。

此外，可能会发生这样的情况，即不同的文档也将获得相同的签名：在我们的示例中，不幸的文档是“I slit a sheet, asheet I slit”和“I slit sheets”（都具有0001100的签名）。而且，如果叶子索引行未存储«tsvector»的值，则索引本身将给出假肯定。当然，在这种情况下，该方法将要求索引引擎使用表重新检查结果，因此用户不会看到这些误报。但是搜索效率可能会受到影响。

实际上，签名在当前实现中为124字节大小，而不是图中的7位，因此与示例相比，上述问题发生的可能性要小得多。但实际上，还有更多文档也被索引了。为了以某种方式减少索引方法的误报次数，该实现有些棘手：被索引的“ tsvector”存储在叶索引行中，但前提是其大小不大（略小于索引的1/16的一个页面，对于8 KB的页面大约为半KB）。

例

要了解对实际数据进行索引的方式，让我们以“ pgsql-hackers”电子邮件归档为例。该示例中使用的版本包含356125条消息，其中包含发送日期，主题，作者和文本：

fts=# select * from mail_messages order by sent limit 1;
-[ 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”类型的列并构建索引。在这里，我们将三个值合并在一个向量中（主题，作者和消息文本），以表明文档不必是一个字段，而是可以包含完全不同的任意部分。

fts=# alter table mail_messages add column tsv tsvector;




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

如我们所见，一些单词由于太大而被删除。但是该索引最终会创建，并且可以支持搜索查询：

fts=# explain (analyze, costs off)
select * from mail_messages where tsv @@ to_tsquery('magic & value');
                        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行一起，访问方法返回了7859多行，这些行通过重新检查表而被过滤掉。这证明了准确性损失对效率的负面影响。

内部

为了分析索引的内容，我们将再次使用«gevel»扩展：

fts=# select level, a
from gist_print('mail_messages_tsv_idx') as t(level int, valid bool, a gtsvector)
where a is not null;
 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”。如果向量可用，则输出包含词素（唯一单词）的数量，否则，包含签名中的真位和假位的数量。

显然，在根节点中，签名退化为“all ones”，即一个索引级别变得绝对无用（另外一个索引级别变得几乎无用，只有四个假位）。

属性

让我们看一下GiST访问方法的属性（使用之前提供的查询）：

 amname |     name      | pg_indexam_has_property
--------+---------------+-------------------------
 gist   | can_order     | f
 gist   | can_unique    | f
 gist   | can_multi_col | t
 gist   | can_exclude   | t

不支持值的排序和唯一约束。如我们所见，索引可以建立在几列上，并用于排除约束中。

以下索引层属性可用：

     name      | pg_index_has_property
---------------+-----------------------
 clusterable   | t
 index_scan    | t
 bitmap_scan   | t
 backward_scan | f

最有趣的属性是列层的属性。一些属性独立于运算符类：

        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»将取决于所使用的运算符类。例如，对于点points，我们将得到：

        name        | pg_index_column_has_property
--------------------+------------------------------
 distance_orderable | t
 returnable         | t

第一个属性表明距离运算符可用于搜索最近的邻居。第二个属性告诉索引可以用于仅索引扫描。尽管叶索引行存储矩形而不是点，但是访问方法可以返回所需的内容。

以下是区间的属性：

        name        | pg_index_column_has_property
--------------------+------------------------------
 distance_orderable | f
 returnable         | t

对于区间，距离函数没有定义，因此无法搜索邻近值。

对于全文搜索，我们得到：

        name        | pg_index_column_has_property--------------------+------------------------------
 distance_orderable | f
 returnable         | f

因为叶行只能包含签名而不能包含数据本身，所以失去了对仅索引扫描的支持。但是，这是一个很小的损失，因为无论如何都没有人对«tsvector»类型的值感兴趣：该值用于选择行，而它是需要显示的源文本，但无论如何都不会从索引中丢失。

其他数据类型

最后，除了已经讨论过的几何类型（以点为例），区间和全文搜索类型之外，我们还将提及GiST访问方法当前支持的其他几种类型。

在标准类型中，这是IP地址的“ inet ” 类型。所有其余的都通过扩展添加：

· cube为多维数据集提供了“cube”数据类型。对于这种类型，就像在平面上的几何类型一样，定义了GiST运算符类：R树，支持搜索邻近值。

· seg为具有指定精度的边界的间隔提供“ seg”数据类型，并为此数据类型（R树）添加GiST索引支持。

· intarray扩展了整数数组的功能，并增加了对它们的GiST支持。实现了两个运算符类：“ gist__int_ops”（带有索引行中键的完整表示的RD树）和“ gist__bigint_ops”（签名RD树）。第一类可用于小数组，第二类可用于大数组。

· ltree为树状结构添加了“ ltree”数据类型，并为此数据类型（RD-tree）提供了GiST支持。

· pg_trgm添加了一个专门的运算符类《 gist_trgm_ops》，用于在全文搜索中使用三元组。但这将与GIN索引一起进一步讨论。

下期预告

下一篇我们将讲述SP-GiST索引，SP-GiST适用于可以将空间递归划分为非相交区域的结构。

作者的往期文章

PostgreSQL中的索引介绍-五（Btree索引）

欢迎投稿

中国开源软件推进联盟PostgreSQL分会，欢迎大家积极投稿，向PGer分享自己的实践经验、心得体会，共建PG中国生态。

投稿邮箱：

press@postgresqlchina.com

postgresql

最后修改时间：2019-11-22 18:58:43

文章转载自开源软件联盟PostgreSQL分会，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

PostgreSQL中的索引介绍-六（GiST）

评论