第一篇 查询优化技术 2
第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查询优化器原理解析 76
第5章PostgreSQL查询优化器概述 76
5.1 PostgreSQL查询执行过程 76
5.2 PostgreSQL查询优化器的 78
架构和设计思想 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查询优化器原理解析 266
第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.prep——优化前的准备工作 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查询优化器 430
第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