Doris Bitmap 精确去重优化实践.pdf

1、DataFunSummit#2023Doris Bitmap精确去重优化实践魏翔-美团-OLAP引擎开发工程师01精确去重简介02Bitmap 聚合性能优化03结合Doris向量化引擎优化04优化效果与总结目录 CONTENTDataFunSummit#202301精确去重简介DataFunSummit#202301精确去重简介去重计算场景与业界解决方案MPP架构两阶段聚合Roaring Bitmap 简介去重场景 去重指标计算 PV，UV的计算 日活用户数 订单量 客户留存(率)去重指标 相较于 普通指标（sum,avg）计算上的复杂度较高因此比较容易成为指标计算的性能瓶颈SELECT dt

2、 AS dt,first_entrance AS first_entrance_code,COUNT(DISTINCT device_id)AS view_uv,FROM TBLA where dt=20230501 and type=view GROUP BY dt,first_entrance业界已有的解决方案1.数仓生产：将各种指标在数仓生产环节提前计算好2.模糊去重：HyperLogLog3.精确去重：导入预聚合,减少现场计算量数仓生产 指标计算层级完全依赖数仓生产指标维度组合指数增长新增指标周期长数仓加工逻辑臃肿模糊去重 HyperLogLog原理 内存桶和哈希函数：将输入数据哈希到

3、多个内存桶中 寻找最长前缀零位（Leading Zero Count，LZC）：对每个哈希值计算 LZC 估计基数：通过统计 LZC 的平均值来估计基数 分桶减少误差StdError 1.04m(m=bucketnum)精确去重简介 精确的必要性 重要指标无法近似：金钱相关 数据驱动决策：近似误差会带来误判 灵活维度分析：不同维度下钻分析 MPP架构下精确去重过程:两阶段聚合-Streaming Agg -Merge Agg 数据结构 -明细模型:HashSet -聚合模型:Bitmap（基于Roaring Bitmap实现）去重指标计算去重指标计算优势缺点数仓生产查询时延很低非常不灵活开发周

4、期长模糊去重（HyperLogLog）查询时延适中支持上卷，灵活维度分析存在误差现场计算明细模型:HashSet支持灵活维度分析高基数场景查询时延很高现场计算聚合模型:Bitmap查询时延较高支持上卷，灵活维度分析高基数场景 Bitmap本身比较大计算吞吐和数据分布强相关Roaring Bitmap简介 Roaring Bitmap 数据结构Bitmap 是一种基于位图思想的用于保存聚合后的明细数据（64位非负整数）的数据结构保存明细数据使得其能够支持rollup构建以及任意维度的上卷分析Roaring Bitmap简介 Container TypeContainer Type数据结构大小Ar

5、ray Containerunsigned short 数组size*16 bitBitset Containerbitset65536 bitRunLen ContainerRun length 编码当size 4096 时:bitset container 更省空间Roaring Bitmap简介 Add Value into Bitmap精确去重简介 Union 时间复杂度union container类型时间复杂度array union arrayO(m+n)array union bitsetO(m)bitset union bitsetO(1)runlen union runlen

6、接近 O(1)精确去重简介-小结 关于精确去重指标1.精确去重指标计算的复杂度高2.精确去重场景中Bitmap 兼顾灵活分析和性能 关于Roaring Bitmap1.面向空间优化的2.尽量将计算卸载到 Bitset Container Union 常数时间开销上3.数据不宜太离散，低位连续，减少Container数量膨胀DataFunSummit#202302Bitmap聚合性能优化DataFunSummit#202302Bitmap聚合性能优化现有性能瓶颈基于输入数据布局的优化基于计算流程的优化Doris Bitmap 聚合现有瓶颈基于输入数据布局的