注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

生命无非记忆

不要在记忆中丢失了自己

 
 
 

日志

 
 

PostgreSQL GIN索引实现原理(2)  

2016-03-16 14:54:53|  分类: postgreSQL[原创] |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

4       GIN索引的页面和元组结构

4.1   页面结构

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页面

 

4.1.1  meta页面

GIN索引的元信息页面,其页面保留区的flagsGIN_META标记。GIN索引的元信息页面的blocknum0meta页面的结构如下:

typedef struct GinMetaPageData

{

         BlockNumber head;

         BlockNumber tail;

         uint32                tailFreeSize;

 

         BlockNumber nPendingPages;

         int64                  nPendingHeapTuples;

 

         BlockNumber nTotalPages;

         BlockNumber nEntryPages;

         BlockNumber nDataPages;

         int64                  nEntries;

 

         int32                  ginVersion;

} GinMetaPageData;

 

1.       head,tail

fast-inserted时使用,用来存储由GIN_LIST页面组成的pending list的头和尾的页面号。这些pending list是还没有插入到GIN索引树上的页面。

2.       tailFreeSize

pending list尾部页面的空闲空间

3.       nPendingPages

pending list的页面个数

4.       nPendingHeapTuples

pending listheap 元组个数

5.       nTotalPages,nEntryPages,nDataPages,nEntries

静态统计信息,由最近的一次VACUUM计算得出

6.       ginVersion

GIN索引的版本号

 

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

4.1.2  special

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

typedef struct GinPageOpaqueData

{

         BlockNumber rightlink;

         OffsetNumber maxoff;

         uint16                flags;

 } GinPageOpaqueData;

 

1.       rightlink:右兄弟节点的页面号,用来建立兄弟链表,把所有处于同一层次的节点连接成一个单向链表

2.       maxoff

a)         GIN_DATA|GIN_LEAF页面(posting tree的叶子页面)

记录posting list的长度

b)         GIN_DATA & ~GIN_LEAF页面(posting tree的非叶子页面)

记录PostingItems的长度

c)         GIN_LIST页面(pending list页面)

记录heap元组的个数

3.       flags:页面标记,用来标记页面的类型

4.1.3  entry tree页面

entry treeGIN索引的主树,用来组织和存储entry

1.       非叶子页面

非叶子页面不带任何标记信息,entry tree的非叶子页面结构与普通btree的页面结构基本上是一样的,如下:

PostgreSQL GIN索引实现原理(2) - zisedeqing - 生命无非记忆

 

2.       叶子页面

叶子页面带有GIN_LEAF标记,表示是entry tree的叶子页面。entry tree的叶子页面与普通btree页面结构类似,只是在元组结构上有所不同,如下:

PostgreSQL GIN索引实现原理(2) - zisedeqing - 生命无非记忆

 

具体不同的地方参见元组结构的介绍

4.1.4  posting tree页面

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

1.       非叶子页面

非叶子页面只有GIN_DATA标记,其页面结构如下:

PostgreSQL GIN索引实现原理(2) - zisedeqing - 生命无非记忆

 

与普通btree的页面类似,不同是其存储的元组是PostingItemPostingItem格式为:

typedef struct

{

BlockIdData child_blkno;

ItemPointerData key;

} PostingItem;

 

child_blkno

是孩子节点的页面号,用于建立posting tree的层次关系。使用BlockIdData类型而不是BlockNumber的原因是避免空间浪费。

key:是posting list中的key,实际上就是tid

页面头后面有一个ItemPointer不知道是干嘛用的,可能是用对齐的?

2.       叶子页面

叶子页面的标记为GIN_DATA|GIN_LEAF,其页面结构如下:

PostgreSQL GIN索引实现原理(2) - zisedeqing - 生命无非记忆

 

与正常的索引页面类似,开始是页面头信息,结尾是special区,不同的是中间区用来记录posting list

4.1.5  pending list 页面

entry tree的页面类似,如下:

PostgreSQL GIN索引实现原理(2) - zisedeqing - 生命无非记忆

不同之处是元组的结构,将在元组结构中介绍。

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

4.2   元组结构

4.2.1  entry tree元组

entry tree的元组依然使用IndexTuple来表示,其结构为:

typedef struct IndexTupleData

{

ItemPointerData t_tid;             /* refrence TID to heap tuple */

unsigned short t_info;               /* various info about tuple */

} IndexTupleData;   

 

但是对于不同的元组其t_tid和后面的key会有所不同。

1.       非叶子节点

