画像分析 - BSI优化方案(Beta)

当用户画像分析场景中存在大量的属性标签和行为标签时,使用Roaring Bitmap算法会有很大局限,Hologres为您提供BSI(Bit-sliced Index)算法,在解决局限问题的基础上尽可能保留Roaring Bitmap的多方优势。本文为您介绍在Hologres中如何通过BSI实现标签计算的最佳实践。

背景信息

Roaring Bitmap在用户画像分析场景,可以通过对标签表构建索引,将用户ID进行编码后以Bitmap格式保存,将关系运算转化为Bitmap的交并差运算,进而加速实时计算性能。但Roaring Bitmap会有以下局限:

  • 多标签联合查询问题:Roaring Bitmap更多用于“属性标签”,且仅可用于固定标签。对于大量“行为标签”,如PV、订单金额、观看时长等量值类标签,联合查询的解决方案只有回溯明细表,明细数据下钻成本增加。

  • 高基数标签的查询问题:当某个标签的去重值数量(基数)很大时,Roaring Bitmap的存储会膨胀,导致查询性能衰减。

针对上述局限,本文通过BSI(Bit-sliced Index)算法与若干函数进行优化,详情请参见BSI函数,解决以下问题:

  • 对于多标签联合查询场景,针对量值类“行为标签”进行预计算,通过BSI进行压缩存储,在保障精度的同时还可以避免与明细表进行关联查询,即可实现“属性标签”和“行为标签”的高效联动分析。

  • 对于高基数的行为标签,通过位切片索引,最多生成32个位切片,即可存储全部用户在INT范围内的行为标签值,并且在查询时可以通过二进制原理和Roaring Bitmap交并差运算进行快速计算,实现对高基数行为标签的压缩存储和低延迟查询。

画像分析方案介绍

假设系统中存在两张用户标签表,其中dws_userbase表示用户基础属性(省份、性别等),usershop_behavior表示用户行为标签(GMV等)。

  • 原始数据格式image.png

  • Bitmap格式:通过rb_tag表描述用户基础属性标签和uid的Bitmap关系,使用tag_name区分省份、性别等不同的标签。

    image.png

  • BSI格式(位切片构建):通过bsi_gmv表描述用户行为标签值和uid的BSI关系,针对标签值的二进制表示,记录每一位切片对应的uid Bitmap,共计4个切片。image.png

通过上述方案,将uid和对应的行为标签数值压缩存储进BSI中,通过BSI和Roaring Bitmap与或非运算实现标签的快速计算。比如:

  • 通过BSI对圈选出的人群做行为标签求和计算:将求和计算转化为每一位BSI切片上的Bitmap交集计算。image.png

  • 通过BSI对圈选出的人群做行为标签Top K计算:将全局排序计算转化为自高位向低位的BSI切片上的Bitmap交集计算。image.png

画像分析基础实践

BSI表设计

表名

表字段

备注

dws_userbase

(uid int, province text, gender text)

用户原始属性标签表,同标签宽表方案。

dws_uid_dict

(encode_uid serial, uid int)

用户uid字典编码表,同Roaring Bitmap方案。

usershop_behavior

(uid int, gmv int)

用户原始行为标签表,记录GMV等行为标签数据。

rb_tag

(tag_name text, tag_val text, bitmap roaringbitmap)

使用Roaring Bitmap表示的用户属性标签表。

bsi_gmv

(gmv_bsi bsi)

使用BSI表示的用户GMV指标明细表。

