数据库查询优化中的位图过滤（Bitmap Filtering）原理解析

位图过滤是一种在分布式数据库或并行执行环境中，通过位图向量提前过滤数据以减少网络传输和计算开销的优化技术。它常用于哈希连接、合并连接等场景，尤其在大表连接时能显著提升性能。

下面我将从原理、场景、实现步骤和示例四个层次详细讲解：

1. 核心原理

位图过滤的核心思想是：在连接操作开始前，先从一个表（通常是维度表或小表）中提取连接键的集合，将其编码成一个位图，然后将这个位图广播到另一个表（通常是事实表或大表）所在的各个计算节点，提前过滤掉不满足连接条件的行，从而减少后续连接时需要处理的数据量。

关键点：

• 位图是紧凑的数据结构，通常一个键对应一个比特位（0或1），存储和传输效率高。
• 过滤发生在数据扫描或Shuffle之前，减少了不必要的I/O、网络和计算。

2. 适用场景

位图过滤通常在以下场景中有效：

• 星型模型或雪花模型：事实表与维度表关联，且维度表较小。
• 连接键基数较低：即连接键的重复值较多，过滤效果更明显。
• 分布式环境：如Spark、Presto、Greenplum等，需要跨节点传输数据。

3. 工作步骤

假设我们有两个表：orders（大表，事实表）和customers（小表，维度表），通过customer_id进行连接。

步骤1：构建位图

• 扫描customers表，收集所有唯一的customer_id值。
• 创建一个位图，长度等于customer_id的基数（或通过哈希函数映射到固定长度）。
• 对每个customer_id，通过哈希函数计算在位图中的位置，将该比特位设为1。

例如，假设customer_id集合是{101, 103, 105}，哈希映射后，位图可能为10100010（1表示存在，0表示不存在）。

步骤2：广播位图

• 将构建好的位图广播到所有存储orders表分区的节点。

步骤3：提前过滤

• 在每个节点扫描orders表时，对每一行的customer_id，用同样的哈希函数计算位图位置。
• 如果位图中对应位为1，则保留该行；如果为0，则直接丢弃。
• 这样，只有那些customer_id存在于customers表中的订单行才会进入后续连接阶段。

步骤4：执行连接

• 将过滤后的orders数据与customers表进行连接（如哈希连接），此时数据量已大大减少。

4. 举例说明

考虑以下SQL：

SELECT o.order_id, o.amount, c.customer_name
FROM orders o
JOIN customers c ON o.customer_id = c.customer_id
WHERE c.region = 'North';

传统执行流程：

1. 扫描customers，找出region='North'的所有customer_id（假设有1000个）。
2. 扫描orders表（假设1亿行），通过customer_id与上面结果做连接。

使用位图过滤后流程：

1. 扫描customers，得到1000个customer_id，构建位图。
2. 广播位图到所有orders分区节点。
3. 扫描orders时，用位图过滤：对每一行，检查customer_id是否在位图中。如果不在，直接跳过。
   假设orders中只有20%的客户在北方区域，则直接过滤掉80%的行，仅剩下约2000万行进入连接阶段。
4. 执行连接时，只需处理2000万行与1000行的连接，而非原始的1亿行。

5. 优化与注意事项

• 位图精度：可能存在哈希冲突（不同键映射到同一位），导致误过滤（假阳性）。优化方法：使用布隆过滤器（多个哈希函数）降低误判率。
• 小表驱动：必须确保构建位图的表足够小，否则位图过大，广播开销可能抵消收益。
• 动态过滤：在流水线执行中，位图可动态更新，适应数据变化。
• 与谓词下推结合：先对维度表做条件过滤（如region='North'），再构建位图，使位图更精准。

6. 总结

位图过滤的本质是用空间换时间，通过提前过滤大表中不相关的行，减少后续连接的计算量和数据传输。它在分布式大数据分析场景中极为有效，是Star Schema优化的常用手段之一。

关键优点：

1. 减少网络Shuffle数据量
2. 降低连接操作的输入数据规模
3. 位图结构紧凑，广播开销小

局限性：

1. 对小表大小敏感
2. 哈希冲突可能导致过滤不精确
3. 适用于等值连接，不适用于范围连接

掌握位图过滤，有助于理解分布式查询优化中数据预过滤的核心思想，并能在设计数据模型时考虑其适用性。