今天查看 Spark SQL 源码时发现针对二元逻辑表达式解析采用了平衡二叉树以规避左递归树的性能下降问题。布尔表达式的语法规则定义位于 SqlBase.g4 at v2.4.4:
1 | booleanExpression |
二元逻辑表达式解析即 logicalBinary
规则解析的源码位于 AstBuilder.scala at v2.4.4:
1 | /** |
核心处理逻辑即为最后这部分,将表达式列表进行自顶向下的构建,以使树的高度尽可能低,case 0
及 case 1
即为递归出口,可以看出这段代码还是比较妙的。