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

原文: Indexes in PostgreSQL — 6 (SP-GiST)

系列文章索引

我们已经讨论了PostgreSQL的索引引擎访问方法接口以及三个索引方法:哈希索引B树GiST。这篇文章中,我们将讨论SP-GiST。

SP-GiST

首先,关于这个名字要说一下。名字中的”GiST”暗指其和同名的GiST索引方法有相似的地方。相似的地方是指:两者都是通用搜索树,都提供了一个构建不同索引方法的通用框架。

“SP”主要是指空间分区(space partitioning)。这里的空间我们通常会理解成我们习惯上所认为的空间,比如说一个二维的平面。但是我们将看到这里的空间可以是任何值域。

SP-GiST适用于那些空间可以被递归的分割成非相交区域的结构(这一点和GiST不同)。这类树包含四叉树(comprises quadtrees)、K维树 (k-D trees)以及弧形树( radix trees)。

结构

所以,SP-GiST的思想是将值域划分为彼此不覆盖的子域,而子域有可以被进一步分割。像这样的分割会导致不平衡树(不像B树和GiST树)

不相交的特性简化了插入和搜索过程的策略。另一方面,作为一项规则,诱导的树是低分枝的。例如,一个四叉树通常有四个子节点(不像B树。子节点的数目可以是上百个)和更高的深度。像这样的树很适合在内存中工作,但是索引是存储在磁盘上的。因此为了减少IO操作的数量,必须将节点打包成页,但是高效的做到这一点并不容易。此外,由于分支的深度不同,在索引中找到不同数值的时间也可能不同。

这个访问方法和GiST一样,做一些底层的工作(并发访问、锁、日志以及纯粹的搜索算法),同时提供了专门的简化接口,来方便增加新的数据和分区算法。

SP-GiST内部的节点存储了对子节点的引用;可以给每一个引用定义一个标签。此外,一个内部节点可以存储一个被叫做prefix的值。实际上这个值不强制一定是前缀,它可以是任意一个满足所有子节点的谓词。

SP-GiST的叶子节点存储了一个索引类型的值和一个对表行的引用。被索引的数据本身(索引键)可以作为这个索引类型的值,但不是必须的:一个缩短类型的值会被存储。

此外,叶子节点可以被分组为列表。因此,一个内部节点不仅可以引用一个值,也可以引用整个列表

请注意,叶子节点的前缀、标签以及值都有自己的数据类型,是彼此独立的。

和GiST一样,为搜索定义的主要函数是一致性函数。这个函数在一个树节点上被调用,并且返回一组子节点,这些子节点的值和搜索的谓语一致。对于一个子节点,一致性函数决定了这个节点中的索引值是否符合搜索谓词。

搜索从根节点开始,一致性函数决定有必要访问的子节点。该算法会在找到的每个子节点上重复运行。该搜索是深度优先的。

在物理层面,索引节点被打包成页,以便在IO层面能让节点的工作更有效率。请注意,一个页面可以包含内部节点和叶子节点,但是不能同时包含。

例子:四叉树

四叉树可以索引平面上的点。思想是根据中心点将平面划分为四个象限,这颗树的分支深度可以是不同的,其深度取决于当前象限内点的密度。

下面是一个样例数据,其数据来源是用openflights.org上的数据对 demo database做了扩充。

首先将平面划分为四个象限

然后再分割每个象限

接着分割,直到得到最后的分区

让我们来提供一个例子来说明更多的细节。这种情况下我们的分区像下图所示。

象限的编号如左图所示。为了明确期间,子节点的象限编号也是按照这个顺序。这种例子下,一个可能的索引结构如下图所示。每个内部节点最多可以引用四个节点,每个引用都可以用象限的编号作为标签。但是实际的实现中没有标签,因为存储四个引用的固定数组会更加方便。

1
2
3
4
5
6
7
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 points_quad_idx on points using spgist(p);

在这个例子中,默认使用的操作符类是”quad_point_ops”,其包含下面这些操作

1
2
3
4
5
6
7
8
postgres=# select amop.amopopr::regoperator, amop.amopstrategy
from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop
where opc.opcname = 'quad_point_ops'
and opf.oid = opc.opcfamily
and am.oid = opf.opfmethod
and amop.amopfamily = opc.opcfamily
and am.amname = 'spgist'
and amop.amoplefttype = opc.opcintype;
1
2
3
4
5
6
7
8
9
     amopopr     | amopstrategy
-----------------+--------------
<<(point,point) | 1 strictly left
>>(point,point) | 5 strictly right
~=(point,point) | 6 coincides
<^(point,point) | 10 strictly below
>^(point,point) | 11 strictly above
<@(point,box) | 8 contained in rectangle
(6 rows)

作为例子,我们来看查询select * from points where p >^ point ‘(2,7)’将被怎么执行

