PostgreSQL中的索引— 9（RUM）

开源软件联盟PostgreSQL分会 2020-02-03

1724

原作者：Egor Rogov

翻译：尚凯

审核：魏波

我们已经讨论了PostgreSQL 索引引擎，访问方法的接口以及主要访问方法，例如：哈希索引，B树，GiST，SP-GiST和GIN。在本文中，我们一起来看GIN如何变为RUM。

RUM

尽管作者称GIN具有强大的功能，但RUM在某些方面更胜一筹：下一代GIN被称为RUM。

这种访问方法扩展了GIN的基础概念，使我们能够更快地执行全文搜索。在本系列文章中，这是PostgreSQL标准交付中唯一未包含的方法，并且是外部扩展。有几个安装选项可供使用：

· 从PGDG存储库中获取«yum»或«apt»软件包。例如，如果从«postgresql-10»软件包安装了PostgreSQL，还要安装«postgresql-10-rum»。

· 从github上的源代码进行构建，然后自行安装（存在用法说明）。

· 用作Postgres Pro Enterprise的一部分，或至少可以从那里阅读相关文档，链接地址https://postgrespro.com/docs/enterprise/9.6/rum。

GIN的局限性

我们来看RUM能够超越GIN的哪些限制？

首先，“ tsvector”数据类型不仅包含词素，还包含它们在文档中位置的信息。正如我们上次观察到的，GIN索引不存储此信息。因此，GIN索引无法有效地支持9.6版中出现的短语搜索操作，并且必须访问原始数据进行重新检查。

其次，搜索系统通常返回按相关性排序的结果。为此，我们可以使用排名函数《 ts_rank》和《 ts_rank_cd》为结果的每一行来，但这肯定会很慢。

大致来说，RUM访问方法可以视为GIN，但它另外存储位置信息，并可以按所需顺序返回结果（例如GiST可以返回最近的邻居）。让我们一步一步地展开。

搜索词组

全文搜索查询可以包含特殊运算符，这些运算符考虑了词素之间的距离。例如，我们以词语 «hand»和 «thigh» （两词之间可以被两个或多个词隔开）搜索文档：

postgres=#select to_tsvector('Clap your hands, slap your thigh') @@
                 to_tsquery('hand <3> thigh'); 
                 ?column?
                 ---------- 
                 t
                 (1 row)

或者我们可以指出单词必须一个接一个地定位：

postgres=#select to_tsvector('Clap your hands, slap your thigh') @@
                 to_tsquery('hand <-> slap'); 
                 ?column?
                 ---------- 
                 t
                 (1 row)

常规GIN索引可以返回包含两个词素的文档，但我们只能通过查看tsvector来检查它们之间的距离：

postgres=#select to_tsvector('Clap your hands, slap your thigh');
                 to_tsvector             
                 -------------------------------------- 
                 'clap':1 'hand':3 'slap':4 'thigh':6
                 (1 row)

在RUM索引中，每个词素不仅引用表行：每个TID都提供了词素在文档中出现的位置列表。我们可以设想在«slit-sheet»表上创建索引的方法，该索引已经为我们所熟悉（默认情况下，运算符类«vector_ops»用于rum_tsvector）：

postgres=# createextension rum;
postgres=# create index on ts using rum(doc_tsv);

图中的灰色方块包含添加的位置信息：

postgres=#select ctid, left(doc,20), doc_tsv from ts;
ctid |         left         |                         doc_tsv
-------+----------------------+--------------------------------------------------------- 
(0,1) | Can a sheet slitter  | 'sheet':3,6 'slit':5 'slitter':4 
(0,2) | How many sheets coul | 'could':4 'mani':2 'sheet':3,6 'slit':8 'slitter':7 
(0,3) | I slit a sheet, a sh | 'sheet':4,6 'slit':2,8 
(1,1) | Upon a slitted sheet | 'sheet':4 'sit':6 'slit':3 'upon':1 
(1,2) | Whoever slit the she | 'good':7 'sheet':4,8 'slit':2 'slitter':9 'whoever':1 
(1,3) | I am a sheet slitter | 'sheet':4 'slitter':5 
(2,1) | I slit sheets.       | 'sheet':3 'slit':2 
(2,2) | I am the sleekest sh | 'ever':8 'sheet':5,10 'sleekest':4 'slit':9 'slitter':6
(2,3) | She slits the sheet  | 'sheet':4 'sit':6 'slit':2
(9 rows)

当指定了“ fastupdate”参数时，GIN还提供了延迟插入的功能。此功能已从RUM中删除。

要查看索引如何处理实时数据，让我们使用熟悉的pgsql-hackers邮件列表档案。

