探究Presto SQL引擎 系列：第1篇《探究Presto SQL引擎(1)-巧用Antlr》介紹了Antlr的基本用法以及如何使用Antlr4實(shí)現(xiàn)解析SQL查詢CSV數(shù)據(jù)，在第2篇《探究Presto SQL引擎(2)-淺析Join》結(jié)合了Join的原理，以及Join的原理，在Presto中的思路。
本文是系列第3篇，介紹基于 Antlr 實(shí)現(xiàn)where條件的解析原理，并對(duì)比了直接解析與代碼生成實(shí)現(xiàn)兩種實(shí)現(xiàn)思路的性能，經(jīng)實(shí)驗(yàn)基于代碼生成的實(shí)現(xiàn)相比直接解析有 3 倍的性能提升。
一、背景問(wèn)題
業(yè)務(wù)開(kāi)發(fā)過(guò)程中，使用SQL進(jìn)行數(shù)據(jù)篩選(where關(guān)鍵詞)和關(guān)聯(lián)(join關(guān)鍵詞)是編寫SQL語(yǔ)句實(shí)現(xiàn)業(yè)務(wù)需求最常見(jiàn)、最基礎(chǔ)的能力。
在海量數(shù)據(jù)和響應(yīng)時(shí)間雙重壓力下，看似簡(jiǎn)單的數(shù)據(jù)篩選和關(guān)聯(lián)在實(shí)現(xiàn)過(guò)程中面臨非常多技術(shù)細(xì)節(jié)問(wèn)題，在研究解決這些問(wèn)題過(guò)程中也誕生了非常有趣的數(shù)據(jù)結(jié)構(gòu)和優(yōu)化思想。比如B樹、LSM樹、列式存儲(chǔ)、動(dòng)態(tài)代碼生成等。
對(duì)于Presto SQL引擎，布爾表達(dá)式的判斷是實(shí)現(xiàn)where和join處理邏輯中非?；A(chǔ)的能力。
本文旨在探究 where 關(guān)鍵詞的實(shí)現(xiàn)思路，探究where語(yǔ)句內(nèi)部實(shí)現(xiàn)的基本思路以及性能優(yōu)化的基本思想。以where語(yǔ)句為例：where篩選支持and 、or 和 not 三種基礎(chǔ)邏輯，在三種基礎(chǔ)邏輯的基礎(chǔ)上，支持基于括號(hào)自定義優(yōu)先級(jí)、表達(dá)式內(nèi)部支持字段、函數(shù)調(diào)用?？此坪?jiǎn)單，實(shí)則別有洞天。值得深入挖掘?qū)W習(xí)。
二、使用 Antlr 實(shí)現(xiàn) where 條件過(guò)濾
對(duì)于Presto查詢引擎，其整體架構(gòu)如下：
其中，Parser&Analyzer就是Antlr的用武之地。任何的SQL語(yǔ)句，必須經(jīng)過(guò)Parser&Analyzer這一步，所謂一夫當(dāng)關(guān)萬(wàn)夫莫開(kāi)。關(guān)于Antlr的背景及基礎(chǔ)操作等內(nèi)容，在《探究Antlr在Presto 引擎的應(yīng)用》一文已有描述，不再贅述。
本文依然采用驅(qū)動(dòng)Antlr的三板斧來(lái)實(shí)現(xiàn)SQL語(yǔ)句對(duì)where條件的支持。
對(duì)于where條件，首先拆解where條件最簡(jiǎn)單的結(jié)構(gòu)：
- and 和or作為組合條件篩選的基本結(jié)構(gòu)。
- 6大比較運(yùn)算符(大于，小于，等于，不等于，大于或等于，小于或等于)作為基本表達(dá)式。
接下來(lái)就是使用 Antlr 的標(biāo)準(zhǔn)流程。
2.1 定義語(yǔ)法規(guī)則
使用antlr定義語(yǔ)法規(guī)則如下 (該規(guī)則基于presto SQL語(yǔ)法裁剪，完整定義可參考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條件后面附帶一個(gè)booleanExpression表達(dá)式規(guī)則，booleanExpression表達(dá)式規(guī)則支持基礎(chǔ)的valueExpression預(yù)測(cè)、and和or以及not條件組合。本文的目的是探索核心思路，而非實(shí)現(xiàn)一個(gè)完成的SQL篩選能力，所以只處理and和or條件即可，以實(shí)現(xiàn)刪繁就簡(jiǎn)，聚焦核心問(wèn)題的目的。
2.2 生成語(yǔ)法解析代碼
參照 Antlr 的官方文檔，使用預(yù)處理好的 Antlr命令處理g4文件，生成代碼即可。
antlr4 -package org.example.antlr -no-listener -visitor .\SqlBase.g4
2.3 開(kāi)發(fā)業(yè)務(wù)代碼處理 AST
2.3.1 定義語(yǔ)法樹節(jié)點(diǎn)
在了解了表達(dá)式構(gòu)成后，先定義兩個(gè)基礎(chǔ)的SQL語(yǔ)法樹節(jié)點(diǎn)，類圖如下：
這兩個(gè)類從結(jié)構(gòu)上是同構(gòu)的：左右各一個(gè)分支表達(dá)式，中間一個(gè)運(yùn)算符。
2.3.2 構(gòu)建語(yǔ)法樹
在AstBuilder實(shí)現(xiàn)中，新增對(duì)logicalBinary, comparison相關(guān)語(yǔ)法的解析實(shí)現(xiàn)。這些工作都是依樣畫葫蘆，沒(méi)有什么難度。
@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));
}
通過(guò)上面的兩步，一個(gè)SQL表達(dá)式就能轉(zhuǎn)化成一個(gè)SQL語(yǔ)法樹了。
2.3.3 遍歷語(yǔ)法樹
有了SQL語(yǔ)法樹后，問(wèn)題就自然而然浮現(xiàn)出來(lái)了：
- a) 這個(gè)SQL語(yǔ)法樹結(jié)構(gòu)有什么用？
- b) 這個(gè)SQL語(yǔ)法樹結(jié)構(gòu)該怎么用？
其實(shí)對(duì)于SQL語(yǔ)法樹的應(yīng)用場(chǎng)景，排除SQL引擎內(nèi)部的邏輯，在我們?nèi)粘ｉ_(kāi)發(fā)中也是很常見(jiàn)的。比如：SQL語(yǔ)句的格式化，SQL的拼寫檢查。
對(duì)于SQL語(yǔ)法樹該怎么用的問(wèn)題，可以通過(guò)一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)說(shuō)明：SQL語(yǔ)句格式化。
在《探究Antlr在Presto 引擎的應(yīng)用》一文中，為了簡(jiǎn)化問(wèn)題采取了直接拆解antlr生成的AST獲取SQL語(yǔ)句中的表名稱和字段名稱，處理方式非常簡(jiǎn)單粗暴。實(shí)際上presto中有一種更為優(yōu)雅的處理思路：AstVisitor。也就是設(shè)計(jì)模式中的訪問(wèn)者模式。
訪問(wèn)者模式定義如下：
- 封裝一些作用于某種數(shù)據(jù)結(jié)構(gòu)中的各元素的操作，它可以在不改變這個(gè)數(shù)據(jù)結(jié)構(gòu)的前提下定義作用于這些元素的新的操作。
這個(gè)定義落實(shí)到SQL語(yǔ)法樹結(jié)構(gòu)實(shí)現(xiàn)要點(diǎn)如下：即SQL語(yǔ)法樹節(jié)點(diǎn)定義一個(gè)accept方法作為節(jié)點(diǎn)操作的入口(參考Node.accept()方法)。定義個(gè)AstVisitor類用于規(guī)范訪問(wèn)節(jié)點(diǎn)樹的操作，具體的實(shí)現(xiàn)類繼承AstVisitor即可?；A(chǔ)結(jié)構(gòu)定義好過(guò)后，后面就是萬(wàn)變不離其宗了。
兩個(gè)類核心框架代碼如下：
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);
}
....
}例如最常見(jiàn)的select * from table where 這類SQL語(yǔ)法，在SelectBase.g4文件中定義查詢的核心結(jié)構(gòu)如下：
querySpecification
: SELECT setQuantifier? selectItem (',' selectItem)*
(FROM relation (',' relation)*)?
(WHERE where=booleanExpression)?
(GROUP BY groupBy)?
(HAVING having=booleanExpression)?
;
以格式化SQL語(yǔ)句為例，Presto實(shí)現(xiàn)了SqlFormatter和ExpressionFormatter兩個(gè)實(shí)現(xiàn)類。格式化這個(gè)語(yǔ)句的代碼如下：
@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;
}
代碼實(shí)現(xiàn)邏輯清晰明了，可讀性極強(qiáng)。
同理， 實(shí)現(xiàn)where條件解析的核心在于比較條件表達(dá)式的處理(visitComparisonExpression)和邏輯條件表達(dá)式的處理(visitLogicalBinaryExpression)。同樣出于聚焦核心流程的考慮，我們只實(shí)現(xiàn)類似于a > 0 or b < 10 這種整型字段的過(guò)濾。
對(duì)于and和or結(jié)構(gòu)，由于是樹形結(jié)構(gòu)，所以會(huì)用到遞歸，即優(yōu)先處理葉子節(jié)點(diǎn)再以層層向上匯總。處理處理邏輯如下代碼所示：
/**
? 處理比較表達(dá)式
? @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;
}
這里的實(shí)現(xiàn)非常簡(jiǎn)單，基于棧存儲(chǔ)葉子節(jié)點(diǎn)(ComparisonExpression )計(jì)算的結(jié)果，遞歸回溯非葉子節(jié)點(diǎn)(LogicalBinaryExpression )時(shí)從棧中取出棧頂?shù)闹?，進(jìn)行and和or的運(yùn)算。說(shuō)明一下：其實(shí)遞歸的實(shí)現(xiàn)方式是可以不使用棧，直接返回值即可。這里基于棧實(shí)現(xiàn)是為了跟下文代碼生成的邏輯從結(jié)構(gòu)上保持一致，方便對(duì)比性能。
2.4 驗(yàn)證表達(dá)式執(zhí)行
為了驗(yàn)證上述方案執(zhí)行結(jié)果，定義一個(gè)簡(jiǎn)單的過(guò)濾規(guī)則，生成隨機(jī)數(shù)驗(yàn)證能否實(shí)現(xiàn)對(duì)表達(dá)式邏輯的判斷。
// antlr處理表達(dá)式語(yǔ)句，生成Expression對(duì)象
SqlParser sqlParser = new SqlParser();
Expression expression = sqlParser.createExpression("a>1 and b<2");
// 基于AstVisitor實(shí)現(xiàn)
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));
}
// ====== 執(zhí)行結(jié)果如下
/**
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
*/
通過(guò)上述的處理流程以及執(zhí)行結(jié)果的驗(yàn)證，可以確定基于Antlr可以非常簡(jiǎn)單實(shí)現(xiàn)where條件的過(guò)濾，這跟antlr實(shí)現(xiàn)四則運(yùn)算能力有異曲同工之妙。但是通過(guò)對(duì)Presto源碼及相關(guān)文檔閱讀，卻發(fā)現(xiàn)實(shí)際上對(duì)于條件過(guò)濾及JOIN的實(shí)現(xiàn)是另辟蹊徑。這是為什么呢？
三、基于 AstVisitor 直接解析 SQL 條件問(wèn)題
在解答Presto的實(shí)現(xiàn)思路之前，需要先鋪墊兩個(gè)基礎(chǔ)的知識(shí)。一個(gè)是CPU的流水線和分支預(yù)測(cè)，另一個(gè)是JVM的方法內(nèi)聯(lián)優(yōu)化。
3.1 CPU流水線和分支預(yù)測(cè)
計(jì)算機(jī)組成原理中關(guān)于CPU指令的執(zhí)行，如下圖所示：
即在早期CPU執(zhí)行指令采用串行的方式，為了提升CPU的吞吐量，在RISC的架構(gòu)中通過(guò)流水線的方式實(shí)現(xiàn)了多條指令重疊進(jìn)行操作的一種準(zhǔn)并行處理實(shí)現(xiàn)技術(shù)。通過(guò)上面的圖示，可以看出：增加一條流水后，單位時(shí)間執(zhí)行的指令數(shù)量就翻倍，即性能提升了1倍。
當(dāng)然這是理想的情況，現(xiàn)實(shí)中會(huì)遇到兩類問(wèn)題：
- 1）下一條指令的執(zhí)行依賴上一條指令執(zhí)行的結(jié)果。
- 2）遇到分支必須等條件計(jì)算完成才知道分支是否執(zhí)行。
對(duì)于問(wèn)題1，通過(guò)亂序執(zhí)行的方法能夠?qū)⑿阅芴嵘?0%~30%。對(duì)于問(wèn)題2，則是通過(guò)分支預(yù)測(cè)的方法來(lái)應(yīng)對(duì)。
關(guān)于利用分支預(yù)測(cè)原理提升性能，有兩個(gè)有意思的案例。
案例1：
stackoverflow上有個(gè)著名的問(wèn)題：why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array。即對(duì)于有序數(shù)組和無(wú)序數(shù)組的遍歷，執(zhí)行時(shí)間差不多有2~3倍的差距。
在筆者的計(jì)算機(jī)上，運(yùn)行案例結(jié)果符合描述。需要注意的是用system.nanotime()來(lái)衡量，system.currenttimemillis()精度不夠。
案例2：
Dubbo源碼ChannelEventRunnable中通過(guò)將switch代碼優(yōu)化成if獲得了近似2倍的效率提升。
簡(jiǎn)單總結(jié)一下，代碼中的分支邏輯會(huì)影響性能，通過(guò)一些優(yōu)化處理(比如數(shù)據(jù)排序/熱點(diǎn)代碼前置)能夠提升分支預(yù)測(cè)的成功率，從而提升程序執(zhí)行的效率。
3.2 JVM 方法內(nèi)聯(lián)優(yōu)化
JVM是基于棧的指令執(zhí)行策略。一個(gè)函數(shù)調(diào)用除了執(zhí)行自身邏輯的開(kāi)銷外，還有函數(shù)執(zhí)行上下文信息維護(hù)的額外開(kāi)銷，例如：棧幀的生成、參數(shù)字段入棧、棧幀的彈出、指令執(zhí)行地址的跳轉(zhuǎn)。JVM內(nèi)聯(lián)優(yōu)化對(duì)于性能的影響非常大。
這里有一個(gè)小實(shí)驗(yàn)，對(duì)于同一段代碼正常執(zhí)行和禁用內(nèi)聯(lián)優(yōu)化(-XX:CompileCommand=dontinline,
test/TestInline.addOp), 其性能差距差不多有6倍。
代碼樣例及數(shù)據(jù)如下：
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();
}
}
// 執(zhí)行結(jié)果如下：
/**
Benchmark Mode Cnt Score Error Units
TestInline.testAdd thrpt 2 18588.318 ops/s(正常執(zhí)行)
TestInline.testAdd thrpt 2 3131.466 ops/s(禁用內(nèi)聯(lián))
**/對(duì)于Java語(yǔ)言，方法內(nèi)聯(lián)優(yōu)化也是有成本的。所以，通常熱點(diǎn)代碼/方法體較小的代碼/用private、static、final修飾的代碼才可能內(nèi)聯(lián)。過(guò)大的方法體和面向?qū)ο蟮睦^承和多態(tài)都會(huì)影響方法的內(nèi)聯(lián)，從而影響性能。
對(duì)于SQL 執(zhí)行引擎中最常見(jiàn)的where和join語(yǔ)句來(lái)說(shuō)，由于執(zhí)行過(guò)程中需要判斷數(shù)據(jù)類型、操作符類型，幾乎每行數(shù)據(jù)的處理都是在影響CPU的分支預(yù)測(cè)，而且每個(gè)數(shù)據(jù)類型，每種操作符都都需要封裝獨(dú)立的處理邏輯。如果采用直接解析SQL語(yǔ)句的方式，勢(shì)必對(duì)分支預(yù)測(cè)和方法內(nèi)聯(lián)影響極大。為了提升性能，降低分支預(yù)測(cè)失敗和方法調(diào)用的開(kāi)銷，動(dòng)態(tài)代碼生成的方案就橫空出世了。
四、基于動(dòng)態(tài)代碼生成實(shí)現(xiàn) where 條件過(guò)濾
在介紹使用動(dòng)態(tài)代碼生成實(shí)現(xiàn)where條件過(guò)濾前，有必要對(duì)字節(jié)碼生成技術(shù)的產(chǎn)生背景，Java語(yǔ)言特有的優(yōu)勢(shì)以及相關(guān)的基本操作進(jìn)行介紹。
4.1 字節(jié)碼生成的方法
Java虛擬機(jī)規(guī)范有兩個(gè)關(guān)鍵點(diǎn)：平臺(tái)無(wú)關(guān)性和語(yǔ)言無(wú)關(guān)性。
平臺(tái)無(wú)關(guān)性實(shí)現(xiàn)了一次編寫，到處運(yùn)行的目標(biāo),。即不受限于操作系統(tǒng)是Windows還是Linux。
語(yǔ)言無(wú)關(guān)性使得JVM上面運(yùn)行的語(yǔ)言不限于Java, 像Groovy, Scala，JRuby 都成為了JVM生態(tài)的一部分。而能夠?qū)崿F(xiàn)平臺(tái)無(wú)關(guān)性和語(yǔ)言無(wú)關(guān)性的的基礎(chǔ)就是基于棧執(zhí)行指令的虛擬機(jī)和字節(jié)碼存儲(chǔ)技術(shù)。
對(duì)于任意一門編程語(yǔ)言：程序分析、程序生成、程序轉(zhuǎn)換技術(shù)在開(kāi)發(fā)中應(yīng)用廣泛，通常應(yīng)用在如下的場(chǎng)景中：
程序分析：基于語(yǔ)法和語(yǔ)義分析，識(shí)別潛在的bug和無(wú)用代碼，或者進(jìn)行逆向工程，研究軟件內(nèi)部原理(比如軟件破解或開(kāi)發(fā)爬蟲)
程序生成：比如傳統(tǒng)的編譯器、用于分布式系統(tǒng)的stub或skeleton編譯器或者JIT編譯器等。
程序轉(zhuǎn)換： 優(yōu)化或者混淆代碼、插入調(diào)試代碼、性能監(jiān)控等。
對(duì)于Java編程語(yǔ)言，由于有Java源碼-字節(jié)碼-機(jī)器碼三個(gè)層級(jí)，所以程序分析、程序生成、程序轉(zhuǎn)換的技術(shù)落地可以有兩個(gè)切入點(diǎn)：Java源碼或者編譯后的Class。選擇編譯后的Class字節(jié)碼有如下的優(yōu)勢(shì)：
無(wú)需源碼。這對(duì)于閉源的商業(yè)軟件也能非常方便實(shí)現(xiàn)跨平臺(tái)的性能監(jiān)控等需求。
運(yùn)行時(shí)分析、生成、轉(zhuǎn)換。只要在class字節(jié)碼被加載到虛擬機(jī)之前處理完就可以了，這樣整個(gè)處理流程就對(duì)用戶透明了。
程序生成技術(shù)在Java中通常有另一個(gè)名字：字節(jié)碼生成技術(shù)。這也表明了Java語(yǔ)言選擇的切入點(diǎn)是編譯后的Class字節(jié)碼。
字節(jié)碼生成技術(shù)在Java技術(shù)棧中應(yīng)用也非常廣泛，比如：Spring項(xiàng)目的AOP，各種ORM框架，Tomcat的熱部署等場(chǎng)景。Java有許多字節(jié)碼操作框架，典型的有asm和javassist、bytebuddy、jnif等。
通常出于性能的考量asm用得更為廣泛。直接使用asm需要理解JVM的指令，對(duì)用戶來(lái)說(shuō)學(xué)習(xí)門檻比較高。Facebook基于asm進(jìn)行了一層封裝，就是airlift.bytecode工具了?；谠摴ぞ咛峁┑膭?dòng)態(tài)代碼生成也是presto性能保障的一大利器。用戶使用airlift.bytecode可以避免直接寫JVM指令。但是該框架文檔較少，通常操作只能從其TestCase和presto的源碼中學(xué)習(xí)，本小節(jié)簡(jiǎn)單總結(jié)使用airlift.bytecode生成代碼的基本用法。
通常，我們理解了變量、數(shù)組、控制邏輯、循環(huán)邏輯、調(diào)用外部方法這幾個(gè)點(diǎn)，就可以操作一門編程語(yǔ)言了。至于核心庫(kù)，其作用是輔助我們更高效地開(kāi)發(fā)。對(duì)于使用airlift.bytecode框架，理解定義類、定義方法(分支、循環(huán)和方法調(diào)用)、方法執(zhí)行這些常用操作就能夠滿足大部分業(yè)務(wù)需求：
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;
}
通過(guò)上面的代碼，就定義了一個(gè)public final修飾的類,而且確保程序運(yùn)行匯總類名不會(huì)重復(fù)。
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邏輯
/**
* 生成循環(huán)邏輯代碼
* 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: 生成類并執(zhí)行方法
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: 操作數(shù)據(jù)結(jié)構(gòu)-從Map數(shù)據(jù)結(jié)構(gòu)取值
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對(duì)應(yīng)的值
method.getBody().append(out.invoke("print", void.class, argRow.invoke("get",Object.class,constantString("aa").cast(Object.class)))).ret();
}
// 代碼執(zhí)行
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);
}通過(guò)上述的幾個(gè)Case, 我們了解了airlift.bytecode框架的基本用法。如果想更深入研究，需要參考閱讀ASM相關(guān)的資料，畢竟airlift.bytecode是基于ASM構(gòu)建的。但是在本文的研究中，到這里就夠用了。
4.2 基于動(dòng)態(tài)代碼生成實(shí)現(xiàn) where 條件過(guò)濾
在熟悉動(dòng)態(tài)代碼生成框架的基本使用方法后，我們就可以使用該工具實(shí)現(xiàn)具體的業(yè)務(wù)邏輯了。同樣地，我們基于AstVisitor實(shí)現(xiàn)生成where條件過(guò)濾的字節(jié)碼。
整體代碼框架跟前面的實(shí)現(xiàn)保持一致，需要解決問(wèn)題的關(guān)鍵點(diǎn)在于字節(jié)碼生成的邏輯。對(duì)于where條件的查詢語(yǔ)句，本質(zhì)上是一個(gè)二叉樹。對(duì)于二叉樹的遍歷，用遞歸是最簡(jiǎn)單的方法。遞歸從某種程度上，跟棧的操作是一致的。
對(duì)于實(shí)現(xiàn)where條件過(guò)濾代碼生成，實(shí)現(xiàn)邏輯描述如下：
輸入：antlr生成的expression表達(dá)式
輸出：airlift.bytecode生成的class
s1：定義清晰生成類的基礎(chǔ)配置：類名、修飾符等信息
s2：定義一個(gè)棧用于存儲(chǔ)比較運(yùn)算(ComparisonExpression)計(jì)算結(jié)果
s3：使用遞歸方式遍歷expression
s4：對(duì)于葉子節(jié)點(diǎn)(ComparisonExpression)，代碼生成邏輯如下：從方法定義的參數(shù)中取出對(duì)應(yīng)的值，根據(jù)比較符號(hào)生成計(jì)算代碼，并將計(jì)算結(jié)果push到stack
s5：對(duì)于非葉子節(jié)點(diǎn)
(LogicalBinaryExpression), 代碼生成邏輯如下：取出棧頂?shù)膬蓚€(gè)值，進(jìn)行and或or操作運(yùn)算，將計(jì)算結(jié)果push到stack
s6：當(dāng)遞歸回退到根節(jié)點(diǎn)時(shí)，取出棧頂?shù)闹底鳛橛?jì)算的最終結(jié)果
s7：基于類和方法的定義生成Class
實(shí)現(xiàn)字節(jié)碼生成代碼如下：
/**
? 生成比較條件語(yǔ)句
**/
@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語(yǔ)句
**/
@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");
}
// 根據(jù)運(yùn)算符生成字節(jié)碼
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;
}
代碼實(shí)現(xiàn)完成后，為了驗(yàn)證處理邏輯是否正常，可以用兩種實(shí)現(xiàn)的方式運(yùn)行同一個(gè)測(cè)試用例，確保同樣的where表達(dá)式在同樣的參數(shù)下執(zhí)行結(jié)果一致。
為了驗(yàn)證兩種實(shí)現(xiàn)方式執(zhí)行的性能，這里引入JMH框架，基于JMH框架生成性能驗(yàn)證代碼：
@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處理表達(dá)式語(yǔ)句，生成Expression對(duì)象
SqlParser sqlParser = new SqlParser();
Expression expression = sqlParser.createExpression("a>5 and b<5");
// 基于AstVisitor實(shí)現(xiàn)
this.filter1 = new WhereExpFilter(expression);
// 基于AstVisitor實(shí)現(xiàn)
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萬(wàn)量級(jí)的數(shù)據(jù)集，性能驗(yàn)證的結(jié)果如下：
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
通過(guò)上述的驗(yàn)證數(shù)據(jù)，可以得出初步的結(jié)論，對(duì)于簡(jiǎn)單的比較表達(dá)式，基于代碼生成的方式相比直接遍歷的方式大約有3倍左右的性能提升。對(duì)比直接基于AstVisitor實(shí)現(xiàn)where條件過(guò)濾，代碼生成無(wú)需對(duì)表達(dá)式中的操作符進(jìn)行判斷，直接基于表達(dá)式動(dòng)態(tài)生成代碼，裁剪了許多判斷的分支。
五、總結(jié)
本文探索了SQL引擎中where表達(dá)式的實(shí)現(xiàn)思路，基于antlr實(shí)現(xiàn)了兩種方式:：
其一是直接遍歷表達(dá)式生成的Expression；
其二是基于表達(dá)式生成的Expression通過(guò)airlift.bytecode動(dòng)態(tài)生成字節(jié)碼。
本文初步分析了Presto中應(yīng)用代碼生成實(shí)現(xiàn)相關(guān)業(yè)務(wù)邏輯的出發(fā)點(diǎn)及背景問(wèn)題。并使用JMH進(jìn)行了性能測(cè)試，測(cè)試結(jié)果表明對(duì)于同樣的實(shí)現(xiàn)思路，基于代碼生成方式相比直接實(shí)現(xiàn)約有3倍的性能提升。
實(shí)際上Presto中使用代碼生成的方式相比本文描述要復(fù)雜得多，跟文本實(shí)現(xiàn)的方式并不一樣?；诒疚牡奶剿鞲嘣谟谔剿餮芯炕镜乃悸?，而非再造一個(gè)Presto。
盡管使用動(dòng)態(tài)代碼生成對(duì)于性能的提升效果明顯，但是在業(yè)務(wù)實(shí)踐中，需要權(quán)衡使用代碼生成的ROI，畢竟使用代碼生成實(shí)現(xiàn)的邏輯，代碼可讀性和可維護(hù)性相比直接編碼要復(fù)雜很多，開(kāi)發(fā)復(fù)雜度也復(fù)雜很多。就像C語(yǔ)言嵌入?yún)R編一樣，代碼生成技術(shù)在業(yè)務(wù)開(kāi)發(fā)中使用同樣需要慎重考慮，使用得當(dāng)能取得事半功倍的效果，使用不當(dāng)或?yàn)E用則會(huì)為項(xiàng)目埋下不可預(yù)知的定時(shí)炸彈。
