數據庫查詢優化器的藝術：原理解析與SQL性能優化（簡體書）

目 錄
推薦序一
推薦序二
前 言
第一篇 查詢優化技術
第1章 數據管理系統的查詢優化  2
1.1 數據庫調優  3
1.2 查詢優化技術  5
1.2.1 查詢重用  5
1.2.2 查詢重寫規則  6
1.2.3 查詢算法優化  6
1.2.4 并行查詢優化  8
1.2.5 分布式查詢優化  9
1.2.6 其他優化  9
1.3 本章小結  9
第2章 邏輯查詢優化  10
2.1 查詢優化技術的理論基礎  10
2.1.1 關系代數  11
2.1.2 關系代數等價變換規則對優化的指導意義  13
2.2 查詢重寫規則  17
2.2.1 子查詢的優化  18
2.2.2 視圖重寫  28
2.2.3 等價謂詞重寫  29
2.2.4 條件化簡  32
2.2.5 外連接消除  33
2.2.6 嵌套連接消除  37
2.2.7 連接消除  38
2.2.8 語義優化  40
2.2.9 針對非SPJ的優化  41
2.3 啟發式規則在邏輯優化階段的應用  42
2.4 本章小結  43
第3章 物理查詢優化  44
3.1 查詢代價估算  44
3.1.1 代價模型  44
3.1.2 選擇率計算的常用方法  45
3.2 單表掃描算法  45
3.2.1 常用的單表掃描算法  45
3.2.2 單表掃描代價計算  47
3.3 索引  47
3.3.1 如何利用索引  47
3.3.2 索引列的位置對使用索引的影響  50
3.3.3 聯合索引對索引使用的影響  56
3.3.4 多個索引對索引使用的影響  57
3.4 兩表連接算法  59
3.4.1 基本的兩表連接算法  59
3.4.2 進一步認識兩表連接算法  61
3.4.3 連接操作代價計算  61
3.5 多表連接算法  62
3.5.1 多表連接順序  62
3.5.2 常用的多表連接算法  63
3.5.3 多表連接算法的比較  68
3.6 本章小結  68
第4章 查詢優化器與其他模塊的關系  70
4.1 查詢優化器整體介紹  70
4.2 查詢優化器與其他模塊的關系  73
4.3 本章小結  74
第二篇 PostgreSQL查詢優化器原理解析
第5章 PostgreSQL查詢優化器概述  76
5.1 PostgreSQL查詢執行過程  76
5.2 PostgreSQL查詢優化器的架構和設計思想  78
5.2.1 PostgreSQL查詢優化器架構  79
5.2.2 PostgreSQL查詢優化器的層次  81
5.2.3 PostgreSQL查詢優化器設計思想  81
5.3 主要概念  81
5.4 代碼層次結構  85
5.5 本章小結  86
第6章 PostgreSQL查詢優化器相關數據結構  88
6.1 主要數據結構  88
6.1.1 基本數據結構  88
6.1.2 查詢樹  91
6.1.3 各種對象的結構  95
6.1.4 連接操作相關的結構  99
6.1.5 查詢執行計劃相關的結構  104
6.2 各個結構之間的關系  108
6.3 各個階段間和主要結構體間的關系  109
6.4 本章小結  110
第7章 PostgreSQL查詢優化器實現原理解析  111
7.1 查詢優化整體流程  111
7.2 查詢優化器實現原理解析  115
7.2.1 planner——主入口函數  115
7.2.2 standard_planner——標準的查詢優化器函數  116
7.2.3 subquery_planner——生成（子）查詢執行計劃函數  117
7.2.4 grouping_planner——生成查詢執行計劃并對非SPJ優化  139
7.2.5 build_minmax_path——聚集函數MIN/MAX的優化函數  141
7.2.6 query_planner——生成最優的查詢路徑函數  142
7.2.7 make_one_rel——構造多表連接路徑并選出最優路徑函數  148
7.2.8 make_rel_from_joinlist——生成多表連接路徑函數  153
7.2.9 optimize_minmax_aggregates——聚集操作MIN/MAX優化函數  163
7.2.10 create_plan——創建查詢執行計劃函數  164
7.2.11 非SPJ處理——grouping_planner的各個子模塊  166
7.2.12 其他重要的函數與操作  170
7.3 代價估算實現原理解析  174
7.3.1 查詢代價估算  174
7.3.2 單表掃描方式的代價估算  174
7.3.3 兩表連接的代價估算  178
7.3.4 其他代價估算函數  184
7.3.5 選擇率的計算  185
7.4 從結構和文件功能角度看查詢優化器  186
7.4.1 查詢優化子模塊與主要文件的關系  187
7.4.2 查詢優化器代碼結構  187
7.5 本章小結  190
第8章 從功能的角度看PostgreSQL查詢優化  192
8.1 優化器之邏輯查詢優化  192
8.1.1 視圖重寫  193
8.1.2 子查詢優化  197
8.1.3 等價謂詞重寫  209
8.1.4 條件化簡  209
8.1.5 外連接消除  210
8.1.6 嵌套連接消除  217
8.1.7 連接的消除  218
8.1.8 語義優化  221
8.1.9 選擇操作下推  226
8.1.10 非SPJ優化  226
8.2 優化器之物理查詢優化  229
8.2.1 PostgreSQL的物理優化主要完成的工作  229
8.2.2 啟發式規則在物理查詢優化階段的使用  230
8.2.3 兩表連接  230
8.2.4 代價估算  230
8.2.5 PostgreSQL的索引與查詢優化  231
8.3 其他  237
8.3.1 grouping_planner函數主干再分析  238
8.3.2 用戶指定的連接語義與PostgreSQL實現兩表連接的函數及算法的關系  240
8.3.3 集合操作優化  242
8.4 本章小結  245
第9章 PostgreSQL查詢優化的關鍵算法  246
9.1 動態規劃算法  246
9.1.1 動態規劃算法的處理流程  247
9.1.2 緊密樹處理流程  248
9.2 遺傳算法  248
9.2.1 PostgreSQL遺傳算法的處理流程  248
9.2.2 主要的數據結構  250
9.2.3 主要的函數和變量  251
9.2.4 應用遺傳算法實現表連接的語義  253
9.2.5 應用遺傳算法計算適應度  254
9.2.6 進一步理解PostgreSQL的遺傳算法  255
9.3 動態規劃算法與遺傳算法對比  256
9.4 本章小結  257
第10章 PostgreSQL查詢優化器與其他部分的關系  259
10.1 查詢優化器與語法分析器  259
10.2 查詢優化器與執行器  260
10.3 查詢優化器與緩沖區管理模塊  261
10.4 查詢優化器與對象訪問模塊  262
10.5 查詢優化器與統計模塊  262
10.6 查詢優化器與索引模塊  263
10.7 本章小結  263
第三篇 MySQL查詢優化器原理解析
第11章 MySQL查詢優化器概述  266
11.1 MySQL查詢執行過程  266
11.2 MySQL查詢優化器的架構和設計思想  267
11.2.1 MySQL查詢優化器架構  268
11.2.2 MySQL查詢優化器的層次  269
11.2.3 MySQL查詢優化器設計思想  269
11.3 主要概念  270
11.3.1 常量表  270
11.3.2 表數據的訪問方式  270
11.4 代碼層次結構  272
11.5 本章小結  274
第12章 MySQL查詢優化器相關數據結構  275
12.1 主要的類和數據結構  275
12.1.1 查詢樹  275
12.1.2 基本對象  276
12.1.3 連接對象與執行計劃  278
12.1.4 代價估算類  281
12.2 各個階段主要結構體間的關系  282
12.3 本章小結  282
第13章 MySQL查詢優化器的原理解析  283
13.1 查詢優化器整體流程  283
13.2 優化器的代碼詳解  285
13.2.1 JOIN.prepare——優化前的準備工作  286
13.2.2 JOIN.optimize——優化器主入口方法  299
13.2.3 make_join_statistics——計算最優的查詢優化執行計劃  315
13.2.4 choose_table_order——求解多表連接最優連接路徑  324
13.2.5 make_join_statistics函數的其他子函數  339
13.2.6 make_join_select——對條件求值、下推連接條件到表中  348
13.2.7 test_if_skip_sort_order——排序操作的優化  350
13.2.8 make_join_readinfo——為連接的每個表構造信息  351
13.2.9 JOIN.exec——執行查詢執行計劃的函數  353
13.3 代價估算  354
13.3.1 查詢代價估算模型  354
13.3.2 查詢代價估算過程  355
13.3.3 其他的代價估算  358
13.3.4 對存儲引擎的調用接口  362
13.3.5 統計信息  364
13.4 本章小結  365
第14章 從功能的角度看MySQL查詢優化  366
14.1 優化器之邏輯查詢優化  366
14.1.1 視圖重寫  367
14.1.2 子查詢優化  371
14.1.3 等價謂詞重寫  387
14.1.4 條件化簡  388
14.1.5 外連接消除  389
14.1.6 嵌套連接消除  396
14.1.7 連接的消除  398
14.1.8 語義優化  400
14.1.9 非SPJ優化  406
14.2 優化器之物理查詢優化  412
14.2.1 MySQL的物理優化主要完成的工作  412
14.2.2 啟發式規則在物理查詢優化階段的使用  413
14.2.3 MySQL的索引與查詢優化  413
14.2.4 用戶指定的連接語義與MySQL實現兩表連接的算法  417
14.3 本章小結  418
第15章 MySQL查詢優化的關鍵算法  419
15.1 深入理解MySQL的多表連接算法  419
15.2 本章小結  424
第16章 MySQL查詢優化器與其他部分的關系  425
16.1 查詢優化器與語法分析器  425
16.2 查詢優化器與執行器  426
16.3 查詢優化器與緩沖區管理模塊  426
16.4 查詢優化器與索引模塊  426
16.5 本章小結  427
第四篇 PostgreSQL查詢優化器 VS MySQL查詢優化器
第17章 PostgreSQL和MySQL的邏輯查詢優化技術  430
17.1 查詢重寫  430
17.1.1 子查詢優化  430
17.1.2 視圖重寫  443
17.1.3 等價謂詞重寫  446
17.1.4 條件化簡  447
17.1.5 外連接消除  448
17.1.6 嵌套連接消除  449
17.1.7 連接消除  451
17.1.8 語義優化  452
17.2 非SPJ的優化  452
17.3 本章小結  456
第18章 PostgreSQL和MySQL的物理查詢優化技術  457
18.1 查詢代價估算模型比較  457
18.2 單表掃描算法  458
18.3 索引  458
18.4 兩表連接算法  466
18.5 多表連接算法  467
18.6 本章小結  467
第19章 PostgreSQL和MySQL的其他異同  468
19.1 啟發式規則的使用比較  468
19.2 綜合比較  469
19.2.1 基本概念的比較  469
19.2.2 數據結構的比較  469
19.2.3 設計思想的比較  469
19.2.4 編碼規范的比較  470
19.3 本章小結  471
附錄A 如何掌握數據庫內核  472
附錄B 如何閱讀本書  496
附錄C 如何閱讀查詢執行計劃  498
附錄D 如何跟蹤查詢執行計劃  508