我们从根节点开始应用一致性函数去选择哪些节点可以被下沉。对于操作符>^,函数将点(2,7)与中心点(4,4)比较以后,选择出可能包含寻求的点数的象限,这个例子中,是第一和第四象限。

在第一象限的节点中,我们再次使用一致性函数来选择出可能的子节点。中心点是(6,6),我们需要再次寻找子节点的第一象限和第四象限。

第一象限的叶子节点是包含了(8,6)和(7,8)的列表,其中只有(7,8)是符合要求的。对第四象限的引用都是空的。

(4,4)节点的第四象限也是空的,因此搜素就完成了。

1
2
3
postgres=# set enable_seqscan = off;

postgres=# explain (costs off) select * from points where p >^ point '(2,7)';
1
2
3
4
5
                   QUERY PLAN                  
------------------------------------------------
Index Only Scan using points_quad_idx on points
Index Cond: (p >^ '(2,7)'::point)
(2 rows)

内部

我们可以使用“gevel”插件来看SP-GiST索引的内部情况。

让我们以示例数据为例

1
demo=# create index airports_coordinates_quad_idx on airports_ml using spgist(coordinates);

首先,我们获取索引的一些统计信息

1
demo=# select * from spgist_stats('airports_coordinates_quad_idx');
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
           spgist_stats           
----------------------------------
totalPages: 33 +
deletedPages: 0 +
innerPages: 3 +
leafPages: 30 +
emptyPages: 2 +
usedSpace: 201.53 kbytes+
usedInnerSpace: 2.17 kbytes +
usedLeafSpace: 199.36 kbytes+
freeSpace: 61.44 kbytes +
fillRatio: 76.64% +
leafTuples: 5993 +
innerTuples: 37 +
innerAllTheSame: 0 +
leafPlaceholders: 725 +
innerPlaceholders: 0 +
leafRedirects: 0 +
innerRedirects: 0
(1 row)

然后,我们输出索引数本身

1
2
3
4
5
6
7
8
9
10
11
12
demo=# select tid, n, level, tid_ptr, prefix, leaf_value
from spgist_print('airports_coordinates_quad_idx') as t(
tid tid,
allthesame bool,
n int,
level int,
tid_ptr tid,
prefix point, -- prefix type
node_label int, -- label type (unused here)
leaf_value point -- list value type
)
order by tid, n;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
   tid   | n | level | tid_ptr |      prefix      |    leaf_value
---------+---+-------+---------+------------------+------------------
(1,1) | 0 | 1 | (5,3) | (-10.220,53.588) |
(1,1) | 1 | 1 | (5,2) | (-10.220,53.588) |
(1,1) | 2 | 1 | (5,1) | (-10.220,53.588) |
(1,1) | 3 | 1 | (5,14) | (-10.220,53.588) |
(3,68) | | 3 | | | (86.107,55.270)
(3,70) | | 3 | | | (129.771,62.093)
(3,85) | | 4 | | | (57.684,-20.430)
(3,122) | | 4 | | | (107.438,51.808)
(3,154) | | 3 | | | (-51.678,64.191)
(5,1) | 0 | 2 | (24,27) | (-88.680,48.638) |
(5,1) | 1 | 2 | (5,7) | (-88.680,48.638) |
...

但是请记住,”spgist_print”输出的不是叶子节点中的所有值,而是列表中的第一个。因此,这里展示的是索引的结构而不是全部的内容。

K维树

同样是平面上的点,我们也可以使用另外一种分区方法。

让我们先画一条横着的线经过第一个被索引的点,这条直线将平面分割维上下两个部分。下一个索引的点就处在这两个部分的一个。通过第二个点,画一条竖着的线,将这个部分再次划分为左右两个部分。然后我们再画一条水平的线通过下一个点,再画一条垂直的线经过下一个点,如此反复。

这样建立的树所有内部的节点都只有两个子节点的引用,这两个引用都可以通向下一个内部节点或者通向叶子节点的列表。

这种方法可以很容易的推广到K维空间,因此在文献中,这些树也被称为k-dimensional (k-D trees)

以机场的例子解释该方法

首先将平面划分为上下两个部分

然后将每个部分分割为左右两个部分

为了使用这样的分区,我们需要在创建索引的时候明确的指定操作符类“kd_point_ops”

1
postgres=# create index points_kd_idx on points using spgist(p kd_point_ops);

这个操作符类包含和默认的”quad_point_ops”完全相同的操作符。

内部

在查看树结构的时候,我们需要考虑到,在这种情况下,前缀只是一个坐标,而不是一个点。

因为是垂直或者水平分割的,因此前缀只需要一个数字就可以表示。

