《大规模分布式计算深入解析》2.1 表达式树与解释开销

表达式树把过滤与投影条件拆成节点,每行都要从根到叶逐节点求值。本节用一棵 9 节点表达式树、100 万行算出 900 万次节点求值,按每节点 4ns 得 36ms 解释成本;并拆解虚调用、类型检查与无法跨节点优化这三类开销,说明解释执行适合一次性查询,lab 用两个用例断言。

2.1 表达式树与解释开销

1.2 把算子之间的调用从每行一次降到每批一次,但算子内部还有一层开销没有处理:每一行仍要把表达式树从根到叶走一遍。过滤条件 price * qty > 100 AND region = 'east' 不是一个整体,而是九个节点组成的树;解释器对每个节点做一次分派、一次求值、一次类型检查。

这一节算清解释执行的账:100 万行、9 个节点、每节点 4ns,总共 36ms。下一节再看代码生成如何把这 36ms 压到 6ms。

一条谓词如何变成树

SQL 里的表达式在解析后被组织成树:内部节点是运算,叶子是列引用或常量。上面那条谓词可以画成:

AND
├── >
│   ├── *
│   │   ├── price
│   │   └── qty
│   └── 100
└── =
    ├── region
    └── east

数一下节点:AND、>、*、price、qty、100、=、region、east,正好 9 个。lab 用例 10 用的就是这个规模。

节点类型数量求值工作
逻辑运算1先算子节点,再短路判断
比较运算2比较两个子节点的值
算术运算1乘法
列引用2从当前行取出字段
常量3直接返回值

树的结构决定了求值顺序,也决定了开销分布。叶子节点看起来最便宜,但它们要访问当前行的列,实际成本不一定低;内部节点则要等待子节点返回,形成一条从叶到根的依赖链。

900 万次节点求值

解释执行的第一个数字是节点访问次数。用例 10 的口径很直接:每行把整棵树求值一次。

节点求值次数 = 行数 × 节点数
             = 1,000,000 × 9
             = 9,000,000 次
量取值来源
输入行数1,000,000统一场景
表达式节点数9上述谓词
节点求值次数9,000,000用例 10

900 万次不是 900 万条指令,而是 900 万次「按节点类型分派」。每个节点都要先判断自己是什么类型,再决定调用哪个求值分支,这个判断本身就是解释器的主要成本之一。

每次 4ns:36ms 的解释成本

lab 用例 11 给每次节点求值估了 4ns,包含分派、取值与基本运算:

// 简化后的树遍历求值:每个节点一次 switch 分派
static Object eval(Node node, Row row) {
    switch (node.kind) {
        case COLUMN:   return row.get(node.index);
        case CONST:    return node.value;
        case MULTIPLY: return (Long) eval(node.left, row) * (Long) eval(node.right, row);
        case GREATER:  return (Long) eval(node.left, row) > (Long) eval(node.right, row);
        case AND:      return (Boolean) eval(node.left, row) && (Boolean) eval(node.right, row);
        default:       throw new IllegalStateException("unsupported: " + node.kind);
    }
}
解释成本 = 行数 × 节点数 × 每节点成本
         = 1,000,000 × 9 × 4ns
         = 36,000,000ns
         = 36ms
量取值
节点求值次数9,000,000
每节点成本4ns
解释执行成本36ms

36ms 是单条表达式的成本。一条查询里通常有多个过滤、多个投影、多个聚合表达式,节点数会叠加;如果每行要算五条 9 节点表达式,解释成本就是 180ms 量级(按 36ms 线性叠加推算)。

4ns 花在哪里

把一次节点求值拆开,能看到解释器无法回避的三类工作:

开销具体动作能否消除
类型分派switch 或虚方法决定节点类型编译后可消除
类型检查子节点返回值装箱、强转编译后可特化
缓存失效树节点分散在堆上,访存不连续编译后指令局部性更好

分派是最大的一块。解释器每到一个节点都要问「你是什么」,而编译执行在生成代码时就已经知道每个节点该做什么,运行时不再需要这个问题。类型检查也是同理:解释器拿到的是 Object,必须装箱与强转;编译后可以直接用 long、boolean 等原生类型。

节点数就是成本杠杆

在行数固定的前提下,解释成本与节点数成正比。下面按每节点 4ns 做公式推导:

节点数100 万行求值次数解释成本
55,000,00020ms(推算)
99,000,00036ms(用例 11)
1515,000,00060ms(推算)

这条线性关系给出两个优化方向:一是减少行数(更早过滤、更好的分区裁剪),二是减少每行要走的节点数(常量折叠、谓词下推、公共子表达式消除)。两者都不需要改执行模型,属于查询优化器的工作。

