Hologres：Bitmap Roaring

Bitmap Roaring cocok untuk skenario berikut:

• Skenario dengan banyak tag: Operasi JOIN diperlukan untuk banyak tabel besar. Fungsi BITMAP_AND dapat menggantikan operasi JOIN untuk mengurangi konsumsi memori. Repositori plugin bitmap meningkatkan pemanfaatan CPU hingga 1%–2% melalui optimasi berbasis Single Instruction Multiple Data (SIMD).

• Skenario dengan volume data besar yang memerlukan deduplikasi: Bitmap menyediakan kemampuan deduplikasi intrinsik untuk mencegah perhitungan vektor unik (UV) dan overhead memori.

Tag dalam sistem profiling diklasifikasikan ke dalam jenis-jenis berikut. Jenis tag yang berbeda menggunakan mode komputasi berbeda, dan beberapa tag harus dikonversi dan disimpan sebagai bitmap.

• Tag properti: Menggambarkan properti pengguna seperti gender, provinsi, dan status pernikahan. Tag ini stabil dan dapat difilter berdasarkan kondisi tertentu. Rasio kompresi bitmap tinggi, sehingga bitmap cocok untuk operasi terkait.

• Tag tindakan: Menggambarkan karakteristik tindakan pengguna pada titik waktu tertentu, seperti tampilan halaman, pembelian, atau log masuk aktif. Data sering diperbarui dan memerlukan pemindaian rentang serta penyaringan agregat. Rasio kompresi bitmap rendah, sehingga bitmap kurang cocok untuk operasi terkait.

Tag properti menggambarkan properti pengguna. Tag ini stabil dan dapat difilter berdasarkan kondisi tertentu. Bitmap digunakan untuk kompresi dan operasi yang efisien.

• Solusi

  Asumsikan bahwa platform manajemen data (DMP) berisi dua tabel tag properti, seperti ditunjukkan pada gambar berikut. Tabel dws_userbase menggambarkan properti dasar pengguna, sedangkan tabel dws_usercate_prefer menggambarkan preferensi pengguna.

  Untuk mendapatkan jumlah pengguna yang memenuhi kondisi filter [province = Beijing] & [cate_prefer = Fashion], Anda dapat melakukan operasi asosiasi, penyaringan, dan deduplikasi. Namun, dalam skenario dengan volume data besar, operasi ini dapat memberikan beban kinerja yang signifikan.

  Solusi optimasi berbasis bitmap menggunakan tabel bitmap yang telah dibuat sebelumnya untuk mengurangi biaya operasi ad hoc. Dalam contoh ini, data dalam tabel-tabel sebelumnya dibagi berdasarkan kolom untuk membuat dua tabel bitmap, seperti ditunjukkan pada gambar berikut. Kemudian, operasi AND bitwise dilakukan untuk mendapatkan pengguna yang memenuhi kondisi filter sebelumnya. Tabel rb_dws_userbase_province menggambarkan hubungan bitmap antara kolom provinsi dan uid, sedangkan tabel rb_dws_usercate_prefer_cprefer menggambarkan hubungan bitmap antara kolom cate_prefer dan uid.

  Namun, solusi ini memiliki potensi masalah. Ketika kolom memiliki hubungan hierarkis, pemisahan dan operasi seperti itu dapat menyebabkan kesalahan komputasi, seperti ditunjukkan pada gambar berikut. Data dalam tabel dws_shop_cust, yang menggambarkan informasi tentang pelanggan baru, ada, dan potensial, dibagi berdasarkan kolom. Tabel bitmap rb_dws_shop_cust_shop_id menggambarkan ID toko, dan tabel bitmap rb_dws_shop_cust_cust_type menggambarkan jenis pelanggan. Jika Anda memfilter pelanggan yang memenuhi kondisi filter [shop_id = A] & [cust_type = Fresh], hasilnya adalah uid [1]. Namun, nilai kolom uid 1 yang sesuai dengan nilai kolom cust_type Fresh tidak ada. Hal ini disebabkan oleh korelasi antara kolom cust_type dan shop_id. Dalam model gudang data, cust_type adalah metrik untuk shop_id dan tidak dapat digunakan secara independen. Anda harus menggunakan shop_id bersama dengan cust_type untuk membuat tabel bitmap rb_dws_shop_cust_sid_ctype guna mencegah kesalahan tersebut.

  Anda harus mengompres nilai uid ke dalam bitmap dan melakukan operasi AND, OR, dan NOT bitwise untuk menghitung tag.