PostgreSQL GIN索引实现原理(2) - zisedeqing - 生命无非记忆

 

与普通索引的元组结构一样,由IndexTupleData + key组成,不同的是其t_tid不是指向heap 元组,而是指向孩子页面。

2.       叶子节点

叶子节点的元组是由IndexTupleData+ key 或者是IndexTupleData + key +posting list表示的,对于posting list超长的情况,元组只记录posting list对于的posting treeroot 节点页面号,所以其元组结构如下:

PostgreSQL GIN索引实现原理(2) - zisedeqing - 生命无非记忆 


1)         元组结构a

该结构的元组,由于posting list太长,无法存储在元组内部,所以把posting list采用外部存储,所以索引元组只记录posting treeroot页面号。

为了区分这两种结构,使用元组中的tid中的ip_posidip_posid == GIN_TREE_POSTING,则表示记录的是posting tree,而tidip_blkid用来存储posting treeroot页面号

2)         元组结构b

该结构的元组,把posting list直接存储到key后面的连续空间中,使用tidip_posid来存储posting list的长度,tidip_blkid来存储posting list在元组内部的偏移。

注:

         GIN索引页面至少要存储3个索引元组,所以索引元组的最大值大约是8192/3 = 2730, 每个itempointer48b,所以一个元组最多可以存储(2730*1024)/48 = 58240, GIN_TREE_POSTING定义为0xffff,远大于索引元组能够存储的posting list的最大值,所以不用担心posting list个数与GIN_TREE_POSTING相同的问题

4.2.2  posting tree 元组

posting tree的元组格式比较简单,就是itempointer或者postingitem

非叶子节点:

[child pointer] [item pointer]

叶子节点:

[item pointer]

4.2.3  pending list元组

pending list的页面存储的是临时的索引元组,其元组格式为:

[tid] [flags] [key]

其中tid指向的是heap元组,这与普通元组一样,而与entry tree的元组不同。

5       GIN索引的构建

GIN索引的构建是根据基表构建GIN索引,在PG中通过index_build接口调用索引注册的build函数完成GIN索引的构建。index_build是一个通用接口,该接口会根据索引的不同类型,自动调用合适的build函数,GIN索引的build接口是ginbuild接口。

GIN索引在构建时,会调用用户定义的compare接口和extractValue接口,compare接口用来实现entry的比较,而extractValue接口用来把基表的属性值提取出对应的entry

GIN索引在构建时为了提高性能,使用了一种RB二叉树的结构来缓存索引元组,然后在RB二叉树大于maintenance_work_mem时,批量的把RB树中的索引元组插入到GINentry tree中。

GIN索引的构建流程是:

1.       初始化GinState结构

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

2.       初始化metaroot页面

其中meta页面的blkno0root页面的blkno1

3.       记录构建日志

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

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

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

a)         对每一个索引列,调用extractValue接口提取entry

b)         把所有的<entry, colno, heap tid>对插入到RB树中

c)         如果RB树大于maintenance_work_mem,则把RB树中的<entry, colno, heap tid>对插入到GIN索引中

此处在查找entry的插入位置时,会调用compare接口比较两个entry之间的大小

6.       RB树中的所有索引元组插入到GINentry tree

7.       结束

6       GIN索引的扫描

GIN索引的扫描是根据扫描条件,同GIN索引中查询满足条件的基表元组,GIN索引的扫描接口与btree索引类似:ginbeginscan/ ginrescan/ ginendscan/ gingetbitmap,不同之处是GIN索引没有提供返回单条基表元组的接口(即类似于btgettuple的接口)GIN索引扫描的基本用法是:

gscan = ginbeginscan(heap, nkeys);

ginrescan(gscan, scankey);

ntids = gingetbitmap(gscan, &btmap);

 

while(BitmapHeapNext(btmap))

{

         do something;

}

ginendscan(gscan)

从上面可以看出GIN索引的扫描结果是一个bitmap,里面存储的是所有满足条件的基表元组的tid

6.1   ScanKey TO GinScanKey

scankey描述了SQL语句的where的条件,pg中使用ScanKeyData来描述,每一个ScanKeyData描述一个条件,ScanKeyData[]的数组描述了所有ScanKeyDataAND操作。而每一个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 U scan2

 

以一次扫描为例,在GIN扫描时,系统会先把scankey转换成GinScanKey,然后根据GinScanKey进行索引的过滤。一个scankey会转换成一个GinScanKey,而每个GinScanKey又会包含多个GinScanEntry,每个GinScanEntry表示scankey中的to_tsquery中的每一项。以r1 @@ to_tsquery(‘A | B’) and r2 @@ to_tsquery(‘C & D’)为例,其scankey为:

