Postgresql源码（47）bitmapset原理

mingjie

发布于 2022-05-18 11:01:00

3650

发布于 2022-05-18 11:01:00

文章被收录于专栏：Postgresql源码分析

bitmapset在优化器、update、plpgsql中都有大量应用。bitmapset本身结构简单，代码量少，这里简单分析记录。

内存结构

bitmapset初始化后，在内存中是Bitmapset结构后跟n个uint32的结构，见下图：

typedef struct Bitmapset
{
	int			nwords;			/* number of words in array */
	bitmapword	words[FLEXIBLE_ARRAY_MEMBER];	/* really [nwords] */
} Bitmapset;

内存结构

在使用时，用到了柔型数组的技巧，在PG中有大量应用：sizeof(Bitmapset) == sizeof(int)，可以一次性申请好全部需要的内存，释放时也只需要一次即可。在找某一个uint32时，直接用word[x]即可。

常用API

集合运算比较简单，函数都在bitmapset.c中，下面是一些常用函数。

所有函数基本都遵循如下流程： 1、wordnum = x / 32 2、bitnum = x % 32 3、a->words[wordnum] & ((bitmapword) 1 << bitnum)

其他API

// 集合union计算
extern Bitmapset *bms_union(const Bitmapset *a, const Bitmapset *b);

// 集合相交计算
extern Bitmapset *bms_intersect(const Bitmapset *a, const Bitmapset *b);

// 集合差异计算
extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);

// 判断子集
extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);

// 计算两个集合的关系：相等、子集、有差异
extern BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b);

// x是不是在bitmap中
extern bool bms_is_member(int x, const Bitmapset *a);

// 判断是否重叠部分
extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);

// 判断重叠List
extern bool bms_overlap_list(const Bitmapset *a, const struct List *b);

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-05-17，如有侵权请联系 cloudcommunity@tencent.com 删除

api