fts=#alter table mail_messagesadd column tsvtsvector; 
fts=#set default_text_search_config = default;
fts=#update mail_messagesset tsv = to_tsvector(body_plain);
...
UPDATE 356125

这是通过GIN索引执行使用短语搜索查询的方式：

fts=#createindex tsv_ginon mail_messagesusing gin(tsv); 
fts=#explain (costs off,analyze)select *from mail_messageswhere tsv @@ to_tsquery('hello <-> hackers');
                                   QUERY PLAN                                   
--------------------------------------------------------------------------------- 
Bitmap Heap Scan on mail_messages (actual time=2.490..18.088 rows=259 loops=1)   
Recheck Cond: (tsv @@ to_tsquery('hello <-> hackers'::text))   
Rows Removed by Index Recheck: 1517   
Heap Blocks: exact=1503
->  Bitmap Index Scan on tsv_gin (actual time=2.204..2.204 rows=1776 loops=1)  
Index Cond: (tsv @@ to_tsquery('hello <-> hackers'::text))
Planning time: 0.266 ms
Execution time: 18.151 ms
(8 rows)

从计划中可以看出，使用了GIN索引，但它返回了1776个潜在匹配项，在重新检查阶段保留了259个匹配项，删除了1517个匹配项。
检查阶段保留了259个匹配项，删除了1517个匹配项。

让我们删除GIN索引并构建RUM。

fts=#drop index tsv_gin;
fts=#create index tsv_rumon mail_messagesusing rum(tsv);

现在，索引包含所有必要的信息，并且搜索准确地执行：

fts=#explain (costs off,analyze)select *from mail_messageswhere tsv @@ to_tsquery('hello <-> hackers');
                                   QUERY PLAN                                 
--------------------------------------------------------------------------------
Bitmap Heap Scan on mail_messages (actual time=2.798..3.015 rows=259 loops=1)
Recheck Cond: (tsv @@ to_tsquery('hello <-> hackers'::text)) 
Heap Blocks: exact=250   ->  Bitmap Index Scan on tsv_rum (actual time=2.768..2.768 rows=259 loops=1)     
Index Cond: (tsv @@ to_tsquery('hello <-> hackers'::text))
Planning time: 0.245 ms
Execution time: 3.053 ms
(7 rows)

按相关性排序

为了方便地按所需顺序返回文档，RUM索引支持排序运算符，我们在GiST相关的文章中对此进行了讨论。RUM扩展定义了这样一个运算符，运算符<=>返回文档（«tsvector»）和查询（«tsquery»）之间的一段距离。例如：

fts=#select to_tsvector('Can a sheet slitter slit sheets?') <=&gtl to_tsquery('slit'); 
?column?
----------  
16.4493
(1 row)
fts=#select to_tsvector('Can a sheet slitter slit sheets?') <=> to_tsquery('sheet'); 
?column?
----------
13.1595
(1 row)

文档与第一个查询比与第二个查询更相关:单词出现的频率越高，它的«valuable»就越小。

让我们再次尝试在相对大的数据大小上比较GIN和RUM：我们将选择十个包含“hello”和“hackers”最相关的文档。

fts=#explain (costs off,analyze)select *from mail_messageswhere tsv @@ to_tsquery('hello & hackers')order by ts_rank(tsv,to_tsquery('hello & hackers'))limit 10;
                                         QUERY PLA
--------------------------------------------------------------------------------------------- 
Limit (actual time=27.076..27.078 rows=10 loops=1)   
->  Sort (actual time=27.075..27.076 rows=10 loops=1)         
Sort Key: (ts_rank(tsv, to_tsquery('hello & hackers'::text)))       
Sort Method: top-N heapsort  Memory: 29kB    
->  Bitmap Heap Scan on mail_messages (actual ... rows=1776 loops=1)               
Recheck Cond: (tsv @@ to_tsquery('hello & hackers'::text))             
Heap Blocks: exact=1503              
->  Bitmap Index Scan on tsv_gin (actual ... rows=1776 loops=1)                   
Index Cond: (tsv @@ to_tsquery('hello & hackers'::text))
Planning time: 0.276 ms
Execution time: 27.121 ms
(11 rows)

GIN索引返回1776个匹配项，然后将这些匹配项作为一个单独的步骤进行排序，以选出10个最佳结果。

对于RUM索引，查询是通过简单的索引扫描来执行的:不需要查看额外的文档，也不需要单独的排序:

fts=#explain (costs off,analyze)select *from mail_messageswhere tsv @@ to_tsquery('hello & hackers')order by tsv <=> to_tsquery('hello & hackers')limit 10;
                                         QUERY PLAN
