Gin index 倒排索引

张彤 2022年06月11日 210次浏览

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"

具体处理流程如下

  1. 第一步,创建文档列表

    文档编号文档数据
    0it is what it is
    1what is it
    2it is a banana
  2. 第二步,创建倒排索引列表

    单词ID单词倒排列表(包含单词ID,docID)
    1a2
    2banana2
    3is0,1,2
    4it0,1,2
    5what0,1

创建索引完毕后,就需要搜索的时候使用这个索引了。

当我们进行检索的时候,

  1. 搜先对输入的数据进行分词,得到用户要搜索的所有词条
  2. 拿着这些词条去倒排表中进行匹配。找到这些词条就能找到包含这些词条的所有文档的编号
  3. 根据文档编号,去文档列表中找到相关的文档。

比如,我们要检索的语句是what is it,那么

  1. 先对输入进行分词,分出what,is,it三个分词

  2. 在倒排表中找到对应的单词的倒排列表,他们分别是 {0,1},{0,1,2},0,1,2

    对找到的倒排列表作交集处理就是

    $${0,1}\cap {0,1,2}\cap {0,1,2} = {0,1}$$

    这个时候问题来了,文档0和文档1都符合条件,如何取舍呢,短语检索的连续条件,仅仅在文档1中具备,文档0不符合。

  3. 根据文档编号0,到文档编号中超出对应的文档内容。

你或许有点眼熟,第二步的倒排索引列表有点像哈希表啊,就是拉链法的数组+链表组成的哈希表。

  • 如果你对哈希不太清楚,请参考之前的哈希索引文章,里面有详细的哈希表介绍。

这里正是采用了哈希表的方法进行的倒排处理。那么哈希表有它的缺点,对于连续和范围处理不是非常好。

这个时候,另外一种数据结构,**B树/B+**树出现了。

  • B树形成了层级查找结构,中间节点用于指出一定顺序范围的词典项目存储在哪个子树中,起到根据词典项比较大小进行导航的作用。
  • 最底层的叶子节点存储单词的地址信息,根据这个地址就可以提取出单词字符串。

gin索引

概述

并不是所有的关系型数据库都有gin索引,这里描述的是Postgresql中的Gin索引。

GIN 用于处理这样的情况:

  • 要被索引的项是复合值,而要由索引处理的查询需要搜索出现在复合项中的元素值
  • 项可以是文档,查询可以是搜索包含特定单词的文档。

我们使用单词item来引用要进行索引的复合值,单词 key 来指代元素值。GIN 总是存储和搜索key,而不是item值本身。

GIN索引的存储结构是一组key,posting-list对,其中posting-list是一组key出现的row IDTID)。

  • 比如,(‘hello', '14:2 23:4'),表示hello14:223:4这两个位置出现过

    在PG中这些位置实际上就是元组的tid(行号,包括数据块ID(32bit),以及item point(16 bit) )

相同的row ID 可以出现在多个posting-list中,因为一个item可以包含多个key

每个键值只存储一次,因此对于同一个键出现多次的情况,GIN 索引非常紧凑。

GIN实现

gin的逻辑结构

GIN索引在逻辑上可以看成一个relation,该relation有两种结构

  1. 只索引基表的一列

    keyvalue
    Key1Posting list( or posting tree)
    Key2Posting list( or posting tree)
  2. 索引基表的多列(复合、联合索引)

    column_idkeyvalue
    Column1 numKey1Posting list( or posting tree)
    Column2 numKey1Posting list( or posting tree)
    Column3 numKey1Posting list( or posting tree)
    .........
    • 这种结构,对于基表中不同列的相同的key,在GIN索引中也会当作不同的key来处理。

gin的物理结构

在内部,GIN 索引包含一个基于键的 b 树索引,其中每个键是一个或多个索引项indexed items的元素(例如数组的元素) 。

叶子页面中的每个元组包含一个指向堆指针 b 树的指针(posting tree) ,

当列表足够小,可以容纳一个索引元组和键值时,叶子页面则维护一个简单的堆指针列表(posting list) 。

image.png

  1. Entry

    GIN索引中的一个元素,可以认为是一个词位,也可以理解为一个key

  2. Entry tree

    在Entry上构建的B树

    entry tree的非叶子节点与普通的btree树的非叶子节点类似。

    其叶子节点与普通btree的叶子节点不同,普通btree的叶子节点指向其索引的元组,而entry tree的叶子节点指向posting list,或者是posting tree。该指针用索引元组结构的tid表示。

  3. Posting list

    一个Entry出现的物理位置(heap ctid, 堆表行号)的链表

  4. 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(堆表行号)有序分段,压缩存储)。

  5. pending list

    索引元组的临时存储链表,用于fastupdate模式的插入操作

    pending list是在fastupdate时,用来临时缓存GIN索引元组的,该链表把索引的插入操作推迟到一定条件时,批量处理。其结构是一个单向链表

从上面可以看出GIN索引主要由Entry treeposting 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页面
  1. meta 页面

    GIN索引的元信息页面,其页面保留区的flags有GIN_META标记。GIN索引的元信息页面的blocknum为0

    目前GIN索引的元数据页面主要记录pending list的相关信息、统计信息和版本号

  2. gin索引页面的特别区域

    GIN索引页面的special区,用来存储GIN索引相关的信息,与BTree的BTPageOpaqueData类似,主要是建立树形结构。

  3. entry tree 页面

    entry tree是GIN索引的主树,用来组织和存储entry。

  4. posting tree 页面

    posting tree 是gin的辅助树,用来组织超长的posting list,以加快其查询速度。该树的页面是由GIN_DATA标记。

  5. pending list 页面

    special区有一个指针,用来指向页面的下一个页面,这样就把所有的pending list页面以单链表的方式组织起来。

Gin索引的构建

  1. 初始化GinState结构

    主要是从系统表中读取GIN索引支持的那5个用户自定义函数:compareextractValueextractQueryconsistentcomparePartial

  2. 初始化meta和root页面

    其中meta页面的blkno是0,root页面的blkno是1

  3. 记录构建日志

  4. 初始化构建时的临时内存上下文和用于缓存的RB树

  5. 调用IndexBuildHeapScan扫描基表,并调用ginBuildCallback对每个基表的索引属性处理

    ginBuildCallback实现对每个基表列的处理:

  6. 把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的流程如下:

  1. 把ScanKey转换成GinScanKey

    会调用extractQuery把查询字符串转换成entry key,然后对每个entry key创建一个GinEntryScan

  2. 扫描pending list,把满足条件的基表元组tid加入到bitmap

  3. 对每个GinEntryScan进行扫描,找到GinEntryScankey对应的叶子节点

    如果是部分匹配,则把所有满足部分匹配的基表元组存储GinEntryScan的临时bitmap中

    会调用comparePartial进行索引entry 与查询key之间的部分匹配

    如果是精确查找,则把索引元组的posting list或者posting tree的root页面的posting list,存储到GinEntryScan的list中

  4. 循环获取满足查询条件的基表元组

    对每一个GinScanKey,调用consistent,合并GinScanKey中所有GinEntryScan的结果

    把所有GinScanKey的结果合并,一次一条的返回

    把满足条件的基表元组tid插入到bitmap中

  5. 返回查询到的基表元组个数