全部產品
Search

搜尋本產品

    AnalyticDB：Roaring Bitmap

    文件中心

    AnalyticDB：Roaring Bitmap

    更新時間：Jun 19, 2024

    Roaring Bitmap是一種高效的資料結構，與Bitmap相比，具備更高的處理效能且佔用更少的記憶體空間。適合集合操作（交集、並集和差集）、去重等計算情境，常用於使用者畫像、個人化推薦、精準營銷等業務情境。

    背景資訊

    位元影像（BitMap）是一種常用的資料結構，位元影像為每個列所有可能的值建立一個單獨的0和1的系列，每個位（bit）對應一個資料行是否存在對應的值。傳統的位元影像會佔用大量記憶體，一般需要對位元影像進行壓縮處理。Roaring Bitmap是一種高效優秀的位元影像壓縮演算法，目前已被廣泛應用在各語言和各巨量資料平台上。

    Roaring Bitmap壓縮演算法簡介

    Roaring Bitmap資料結構是將32位整型（INT）數劃分為高16位和低16位。其中，高16位被劃分為多個資料區塊（Chunk），低16位使用一個容器（Container）來存放，因此每個資料區塊最多能夠儲存2^16個整數。Roaring Bitmap將這些容器儲存在一個動態數組中，按照高16位進行排序，可以通過高16位二分尋找快速定位對應的容器。根據資料特徵，使用三種不同的容器進行儲存： 

    • 數組容器（Array Container）：儲存稀疏的資料，整數較為分散且不連續的情況。若容器裡的最巨量資料小於4096，則使用數組容器來儲存值。

    • 位元影像容器（Bitmap Container）：儲存稠密的資料，有很多連續的整數存在的情況。若容器裡的最巨量資料大於等於4096，則使用位元影像容器來儲存值。

    • 運行容器（Run Container）： 儲存連續值較多的資料。Run Container只有在其儲存空間大小同時小於Array Container和Bitmap Container時才會被使用。 

    採用這種儲存結構，Roaring Bitmap極大地提高了資料的壓縮率，並且可以快速檢索一個特定的值。在做位元影像計算（AND，OR，XOR）時，Roaring Bitmap提供了相應的演算法來高效地實現在三種容器之間的運算。使得Roaring Bitmap無論在儲存和計算效能上都變得優秀。

    更多關於Roaring Bitmap的介紹資訊，請參見Roaring Bitmap官方網站。

    注意事項

    僅V6.3.8.9及以上版本支援使用Roaring Bitmap。如何查看執行個體核心版本，請參見查看核心小版本。

    使用Roaring Bitmap位元影像計算

    安裝外掛程式

    使用Roaring Bitmap位元影像計算功能之前，您需要在AnalyticDB for PostgreSQL執行個體中外掛程式管理中安裝Roaring Bitmap外掛程式。具體操作，請參見安裝、升級與卸載外掛程式。

    建立表

    建立帶有Roaring Bitmap資料類型的表。

    CREATE TABLE t1 (id integer, bitmap roaringbitmap);

    插入資料

    使用rb_build函數插入Roaring Bitmap的資料。

    --數組位置對應的bit值為1。
INSERT INTO t1 SELECT 1,RB_BUILD(ARRAY[1,2,3,4,5,6,7,8,9,200]);
--將輸入的多條記錄的值對應位置的bit值設定為1，最後彙總為一個Roaring Bitmap。 
INSERT INTO t1 SELECT 2,RB_BUILD_AGG(e) FROM GENERATE_SERIES(1,100) e;

    查詢資料

    從Roaring Bitmap中返回位置為1的bit下標（位置值）。

    SELECT RB_ITERATE(bitmap) FROM t1 WHERE id = 1;

    更多位元影像計算樣本如下。

    • Bitmap計算（OR、AND、XOR、ANDNOT）。

      SELECT RB_OR(a.bitmap,b.bitmap) FROM (SELECT bitmap FROM t1 WHERE id = 1) AS a,(SELECT bitmap FROM t1 WHERE id = 2) AS b;

    • Bitmap彙總計算（OR、AND、XOR、BUILD），並產生新的Roaring Bitmap類型。

      SELECT RB_OR_AGG(bitmap) FROM t1;
