数据库内核月报 - 2018 / 08

PgSQL · 最佳实践 · Greenplum RoaringBitmap多阶段聚合

背景

为了让阿里云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再聚合,从而导致聚合性能不佳。

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

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

优化改进

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

pic

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

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

性能测试1

  • 表结构
 CREATE TABLE t1 (id integer, bitmap roaringbitmap);
 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长度的大小不会使得改进后的方案性能降低,进行了第二轮性能测试。

  • 表结构
 CREATE TABLE t1 (id integer, bitmap roaringbitmap);
 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毫秒。

部署方法

创建插件

postgres=# create extension roaringbitmap;
CREATE EXTENSION

创建测试表

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

插入测试数据

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

聚合函数使用测试

postgres=# select rb_or_agg(bitmap) from t1;
                                                                 rb_or_agg
--------------------------------------------------------------------------------------------------------------------------------------------
 :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
(1 row)


postgres=# select rb_or_agg(bitmap) from t1;
                                                                 rb_or_agg
--------------------------------------------------------------------------------------------------------------------------------------------
 :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
(1 row)

postgres=# select rb_and_agg(bitmap) from t1;
                                                                 rb_and_agg
--------------------------------------------------------------------------------------------------------------------------------------------
 :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
(1 row)

postgres=# select rb_xor_agg(bitmap) from t1;
                                                                 rb_xor_agg
--------------------------------------------------------------------------------------------------------------------------------------------
 :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
(1 row)

postgres=# select rb_build_agg(id) from t1;
                            rb_build_agg
--------------------------------------------------------------------
 :0\000\000\001\000\000\000\000\000\000\000\020\000\000\000\001\000
(1 row)


postgres=# select rb_or_cardinality_agg(bitmap) from t1;
 rb_or_cardinality_agg
-----------------------
                    10
(1 row)

postgres=# select rb_and_cardinality_agg(bitmap) from t1;
 rb_and_cardinality_agg
------------------------
                     10
(1 row)

postgres=# select rb_xor_cardinality_agg(bitmap) from t1;
 rb_xor_cardinality_agg
------------------------
                     10
(1 row)

总结

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