• Prosedur

  • Enkode Informasi Pengguna

    ID pengguna mungkin berupa string, tetapi bitmap hanya berisi bilangan bulat. Oleh karena itu, Anda harus membuat tabel dengan bidang auto-increment menggunakan tipe data SERIAL atau BIGSERIAL untuk meng-enkode nilai uid tipe string menjadi bilangan bulat. Untuk informasi lebih lanjut, lihat PostgreSQL SERIAL.

    --Buat tabel kamus.
    CREATE TABLE dws_uid_dict (
        encode_uid bigserial,
          uid text primary key
    );
    
    --Masukkan nilai uid dari tabel tag.
    INSERT INTO dws_uid_dict(uid)
    SELECT uid
    FROM dws_userbase ON conflict DO NOTHING;

    ID pengguna yang di-enkode mempertahankan kontinuitas dan dapat disimpan dengan mudah sebagai bitmap. Gambar berikut menunjukkan contoh di mana bitmap2 berisi data jarang dan memberikan efisiensi penyimpanan jauh lebih rendah daripada bitmap1. Oleh karena itu, jika ID pengguna di-enkode, biaya penyimpanan dapat dikurangi dan efisiensi komputasi dapat ditingkatkan.

    Data numerik jarang dapat di-enkode, tetapi overhead kinerja tambahan mungkin terjadi. Misalnya, DMP iklan memerlukan profil kinerja tinggi dan output real-time detail pengguna. Jika output real-time detail pengguna diperlukan, tabel ID pengguna harus digabungkan untuk mengembalikan ID pengguna yang di-enkode, yang menyebabkan overhead kinerja tambahan. Anda harus menentukan apakah akan meng-enkode ID pengguna berdasarkan skenario spesifik Anda. Berikut adalah rekomendasi kami:

    • Untuk ID pengguna tipe string, kami sarankan Anda meng-enkodenya.

    • Untuk ID pengguna tipe integer yang memerlukan pemulihan ID pengguna yang di-enkode secara sering, kami tidak menyarankan Anda meng-enkodenya.

    • Untuk ID pengguna tipe integer yang tidak memerlukan pemulihan ID pengguna yang di-enkode secara sering, kami sarankan Anda meng-enkodenya.

  • Proses dan Kueri Bitmap

    Pisahkan tabel dws_userbase dan dws_shop_cust menjadi satu tabel bitmap yang berisi kolom provinsi dan gender. Nilai kolom gender hanya mencakup Pria dan Wanita. Bitmap yang dikompresi hanya didistribusikan pada dua node dalam kluster, sehingga sumber daya komputasi dan penyimpanan tidak didistribusikan secara merata. Dalam hal ini, bitmap harus dipisah menjadi beberapa segmen dan didistribusikan dalam kluster untuk eksekusi bersamaan. Misalnya, Anda dapat mengeksekusi pernyataan SQL berikut untuk membagi bitmap menjadi 65.536 segmen:

    -- Buat tabel lebar bernama dws_userbase.
    BEGIN;
    CREATE TABLE dws_shop_cust
    (
      uid text not null primary key,
      shop_id text,
        cust_type text
    );
    call set_table_property('dws_shop_cust', 'distribution_key', 'uid');
    END;
    
    -- Buat ekstensi bitmap.
    CREATE EXTENSION roaringbitmap;
    
    BEGIN;
    CREATE TABLE rb_dws_userbase_province (
        province text,
      bucket int,
        bitmap roaringbitmap
    );
    call set_table_property('rb_dws_userbase_province', 'distribution_key', 'bucket');
    END;
    
    BEGIN;
    CREATE TABLE rb_dws_shop_cust_sid_ctype (
        shop_id text,
      cust_type text,
      bucket int,
        bitmap roaringbitmap
    );
    call set_table_property('rb_dws_shop_cust_sid_ctype', 'distribution_key', 'bucket');
    END;
    
    -- Tulis data ke tabel bitmap.
    INSERT INTO rb_dws_userbase_province
    SELECT province,
           encode_uid / 65536 as "bucket",
           rb_build_agg(b.encode_uid) AS bitmap
    FROM dws_userbase a join dws_uid_dict b on a.uid = b.uid
    GROUP BY province, "bucket";
    
    INSERT INTO rb_dws_shop_cust_sid_ctype
    SELECT shop_id,
           cust_type,
           encode_uid / 65536 AS "bucket",
           rb_build_agg(b.encode_uid) AS bitmap
    FROM dws_shop_cust a
    JOIN dws_uid_dict b ON a.uid = b.uid
    GROUP BY shop_id, cust_type, "bucket";

    Untuk mendapatkan pengguna yang memenuhi kondisi filter [shop_id = A] & [cust_type = Fresh] & [province = Beijing], Anda dapat melakukan operasi AND, OR, dan NOT pada bitmap. Anda dapat mengeksekusi pernyataan SQL berikut:

    SELECT SUM(RB_CARDINALITY(rb_and(ub.bitmap, uc.bitmap)))
    FROM
      (SELECT rb_or_agg(bitmap) AS bitmap,
              bucket
       FROM rb_dws_userbase_province
       WHERE province = 'Beijing'
       GROUP BY bucket) ub
    JOIN
      (SELECT rb_or_agg(bitmap) AS bitmap,
              bucket
       FROM rb_dws_shop_cust_sid_ctype
       WHERE shop_id = 'A'
         AND cust_type = 'Fresh'
       GROUP BY bucket) uc ON ub.bucket = uc.bucket;

