利用pg_trgm的gist和gin索引加速字符匹配查询

pg_trgm是用来做相似度匹配的，在一些情况下也可以拿来代替全文检索做字符匹配。
从大量数据中通过字符串的匹配查找数据的关键是索引，对字符串的精确相等匹配，前缀匹配(like 'x%')和后缀匹配(like '%x')可以使用btree索引,对中缀匹配(like '%x%')和正则表达式匹配就可以用pg_trgm的索引了。下面用一个例子说明一下。

1.环境

CentOS 6.5
PostgreSQL 9.4.0

2.测试数据

没有特意找什么测试数据，正好手头有一份翻译中的PostgreSQL9.3中文手册，就拿它当测试数据了。

建表

create table t1(id serial,c1 text);

导数据，手册中的每一行作为一条记录。

-bash-4.1$ tar xf pg9.3.1.html.tar.gz
-bash-4.1$ find html -name *.html -exec cat {} \;|iconv -f GBK -t UTF8|sed 's\[\]\\g'|psql -p 5433 testdb -c "copy t1(c1) from stdin"

注）翻译中的PostgreSQL9.3中文手册(pg9.3.1.html.tar.gz)可从以下位置下载：

查看数据大小

testdb=# select count(*) from t1;
 count
--------
 702476
(1 row)
testdb=# select pg_table_size('t1');
 pg_table_size
---------------
      37519360
(1 row)
testdb=# select * from t1 where c1 like '%存储过程%';
   id | c1
--------+------------------------------------------------------------------------------------------------------------------------
 132113 | >有些其它数据库系统定义动态的数据库规则。这些通常是存储过程和触发器，
 132119 | >规则系统(更准确地说是查询重写规则系统)是和存储过程和触发器完全不同的东西。
 260249 | >如果你的需求超过这些条件表达式的能力，你可能会希望用一种更富表现力的编程语言写一个存储过程。</P
 473911 | >下面是一个用 C 写的存储过程语言处理器的模版：
 562282 | >请注意开销估计函数必须用 C 写，而不能用 SQL 或者任何可用的存储过程语言，因为它们必须访问规划器/优化器的内部数据结构。
 566142 | >登记编程语言，你可以用这些语言或接口写函数或者存储过程。
(6 rows)

3.模糊匹配测试

3.1 通过全表扫描做模糊匹配

testdb=# explain (analyze,buffers) select * from t1 where c1 like '%存储过程%';
                                             QUERY PLAN
-----------------------------------------------------------------------------------------------------
 Seq Scan on t1 (cost=0.00..13354.95 rows=30 width=21) (actual time=34.920..186.967 rows=6 loops=1)
   Filter: (c1 ~~ '%存储过程%'::text)
   Rows Removed by Filter: 702470
   Buffers: shared hit=4574
 Planning time: 0.121 ms
 Execution time: 187.003 ms
(6 rows)

Time: 187.635 ms

3.2 使用pg_trgm的gist索引扫描做模糊匹配

testdb=# create extension pg_trgm;
CREATE EXTENSION
testdb=# create index t1_c1_gist_idx on t1 using gist(c1 gist_trgm_ops);
LOG: checkpoints are occurring too frequently (22 seconds apart)
HINT: Consider increasing the configuration parameter "checkpoint_segments".
LOG: checkpoints are occurring too frequently (5 seconds apart)
HINT: Consider increasing the configuration parameter "checkpoint_segments".
CREATE INDEX
Time: 15988.394 ms

testdb=# select pg_relation_size('t1_c1_gist_idx');
 pg_relation_size
------------------
         55214080
(1 row)

Time: 0.461 ms

testdb=# explain (analyze,buffers) select * from t1 where c1 like '%存储过程%';
                                                        QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on t1 (cost=4.52..117.60 rows=30 width=21) (actual time=71.292..71.303 rows=6 loops=1)
   Recheck Cond: (c1 ~~ '%存储过程%'::text)
   Heap Blocks: exact=5
   Buffers: shared hit=5249
   -> Bitmap Index Scan on t1_c1_gist_idx (cost=0.00..4.51 rows=30 width=0) (actual time=71.268..71.268 rows=6 loops=1)
         Index Cond: (c1 ~~ '%存储过程%'::text)
         Buffers: shared hit=5244
 Planning time: 0.146 ms
 Execution time: 71.344 ms
