《大规模分布式计算深入解析》4.3 semi/anti join、runtime filter 与 bloom 下推

运行时过滤从 Build 侧收集约束,用于提前排除确定无匹配的 Probe 行。能否下推取决于连接语义、过滤到达时间和扫描实现。

4.3 semi/anti join、runtime filter 与 bloom 下推

运行时过滤从 Build 侧收集约束,用于提前排除确定无匹配的 Probe 行。能否下推取决于连接语义、过滤到达时间和扫描实现。

区分过滤器精度与查询正确性

对内等值 Join,安全的 Build 键超集允许丢弃确定不匹配的 Probe 行;最终还做真实键比较。对 LEFT JOIN 的左保留侧,直接丢弃未匹配行会改变结果。右侧含 NULL 时,普通等值 NOT EXISTS 与 SQL 三值逻辑下的 NOT IN 也可能不同。实验包的 SQLite 对照得到 3 与 0 行,误过滤保留侧时,LEFT JOIN 从 4 行降到 1 行。

假设 Bloom 对 100 万键分配每键 10 bit,原始位阵列约 1.25 MB,7 次 Hash 的理论假阳性率约 0.82%。若真实匹配比例 5%,预计进入 Probe 的比例约为 5% + 95% × 0.82% ≈ 5.78%。这不同于文件裁剪比例。Trino 的动态过滤可能以离散域或范围表达约束,检查 dynamicFilterAssignments、扫描侧动态过滤与运行统计。过滤来晚时,已经发出的 Split 可能无法追回。

实测:过滤域出现,扫描量仍相同

随附 Trino 484 实测中,开启后计划含 dynamicFilterAssignments,分析结果中能定位单值域 nationkey = 3。开关两次均执行 8 个 Customer Split,扫描侧报告 1500 行输入,结果同为 5 组共 69 条匹配。动态过滤可以存在于计划中而不降低当前数据源的扫描量。跨节点复现见第 13.1 节 。

实验与资料

下载卷六实验包 ,参照包内 README。src/ 下的 Java 8 教学模型 · sql-counterexamples.py 的语义对照 · trino-probe.py 的真实执行计划。本章架构或流程见本章机制图 。

Trino 动态过滤 · Trino SELECT 的 ORDER BY、OFFSET 与 FETCH

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图