Greenplum执行器位图——让查询更有效

为了让查询更加有效，Greenplum引入了索引，但是索引在一些应用场景上也会有访问性能、过滤条件限制等问题，而位图和基于位图的访问很好的解决了这一问题。今天我们通过这篇文章来看一下Greenplum执行器的奥秘。

为什么需要位图扫描

首先来看一个普通的查询

SELECT sid FROM student WHERE enroll_year = 2017 OR enroll_year = 2018 OR enroll_year = 2019;

执行上面查询时，Greenplum最简单的方式可以采用对表student顺序扫描（Sequence Scan）。如果表student很大，并且查询只需要读取少量元组时，顺序扫描需要将全部元组从数据文件读出再进行过滤，这显然不是一个经济的方式。对此，Greenplum引入了索引，利用索引通过过滤条件可以很有效的定位到需要的元组，但是基于索引也会带来自身的问题。

第一个问题就是，如果结果元组比较多，但又没有到全部数据那么大的量级，通过索引访问元组会导致随机访问磁盘，访问性能上会差一个数量级。因为元组在磁盘上的存放顺序跟索引键的排序有可能是不同的，特别是对于存在多个索引的情况下。Greenplum期望能够做到基于结果集的顺序访问磁盘。

另外一个问题是，对于上面的查询语句，如果过滤条件是多个过滤条件的组合比如析取，无法直接利用索引进行查询。一个可能的解决办法是，可以通过各个查询条件分析到索引中查询到结果，再将所有结果“合并”到一起。通过最后“合并”后的结果进行查询。

所以，Greenplum引入了位图和基于位图的访问，位图中的第n位对应Greenplum中的第n个元组，通过位图中的1来表示对应元组命中，0表示跳过对应元组。如果将位图与元组的位置进行映射，就涉及到Greenplum元组的寻址问题。另外，Greenplum从索引接口上也直接支持返回满足条件元组的位图。

Greenplum元组的寻址与位图映射

Greenplum中的表，从存储格式上分为Heap表和AO表。Heap表支持频繁的元组更新和修改，结合磁盘读写的特点，为了效率，以页为单位进行访问。在Greenplum系统设计中，一个文件页是以32K （BLCKSZ）字节为大小，为物理磁盘页的整数倍。以32K字节为大小，在联机分析处理（OLAP）的场景下，可以获得较好的文件IO吞吐量，特别是对应顺序扫描的情况。上一节中讲到了表文件的分段存储，从逻辑上来看，对于同一个表的数据文件，文件地址空间可以认为是一维的线性空间，然后按照文件页大小32K进行切分。每个文件大小限制最多为32K（RELSEG_SIZE）个块，而每个页大小是32K （BLCKSZ）字节，所以一个文件最大可以为1G（BLCKSZ * RELSEG_SIZE）字节。如果表的数据的很大，可以采用多个文件连续存储。每个数据文件称为一个文件段（seg）。文件页的逻辑序号Greenplum中称为块号，块号从第0开始，通过块号 + 块内偏移就可以寻址寻址到任何字节。给出逻辑的一维地址（address）空间，可以转换成对应的块号（block_number），也算出所对应的文件段号（seg_number）和对应段文件内偏移（seg_offset）。

相互直接的转换公式为

block_number=address / BLCKSZ

seg_number=address / (BLCKSZ*RELSEG_SIZE)

seg_number=block_number / RELSEG_SIZE

seg_offset=address % (BLCKSZ*RELSEG_SIZE)

所以，通过块号 + 块内偏移就能够寻址到第n个元组，Greenplum通过数据结构ItemPointerData来寻址元组。可以看到结构的总大小为48位。

Greenplum中假设每个页面能够存储的最大元组数为65536（64K），对于32K字节大小的页面来说，该值已经足够大，可以通过下面公式换算位图中的第n位bitmap_nth。

bitmap_nth=block_number * BLCKSZ + ip_posid

对于AO表的元组来说，也采用称为AOTupleId的48位结构来寻址元组，所存储的内容会有不同，由于篇幅限制，这里不做熬述。

位图在执行器中的表示

Greenplum中有种索引类型叫做位图索引，其属于索引的范畴，本文主要讲解执行器，所以不会涵盖位图索引的内容。这里只讲述执行器中位图的内存表示格式。

通过上面的映射关系，每个元组存在与否的信息可以通过一个比特位表示，通过下面的格式。

============================ |

BitWord0 : | T0 | T1 | T2 | T3|...| T63| |

------------------------------------------------- |

