模糊查询，是一个需求量很大，同时也是一个对数据库来说非常难缠的需求。 对于前模糊(like '%xxx')，可以使用倒排B-TREE索引解决，对于后模糊(like 'xxx%')，可以使用B-TREE索引解决。B-TREE索引通常支持的查询包括 > , < , = , <= , >= 以及排序。 目前大多数数据库都支持B-TREE索引方法。但是对于前后模糊(like '%xxxx%')，对于以及前后模糊的正则表达式(~ '.ab?cd[e-f]{1,10}-0.')，则很多数据库无从下手，无法优化，只能全表扫描，对每条记录进行单独的处理。

PostgreSQL数据库的开放性使得这一切成为了可能，在数据库中进行前后模糊，正则表达查询的索引检索成为可能。 原因是PostgreSQL开放的索引接口，数据类型。（比如支持GIN, GIST, RUM, 自定义索引方法，你可以认为这是PG的独门绝技之一，目前还没有其他数据库支持这一特性）。

其实我在之前介绍过很多模糊查询的索引优化方法，很多第一次接触的同学会认为打开了新世界的大门。

《PostgreSQL 9.3 pg_trgm imporve support multi-bytes char and gist,gin index for reg-exp search》

《中文模糊查询性能优化 by PostgreSQL trgm》

《PostgreSQL 全文检索加速 快到没有朋友 - RUM索引接口(潘多拉魔盒)》

《聊一聊双十一背后的技术 - 毫秒分词算啥, 试试正则和相似度》

PostgreSQL internal

PostgreSQL index internal

目前有三种索引可以参与模糊查询的优化，到底用哪个好呢？ 本文将给大家分享一下 gin,gist,rum 索引背后的原理，大伙就知道该如何选择了，看好就该迎接2017新年啦，提前祝大家新年快乐，明年步步高升。

gin索引，是将列(比如数组，全文检索类型)中的值拿出来，再存储到树形结构中（类似B+TREE，值+行号s），对于高频值，为了减少树的深度，行号s会存储在另外的页中。

GIN fashupdate

由于GIN存储的是元素索引，所以当一条记录被插入或更新时，可能涉及到很多个元素，对GIN索引来说，就会涉及到很多ITEM的变更。

为了提升插入，更新，删除的性能，PostgreSQL支持类似MySQL的索引组织表类似的buffer ，先写入BUFFER，然后再合并到树里去。

而相比MySQL索引组织表更优一些的地方是，查询不会堵塞合并，也不会堵塞写入。因为查询时不需要等待BUFFER中的数据合并到树中，而是直接查询BUFFER（如果BUFFER非常大，可能查询速度会受到一定的影响）。 、

用户可通过参数来控制BUFFER的大小，GIN会在BUFFER增长到一定程度后自动进行合并。或者等VACUUM来合并。

所以一个完整的GIN索引长这样

GIN使用注意

为了提高更新速度，使用了FASTER UPDATE技术，当BUFFER很大时（可自己设置），查询速度可能会较慢。所以权衡插入和查询，建议设置合理的BUFFER大小。

仅支持bitmap查询，也就是说取到所有的行号之后，排序，然后再去检索，好处显然是可以减少随机的HEAP PAGE扫描，但是坏处是，当涉及的行非常多（比如每行都包含了某个元素）很大时，排序耗费资源较多，耗时较长，从执行到获得第一条的时间较长，如果用户使用了LIMIT，也要等排序结束。

GIN应用举例

《恭迎万亿级营销(圈人)潇洒的迈入毫秒时代 - 万亿user_tags级实时推荐系统数据库设计》

《从相似度算法谈起 - Effective similarity search in PostgreSQL》

Generalized Search Tree，或者叫归纳树，用于解决一些b-tree, gin难以解决的数据减少问题，例如，范围是否相交，是否包含，地理位置中的点面相交，或者按点搜索附近的点，当然，它能实现的功能还不仅于此。

以范围类型为例，下图每一条线段表示某条记录，某个字段上面存储的范围类型所覆盖的范围。

找到存储的范围有相交的记录s

按范围的最小值（左值）排序（请忽略红色框框的存在）

按范围的最大值（右值）排序（请忽略红色框框的存在）

