数据库查询优化中的动态过滤（Dynamic Filtering）原理解析
字数 2886 2025-12-09 05:31:33

数据库查询优化中的动态过滤（Dynamic Filtering）原理解析

动态过滤是一种在大数据或分布式数据库系统中常用的查询优化技术。它的核心思想是在运行时生成和应用过滤条件，以减少连接（特别是Shuffle Join）操作中需要传输和处理的数据量。它主要针对一种常见场景：一个大表与一个小表（或一个经过过滤后结果集很小的表）进行等值连接。

一、 问题背景：为什么需要动态过滤？

想象一个典型的星型模型查询：

SELECT *
FROM 大事实表 f
JOIN 小维度表 d ON f.dim_id = d.id
WHERE d.category = 'A';

传统执行过程（以Shuffle Hash Join为例）:

  1. 读取小维度表d，应用WHERE d.category = 'A'条件，得到一个小的结果集（比如只有10行）。我们称它为“构建侧”（Build Side）。
  2. 读取整个大事实表f（可能有数十亿行）。这是“探测侧”（Probe Side）。
  3. 将小表的10行数据构建成内存哈希表。
  4. 将大表的每一行，根据dim_id去哈希表中查找匹配。虽然哈希表很小，但大表仍需读取和扫描全部数十亿行，其中绝大多数dim_id的值根本不在小表的10个id中，这些读取和传输都是巨大的浪费。

关键痛点：在扫描大表时，我们提前知道只有dim_id等于小表结果集中那些id的行才可能匹配。如果能把这个信息（一个过滤列表）提前应用到大表扫描阶段，就能大幅减少IO和网络传输。这就是动态过滤要解决的问题。

二、 动态过滤的核心原理

动态过滤在查询执行过程中，从一个结果已知的表（通常是构建侧）动态地收集过滤值（如连接键的集合），并将这个过滤条件下推到另一个表（探测侧）的扫描或数据交换（Shuffle）操作之前。

核心步骤分解：

  1. 收集过滤值（Collect）：

    • 优化器或执行引擎识别出可以进行动态过滤的连接模式（大表JOIN小表，且是等值连接）。
    • 在运行时，先执行构建侧的操作（例如扫描维度表并过滤）。执行引擎会实时收集构建侧结果集中连接键（如id）的所有去重值，形成一个“过滤值集合”。

  2. 创建与广播过滤（Create & Broadcast）：

    • 将这个“过滤值集合”封装成一个动态过滤器（可能是一个Bloom Filter，也可能是一个哈希集合）。
    • 将该过滤器广播给所有正在执行探测侧扫描任务的节点。

  3. 应用过滤（Apply）：

    • 探测侧的每个数据扫描任务（例如读取大表的一个分区）在读取每一行数据时，在数据进入连接操作甚至进行Shuffle之前，就使用接收到的动态过滤器进行检查。
    • 对于大表的一行，提取其连接键（如dim_id），用过滤器判断：如果 dim_id 不在过滤器中，则丢弃该行；如果在，则保留并传递到下游进行连接。
    • 因为过滤器体积小（特别是Bloom Filter），这个检查非常快，但能提前过滤掉绝大部分无关数据。

  4. 执行连接：

    • 经过动态过滤后的大表数据量已大幅减少，再与构建侧的小表进行常规的连接操作（如Hash Join）。

三、 技术实现的关键细节

  1. 过滤器的选择：

    • 精确集合：如果构建侧结果集非常小（如几十、几百个键），可以直接将去重的键值列表作为过滤器。检查是精确的O(1)哈希查找。
    • Bloom Filter：如果构建侧结果集有数千甚至数万个键，广播完整的列表开销较大。此时使用Bloom Filter——一种概率型数据结构。它用很小的空间表示一个集合，检查一个元素“肯定不在集合中”或“可能在集合中”。虽然有“可能”的误判（False Positive），但“肯定不在”的判定是精确的。在动态过滤场景下，我们主要利用其“肯定排除”的能力，过滤掉大量无关数据，即使有少量“可能”的数据被保留，对整体性能提升也巨大，且结果绝对正确。

  2. 应用时机：

    • 数据源扫描时：最优情况。在从存储（如HDFS， S3）读取数据块时即应用过滤，直接减少IO。
    • Shuffle之前：在Map阶段输出、准备进行网络传输（Shuffle）前应用，可以减少网络传输量。
    • 数据库系统（如Presto/Trino, Spark SQL）会尽可能将过滤条件下推到离数据源最近的操作。

  3. 自适应触发：

    • 并非所有大小表连接都启用动态过滤。优化器会根据统计信息（如表大小、过滤条件的选择性）来估算构建侧结果集的大小。如果预计结果集很小，才会启用此优化。
    • 在运行时，如果发现构建侧结果集实际过大（例如超过阈值），可能会动态禁用过滤器生成，以避免创建和广播大过滤器的开销。