1
2
3
4
5
6
7
8
9
10
11
12
demo=# select tid, n, level, tid_ptr, prefix, leaf_value
from spgist_print('airports_coordinates_kd_idx') as t(
tid tid,
allthesame bool,
n int,
level int,
tid_ptr tid,
prefix float, -- prefix type
node_label int, -- label type (unused here)
leaf_value point -- list node type
)
order by tid, n;
1
2
3
4
5
6
7
8
9
10
11
   tid   | n | level | tid_ptr |   prefix   |    leaf_value
---------+---+-------+---------+------------+------------------
(1,1) | 0 | 1 | (5,1) | 53.740 |
(1,1) | 1 | 1 | (5,4) | 53.740 |
(3,113) | | 6 | | | (-7.277,62.064)
(3,114) | | 6 | | | (-85.033,73.006)
(5,1) | 0 | 2 | (5,12) | -65.449 |
(5,1) | 1 | 2 | (5,2) | -65.449 |
(5,2) | 0 | 3 | (5,6) | 35.624 |
(5,2) | 1 | 3 | (5,3) | 35.624 |
...

例子:弧度树

我们也可以用SP-GiST来为字符串实现一个弧度树。弧度树的思想是要索引的字符串并不完全存储在一个叶子节点中,而是通过串联的存储在这个节点以上直到根部的值来获取到。

假设我们需要索引几个地址:”postgrespro.ru”,”postgrespro.com”,”postgresql.org”和”planet.postgresql.org”

1
2
3
4
5
postgres=# create table sites(url text);

postgres=# insert into sites values ('postgrespro.ru'),('postgrespro.com'),('postgresql.org'),('planet.postgresql.org');

postgres=# create index on sites using spgist(url);

树的结构如下所示:

数字的叶子节点存储了所有子节点的前缀。例如,在”stgres”这个节点的子节点中的值都以 “p” + “o” + “stgres”为前缀。

与四叉树不同的是,每一个指向子节点的指针中都使用了额外的一个字符(更精确的来说是两个字节,但是这并不重要)作为标签。

“text_ops “运算符类支持类似B-树的运算符: “equal”, “greater”, and “less”:

1
2
3
4
5
6
7
8
postgres=# select amop.amopopr::regoperator, amop.amopstrategy
from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop
where opc.opcname = 'text_ops'
and opf.oid = opc.opcfamily
and am.oid = opf.opfmethod
and amop.amopfamily = opc.opcfamily
and am.amname = 'spgist'
and amop.amoplefttype = opc.opcintype;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
     amopopr     | amopstrategy 
-----------------+--------------
~<~(text,text) | 1
~<=~(text,text) | 2
=(text,text) | 3
~>=~(text,text) | 4
~>~(text,text) | 5
<(text,text) | 11
<=(text,text) | 12
>=(text,text) | 14
>(text,text) | 15
^@(text,text) | 28
(10 rows)

带标记的运算符的区别在于,他们操作的是字节而不是字符。

有的时候,用弧度树的形式表示可能会比B树更加紧凑的,因为数值不是完全存储的,而是通过树的下降来重建字符串。

考虑到这个查询:select * from sites where url like ‘postgresp%ru’。它可以通过索引来执行

1
2
postgres=# set enable_seqscan = off;
postgres=# explain (costs off) select * from sites where url like 'postgresp%ru';
1
2
3
4
5
6
                                  QUERY PLAN                                  
------------------------------------------------------------------------------
Index Only Scan using sites_url_idx on sites
Index Cond: ((url ~>=~ 'postgresp'::text) AND (url ~<~ 'postgresq'::text))
Filter: (url ~~ 'postgresp%ru'::text)
(3 rows)

实际上索引是用来寻找大于等于postgresp并且小于postgresq的值,然后从结果中选择匹配的值。

首先一致性函数必须决定出要下降到p的哪个子节点。显然,需要下降到”p “+”o “+”stgres”

对于 “stgres “节点,需要再次调用一致性函数来检查。 这次下降到”postgres “+”p “+”ro”。

对于”ro.”节点以及所有的叶子节点,一致性函数将返回TRUE,因此索引方法返回了两个值:”postgrespro.com “和 “postgrespro.ru”。然后在过滤阶段从他们中选择匹配的值。

内部

在查看树状结构的时候,需要将数据类型考虑在内

1
2
3
4
5
6
7
8
9
10
11
postgres=# select * from spgist_print('sites_url_idx') as t(
tid tid,
allthesame bool,
n int,
level int,
tid_ptr tid,
prefix text, -- prefix type
node_label smallint, -- label type
leaf_value text -- leaf node type
)
order by tid, n;

原文中并没有,下面的结果是自己运行后结果。 但是由于原文中插入的数据过少,展示出的结果只有一个层级,因此我在里面又插入了几千条记录得出的内部树结构。node_label的值是字符的ASCII码,例如112是p、 119 是 w。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
   tid    | allthesame | n  | level | tid_ptr | prefix | node_label |      leaf_value      