--------------------------------------------------------------------------------------------
Limit (actual time=5.083..5.171 rows=10 loops=1)   
->  Index Scan using tsv_rum on mail_messages (actual ... rows=10 loops=1)        
Index Cond: (tsv @@ to_tsquery('hello & hackers'::text))         
Order By: (tsv <=> to_tsquery('hello & hackers'::text))
Planning time: 0.244 ms 
Execution time: 5.207 ms
(6 rows)

其它信息

RUM和GIN索引可以建立在几个字段上。但是，尽管GIN独立存储每一列中的词素，而RUM能使我们关联«associate»主字段«tsvector»的一个附加字段。为此，我们需要使用专门的运算符类«rum_tsvector_addon_ops»：

fts=#createindex on mail_messagesusing rum(tsv RUM_TSVECTOR_ADDON_OPS, sent)  
WITH (ATTACH='sent',TO='tsv');

我们可以使用此索引返回按附加字段排序的结果：

fts=#select id, sent, sent <=>'2017-01-01 15:00:00'from mail_messageswhere tsv @@ to_tsquery('hello')order by sent <=>'2017-01-01 15:00:00'limit 10;   
id    |        sent         | ?column?---------+---------------------+---------- 
2298548 | 2017-01-01 15:03:22 |      202 
2298547 | 2017-01-01 14:53:13 |      407 
2298545 | 2017-01-01 13:28:12 |     5508 
2298554 | 2017-01-01 18:30:45 |    12645 
2298530 | 2016-12-31 20:28:48 |    66672 
2298587 | 2017-01-02 12:39:26 |    77966 
2298588 | 2017-01-02 12:43:22 |    78202 
2298597 | 2017-01-02 13:48:02 |    82082 
2298606 | 2017-01-02 15:50:50 |    89450 
2298628 | 2017-01-02 18:55:49 |   100549
(10 rows)

在这里无论是早或晚，我们搜索尽可能接近指定日期的匹配行。要获得严格在指定日期之前(或之后)的结果，需要使用<=|(或|=>)操作符。

如我们所料，查询仅通过简单的索引扫描执行：

ts=#explain (costs off)select id, sent, sent <=> '2017-01-01 15:00:00' from mail_messageswhere tsv @@ to_tsquery('hello')order by sent <=>'2017-01-01 15:00:00'limit 10;
                                   QUERY PLAN
--------------------------------------------------------------------------------- 
Limit   
->  Index Scan using mail_messages_tsv_sent_idx on mail_messages         
Index Cond: (tsv @@ to_tsquery('hello'::text))         
Order By: (sent <=> '2017-01-01 15:00:00'::timestamp without time zone)
(4 rows)

如果创建索引时没有关于字段关联的其他信息，对于类似的查询，我们将必须对索引扫描的所有结果进行排序。

除了日期，我们也可以将其他数据类型的字段添加到RUM索引中。几乎所有基本类型都受支持。例如，在线商店可以按新颖性（日期），价格（数字），受欢迎程度或折扣值（整数或浮点数）快速显示商品。

其他操作符类别

为了使图片更完整，我们应该提到其他可用的运算符类。

让我们«rum_tsvector_hash_ops» 和«rum_tsvector_hash_addon_ops»开始。已经讨论过的《 rum_tsvector_ops》和《 rum_tsvector_addon_ops》，但是索引存储的是词素的哈希码，而不是词素本身。这可以减小索引的大小，但是搜索的准确性当然会降低，需要重新检查。此外，索引不再支持部分匹配的搜索。

看看《 rum_tsquery_ops》是很有趣的操作符类别。它使我们能够解决«inverse» 逆向问题：查找与文档匹配的查询。为什么需要这个？来看一个例子，根据用户的过滤器为用户订阅新商品或自动对新文档进行分类。看这个简单的例子：

fts=#createtable categories(query tsquery, categorytext); 
fts=#insert into categoriesvalues  
(to_tsquery('vacuum | autovacuum | freeze'),'vacuum'),  
(to_tsquery('xmin | xmax | snapshot | isolation'),'mvcc'),  
(to_tsquery('wal | (write & ahead & log) | durability'),'wal'); 
fts=#create index on categoriesusing rum(query); 
fts=#select array_agg(category)from categorieswhere to_tsvector(  
'Hello hackers, the attached patch greatly improves performance of tuple   
freezing and also reduces size of generated write-ahead logs.') @@ query;  
array_agg 
-------------- 
{vacuum,wal}
(1 row)

其余的操作符类“rum_anyarray_ops”和“rum_anyarray_addon_ops”被设计成比“tsvector”更能处理数组类型。

上次已经针对GIN进行了讨论，在此不做重复。

索引和预写日志（WAL）的大小

显然，由于RUM比GIN存储更多的信息，因此它具有更大的大小。我们上次比较了不同索引的大小；让我们将RUM添加到此表中：

rum	gin	gist	btree
457MB	179MB	125MB	546MB