GiST 的组织形式

首先把它们聚集到不同的分组（有点类似K-Means干的事情）（请忽略红色框框的存在）

聚集之后的数据，你可以理解为就是对应GiST的单个index page里包含的信息（可以多级聚集，即对应后面的2级结构）。

GiST单个index page长这样：

key + 行号 (索引和记录一一对应)

在index内无序存放。

蓝色框框中，左边列的值代表KEY，右边列的值代表行号（第几个HEAP PAGE，里面的第几条记录）。

GiST两级索引长这样，上一级代表下一级中单个INDEX PAGE的大范围。

例如搜索[55,60]这个范围，如何搜索的呢？

GiST 小结

GiST的灵魂是聚集，所以首先是聚集的动作，聚集后，在单个组内包含的KEY+HEAP行号会放到单个INDEX PAGE中。

聚集的范围作为一级结构，存储在GiST的entry 中，便于检索。

既然灵魂是聚集，那么GiST的性能就和他的聚集算法息息相关，PostgreSQL把这个接口留给了用户，用户在自定义数据类型时，如果要自己实现对应的GIST索引，那么就好好考虑这个类型聚集怎么做吧。

PostgreSQL内置的range, geometry等类型的GIST已经帮你做好了，你只需要做新增的类型，比如你新增了一个存储人体结构的类型，存储图片的类型，或者存储X光片的类型，怎么快速检索它们，那就是你要实现的GIST索引聚集部分了。

RUM 参考了GIN的实现，并改进了GIN在全文检索时的一些弱点，比如：

1. Slow ranking. (GIN没有存储全文检索的lexem位置信息，所以无法支持索引级的ranking，需要扫描HEAP PAGE后，通过CPU运算得到)

It is need position information about lexems to ranking. GIN index doesn't store positions of lexems. So after index scan we need additional heap scan to retreive lexems positions.

2. Slow phrase search with GIN index. (同样由于GIN没有存储位置信息，所以无法支持索引级的phrase搜索，例如 '速度' <1> '激情' 不能支持，或者 '中国:100' 无法支持到索引级别的搜索. )

This problem relates with previous problem. It is need position information to perform phrase search.

3. Slow ordering by timestamp. (因为GIN只存储了tsvector TOKEN，没有任何附带字段信息（例如全文检索+索引字段 双字段索引），所以一些炫酷或者业务扩展的功能，都需要heap page的扫描和CPU的处理)

GIN index can't store some related information in index with lexemes. So it is necessary to perform additional heap scan.

RUM的改进方法，在INDEX 中加入了附加信息，比如TOKEN位置，从而可以支持以上查询。 同时支持双字段索引（如 tsvector+timestamp）

RUM solves this problems by storing additional information in posting tree.

For example, positional information of lexemes or timestamps.

You can get an idea of RUM by the following picture:

RUM带来的问题，建立索引以及数据变更的时间，比GIN长，这个已经在RUM的TODO 中，会是后面的改进重点。

Drawback of RUM is that it has slower build and insert time than GIN.

It is because we need to store additional information besides keys and because RUM uses generic WAL.

RUM场景举例

《聊一聊双十一背后的技术 - 毫秒分词算啥, 试试正则和相似度》

《聊一聊双十一背后的技术 - 分词和搜索》

PostgreSQL目前支持哪些索引方法

B-Tree

SP-GiST

《"物联网"流式处理应用 - 用PostgreSQL实时处理(万亿每天)》

PostgreSQL 如何潇洒的处理每天上百TB的数据增量

《PostgreSQL 9.5 new feature - BRIN (block range index) index》

《PostgreSQL 9.5 new feature - lets BRIN be used with R-Tree-like indexing strategies For "inclusion" opclasses》

《PostgreSQL 全文检索加速 快到没有朋友 - RUM索引接口(潘多拉魔盒)》

BLOOM

《PostgreSQL 9.6 黑科技 bloom 算法索引，一个索引支撑任意列组合查询》

还有开放的接口，你可以自定义你的索引方法，请参考bloom索引的实现。

回到模糊查询的需求

介绍完PostgreSQL支持的索引方法，目前对于前模糊和后模糊，我们同样可以使用B-Tree来搜索。