----------+------------+----+-------+---------+--------+------------+----------------------
(1,1) | f | 0 | 1 | | | 112 |
(1,1) | f | 1 | 1 | | | 119 |
(3,4) | | | 2 | | | | lanet.postgresql.org
(3,85) | | | 3 | | | | 63.com
(3,87) | | | 3 | | | | d.com
(3,89) | | | 4 | | | | cuweather.com
(3,91) | | | 4 | | | | swers.yahoo.com
(3,100) | | | 3 | | | | 60.cn
(3,103) | | | 3 | | | | ao123.com
(3,104) | | | 3 | | | | sn.com
(3,109) | | | 3 | | | | q.com
(3,112) | | | 3 | | | | acebook.com
(5,1) | f | 0 | 2 | | ww. | 49 |
(5,1) | f | 1 | 2 | | ww. | 51 |
(5,1) | f | 2 | 2 | | ww. | 97 |
(5,1) | f | 3 | 2 | | ww. | 98 |
(5,1) | f | 4 | 2 | | ww. | 99 |
(5,1) | f | 5 | 2 | | ww. | 100 |
(5,1) | f | 6 | 2 | | ww. | 101 |
(5,1) | f | 7 | 2 | | ww. | 102 |
...

属性

然后来看一下 SP-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 = 'spgist'
order by a.amname;
1
2
3
4
5
6
7
 amname |     name      | pg_indexam_has_property 
--------+---------------+-------------------------
spgist | can_order | f
spgist | can_unique | f
spgist | can_multi_col | f
spgist | can_exclude | t
(4 rows)

spgist不支持用来排序也不能做唯一约束。此外,这样的索引也不能建立在多个字段上,但是允许用来做唯一约束。

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

1
2
3
4
select p.name, pg_index_has_property('sites_url_idx'::regclass,p.name)
from unnest(array[
'clusterable','index_scan','bitmap_scan','backward_scan'
]) p(name);
1
2
3
4
5
6
7
8
     name      | pg_index_has_property 
---------------+-----------------------
clusterable | f
index_scan | t
bitmap_scan | t
backward_scan | f
(4 rows)

这里与GiST的区别在于,SP-GiST不支持聚类。

最后,下面是列属性

1
2
3
4
5
6
select p.name,
pg_index_column_has_property('sites_url_idx'::regclass,1,p.name)
from unnest(array[
'asc','desc','nulls_first','nulls_last','orderable','distance_orderable',
'returnable','search_array','search_nulls'
]) p(name);
1
2
3
4
5
6
7
8
9
10
11
12
        name        | pg_index_column_has_property 
--------------------+------------------------------
asc | f
desc | f
nulls_first | f
nulls_last | f
orderable | f
distance_orderable | f
returnable | t
search_array | f
search_nulls | t
(9 rows)

不支持排序,这是可以预见的。到目前为止,SP-GiST中还没有用于搜索近邻的距离运算符。最有可能的是,这个功能将在未来得到支持。

SP-GiST可以用于纯索引扫描,至少对于所讨论的运算符类来说是这样。正如我们所看到的,在某些情况下,索引值被明确地存储在叶子节点中,而在其他情况下,这些值是在树的下降过程中逐部分重建的。

NULLs

为了不使情况复杂化,到目前为止我们还没有提到NULL。从索引属性中可以看出,NULL是被支持的

1
2
postgres=# explain (costs off)
select * from sites where url is null;
1
2
3
4
5
                  QUERY PLAN                  
----------------------------------------------
Index Only Scan using sites_url_idx on sites
Index Cond: (url IS NULL)
(2 rows)

然而,NULL对于SP-GiST来说是一个陌生的东西。所有来自 “spgist “操作符类的操作符都必须是严格的:只要操作符的任何参数是NULL,就必须返回NULL。方法本身确保了这一点。NULL不会被传递给操作符。

但是,为了使用只扫描索引的访问方法,NULL必须被存储在索引中。它们被存储在在一个单独的有自己根的树中。

其它数据类型

除了点和为了字符串使用的弧度树以外,还有一些其它的基实现了SP-GiST的访问方法。

  • “box_ops “运算符类为矩形提供了一个四象限树。每个矩形用四维空间中的一个点来表示,因此象限的数量是16。如果存在很多相交的矩形,SP-GiST索引就会比GiST有更高的性能:在GiST中,没有这样的边界能够将彼此相交的分离开来,而点(即使是四维的)则没有这样的问题。
  • “range_ops “运算符类为区间(intervals)提供了一个四叉树。一个区间由一个二维的点来表示:下边界成为横轴,上边界成为纵轴。