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