Gin Index
倒排索引
GIN 的意思是 Generalized Inverted Index
,通用倒排索引
倒排索引最经典的一个例子就是应用于ELK
。首先我们需要了解一下这种特殊的索引。
倒排索引(英语:Inverted index),也常被称为反向索引、置入档案或反向档案。
有两种不同的反向索引
- 一条记录的水平反向索引(或者反向档案索引)包含每个引用单词的文档的列表
- 一个单词的水平反向索引(或者完全反向索引)又包含每个单词在一个文档中的位置。
后者的形式提供了更多的兼容性比如短语搜索
,但是需要更多的时间和空间来创建。
下面以英文文本的搜索为例:
被搜索的文本如下
- $T_0=$"it is what it is"
- $T_1=$"what is it"
- $T_2$="it is a banana"
具体处理流程如下
-
第一步,创建文档列表
文档编号 文档数据 0 it is what it is 1 what is it 2 it is a banana -
第二步,创建倒排索引列表
单词ID 单词 倒排列表(包含单词ID,docID) 1 a 2 2 banana 2 3 is 0,1,2 4 it 0,1,2 5 what 0,1
创建索引完毕后,就需要搜索的时候使用这个索引了。
当我们进行检索的时候,
- 搜先对输入的数据进行分词,得到用户要搜索的所有词条。
- 拿着这些词条去倒排表中进行匹配。找到这些词条就能找到包含这些词条的所有文档的编号。
- 根据文档编号,去文档列表中找到相关的文档。
比如,我们要检索的语句是what is it
,那么
-
先对输入进行分词,分出
what
,is
,it
三个分词 -
在倒排表中找到对应的单词的倒排列表,他们分别是
{0,1}
,{0,1,2}
,0,1,2
。对找到的倒排列表作交集处理就是
$${0,1}\cap {0,1,2}\cap {0,1,2} = {0,1}$$
这个时候问题来了,文档0和文档1都符合条件,如何取舍呢,短语检索的连续条件,仅仅在文档1中具备,文档0不符合。
-
根据文档编号0,到文档编号中超出对应的文档内容。
你或许有点眼熟,第二步的倒排索引列表
有点像哈希表啊,就是拉链法的数组+链表组成的哈希表。
- 如果你对哈希不太清楚,请参考之前的哈希索引文章,里面有详细的哈希表介绍。
这里正是采用了哈希表的方法进行的倒排处理。那么哈希表有它的缺点,对于连续和范围处理不是非常好。
这个时候,另外一种数据结构,**B树/B+**树出现了。
- B树形成了层级查找结构,中间节点用于指出一定顺序范围的词典项目存储在哪个子树中,起到根据词典项比较大小进行导航的作用。
- 最底层的叶子节点存储单词的地址信息,根据这个地址就可以提取出单词字符串。
gin索引
概述
并不是所有的关系型数据库都有gin索引,这里描述的是Postgresql中的Gin索引。
GIN 用于处理这样的情况:
- 要被索引的项是复合值,而要由索引处理的查询需要搜索出现在复合项中的元素值
- 项可以是文档,查询可以是搜索包含特定单词的文档。
我们使用单词item
来引用要进行索引的复合值,单词 key
来指代元素值。GIN 总是存储和搜索key,而不是item
值本身。
GIN索引的存储结构是一组key,posting-list
对,其中posting-list
是一组key
出现的row ID
(TID
)。
-
比如,(‘hello', '14:2 23:4'),表示
hello
在14:2
和23:4
这两个位置出现过在PG中这些位置实际上就是元组的tid(行号,包括数据块ID(32bit),以及item point(16 bit) )
相同的row ID 可以出现在多个posting-list
中,因为一个item
可以包含多个key
。
每个键值只存储一次,因此对于同一个键出现多次的情况,GIN 索引非常紧凑。
GIN实现
gin的逻辑结构
GIN索引在逻辑上可以看成一个relation,该relation有两种结构
-
只索引基表的一列
key value Key1 Posting list( or posting tree) Key2 Posting list( or posting tree) … … -
索引基表的多列(复合、联合索引)
column_id key value Column1 num Key1 Posting list( or posting tree) Column2 num Key1 Posting list( or posting tree) Column3 num Key1 Posting list( or posting tree) ... ... ... - 这种结构,对于基表中不同列的相同的key,在GIN索引中也会当作不同的key来处理。
gin的物理结构
在内部,GIN 索引包含一个基于键的 b 树索引,其中每个键是一个或多个索引项indexed items
的元素(例如数组的元素) 。
叶子页面中的每个元组包含一个指向堆指针 b 树的指针(posting tree
) ,
当列表足够小,可以容纳一个索引元组和键值时,叶子页面则维护一个简单的堆指针列表(posting list
) 。
-
Entry
GIN索引中的一个元素,可以认为是一个词位,也可以理解为一个key
-
Entry tree
在Entry上构建的B树
entry tree的非叶子节点与普通的btree树的非叶子节点类似。
其叶子节点与普通btree的叶子节点不同,普通btree的叶子节点指向其索引的元组,而entry tree的叶子节点指向posting list,或者是posting tree。该指针用索引元组结构的tid表示。
-
Posting list
一个Entry出现的物理位置(heap ctid, 堆表行号)的链表
-
posting tree
在一个Entry出现的物理位置链表(heap ctid, 堆表行号)上构建的B树,所以posting tree的KEY是
ctid
,而entry tree的KEY是被索引的列的值
posting tree与entry tree 类似,也是一个B树,其树结构与entry tree完全一样,不同之处就是posting tree页面存储的元组内容与entry tree不同
posting tree 非叶子节点,KEY是堆表行号,VALUE是下层节点的块ID。
posting tree 叶子节点,是堆表行号list, 即posting list,(PostgreSQL使用了segment进行管理,将posting list中存储的item point(堆表行号)有序分段,压缩存储)。
-
pending list
索引元组的临时存储链表,用于fastupdate模式的插入操作
pending list是在fastupdate时,用来临时缓存GIN索引元组的,该链表把索引的插入操作推迟到一定条件时,批量处理。其结构是一个单向链表
从上面可以看出GIN索引主要由Entry tree
和posting tree
(or posting list)组成,
其中Entry tree是GIN索引的主结构树,posting tree是辅助树。
- entry tree类似于b+Tree,而posting tree则类似于BTree。
- 另外,不管entry tree还是posting tree,它们都是按KEY有序组织的。
GIN索引的页面和元组结构
GIN索引共有6种类型的页面:
类型 | 说明 |
---|---|
GIN_DATA (1 << 0) | 存放posting tree的页面 |
GIN_LEAF (1 << 1) | 叶子页面 |
GIN_DELETED (1 << 2) | 被标志删除的页面 |
GIN_META (1 << 3) | Gin索引的元页面 |
GIN_LIST (1 << 4) | Pending list页面 |
GIN_LIST_FULLROW (1 << 5) | 被填满的GIN_LIST页面 |
-
meta 页面
GIN索引的元信息页面,其页面保留区的flags有GIN_META标记。GIN索引的元信息页面的
blocknum
为0目前GIN索引的元数据页面主要记录pending list的相关信息、统计信息和版本号
-
gin索引页面的特别区域
GIN索引页面的special区,用来存储GIN索引相关的信息,与BTree的BTPageOpaqueData类似,主要是建立树形结构。
-
entry tree 页面
entry tree是GIN索引的主树,用来组织和存储entry。
-
posting tree 页面
posting tree 是gin的辅助树,用来组织超长的
posting list
,以加快其查询速度。该树的页面是由GIN_DATA标记。 -
pending list 页面
special区有一个指针,用来指向页面的下一个页面,这样就把所有的pending list页面以单链表的方式组织起来。
Gin索引的构建
-
初始化GinState结构
主要是从系统表中读取GIN索引支持的那5个用户自定义函数:
compare
、extractValue
、extractQuery
、consistent
、comparePartial
-
初始化meta和root页面
其中meta页面的blkno是0,root页面的blkno是1
-
记录构建日志
-
初始化构建时的临时内存上下文和用于缓存的RB树
-
调用
IndexBuildHeapScan
扫描基表,并调用ginBuildCallback
对每个基表的索引属性处理ginBuildCallback
实现对每个基表列的处理: -
把RB树中的所有索引元组插入到GIN的entry tree中
GIN索引的扫描
GIN索引的扫描是根据扫描条件,同GIN索引中查询满足条件的基表元组,GIN索引的扫描接口与btree索引类似:ginbeginscan/ ginrescan/ ginendscan/ gingetbitmap
,不同之处是GIN索引没有提供返回单条基表元组的接口(即类似于btgettuple的接口)。
GIN索引的扫描结果是一个bitmap
,里面存储的是所有满足条件的基表元组的tid。
1. ScanKey TO GinScanKey (where 转换)
scankey描述了SQL语句的where的条件,pg中使用ScanKeyData来描述,每一个ScanKeyData描述一个条件,ScanKeyData[]的数组描述了所有ScanKeyData的AND操作。而每一个ScanKeyData[]数组对应于一次扫描,所以对于有OR的查询,在执行时至少分成两个扫描,输出结果是两个扫描结果集的并集。对于如下的where条件A and B or C,分成两个扫描A and B 和C。我们研究的重点在于对索引的一次扫描。
对应于全文检索,如下的查询:
r1 @@ to_tsquery('A | B') and r2 @@ to_tsquery('C & D') or r3 @@ to_tsquery('E| F')
其会分成
scan1: r1 @@ to_tsquery('A | B') and r2 @@ to_tsquery('C & D')
scan2: r3 @@ to_tsquery('E| F')
结果就是 scan1 和 scan 2结果的并集
2. gingetbitmap GIN扫描接口
gingetbitmap
是实现GIN扫描的接口,该接口根据GinScanKey
把满足过滤条件的所有基表元组的tid存储到bitmap
中。
bitmap的大小由work_mem
参数控制,如果gin索引扫描出过多元组,则bitmap会自动的根据需要选择lossy存储。
bitmap的lossy存储是不再存储元组的tid而是直接存储元组所在页面的blkno。
由于此种存储bitmap没有存储具体元组,所以在执行层必须对bitmap返回的元组做recheck。
对于GIN索引,除了上面的情况下gin返回的元组需要做recheck外,还有一种情况需要做recheck:consistent方法会根据查询设置是否需要做recheck。
还是以下列查询为例
r1 @@ to_tsquery('A | B') and r2 @@ to_tsquery('C & D')
会分解成为两个GinScanKey
GinScanKey1(r1 @@ to_tsquery('A | B'))
GinScanKey2(r2 @@ to_tsquery('C & D'))
这两个条件的关系是 $$\cap$$
而GinScanKey1又分解为2个entry scan:entryA
$$\cup$$ entryB
GinScanKey2分解为entryC
$$\cap$$ entryD
每个entry scan扫描的结果都是一个posting list(posting tree也是posting list)
因此查询可以转换为
(plA ∪ plB) ∩ (plC ∩ plD)
- pl是posting list的缩写
即对posting list集合的逻辑运算,运算的结果构成的集合就是查询的结果
gingetbitmap的流程如下:
-
把ScanKey转换成GinScanKey
会调用extractQuery把查询字符串转换成entry key,然后对每个entry key创建一个GinEntryScan
-
扫描
pending list
,把满足条件的基表元组tid
加入到bitmap
中 -
对每个
GinEntryScan
进行扫描,找到GinEntryScan
的key
对应的叶子节点如果是部分匹配,则把所有满足部分匹配的基表元组存储
GinEntryScan
的临时bitmap中会调用comparePartial进行索引entry 与查询key之间的部分匹配
如果是精确查找,则把索引元组的posting list或者posting tree的root页面的posting list,存储到GinEntryScan的list中
-
循环获取满足查询条件的基表元组
对每一个GinScanKey,调用consistent,合并GinScanKey中所有GinEntryScan的结果
把所有GinScanKey的结果合并,一次一条的返回
把满足条件的基表元组tid插入到bitmap中
-
返回查询到的基表元组个数