背景

为了让阿里云RDS PG以更低的成本、更高的性能支持用户海量数据画像的实时计算，在Greenplum分布式数据库内核中，我们引入了RoaringBitmap功能的插件。Greenplum roaring bitmap与业务场景 (类阿里云RDS PG varbitx, 应用于海量用户 实时画像和圈选、透视) 位图索引在数据库领域应用很广泛。传统位图索引通过判断一个整数对应位图bit位是否置1，来进行快速索引。32位操作系统下，整数范围最大为2^32-1，为构建该整数的位图结构，需要占用2^32/8/1024/1024=512M大小的内存空间，而在大多数情况下，一个整数集合构建好的bitmap，bitmap中元素稀疏程度较大，用512M内存来存储当前数据结构，显然是不可接受的。 RoaringBitmap被描述为压缩位图，其实现方式是将一个32位长度的整数分为高16位和低16位两部分。对于高16位，作为key被存储在keys[]中，而对于低16位，作为value被存储在containers[]中。key和value通过数组下标进行对应。keys被维护为一个有序数组，每次通过二分查找在O(logn)内完成高16位的索引。 对于低16位，可以分为两种实现。元素个数小于4096，直接存储16位数，即采用2字节大小的short结构进行存储。元素个数超过4096，采用1024个long来对65536个bit进行存储。

pic

原生功能

原生的Greenplum内核不带有RoaringBitmap插件，开源社区实现了该功能，从而使得Greenplum可以支持RoaringBitmap类型。但该版本对于多阶段的聚合，并没有将聚合做到计算节点，而是实现为在主节点gathermotion再聚合，从而导致聚合性能不佳。

  1. postgres=# explain select rb_cardinality(rb_and_agg(bitmap)) from t1;  
  2.                                        QUERY PLAN                                         
  3. ----------------------------------------------------------------------------------------  
  4.  Aggregate  (cost=1.05..1.07 rows=1 width=4)  
  5.    ->  Gather Motion 3:1  (slice1; segments: 3)  (cost=0.00..1.05 rows=1 width=1254608)  
  6.          ->  Seq Scan on t1  (cost=0.00..1.01 rows=1 width=1254608)  
  7. (3 rows)  
  9. Time: 0.727 ms

从SQL执行计划也可以看出，原生方式下的RoaringBitmap实现，采用的是主节点上的单阶段聚合，这也成为了我们可以进行性能优化的一个方面。

优化改进

我们针对聚合操作进行了优化并改进，使得聚合操作采用多阶段聚合的方式实现，进一步提升RoaringBitmap在阿里云RDS实际业务中的性能。改进后的具体实现逻辑如下：

pic

我们通过在从节点完成一阶段聚合操作，再由主节点完成二阶段聚合，从而充分利用从节点自身计算性能，采用多阶段方式，提高聚合操作性能。 改进后的执行计划为多阶段方式执行。

  1. postgres=# explain select RB_AND_AGG(bitmap) from t1;
  2.                                     QUERY PLAN
  3. -----------------------------------------------------------------------------------
  4.  Aggregate  (cost=1.08..1.09 rows=1 width=32)
  5.    ->  Gather Motion 3:1  (slice1; segments: 3)  (cost=1.01..1.06 rows=1 width=32)
  6.          ->  Aggregate  (cost=1.01..1.02 rows=1 width=32)
  7.                ->  Seq Scan on t1  (cost=0.00..1.01 rows=1 width=40)
  8. (4 rows)

性能测试1

  • 表结构
  1.  CREATE TABLE t1 (id integer, bitmap roaringbitmap);
  2.  INSERT INTO t1 SELECT GENERATE_SERIES(1,1000000),RB_BUILD(ARRAY[1,2,3,4,5,6,7,8,9,200]);
  • 测试结果

pic

  • 结果分析

主节点个数为1，从节点个数为3，相较于不采用多阶段聚合方式，性能提升基本在2-3倍，其中rb_and_agg原生环境下在主节点聚合所有数据，优化后效果明显。

性能测试2