(9 rows)

Time: 71.976 ms

性能提升了1倍多(187.635/71.976)，可以说效果并不明显，尤其需要注意的是索引太大，而且扫描的索引数据块太多(5244)，几乎把整个索引都扫了一遍。而匹配的记录其实只有6条。下面看看gin索引的效果。

3.3 使用pg_trgm的gin索引扫描做模糊匹配

testdb=# drop index t1_c1_gist_idx;
DROP INDEX
Time: 22.827 ms
testdb=# create index t1_c1_gin_idx on t1 using gin(c1 gin_trgm_ops);
CREATE INDEX
Time: 4995.957 ms
testdb=# select pg_relation_size('t1_c1_gin_idx');
 pg_relation_size
------------------
         29663232
(1 row)

Time: 0.670 ms

testdb=# explain (analyze,buffers) select * from t1 where c1 like '%存储过程%';
                                                       QUERY PLAN
------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on t1 (cost=28.23..141.32 rows=30 width=21) (actual time=0.115..0.135 rows=6 loops=1)
   Recheck Cond: (c1 ~~ '%存储过程%'::text)
   Heap Blocks: exact=5
   Buffers: shared hit=12
   -> Bitmap Index Scan on t1_c1_gin_idx (cost=0.00..28.22 rows=30 width=0) (actual time=0.093..0.093 rows=6 loops=1)
         Index Cond: (c1 ~~ '%存储过程%'::text)
         Buffers: shared hit=7
 Planning time: 1.348 ms
 Execution time: 0.265 ms
(9 rows)

Time: 2.721 ms

gin_trgm索引的效果好多了。性能提升了69倍(187.635/2.721)。
很妙的是除了like,gin_trgm索引还可以用在正则表达式匹配上。比如，查出所有不是出现在句子结尾的“存储过程”。

testdb=# select * from t1 where c1 ~ '存储过程[^。]';
   id | c1
--------+------------------------------------------------------------------------------------------------------------------------
 132113 | >有些其它数据库系统定义动态的数据库规则。这些通常是存储过程和触发器，
 132119 | >规则系统(更准确地说是查询重写规则系统)是和存储过程和触发器完全不同的东西。
 473911 | >下面是一个用 C 写的存储过程语言处理器的模版：
 562282 | >请注意开销估计函数必须用 C 写，而不能用 SQL 或者任何可用的存储过程语言，因为它们必须访问规划器/优化器的内部数据结构。
(4 rows)

Time: 0.978 ms
testdb=# explain (analyze,buffers) select * from t1 where c1 ~ '存储过程[^。]';
                                                       QUERY PLAN
------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on t1 (cost=28.23..141.32 rows=30 width=21) (actual time=0.141..0.172 rows=4 loops=1)
   Recheck Cond: (c1 ~ '存储过程[^。]'::text)
   Rows Removed by Index Recheck: 2
   Heap Blocks: exact=5
   Buffers: shared hit=12
   -> Bitmap Index Scan on t1_c1_gin_idx (cost=0.00..28.22 rows=30 width=0) (actual time=0.120..0.120 rows=6 loops=1)
         Index Cond: (c1 ~ '存储过程[^。]'::text)
         Buffers: shared hit=7
 Planning time: 0.441 ms
 Execution time: 0.281 ms
(10 rows)

Time: 1.261 ms

3.4 对比一下使用zhparser插件的全文检索的效果

zhparser的使用方法参考前一篇博客《PostgreSQL的全文检索插件zhparser的中文分词效果》。
libscws的分词模式设成短词+重要单字的复合分词。

