本书基于开源数据库管理系统PostgreSQL 8.4.1,对其底层运行、实现机制进行了详尽介绍,使读者从全局的角度理解数据库管理系统。
随着信息化进程的加快,数据库管理系统的新的应用领域不断出现,现有的数据库管理系统产品已经不能满足日益出现的新需求。很多用户开始采用开源数据库管理系统或者在其上定制、开发满足自己需求的数据库管理系统。开源数据库管理系统已经脱离纯研究层面,吸引大批技术开发人员、研究者以及其他技术爱好者的注意。
本书是全面分析开源数据库管理系统PostgreSQL的开山之作,引导读者轻松、透彻地理解数据库管理系统的内部运行机制,揭示实际数据库管理系统的运行过程。读者更可以通过阅读本书深入地理解、认识数据库或者验证数据库的新技术,进而有助于读者基于 PostgreSQL定制数据库系统、开发数据库内核或数据库管理系统。
本书的特点
本书按照PostgreSQL的体系结构,从存储、索引、查询编译、查询执行、并发控制以及安全几个方面切入,全面介绍PostgreSQL各种机制的运行原理。
为了清晰阐述复杂的运行机理,书中穿插了大量的原理图、程序流程图进行辅助讲解,使数据库的运行过程一目了然。
本书没有单纯地介绍数据库原理或逐行分析源代码,而是从数据库设计者的角度,阐释数据库内部各个模块之间如何配合实现各种功能。
本书对PostgreSQL的分析工作基于PostgreSQL 8.4.1,该版本的源代码可以从ftp://ftp-archives.postgresql.org/pub/source/v8.4.1/下载。
随着计算机与互联网技术的发展和普及,数据库技术已经渗透到人们日常生活的每个角落,无论是信息检索、电子商务、网上交友,还是日常工作时使用的各种信息管理系统,无一例外地都用到了数据库管理系统,它已经成为最常用的软件之一。
目前,市场上有多种数据库管理系统产品,商业版数据库管理系统产品有Oracle、DB2、SQL Server等,开源版数据库管理系统产品有PostgreSQL、MySQL等。商业版数据库管理系统虽占据着较大的市场份额,但随着新的应用领域的出现以及成本方面的考虑,有很多用户开始采用开源版的数据库管理系统或者在开源数据库基础之上定制自己的数据库管理系统。
开源数据库管理系统的广泛使用也吸引了大量的开发者、技术人员,与此同时也出现了大量与数据库管理系统相关的技术性书籍和教材。但这些书籍要么是介绍数据库管理系统的管理和使用技巧,要么是介绍如何在这些数据库管理系统上开发应用,鲜见从数据库底层实现的角度来分析数据库系统内部实现机制的书籍。
本书尝试从PostgreSQL数据库源代码入手,介绍典型开源数据库管理系统的内部实现细节,揭开一个真正的数据库管理系统的内部奥秘。写作本书的重要动机是向数据库内核开发人员以及科研人员介绍PostgreSQL的实现机制,帮助他们基于PostgreSQL定制满足特定需求的数据库系统,或者在数据库内核中实现并验证数据库的新技术。我们希望本书有助于不同背景和经验的人交换对PostgreSQL源代码的理解,为进一步推进PostgreSQL的发展及使用做出贡献。
读者定位
对本书感兴趣的读者包括:数据库内核开发人员、研究人员、DBA、高校学生、教师以及其他希望了解数据库内核实现的人们。
对于那些希望在PostgreSQL内核中进行改进或裁剪形成自己组织内部定制数据库的开发人员来说,本书将有助于他们了解PostgreSQL内部的实现机制,从而可以按照需要对数据库进行修改。
本书也可以作为计算机专业高年级本科生或者研究生的教材,尤其对于那些日后希望从事数据库领域研究的学生,我们希望本书能够激发学生对数据库内部实现机制的兴趣。
为更好地理解本书的内容,我们希望读者能具备以下基础:
了解数据库系统的基本概念和常用术语。
有使用PostgreSQL开发应用的实际经验。
阅读过介绍数据库系统实现基本原理的书籍。
本书的组织
本书的组织如下:
第1章介绍PostgreSQL的发展历史、特点、在商业领域的应用以及源代码的结构、安装、使用等内容。
第2章介绍PostgreSQL的体系结构,包括系统表的结构和用途、数据集簇、进程结构,并重点分析了守护进程Postmaster、服务进程Postgres以及各个辅助进程的实现机制。
第3章介绍PostgreSQL的存储管理,对PostgreSQL中管理内存和外存的方式进行了详细分析。
第4章介绍PostgreSQL的索引机制,分析了B-Tree、Hash、GiST、GIN等索引的组织结构、操作方式,并介绍了全文搜索TSearch 2模块的实现与使用。
第5章介绍PostgreSQL的查询编译器,给出了如何将一个SQL命令进行编译、优化并最终形成执行计划的过程。
第6章介绍PostgreSQL的查询执行器,描述了执行计划如何被PostgreSQL进行解释执行,对执行计划中每一种节点的执行算法给出了详细分析。
第7章介绍PostgreSQL的并发控制机制,给出了事务系统和日志系统的具体实现方法。
第8章介绍PostgreSQL的安全措施,描述了用户标识与认证、权限管理和对象访问控制等有关数据库安全措施方面的实现细节。
源代码版本
本书对PostgreSQL的分析工作基于PostgreSQL 8.4.1,该版本的源代码可以从以下地址下载:ftp://ftp-archives.postgresql.org/pub/source/v8.4.1/。
错误
由于作者的水平有限,本书可能包含笔误、差错或遗漏,我们非常希望您能够告诉我们所发现的错误以及对于本书的建议或批评。您可以发送电子邮件到pgbook@whu.edu.cn,很抱歉我们可能无法一一回答所有的电子邮件,但是我们会将发现的错误和收到的建议整理后公布在网址http://totemdb.whu.edu.cn/pgbook/以及华章网站http://www.hzbook.com上。
致谢
本书的内容是武汉大学珞珈图腾数据库实验室对于PostgreSQL十年分析工作的结晶,在这十年中,实验室的各届研究生进行了不懈的努力,对此做出了巨大的贡献,在此两位作者对他们在PostgreSQL代码分析过程中付出的辛勤劳动表示由衷的感谢!在编写本书的过程中,作者参阅了相关的书籍、网上资料、技术文档等,在此也向这些资料的作者表示感谢!
计算机\数据库
随着信息化进程的加快,数据库管理系统的新的应用领域不断出现,现有的数据库管理系统产品已经不能满足日益出现的新需求。很多用户开始采用开源数据库管理系统或者在其上定制、开发满足自己需求的数据库管理系统。开源数据库管理系统已经脱离纯研究层面,吸引大批技术开发人员、研究者以及其他技术爱好者的注意。
本书是全面分析开源数据库管理系统PostgreSQL的开山之作,引导读者轻松、透彻地理解数据库管理系统的内部运行机制,揭示实际数据库管理系统的运行过程。读者更可以通过阅读本书更深入地理解、认识数据库的或者验证数据库的新技术,进而有助于他们基于 PostgreSQL定制数据库系统、开发数据库内核或数据库管理系统。
本书的特点
本书按照PostgreSQL的体系结构,从存储、索引、查询编译、查询执行、并发控制以及安全几个方面切入,全面介绍了PostgreSQL各种机制的运行原理。
为了清晰阐述复杂的运行机理,书中穿插了大量的原理图、程序流程图进行辅助讲解,使数据库的运行过程一目了然。
本书没有单纯地介绍数据库原理或逐行分析源代码,而是从数据库设计者的角度,阐释数据库内部各个模块之间如何配合实现各种功能。
本书对PostgreSQL的分析工作基于PostgreSQL 8.4.1,该版本的源代码可以从ftp://ftp-archives.postgresql.org/pub/source/v8.4.1/下载。
前 言
第1章 PostgreSQL系统概述/1
1.1 PostgreSQL简介及发展历程/1
1.2 PostgreSQL的特性/2
1.3 PostgreSQL的应用/3
1.4 PostgreSQL代码结构/3
1.5 安装PostgreSQL/4
1.6 PostgreSQL数据库命令/5
第2章 PostgreSQL的体系结构/7
2.1 系统表/8
2.1.1 主要系统表功能及依赖关系/8
2.1.2 系统视图/14
2.2 数据集簇/15
2.2.1 initdb的使用/17
2.2.2 postgres.bki/17
2.2.3 initdb的执行过程/19
2.2.4 系统数据库/20
2.3 PostgreSQL进程结构/21
2.4 守护进程Postmaster/22
2.4.1 初始化内存上下文/23
2.4.2 配置参数/23
2.4.3 创建监听套接字/28
2.4.4 注册信号处理函数/29
2.4.5 辅助进程启动/31
2.4.6 装载客户端认证文件/32
2.4.7 循环等待客户连接请求/33
2.5 辅助进程/34
2.5.1 SysLogger系统日志进程/34
2.5.2 BgWriter后台写进程/36
2.5.3 WalWriter预写式日志写进程/38
2.5.4 PgArch预写式日志归档进程/40
2.5.5 AutoVacuum系统自动清理进程/41
2.5.6 PgStat统计数据收集进程/44
2.6 服务进程Postgres/47
2.6.1 初始化内存环境/48
2.6.2 配置运行参数和处理客户端传递的GUC参数/48
2.6.3 设置信号处理和信号屏蔽/48
2.6.4 初始化Postgres的运行环境/49
2.6.5 创建内存上下文并设置查询取消跳跃点/50
2.6.6 循环等待处理查询/50
2.6.7 简单查询的执行流程/52
2.7 小结/53
第3章 存储管理/54
3.1 存储管理器的体系结构/54
3.2 外存管理/57
3.2.1 表和元组的组织方式/58
3.2.2 磁盘管理器/60
3.2.3 VFD机制/61
3.2.4 空闲空间映射表/64
3.2.5 可见性映射表/69
3.2.6 大数据存储/69
3.3 内存管理/76
3.3.1 内存上下文概述/77
3.3.2 高速缓存/84
3.3.3 缓冲池管理/94
3.3.4 IPC/102
3.4 表操作与元组操作/106
3.4.1 表操作/106
3.4.2 元组操作/112
3.5 VACUUM机制/115
3.5.1 VACUUM操作/115
3.5.2 Lazy VACUUM/116
3.5.3 Full VACUUM/118
3.6 ResourceOwner资源跟踪/120
3.7 小结/122
第4章 索引/123
4.1 概述/123
4.1.1 索引方式/124
4.1.2 索引类型/125
4.1.3 索引相关系统表/125
4.1.4 索引的操作函数/129
4.2 B-Tree索引/131
4.2.1 B-Tree索引的组织结构/132
4.2.2 B-Tree索引的操作/135
4.3 Hash索引/146
4.3.1 Hash索引的组织结构/147
4.3.2 Hash索引的实现/153
4.4 GiST索引/161
4.4.1 GiST的扩展性/161
4.4.2 GiST索引的组织结构/162
4.4.3 GiST索引的实现/163
4.4.4 GiST索引实例/166
4.5 GIN索引/168
4.5.1 GIN索引的扩展性/168
4.5.2 GIN索引的组织结构/170
4.5.3 GIN索引的操作/172
4.6 TSearch2全文搜索/179
4.6.1 全文索引的创建/180
4.6.2 全文索引的查询/184
4.6.3 查询结果处理/185
4.7 小结/186
第5章 查询编译/187
5.1 概述/187
5.2 查询分析/188
5.2.1 Lex和Yacc简介/189
5.2.2 词法和语法分析/193
5.2.3 语义分析/208
5.3 查询重写/218
5.3.1 规则系统/219
5.3.2 查询重写的处理操作/224
5.4 查询规划/228
5.4.1 总体处理流程/229
5.4.2 预处理/237
5.4.3 生成路径/240
5.4.4 生成可优化的MIN/MAX聚集计划/253
5.4.5 生成普通计划/254
5.4.6 生成完整计划/257
5.4.7 整理计划树/259
5.4.8 实例分析/260
5.5 代价估计/266
5.5.1 代价估算公式/267
5.5.2 选择度/268
5.5.3 单个表的扫描代价/268
5.5.4 两个表的连接代价/268
5.6 PostgreSQL中的遗传算法/268
5.6.1 个体编码方式及种群初始化/269
5.6.2 适应值/270
5.6.3 父体选择策略/270
5.6.4 杂交算子/270
5.6.5 变异算子/275
5.6.6 终止条件/275
5.6.7 基于排列生成路径/276
5.6.8 实例分析/276
5.7 小结/280
第6章 查询执行/282
6.1 查询执行策略/283
6.1.1 可优化语句和数据定义语句/284
6.1.2 四种执行策略/284
6.1.3 策略选择的实现/286
6.1.4 Portal执行的过程/288
6.2 数据定义语句执行/289
6.2.1 数据定义语句执行流程/289
6.2.2 执行实例/290
6.2.3 主要的功能处理器函数/293
6.3 可优化语句执行/293
6.3.1 物理代数与处理模型/294
6.3.2 物理操作符的数据结构/295
6.3.3 执行器的运行/297
6.3.4 执行实例/301
6.4 计划节点/303
6.4.1 控制节点/304
6.4.2 扫描节点/310
6.4.3 物化节点/319
6.4.4 连接节点/328
6.5 其他子功能介绍/334
6.5.1 元组操作/334
6.5.2 表达式计算/337
6.5.3 投影操作/340
6.6 小结/342
第7章 事务处理与并发控制/343
7.1 事务系统简介/343
7.2 事务系统的上层/344
7.2.1 事务块状态/345
7.2.2 事务块操作/346
7.3 事务系统的底层/348
7.3.1 事务状态/348
7.3.2 事务操作函数/350
7.3.3 简单查询事务执行过程实例/352
7.4 事务保存点和子事务/353
7.4.1 保存点实现原理/353
7.4.2 子事务/353
7.5 两阶段提交/354
7.5.1 预提交阶段/354
7.5.2 全局提交阶段/355
7.6 PostgreSQL的并发控制/355
7.7 PostgreSQL中的三种锁/357
7.7.1 SpinLock/357
7.7.2 LWLock/358
7.7.3 RegularLock/360
7.8 锁管理机制/368
7.8.1 表粒度的锁操作/368
7.8.2 页粒度的锁操作/369
7.8.3 元组粒度的锁操作/369
7.8.4 事务粒度的锁操作/369
7.8.5 一般对象的锁操作/369
7.9 死锁处理机制/370
7.9.1 死锁处理相关数据结构/371
7.9.2 死锁处理相关操作/372
7.10 多版本并发控制/373
7.10.1 MVCC相关数据结构/373
7.10.2 MVCC相关操作/375
7.10.3 MVCC与快照/379
7.11 日志管理/380
7.11.1 SLRU缓冲池/381
7.11.2 CLOG日志管理器/386
7.11.3 SUBTRANS日志管理器/390
7.11.4 MULTIXACT日志管理器/392
7.11.5 XLOG日志管理器/394
7.11.6 日志管理器总结/402
7.12 小结/403
第8章 数据库安全/404
8.1 PostgreSQL安全简介/404
8.2 用户标识和认证/405
8.2.1 客户端配置文件/406
8.2.2 认证方法/408
8.2.3 客户端认证/410
8.3 基于角色的权限管理/413
8.3.1 用户和角色/413
8.3.2 角色相关的系统表/415
8.3.3 角色管理/416
8.4 对象访问控制/426
8.4.1 访问控制列表/426
8.4.2 对象权限管理/428
8.4.3 对象权限检查/432
8.5 小结/433
附录A 用Eclipse开发和调试PostgreSQL/434