为进一步说明ARRAY长度的大小不会使得改进后的方案性能降低，进行了第二轮性能测试。

  • 表结构
  1.  CREATE TABLE t1 (id integer, bitmap roaringbitmap);
  2.  INSERT INTO t1 SELECT GENERATE_SERIES(1,1000000),RB_BUILD(ARRAY(SELECT *FROM GENERATE_SERIES(1,10000)));
  • 测试结果

pic

  • 结果分析

主节点个数为1，从节点个数为3，相较于不采用多阶段聚合方式，性能提升基本在2-3倍。其中rb_and_agg与rb_and_cardinality_agg执行时间超过10分钟，为方便构建测试结果图，取10w毫秒。

部署方法

创建插件

  1. postgres=# create extension roaringbitmap;
  2. CREATE EXTENSION

创建测试表

  1. postgres=# create table t1 (id integer, bitmap roaringbitmap);
  2. NOTICE:  Table doesn't have 'DISTRIBUTED BY' clause -- Using column named 'id' as the Greenplum Database data distribution key for this table.
  3. HINT:  The 'DISTRIBUTED BY' clause determines the distribution of data. Make sure column(s) chosen are the optimal data distribution key to minimize skew.
  4. CREATE TABLE

插入测试数据

  1. postgres=# insert into t1 (select 1, rb_build(array[1,2,3,4,5,6,7,8,9,200]));
  2. INSERT 0 1

聚合函数使用测试

  1. postgres=# select rb_or_agg(bitmap) from t1;
  2.                                                                  rb_or_agg
  3. --------------------------------------------------------------------------------------------------------------------------------------------
  4.  :0\000\000\001\000\000\000\000\000\011\000\020\000\000\000\001\000\002\000\003\000\004\000\005\000\006\000\007\000\010\000\011\000\310\000
  5. (1 row)
  8. postgres=# select rb_or_agg(bitmap) from t1;
  9.                                                                  rb_or_agg
  10. --------------------------------------------------------------------------------------------------------------------------------------------
  11.  :0\000\000\001\000\000\000\000\000\011\000\020\000\000\000\001\000\002\000\003\000\004\000\005\000\006\000\007\000\010\000\011\000\310\000
  12. (1 row)
  14. postgres=# select rb_and_agg(bitmap) from t1;
  15.                                                                  rb_and_agg
  16. --------------------------------------------------------------------------------------------------------------------------------------------
  17.  :0\000\000\001\000\000\000\000\000\011\000\020\000\000\000\001\000\002\000\003\000\004\000\005\000\006\000\007\000\010\000\011\000\310\000
  18. (1 row)
  20. postgres=# select rb_xor_agg(bitmap) from t1;
  21.                                                                  rb_xor_agg
  22. --------------------------------------------------------------------------------------------------------------------------------------------
  23.  :0\000\000\001\000\000\000\000\000\011\000\020\000\000\000\001\000\002\000\003\000\004\000\005\000\006\000\007\000\010\000\011\000\310\000
  24. (1 row)
  26. postgres=# select rb_build_agg(id) from t1;
  27.                             rb_build_agg
  28. --------------------------------------------------------------------
  29.  :0\000\000\001\000\000\000\000\000\000\000\020\000\000\000\001\000
  30. (1 row)
  33. postgres=# select rb_or_cardinality_agg(bitmap) from t1;
  34.  rb_or_cardinality_agg
  35. -----------------------
  36.                     10
  37. (1 row)
  39. postgres=# select rb_and_cardinality_agg(bitmap) from t1;
  40.  rb_and_cardinality_agg
  41. ------------------------
  42.                      10
  43. (1 row)
  45. postgres=# select rb_xor_cardinality_agg(bitmap) from t1;
  46.  rb_xor_cardinality_agg
  47. ------------------------
  48.                      10
  49. (1 row)

总结

我们将Greenplum原生RoaringBitmap插件进行了优化，增加了对聚合操作的多阶段执行处理，提升了RoaringBitmap多阶段聚合操作的执行性能。