testdb=# create index t1_c1_fts_idx on t1 using gin(to_tsvector('testzhcfg',c1));
CREATE INDEX
Time: 4523.277 ms
testdb=# select pg_relation_size('t1_c1_fts_idx');
 pg_relation_size
------------------
          8765440
(1 row)

Time: 0.543 ms

testdb=# explain (analyze,buffers) select * from t1 where to_tsvector('testzhcfg',c1) @@ to_tsquery('testzhcfg','存储过程');
                                                             QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on t1 (cost=76.00..80.02 rows=1 width=21) (actual time=0.437..0.465 rows=13 loops=1)
   Recheck Cond: (to_tsvector('testzhcfg'::regconfig, c1) @@ '''存储'' & ''存'' & ''储'' & ''过程'' & ''过'' & ''程'''::tsquery)
   Heap Blocks: exact=12
   Buffers: shared hit=35
   -> Bitmap Index Scan on t1_c1_fts_idx (cost=0.00..76.00 rows=1 width=0) (actual time=0.424..0.424 rows=13 loops=1)
         Index Cond: (to_tsvector('testzhcfg'::regconfig, c1) @@ '''存储'' & ''存'' & ''储'' & ''过程'' & ''过'' & ''程'''::tsquery)
         Buffers: shared hit=23
 Planning time: 0.192 ms
 Execution time: 0.506 ms
(9 rows)

Time: 1.486 ms

全文检索果然索引更小，搜索更快(在我的测试条件下，性能其实相差不大，而且每次测试结果都不一样；随着数据量的增大中文分词会更有性能优势)。但是pg_trgm贵在不需要涉及中文分词的那么多不确定性。比如上面的例子，用全文检索搜出来的就是13条记录，而不是6条。因为用于分词的词典里没有“存储过程”这个词，“存储过程”被拆成了“存储”和“过程”两个词，只要记录里有这两个词，不管是否连在一起，都被认为匹配。如下:

testdb=# select * from t1 where to_tsvector('testzhcfg',c1) @@ to_tsquery('testzhcfg','存储过程');
   id | c1
--------+------------------------------------------------------------------------------------------------------------------------
 120827 | 在描述这些变化的日志记录刷新到永久存储器之后。如果我们遵循这个过程，
 132113 | >有些其它数据库系统定义动态的数据库规则。这些通常是存储过程和触发器，
 132119 | >规则系统(更准确地说是查询重写规则系统)是和存储过程和触发器完全不同的东西。
 260249 | >如果你的需求超过这些条件表达式的能力，你可能会希望用一种更富表现力的编程语言写一个存储过程。</P
 263598 | >表存储关于函数(或过程)的信息。参阅<A
 320664 | 然后在使用过程中大概需要在一个平面文本文件里存放同等数据量五倍的空间存储数据。
 376663 | 实现节点将数据保存在存储器中，因为它被读取，然后从存储器每个后续过程中返回每一个数据。</P
 436633 | >存储有关与访问方法操作符族相关联的支持过程的信息。
 455406 | >表为过程语言存储<SPAN
 473911 | >下面是一个用 C 写的存储过程语言处理器的模版：
 552426 | 我们加速了存储器分配，优化，表联合以及行传输过程。</P
 562282 | >请注意开销估计函数必须用 C 写，而不能用 SQL 或者任何可用的存储过程语言，因为它们必须访问规划器/优化器的内部数据结构。
 566142 | >登记编程语言，你可以用这些语言或接口写函数或者存储过程。
(13 rows)

pg_trgm本质上虽然也相当于一种特殊的分词方法，但是pg_trgm索引只有用来做初次筛选，最终结果还有recheck来把关，所以结果是确定的。

4 pg_trgm做索引的注意事项

4.1 不支持小于3个字的匹配条件

pg_trgm的工作原理是把字符串切成N个3元组，然后对这些3元组做匹配，所以如果作为查询条件的字符串小于3个字符它就罢工了。
对pg_trgm的gist索引，走的还是索引扫描。但是悲剧的是，索引没有起到任何筛选的作用，702476条记录一个不落全给提出来了，这样还不如直接全表扫描呢。

