OLAP引擎底層原理與設(shè)計實(shí)踐

Contents　目　錄
序一
序二
序三
序四（原版）
序四（中文版）
前言
致謝一
致謝二
第一篇　背景知識
第1章　OLAP引擎介紹與對比2
1.1　OLAP的定義與對比標(biāo)準(zhǔn)2
1.1.1　OLAP的定義2
1.1.2　OLAP引擎之間的對比標(biāo)準(zhǔn)3
1.2　各種OLAP引擎的主要特點(diǎn)6
1.2.1　Hive6
1.2.2　SparkSQL、FlinkSQL6
1.2.3　ClickHouse6
1.2.4　Elasticsearch8
1.2.5　Presto9
1.2.6　Impala10
1.2.7　Doris10
1.2.8　Druid11
1.2.9　總結(jié)12
1.3　再談對Presto技術(shù)發(fā)展的理解13
1.4　總結(jié)、思考、實(shí)踐15
第2章　Presto基本介紹16
2.1　Presto概述：特性、原理、架構(gòu)16
2.1.1　一個高性能、分布式的SQL
　　　執(zhí)行框架17
2.1.2　一套插件化體系18
2.1.3　開箱即用的SQL內(nèi)置函數(shù)和
　　　連接器20
2.2　Presto的應(yīng)用場景與企業(yè)案例20
2.2.1　Presto的應(yīng)用場景20
2.2.2　Presto的企業(yè)案例21
2.2.3　Presto不適合哪些場景23
2.3　Presto常見問題及應(yīng)對策略25
2.3.1　查詢協(xié)調(diào)節(jié)點(diǎn)單點(diǎn)問題25
2.3.2　查詢執(zhí)行過程沒有容錯機(jī)制27
2.3.3　查詢執(zhí)行時報錯exceeding
　　　memory limits27
2.3.4　無法動態(tài)增刪改或加載數(shù)據(jù)
　　　目錄與UDF28
2.3.5　查詢執(zhí)行結(jié)果必須經(jīng)集群協(xié)調(diào)節(jié)
　　　點(diǎn)返回28
2.3.6　不支持低延遲、高并發(fā)28
2.4　Presto與Trino的項(xiàng)目與版本
　　選擇30
2.4.1　Trino與Presto選擇哪個30
2.4.2　本書為什么用Trino的v350
　　　版本來做介紹31
2.4.3　Presto項(xiàng)目源碼結(jié)構(gòu)32
2.5　編譯與運(yùn)行Presto源碼34
2.5.1　環(huán)境準(zhǔn)備34
2.5.2　下載源碼并載入IDEA35
2.5.3　編譯Presto源碼36
2.5.4　標(biāo)記Antlr4自動生成的代碼
　　　為generated source36
2.5.5　在IDEA中運(yùn)行3個節(jié)點(diǎn)的
　　　Presto集群38
2.5.6　運(yùn)行Presto命令行工具44
2.5.7　調(diào)試Presto源碼常見問題44
2.6　基于Presto的數(shù)據(jù)倉庫及本書
　　常用SQL46
2.6.1　數(shù)據(jù)倉庫介紹46
2.6.2　TPC-DS Data Model數(shù)據(jù)
　　　模型介紹47
2.6.3　本書常用SQL49
2.6.4　在哪里執(zhí)行本節(jié)介紹的SQL54
2.7　總結(jié)、思考、實(shí)踐54
第二篇　核心原理
第3章　分布式查詢執(zhí)行的整體流程56
3.1　分布式OLAP引擎整體架構(gòu)及
　　　查詢執(zhí)行原理56
3.2　分布式查詢執(zhí)行的整體介紹58
3.2.1　從分布式架構(gòu)看SQL查詢
　　　的執(zhí)行流程58
3.2.2　從功能模塊看SQL執(zhí)行流程58
3.2.3　原理講解涉及的案例介紹59
3.3　查詢的接收、解析與提交60
3.3.1　接收SQL查詢請求60
3.3.2　詞法與語法分析并生成抽象
　　　語法樹62
3.3.3　創(chuàng)建并提交QueryExecution63
3.4　執(zhí)行計劃的生成與優(yōu)化64
3.4.1　語義分析，生成執(zhí)行計劃64
3.4.2　優(yōu)化執(zhí)行計劃，生成優(yōu)化后
　　　的執(zhí)行計劃65
3.4.3　將邏輯執(zhí)行計劃樹拆分為
　　　多棵子樹68
3.5　執(zhí)行計劃的調(diào)度69
3.5.1　創(chuàng)建SqlStageExecution69
3.5.2　調(diào)度并分發(fā)HttpRemoteTask72
3.6　執(zhí)行計劃的執(zhí)行78
3.6.1　在多個查詢執(zhí)行節(jié)點(diǎn)上執(zhí)行
　　　任務(wù)78
3.6.2　分批返回查詢計算結(jié)果給
　　　SQL客戶端85
3.7　總結(jié)、思考、實(shí)踐87
第4章　查詢引擎核心模塊拆解88
4.1　執(zhí)行計劃生成的設(shè)計實(shí)現(xiàn)88
4.1.1　從SQL到抽象語法樹88
4.1.2　語義分析95
4.1.3　生成初始邏輯執(zhí)行計劃101
4.2　執(zhí)行計劃優(yōu)化的目的、基本
　　原理和基礎(chǔ)算法106
4.2.1　執(zhí)行計劃優(yōu)化的目的106
4.2.2　執(zhí)行計劃優(yōu)化的基本原理106
4.2.3　執(zhí)行計劃優(yōu)化的基礎(chǔ)算法110
4.3　執(zhí)行計劃優(yōu)化的設(shè)計實(shí)現(xiàn)115
4.3.1　執(zhí)行計劃優(yōu)化的工作流程115
4.3.2　非迭代式優(yōu)化器和迭代式
　　　優(yōu)化器118
4.4　總結(jié)、思考、實(shí)踐125
第三篇　經(jīng)典SQL
第5章　數(shù)據(jù)過濾與投影相關(guān)查詢
　　　　的執(zhí)行原理解析128
5.1　SQL-01簡單拉取數(shù)據(jù)查詢的
　　　實(shí)現(xiàn)原理128
5.1.1　執(zhí)行計劃的生成與優(yōu)化128
5.1.2　分布式調(diào)度與執(zhí)行的設(shè)計實(shí)現(xiàn)130
5.2　SQL-02數(shù)據(jù)過濾與投影查詢的
　　實(shí)現(xiàn)原理134
5.2.1　執(zhí)行計劃的生成與優(yōu)化134
5.2.2　分布式調(diào)度與執(zhí)行的設(shè)計實(shí)現(xiàn)136
5.3　數(shù)據(jù)過濾與投影相關(guān)查詢涉及
　　的查詢優(yōu)化147
5.3.1　列裁剪147
5.3.2　部分計算下推到存儲服務(wù)148
5.3.3　表達(dá)式計算的優(yōu)化150
5.4　總結(jié)、思考、實(shí)踐151
第6章　行數(shù)限定與排序相關(guān)
　　　　查詢的執(zhí)行原理解析153
6.1　SQL-10行數(shù)限定查詢的實(shí)現(xiàn)
　　原理153
6.1.1　執(zhí)行計劃的生成與優(yōu)化154
6.1.2　分布式調(diào)度與執(zhí)行的設(shè)計
　　　實(shí)現(xiàn)155
6.2　SQL-11 排序查詢的實(shí)現(xiàn)原理158
6.2.1　執(zhí)行計劃的生成與優(yōu)化158
6.2.2　分布式調(diào)度與執(zhí)行的設(shè)計實(shí)現(xiàn)160
6.3　SQL-12 排序與行數(shù)限定組合
　　查詢的實(shí)現(xiàn)原理174
6.3.1　執(zhí)行計劃的生成與優(yōu)化174
6.3.2　分布式調(diào)度與執(zhí)行的設(shè)計實(shí)現(xiàn)176
6.4　簡單SELECT查詢相關(guān)的查詢
　　優(yōu)化191
6.4.1　將LIMIT計算下推到數(shù)據(jù)
　　　源連接器191
6.4.2　去除不需要的LIMIT計算192
6.5　總結(jié)、思考、實(shí)踐193
第7章　簡單聚合查詢的執(zhí)行原理
　　　　解析194
7.1　聚合查詢原理通識性介紹194
7.1.1　常見的聚合查詢194
7.1.2　聚合查詢是有狀態(tài)計算196
7.1.3　實(shí)現(xiàn)分布式聚合的幾種執(zhí)行
　　　模型196
7.1.4　Presto對聚合查詢的設(shè)計與
　　　抽象197
7.2　SQL-20不分組聚合查詢的實(shí)現(xiàn)
　　　原理198
7.2.1　執(zhí)行計劃的生成與優(yōu)化198
7.2.2　分布式調(diào)度與執(zhí)行的設(shè)計實(shí)現(xiàn)201
7.2.3　使用Scatter-Gather執(zhí)行模型
　　　實(shí)現(xiàn)SQL-20211
7.3　SQL-21分組聚合查詢的實(shí)現(xiàn)原理212
7.3.1　執(zhí)行計劃的生成與優(yōu)化213
7.3.2　分布式調(diào)度與執(zhí)行的設(shè)計實(shí)現(xiàn)214
7.3.3　使用Scatter-Gather執(zhí)行模型
　　　實(shí)現(xiàn)SQL-21236
7.3.4　總結(jié)237
7.4　聚合函數(shù)的設(shè)計與實(shí)現(xiàn)238
7.5　總結(jié)、思考、實(shí)踐240
第8章　復(fù)雜聚合查詢的執(zhí)行原理
　　　　解析242
8.1　SQL-22去重計數(shù)查詢的實(shí)現(xiàn)
　　原理242
8.1.1　執(zhí)行計劃的生成與優(yōu)化243
8.1.2　分布式調(diào)度與執(zhí)行的設(shè)計實(shí)現(xiàn)246
8.1.3　使用Scatter-Gather執(zhí)行模型
　　　實(shí)現(xiàn)SQL-22247
8.1.4　總結(jié)248
8.2　SQL-23多個聚合計算查詢的
　　　實(shí)現(xiàn)原理248
8.2.1　執(zhí)行計劃的生成與優(yōu)化249
8.2.2　分布式調(diào)度與執(zhí)行的設(shè)計實(shí)現(xiàn)252
8.2.3　為什么Presto要引入MarkDistinct
　　　優(yōu)化258
8.2.4　使用Scatter-Gather執(zhí)行模型
　　　實(shí)現(xiàn)SQL-23260
8.3　SQL-30綜合多種計算查詢的
　 　實(shí)現(xiàn)原理260
8.3.1　執(zhí)行計劃的生成與優(yōu)化261
8.3.2　分布式調(diào)度與執(zhí)行的設(shè)計實(shí)現(xiàn)264
8.3.3　使用Scatter-Gather執(zhí)行模型
　　　實(shí)現(xiàn)SQL-30265
8.3.4　總結(jié)266
8.4　常見聚合查詢優(yōu)化手段與優(yōu)化器267
8.4.1　將聚合操作拆分為部分聚合與
　　　最終聚合267
8.4.2　在上下游任務(wù)中傳播哈希聚合
　　　分組列的哈希值267
8.4.3　部分聚合計算下推268
8.4.4　將ORDER BY與LIMI T計算
　　　優(yōu)化為TopN計算268
8.4.5　基于代價評估的方式來決定
　　　如何選擇執(zhí)行模型268
8.4.6　利用存儲的數(shù)據(jù)分布特性做
　　　優(yōu)化269
8.5　總結(jié)、思考、實(shí)踐270
第四篇　數(shù)據(jù)交換機(jī)制
第9章　數(shù)據(jù)交換在查詢規(guī)劃、
　　　　調(diào)度、執(zhí)行中的基本原理272
9.1　數(shù)據(jù)交換機(jī)制簡介272
9.1.1　數(shù)據(jù)交換是什么272
9.1.2　何時需要做數(shù)據(jù)交換273
9.1.3　數(shù)據(jù)交換是拉取模型274
9.1.4　任務(wù)之間數(shù)據(jù)交換與任務(wù)內(nèi)部
　　　數(shù)據(jù)交換275
9.1.5　數(shù)據(jù)交換的代價276
9.2　查詢優(yōu)化階段任務(wù)之間數(shù)據(jù)交換
　 　的設(shè)計實(shí)現(xiàn)276
9.2.1　任務(wù)之間數(shù)據(jù)交換的3個
　　　階段276
9.2.2　ExchangeNode的實(shí)現(xiàn)277
9.2.3　利用AddExchanges優(yōu)化器
　　　插入ExchangeNode282
9.2.4　AddExchanges決策在哪里
　　　插入ExchangeNode的主要
　　　考慮因素284
9.2.5　AddExchanges優(yōu)化器的設(shè)計思路
　　　與案例285
9.2.6　拆分PlanFragment296
9.3　查詢調(diào)度與執(zhí)行階段的整體設(shè)計
　 　思路297
9.3.1　在分布式查詢集群中唯一確定
　　　某個任務(wù)297
9.3.2　每個任務(wù)的上游和下游298
9.3.3　交付上游任務(wù)產(chǎn)出的數(shù)據(jù)298
9.3.4　上下游任務(wù)數(shù)據(jù)交換的交互
　　　機(jī)制300
9.3.5　上下游任務(wù)生產(chǎn)與消費(fèi)的速度301
9.4　總結(jié)、思考、實(shí)踐301
第10章　數(shù)據(jù)交換在查詢調(diào)度與
　　　　　執(zhí)行中的詳細(xì)設(shè)計302
10.1　查詢調(diào)度階段任務(wù)之間數(shù)據(jù)
　　　交換的設(shè)計實(shí)現(xiàn)302
10.1.1　調(diào)度部分整體介紹302
10.1.2　建立相鄰上下游查詢執(zhí)行
　　　　階段間的數(shù)據(jù)依賴關(guān)系303
10.1.3　RemoteTask中與任務(wù)之間
　　　　數(shù)據(jù)交換相關(guān)的抽象設(shè)計308
10.2　查詢執(zhí)行階段任務(wù)之間數(shù)據(jù)交換
　　　上游的設(shè)計實(shí)現(xiàn)309
10.2.1　整體概述309
10.2.2　OutputBuffer的工作流程309
10.2.3　不同的OutputBuffer具體實(shí)現(xiàn)313
10.2.4　兩種OutputOperator315
10.3　查詢執(zhí)行階段任務(wù)之間數(shù)據(jù)交換
　　　下游的設(shè)計實(shí)現(xiàn)315
10.3.1　整體概述315
10.3.2　兩種用于拉取上游任務(wù)數(shù)據(jù)
　　　　的SourceOperator316
10.4　上下游任務(wù)之間數(shù)據(jù)交換的RPC
　　　交互機(jī)制321
10.4.1　數(shù)據(jù)交換的RPC通信協(xié)議321
10.4.2　SerializedPage的序列化
　　　 　格式323
10.5　任務(wù)內(nèi)部數(shù)據(jù)交換的基本原理324
10.6　利用數(shù)據(jù)交換能力實(shí)現(xiàn)的特殊
　　　功能326
10.6.1　利用數(shù)據(jù)交換能力在查詢執(zhí)行
　　　　路徑實(shí)現(xiàn)的反壓機(jī)制326
10.6.2　利用數(shù)據(jù)交換能力實(shí)現(xiàn)部分
　　　　SQL的LIMIT語義328
10.6.3　任務(wù)之間數(shù)據(jù)交換交互中的
　　　　亂序請求328
10.6.4　分批計算與返回執(zhí)行結(jié)果329
10.7　總結(jié)、思考、實(shí)踐330
第五篇　插件體系與連接器
第11章　連接器插件體系詳解334
11.1　插件體系整體介紹334
11.1.1　插件概述335
11.1.2　插件分類335
11.1.3　SPI機(jī)制337
11.2　插件加載機(jī)制341
11.2.1　插件初始化流程入口341
11.2.2　插件加載343
11.2.3　插件整合346
11.2.4　類加載原理347
11.3　連接器實(shí)現(xiàn)原理351
11.3.1　連接器概述351
11.3.2　連接器插件實(shí)例化353
11.3.3　元數(shù)據(jù)模塊359
11.3.4　數(shù)據(jù)讀取366
11.3.5　部分計算下推371
11.3.6　連接器在查詢執(zhí)行中的作用374
11.4　關(guān)于連接器的一些深入思考375
11.4.1　使用連接器的注意事項(xiàng)376
11.4.2　站在OLAP引擎設(shè)計者視角來
　　　　理解連接器的設(shè)計范式376
11.5　總結(jié)、思考、實(shí)踐377
第12章　連接器開發(fā)實(shí)踐：以Example-
　　　　HTTP連接器為例378
12.1　Example-HTTP連接器基本介紹379
12.2　基礎(chǔ)代碼380
12.2.1　ExamplePlugin380
12.2.2　ExampleConfig380
12.2.3　ExampleModule381
12.2.4　ExampleConnector382
12.2.5　ExampleConnectorFactory383
12.3　元數(shù)據(jù)模塊385
12.3.1　ExampleClient386
12.3.2　ExampleTable387
12.4　自定義句柄387
12.5　劃分分片388
12.6　讀取分片389
12.7　實(shí)現(xiàn)與連接器交互的HTTP
　　　數(shù)據(jù)源392
12.7.1　定義元數(shù)據(jù)接口393
12.7.2　定義數(shù)據(jù)接口394
12.7.3　Example-HTTP數(shù)據(jù)源的代碼
　　 　實(shí)現(xiàn)示例395
12.7.4　在Presto跑通Example-HTTP
　　　　數(shù)據(jù)源的查詢396
12.8　總結(jié)、思考、實(shí)踐398
第六篇　函數(shù)原理與開發(fā)
第13章　函數(shù)的執(zhí)行原理402
13.1　函數(shù)體系總覽402
13.1.1　函數(shù)分類403
13.1.2　函數(shù)的生命周期403
13.1.3　函數(shù)開發(fā)的幾種途徑404
13.1.4　MethodHandle407
13.1.5　入門函數(shù)體系知識的學(xué)習(xí)思路408
13.2　函數(shù)的基本構(gòu)成409
13.2.1　函數(shù)管理409
13.2.2　函數(shù)元數(shù)據(jù)410
13.2.3　函數(shù)簽名411
13.2.4　泛型變量412
13.2.5　字面量變量414
13.2.6　自動注入的參數(shù)415
13.3　函數(shù)相關(guān)的主要流程415
13.3.1　引擎啟動時的函數(shù)注冊415
13.3.2　查詢執(zhí)行時的函數(shù)解析416
13.3.3　查詢執(zhí)行時的函數(shù)調(diào)用418
13.4　總結(jié)、思考、實(shí)踐419
第14章　自定義函數(shù)開發(fā)實(shí)踐421
14.1　標(biāo)量函數(shù)開發(fā)方法421
14.1.1　注解框架422
14.1.2　底層開發(fā)428
14.2　聚合函數(shù)開發(fā)實(shí)踐433
14.2.1　實(shí)現(xiàn)聚合函數(shù)的核心原理433
14.2.2　注解框架435
14.2.3　底層開發(fā)436
14.3　總結(jié)、思考、實(shí)踐444