四、 举例说明

假设查询：

SELECT f.*, d.name
FROM sales f -- 事实表，100亿行
JOIN product d ON f.product_id = d.id -- 产品维度表
WHERE d.brand = 'Nike';

假设product表中brand='Nike'的产品只有100个。

无动态过滤的执行流程：

  1. 从product表读取所有行，过滤出100个brand='Nike'的id，构建哈希表。
  2. 从存储中完整读取sales表的100亿行。
  3. 对这100亿行逐行用product_id探测哈希表，最终可能只匹配出10亿行（假设Nike产品销量占比10%）。
  4. 问题：读取和传输了90亿无效行。

有动态过滤的执行流程：

  1. 从product表读取并过滤，得到100个id，构建哈希表（用于连接），同时用这100个id构建一个Bloom Filter。
  2. 广播这个Bloom Filter到所有负责扫描sales表的节点。
  3. 每个节点扫描sales表分区时，对每一行：
    • 取出product_id，用Bloom Filter检查。
    • 如果Bloom Filter说“肯定不在”，则立即丢弃该行。
    • 如果Bloom Filter说“可能在”，则保留该行，继续后续流程。
    • （假设过滤掉90%的无关数据）。
  4. 只有约10亿行“可能”的数据被Shuffle并传输到连接节点。
  5. 这10亿行与之前构建的product哈希表进行精确连接，得到最终结果。

效果：IO、网络传输、中间数据处理量减少约90%。

五、 适用场景与限制

适用场景：

  • 星型模型或雪花模型中的事实表与维度表连接。
  • 等值连接，且构建侧结果集远小于探测侧。
  • 分布式计算环境（如Spark, Presto/Trino, Hive）或支持此特性的MPP数据库。

限制与挑战：

  • 非等值连接不适用：动态过滤依赖于精确的键值集合，>, <, BETWEEN等连接条件无法使用。
  • 构建侧过大的开销：如果构建侧结果集本身很大，创建和广播过滤器本身会成为性能瓶颈。
  • 数据倾斜：如果构建侧的某个键在探测侧极端倾斜，动态过滤效果会打折扣，但仍有整体收益。
  • 优化器误判：优化器如果错误估计了构建侧大小，可能导致错误地启用或禁用此优化。

总结

动态过滤是一种运行时感知的优化技术，它将连接操作的语义（等值匹配）转化为一种高效的运行时过滤条件，并尽可能早地应用于数据流水线中。其本质是用构建侧的已知信息，在探测侧扫描时提前进行“预连接”判断，从而在分布式大数据场景下，极大地减少了不必要的数据移动和计算，是提升连接查询性能的关键优化手段之一。

