目录

目录... 1

图表目录... 4

第一章 引言... 6

1.1 项目修改目标... 6

1.1.1 问题描述... 6

1.1.2 涉及部分... 6

1.2 本报告组织形式... 6

1.3 已做的代码阅读工作简述... 6

第二章 问题分析——查询优化执行流程... 8

2.1 问题总体分析... 8

2.2 查询优化整体流程... 8

2.3 ExecLimit详细分析... 9

2.3.1 ExecLimit关键代码及注释... 9

2.3.2 ExecLimit流程分析与描述... 12

2.3.3 ExecLimit流程图解... 12

2.4 ExecSort详细分析... 12

2.4.1 ExecSort关键代码及注释... 12

2.4.2 ExecSort流程分析与描述... 13

2.4.3 ExecSort流程图解... 13

2.5 tuplesort_performsort详细分析... 14

2.5.1 tuplesort_performsort关键代码及注释... 14

2.5.2 tuplesort_performsort流程分析与描述... 15

2.5.3 tuplesort_performsort 流程图解... 16

2.6 重要的数据结构分析... 16

2.6.1 PlanState. 16

2.6.2 LimitState. 17

2.6.3 SortState. 17

2.6.4 Tuplesortstate. 18

2.7 外存处理流程分析... 18

2.7.1多阶段合并算法... 18

2.7.2 PostgreSQL中多阶段合并算法实现流程... 20

第三章 解决方案设计与实现... 21

3.1 总体思路... 21

3.1.1 参数的传递思路... 21

3.1.2 执行流程修改思路... 21

3.2 简单选择置换方案... 21

3.2.1 方案设计思路... 21

3.2.2参数传递... 21

3.2.3 流程修改... 24

3.2.4 代价分析... 27

3.3 Select(S,K)算法方案... 27

3.3.1 方案设计思路... 27

3.3.2参数传递... 28

3.3.3 流程修改... 28

3.3.4 代价分析... 33

3.4 外存修改方案... 33

3.4.1 方案设计思路... 33

3.4.2 参数传递... 34

3.4.3 流程修改... 36

3.4.4 优化分析... 38

第四章 解决方案测评... 39

@L_301_52@

4.2 测试结果... 40

4.3 总体评价... 40

4.3.1 时间复杂度大为降低... 40

4.3.2 扩展性很好... 41

4.3.3 健壮性比较强... 41

4.3.4 代码风格良好... 41

第五章 遇到的问题及解决方案... 42

5.1 “奇怪”的段错误... 42

5.1.1 问题后果及前因... 42

5.1.2 问题解决之道... 42

5.1.3 经验 结论 技巧... 42

5.2 不能Debug出来的宏错误... 42

5.2.1 问题后果及前因... 42

5.2.2 问题解决之道... 44

5.2.3 经验 结论 技巧... 44

5.3 结构体成员访问错误... 44

5.3.1 问题后果及前因... 44

5.3.2 问题解决之道... 44

5.3.3 经验 结论 技巧... 44

5.4 “防不胜防”的下标出错... 44

5.4.1 问题后果及前因... 44

5.4.2 问题解决之道... 44

5.4.3 经验 结论 技巧... 45

5.5 “不可思议”的死循环... 45

5.5.1 问题后果及前因... 45

5.5.2 问题解决之道... 45

5.5.3 经验 结论 技巧... 47

第六章 心得体会... 48

6.1 版本控制 提纲挈领... 48

6.1.1 版本控制 事关重大... 48

6.1.2 统一注释方便搜索... 48

6.1.3 建立映像文件夹 只保存修改文件... 48

6.2 小议内存 指针乃王道... 48

6.2.1 程序员与内存... 48

6.2.2 类型与变量 指针变量与内存布局... 48

6.2.3 类型与函数 定义与声明... 49

6.3 面向对象 大势所趋... 49

6.3.1 面向过程与面向对象... 49

6.3.2 C与伪继承... 50

6.3.3 C与多态... 50

6.4 编程经验积累... 50

6.4.1 编译与运行 静态与动态... 50

6.4.2 继承与组合 统一与灵活... 51

6.5 一份耕耘 一分收获... 51

参考文献: 51

图表目录

图表 1：exec_simple_query总体流程... 8

图表 2：示例语句的计划树结构... 9

图表 3：ExecLimit关键代码及注释... 11

图表 4：ExecLimit流程图解... 12

图表 5：ExecSort关键代码及注释... 13

图表 6：ExecSort流程图解... 14

图表 7:tuplesort_performsort关键代码及注释... 15

图表 8：tuplesort_performsort 流程图解... 16

图表 9：PlanState关键代码及注释... 16

图表 10：LimitState关键代码及注释... 17

