PostgreSQL gist, spgist索引的原理、差别、应用场景

digoal 2019-06-04

1328

作者

digoal

日期

2019-06-04

背景

gist和spgist索引是PG的两个扩展索引接口。这两种索引都是来自大学，介绍一下这两种索引的结构，应用。

Emerging database applications require the use of new indexing structures beyond B-trees and R-trees. Examples are the k-d tree, the trie, the quadtree, and their variants. They are often proposed as supporting structures in data mining, GIS, CAD/CAM and biological database applications. A common feature of all these indexes is that they recursively divide the space into partitions.

《PostgreSQL 黑科技 - 空间聚集存储, 内窥GIN, GiST, SP-GiST索引》

Generalized Search Tree

1、gist的内部结构与特点

```
树结构，深度一致。Tree-structure

索引PAGE内的数据不按KEY的顺序排序。No order within pages

不同的索引PAGE的内容可能存在交叉，例如RANGE类型，值交叉。Key ranges of pages can overlap

由于第三条，所以搜索一条TUPLE时，可能会找到多个满足条件的PAGE。No single “correct” location for a particular tuple
```

2、single gist page的结构

```
Stores key + TID

One index tuple per heap tuple

Unordered
```

3、一个GIST索引页的内容例子（range类型的gist索引为例）

```
keyvalue -> ctid

[100,150] (1, 10)
[1, 200] (0, 2)
[10, 60] (4, 2)
[30, 50] (4, 3)
[20, 70] (5, 1)
[110, 120] (2, 2)
[15, 30] (2, 1)
[105, 115] (3, 4)
[80, 90] (9, 2)
[25, 45] (8, 1)
[10, 20] (1, 7)
```

4、两级结构的例子

（每个PAGE内的KEY无序，PAGE与PAGE自建可能存在OVERLAP）

5、包含查询，满足条件的可能是多个PAGE，也可能是一个PAGE

6、GiST的特征与性能

6.1、TUPLE在GIST INDEX 的同一个PAGE内部没有顺序。Loose ordering

6.2、任何KEY可以存储在任意PAGE中。但是好的组织形式可能会对某些查询（OPERATOR）有比较好的查询效率，所以GIST是真正的面向应用特征可定制化的。Any key can legitimately be stored anywhere in the tree

As long as the keys in the upper levels are updated accordingly.

Performance goes out the window if you do that.

6.3、性能取决于定义GIST索引时写的Picksplit and Choose functions这两个接口函数。 Performance depends on how well the userdefined Picksplit and Choose functions can group keys

7、What can you do with GiST?

7.1、GIS stuff

7.2、Find points within a bounding box

7.3、Nearest Neighbor

8、GiST, not only for geometries

gist索引不仅能用在GIS数据中，还可以支持其他的数据类型。

Contrib/intarray

Full-text search

Upper node “contains” everything below it

For points, a bounding box of all points below it

For intarray, the OR of all the nodes below it

Space-Partitioned GiST

上图以字符串spgist索引为例, branch节点（inner节点）包含prefix, leaf node包含的是postfix的内容。

amsterdam ankara belgrade berlin bern bucharest budapest helsinki

1、sp-gist特征

nodes之间不存在数据的交叉。这一点与GIST不一样。No overlap between nodes

一个物理PAGE中可能存储多个NODE。Multiple nodes per physical page

与GIST结构非常不同。Quite different from GiST

层级可能是可变的，例如有些leaf处于第四层，有些leaf处于第二层。Variable depth

sp-gist索引的内部构造请参考

http://www.sai.msu.su/~megera/wiki/spgist_dev

src/backend/access/spgist/README

查询当前实例中gist与spgist索引支持的opclass与操作符

SELECT am.amname AS index_method, opf.opfname AS opfamily_name, opc.opcname AS opclass_name, amop.amopopr::regoperator AS opfamily_operator FROM pg_am am, pg_opfamily opf, pg_opclass opc, pg_amop amop WHERE opf.opfmethod = am.oid AND amop.amopfamily = opf.oid AND opc.opcmethod = am.oid AND opc.opcfamily = opf.oid ORDER BY index_method, opfamily_name, opfamily_operator;

参考

https://www.pgcon.org/2016/schedule/attachments/434_Index-internals-PGCon2016.pdf

《PostgreSQL 如何确定某个opclass支持哪些操作符(支持索引)，JOIN方法，排序 - 了解opclass,am,opfamily,amop》

https://www.postgresql.org/docs/12/gist.html

https://www.postgresql.org/docs/12/spgist.html

https://www.cs.purdue.edu/spgist/