数据库查询优化中的动态过滤（Dynamic Filtering）原理解析 动态过滤是一种在大数据或分布式数据库系统中常用的查询优化技术。它的核心思想是 在运行时生成和应用过滤条件，以减少连接（特别是Shuffle Join）操作中需要传输和处理的数据量 。它主要针对一种常见场景：一个大表与一个小表（或一个经过过滤后结果集很小的表）进行等值连接。 一、 问题背景：为什么需要动态过滤？ 想象一个典型的星型模型查询： 传统执行过程（以Shuffle Hash Join为例）: 读取小维度表d ，应用 WHERE d.category = 'A' 条件，得到一个小的结果集（比如只有10行）。我们称它为“构建侧”（Build Side）。 读取整个大事实表f （可能有数十亿行）。这是“探测侧”（Probe Side）。 将小表的10行数据构建成内存哈希表。 将大表的每一行，根据 dim_id 去哈希表中查找匹配。虽然哈希表很小，但大表仍需读取和扫描全部数十亿行，其中绝大多数 dim_id 的值根本不在小表的10个id中，这些读取和传输都是巨大的浪费。 关键痛点 ：在扫描大表时，我们 提前知道 只有 dim_id 等于小表结果集中那些id的行才可能匹配。如果能把这个信息（一个过滤列表）提前应用到大表扫描阶段，就能 大幅减少IO和网络传输 。这就是动态过滤要解决的问题。 二、 动态过滤的核心原理 动态过滤在 查询执行过程中，从一个结果已知的表（通常是构建侧）动态地收集过滤值（如连接键的集合），并将这个过滤条件下推到另一个表（探测侧）的扫描或数据交换（Shuffle）操作之前 。 核心步骤分解 ： 收集过滤值（Collect） ： 优化器或执行引擎识别出可以进行动态过滤的连接模式（大表JOIN小表，且是等值连接）。 在运行时， 先执行构建侧 的操作（例如扫描维度表并过滤）。执行引擎会 实时收集 构建侧结果集中连接键（如 id ）的所有 去重值 ，形成一个“过滤值集合”。 创建与广播过滤（Create & Broadcast） ： 将这个“过滤值集合”封装成一个 动态过滤器 （可能是一个Bloom Filter，也可能是一个哈希集合）。 将该过滤器 广播 给所有正在执行探测侧扫描任务的节点。 应用过滤（Apply） ： 探测侧的每个数据扫描任务（例如读取大表的一个分区）在读取每一行数据时， 在数据进入连接操作甚至进行Shuffle之前 ，就使用接收到的动态过滤器进行检查。 对于大表的一行，提取其连接键（如 dim_id ），用过滤器判断： 如果 dim_id 不在过滤器中，则丢弃该行；如果在，则保留并传递到下游进行连接 。 因为过滤器体积小（特别是Bloom Filter），这个检查非常快，但能提前过滤掉绝大部分无关数据。 执行连接 ： 经过动态过滤后的大表数据量已大幅减少，再与构建侧的小表进行常规的连接操作（如Hash Join）。 三、 技术实现的关键细节 过滤器的选择 ： 精确集合 ：如果构建侧结果集非常小（如几十、几百个键），可以直接将去重的键值列表作为过滤器。检查是精确的O(1)哈希查找。 Bloom Filter ：如果构建侧结果集有数千甚至数万个键，广播完整的列表开销较大。此时使用 Bloom Filter ——一种概率型数据结构。它用很小的空间表示一个集合，检查一个元素“ 肯定不在集合中 ”或“ 可能在集合中 ”。虽然有“可能”的误判（False Positive），但“肯定不在”的判定是精确的。在动态过滤场景下，我们主要利用其“ 肯定排除 ”的能力，过滤掉大量无关数据，即使有少量“可能”的数据被保留，对整体性能提升也巨大，且结果绝对正确。 应用时机 ： 数据源扫描时 ：最优情况。在从存储（如HDFS， S3）读取数据块时即应用过滤，直接减少IO。 Shuffle之前 ：在Map阶段输出、准备进行网络传输（Shuffle）前应用，可以减少网络传输量。 数据库系统（如Presto/Trino, Spark SQL）会尽可能将过滤条件下推到离数据源最近的操作。 自适应触发 ： 并非所有大小表连接都启用动态过滤。优化器会根据统计信息（如表大小、过滤条件的选择性）来估算构建侧结果集的大小。如果预计结果集很小，才会启用此优化。 在运行时，如果发现构建侧结果集实际过大（例如超过阈值），可能会动态禁用过滤器生成，以避免创建和广播大过滤器的开销。 四、 举例说明 假设查询： 假设 product 表中 brand='Nike' 的产品只有100个。 无动态过滤的执行流程 ： 从 product 表读取所有行，过滤出100个 brand='Nike' 的 id ，构建哈希表。 从存储中 完整读取 sales 表的100亿行。 对这100亿行逐行用 product_id 探测哈希表，最终可能只匹配出10亿行（假设Nike产品销量占比10%）。 问题 ：读取和传输了90亿无效行。 有动态过滤的执行流程 ： 从 product 表读取并过滤，得到100个 id ，构建哈希表（用于连接）， 同时 用这100个 id 构建一个Bloom Filter。 广播 这个Bloom Filter到所有负责扫描 sales 表的节点。 每个节点扫描 sales 表分区时，对每一行： 取出 product_id ，用Bloom Filter检查。 如果Bloom Filter说“ 肯定不在 ”，则 立即丢弃 该行。 如果Bloom Filter说“ 可能在 ”，则保留该行，继续后续流程。 （假设过滤掉90%的无关数据）。 只有约10亿行“可能”的数据被Shuffle并传输到连接节点。 这10亿行与之前构建的 product 哈希表进行精确连接，得到最终结果。 效果 ：IO、网络传输、中间数据处理量减少约90%。 五、 适用场景与限制 适用场景 ： 星型模型或雪花模型中的事实表与维度表连接。 等值连接，且构建侧结果集远小于探测侧。 分布式计算环境（如Spark, Presto/Trino, Hive）或支持此特性的MPP数据库。 限制与挑战 ： 非等值连接不适用 ：动态过滤依赖于精确的键值集合， > , < , BETWEEN 等连接条件无法使用。 构建侧过大的开销 ：如果构建侧结果集本身很大，创建和广播过滤器本身会成为性能瓶颈。 数据倾斜 ：如果构建侧的某个键在探测侧极端倾斜，动态过滤效果会打折扣，但仍有整体收益。 优化器误判 ：优化器如果错误估计了构建侧大小，可能导致错误地启用或禁用此优化。 总结 动态过滤是一种 运行时感知 的优化技术，它将连接操作的语义（等值匹配）转化为一种高效的运行时过滤条件，并尽可能早地应用于数据流水线中。其本质是 用构建侧的已知信息，在探测侧扫描时提前进行“预连接”判断 ，从而在分布式大数据场景下，极大地减少了不必要的数据移动和计算，是提升连接查询性能的关键优化手段之一。