但线性关系也说明:只要还在解释执行,节点数降不下去的部分就会一直付费。把 9 个节点优化到 5 个能省 16ms,但剩下的 20ms 仍然按行数增长。要突破这条线,只能换执行方式。

为什么解释执行仍然是默认选择

既然编译更快,为什么大多数引擎不把所有表达式都编译?因为编译有固定成本,而且表达式千变万化:

因素解释执行编译执行
启动成本几乎为零一次编译,几十毫秒量级
表达式变化直接换树需要重新编译或缓存
实现复杂度低高,涉及代码生成与回退
调试难度低,可打印树高,要看生成代码
短查询更合适编译成本盖过收益

解释执行的优势是「零启动」。一条只扫一万行的查询,36ms 的树遍历按比例只有 0.36ms;如果先花 20ms 编译,总时间反而变成 20ms 量级。这个反噬在 2.3 会用具体用例算清楚。

解释与编译的分界

场景建议原因
一次性 ad-hoc 查询解释编译成本无法摊销
重复执行的热路径编译或代码生成编译成本可摊到多行多次
复杂 UDF、未知类型解释编译器难以特化
简单过滤与投影编译表达式结构固定,收益明显
极短查询解释启动成本优先

分界不看「表达式复杂度」,而看「同一份表达式要执行多少次」。执行次数足够多,编译的固定成本才能被摊薄;只跑一次,解释的零启动就是优势。2.2 会给出编译后每行 6ns、6ms 的账本,2.3 再补上 20ms 编译成本的反例。

短路求值能省多少

上面的 900 万次与 36ms 是「整棵树每行都走完」的口径,也是解释成本的上界。真实的 AND 会短路:左子树为假时,右子树根本不求值。前面那棵树的结构是 AND + 左 5 节点 + 右 3 节点,设左子树通过率为 p,则每行求值节点数为 6 + 3p:

左子树通过率每行节点数100 万行总求值解释成本(按 4ns 推算)
100%99,000,00036ms(用例 11)
50%7.57,500,00030ms
30%6.96,900,00027.6ms

短路能把成本压低,但压不到零:AND 节点与左子树每行都要走,这部分是 6 个节点的固定开销;右子树再便宜,也只能省下 3 个节点里的一部分。lab 用 9 节点全遍历作为上界,正是为了给出一个不依赖数据分布的稳定口径。

这也解释了为什么 2.1 的 Java 片段里 case AND 用了 &&:语言层面的短路是解释器自带的优化,但它只作用于布尔逻辑,无法消除类型分派与装箱——这两项才是 4ns 里的主体。

三个常见误解

误解一:表达式求值的开销可以忽略,瓶颈总在扫描和网络。 真相:100 万行、9 节点就是 900 万次求值、36ms;多表达式叠加后,解释成本会进入百毫秒量级。

误解二:解释执行慢是因为 Java 或解释器语言慢。 真相:慢在逐节点的类型分派、装箱与强转,换成 C++ 写树遍历同样要付这些成本,根因是执行方式而不是宿主语言。

误解三:表达式树只用于 WHERE 过滤。 真相:投影表达式、JOIN 条件、聚合参数、排序键都走同一套树求值,节点数会跨算子累加。

一句话总结本节

表达式树把谓词拆成 9 个节点,100 万行要执行 900 万次节点求值;按每节点 4ns 计算是 36ms 解释成本,主要花在类型分派、装箱强转与不连续的树节点访存上。解释执行胜在零启动,适合一次性与短查询;重复执行的热路径必须靠代码生成把这 36ms 压下去。

上游实现参照

Spark 3.5.7 WholeStageCodegenExec

本节 lab

下载卷五 Java 8 实验 · 实验运行与版本说明

在 bd-engine-lab 中验证表达式树的求值次数与解释成本:

  • 源码:src/exec/Exec.java 与 src/exec/ExecSuite.java。
  • 运行:cd bd-engine-lab && mkdir -p out && javac -d out $(find src -name '*.java') && java -cp out lab.RunAll。
  • 断言:用例 10 验证「9 节点表达式树、100 万行,共 900 万次节点求值」;用例 11 验证「900 万次 × 每节点 4ns = 36ms 解释执行成本」。
  • 整卷 runner 的预期汇总为 TOTAL: 116 passed, 0 failed。

对应本节判断链:看到过滤与投影逐行变慢 → 把谓词拆成 9 节点表达式树 → 算出 900 万次节点求值与 36ms 解释成本 → 成本随节点数线性增长、无法靠调参消除 → 一次性查询保留解释,热路径转向代码生成。

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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