图表 11：SortState 关键代码及注释... 17

图表 12：Tuplesortstate关键代码及注释... 18

图表 13：多阶段合并算法流程示意图... 19

图表 14：多阶段合并算法算法步骤... 19

图表 15：SortState修改关键代码及注释... 22

图表 16：ExecLimit修改关键代码及注释... 23

图表 17：ExecSort修改关键代码 及注释... 24

图表 18：my_tuplesort_performsort关键代码及注释... 26

图表 19：my_simple_select_sort算法实现代码及注释... 27

图表 20：Select(S,K)的算法思想和伪码... 28

图表 21：Select(S,K)中子问题示意图... 28

图表 22：Select(S,K)所有相关代码及注释... 33

图表 23：Select(S,K)子问题规模示意图... 33

图表 24：Tuplesortstate修改代码及注释... 35

图表 25：Tuplesortstate的参数传递... 36

图表 26：beginmerge修改关键代码及注释... 38

图表 27：测试方案实现代码... 40

图表 28：用宏实现的swap注释及测试代码... 43

图表 29：“不可思议”的死循环BUG的跟踪观察结果... 45

图表 30：“不可思议”的死循环问题的解决代码... 46

图表 31：类的内存布局测试代码... 49

Postgresql源码修改报告

——查询优化

摘 要： Postgresql是一个优秀的开放源码数据库管理软件，阅读分析其实现代码，并在其基础上修改或扩展其功能，对于学习《数据库系统实现》课程和提高自己实践能力都有很大的帮助。

本文着力于分析Postgresql的查询处理的部分的流程与实现，为在Postgresql基础上实现查询优化的扩展功能。

关键词:：@H_479_1404@Postgresql;查询处理;查询优化; 数据库系统实现;代码修改;课程实习

第一章 引言

1.1 项目修改目标

1.1.1 问题描述

返回行数限制的优化。原来：真正对查询结果排序后才返回指定行。希望能修改为：查询结果进行一遍扫描即返回指定行。

比如select * from teacher order by name limits 2 offset 1.原来Postgresql是全排序后返回第2和第3大的元素。现在希望不用全排序，也可以返回正确的两个元组。

1.1.2 涉及部分

查询优化和执行。控制和修改查询树执行的流程。

1.2 本报告组织形式

本文主体部分共分六章。

第一章 引言，提出问题，主要介绍了实习的目标和之前做的代码阅读情况。

第二章 分析问题，详细分析了目标相关的所有重要的执行模块流程及数据结构。在每个模块流程分析的小节中，又分为关键代码及注释、流程分析与描述和流程图解三部分，从不同的角度分析模块的执行与实现。所有对流程以分析又可以分为两种，一种是对内存模式的分析，一种是对外存模式的分析，其中，内存模式是本文的重点。

第三章 解决问题，在提出总体思路之后，又分别提出三种不同的解决方案的设计和实现。在每个方案中，又可分为四节：方案设计思路、参数传递、流程修改、代价分析。第一节为方案的总体设计思路，第二与第三节为方案的具体实现，含有关键的代码及注释。第四节为方案的评测，对方案提出的算法设计，进行理论上的算法代价估计。

第四章 解决方案测评，就测试方案，测试结果和总体评价三个方面对提出的解决方案做一个实际用例的测试和评价。

第五章 遇到的问题及解决方案，主要是记录在具体的实习的过程中，总结了自己遇到的部分实际问题，我们觉得这些实际的问题具有一定的普遍性，因此归纳出来，以方便后续的研究者。每个问题都分为三小节，分别叙述“问题后果及前因”、“问题解决之道”及“经验 结论 技巧”。

最后一章第六章 为实习的心得体会。主要是对项目管理、程序设计、C特性和编程经验的总结，最后还有一点小小的感言，以鼓励他人，也鼓励自己。

1.3 已做的代码阅读工作简述

通过前期有代码阅读，我们已经知道：Postgresql从用户输入查询到最后结果的输出可以分为两个大的部分：前台处理和后台执行。其中后台执行又有四个部分：Parser,Rewriter,Planner,Executor。和本项目相关的是第四个部分。

前期的工作主要对前台处理和后台处理的四个部分的总体流程有了一个大概的分析。对其涉及到的数据结构也做了简要的分析。但修改代码应该落实到具体的数据结构与模块函数，因此，现在本期的工作就话在一些重要的函数的执行详细流程和一些重要的数据结构的运行上。

其中，和本项目最相关的是后台执行的Executor部分，这部分的输入是已经重写后生成的查询计划树。当Postgresql在执行查询计划树上的查询计划时，从根到孩子式的递归调用执行，直到执行完一棵计划树。

下面着重对Executor涉及的一些重要的函数执行流程做一些更为细致的分析。