Greenplum roaring bitmap与业务场景 (类阿里云RDS PG varbitx, 应用于海量用户 实时画像和圈选、透视)
摘要： 標簽 PostgreSQL , Greenplum , varbitx , roaring bitmap , pilosa , varbit , hll , 多階段聚合 背景 roaring bitmap是一個壓縮比很高同時性能不錯的BIT庫，被廣泛使用（例如Greenplum, ES, InfluxDB.
點此查看原文
標簽
PostgreSQL , Greenplum , varbitx , roaring bitmap , pilosa , varbit , hll , 多階段聚合
背景
roaring bitmap是一個壓縮比很高同時性能不錯的BIT庫，被廣泛使用（例如Greenplum, ES, InfluxDB......）：
Roaring bitmaps are compressed bitmaps which tend to outperform conventional compressed bitmaps such as WAH, EWAH or Concise. They are used by several major systems such as Apache Lucene and derivative systems such as Solr and Elasticsearch, Metamarkets' Druid, LinkedIn Pinot, Netflix Atlas, Apache Spark, OpenSearchServer, Cloud Torrent, Whoosh, InfluxDB, Pilosa, Bleve, Microsoft Visual Studio Team Services (VSTS), and eBay's Apache Kylin.
《Roaring Bitmap - A better compressed bitset》
https://github.com/RoaringBitmap/CRoaring
在PostgreSQL中內置了varbit的數據類型，阿里云在其基礎上擴展了對varbit的操作符：
《阿里云RDS for PostgreSQL varbitx插件與實時畫像應用場景介紹》
是的阿里云RDS PG支持以更低的成本、更高的性能支持海量畫像的實時計算：
《阿里云RDS PostgreSQL varbitx實踐 - 流式標簽 (閱后即焚流式批量計算) - 萬億級，任意標簽圈人，毫秒響應》
《基于 阿里云 RDS PostgreSQL 打造實時用戶畫像推薦系統(varbitx)》
《驚天性能！單RDS PostgreSQL實例 支撐 2000億 - 實時標簽透視案例》
對于Greenplum，同樣有社區的朋友貢獻的插件，讓Greenplum可以支持roaringbitmap類型。
開源代碼如下（感謝貢獻代碼的小伙伴）：
https://github.com/zeromax007/gpdb-roaringbitmap
（目前這個版本沒有將聚合做到計算節點，而是走了gather motion再聚合的方式，聚合性能不佳）。
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建議有興趣的同學可以改進一下 roaringbitmap for Greenplum 聚合代碼，改成多階段聚合，讓聚合先在計算節點做。
自定義分布式聚合的方法參考如下：
《PostgreSQL 10 自定義并行計算聚合函數的原理與實踐》
《Postgres-XC customized aggregate introduction》
《PostgreSQL aggregate function customize》
《Greenplum 最佳實踐 - 估值插件hll的使用(以及hll分式聚合函數優化)》
接下來簡單介紹一下roaringbitmap的安裝與功能點。
安裝
1、首先你需要安裝好greenplum。
2、然后你需要下載gpdb-roaringbitmap
git clone https://github.com/zeromax007/gpdb-roaringbitmap3、編譯gpdb-roaringbitmap
If $GPHOME is /usr/local/gpdb . gcc -march=native -O3 -std=c11 -Wall -Wpointer-arith -Wendif-labels -Wformat-security \ -fno-strict-aliasing -fwrapv -fexcess-precision=standard -fno-aggressive-loop-optimizations \ -Wno-unused-but-set-variable -Wno-address -fpic -D_GNU_SOURCE \ -I/usr/local/gpdb/include/postgresql/server \ -I/usr/local/gpdb/include/postgresql/internal \ -c -o roaringbitmap.o roaringbitmap.c 或如下，主要看你的頭文件在哪里 gcc -march=native -O3 -std=c11 -Wall -Wpointer-arith -Wendif-labels -Wformat-security \ -fno-strict-aliasing -fwrapv -fexcess-precision=standard -fno-aggressive-loop-optimizations \ -Wno-unused-but-set-variable -Wno-address -fpic -D_GNU_SOURCE \ -I/usr/local/gpdb/include/server \ -I/usr/local/gpdb/include/internal \ -c -o roaringbitmap.o roaringbitmap.c gcc -O3 -std=gnu99 -Wall -Wpointer-arith -Wendif-labels -Wformat-security \ -fno-strict-aliasing -fwrapv -fexcess-precision=standard -fno-aggressive-loop-optimizations \ -Wno-unused-but-set-variable -Wno-address -fpic -shared --enable-new-dtags \ -o roaringbitmap.so roaringbitmap.o4、將so文件拷貝到所有gpdb節點(所有master, slave, segment, mirror等)的軟件目錄對應的lib目錄中.
cp ./roaringbitmap.so /usr/local/gpdb/lib/postgresql/5、在MASTER節點，連接到需要使用roaringbitmap的DB中，執行如下SQL，安裝對應的類型，操作符，函數等。
psql -f ./roaringbitmap.sql使用DEMO
1、建表，使用roaringbitmap數據類型
CREATE TABLE t1 (id integer, bitmap roaringbitmap);2、使用rb_build生成roaringbitmap的數據(輸入為數組，輸出為roaringbitmap。含義：數組位置對應的bit值設置為1)。
INSERT INTO t1 SELECT 1,RB_BUILD(ARRAY[1,2,3,4,5,6,7,8,9,200]); -- 將輸入的多條記錄的值對應位置的BIT值設置為1，最后聚合為一個roaringbitmap INSERT INTO t1 SELECT 2,RB_BUILD_AGG(e) FROM GENERATE_SERIES(1,100) e;3、兩個roaringbitmap的BIT計算（OR, AND, XOR, ANDNOT）。andnot表示第一個參數與第二個參數的NOT進行AND操作，等同于andnot(c1,c2)==and(c1, not(c2))
SELECT RB_OR(a.bitmap,b.bitmap) FORM (SELECT bitmap FROM t1 WHERE id = 1) AS a, (SELECT bitmap FROM t1 WHERE id = 2) AS b;4、一些聚合操作，并生成新的roaringbitmap (OR, AND, XOR, BUILD)
SELECT RB_OR_AGG(bitmap) FROM t1; SELECT RB_AND_AGG(bitmap) FORM t1; SELECT RB_XOR_AGG(bitmap) FROM t1; SELECT RB_BUILD_AGG(e) FROM GENERATE_SERIES(1,100) e;5、Cardinality，即roaringbitmap中包含多少個位置為1的BIT位。
SELECT RB_CARDINALITY(bitmap) FROM t1;6、從roaringbitmap返回位置為1的BIT的下標（位置值）。
SELECT RB_ITERATE(bitmap) FROM t1 WHERE id = 1; postgres=# select rb_iterate(rb_build('{1,4,100}')); rb_iterate ------------ 1 4 100 (3 rows)7、一些bit設置操作
postgres=# select rb_iterate(rb_flip(rb_build('{1,2,3,100,4,5}'),7,10)); rb_iterate ------------ 1 2 3 4 5 7 8 9 100 (9 rows)內置計算函數說明
List of functions Schema | Name | Result data type | Argument data types | Type ------------+------------------------+------------------+--------------------------------------------+-------- public | rb_and | roaringbitmap | roaringbitmap, roaringbitmap | normal public | rb_and_cardinality | integer | roaringbitmap, roaringbitmap | normal public | rb_andnot | roaringbitmap | roaringbitmap, roaringbitmap | normal public | rb_andnot_cardinality | integer | roaringbitmap, roaringbitmap | normal public | rb_build | roaringbitmap | integer[] | normal public | rb_cardinality | integer | roaringbitmap | normal public | rb_equals | boolean | roaringbitmap, roaringbitmap | normal public | rb_flip | roaringbitmap | roaringbitmap, integer, integer | normal public | rb_intersect | boolean | roaringbitmap, roaringbitmap | normal public | rb_is_empty | boolean | roaringbitmap | normal public | rb_iterate | SETOF integer | roaringbitmap | normal public | rb_maximum | integer | roaringbitmap | normal public | rb_minimum | integer | roaringbitmap | normal public | rb_or | roaringbitmap | roaringbitmap, roaringbitmap | normal public | rb_or_cardinality | integer | roaringbitmap, roaringbitmap | normal public | rb_rank | integer | roaringbitmap, integer | normal public | rb_remove | roaringbitmap | roaringbitmap, integer | normal public | rb_xor | roaringbitmap | roaringbitmap, roaringbitmap | normal public | rb_xor_cardinality | integer | roaringbitmap, roaringbitmap | normal| rb_build | integer[] | roaringbitmap | Build a roaringbitmap tuple from integer array. | rb_build('{1,2,3,4,5}') |
| rb_and | roraingbitmap,roaringbitmap | roaringbitmap | Two roaringbitmap tuples and calculation. | rb_and(rb_build('{1,2,3}'),rb_build('{3,4,5}')) |
| rb_or | roraingbitmap,roaringbitmap | roaringbitmap | Two roaringbitmap tuples or calculation. | rb_or(rb_build('{1,2,3}'),rb_build('{3,4,5}')) |
| rb_xor | roraingbitmap,roaringbitmap | roaringbitmap | Two roaringbitmap tuples xor calculation. | rb_xor(rb_build('{1,2,3}'),rb_build('{3,4,5}')) |
| rb_andnot | roraingbitmap,roaringbitmap | roaringbitmap | Two roaringbitmap tuples andnot calculation. | rb_andnot(rb_build('{1,2,3}'),rb_build('{3,4,5}')) |
| rb_cardinality | roraingbitmap | integer | Retrun roaringbitmap tuple's cardinality. | rb_cardinality(rb_build('{1,2,3,4,5}')) |
| rb_and_cardinality | roraingbitmap,roaringbitmap | integer | Two roaringbitmap tuples and calculation, return cardinality. | rb_and_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}')) |
| rb_or_cardinality | roraingbitmap,roaringbitmap | integer | Two roaringbitmap tuples or calculation, return cardinality. | rb_or_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}')) |
| rb_xor_cardinality | roraingbitmap,roaringbitmap | integer | Two roaringbitmap tuples xor calculation, return cardinality. | rb_xor_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}')) |
| rb_andnot_cardinality | roraingbitmap,roaringbitmap | integer | Two roaringbitmap tuples andnot calculation, return cardinality. | rb_andnot_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}')) |
| rb_is_empty | roraingbitmap | boolean | Check if roaringbitmap tuple is empty. | rb_is_empty(rb_build('{1,2,3,4,5}')) |
| rb_equals | roraingbitmap,roaringbitmap | boolean | Check two roaringbitmap tuples are equal. | rb_equals(rb_build('{1,2,3}'),rb_build('{3,4,5}')) |
| rb_intersect | roraingbitmap,roaringbitmap | boolean | Check two roaringbitmap tuples are intersect. | rb_intersect(rb_build('{1,2,3}'),rb_build('{3,4,5}')) |
| rb_remove | roraingbitmap,integer | roraingbitmap | Remove the specified offset from roaringbitmap tuple. | rb_remove(rb_build('{1,2,3}'),3) |
| rb_flip | roraingbitmap,integer,integer | roraingbitmap | Flip the specified offsets range (not include the end) from roaringbitmap tuple. | rb_flip(rb_build('{1,2,3}'),7,10) -- 翻轉BIT位置為7到10（不含10）的BIT值 |
| rb_minimum | roraingbitmap | integer | Return the smallest offset in roaringbitmap tuple. Return UINT32_MAX if the bitmap tuple is empty. | rb_minimum(rb_build('{1,2,3}')) -- 返回該roaringbitmap中bit值設置為1的最小位置 |
| rb_maximum | roraingbitmap | integer | Return the greatest offset in roaringbitmap tuple. Return 0 if the bitmap tuple is empty. | rb_maximum(rb_build('{1,2,3}')) -- 返回該roaringbitmap中bit值設置為1的最大位置 |
| rb_rank | roraingbitmap,integer | integer | Return the number of offsets that are smaller or equal to the specified offset. | rb_rank(rb_build('{1,2,3}'),3) -- BIT位置小于等于N的BIT中，有多少個bit位置被設置為1 |
| rb_iterate | roaringbitmap | SETOF integer | Bitmap to SETOF integer | rb_iterate(rb_build('{1,2,3,100}')) |
內置聚合函數說明
List of functions Schema | Name | Result data type | Argument data types | Type --------+-------------------------+---------------------------+--------------------------------------------------+-------- public | rb_and_agg | roaringbitmap | roaringbitmap | agg public | rb_and_cardinality_agg | integer | roaringbitmap | agg public | rb_build_agg | roaringbitmap | integer | agg public | rb_or_agg | roaringbitmap | roaringbitmap | agg public | rb_or_cardinality_agg | integer | roaringbitmap | agg public | rb_xor_agg | roaringbitmap | roaringbitmap | agg public | rb_xor_cardinality_agg | integer | roaringbitmap | agg| rb_build_agg | integer | roraingbitmap | Build a roaringbitmap tuple from a integer set. | rb_build_agg(1) |
| rb_or_agg | roraingbitmap | roraingbitmap | Or Aggregate calculations from a roraingbitmap set. | rb_or_agg(rb_build('{1,2,3}')) |
| rb_and_agg | roraingbitmap | roraingbitmap | And Aggregate calculations from a roraingbitmap set. | rb_and_agg(rb_build('{1,2,3}')) |
| rb_xor_agg | roraingbitmap | roraingbitmap | Xor Aggregate calculations from a roraingbitmap set. | rb_xor_agg(rb_build('{1,2,3}')) |
| rb_or_cardinality_agg | roraingbitmap | integer | Or Aggregate calculations from a roraingbitmap set, return cardinality. | rb_or_cardinality_agg(rb_build('{1,2,3}')) |
| rb_and_cardinality_agg | roraingbitmap | integer | And Aggregate calculations from a roraingbitmap set, return cardinality. | rb_and_cardinality_agg(rb_build('{1,2,3}')) |
| rb_xor_cardinality_agg | roraingbitmap | integer | Xor Aggregate calculations from a roraingbitmap set, return cardinality. | rb_xor_cardinality_agg(rb_build('{1,2,3}')) |
例子
《驚天性能！單RDS PostgreSQL實例 支撐 2000億 - 實時標簽透視案例》
背景：
有20億個BIT，有幾千萬的標簽。意味著有幾千萬行，每一行有20億個BIT組成的roaringbitmap。
求任意標簽組合的cardinate. (rb_???_cardinality_agg)
設計：
數據按標簽字段分布：
create table tbl (tagid int primary key, bitmap roaringbitmap) distributed by (tagid) ;SQL：
1、求合并的BIT中有多少為1的BIT
select rb_and_cardinality_agg(bitmap) from tbl where tagid in (?,......?);2、求合并的BIT，對應的BIT位置
select RB_ITERATE(rb) from (select rb_and_agg(bitmap) as rb from tbl where tagid in(1,2,3)) t;加速
由于目前roaringbitmap gp這個插件沒有支持agg中的prefunc，所以聚合是收集到master節點操作的，這個勢必影響性能。
postgres=# explain select rb_and_cardinality_agg(bitmap) from tbl where tagid in (1,2,3,4,5,6,7,8); QUERY PLAN ----------------------------------------------------------------------------------- Aggregate (cost=0.04..0.06 rows=1 width=4) -> Gather Motion 3:1 (slice1; segments: 3) (cost=0.00..0.04 rows=1 width=32) -> Seq Scan on tbl (cost=0.00..0.00 rows=1 width=32) Filter: tagid = ANY ('{1,2,3,4,5,6,7,8}'::integer[]) (4 rows) postgres=# explain select RB_ITERATE(rb) from (select rb_and_agg(bitmap) as rb from tbl where tagid in(1,2,3)) t; QUERY PLAN ----------------------------------------------------------------------------------------- Result (cost=0.04..0.07 rows=3 width=32) -> Aggregate (cost=0.04..0.06 rows=1 width=32) -> Gather Motion 3:1 (slice1; segments: 3) (cost=0.00..0.04 rows=1 width=32) -> Seq Scan on tbl (cost=0.00..0.00 rows=1 width=32) Filter: tagid = ANY ('{1,2,3}'::integer[]) (5 rows)為了加速，務必要實現這些聚合函數的prefunc。
Greenplum支持的兩種聚合運算模式：
1. 如果只配置了sfunc，則相關數據全部收集到master節點，在master節點對所有數據依條加上sfunc的結果(第一次可選為initcond)輸入給sfunc計算，直到所有數據都跑完sfunc，最后如果設置了finalfunc，則計算并得到最終結果。
2. 如果同時配置了sfunc和prefunc，則在segment節點并行完成sfunc，然后將segment節點執行的結果發給master，在master調用prefunc進行再次聚合，輸出結果，如果配置了finalfunc，則這個結果再給finalfunc執行并輸出最終結果。
優化例子：
//bitmap and trans PG_FUNCTION_INFO_V1(rb_and_trans_pre); Datum rb_and_trans_pre(PG_FUNCTION_ARGS); Datum rb_and_trans_pre(PG_FUNCTION_ARGS) { MemoryContext aggctx; roaring_bitmap_t *r1; roaring_bitmap_t *r2; // We must be called as a transition routine or we fail. if (!AggCheckCallContext(fcinfo, &aggctx)) ereport(ERROR, (errcode(ERRCODE_DATA_EXCEPTION), errmsg("rb_and_trans outside transition context"))); // Is the first argument a NULL? if (PG_ARGISNULL(0)) { r1 = setup_roaringbitmap(aggctx); } else { r1 = (roaring_bitmap_t *) PG_GETARG_POINTER(0); } // Is the second argument non-null? if (!PG_ARGISNULL(1)) { r2 = (roaring_bitmap_t *) PG_GETARG_POINTER(1); if (PG_ARGISNULL(0)) { r1 = roaring_bitmap_copy(r2); } else { roaring_bitmap_and_inplace(r1, r2); } roaring_bitmap_free(r2); } PG_RETURN_POINTER(r1); } CREATE OR REPLACE FUNCTION rb_and_trans_pre(internal, internal) RETURNS internal AS 'roaringbitmap.so', 'rb_and_trans_pre' LANGUAGE C IMMUTABLE; CREATE AGGREGATE rb_and_agg(roaringbitmap)( SFUNC = rb_and_trans, PREFUNC = rb_and_trans_pre, STYPE = internal, FINALFUNC = rb_serialize );實現prefunc后，執行計劃就會變成這樣的，先在計算節點執行一階段聚合，然后再到master執行第二階段的聚合，效率明顯提升。
postgres=# explain select RB_ITERATE(rb) from (select rb_and_agg(bitmap) as rb from tbl where tagid in(1,2,3)) t;QUERY PLAN ----------------------------------------------------------------------------------------Result (cost=0.07..0.10 rows=3 width=32)-> Aggregate (cost=0.07..0.08 rows=1 width=32)-> Gather Motion 3:1 (slice1; segments: 3) (cost=0.01..0.06 rows=1 width=4)-> Aggregate (cost=0.01..0.01 rows=1 width=4)-> Seq Scan on tbl (cost=0.00..0.00 rows=1 width=32)Filter: tagid = ANY ('{1,2,3}'::integer[]) (6 rows)postgres=# explain select rb_and_agg(bitmap) from tbl where tagid in (1,2,3,4,5,6,7,8);QUERY PLAN ----------------------------------------------------------------------------------Aggregate (cost=0.07..0.08 rows=1 width=32)-> Gather Motion 3:1 (slice1; segments: 3) (cost=0.01..0.06 rows=1 width=4)-> Aggregate (cost=0.01..0.01 rows=1 width=4)-> Seq Scan on tbl (cost=0.00..0.00 rows=1 width=32)Filter: tagid = ANY ('{1,2,3,4,5,6,7,8}'::integer[]) (5 rows)小結
gpdb-roaringbitmap是一個很好的插件，可以幫助用戶高效的實現多組標簽的人群圈選。
目前需要實現prefunc來支持多階段聚合，否則只能gather到master去聚合。文中有例子。
參考
《PostgreSQL (varbit, roaring bitmap) VS pilosa(bitmap庫)》
《Roaring Bitmap - A better compressed bitset》
《阿里云RDS PostgreSQL varbitx實踐 - 流式標簽 (閱后即焚流式批量計算) - 萬億級，任意標簽圈人，毫秒響應》
《基于 阿里云 RDS PostgreSQL 打造實時用戶畫像推薦系統(varbitx)》
《阿里云RDS for PostgreSQL varbitx插件與實時畫像應用場景介紹》
《Greenplum 最佳實踐 - 估值插件hll的使用(以及hll分式聚合函數優化)》
《PostgreSQL 10 自定義并行計算聚合函數的原理與實踐》
《Postgres-XC customized aggregate introduction》
《PostgreSQL aggregate function customize》
https://github.com/RoaringBitmap/CRoaring
https://github.com/zeromax007/gpdb-roaringbitmap
《驚天性能！單RDS PostgreSQL實例 支撐 2000億 - 實時標簽透視案例》
掃描二維碼獲取更多消息：?
總結
以上是生活随笔為你收集整理的Greenplum roaring bitmap与业务场景 (类阿里云RDS PG varbitx, 应用于海量用户 实时画像和圈选、透视)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 车联网上云最佳实践（二）
- 下一篇： PostgreSQL 查询涉及分区表过多