ScanKey[0] : r1 @@ to_tsquery(‘A | B’)

ScanKey[1] : r2 @@ to_tsquery(‘C & D’)

 

其转换后的结构是:

PostgreSQL GIN索引实现原理(2) - zisedeqing - 生命无非记忆

 

 

转换的实现是通过用户定义函数extractQuery来完成的,还以上面的查询为例,系统对每一to_tsquery(‘A | B’)类型的查询调用extractQuery,提取出每个用于查询的键值(对于to_tsquery(‘A | B’)提取后的键值是querykey = {“A”, “B”}),然后对每个查询键值创建一个GinScanEntryGIN索引的每个GinScanEntry就是对GIN索引的一次扫描。如下:

PostgreSQL GIN索引实现原理(2) - zisedeqing - 生命无非记忆

 

6.2   gingetbitmap

gingetbitmap是实现GIN扫描的接口,该接口根据GinScanKey把满足过滤条件的所有基表元组的tid存储到bitmap中。

bitmap的大小由work_mem参数控制,如果gin索引扫描出过多元组,则bitmap会自动的根据需要选择lossy存储。bitmaplossy存储是不再存储元组的tid而是直接存储元组所在页面的blkno。由于此种存储bitmap没有存储具体元组,所以在执行层必须对bitmap返回的元组做recheck

对于GIN索引,除了上面的情况下gin返回的元组需要做recheck外,还有一种情况需要做recheckconsistent方法会根据查询设置是否需要做recheck

 

我们还以查询r1 @@ to_tsquery(‘A | B’) and r2 @@ to_tsquery(‘C & D’)来说明gingetbitmap实现原理。查询r1 @@ to_tsquery(‘A | B’) and r2 @@ to_tsquery(‘C & D’),会分解为2GinScanKeyGinScanKey1(r1 @@ to_tsquery(‘A | B’))GinScanKey2(r2 @@ to_tsquery(‘C & D’)),这两个条件的关系是,而GinScanKey1又分解为2entry scanentryA entryBGinScanKey2分解为entryC  ∩ entryD。每个entry scan扫描的结果都是一个posting list(posting tree也是posting list),因此r1 @@ to_tsquery(‘A | B’) and r2 @@ to_tsquery(‘C & D’)就转化为:

(plA  plB)  (plC ∩ plD), 其中plposting list的缩写

即对posting list集合的逻辑运算,运算的结果构成的集合就是查询的结果。

gingetbitmap会调用用户4个自定义的接口:compareextractQueryconsistentcomparePartialcompareentry scan时用于比较两个entry key的大小;extractQuery用来把查询字符串转换成entry keyconsistent用来合并每一个GinScanKey的结果集;comparePartial用来实现部分匹配。gingetbitmap的流程如下:

1.       ScanKey转换成GinScanKey

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

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

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

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

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

b)         如果是精确查找,则把索引元组的posting list或者posting treeroot页面的posting list,存储到GinEntryScanlist

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

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

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

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

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

7       GIN索引的insert

GIN索引的插入操作与btree索引不同,对于btree索引,基表增加一行,btree索引也是增加一个索引项。而对于GIN索引基表增加一行,GIN索引可能需要增加多个索引项。所以GIN索引的插入是低效的。所以PG为了解决这个问题,实现了两种插入模式:

1.       正常模式

在该模式下,基表元组产生的新的GIN索引,会被立即插入到GIN索引

2.       fastupdate模式

在该模式下,基表元组产生的新的GIN索引,会被插入到pending list中,而pending list会在一定条件下批量的插入到GIN索引中

下面就说明一下fastupdate模式的插入。

 

1.     开启和关闭fastupdate模式

可以通过create index WITH FASTUPDATE = OFF来关闭fastupdate模式,默认情况下是开启fastupdate模式

2.     对索引扫描的影响

fastupdate模式下,新的索引元组以追加的方式插入到pending list中,不会进行任何的排序和去重操作,所以,在扫描时,只能顺序扫描,因此pending list的扫描效率是非常低的,必须保证pending list的大小不要太大

3.     对插入的影响

通常情况下,在fastupdate模式下,基表的更新效率是比较高的,但是如果一个事务的更新刚好让pending list到达临界点,而导致合并操作,则会使该事务比正常的事务慢很多