如我们所见，大小明显增加，这就是快速搜索的成本。

值得一提的是：RUM是扩展，也就是说，可以在不对系统核心进行任何修改的情况下安装RUM。感谢Alexander Korotkov的补丁，此功能已在9.6版中启用。为此必须解决的问题之一是日志记录的生成。用于记录日志的技术必须绝对可靠，因此，不能在此引入扩展。执行以下操作代替了允许扩展程序创建自己的日志记录类型：扩展程序的代码传达了其修改页面的意图，对其进行任何更改并发出完成的信号，由系统核心比较页面的旧版本和新版本，并生成所需的统一日志记录。

当前的日志生成算法是逐字节比较页面，检测更新的片段，并记录每个片段及页面开始的偏移量。仅更新几个字节或整个页面时，此方法工作正常。但是，如果我们在页面内添加一个片段，将其余内容向下移动（反之亦然，删除一个片段，向上移动内容），则更改的字节数将比实际添加或删除的字节多得多。

因此，大量更改RUM索引可能会生成比GIN大得多的日志记录（GIN不是扩展，而是核心的一部分，它自己管理日志）。这种不良影响在很大程度上取决于实际的工作量，为了深入了解该问题，让我们尝试多次删除并添加许多行，并将这些操作与“vaccum”操作关联在一起。我们可以按以下方式评估日志记录的大小：在开始和结束时，使用函数«pg_current_wal_location»（在V10以前的版本中为«pg_current_xlog_location»）记住日志中的位置，然后查看它们之间的区别。

但是，我们当然应该在这里考虑很多方面。需要确保只有一个用户正在使用该系统（否则，将考虑«extra»额外记录）。即使这样，我们不仅要考虑RUM，还要考虑表本身以及支持主键索引的更新。配置参数的值也会影响大小（此处使用的是«replica»日志级别，未压缩）。接下来让我们验证一下。

fts=#select pg_current_wal_location()as start_lsn \gset
 fts=#insert into mail_messages(parent_id, sent, subject, author, body_plain, tsv)  select parent_id, sent, subject, author, body_plain, tsv  from mail_messageswhere id %100 =0;INSERT 0 3576
 fts=#delete from mail_messageswhere id %100 =99;DELETE 3590
 fts=#vacuum mail_messages;
 fts=#insert into mail_messages(parent_id, sent, subject, author, body_plain, tsv)  select parent_id, sent, subject, author, body_plain, tsv  from mail_messageswhere id %100 =1;INSERT 0 3605
 fts=#delete from mail_messageswhere id %100 =98;DELETE 3637
 fts=#vacuum mail_messages;
 fts=#insert into mail_messages(parent_id, sent, subject, author, body_plain, tsv)  select parent_id, sent, subject, author, body_plain, tsv from mail_messages  where id %100 =2;INSERT 0 3625
 fts=#delete from mail_messageswhere id %100 =97;DELETE 3668
 fts=#vacuum mail_messages;
 fts=#select pg_current_wal_location() as end_lsn \gsetfts=#select pg_size_pretty(:'end_lsn'::pg_lsn - :'start_lsn'::pg_lsn); pg_size_pretty---------------- 3114 MB
 (1 row)

因此，我们得到了大约3 GB事务日志。但是，如果我们对GIN索引重复进行相同的实验，只会占用700 MB左右的空间。

因此，希望有一种不同的算法，该算法可以将页面的一种状态转换为另一种状态的最小数量的插入和删除操作。«diff»实用程序的工作方式与此类似。Oleg Ivanov已经实现了这样的算法，并且他的补丁正在讨论中。在上面的示例中，此补丁使我们能够将日志记录的大小减少1.5倍，至1900 MB，但代价是速度有所降低。

不幸的是，补丁已暂停，并目前还没有与之相关的活动。

属性

像往常一样，让我们看一下RUM访问方法的属性，注意与GIN的区别。

以下是访问方法的属性：

 amname |     name      | pg_indexam_has_property
--------+---------------+------------------------- 
 rum    | can_order     | f 
 rum    | can_unique    | f 
 rum    | can_multi_col | t 
 rum    | can_exclude   | t -- f for gin

以下索引层属性是可用的：

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

请注意，与GIN不同，RUM支持索引扫描。否则，不可能在带有«limit»子句的查询中精确返回所需数目的结果。不需要使用相应地参数«gin_fuzzy_search_limit»。因此，该索引可用于支持排除约束。

以下是列层属性：

        name        | pg_index_column_has_property
--------------------+------------------------------ 
 asc                | f 
 desc               |  f 
 nulls_first        | f 
 nulls_last         |  f 
 orderable          | f 
 distance_orderable |  t -- f for gin 
 returnable         |  f 
 search_array       |  f 
 search_nulls       |  f