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》
发表回复