本节简单介绍了PostgreSQL中的GIN索引,包括GIN索引的基础知识和结构等.GIN索引的主要用处是加快全文检索full-text search的速度. **全文检索** 全文检索full-text search的目的是从文档集中找到匹配检索条件的文档(document).在搜索引擎中,如果有很多匹配的文档,那么需要找到最匹配的那些,但在数据库查询中,找到满足条件的即可. 在PG中,出于搜索的目的,文档会被转换为特定的类型*tsvector*,包含词素(lexemes)和它们在文档中的位置.词素Lexemes是那些转换适合查询的单词形式(即分词).比如: ``` testdb=# select to_tsvector('There was a crooked man, and he walked a crooked mile'); to_tsvector ----------------------------------------- 'crook':4,10 'man':5 'mile':11 'walk':8 (1 row) ``` 从本例可以看到,分词后,出现了crook/man/mile和walk,其位置分别是4,10/5/11/8.同时,也可以看到比如there等词被忽略了,因为这些词是stop words(从搜索引擎的角度来看,这些词太过普通,不需要记录),当然这是可以配置的. PG全文检索中的查询通过tsquery来表示,查询条件包含1个或多个使用and(\&)/or(|)/not(!)等操作符连接的词素.同样的,使用括号来阐明操作的优先级. ``` testdb=# select to_tsquery('man & (walking | running)'); to_tsquery ---------------------------- 'man' & ( 'walk' | 'run' ) (1 row) ``` 操作符 @@ 用于全文检索 ``` testdb=# select to_tsvector('There was a crooked man, and he walked a crooked mile') @@ to_tsquery('man & (walking | running)'); ?column? ---------- t (1 row) select to_tsvector('There was a crooked man, and he walked a crooked mile') @@ to_tsquery('man & (going | running)'); ?column? ---------- f (1 row) ``` **GIN简介** GIN是Generalized Inverted Index通用倒排索引的简称,如熟悉搜索引擎,这个概念不难理解.它所操作的数据类型的值由元素组成而不是原子的.这样的数据类型成为复合数据类型.索引的是数据值中的元素. 举个例子,比如书末尾的索引，它为每个术语提供了一个包含该术语出现位置所对应的页面列表。访问方法(AM)需要确保索引元素的快速访问,因此这些元素存储在类似Btree中,引用包含复合值(内含元素)数据行的有序集合链接到每个元素上.有序对于数据检索并不重要(如TIDs的排序),但对于索引的内部结构很重要. 元素不会从GIN索引中删除,可能有人会认为包含元素的值可以消失/新增/变化,但组成这些元素的元素集大多是稳定的.这样的处理方式大大简化了多进程使用索引的算法. 如果TIDs不大,那么可以跟元素存储在同一个page中(*称为posting list*),但如果链表很大,会采用Btree这种更有效的数据结构,会存储在分开的数据页中(*称为posting tree*). 因此,GIN索引包含含有元素的Btree,TIDs Btree或者普通链表会链接到该Btree的叶子行上. 与前面讨论的GiST和SP-GiST索引一样，GIN为应用程序开发人员提供了接口，以支持复合数据类型上的各种操作。 举个例子,下面是表ts,为ts创建GIN索引: ``` testdb=# drop table if exists ts; psql: NOTICE: table "ts" does not exist, skipping DROP TABLE testdb=# create table ts(doc text, doc_tsv tsvector); CREATE TABLE testdb=# truncate table ts; slitter.'), ('I am a sheet slitter.'), ('I slit sheets.'), ('I am the sleekest sheet slitter that ever slit sheets.'), ('She slits the sheet she sits on.'); update ts set doc_tsv = to_tsvector(doc); create index on ts using gin(doc_tsv); TRUNCATE TABLE testdb=# insert into ts(doc) values testdb-# ('Can a sheet slitter slit sheets?'), testdb-# ('How many sheets could a sheet slitter slit?'), testdb-# ('I slit a sheet, a sheet I slit.'), testdb-# ('Upon a slitted sheet I sit.'), testdb-# ('Whoever slit the sheets is a good sheet slitter.'), testdb-# ('I am a sheet slitter.'), testdb-# ('I slit sheets.'), testdb-# ('I am the sleekest sheet slitter that ever slit sheets.'), testdb-# ('She slits the sheet she sits on.'); INSERT 0 9 testdb=# testdb=# update ts set doc_tsv = to_tsvector(doc); UPDATE 9 testdb=# testdb=# create index on ts using gin(doc_tsv); CREATE INDEX ``` 其可能的索引结构如下图所示:  在这里,使用黑底(page编号 + page内偏移)而不是箭头来表示对TIDs的引用. 与常规的Btree不同,因为遍历只有一种方法,GIN索引由单向链表连接,而不是双向链表. ``` testdb=# select ctid, left(doc,20), doc_tsv from ts; ctid | left | doc_tsv --------+----------------------+--------------------------------------------------------- (0,10) | Can a sheet slitter | 'sheet':3,6 'slit':5 'slitter':4 (0,11) | How many sheets coul | 'could':4 'mani':2 'sheet':3,6 'slit':8 'slitter':7 (0,12) | I slit a sheet, a sh | 'sheet':4,6 'slit':2,8 (0,13) | Upon a slitted sheet | 'sheet':4 'sit':6 'slit':3 'upon':1 (0,14) | Whoever slit the she | 'good':7 'sheet':4,8 'slit':2 'slitter':9 'whoever':1 (0,15) | I am a sheet slitter | 'sheet':4 'slitter':5 (0,16) | I slit sheets. | 'sheet':3 'slit':2 (0,17) | I am the sleekest sh | 'ever':8 'sheet':5,10 'sleekest':4 'slit':9 'slitter':6 (0,18) | She slits the sheet | 'sheet':4 'sit':6 'slit':2 (9 rows) ``` 在这个例子中,sheet/slit/slitter使用Btree存储而其他元素则使用简单的链表. 如果我们希望知道元素的个数,如何获取? ``` testdb=# select (unnest(doc_tsv)).lexeme, count(*) from ts testdb-# group by 1 order by 2 desc; lexeme | count ----------+------- sheet | 9 slit | 8 slitter | 5 sit | 2 upon | 1 mani | 1 whoever | 1 sleekest | 1 good | 1 could | 1 ever | 1 (11 rows) ``` 下面举例说明如何通过GIN索引进行扫描: ``` testdb=# explain(costs off) testdb-# select doc from ts where doc_tsv @@ to_tsquery('many & slitter'); QUERY PLAN ----------------------------------------------------------- Seq Scan on ts Filter: (doc_tsv @@ to_tsquery('many & slitter'::text)) (2 rows) testdb=# set enable_seqscan=off; SET testdb=# explain(costs off) select doc from ts where doc_tsv @@ to_tsquery('many & slitter'); QUERY PLAN --------------------------------------------------------------------- Bitmap Heap Scan on ts Recheck Cond: (doc_tsv @@ to_tsquery('many & slitter'::text)) -> Bitmap Index Scan on ts_doc_tsv_idx Index Cond: (doc_tsv @@ to_tsquery('many & slitter'::text)) (4 rows) ``` 执行此查询首先需要提取单个词素(lexeme,亦即检索键):mani/slitter.PG中有专门的API函数来完成,该函数考虑了由op class确定的数据类型和使用场景. ``` testdb=# select amop.amopopr::regoperator, amop.amopstrategy testdb-# from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop testdb-# where opc.opcname = 'tsvector_ops' testdb-# and opf.oid = opc.opcfamily testdb-# and am.oid = opf.opfmethod testdb-# and amop.amopfamily = opc.opcfamily testdb-# and am.amname = 'gin' testdb-# and amop.amoplefttype = opc.opcintype; amopopr | amopstrategy -----------------------+-------------- @@(tsvector,tsquery) | 1 @@@(tsvector,tsquery) | 2 (2 rows) ``` 回到本例中,在词素Btree中,下一步会同时检索键并进入TIDs链表中,得到: mani -- (0,2) slitter -- (0,1), (0,2), (1,2), (1,3), (2,2) 详见下图:  对于每一个找到的TID,调用*consistency function* API,由此函数确定找到的行是否匹配检索键.因为查询为AND,因此只返回(0,2). ``` testdb=# select doc from ts where doc_tsv @@ to_tsquery('many & slitter'); doc --------------------------------------------- How many sheets could a sheet slitter slit? (1 row) ``` **Slow Update** 对GIN index的列进行DML(主要是insert & update)是相当慢的,每一个文档通常包含许多需要索引的词素.因此,虽然只添加或更新一个文档,但也需要更新大量索引树.换句话说,如果多个文档同时更新,这些文档中的词素可能是一样的,因此总的消耗可能比逐个更新文档要小. PG提供了fastupdate选项,用打开此参数后,更新将在一个单独的无序链表中处理,当这个链表超过阈值(参数:gin_pending_list_limit或索引同名存储参数)时才会对索引进行更新.这种技术也有负面影响,一是降低了查询效率(需额外扫描该链表),二是某个更新恰好碰上索引更新,那么该次更新会相对很久. **Limiting the query result** GIN AM的其中一个特性时通常会返回bitmap而不是逐个返回TID,因此执行计划都是bitmap scan. 这样的特性胡导致LIMIT子句不会太有效: ``` testdb=# explain verbose select doc from ts where doc_tsv @@ to_tsquery('many & slitter'); QUERY PLAN ------------------------------------------------------------------------------ Bitmap Heap Scan on public.ts (cost=12.25..16.51 rows=1 width=32) Output: doc Recheck Cond: (ts.doc_tsv @@ to_tsquery('many & slitter'::text)) -> Bitmap Index Scan on ts_doc_tsv_idx (cost=0.00..12.25 rows=1 width=0) Index Cond: (ts.doc_tsv @@ to_tsquery('many & slitter'::text)) (5 rows) testdb=# explain verbose select doc from ts where doc_tsv @@ to_tsquery('many & slitter') limit 1; QUERY PLAN ------------------------------------------------------------------------------------ Limit (cost=12.25..16.51 rows=1 width=32) Output: doc -> Bitmap Heap Scan on public.ts (cost=12.25..16.51 rows=1 width=32) Output: doc Recheck Cond: (ts.doc_tsv @@ to_tsquery('many & slitter'::text)) -> Bitmap Index Scan on ts_doc_tsv_idx (cost=0.00..12.25 rows=1 width=0) Index Cond: (ts.doc_tsv @@ to_tsquery('many & slitter'::text)) (7 rows) ``` 这是因为Bitmap Heap Scan的启动成本与Bitmap Index Scan不会差太多. 基于这样的情况,PG提供了gin_fuzzy_search_limit参数控制返回的结果行数(默认为0,即全部返回). ``` testdb=# show gin_fuzzy_search_limit ; gin_fuzzy_search_limit ------------------------ 0 (1 row) ``` **参考资料** [Indexes in PostgreSQL — 7 (GIN)](https://habr.com/en/company/postgrespro/blog/448746/)