Bitmap 的数据库持久化实现
刘鑫
Bitmap 的数据库持久化实现
Bitmap 是一个常见的数据类型，常用于优化大量数值的存储和查询。这个概念对于数据 库程序员应该不陌生，Oracle 等数据库通过这种技术优化查询。通常程序员会在一些算法 或数据结构书籍上读到以 C 语言 char* 实现的 bitmap 。这里，我们考虑一个在数据库中 存储的 bitmap 实现。
PG 上的数据结构实现
bitmap 的实现不难，PostgreSQL 中提供了 bitstring 类型，可以直接存储位串。但是单行 bitstring 能提供的数据长度终归有限。为了存储和性能的需要，我们将其设计为一个表。 通过索引值将 bitmap 分片为 bitstring 集。
create table bitmap(idx bigint, segment bit(32));
分析
计算时我们将一个bitmap表视为一个完整的bitmap数据集，设 segment 的宽度为 w ，索引 值为 i 。将第行的 idx 置为0，则第 i 个索引行上的第 b 位对应整个 bitmap 的第 b+i*w 位。逆推之，bitmap 第 x 位为 x div w 行，第 x%w 位。
因为数据分行存储，位计算操作也需要重新定义，要考虑跨界定位问题。Postgres 的 bit 本身支持左移右移操作。这点并不复杂。可以利用掩码技巧将计算参数分解为区片。具体算 法几乎与 C 语言版本一致。当然针对一些有规则操作时，可以充分的利用 SQL 和 PLSQL 的语法特色进行简化。
实例
覆盖统计
详细内容介绍见下一段中的链接。这里简单介绍一下：每个数据样本是一个由大量一维区间 值组成的文本。每一行是一个（起点，终点）区间。要计算二到N个样本件的覆盖率。而数 据本身是未经整理的，可能有重复。
事实上，这个例子是我最初着手实现 bitmap 的起因。可以说 bitmap 可以直接优化此类问 题，首先bitmap以至少8倍以上的比例节省存储空间（以 c 语言 char* 每字节存储位置状 态来计）。而空间缩减后对查询性能也有直接提升。
这个应用的操作非常好实现，将收集来的数据区间段(s, e)转换为二进制数 2^s+2^(s+1)+...+2^e ，即从 s 到 e 之间都为1的二进制位串。然后与整个 bitmap 做或 运算。示例代码如下：
create or replace function segment_over(s bigint, e bigint) returns void as $$
declare
sidx bigint;
eidx bigint;
d_data bit(32) := 4294967295::bit(32); -- pow(2, 32) -1
begin
if currval('bitmap_idx_seq') < (e/32)+1 then
for i in currval('bitmap_idx_seq')..e/32+1 loop
insert into bitmap(segment) select 0::bit(32);
end loop;
end if;
sidx := s/32;
eidx := e/32;
if sidx = eidx then
update bitmap set segment = (d_data << cast((32-e%32) as int))&(d_data >> cast((s%32) as int)) where idx = sidx;
else
update bitmap set segment = segment | (d_data >> cast((s%32) as int)) where idx = sidx;
update bitmap set segment = d_data where sidx < idx and idx < eidx;
update bitmap set segment = segment | (d_data << cast((e%32) AS INT)) where idx = eidx;
end if;
end;
$$ language plpgsql;
优化分析
此示例中，segment_over 操作并未做任何深度优化，仅仅是将前述的思路直接实现出来而 已。实际上根据业务，我们还可以进一步的提高操作效率。
例如，由于覆盖度操作是在数据区迭加或操作，单向的填充动作，可以将已覆盖区间直接压 缩掉（这需要将 idx 字段扩展为起点和终点一对数据，或者通过触发器机制同步一个查询 表）。
再例如，前例中我们的 segment 长度为32，idx 是一个 bigint 类型。这对于海量数据比 较有效，不过如果总样本量较小，完全可以用 integer ，这样可以减少很多转型操作。
在 segment_over 中，我写了一个防出错的探测代码，如果索引值超出了初始化范围，会扩 展 bitmap 表。但是实际上很多应用，其总数据量是有明确上界的。此时可以去掉这部分代 码，使用一个一次性的初始化代码，例如下面这样：
create or replace function init(len bigint) returns void as $$
declare
i bigint;
begin
truncate table bitmap restart identity;
insert into bitmap(idx, segment) select 0, 0::bit(32);
if len/32 < 1 then
return;
end if;
for i in 1..len/32 loop
insert into bitmap(segment) select 0::bit(32);
end loop;
if len%32 > 0 then
insert into bitmap(segment) select 0::bit(32);
end if;
end;
$$ language plpgsql;
将 segment 的宽度调整为略大于覆盖区间长度期望值的数值，可以减少对中间区间的覆盖 操作，也有优化读写效率的可能。
数据库实现的动机
使用数据库存储 bitmap ，可以避免海量长度 bitmap 超出内存容量的情况，是一个比较经 济的实现方式，特别是在机器不够强劲，或者没有条件部署云或网格集群的场景。只要熟练 数据库层开发即可。
由于 Postgres 中已经实现了完备的并发访问、数据备份和查询等功能，可以避免自己开发 文件型 bitmap 所需要考虑以上问题，带来的开发成本。轻松可以满足 OLAP 的需求，在线 随时查询覆盖情况。
合理的使用数据库功能，可以有效的降低使用和开发成本，这种组件式的开发和集成方式， 对于当下追求灵活、高性价比和可持续性的 IT 产业理念，是契合的。
……
劉鑫
March.Liu
Zoom.Quiet
> 以下是基于数据覆盖的一个初步讨论，实用中，位映射有广泛的应用领域，也有大量的算法实现需求。在经过初步的推演后，我发现这不是可以一蹴而就的。所以先给出一个简单的实现和应用算法讨论。
>
在部门的 土拨鼠时间演示过，
基本功能都可以看到，
但是当前俺就是没有反应过来，这一功能簇，最适合在什么场景中使用...?
--
http://zoomquiet.org 人生苦短? Pythonic!
Free as in Freedom! 哲思社区:http://zeuux.com
刘鑫
2009/10/8 刘鑫 <marc...@gmail.com>:
> 以下是基于数据覆盖的一个初步讨论，实用中，位映射有广泛的应用领域，也有大量的算法实现需求。在经过初步的推演后，我发现这不是可以一蹴而就的。所以先给出一个简单的实现和应用算法讨论。在部门的 土拨鼠时间演示过，
>
基本功能都可以看到，
但是当前俺就是没有反应过来，这一功能簇，最适合在什么场景中使用...?
例如，搜索引擎，记录哪些URL爬过。
网络安全数据库，记录安全和不安全的URL（Hash 化的）。
一个比较有名的实例，就是布隆过滤器。
还有就是在基因研究方面有非常广泛的应用，例如前段时间Perl中文社区曾经讨论过这个问题:
https://groups.google.com/group/perlchina/browse_thread/thread/a019034ad1dc584e?hl=zh-CN
--
光见贼吃肉，没见贼挨打。
……
劉鑫
March.Liu