testdb=# explain analyze select * from t1 where c1 like '%存储%';
                                                         QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on t1 (cost=4.52..117.60 rows=30 width=21) (actual time=106.022..221.730 rows=640 loops=1)
   Recheck Cond: (c1 ~~ '%存储%'::text)
   Rows Removed by Index Recheck: 701836
   Heap Blocks: exact=4574
   -> Bitmap Index Scan on t1_c1_gist_idx (cost=0.00..4.51 rows=30 width=0) (actual time=105.184..105.184 rows=702476 loops=1)
         Index Cond: (c1 ~~ '%存储%'::text)
 Planning time: 0.102 ms
 Execution time: 221.855 ms
(8 rows)

Time: 222.311 ms

对pg_trgm的gin索引，优化器看出来这时候走索引是白费功夫，所以就直接走的全表扫描。

testdb=# explain analyze select * from t1 where c1 like '%存储%';
                                                         QUERY PLAN
------------------------------------------------------------------------------------------------------
 Seq Scan on t1 (cost=0.00..13354.95 rows=30 width=21) (actual time=0.541..207.416 rows=640 loops=1)
   Filter: (c1 ~~ '%存储%'::text)
   Rows Removed by Filter: 701836
   Buffers: shared hit=4574
 Planning time: 0.183 ms
 Execution time: 207.608 ms
(6 rows)

Time: 208.288 ms

4.2 数据库的LC_CTYPE需要设置为中文区域

在你的环境下，可能会发现pg_trgm不支持中文，中文字符都被截掉了。就像这样:

utf8_C=# select show_trgm('存储过程');
 show_trgm
-----------
 {}
(1 row)

正确的应该是这样：

testdb=# select show_trgm('存储过程');
                   show_trgm
------------------------------------------------
 {0x9acb56,0xa61c30,0xaad876,0xd07577,0x5e9b60}
(1 row)

这是因为，pg_trgm调用了系统的isalpha()函数判断字符，而isalpha()依赖于LC_CTYPE，如果数据库的LC_CTYPE是C，isalpha()就不能识别中文。所以需要把数据库的LC_CTYPE设成zh_CN。

trgm.h:

#define t_isdigit(x)    isdigit(TOUCHAR(x))
...
#define t_isalpha(x)    isalpha(TOUCHAR(x))
...
#define ISWORDCHR(c)    (t_isalpha(c) || t_isdigit(c))

trgm_opt.c:

/*
 * Finds first word in string, returns pointer to the word,
 * endword points to the character after word
 */
static char *
find_word(char *str, int lenstr, char **endword, int *charlen)
{
    char     *beginword = str;

    while (beginword - str < lenstr && !ISWORDCHR(beginword))
        beginword += pg_mblen(beginword);

    if (beginword - str >= lenstr)
        return NULL;

    *endword = beginword;
    *charlen = 0;
    while (*endword - str < lenstr && ISWORDCHR(*endword))
    {
        *endword += pg_mblen(*endword);
        (*charlen)++;
    }

    return beginword;
}

数据库的LC_CTYPE：

testdb=#  \l
                                 List of databases
   Name    |  Owner   | Encoding |  Collate   |   Ctype    |   Access privileges   
-----------+----------+----------+------------+------------+-----------------------
 postgres  | postgres | UTF8     | zh_CN.utf8 | zh_CN.utf8 | 
 template0 | postgres | UTF8     | zh_CN.utf8 | zh_CN.utf8 | =c/postgres          +
           |          |          |            |            | postgres=CTc/postgres
 template1 | postgres | UTF8     | zh_CN.utf8 | zh_CN.utf8 | postgres=CTc/postgres+
           |          |          |            |            | =c/postgres
 testdb    | postgres | UTF8     | zh_CN.utf8 | zh_CN.utf8 | 
 utf8_C    | postgres | UTF8     | C          | C          | 
(5 rows)

5.参考

http://blog.2ndquadrant.com/text-search-strategies-in-postgresql/

http://my.oschina.net/Kenyon/blog/366505