1TidBitmap结构分析

TidBitmap是一个专门用来在内存中缓存Tuple的tid的数据结构。TidBitmap位于Postgresql存储引擎StorageEngine\ src\ backend\ nodes\tidbitmap.c中，其结构如图1-1所示，是一个由若干名为PagetableEntry的位图构成的一张动态Hash表Pagetable。其中，每个bucket对应一个PagetableEntry。TidBitmap顾名思义，正常情况下，每个PagetableEntry代表一个Page，而在该PagetableEntry中，共有(Max_Tuples_Per_Page - 1)/(Bits_Per_BitMapWord +1)位，即默认情况下一个Page总共最多可以存储256个Tuple，那么PagetableEntry中就有256位，每一位初始为0，代表着该Tuple在page中的偏移位置，该Page的bucket映射的Page号和tuple在PagetanleEntry中的偏移位置共同构成了该tuple的实际物理存储位置即Tid。当需要存储一个Tuple的Tid时，我们只需要根据该Tuple的页号（BlockNum)映射到对应的Bucket上，再根据该tuple在Page上的偏移位置将Bucket对应的PageTableEntry中相应的位置1即可。

值得注意的是，PageTableEntry不仅可以表示一个Page(页），同时也可以表示一个Chunk(块）。对于Chunk的定义，Postgresql是这样描述的，即一个Chunk为若干Page的集合。在Postgresql中定义Page_Per_Chunk为 BLCKSZ / 32，即默认情况下一页的大小为8192B，一个8192B大小的Chunk可以表示256页。其中每一位对应着页号。至于其用法将在第3节中深入解释。

图1-1 TidBitMap结构

2 TidBitmap使用场景

对于Postgresql存储引擎而言，上层调用存储引擎读取相关tuple有三种途径，如图2-1所示。

第一种是直接扫描heap表进行heapscan（图2-1 C块），红色箭头流程。这种情况仅适用于需要进行全表扫描或者该heap表没有建立索引但仍需要查找某一tuple的情况，尤其是后者当heap表足够大时需要耗费大量时间。

第二种是tuple所在的heap表上建立起Index表（图2-1 A块），绿色箭头流程。当需要读取相关tuple时，将首先依据相应检索条件通过Index表查找出合适的tuple的Tid，然后再通过该Tid去heap表上将真正的tuple内容缓存到相应的Buffer中，再然后在Index表读取下一个符合查找条件的tid，再到heap表上去查找。对于heap表而言，每一次的查找都相当于一次随机查找，其IO代价较大。

图2-1 三种获取tuple的途径

第三种是***箭头流程，在第二种方式的基础上，通过检索条件在Index表上查找出符合条件的某一个tuple的Tid时，会将该Tid存入TidBitmap中。然后继续在索引表上查找下一个符合条件的Tid，再将其存入TidBitmap，直到所有符合条件的Tid都存入TidBitmap后，该TidBitmap会将存入的所有Tid按照tuple所在的页号从小到大进行排序，存入TidBitmap中的指定链表中PagetableEntry ** spages（或者是PagetableEntry **schunks）。最后再通过该spages链表，去heap中将每一个tuple读取至缓存中。由于每次从heap中读取的tuple都是按照页号从小到大排序好的，故每次IO代价相对于第二种随机IO要低的多。

3TidBitMap具体操作流程

TidBitmap的调用接口在IndexEntrySetScan类中，当通过索引查找符合条件的tuple时，可以选择是否使用bitmap查找，如若使用将首先调用该类中的getBitmap函数，从而触发tidbitmap中的tbm_create函数。

在tbm_create函数中，初始默认设置该hash表为10MB大小。TidBitMap的状态有三种，分别为TBM_EMPTY，TBM_ONE_PAGE，TBM_HASH。分别对应着TidBitMap初始空状态，只存储一个PageTableEntry状态，以及存储多个PageTableEntry状态。这里需要说明的是，之所以存在TBM_ONE_PAGE状态是因为当TidBitMap中只存储一个PageTableEntry时，无需花费相对高昂的代价构建起动态Hash表，只需要用一个PageTableEntry类型的指针entry1指向该PageTableEntry即可。此时在tbm_create函数中，置TBM的状态为TBM_EMPTY。在第1节提到过，TBM是一个由n个PageTableEntry位图构成的动态hash表，因此在tbm_create过程中将计算初始大小下(10MB)最多能够存储多少个PageTableEntry，即nbuckets值，具体的计算过程将在第4节介绍，本节不再详述，至此TBM的初始化过程结束。

紧接着，当初始化完TBM后，将在索引上查找出符合查询条件的Tid，并将相应的Tid存入TBM中。假设索引为B-Tree索引，那么这个过程将在nbtree.c中的btgetbitmap函数中完成。在该函数中，每次将从B-Tree索引中通过执行_bt_next函数读取出一个Tid，再执行tbm_add_tuples函数，将该Tid添加入TBM中。

在tbm_add_tuples函数中，有三个重要的步骤：

首先，要能根据Page页号在TBM的动态Hash表中找到其对应的Bucket，从而找到对应的PageTableEntry。该过程通过tbm_get_pageentry函数完成。如若TBM只含有一个TBM_ONE_PAGE，那么我们将直接返回TBM中entry1成员变量对应的PageTableEntry。否则，我们将通过Hash映射查找。

其次，当得到对应的PageTableEntry后，如若该Tid为0页第2个tuple，由于一个PageTableEntry可以表示256个tuple，每一位表示一个tuple，故PageTableEntry共由8个uint32类型的bitmapword组成，此时2/32取整很容易算出即将修改的位在第0个bitmapword。2%32取余亦算出待修改位在第bitmapword中的2个位置(实际Postgresql代码中位号是按照0-7排列故实际位置需减1)。然后将相应的位由0置为1，即完成插入操作。

最后，值得注意的是，TBM初始化时默认设置为10MB，则计算出该PageTable在当前大小下最大能容纳131074个Bucket，此即为其MaxEntries，当添加的tid导致当前PageTable的entry数大于MaxEntries，此时受限于TBM大小，TBM将进行lossify操作，即将部分本来存储Tid的PageTableEntry删除，转而生成存储该Tid所在Page号的PageTableEntry，从而使得该TBM当前entry数下降，达到限制TBM大小的目的。该操作在tbm_lossify函数中完成，现举例说明：假设TBM的动态Hash表PageTable只有4个Buckets即只能存储4个PageTableEntry，每个PageTableEntry能够存256个Tid，假如该TBM先前已经加入4个Tid，分别第0页到第3页的第1个tuple，那么此时TBM的nentries数为4，达到了当前PageTable的maxentries个数，此时如果添加一个4页第1个tuple进来，则TBM将执行lossify操作，对每一个PageTableEntry进行压缩，直到当前TBM的PageTableEntry个数小于TBM的maxentries。每个PageTableEntry压缩的具体过程在tbm_mark_page_lossy函数中完成。

在tbm_mark_page_lossy函数中可以看到，对于待处理的PageTableEntry将首先从动态Hash表中找到，并将其删除。然后根据已删除的PageTableEntry所表示的页号计算Chunk号，例如先处理第0页的PageTableEntry，由于一个Chunk能表示256页，故0/256取整，即该Page在第0个Chunk上。然后从动态Hash表，依据Chunk号去寻找其对应的Bucket。此时如果该Bucket上没有PageTableEntry，则构建该Chunk的PageTableEntry。否则将对应的Tuple类型的PageTableEntry初始化为Chunk类型的PageTableEntry，丢失掉之前存储的Tuple信息，最后再将该页的页号对应的位置1，即完成一个PageTableEntry的lossify操作。此时对于整个TBM而言，删除了1个Page类型的entry，新建了一个Chunk类型的entry，整体entry总数仍然为4。继续处理表示第1页的PageTableEntry，同样从Hash表中删除该PageTableEntry，然后找到第1页对应的Chunk类型的PageTableEntry，此Chunk类型的entry在处理第0页时已经构建好了，故只需在对应的位上置1即可，此时TBM删除了一个Page类型的entry，没有增加新的Chunk类型的entry，整体entry总数为3。继续处理第2页的PageTableEntry，同理删除该entry，在相应的Chunk类型的entry中适当的位置置1，此时entry总数降为2。处理第3页后，此时entry总数降为1，达到了lossify的终止条件，即nentries < max

entries/2，压缩过程终止。

当将所有符合条件的Tid加入TBM，即tbm_add_tuples函数执行完毕后，将逐次从TBM中取出相应的Tid去Heap表中进行Tuple查找。在第一次从TBM取Tid时，将会执行一个排序操作，TBM会将其中所有的Page类型的PageTableEntry指针按照页号从小到大的顺序存储在其spages链表中。(同理，也会将所有的Chunk类型的PageTableEntry按照Chunk号从小到大的顺序存储在其schunks链表中。)由于spages中存储的Tid均为符合条件的待查找Tuple，故之后每次从TBM取出Tid时只需从spages链表中逐个读取PageTableEntry，取出对应的Tid即可。上述操作是在tbm_begin_iterate函数中完成的。

最后将取出的Tid通过heapam.c中的bitgetpage函数在heap表中进行查找，得到最终的tuple，并将其缓存至内存中来。

4TidBitMap优劣分析

首先从使用场景上来看，依据第2节的分析可知，TidBitMap主要应用于已构建索引的heap表的查找，对于没有构建索引的heap表只能够顺序扫描heap表。对于前者，目前Postgresql存储引擎提供了俩种索引查找方式，第一种是通过索引查找出符合条件的的tid后，直接去heap中进行查找。第二种是将索引查找出的tid先存入内存中的TidBitMap，并按照页号进行排序，再从小到大依次从heap中取出相应的tuple。第一种方式相对于第二种方式省去了中间构建TidBitMap的过程，但是由于从索引中取出的tid无序，因此每一次对于heap的scan都相当于是一次随机I/O，代价较大。而第二种方式虽然增加了构建TidBitMap的过程，但是由于所有的tid都是按照页号从小到大排序好的，因此在对heap进行scan时相当于顺序读取，I/O代价较低。因此可以看出，当查询结果集较大时，采用构建TidBitMap缓存查询结果集，再顺序扫描heap表读取相应tuple更加有优势，如若采用第一种方式将花费大量时间对heap表进行随机I/O，其代价要大于额外构建TidBitMap的代价。

其次从内存耗费上来看，使用TidBitMap来缓存大结果集的Tid，不可避免的要造成额外的内存开销，下面将针对这种情况做出分析：

如图4-1可以看到对于TidBitMap而言占用空间最大的两个结构分别是动态Hash表Pagetable以及排好序的结果集链表spages和schunks。对于一个64GB大小的heap表而言，一页为8K，则该heap表共包含8MB页，每一页最多可以包含256个tuple，则64GB的heap表共包含有2048MB个tuple。

图4-1 TidBitmap代码结构

我们假设两种极端情况：

当查询结果集涵盖整个heap表时，共需要缓存8M个PageTableEntry，每个PageTableEntry由8个unit32位bitmapword构成。10MB大小的Hash表能够提供最多131072个Buckets，故理论上Hash表大小至少为(8M/131072)*10大小，即610MB。而结果集链表大小为8M*8B(64位)，即64MB。故对于TidBitMap而言极端情况下，不lossify至少需要674兆内存空间。请注意，这里说至少是因为，TidBitMap所采用的是动态Hash表，初始值设置为10兆大小，在不断地向TBM添加Tid时，若TBM的当前entry数目大于当前Hash表最大能支持的entry数时，该Hash表将会翻倍扩容，故最坏情况下TBM不lossify，每次动态Hash表扩容翻倍，为了能够装下64GB的heap所有的页，此时Hash表大小应为640兆(初始值设为10兆），总TidBitMap则为704MB的内存占用。

考虑到TidBitMap当内存受限时会自主进行lossify操作。设想64GB的heap表，共8M页全部lossify化，则需要8M/256个Chunk，即32K个，动态Hash表初始值10MB完全能够满足。schunk链表大小为32K*8B(64位)，即256KB，也就是说如果全部压缩的话仅需11MB左右的大小即可表示64GB的heap表。但是压缩的代价是在进行heap表scan时需要重新查找符合条件的tuple的正确偏移位置。

当然在正常情况下TidBitMap会不断压缩调整，即其中会同时存在lossify的PageTableEntry以及未lossify的PageTableEntry。在TidBitMap扩展条件中，只有当全部PageTableEntry全部lossify后，其Entries个数仍然大于MaxEntries的一半，才会触发整个Hash表的翻倍扩容。故真正情况下，在不断地lossify操作后，初始的10MB大小的TidBitMap是可以存储下64GB的heap表的。

通过上述分析可以看到在实际使用中随着查询结果集的不断增大，TidBitMap所占用的内存也会不断增长，并且TidBitMap会不断地循环执行lossify操作以适应"大BitMap，小Working-Mem"的工作环境，从而在查询性能上带来一定的影响。