而对于前后模糊，以及正则表达式，我们也有了索引的支持

前后模糊：

gin, gist, rum

正则表达：

gin, gist

有例子如下

《聊一聊双十一背后的技术 - 毫秒分词算啥, 试试正则和相似度》

接下来对比一下gin, gist, rum在不同输入条件下的性能，以及我们如何选择

为了达到测试效果，我们需要在一个列上创建多个索引，需要使用pg_hint_plan选择合适的索引。

一列可以建多个索引

PostgreSQL允许你在一个列上面创建多个索引，比如我们接下来的测试，我们需要使用gin, gist, rum来创建不同的索引。

自由选择索引, pg_hint_plan

《阿里云 PostgreSQL pg_hint_plan插件的用法》

《关键时刻HINT出彩 - PG优化器的参数优化、执行计划固化CASE》

《PostgreSQL SQL HINT的使用》

《PostgreSQL 特性分析 Plan Hint》

将字符串转化为全文检索的lexeme

为了达到测试rum支持模糊查询的目的，我们需要将字符串转换为全文检索类型，同时检索是需要输入tsquery，所以也需要转换为tsquery类型。

找到转义字符的ascii值

将字符串转换为带位置标记的tsvector

将字符串转换为带位置标记的tsquery

安装插件啥的就不写了，需要三个插件pg_trgm, pg_hint_plan, rum

info字段的字符串就是我们接下来要进行模糊测试的字段

写入100万测试数据

创建gin索引

创建gist索引

创建rum函数索引

转换后的tsvector长什么样？

一、test case1

中间结果集很大（匹配精度低，满足条件的记录数多），返回结果也很大，未使用LIMIT

1. gin

完整执行计划，注意评估行数，评估成本，后期可作为我们可用于评估哪个索引方法好的判断标准。

2. gist

完整执行计划，注意评估行数，评估成本，后期可作为我们可用于评估哪个索引方法好的判断标准。

3. rum

完整执行计划，注意评估行数，评估成本，后期可作为我们可用于评估哪个索引方法好的判断标准。

二、test case2

中间结果集很大（匹配精度低，满足条件的记录数多），返回结果很少，使用LIMIT。 如果这个好，那么使用分页也很有效。

1. gin

完整执行计划，注意评估行数，评估成本，后期可作为我们可用于评估哪个索引方法好的判断标准。

2. gist

完整执行计划，注意评估行数，评估成本，后期可作为我们可用于评估哪个索引方法好的判断标准。

3. rum

完整执行计划，注意评估行数，评估成本，后期可作为我们可用于评估哪个索引方法好的判断标准。

三、test case3

中间结果集很小（匹配精度高）

1. gin

完整执行计划，注意评估行数，评估成本，后期可作为我们可用于评估哪个索引方法好的判断标准。

2. gist

完整执行计划，注意评估行数，评估成本，后期可作为我们可用于评估哪个索引方法好的判断标准。

3. rum

完整执行计划，注意评估行数，评估成本，后期可作为我们可用于评估哪个索引方法好的判断标准。

如何评估选哪个索引方法

当中间结果集较少（输入条件的精确度高）时，建议使用GIN索引。 当中间结果集较大（输入条件的精确度低）时，不管是不是分页输出，或者是否使用LIMIT，或者是否使用游标，都建议使用GIST索引。 什么时候使用RUM呢？当真的需要全文检索时，或者需要tsvector+timestamp复合查询时，建议使用RUM。

设置统计粒度

找到对应的NODE，并评估中间结果数

查看对应节点的rows, 如果没有LIMIT， 则选择顶级NODE的ROWS，如果是LIMIT，则选择第二个NODE的ROWS。

如果是更复杂的查询，比如使用了多个条件查询时，则最好使用hint, 通过hint对应的索引，找到对应的node. 如：

跟进中间结果数，以及前面我给点建议，选择合适的HINT，开始执行QUERY。

-END-

ID： yunqiinsight

云计算丨互联网架构丨大数据丨机器学习 丨运维 返回搜狐，查看更多

责任编辑：

声明：该文观点仅代表作者本人，搜狐号系信息发布平台，搜狐仅提供信息存储空间服务。