SELECT RB_AND_AGG(bitmap) FROM t1;
SELECT RB_XOR_AGG(bitmap) FROM t1;
SELECT RB_BUILD_AGG(e) FROM GENERATE_SERIES(1,100) e;

    • 統計基數（Cardinality），即統計Roaring Bitmap中包含多少個位置為1的bit位。

      SELECT RB_CARDINALITY(bitmap) FROM t1;

    Bitmap函數列表

    函數名

    輸入

    輸出

    描述

    樣本

    rb_build

    integer[]

    roaringbitmap

    通過數組建立一個Bitmap。

    rb_build('{1,2,3,4,5}')

    rb_and

    roaringbitmap,roaringbitmap

    roaringbitmap

    And計算。

    rb_and(rb_build('{1,2,3}'),rb_build('{3,4,5}'))

    rb_or

    roaringbitmap,roaringbitmap

    roaringbitmap

    Or計算。

    rb_or(rb_build('{1,2,3}'),rb_build('{3,4,5}'))

    rb_xor

    roaringbitmap,roaringbitmap

    roaringbitmap

    Xor計算。

    rb_xor(rb_build('{1,2,3}'),rb_build('{3,4,5}'))

    rb_andnot

    roaringbitmap,roaringbitmap

    roaringbitmap

    AndNot計算。

    rb_andnot(rb_build('{1,2,3}'),rb_build('{3,4,5}'))

    rb_cardinality

    roaringbitmap

    integer

    統計基數。

    rb_cardinality(rb_build('{1,2,3,4,5}'))

    rb_and_cardinality

    roaringbitmap,roaringbitmap

    integer

    And計算並返回基數。

    rb_and_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}'))

    rb_or_cardinality

    roaringbitmap,roaringbitmap

    integer

    Or計算並返回基數。

    rb_or_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}'))

    rb_xor_cardinality

    roaringbitmap,roaringbitmap

    integer

    Xor計算並返回基數。

    rb_xor_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}'))

    rb_andnot_cardinality

    roaringbitmap,roaringbitmap

    integer

    AndNot計算並返回基數。

    rb_andnot_cardinality(rb_build('{1,2,3}'),rb_build('{3,4,5}'))

    rb_is_empty

    roaringbitmap

    boolean

    判斷是否為空白的Bitmap。

    rb_is_empty(rb_build('{1,2,3,4,5}'))

    rb_equals

    roaringbitmap,roaringbitmap

    boolean

    判斷兩個Bitmap是否相等。

    rb_equals(rb_build('{1,2,3}'),rb_build('{3,4,5}'))

    rb_intersect

    roaringbitmap,roaringbitmap

    boolean

    判斷兩個Bitmap是否相交。

    rb_intersect(rb_build('{1,2,3}'),rb_build('{3,4,5}'))

    rb_remove

    roaringbitmap,integer

    roaringbitmap

    從Bitmap移除特定的Offset。

    rb_remove(rb_build('{1,2,3}'),3)

    rb_flip

    roaringbitmap,integer

    roraingbitmap

    翻轉Bitmap中特定的Offset。

    rb_flip(rb_build('{1,2,3}'),3)

    rb_flip

    roaringbitmap,integer,integer

    roaringbitmap

    翻轉Bitmap中特定的Offset段。

    rb_flip(rb_build('{1,2,3}'),2,3)

    rb_minimum

    roaringbitmap

    integer

    返回Bitmap中最小的Offset，如果Bitmap為空白則返回-1。

    rb_minimum(rb_build('{1,2,3}'))

    rb_maximum

    roaringbitmap

    integer

    返回Bitmap中最大的Offset，如果Bitmap為空白則返回0。

    rb_maximum(rb_build('{1,2,3}'))

    rb_rank

    roaringbitmap,integer

    integer

    返回Bitmap中小於等於指定Offset的基數。

    rb_rank(rb_build('{1,2,3}'),3)

    rb_iterate

    roaringbitmap

    setof integer

    返回Offset List。

    rb_iterate(rb_build('{1,2,3}'))

    rb_contains

    roaringbitmap, integer

    bool

    判斷Bitmap是否包含特定的Offset。

    rb_contains(rb_build('{1,2,3}'),1)

    rb_contains

    roaringbitmap,integer,integer

    bool

    判斷Bitmap是否包含特定的Offset段（某個範圍）。

    rb_contains(rb_build('{1,2,3}'),rb_build('{3,4,5}'))

    rb_contains

    roaringbitmap, roaringbitmap

    bool

    判斷Bitmap是否包含另外一個bitmap。

     rb_contains(rb_build('{1,2,3}'),rb_build('{3,4,5}'))

    rb_becontained

    integer, roaringbitmap

    bool

    判斷特定的Offset是否被Bitmap包含。

    rb_becontained(1, rb_build('{1,2,3}'))

    rb_becontained

    roaringbitmap,roaringbitmap

    bool

    判斷Bitmap是否被另外一個包含。

    rb_becontained(rb_build('{1}'), rb_build('{1,2,3}'))

    rb_add

    roaringbitmap, integer

    roaringbitmap

    添加特定的Offset到Bitmap。

    rb_add(rb_build('{1,2,3,4}'), 5)

    rb_add_2

    integer, roaringbitmap

    roaringbitmap

    Add a specific offset to roaringbitmap.

    rb_add_2(5, rb_build('{1,2,3,4}'))

    rb_add

    roaringbitmap,integer, integer

    roaringbitmap

    添加特定的Offset段到Bitmap。

    rb_add(rb_build('{1,2,3,4}'), 6,8)

    rb_remove

    roaringbitmap,integer, integer

    roaringbitmap

    從Bitmap移除特定的Offset。

    rb_remove(rb_build('{1,2,3,4,6,7,8}'), 6,8)

    rb_jaccard_index

    roaringbitmap,roaringbitmap

    float8

    計算兩個Bitmap之間的jaccard相似係數。

    rb_jaccard_index(rb_build('{1,2,3,4}'), rb_build('{1,2}'))

    rb_to_array

    roaringbitmap

    integer[]

    Bitmap轉數組。

    rb_to_array(rb_build('{1,2,3,4}'))

    rb_iterate_decrement

    roaringbitmap

    integer[]

    返回Offset List（從大到小）。

    rb_iterate_decrement(rb_build('{1,2,3,4}'))

    Bitmap彙總函式列表

    彙總函式名

    輸入

    輸出

    描述

    樣本

    rb_build_agg

    integer

    roaringbitmap

    將Offset彙總成Bitmap。

    rb_build_agg(1)

    rb_or_agg

    roaringbitmap

    roaringbitmap

    Or彙總計算。

    rb_or_agg(rb_build('{1,2,3}'))

    rb_and_agg

    roaringbitmap

    roaringbitmap

    And彙總計算。

    rb_and_agg(rb_build('{1,2,3}'))

    rb_xor_agg

    roaringbitmap

    roaringbitmap

    Xor彙總計算。

    rb_xor_agg(rb_build('{1,2,3}'))

    rb_or_cardinality_agg

    roaringbitmap

    integer

    Or彙總計算並返回其基數。

    rb_or_cardinality_agg(rb_build('{1,2,3}'))

    rb_and_cardinality_agg

    roaringbitmap

    integer

    And彙總計算並返回其基數。

    rb_and_cardinality_agg(rb_build('{1,2,3}'))

    rb_xor_cardinality_agg

    roaringbitmap

    integer

    Xor彙總計算並返回其基數。

    rb_xor_cardinality_agg(rb_build('{1,2,3}'))

    操作符

    操作符

    left

    right

    output

    描述

    樣本

    &

    roaringbitmap

    roaringbitmap

    roaringbitmap

    兩個Bitmap And操作。

    rb_build('{1,2,3}') & rb_build('{1,2,4}')

    |

    roaringbitmap

    roaringbitmap

    roaringbitmap

    兩個Bitmap Or操作。

    rb_build('{1,2}') | rb_build('{1,3}')

    #

    roaringbitmap

    roaringbitmap

    roaringbitmap

    兩個Bitmap Xor操作。

    rb_build('{1,2}') # rb_build('{1,3}')

    ~

    roaringbitmap

    roaringbitmap

    roaringbitmap

    兩個Bitmap Andnot操作。

    rb_build('{2,3}') ~ rb_build('{2,4}')

    +

    roraingbitmap

    integer

    roaringbitmap

    向Bitmap中添加特定的Offset。

    rb_build('{2,3}') + 1

    -

    roraingbitmap

    integer

    roaringbitmap

    從Bitmap移除特定的Offset。

    rb_build('{1,2,3}') - 1

    =

    roaringbitmap

    roaringbitmap

    boolean

    判斷兩個Bitmap是否相等。

    rb_build('{2,3}') = rb_build('{2,3}')

    <>

    roaringbitmap

    roaringbitmap

    boolean

    判斷兩個Bitmap是否不相等。

    rb_build('{2,3}') <> rb_build('{1,2,3}')

    &&

    roaringbitmap

    roaringbitmap

    boolean

    判斷兩個Bitmap是否相交。

    rb_build('{2,3}') && rb_build('{3,4}')

    @>

    roaringbitmap

    roaringbitmap

    boolean

    判斷Bitmap是否包含另外一個。

    rb_build('{2,3}') @> rb_build('{2}')

    @>

    roaringbitmap

    integer

    boolean

    判斷Bitmap是否包含特定的Offset。

    rb_build('{2,3}') @> 2

    <@

    roaringbitmap

    roaringbitmap

    boolean

    判斷Bitmap是否被另外一個包含。

    rb_build('{2,3}') <@ rb_build('{1,2,3}')

    <@

    integer

    roaringbitmap

    boolean

    判斷特定的Offset是否被Bitmap包含。

    rb_build('{2,3}') <@ rb_build('{3}')