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

Contents　目　錄
序一
序二
序三
序四（原版）
序四（中文版）
前言
致謝一
致謝二
第一篇　背景知識(shí)
第1章　OLAP引擎介紹與對(duì)比2
1.1　OLAP的定義與對(duì)比標(biāo)準(zhǔn)2
1.1.1　OLAP的定義2
1.1.2　OLAP引擎之間的對(duì)比標(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　再談對(duì)Presto技術(shù)發(fā)展的理解13
1.4　總結(jié)、思考、實(shí)踐15
第2章　Presto基本介紹16
2.1　Presto概述：特性、原理、架構(gòu)16
2.1.1　一個(gè)高性能、分布式的SQL
　　　執(zhí)行框架17
2.1.2　一套插件化體系18
2.1.3　開(kāi)箱即用的SQL內(nèi)置函數(shù)和
　　　連接器20
2.2　Presto的應(yīng)用場(chǎng)景與企業(yè)案例20
2.2.1　Presto的應(yīng)用場(chǎng)景20
2.2.2　Presto的企業(yè)案例21
2.2.3　Presto不適合哪些場(chǎng)景23
2.3　Presto常見(jiàn)問(wèn)題及應(yīng)對(duì)策略25
2.3.1　查詢協(xié)調(diào)節(jié)點(diǎn)單點(diǎn)問(wèn)題25
2.3.2　查詢執(zhí)行過(guò)程沒(méi)有容錯(cuò)機(jī)制27
2.3.3　查詢執(zhí)行時(shí)報(bào)錯(cuò)exceeding
　　　memory limits27
2.3.4　無(wú)法動(dòng)態(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選擇哪個(gè)30
2.4.2　本書(shū)為什么用Trino的v350
　　　版本來(lái)做介紹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自動(dòng)生成的代碼
　　　為generated source36
2.5.5　在IDEA中運(yùn)行3個(gè)節(jié)點(diǎn)的
　　　Presto集群38
2.5.6　運(yùn)行Presto命令行工具44
2.5.7　調(diào)試Presto源碼常見(jiàn)問(wèn)題44
2.6　基于Presto的數(shù)據(jù)倉(cāng)庫(kù)及本書(shū)
　　常用SQL46
2.6.1　數(shù)據(jù)倉(cāng)庫(kù)介紹46
2.6.2　TPC-DS Data Model數(shù)據(jù)
　　　模型介紹47
2.6.3　本書(shū)常用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查詢請(qǐng)求60
3.3.2　詞法與語(yǔ)法分析并生成抽象
　　　語(yǔ)法樹(shù)62
3.3.3　創(chuàng)建并提交QueryExecution63
3.4　執(zhí)行計(jì)劃的生成與優(yōu)化64
3.4.1　語(yǔ)義分析，生成執(zhí)行計(jì)劃64
3.4.2　優(yōu)化執(zhí)行計(jì)劃，生成優(yōu)化后
　　　的執(zhí)行計(jì)劃65
3.4.3　將邏輯執(zhí)行計(jì)劃樹(shù)拆分為
　　　多棵子樹(shù)68
3.5　執(zhí)行計(jì)劃的調(diào)度69
3.5.1　創(chuàng)建SqlStageExecution69
3.5.2　調(diào)度并分發(fā)HttpRemoteTask72
3.6　執(zhí)行計(jì)劃的執(zhí)行78
3.6.1　在多個(gè)查詢執(zhí)行節(jié)點(diǎn)上執(zhí)行
　　　任務(wù)78
3.6.2　分批返回查詢計(jì)算結(jié)果給
　　　SQL客戶端85
3.7　總結(jié)、思考、實(shí)踐87
第4章　查詢引擎核心模塊拆解88
4.1　執(zhí)行計(jì)劃生成的設(shè)計(jì)實(shí)現(xiàn)88
4.1.1　從SQL到抽象語(yǔ)法樹(shù)88
4.1.2　語(yǔ)義分析95
4.1.3　生成初始邏輯執(zhí)行計(jì)劃101
4.2　執(zhí)行計(jì)劃優(yōu)化的目的、基本
　　原理和基礎(chǔ)算法106
4.2.1　執(zhí)行計(jì)劃優(yōu)化的目的106
4.2.2　執(zhí)行計(jì)劃優(yōu)化的基本原理106
4.2.3　執(zhí)行計(jì)劃優(yōu)化的基礎(chǔ)算法110
4.3　執(zhí)行計(jì)劃優(yōu)化的設(shè)計(jì)實(shí)現(xiàn)115
4.3.1　執(zhí)行計(jì)劃優(yōu)化的工作流程115
4.3.2　非迭代式優(yōu)化器和迭代式
　　　優(yōu)化器118
4.4　總結(jié)、思考、實(shí)踐125
第三篇　經(jīng)典SQL
第5章　數(shù)據(jù)過(guò)濾與投影相關(guān)查詢
　　　　的執(zhí)行原理解析128
5.1　SQL-01簡(jiǎn)單拉取數(shù)據(jù)查詢的
　　　實(shí)現(xiàn)原理128
5.1.1　執(zhí)行計(jì)劃的生成與優(yōu)化128
5.1.2　分布式調(diào)度與執(zhí)行的設(shè)計(jì)實(shí)現(xiàn)130
5.2　SQL-02數(shù)據(jù)過(guò)濾與投影查詢的
　　實(shí)現(xiàn)原理134
5.2.1　執(zhí)行計(jì)劃的生成與優(yōu)化134
5.2.2　分布式調(diào)度與執(zhí)行的設(shè)計(jì)實(shí)現(xiàn)136
5.3　數(shù)據(jù)過(guò)濾與投影相關(guān)查詢涉及
　　的查詢優(yōu)化147
5.3.1　列裁剪147
5.3.2　部分計(jì)算下推到存儲(chǔ)服務(wù)148
5.3.3　表達(dá)式計(jì)算的優(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í)行計(jì)劃的生成與優(yōu)化154
6.1.2　分布式調(diào)度與執(zhí)行的設(shè)計(jì)
　　　實(shí)現(xiàn)155
6.2　SQL-11 排序查詢的實(shí)現(xiàn)原理158
6.2.1　執(zhí)行計(jì)劃的生成與優(yōu)化158
6.2.2　分布式調(diào)度與執(zhí)行的設(shè)計(jì)實(shí)現(xiàn)160
6.3　SQL-12 排序與行數(shù)限定組合
　　查詢的實(shí)現(xiàn)原理174
6.3.1　執(zhí)行計(jì)劃的生成與優(yōu)化174
6.3.2　分布式調(diào)度與執(zhí)行的設(shè)計(jì)實(shí)現(xiàn)176
6.4　簡(jiǎn)單SELECT查詢相關(guān)的查詢
　　優(yōu)化191
6.4.1　將LIMIT計(jì)算下推到數(shù)據(jù)
　　　源連接器191
6.4.2　去除不需要的LIMIT計(jì)算192
6.5　總結(jié)、思考、實(shí)踐193
第7章　簡(jiǎn)單聚合查詢的執(zhí)行原理
　　　　解析194
7.1　聚合查詢?cè)硗ㄗR(shí)性介紹194
7.1.1　常見(jiàn)的聚合查詢194
7.1.2　聚合查詢是有狀態(tài)計(jì)算196
7.1.3　實(shí)現(xiàn)分布式聚合的幾種執(zhí)行
　　　模型196
7.1.4　Presto對(duì)聚合查詢的設(shè)計(jì)與
　　　抽象197
7.2　SQL-20不分組聚合查詢的實(shí)現(xiàn)
　　　原理198
7.2.1　執(zhí)行計(jì)劃的生成與優(yōu)化198
7.2.2　分布式調(diào)度與執(zhí)行的設(shè)計(jì)實(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í)行計(jì)劃的生成與優(yōu)化213
7.3.2　分布式調(diào)度與執(zhí)行的設(shè)計(jì)實(shí)現(xiàn)214
7.3.3　使用Scatter-Gather執(zhí)行模型
　　　實(shí)現(xiàn)SQL-21236
7.3.4　總結(jié)237
7.4　聚合函數(shù)的設(shè)計(jì)與實(shí)現(xiàn)238
7.5　總結(jié)、思考、實(shí)踐240
第8章　復(fù)雜聚合查詢的執(zhí)行原理
　　　　解析242
8.1　SQL-22去重計(jì)數(shù)查詢的實(shí)現(xiàn)
　　原理242
8.1.1　執(zhí)行計(jì)劃的生成與優(yōu)化243
8.1.2　分布式調(diào)度與執(zhí)行的設(shè)計(jì)實(shí)現(xiàn)246
8.1.3　使用Scatter-Gather執(zhí)行模型
　　　實(shí)現(xiàn)SQL-22247
8.1.4　總結(jié)248
8.2　SQL-23多個(gè)聚合計(jì)算查詢的
　　　實(shí)現(xiàn)原理248
8.2.1　執(zhí)行計(jì)劃的生成與優(yōu)化249
8.2.2　分布式調(diào)度與執(zhí)行的設(shè)計(jì)實(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綜合多種計(jì)算查詢的
　 　實(shí)現(xiàn)原理260
8.3.1　執(zhí)行計(jì)劃的生成與優(yōu)化261
8.3.2　分布式調(diào)度與執(zhí)行的設(shè)計(jì)實(shí)現(xiàn)264
8.3.3　使用Scatter-Gather執(zhí)行模型
　　　實(shí)現(xiàn)SQL-30265
8.3.4　總結(jié)266
8.4　常見(jiàn)聚合查詢優(yōu)化手段與優(yōu)化器267
8.4.1　將聚合操作拆分為部分聚合與
　　　最終聚合267
8.4.2　在上下游任務(wù)中傳播哈希聚合
　　　分組列的哈希值267
8.4.3　部分聚合計(jì)算下推268
8.4.4　將ORDER BY與LIMI T計(jì)算
　　　優(yōu)化為TopN計(jì)算268
8.4.5　基于代價(jià)評(píng)估的方式來(lái)決定
　　　如何選擇執(zhí)行模型268
8.4.6　利用存儲(chǔ)的數(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ī)制簡(jiǎn)介272
9.1.1　數(shù)據(jù)交換是什么272
9.1.2　何時(shí)需要做數(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ù)交換的代價(jià)276
9.2　查詢優(yōu)化階段任務(wù)之間數(shù)據(jù)交換
　 　的設(shè)計(jì)實(shí)現(xiàn)276
9.2.1　任務(wù)之間數(shù)據(jù)交換的3個(gè)
　　　階段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è)計(jì)思路
　　　與案例285
9.2.6　拆分PlanFragment296
9.3　查詢調(diào)度與執(zhí)行階段的整體設(shè)計(jì)
　 　思路297
9.3.1　在分布式查詢集群中唯一確定
　　　某個(gè)任務(wù)297
9.3.2　每個(gè)任務(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è)計(jì)302
10.1　查詢調(diào)度階段任務(wù)之間數(shù)據(jù)
　　　交換的設(shè)計(jì)實(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è)計(jì)308
10.2　查詢執(zhí)行階段任務(wù)之間數(shù)據(jù)交換
　　　上游的設(shè)計(jì)實(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è)計(jì)實(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語(yǔ)義328
10.6.3　任務(wù)之間數(shù)據(jù)交換交互中的
　　　　亂序請(qǐng)求328
10.6.4　分批計(jì)算與返回執(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　部分計(jì)算下推371
11.3.6　連接器在查詢執(zhí)行中的作用374
11.4　關(guān)于連接器的一些深入思考375
11.4.1　使用連接器的注意事項(xiàng)376
11.4.2　站在OLAP引擎設(shè)計(jì)者視角來(lái)
　　　　理解連接器的設(shè)計(jì)范式376
11.5　總結(jié)、思考、實(shí)踐377
第12章　連接器開(kāi)發(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ù)原理與開(kāi)發(fā)
第13章　函數(shù)的執(zhí)行原理402
13.1　函數(shù)體系總覽402
13.1.1　函數(shù)分類403
13.1.2　函數(shù)的生命周期403
13.1.3　函數(shù)開(kāi)發(fā)的幾種途徑404
13.1.4　MethodHandle407
13.1.5　入門函數(shù)體系知識(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　自動(dòng)注入的參數(shù)415
13.3　函數(shù)相關(guān)的主要流程415
13.3.1　引擎啟動(dòng)時(shí)的函數(shù)注冊(cè)415
13.3.2　查詢執(zhí)行時(shí)的函數(shù)解析416
13.3.3　查詢執(zhí)行時(shí)的函數(shù)調(diào)用418
13.4　總結(jié)、思考、實(shí)踐419
第14章　自定義函數(shù)開(kāi)發(fā)實(shí)踐421
14.1　標(biāo)量函數(shù)開(kāi)發(fā)方法421
14.1.1　注解框架422
14.1.2　底層開(kāi)發(fā)428
14.2　聚合函數(shù)開(kāi)發(fā)實(shí)踐433
14.2.1　實(shí)現(xiàn)聚合函數(shù)的核心原理433
14.2.2　注解框架435
14.2.3　底層開(kāi)發(fā)436
14.3　總結(jié)、思考、實(shí)踐444