OLAP引擎底層原理與設計實踐

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