Amazon L6：查询树常量折叠，什么才是“安全节点”？

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练区分Query结构与其中Expression；具体operator、NULL、overflow与error策略由目标语义定义，不假定全部Python算术等价SQL。
• 仅折叠经过类型检查、参数常量且确定性无副作用的表达式；查询依赖数据或外部环境不能当常量。
• 不把整棵subquery作为scalar常量执行，数据读取、关联变量、权限和执行快照均可能改变结果。

解题路线

1. 遍历先递归每个nested query，再后序访问projection/predicate里的表达式子节点。表达式子节点先被折成literal，父节点才有机会成为全常量；不靠字符串替换。
2. 安全谓词需核类型已绑定、运算确定性、无副作用、求值时点相同和异常策略一致。now/random/sequence等不能仅因无参数就折叠；参数或session上下文相关函数也须分类。
3. NULL与三值逻辑不能用普通布尔算术替代。比如NULL比较结果为UNKNOWN，不自动等于FALSE；投影值和WHERE过滤合同不同，需由目标语义的常量解释器评价。
4. 把1/0提前求值可能把运行时错误变编译时错误，或让原本不可执行的短路分支报错。0*x也不一定可删x，x可能报错或有副作用；只有语言许可的纯表达式与求值规则下才能用代数简化。
5. rewrite返回新不可变节点或copy-on-write，保留source location、type和诊断信息。查询DAG共享节点可按(node_id,绑定环境)memo；仅node_id缓存会把不同关联上下文混在一起。
6. 验证以原树和重写树在同环境下的值、NULL与错误行为作差分；覆盖嵌套query、未知变量、volatile function、overflow和分支。性能成功不能替代语义等价。

手动走一遍

训练投影Add(Literal(2),Literal(3))可变成5；Add(Column(price),Literal(3))保留。Random()+1不折，NULL=1不能变false，Case(false,1/0,2)的错误策略取决于正式语言合同，不能一律先算1/0。

规模与取舍

纯树节点N后序访问O(N)加常量计算成本，栈/新树O(N)最坏；大整数、巨大literal结果与共享DAG另设资源预算，避免编译期折叠造成内存爆炸。

易错点与追问

容易失分的边界

• 无参数函数都视常量。
• Python truthiness替代SQL三值逻辑。
• 代数恒等忽略错误与副作用。
• 直接执行未知子查询。

继续深挖

• 如何定义fold与simplify区别？
• 相同DAG在不同scope共享怎么memo？
• 巨大常量表达式何时停止折叠？