vivo 互联网服务器团队 - Shuai Guangying
探索 Presto SQL 引擎 系列：第 1 篇《探索 Presto SQL 引擎(1)- 巧用 Antlr》介绍了 Antlr 的根本用法以及如何应用 Antlr4 实现解析 SQL 查问 CSV 数据，在第 2 篇《探索 Presto SQL 引擎(2)- 浅析 Join》联合了 Join 的原理，以及 Join 的原理，在 Presto 中的思路。
本文是系列第 3 篇，介绍基于 Antlr 实现 where 条件的解析原理，并比照了间接解析与代码生成实现两种实现思路的性能，经试验基于代码生成的实现相比间接解析有 3 倍的性能晋升。
一、背景问题
业务开发过程中，应用 SQL 进行数据筛选 (where 关键词) 和关联 (join 关键词) 是编写 SQL 语句实现业务需要最常见、最根底的能力。
在海量数据和响应工夫双重压力下，看似简略的数据筛选和关联在实现过程中面临十分多技术细节问题，在钻研解决这些问题过程中也诞生了十分乏味的数据结构和优化思维。比方 B 树、LSM 树、列式存储、动静代码生成等。
对于 Presto SQL 引擎，布尔表达式的判断是实现 where 和 join 解决逻辑中十分根底的能力。
本文旨在探索 where 关键词的实现思路，探索 where 语句外部实现的基本思路以及性能优化的根本思维。以 where 语句为例：where 筛选反对 and、or 和 not 三种根底逻辑，在三种根底逻辑的根底上，反对基于括号自定义优先级、表达式外部反对字段、函数调用。看似简略，实则别有洞天。值得深刻开掘学习。
二、应用 Antlr 实现 where 条件过滤
对于 Presto 查问引擎，其整体架构如下：
其中，Parser&Analyzer 就是 Antlr 的用武之地。任何的 SQL 语句，必须通过 Parser&Analyzer 这一步，所谓一夫当关万夫莫开。对于 Antlr 的背景及根底操作等内容，在《探索 Antlr 在 Presto 引擎的利用》一文已有形容，不再赘述。
本文仍然采纳驱动 Antlr 的三板斧来实现 SQL 语句对 where 条件的反对。
对于 where 条件，首先拆解 where 条件最简略的构造：
and 和 or 作为组合条件筛选的根本构造。
6 大比拟运算符 (大于，小于，等于，不等于，大于或等于，小于或等于) 作为根本表达式。
接下来就是应用 Antlr 的规范流程。
2.1 定义语法规定
应用 antlr 定义语法规定如下 (该规定基于 presto SQL 语法裁剪，残缺定义可参考 presto SelectBase.g4 文件)：
querySpecification
: SELECT selectItem (',' selectItem)*
(FROM relation (',' relation)*)?
(WHERE where=booleanExpression)?
;
...
booleanExpression
: valueExpression predicate[$valueExpression.ctx]? #predicated
| NOT booleanExpression #logicalNot
| left=booleanExpression operator=AND right=booleanExpression #logicalBinary
| left=booleanExpression operator=OR right=booleanExpression #logicalBinary
;
predicate[ParserRuleContext value]
: comparisonOperator right=valueExpression #comparison
;
即 where 条件前面附带一个 booleanExpression 表达式规定，booleanExpression 表达式规定反对根底的 valueExpression 预测、and 和 or 以及 not 条件组合。本文的目标是摸索外围思路，而非实现一个实现的 SQL 筛选能力，所以只解决 and 和 or 条件即可，以实现删繁就简，聚焦外围问题的目标。
2.2 生成语法解析代码
参照 Antlr 的官网文档，应用预处理好的 Antlr 命令解决 g4 文件，生成代码即可。
antlr4 -package org.example.antlr -no-listener -visitor .\SqlBase.g4
2.3 开发业务代码解决 AST
2.3.1 定义语法树节点
在理解了表达式形成后，先定义两个根底的 SQL 语法树节点，类图如下：
这两个类从构造上是同构的：左右各一个分支表达式，两头一个运算符。
2.3.2 构建语法树
在 AstBuilder 实现中，新增对 logicalBinary, comparison 相干语法的解析实现。这些工作都是如法炮制，没有什么难度。
@Override
public Node visitComparison(Select1Parser.ComparisonContext context)
{
return new ComparisonExpression(getLocation(context.comparisonOperator()),
getComparisonOperator(((TerminalNode) context.comparisonOperator().getChild(0)).getSymbol()),
(Expression) visit(context.value),
(Expression) visit(context.right));
}
@Override
public Node visitLogicalBinary(Select1Parser.LogicalBinaryContext context)
{
return new LogicalBinaryExpression(getLocation(context.operator),
getLogicalBinaryOperator(context.operator),
(Expression) visit(context.left),
(Expression) visit(context.right));
}通过下面的两步，一个 SQL 表达式就能转化成一个 SQL 语法树了。
2.3.3 遍历语法树
有了 SQL 语法树后，问题就自然而然浮现进去了：
a) 这个 SQL 语法树结构有什么用？
b) 这个 SQL 语法树结构该怎么用？
其实对于 SQL 语法树的利用场景，排除 SQL 引擎外部的逻辑，在咱们日常开发中也是很常见的。比方：SQL 语句的格式化，SQL 的拼写查看。
对于 SQL 语法树该怎么用的问题，能够通过一个简略的例子来说阐明：SQL 语句格式化。
在《探索 Antlr 在 Presto 引擎的利用》一文中，为了简化问题采取了间接拆解 antlr 生成的 AST 获取 SQL 语句中的表名称和字段名称，解决形式非常简单粗犷。实际上 presto 中有一种更为优雅的解决思路：AstVisitor。也就是设计模式中的访问者模式。
访问者模式定义如下：
封装一些作用于某种数据结构中的各元素的操作，它能够在不扭转这个数据结构的前提下定义作用于这些元素的新的操作。
这个定义落实到 SQL 语法树结构实现要点如下：即 SQL 语法树节点定义一个 accept 办法作为节点操作的入口 (参考 Node.accept() 办法)。定义个 AstVisitor 类用于标准拜访节点树的操作，具体的实现类继承 AstVisitor 即可。根底构造定义好过后，前面就是万变不离其宗了。
两个类外围框架代码如下：
public abstract class Node
{
/**
* Accessible for {@link AstVisitor}, use {@link AstVisitor#process(Node, Object)} instead.
*/
protected <R, C> R accept(AstVisitor<R, C> visitor, C context)
{return visitor.visitNode(this, context);
}
}
public abstract class AstVisitor<R, C>
{protected R visitStatement(Statement node, C context)
{return visitNode(node, context);
}
protected R visitQuery(Query node, C context)
{return visitStatement(node, context);
}
....
}例如最常见的 select * from table where 这类 SQL 语法，在 SelectBase.g4 文件中定义查问的外围构造如下：
querySpecification
: SELECT setQuantifier? selectItem (',' selectItem)*
(FROM relation (',' relation)*)?
(WHERE where=booleanExpression)?
(GROUP BY groupBy)?
(HAVING having=booleanExpression)?
;以格式化 SQL 语句为例，Presto 实现了 SqlFormatter 和 ExpressionFormatter 两个实现类。格式化这个语句的代码如下：
@Override
protected Void visitQuerySpecification(QuerySpecification node, Integer indent)
{process(node.getSelect(), indent);
if (node.getFrom().isPresent()) {append(indent, "FROM");
builder.append('\n');
append(indent, " ");
process(node.getFrom().get(), indent);
}
builder.append('\n');
if (node.getWhere().isPresent()) {append(indent, "WHERE" + formatExpression(node.getWhere().get(), parameters))
.append('\n');
}
if (node.getGroupBy().isPresent()) {append(indent, "GROUP BY" + (node.getGroupBy().get().isDistinct() ? "DISTINCT" : "") + formatGroupBy(node.getGroupBy().get().getGroupingElements())).append('\n');
}
if (node.getHaving().isPresent()) {append(indent, "HAVING" + formatExpression(node.getHaving().get(), parameters))
.append('\n');
}
if (node.getOrderBy().isPresent()) {process(node.getOrderBy().get(), indent);
}
if (node.getLimit().isPresent()) {append(indent, "LIMIT" + node.getLimit().get())
.append('\n');
}
return null;
}
代码实现逻辑清晰明了，可读性极强。
同理，实现 where 条件解析的外围在于比拟条件表达式的解决 (visitComparisonExpression) 和逻辑条件表达式的解决(visitLogicalBinaryExpression)。同样出于聚焦外围流程的思考，咱们只实现相似于 a > 0 or b < 10 这种整型字段的过滤。
对于 and 和 or 构造，因为是树形构造，所以会用到递归，即优先解决叶子节点再以层层向上汇总。解决解决逻辑如下代码所示：
/**
* 解决比拟表达式
* @param node
* @param context
* @return
*/
@Override
protected Void visitComparisonExpression(ComparisonExpression node, Map<String,Long> context) {Expression left = node.getLeft();
Expression right = node.getRight();
String leftKey = ((Identifier) left).getValue();
Long rightKey = ((LongLiteral) right).getValue();
Long leftVal = context.get(leftKey);
if(leftVal == null){stack.push(false);
}
ComparisonExpression.Operator op = node.getOperator();
switch (op){
case EQUAL:
stack.push(leftVal.equals(rightKey));break;
case LESS_THAN:
stack.push(leftVal < rightKey);;break;
case NOT_EQUAL:
stack.push(!leftVal.equals(rightKey));break;
case GREATER_THAN:
stack.push(leftVal>rightKey);break;
case LESS_THAN_OR_EQUAL:
stack.push(leftVal<=rightKey);break;
case GREATER_THAN_OR_EQUAL:
stack.push(leftVal>=rightKey);break;
case IS_DISTINCT_FROM:
default:
throw new UnsupportedOperationException("not supported");
}
return null;
}这里的实现非常简单，基于栈存储叶子节点 (ComparisonExpression) 计算的后果，递归回溯非叶子节点 (LogicalBinaryExpression) 时从栈中取出栈顶的值，进行 and 和 or 的运算。阐明一下：其实递归的实现形式是能够不应用栈，间接返回值即可。这里基于栈实现是为了跟下文代码生成的逻辑从构造上保持一致，不便比照性能。
2.4 验证表达式执行
为了验证上述计划执行后果，定义一个简略的过滤规定，生成随机数验证是否实现对表达式逻辑的判断。
// antlr 解决表达式语句，生成 Expression 对象
SqlParser sqlParser = new SqlParser();
Expression expression = sqlParser.createExpression("a>1 and b<2");
// 基于 AstVisitor 实现
WhereExpFilter rowFilter = new WhereExpFilter(expression);
Random r = new Random();
for(int i=0;i<10;i++){Map<String,Long> row = new HashMap<>();
row.put("a", (long) r.nextInt(10));
row.put("b", (long) r.nextInt(10));
System.out.println("exp: a>1 and b<2, param:"+row+", ret:"+rowFilter.filter(row));
}
// ====== 执行后果如下
/**
exp: a>1 and b<2, param:{a=9, b=8}, ret:false
exp: a>1 and b<2, param:{a=7, b=3}, ret:false
exp: a>1 and b<2, param:{a=0, b=7}, ret:false
exp: a>1 and b<2, param:{a=6, b=0}, ret:true
exp: a>1 and b<2, param:{a=2, b=0}, ret:true
exp: a>1 and b<2, param:{a=9, b=0}, ret:true
exp: a>1 and b<2, param:{a=3, b=6}, ret:false
exp: a>1 and b<2, param:{a=8, b=7}, ret:false
exp: a>1 and b<2, param:{a=6, b=1}, ret:true
exp: a>1 and b<2, param:{a=4, b=6}, ret:false
*/通过上述的解决流程以及执行后果的验证，能够确定基于 Antlr 能够非常简单实现 where 条件的过滤，这跟 antlr 实现四则运算能力有殊途同归之妙。然而通过对 Presto 源码及相干文档浏览，却发现实际上对于条件过滤及 JOIN 的实现是另辟蹊径。这是为什么呢？
三、基于 AstVisitor 间接解析 SQL 条件问题
在解答 Presto 的实现思路之前，须要先铺垫两个根底的常识。一个是 CPU 的流水线和分支预测，另一个是 JVM 的办法内联优化。
3.1 CPU 流水线和分支预测
计算机组成原理中对于 CPU 指令的执行，如下图所示：
即在晚期 CPU 执行指令采纳串行的形式，为了晋升 CPU 的吞吐量，在 RISC 的架构中通过流水线的形式实现了多条指令重叠进行操作的一种准并行处理实现技术。通过下面的图示，能够看出：减少一条流水后，单位工夫执行的指令数量就翻倍，即性能晋升了 1 倍。
当然这是现实的状况，事实中会遇到两类问题：
1）下一条指令的执行依赖上一条指令执行的后果。
2）遇到分支必须等条件计算实现才晓得分支是否执行。
对于问题 1，通过乱序执行的办法可能将性能晋升 20%~30%。对于问题 2，则是通过分支预测的办法来应答。
对于利用分支预测原理晋升性能，有两个有意思的案例。
案例 1：
stackoverflow 上有个驰名的问题：why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array。即对于有序数组和无序数组的遍历，执行工夫差不多有 2~3 倍的差距。
在笔者的计算机上，运行案例后果合乎形容。须要留神的是用 system.nanotime()来掂量，system.currenttimemillis()精度不够。
案例 2：
Dubbo 源码 ChannelEventRunnable 中通过将 switch 代码优化成 if 取得了近似 2 倍的效率晋升。
简略总结一下，代码中的分支逻辑会影响性能，通过一些优化解决 (比方数据排序 / 热点代码前置) 可能晋升分支预测的成功率，从而晋升程序执行的效率。
3.2 JVM 办法内联优化
JVM 是基于栈的指令执行策略。一个函数调用除了执行本身逻辑的开销外，还有函数执行上下文信息保护的额定开销，例如：栈帧的生成、参数字段入栈、栈帧的弹出、指令执行地址的跳转。JVM 内联优化对于性能的影响十分大。
这里有一个小试验，对于同一段代码失常执行和禁用内联优化(-XX:CompileCommand=dontinline,
test/TestInline.addOp), 其性能差距差不多有 6 倍。
代码样例及数据如下：
public class TestInline {public int addOp(int a,int b){return a+b;}
@Benchmark
public int testAdd(){
int sum=0;
for(int i=0;i<100000;i++){sum=addOp(sum,i);
}
return sum;
}
public static void main(String[] args) throws RunnerException {Options options = new OptionsBuilder()
.warmupIterations(2).measurementIterations(2)
.forks(1).build();
new Runner(options).run();}
}
// 执行后果如下：/**
Benchmark Mode Cnt Score Error Units
TestInline.testAdd thrpt 2 18588.318 ops/s(失常执行)
TestInline.testAdd thrpt 2 3131.466 ops/s(禁用内联)
**/对于 Java 语言，办法内联优化也是有老本的。所以，通常热点代码 / 办法体较小的代码 / 用 private、static、final 润饰的代码才可能内联。过大的办法体和面向对象的继承和多态都会影响办法的内联，从而影响性能。
对于 SQL 执行引擎中最常见的 where 和 join 语句来说，因为执行过程中须要判断数据类型、操作符类型，简直每行数据的解决都是在影响 CPU 的分支预测，而且每个数据类型，每种操作符都都须要封装独立的解决逻辑。如果采纳间接解析 SQL 语句的形式，势必对分支预测和办法内联影响极大。为了晋升性能，升高分支预测失败和办法调用的开销，动静代码生成的计划就横空出世了。
四、基于动静代码生成实现 where 条件过滤
在介绍应用动静代码生成实现 where 条件过滤前，有必要对字节码生成技术的产生背景，Java 语言特有的劣势以及相干的基本操作进行介绍。
4.1 字节码生成的办法
Java 虚拟机标准有两个关键点：平台无关性和语言无关性。
平台无关性 实现了一次编写，到处运行的指标,。即不受限于操作系统是 Windows 还是 Linux。
语言无关性 使得 JVM 下面运行的语言不限于 Java, 像 Groovy, Scala，JRuby 都成为了 JVM 生态的一部分。而可能实现平台无关性和语言无关性的的根底就是基于栈执行指令的虚拟机和字节码存储技术。
对于任意一门编程语言：程序剖析、程序生成、程序转换技术在开发中利用宽泛，通常利用在如下的场景中：
- 程序剖析：基于语法和语义剖析，辨认潜在的 bug 和无用代码，或者进行逆向工程，钻研软件外部原理(比方软件破解或开发爬虫)
- 程序生成：比方传统的编译器、用于分布式系统的 stub 或 skeleton 编译器或者 JIT 编译器等。
- 程序转换： 优化或者混同代码、插入调试代码、性能监控等。
对于 Java 编程语言，因为有 Java 源码 - 字节码 - 机器码三个层级，所以程序剖析、程序生成、程序转换的技术落地能够有两个切入点：Java 源码或者编译后的 Class。抉择编译后的 Class 字节码有如下的劣势：
- 无需源码。这对于闭源的商业软件也能十分不便实现跨平台的性能监控等需要。
- 运行时剖析、生成、转换。只有在 class 字节码被加载到虚拟机之前解决完就能够了，这样整个解决流程就对用户通明了。
程序生成技术在 Java 中通常有另一个名字：字节码生成技术。这也表明了 Java 语言选择的切入点是编译后的 Class 字节码。
字节码生成技术在 Java 技术栈中利用也十分宽泛，比方：Spring 我的项目的 AOP，各种 ORM 框架，Tomcat 的热部署等场景。Java 有许多字节码操作框架，典型的有 asm 和 javassist、bytebuddy、jnif 等。
通常出于性能的考量 asm 用得更为宽泛。间接应用 asm 须要了解 JVM 的指令，对用户来说学习门槛比拟高。Facebook 基于 asm 进行了一层封装，就是 airlift.bytecode 工具了。基于该工具提供的动静代码生成也是 presto 性能保障的一大利器。用户应用 airlift.bytecode 能够防止间接写 JVM 指令。然而该框架文档较少，通常操作只能从其 TestCase 和 presto 的源码中学习，本大节简略总结应用 airlift.bytecode 生成代码的根本用法。
通常，咱们了解了变量、数组、管制逻辑、循环逻辑、调用内部办法这几个点，就能够操作一门编程语言了。至于外围库，其作用是辅助咱们更高效地开发。对于应用 airlift.bytecode 框架，了解定义类、定义方法(分支、循环和办法调用)、办法执行这些罕用操作就可能满足大部分业务需要：
Case 1: 定义类
private static final AtomicLong CLASS_ID = new AtomicLong();
private static final DateTimeFormatter TIMESTAMP_FORMAT = DateTimeFormatter.ofPattern("YYYYMMdd_HHmmss");
private String clazzName;
private ClassDefinition classDefinition;
public ByteCodeGenDemo(String clazzName){this.clazzName=clazzName;}
public static ParameterizedType makeClassName(String baseName, Optional<String> suffix)
{
String className = baseName
+ "_" + suffix.orElseGet(() -> Instant.now().atZone(UTC).format(TIMESTAMP_FORMAT))
+ "_" + CLASS_ID.incrementAndGet();
return typeFromJavaClassName("org.shgy.demo.$gen." + toJavaIdentifierString(className));
}
public void buildClass(){
ClassDefinition classDefinition = new ClassDefinition(a(PUBLIC, FINAL),
makeClassName(clazzName,Optional.empty()),
type(Object.class));
this.classDefinition=classDefinition;
}
通过下面的代码，就定义了一个 public final 润饰的类, 而且确保程序运行汇总类名不会反复。
Case 2: 定义方法 –IF 管制逻辑
/**
* 生成 if 分支代码
* if(a<0){* System.out.println(a +"a<0");
* }else{* System.out.println(a +"a>=0");
* }
* @param methodName
*/
public void buildMethod1(String methodName){Parameter argA = arg("a", int.class);
MethodDefinition method = classDefinition.declareMethod(a(PUBLIC, STATIC),
methodName,
type(void.class),
ImmutableList.of(argA));
BytecodeExpression out = getStatic(System.class, "out");
IfStatement ifStatement = new IfStatement();
ifStatement.condition(lessThan(argA,constantInt(0)))
.ifTrue(new BytecodeBlock()
.append(out.invoke("print", void.class, argA))
.append(out.invoke("println", void.class, constantString("a<0")))
)
.ifFalse(new BytecodeBlock()
.append(out.invoke("print", void.class, argA))
.append(out.invoke("println", void.class, constantString("a>=0")))
);
method.getBody().append(ifStatement).ret();}
Case 3: 定义方法–Switch 管制逻辑
/**
* 生成 switch 分支代码
* switch (a){
* case 1:
* System.out.println("a=1");
* break;
* case 2:
* System.out.println("a=2");
* break;
* default:
* System.out.println("a=others");
* }
* @param methodName
*/
public void buildMethod2(String methodName){Parameter argA = arg("a", int.class);
MethodDefinition method = classDefinition.declareMethod(a(PUBLIC, STATIC),
methodName,
type(void.class),
ImmutableList.of(argA));
SwitchStatement.SwitchBuilder switchBuilder = new SwitchStatement.SwitchBuilder().expression(argA);
switchBuilder.addCase(1, BytecodeExpressions.print(BytecodeExpressions.constantString("a=1")));
switchBuilder.addCase(2,BytecodeExpressions.print(BytecodeExpressions.constantString("a=2")));
switchBuilder.defaultCase(invokeStatic(ByteCodeGenDemo.class,"defaultCase", void.class));
method.getBody().append(switchBuilder.build()).ret();}
public static void defaultCase(){System.out.println("a=others");
}
Case 4: 定义方法 -ForLoop 逻辑
/**
* 生成循环逻辑代码
* int sum=0;
* for(int i=s;i<=e;i++){
* sum+=i;
* System.out.println("i="+i+",sum="+sum);
* }
* @param methodName
*/
public void buildMethodLoop(String methodName){Parameter argS = arg("s", int.class);
Parameter argE = arg("e", int.class);
MethodDefinition method = classDefinition.declareMethod(a(PUBLIC, STATIC),
methodName,
type(int.class),
ImmutableList.of(argS, argE));
Scope scope = method.getScope();
Variable i = scope.declareVariable(int.class,"i");
Variable sum = scope.declareVariable(int.class,"sum");
BytecodeExpression out = getStatic(System.class, "out");
ForLoop loop = new ForLoop()
.initialize(i.set(argS))
.condition(lessThanOrEqual(i, argE))
.update(incrementVariable(i,(byte)1))
.body(new BytecodeBlock()
.append(sum.set(add(sum,i)))
.append(out.invoke("print", void.class, constantString("i=")))
.append(out.invoke("print", void.class, i))
.append(out.invoke("print", void.class, constantString(",sum=")))
.append(out.invoke("println", void.class,sum))
);
method.getBody().initializeVariable(i).putVariable(sum,0).append(loop).append(sum).retInt();}
Case 5: 生成类并执行办法
public void executeLoop(String methodName) throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
// invoke
Class<?> clazz = classGenerator(new DynamicClassLoader(this.getClass().getClassLoader())).defineClass(this.classDefinition,Object.class);
Method loopMethod = clazz.getMethod(methodName, int.class,int.class);
loopMethod.invoke(null,1,10);
}
Case 6: 操作数据结构 - 从 Map 数据结构取值
public void buildMapGetter(String methodName){Parameter argRow = arg("row", Map.class);
MethodDefinition method = classDefinition.declareMethod(a(PUBLIC, STATIC),
methodName,
type(void.class),
of(argRow));
BytecodeExpression out = getStatic(System.class, "out");
Scope scope = method.getScope();
Variable a = scope.declareVariable(int.class,"a");
// 从 map 中获取 key=aa 对应的值
method.getBody().append(out.invoke("print", void.class, argRow.invoke("get",Object.class,constantString("aa").cast(Object.class)))).ret();}
// 代码执行
public void executeMapOp(String methodName) throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
// invoke
Class<?> clazz = classGenerator(new DynamicClassLoader(this.getClass().getClassLoader())).defineClass(this.classDefinition,Object.class);
Method loopMethod = clazz.getMethod(methodName, Map.class);
Map<String,Integer> map = Maps.newHashMap();
map.put("aa",111);
loopMethod.invoke(null,map);
}通过上述的几个 Case, 咱们理解了 airlift.bytecode 框架的根本用法。如果想更深入研究，须要参考浏览 ASM 相干的材料，毕竟 airlift.bytecode 是基于 ASM 构建的。然而在本文的钻研中，到这里就够用了。
4.2 基于动静代码生成实现 where 条件过滤
在相熟动静代码生成框架的根本应用办法后，咱们就能够应用该工具实现具体的业务逻辑了。同样地，咱们基于 AstVisitor 实现生成 where 条件过滤的字节码。
整体代码框架跟后面的实现保持一致，须要解决问题的关键点在于字节码生成的逻辑。对于 where 条件的查问语句，实质上是一个二叉树。对于二叉树的遍历，用递归是最简略的办法。递归从某种程度上，跟栈的操作是统一的。
对于实现 where 条件过滤代码生成，实现逻辑形容如下：
输出：antlr 生成的 expression 表达式
输入：airlift.bytecode 生成的 class
s1：定义清晰生成类的根底配置：类名、修饰符等信息
s2：定义一个栈用于存储比拟运算(ComparisonExpression) 计算结果
s3：应用递归形式遍历 expression
s4：对于叶子节点(ComparisonExpression)，代码生成逻辑如下：从办法定义的参数中取出对应的值，依据比拟符号生成计算代码，并将计算结果 push 到 stack
s5：对于非叶子节点(LogicalBinaryExpression), 代码生成逻辑如下：取出栈顶的两个值，进行 and 或 or 操作运算，将计算结果 push 到 stack
s6：当递归回退到根节点时，取出栈顶的值作为计算的最终后果
s7：基于类和办法的定义生成 Class
实现字节码生成代码如下：
/**
* 生成比拟条件语句
**/
@Override
protected Void visitComparisonExpression(ComparisonExpression node, MethodDefinition context) {ComparisonExpression.Operator op = node.getOperator();
Expression left = node.getLeft();
Expression right = node.getRight();
if(left instanceof Identifier && right instanceof LongLiteral){String leftKey = ((Identifier) left).getValue();
Long rightKey = ((LongLiteral) right).getValue();
Parameter argRow = context.getParameters().get(0);
Variable stack = context.getScope().getVariable("stack");
BytecodeBlock body = context.getBody();
BytecodeExpression leftVal = argRow.invoke("get", Object.class,constantString(leftKey).cast(Object.class)).cast(long.class);
BytecodeExpression cResult;
switch (op){
case EQUAL:
cResult = equal(leftVal,constantLong(rightKey));
break;
case LESS_THAN:
cResult = lessThan(leftVal,constantLong(rightKey));
break;
case GREATER_THAN:
cResult =greaterThan(leftVal,constantLong(rightKey));
break;
case NOT_EQUAL:
cResult = notEqual(leftVal,constantLong(rightKey));
break;
case LESS_THAN_OR_EQUAL:
cResult = lessThanOrEqual(leftVal,constantLong(rightKey));
break;
case GREATER_THAN_OR_EQUAL:
cResult = greaterThanOrEqual(leftVal,constantLong(rightKey));
break;
default:
throw new UnsupportedOperationException("not implemented");
}
body.append(stack.invoke("push",Object.class, cResult.cast(Object.class)));
return null;
}else{throw new UnsupportedOperationException("not implemented");
}
}代码实现实现后，为了验证解决逻辑是否失常，能够用两种实现的形式运行同一个测试用例，确保同样的 where 表达式在同样的参数下执行后果统一。
为了验证两种实现形式执行的性能，这里引入 JMH 框架，基于 JMH 框架生成性能验证代码：
@BenchmarkMode(Mode.Throughput)
@Fork(1)
@State(value = Scope.Benchmark)
public class RowFilterBenchmark {
private RowFilter filter1;
private RowFilter filter2;
private List<Map<String,Long>> dataSet = Lists.newArrayListWithCapacity(100000);
@Setup
public void init(){
// antlr 解决表达式语句，生成 Expression 对象
SqlParser sqlParser = new SqlParser();
Expression expression = sqlParser.createExpression("a>5 and b<5");
// 基于 AstVisitor 实现
this.filter1 = new WhereExpFilter(expression);
// 基于 AstVisitor 实现
ExpressionCodeCompiler compiler = new ExpressionCodeCompiler();
Class clazz = compiler.compile(expression);
try {this.filter2 = (RowFilter) clazz.newInstance();} catch (InstantiationException e) {e.printStackTrace();
} catch (IllegalAccessException e) {e.printStackTrace();
}
Random r = new Random();
for(int i=0;i<100000;i++){Map<String,Long> row = new HashMap<>();
row.put("a", (long) r.nextInt(10));
row.put("b", (long) r.nextInt(10));
dataSet.add(row);
}
}
@Benchmark
public int testAstDirect() {
int cnt =0;
for(Map<String,Long> row:dataSet){boolean ret = filter1.filter(row);
if(ret){cnt++;}
}
return cnt;
}
@Benchmark
public int testAstCompile() {
int cnt =0;
for(Map<String,Long> row:dataSet){boolean ret = filter2.filter(row);
if(ret){cnt++;}
}
return cnt;
}
public static void main(String[] args) throws RunnerException {Options opt = new OptionsBuilder()
.include(RowFilterBenchmark.class.getSimpleName())
.build();
new Runner(opt).run();}
}应用 10 万量级的数据集，性能验证的后果如下：
Benchmark Mode Cnt Score Error Units
RowFilterBenchmark.testAstCompile thrpt 5 211.298 ± 30.832 ops/s
RowFilterBenchmark.testAstDirect thrpt 5 62.254 ± 8.269 ops/s通过上述的验证数据，能够得出初步的论断，对于简略的比拟表达式，基于代码生成的形式相比间接遍历的形式大概有 3 倍左右的性能晋升。比照间接基于 AstVisitor 实现 where 条件过滤，代码生成无需对表达式中的操作符进行判断，间接基于表达式动静生成代码，裁剪了许多判断的分支。
五、总结
本文摸索了 SQL 引擎中 where 表达式的实现思路，基于 antlr 实现了两种形式：
其一是间接遍历表达式生成的 Expression；
其二是基于表达式生成的 Expression 通过 airlift.bytecode 动静生成字节码。
本文初步剖析了 Presto 中利用代码生成实现相干业务逻辑的出发点及背景问题。并应用 JMH 进行了性能测试，测试结果表明对于同样的实现思路，基于代码生成形式相比间接实现约有 3 倍的性能晋升。
实际上 Presto 中应用代码生成的形式相比本文形容要简单得多，跟文本实现的形式并不一样。基于本文的摸索更多在于摸索钻研根本的思路，而非再造一个 Presto。
只管应用动静代码生成对于性能的晋升成果显著，然而在业务实际中，须要衡量应用代码生成的 ROI，毕竟应用代码生成实现的逻辑，代码可读性和可维护性相比间接编码要简单很多，开发复杂度也简单很多。就像 C 语言嵌入汇编一样，代码生成技术在业务开发中应用同样须要慎重考虑，应用切当能获得事倍功半的成果，使用不当或滥用则会为我的项目埋下不可预知的定时炸弹。
参考资料：
- 《计算机科学导论》
- 《深刻了解 Java 虚拟机》
- 《asm4-guide》