Anda dapat mengeksekusi pernyataan SQL berikut untuk mendapatkan pengguna yang memenuhi kondisi filter [province=Beijing] & [shop_id=A DAN Tidak ada pembelian selama 7 hari].

-- Buat tabel tindakan.
BEGIN;
CREATE TABLE dws_usershop_behavior
(
  uid int not null,
  shop_id text not null,
  pv_cnt int,
  trd_cnt int,
  ds integer not null
);
call set_table_property('dws_usershop_behavior', 'distribution_key', 'uid');
COMMIT;

-- Enkode tabel tindakan.
BEGIN;
CREATE TABLE dws_usershop_behavior_bucket
(
  encode_uid int not null,
  shop_id text not null,
  pv_cnt int,
  trd_cnt int,
  ds int not null,
  bucket int
);
CALL set_table_property('dws_usershop_behavior_bucket', 'orientation', 'column');
call set_table_property('dws_usershop_behavior_bucket', 'distribution_key', 'bucket');
CALL set_table_property('dws_usershop_behavior_bucket', 'clustering_key', 'shop_id,encode_uid');
COMMIT;

-- Tulis data fakta.
INSERT INTO dws_usershop_behavior_bucket
SELECT *,
             encode_uid,
       shop_id,
       pv_cnt,
       trd_cnt,
       encode_uid / 65536
FROM dws_usershop_behavior a JOIN dws_uid_dictionary b
on a.uid = b.uid;

-- Gabungkan data fakta dan data properti.
SELECT sum(rb_cardinality(bitmap)) AS cnt
FROM
  (SELECT rb_and(ub.bitmap, us.bitmap) AS bitmap,
          ub.bucket
   FROM
     (SELECT rb_or_agg(bitmap) AS bitmap,
             bucket
      FROM rb_dws_userbase_province
      WHERE province = 'Beijing'
      GROUP BY bucket) AS ub
   JOIN
     (SELECT rb_build_agg(uid) AS bitmap,
             bucket
      FROM
        (SELECT uid,
                bucket
         FROM dws_usershop_behavior_bucket
         WHERE shop_id = 'A' AND ds > to_char(current_date-7, 'YYYYMMdd')::int
         GROUP BY uid,
                  bucket HAVING sum(trd_cnt) = 0) tmp
      GROUP BY bucket) us ON ub.bucket = us.bucket) r

Anda dapat memilih untuk memproses data bitmap secara offline untuk mencegah komputasi data bitmap memengaruhi bisnis Anda. Anda dapat memuat data dari tabel asing di MaxCompute atau Hive. Bitmap diproses dengan cara yang serupa baik online maupun offline. Data dapat dihasilkan melalui enkode dan agregasi. Kode berikut memberikan contoh cara membuat data bitmap secara offline di MaxCompute.

-- Pilih proyek.
USE bitmap_demo; 

-- Buat tabel sumber.
CREATE TABLE mc_dws_uid_dict (
encode_uid bigint,
bucket bigint,
uid string
);