BitWord1: |T64|T64|...... |T127| | PAGE0 (WORDS_PER_PAGE个行）

------------------------------------------------- |

….. |

============================= |

============================ |

BitWord0 : | T0 | T1 | T2 | T3|...| T63| |

------------------------------------------------- |

BitWord1: |T64|T64|...... |T127| | PAGE1

------------------------------------------------- |

….. |

============================= |

其中Tn表示第n个元组是否存在，通过0或1表表示。位图会切分成多个页来存储，每个页面内又会分成多个行存储，每行称为位图的一个字（Word），用64位表示。当需要定位到第n个比特位时，先计算位图中的页号，然后在计算字号，最后是字内偏移号。

实现时，Greenplum考虑到了一种存储上的优化，对于很大的表，文件很大的情况下，文件页的数目会比较多，对应位图会占有比较大的内存空间。另外，如果一个文件页内几乎所有元组都命中，没有必要为每个元组都保留比特位。此时，只需要设置整个文件页的比特位为1，表示块内有元组命中。否则，如果文件页对应比特位为0，则跳过扫描对应文件页。这种存储方式称为位图的lossy存储或有损存储，因为lossy存储丢失了每个元组是否匹配的信息，但是减少了存储空间。

当位图中的位表示的是文件页的而不是元组，扫描时需要对文件页内的各个元组重新做一次检查判断其是否满足过滤条件，该检查叫做recheck。

实现时，每个位图页面的数据结构通过PagetableEntry实现。

typedef struct PagetableEntry

{

BlockNumber blockno; /* page number (hashtable key) */

bool ischunk; /* T = lossy storage, F = exact */

bool recheck; /* should the tuples be rechecked? */

tbm_bitmapword words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)];

} PagetableEntry;

ischunk用来表示位图页中的存储格式是否为lossy方式，即位信息对应的是元组还是文件页的。

对于非lossy存储格式，blockno记录的是对应文件页号。对于lossy存储格式，每个位图页可以标记PAGES_PER_CHUNK个文件页的信息，该大小定义为BLCKSZ / 32。PagetableEntry记录了连续PAGES_PER_CHUNK个文件页的标记信息，其中blockno记录了起始文件页块号。

基于位图扫描元组

基于位图扫描元组的工作是通过执行器节点BitmapHeapScan来完成的。由于历史原因，该节点不仅支持基于Heap表的扫描，也支持基于AO表和AOCO列存表的扫描。其基本流程就是从前往后遍历位图，基于当前位图页的类型：

·如果发现当前位图页为lossy存储，则根据blockno记录的文件页号读取所有元组的位置信息到记录到内存中。

·如果发现当前位图页不为lossy存储，则根据words字段存储的元组位置信息记录到内存中。

扫描时，根据是否recheck进行元组的重新过滤判断返回满足条件的元组。

位图上的AND与OR操作

对于如下的复杂查询

# explain select * from student where (sage = 10 OR sid = 20) AND (sage = 12 OR sid = 15);

QUERY PLAN

----------------------------------------------------------------------------------------------------

Gather Motion 3:1 (slice1; segments: 3) (cost=5915.01..17857.54 rows=39185 width=15)

-> Bitmap Heap Scan on student (cost=5915.01..17073.85 rows=13062 width=15)

Recheck Cond: (((sage = 12) OR (sid = 15)) AND ((sage = 10) OR (sid = 20)))

-> BitmapAnd (cost=5915.01..5915.01 rows=2097 width=0)

-> BitmapOr (cost=2862.77..2862.77 rows=81370 width=0)

-> Bitmap Index Scan on stu_sage_idx (cost=0.00..2838.99 ...)

Index Cond: (sage = 12)

-> Bitmap Index Scan on stu_sid_idx (cost=0.00..4.19 rows=1 width=0)

Index Cond: (sid = 15)

-> BitmapOr (cost=3051.99..3051.99 rows=86757 width=0)

-> Bitmap Index Scan on stu_sage_idx (cost=0.00..3028.20 ...)

Index Cond: (sage = 10)

-> Bitmap Index Scan on stu_sid_idx (cost=0.00..4.19 rows=1 width=0)

Index Cond: (sid = 20)

由于sage列和sid列上都创建有索引，查询优化器经过代价估算之后，采用先通过各自条件获取过滤条件对应的位图，然后位图间做OR运算，最后两个位图间再做AND运算得到最后的结果位图。再基于最后的结果位图进行Heap表扫描。

对于AND和OR操作，都是二元运算符，其输入参数称为左位图和右位图。运算时，每次各取一个左右位图页进行操作返回一个结果位图页。对于每一个左位图页和右位图页，存在下面可能四种情况：

1. 左位图页为lossy存储，右位图页为lossy存储

2. 左位图页为lossy存储，右位图页为非lossy存储

3. 左位图页为非lossy存储，右位图页为lossy存储

4. 左位图页为非lossy存储，右位图页为非lossy存储

运算的逻辑可以通过表格来表示

结束语

位图在Greenplum中被广泛使用，本文只对Greenplum执行器中的位图进行了简单介绍，包括位图的表示，基于位图的元组扫描，和位图上的运算AND和OR。对于位图这种索引类型，不在本章介绍的范围。通过本章的介绍，希望读者能够对Greenplum执行器中的位图有个初步认识，希望进一步了解代码的读者可以参阅如下目录和文件：

src/backend/access/bitmap

src/backend/executor/nodeBitmapAnd.c

src/backend/executor/nodeBitmapOr.c

src/backend/executor/nodeBitmapHeapscan.c