4.     pending list的合并

pending list的索引元组合并到GIN索引树上有2种触发条件:

1)         pending list所占空间大于work_mem

2)         vacuum 索引的基表时

因此可以根据autovacuum的间隔时间和work_mem来控制pending list的大小,避免其过大而拖慢扫描速度

pending list合并时,其采用与GIN索引构建时相同的方式,即先把pending list内的数据,组织成一个RB树,然后再把RB树合并到GIN索引上。RB树可以把pending list中无序的数据变成有序,并且可以合并重复key的项,提高插入效率。

8       GIN索引的vacuum

GIN索引的vacuum是用来清理无用的posting list或者posting tree的,GIN索引的vacuumbtree索引的vacuum一样,提供了两个接口ginbulkdeleteginvacuumcleanup

GIN索引的vacuum主要是清理entry treeposting tree,如果entryposting list为空了,vacuum依然不会删除该entry,说明entry tree中的entry永远不会被删除;对于posting tree,如果posting tree也空了,在系统依然会把posting treeroot页面保留,并关联到entry上面。

9       GIN索引的并发控制

以后补充

10             GIN索引的日志

以后补充

11             TSVector类型的GIN索引

PG默认提供了对TSVector数据类型的GIN索引的支持,并提供了对TEXT类型转换TSVector类型的接口,因此PG在对TEXT类型的属性建立GIN索引时,需要使用to_tsvector接口把TEXT类型转换成TSVector

11.1     TSVector

TSVectorPG中的一种数据类型,用来实现全文搜索。它实际上是一个<key, pos list>的数组,其中key是一个关键词,pos listkey在字符串中出现的位置列表。如字符串:

’ Before you can use PostgreSQL you need to install it’

在转换成TSVector后的值为:

[Before, 1] [you, 2:6] [can, 3] [use, 4] [PostgreSQL, 5] [need, 7] [to, 8] [install, 9] [it, 10]

因此TSVector实际上就是一组key和其出现位置的集合。

在代码中使用如下结构表示TSVector

typedef struct

{

         int32                  vl_len_;

         int32                  size;

         WordEntry        entries[1];                  /* var size */

         /* lexemes follow */

} TSVectorData;

其中WordEntry为:

typedef struct

{

         uint32

                                     haspos:1,

                                     len:11,                        /* MAX 2Kb */

                                     pos:20;                        /* MAX 1Mb */

} WordEntry;

WordEntry的定义可以看出PG中每个key的最大长度是2Kb,而每个TSVector的最大长度是1MB

根据定义,TSVector的内存结构为:

[vl_len_] [size] [entry array] {[lexeme][pos num][pos array], … , [lexeme][pos num][pos array]}

 

对于TEXT类型,在更新索引时,会先调用to_tsvector把基表的索引列的字符串转换成TSVector表示的key和位置列表的集合,然后在使用用户自定义的extractValueTSVector中所有的key提取出来,对每个key创建一个索引元组,然后插入到GIN索引中。

11.2     TSQuery

TSQuery用来表示全文搜索的查询,PG提供了一个to_tsqueryplainto_tsquery接口把待查询的字符串格式化成TSQuery,其结构如下:

typedef struct

{

         int32                  vl_len_;

         int4           size;                    /* number of QueryItems */

         char          data[1];

} TSQueryData;

其中QueryItem的结构为:

typedef union

{

         QueryItemType type;

         QueryOperator qoperator;

         QueryOperand qoperand;

} QueryItem;

QueryItem是一个操作符和操作数的联合体,对于to_tsquery中的每一项都会转换成一个QueryItem

GIN扫描之前会把TSQuery中的key使用函数extractQuery提取出来,并为每个key创建一个GinScanEntry。在GIN扫描时,会对每个GinScanKey调用consistent接口根据TSQuery中记录的key之间的关系(&|、!)合并每个GinScanEntry的结果集。

11.3     5GIN方法的实现

PG提供了TSVector数据类型的5GIN索引用户自定义方法:

1.       compare方法:gin_cmp_tslexeme

比较两个key之间的大小

2.       extractValue方法:gin_extract_tsvector

提取TSVector中的key

3.       extractQuery方法:gin_extract_tsquery

提取TSQuery中的key

4.       consistent方法:gin_tsquery_consistent

根据TSQuery判断输入是否满足查询条件

5.       comparePartial方法:gin_cmp_prefix

部分匹d配,PG只实现了前缀匹配的接口。

  评论这张
 
阅读(142)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017