CREATE TABLE mc_dws_userbase
(
  uid string,
  province string,
  gender string,
  marriaged string
);

-- Enkode nilai uid.
-- Hitung nilai uid baru.
WITH uids_to_encode AS
  (SELECT DISTINCT(ub.uid),
          CAST(ub.uid / 65336 AS BIGINT) AS bucket
   FROM mc_dws_userbase ub
   LEFT JOIN mc_dws_uid_dict d ON ub.uid = d.uid
   WHERE d.uid IS NULL),
-- Hitung jumlah uid yang akan di-enkode di setiap bucket. Gunakan fungsi SUM untuk mendapatkan offset bucket.
uids_bucket_encode_offset AS
  (SELECT bucket,
          sum(cnt) over (ORDER BY bucket ASC) - cnt AS bucket_offset
   FROM
     (SELECT count(1) AS cnt,
             bucket
      FROM uids_to_encode
      GROUP BY bucket) x),
-- Hitung jumlah maksimum uid yang di-enkode.
dict_used_id_offset AS
  (SELECT max(encode_uid) AS used_id_offset FROM mc_dws_uid_dict)
-- Uid baru = Jumlah maksimum uid yang di-enkode + Offset bucket + Nomor baris
INSERT INTO mc_dws_uid_dict
SELECT
       COALESCE((SELECT used_id_offset FROM dict_used_id_offset),0) + bucket_offset + rn,
       bucket,
       uid
FROM
  (SELECT row_number() OVER (partition BY ub.bucket ORDER BY ub.uid) AS rn,
          ub.bucket,
          bo.bucket_offset,
          uid
   FROM uids_to_encode ub
   JOIN uids_bucket_encode_offset bo ON ub.bucket = bo.bucket) j


-- Buat fungsi terkait bitmap.
add jar function_jar_dir/mc-bitmap-functions.jar as mc_bitmap_func.jar -f;
create function mc_rb_cardinality as com.alibaba.hologres.RbCardinalityUDF using mc_bitmap_func.jar;
create function mc_rb_build_agg as com.alibaba.hologres.RbBuildAggUDAF using mc_bitmap_func.jar;

-- Buat tabel bitmap dan tulis data ke tabel.
CREATE TABLE mc_rb_dws_userbase_province
(
  province string,
  bucket int,
  bitmap string
);
INSERT INTO mc_rb_dws_userbase_province
SELECT province,
       b.bucket_num,
       mc_rb_build_agg(b.encode_uid) AS bitmap
FROM mc_dws_userbase a join mc_dws_uid_dict b on a.uid = b.uid
GROUP BY province, b.bucket_num;

Eksekusi pernyataan berikut di Hologres:

-- Buat tabel MaxCompute.
CREATE TABLE mc_rb_dws_userbase_province (
    province text,
  bucket int,
    bitmap text
) server odps_server options(project_name 'bitmap_demo', table_name 'mc_rb_dws_userbase_province');
-- Tulis data bitmap dari tabel MaxCompute ke Hologres.
INSERT INTO rb_dws_userbase_province
SELECT province,
       bucket::INT,
       roaringbitmap_text(bitmap, FALSE)
FROM mc_rb_dws_userbase_province;

Setelah langkah-langkah sebelumnya dilakukan, data dimuat ke Hologres. Anda kemudian dapat melakukan operasi bitwise untuk mempercepat kueri.

• Anda dapat menggunakan mc-bitmap untuk menghitung data bitmap di MaxCompute.

• Untuk informasi lebih lanjut tentang pemrosesan offline bitmap, lihat Perhitungan UV Batch.

Dalam skenario komputasi real-time, Anda dapat menggunakan Hologres bersama dengan Flink untuk melakukan deduplikasi real-time untuk tag pengguna berdasarkan bitmap Roaring. Langkah-langkahnya adalah sebagai berikut:

1. Gunakan tabel kamus ID pengguna sebagai tabel dimensi dan gunakan pernyataan INSERT ON CONFLICT Hologres untuk menambahkan ID pengguna. Kemudian, gabungkan tabel dimensi dan tindakan di Flink.

2. Agregasikan tabel yang dihasilkan dengan bitmap Roaring berdasarkan tag.

3. Tulis bitmap yang dihasilkan ke dalam tabel bitmap di Hologres.