表DDL语句如下:

  • 用户原始属性标签表

    CREATE TABLE dws_userbase (
        uid int NOT NULL PRIMARY KEY,
        province text,
        gender text
        ...     -- 其他属性列
    )
    WITH (
        distribution_key = 'uid'
    );
  • 用户uid字典编码表

    CREATE TABLE dws_uid_dict (
        encode_uid serial,
        uid int PRIMARY KEY
    );
  • 用户原始行为标签表

    CREATE TABLE usershop_behavior (
        uid int NOT NULL,
        gmv int
    )
    WITH (
        distribution_key = 'uid'
    );
  • Roaring Bitmap表示的用户属性标签表

    CREATE TABLE rb_tag (
        tag_name text,
        tag_val text,
        bitmap roaringbitmap
    );
  • BSI表示的用户行为标签表(GMV)

    CREATE TABLE bsi_gmv (

    gmv_bsi bsi

    CREATE TABLE bsi_gmv (
        gmv_bsi bsi
    );

数据导入

  • 通过原始属性标签表和uid字典编码表生成属性标签Roaring Bitmap数据并分桶

    INSERT INTO rb_tag
    SELECT
        'province',
        province,
        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;
    
    INSERT INTO rb_tag
    SELECT
        'gender',
        gender,
        rb_build_agg (b.encode_uid) AS bitmap
    FROM
        dws_userbase a
        JOIN dws_uid_dict b ON a.uid = b.uid
    GROUP BY
        gender;
  • 通过原始行为标签表和uid字典编码表生成行为标签BSI数据并分桶

    INSERT INTO bsi_gmv
    SELECT
        bsi_build(array_agg(b.encode_uid),array_agg(a.gmv)) AS bitmap
    FROM
        usershop_behavior a
        JOIN dws_uid_dict b ON a.uid = b.uid
    ;

画像分析

通过BSI,可以非常便捷的将人群的属性标签和行为标签关联分析,包括人群圈选后的行为标签洞察、基于行为标签过滤的人群圈选等多个场景,示例如下:

人群圈选+行为标签分析

  • 查询“广东”“男”用户的GMV总值和人均GMV:

    • 通过BSI和Roaring Bitmap查询。

      SELECT 
          sum(kv[1]) AS total_gmv, -- 总GMV
          sum(kv[1])/sum(kv[2]) AS avg_gmv -- 人均GMV
      FROM (
          SELECT 
      	    bsi_sum(t1.gmv_bsi,t2.crowd) AS kv
          FROM
              bsi_gmv t1,
              (SELECT rb_and(a.bitmap,b.bitmap) AS crowd FROM
                  (SELECT bitmap FROM rb_tag WHERE tag_name = 'gender' AND tag_val = 'Male') a, -- 男性用户
                  (SELECT bitmap FROM rb_tag WHERE tag_name = 'province' AND tag_val = '广东') b -- 广东用户
              ) t2 
          ) t;
    • 通过原始属性标签与行为标签表查询。

      SELECT
          sum(b.gmv) AS total_gmv,
          avg(b.gmv) AS avg_gmv
      FROM
          dws_userbase a
          JOIN usershop_behavior b ON a.uid = b.uid
      WHERE
          a.province = '广东'
          AND a.gender = 'Male';
  • 查询“广东”“男”用户的消费金额分布:

    • 通过BSI和Roaring Bitmap查询:通过bsi_stat函数,定义边界值数组,即可高效完成多个区间内查询。

      SELECT
          bsi_stat('{100,300,500}', filter_bsi)
      FROM (
          SELECT
              bsi_filter(t1.gmv_bsi,t2.crowd) AS filter_bsi
          FROM 
              bsi_gmv t1,
              (SELECT rb_and(a.bitmap,b.bitmap) AS crowd FROM
                  (SELECT bitmap FROM rb_tag WHERE tag_name = 'gender' AND tag_val = 'Male') a, -- 男性用户
                  (SELECT bitmap FROM rb_tag WHERE tag_name = 'province' AND tag_val = '广东') b -- 广东用户
              ) t2
          ) t;
    • 通过原始属性标签和行为标签表查询:只能通过CASE WHEN语法表达。

      SELECT
          CASE
              WHEN gmv >= 0 AND gmv <= 100 THEN '0-100'
              WHEN gmv > 100 AND gmv <= 300 THEN '100-300'
              WHEN gmv > 300 AND gmv <= 500 THEN '300-500'
              WHEN gmv > 500 THEN '>500'
          END AS gmv_range,
          COUNT(*) AS user_count
      FROM 
          dws_userbase a
          JOIN usershop_behavior b ON a.uid = b.uid
      WHERE a.province = '广东'
          AND a.gender = 'Male'
      GROUP BY gmv_range
      ORDER BY gmv_range;
  • 昨日“广东”“男”用户消费金额Top K查询:

    • 通过BSI和Roaring Bitmap查询。

      SELECT
          rb_to_array(bsi_topk(filter_bsi,10))
      FROM (
          SELECT
              bsi_filter(t1.gmv_bsi,t2.crowd) AS filter_bsi
          FROM 
              bsi_gmv t1,
              (SELECT rb_and(a.bitmap,b.bitmap) AS crowd FROM
                  (SELECT bitmap FROM rb_tag WHERE tag_name = 'gender' AND tag_val = 'Male') a, -- 男性用户
                  (SELECT bitmap FROM rb_tag WHERE tag_name = 'province' AND tag_val = '广东') b -- 广东用户
              ) t2
          ) t;
    • 通过原始属性标签与行为标签表查询:

      SELECT
          b.uid,
          b.gmv
      FROM
          dws_userbase a
          JOIN usershop_behavior b ON a.uid = b.uid
      WHERE
          a.province = '广东'
          AND a.gender = 'Male'
      ORDER BY gmv DESC
      LIMIT 10;

基于行为标签的人群圈选

  • 圈选消费金额大于1000的用户:

    • 通过BSI和Roaring Bitmap查询。

      SELECT
          rb_to_array(bsi_gt(gmv_bsi, 1000)) AS crowd
      FROM
          bsi_gmv;
    • 通过原始属性标签与行为标签表查询。

      SELECT
          array_agg(uid)
      FROM
          usershop_behavior
      WHERE
          gmv > 800;

画像分析高级实践-分桶计算

依据上文的方案,将dws_userbase表按照省份、性别的列Bitmap压缩为一个Roaring Bitmap表,将usershop_behavior压缩成一个BSI表,压缩出来的Bitmap和BSI只能分布与集群中的少数节点,计算存储都不均匀,集群的资源并不能充分利用。因此,有必要将Bitmap和BSI拆分成多段,并将它们打散到集群中来提升并发执行的能力,假设将Bitmap和BSI都打散成65536段,实践方案如下:

BSI表设计

表名

表字段

备注

dws_userbase

(uid int, province text, gender text)

用户原始属性标签表,同上文基础实践。

dws_uid_dict

(encode_uid serial, uid int)

用户uid字典编码表,同上文基础实践。

usershop_behavior

(uid int, category text, gmv int, ds date)

用户原始行为标签表。

相较于基础实践,增加了类目(category)、日期(ds)字段,用于对数据进行分类,分时计算。

rb_tag

(tag_name text, tag_val text, bucket int, bitmap roaringbitmap)

使用Roaring Bitmap表示的用户属性标签表。

相较于基础实践,增加分桶(bucket)字段。

bsi_gmv

(ds text, category text, bucket int, gmv_bsi bsi)

使用BSI表示的用户GMV指标明细表。

相较于基础实践,增加了类目(category)、日期(ds)、分桶(bucket)字段,用于对BSI数据进行分类、分时、分桶计算。

表DDL语句如下:

  • Roaring Bitmap表示的用户属性标签表并分桶

    CREATE TABLE rb_tag (
        tag_name text,
        tag_val text,
        bucket int,
        bitmap roaringbitmap
    )
    WITH (
        distribution_key = 'bucket' -- 将分桶编号作为distribution_key
    );
  • BSI表示的用户行为标签表(GMV)并分桶

    CREATE TABLE bsi_gmv (
        category text,
        bucket int,
        gmv_bsi bsi,
        ds date
    )
    WITH (
        distribution_key = 'bucket' -- 将分桶编号作为distribution_key
    );

数据导入

  • 通过原始属性标签表和uid字典编码表生成属性标签Roaring Bitmap数据并分桶

    INSERT INTO rb_tag
    SELECT
        'province',
        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_tag
    SELECT
        'gender',
        gender,
        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
        gender,
        "bucket";
  • 通过原始行为标签表和uid字典编码表生成行为标签BSI数据并分桶

    INSERT INTO bsi_gmv
    SELECT
        a.category,
        b.encode_uid / 65536 AS "bucket",
        bsi_build(array_agg(b.encode_uid),array_agg(a.gmv)) AS bitmap,
        a.ds
    FROM
        usershop_behavior a
        JOIN dws_uid_dict b ON a.uid = b.uid
    WHERE
        ds = CURRENT_DATE - interval '1 day'
    GROUP BY
        category,
        "bucket",
        ds;

画像分析

通过BSI,可以非常便捷的将人群的属性标签和行为标签关联分析,包括人群圈选后的行为标签洞察、基于行为标签过滤的人群圈选等多个场景,同时还可以通过将人群数据打散到不同分桶进行加速计算,具体如下:

人群圈选+行为标签分析

  • 查询“广东”“男”用户“昨天”在“3C”类目下的GMV总值和人均GMV:

    SELECT 
        sum(kv[1]) AS total_gmv, -- 总GMV
        sum(kv[1])/sum(kv[2]) AS avg_gmv -- 人均GMV
    FROM (
        SELECT 
    	    bsi_sum(t1.gmv_bsi,t2.crowd) AS kv, 
            t1.bucket
        FROM
            (SELECT gmv_bsi, bucket FROM bsi_gmv WHERE category = '3C' AND ds = CURRENT_DATE - interval '1 day') t1
        JOIN
            (SELECT rb_and(a.bitmap,b.bitmap) AS crowd, a.bucket FROM
                (SELECT bitmap, bucket FROM rb_tag WHERE tag_name = 'gender' AND tag_val = 'Male') a -- 男性用户
             JOIN
                (SELECT bitmap, bucket FROM rb_tag WHERE tag_name = 'province' AND tag_val = '广东') b -- 广东用户
             ON a.bucket = b.bucket
            ) t2 
        ON t1.bucket = t2.bucket
        ) t;
  • 查询“广东”“男”用户“昨天”在“3C”类目下的消费金额分布:

    SELECT
        bsi_stat('{100,300,500}', bsi_add_agg(filter_bsi))
    FROM (
        SELECT
            bsi_filter(t1.gmv_bsi,t2.crowd) AS filter_bsi,
            t1.bucket
        FROM 
            (SELECT gmv_bsi, bucket FROM bsi_gmv WHERE category = '3C' AND ds = CURRENT_DATE - interval '1 day') t1
        JOIN
            (SELECT rb_and(a.bitmap,b.bitmap) AS crowd, a.bucket FROM
                (SELECT bitmap, bucket FROM rb_tag WHERE tag_name = 'gender' AND tag_val = 'Male') a -- 男性用户
             JOIN
                (SELECT bitmap, bucket FROM rb_tag WHERE tag_name = 'province' AND tag_val = '广东') b -- 广东用户
             ON a.bucket = b.bucket
            ) t2
        ON t1.bucket = t2.bucket
        ) t;
  • “广东”“男”用户“昨日”消费金额Top K查询:

    SELECT
        bsi_topk(bsi_add_agg(filter_bsi),10)
    FROM (
        SELECT
            bsi_filter(t1.gmv_bsi,t2.crowd) AS filter_bsi,
            t1.bucket
        FROM 
            (SELECT bsi_add_agg(gmv_bsi) AS gmv_bsi, bucket FROM bsi_gmv WHERE ds = CURRENT_DATE - interval '1 day' GROUP BY bucket) t1
        JOIN
            (SELECT rb_and(a.bitmap,b.bitmap) AS crowd, a.bucket FROM
                (SELECT bitmap, bucket FROM rb_tag WHERE tag_name = 'gender' AND tag_val = 'Male') a -- 男性用户
             JOIN
                (SELECT bitmap, bucket FROM rb_tag WHERE tag_name = 'province' AND tag_val = '广东') b -- 广东用户
             ON a.bucket = b.bucket
            ) t2
        ON t1.bucket = t2.bucket
        ) t;

基于行为标签的人群圈选

  • 圈选“近一个月”在“3C”类目下消费金额大于1000的用户:

    SELECT
        rb_to_array(bsi_gt(bsi_add_agg(gmv_bsi), 1000)) AS crowd
    FROM
        bsi_gmv
    WHERE
        category = '3C'
        AND ds BETWEEN CURRENT_DATE - interval '30 day' AND CURRENT_DATE - interval '1 day';