StarRocks 查询加速1 - Bitmap

1 列基数（Cardinality）

列基数是指数据表中某一列的 “不同值的数量”，它直接决定了这一列数据的 “区分度”，分为两类：

2 Bitmap 索引的核心原理

1. 数据结构本质：基于 bit 数组（bitmap）实现，数组中每个 bit 对应数据表中的一行，用1表示该行符合某列的特定值，0表示不符合。 例：若 “性别” 列有值 “男”，则对应 bitmap 中所有 “性别 = 男” 的行标记为1，其余为0。
2. 与前缀索引的互补性：
   • 前缀索引是表的 “默认单索引”，仅对包含其前缀的过滤条件有效；
   • 当查询条件不匹配前缀索引时，可为对应列创建 Bitmap 索引，作为补充加速手段。

3 使用场景

1. 为什么不适用于单个低基数列？

• 核心逻辑：单个低基数列的查询过滤效果差，导致 Bitmap 索引无法减少 Page 扫描量，甚至增加额外开销。
• 原理支撑： 低基数列的 “不同值数量极少”（如 “性别 = 男 / 女”），单个值可能覆盖 30%-50% 的行。此时，Bitmap 索引的位图中 “1” 占比极高，过滤后仍需扫描大量 Page（例如 100 万行表中保留 50 万行），与全表扫描相比，节省的 IO 成本有限，但需额外加载和计算位图，反而可能降低效率。 例如：查询 “性别 = 男”，若 50% 行符合条件，Bitmap 索引需加载位图并计算，但最终仍需扫描 50% 的 Page，效率不如直接扫描。

2. 为什么适用于 “多个低基数列的组合查询”？

• 核心逻辑：多个低基数列的 “与运算” 可叠加过滤效果，最终达到 99.9% 以上的过滤率，而 Bitmap 索引的 “位图位运算” 能高效计算组合条件。
• 原理支撑： 单个低基数列（如 “性别 = 男”）过滤效果差（可能保留 50% 行），但多列组合（如 “性别 = 男 AND 部门 = 技术 AND 状态 = 在职”）通过 “条件叠加”，符合条件的行数占比可降至 0.1% 以下。 Bitmap 索引对每个列的条件生成独立位图，通过 “位与（AND）” 运算可瞬间得到组合条件的结果位图，直接定位目标行，避免扫描大量无关 Page。 例如：3 个低基数列各保留 30% 行，组合后仅保留 30%×30%×30%=2.7% 行，若再叠加 1 个条件，可进一步降至 0.8%，接近 99.9% 过滤率。

3. 为什么适用于 “较高基数列”？

• 核心逻辑：较高基数列的单值查询能实现极强的过滤效果（过滤 99.9% 以上数据），与 Bitmap 索引的 “位图快速定位” 特性高度匹配。
• 原理支撑： 较高基数列的 “不同值数量较多”（如城市列有 300 个值），但单个值对应的行数占比极低（例如 “城市 = 北京” 仅占 0.1% 行）。此时，Bitmap 索引中该值对应的位图仅有 0.1% 的 “1”，通过位运算可快速定位这些行，直接排除 99.9% 的数据页（Page），大幅减少磁盘 IO 和 Page 解码开销。 例如：100 万行表中，“城市 = 北京” 仅 1000 行符合条件，Bitmap 索引的位图中 “1” 占比 0.1%，查询时无需扫描 99.9% 的 Page，效率远高于全表扫描。

4. 为什么不适用于 “极高基数列”？

• 核心逻辑：极高基数列会导致 Bitmap 索引体积暴增，且维护和查询开销超过收益。
• 原理支撑： 极高基数列（如身份证号、订单 ID）的 “不同值数量接近总行数”（每个值对应 1 行），此时需为每个值生成一个位图，索引体积会达到 “总行数 × 值数量” 级别（例如 100 万行表需 100 万个位图），磁盘占用极大。 同时，导入数据时需为每个新值构建位图，频繁导入会显著降低性能；查询时若涉及多个值（如 “ID IN (100 个值)”），需加载 100 个位图，计算开销远超查询收益。

5. 如何权衡 Bitmap 索引的设计？

需在 “查询加速效果” 与 “额外成本” 间找到平衡，核心权衡维度如下：

1. 过滤效果优先：确保查询能过滤 99.9% 以上数据（即保留行数≤0.1%），这是 Bitmap 索引有效的前提。若过滤效果差，即使创建索引，数据库也会自动跳过（如 StarRocks 的自适应机制）。
2. 磁盘空间成本：高基数列的索引体积与基数正相关，需评估存储成本是否可接受（例如基数 10 万的列，索引体积可能达到表数据量的 50%）。
3. 导入性能影响：频繁导入场景（如实时同步）需避免在高基数列建 Bitmap 索引，否则每次导入需更新大量位图，导致延迟增加。
4. 查询索引加载开销：若查询条件涉及多个值（如 “城市 IN (10 个城市)”），需计算 “值数量 × 位图大小” 的加载成本，若成本超过全表扫描，则索引无效。

6. 实践建议：

• 对较高基数列（如城市、年龄段），先测试单值查询的过滤率，若≥99.9% 则创建索引；
• 对低基数列，优先通过 “多列组合查询” 设计索引，确保组合过滤率达标；
• 结合实际业务数据进行性能测试，对比 “有无 Bitmap 索引” 的查询耗时、存储占用和导入延迟，再决定是否使用。

7. StarRocks 的自适应机制

StarRocks 会自动判断 Bitmap 索引是否适用：

• 若索引能有效过滤数据且加载开销小，则启用；
• 若索引过滤效果差或加载开销大，则自动跳过，避免影响查询性能。 这一机制降低了 “不合理索引” 对查询的负面影响，提高了使用灵活性。