探究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 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");
}
}
生成具體的and 和or操作：
/**
* 生成比較and or語句
**/
@Override
protected Void visitLogicalBinaryExpression(LogicalBinaryExpression node, MethodDefinition context)
{
Expression left = node.getLeft();
Expression right = node.getRight();
// 處理左子樹
if(left instanceof ComparisonExpression){
visitComparisonExpression((ComparisonExpression)left,context);
}else if(left instanceof LogicalBinaryExpression){
visitLogicalBinaryExpression((LogicalBinaryExpression) left,context);
}else{
throw new UnsupportedOperationException("not implemented");
}
// 處理右子樹
if(right instanceof ComparisonExpression){
visitComparisonExpression((ComparisonExpression)right,context);
}else if(right instanceof LogicalBinaryExpression){
visitLogicalBinaryExpression((LogicalBinaryExpression) right,context);
}else{
throw new UnsupportedOperationException("not implemented");
}
// 根據運算符生成字節碼
LogicalBinaryExpression.Operator op = node.getOperator();
Variable stack = context.getScope().getVariable("stack");
BytecodeExpression result;
switch (op){
case AND:
result = stack.invoke("push",Object.class,
and(
stack.invoke("pop",Object.class).cast(boolean.class),
stack.invoke("pop",Object.class).cast(boolean.class)
).cast(Object.class));
break;
case OR:
result = stack.invoke("push",Object.class,
or(
stack.invoke("pop",Object.class).cast(boolean.class),
stack.invoke("pop",Object.class).cast(boolean.class)
).cast(Object.class));
break;
default:
throw new UnsupportedOperationException("not implemented");
}
context.getBody().append(result);
return null;
}
代碼實現完成后，為了驗證處理邏輯是否正常，可以用兩種實現的方式運行同一個測試用例，確保同樣的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語言嵌入匯編一樣，代碼生成技術在業務開發中使用同樣需要慎重考慮，使用得當能取得事半功倍的效果，使用不當或濫用則會為項目埋下不可預知的定時炸彈。
