引言

  postgre是一个典型单机关系型数据库，它的理论完备，代码层次清晰。本报告从一条查询语句入手讲述postgre的逻辑计划优化和生成，进而到物理计划优化和生成。讲解的过程中穿插这个过程涉及的数据结构和算法。下面我们先从理论的角度宏观把控一下逻辑计划和物理计划。
  数据库要完成一系列的操作如增、删、改、查，必然要经过一系列的操作。当我们只需要操作单个表时其实并不复杂，更多的可能是从这个单表中获取某些数据即可，这个过程可能涉及到怎样查找这个数据的效率更高，当然这也依赖于存储层的设计。但是当我们的操作涉及多个表时，这个过程就变得异常复杂。比如我们现在有一个teacher表和一个 student表，如下图。

  假如我们现在要查询学号为3的这个同学的班主任的手机号是多少。我们可能需要先对学生表进行扫描找到学号为3的同学，进而找到他的班主任叫wang。然后我们拿着这个wang再去老师表中找到这个叫wang的老师，进而获得这个老师的手机号。在这个过程中我们涉及了两次单表的扫描操作，乍看好像这个过程也没什么，效率好像也很高嘛，而且学号是主键，可以利用索引快速找到学号为3的同学。事实真的如此吗？如果学生表是下面这样呢？

  如果这个时候我不用学号查而是用名字查呢？如果我要找的不是某个特定的学生，而是某个年龄的学生呢？这样会多出很多扫描操作，事实上这是一个双重的嵌套循环。在实际中关系型数据库的查询可能会涉及到多个表的操作，而受限于关系型数据库的表的形式，当我们需要查找一个表和另一个表相关联的数据时，就会出现这种很耗费时间的扫描，即遍历一个表依次拿数据再遍历另一个表对比数据。为了解决这个问题，join操作应运而生。我们通过某种算法，以两个表相关联的数据项作为纽带，将两个表关联起来。从形式上看，是从两个或者多个表中选出某些元组，再将它们合成一个表，完成列的扩展。目前的join算法有如嵌套循环join、基于排序的归并join和哈希join。
  上述我们引入了数据库一个非常重要的概念，即join。join的出现本身就是为了解决查询的效率问题，但是如何做join其实也是一个需要解决的问题。比如我们有一条查询语句涉及到多个表的join操作，先做哪两个表的join，后做哪个表的join都会影响查询效率。所以数据库优化最核心的部分实际就是这个join，这也是物理计划需要解决的核心问题。
  在数据库查询优化的早期，实际上并没有所谓的逻辑计划和物理计划的区分，整个是拉通的，因为核心是单表的扫描、多表的join顺序等等，那直接去考虑这些就好了呀，而这一部分的优化是要基于代价的，通俗来讲就是需要知道做join运算的表的规模以及join操作产生的新的“表”的规模。但是在数据库的逐步发展中，人们发现了有一部分的优化实际上和代价没有关系，这一部分完全不需要知道代价就可以进行优化，这是一种“肉眼可见”的优化操作。而这一部分的优化实际上和我们的数据库的使用者是密切相关的，因为这其中的大部分优化他们在使用数据库时就可以自己优化，实际上大部分逻辑计划的优化是在帮他们进行优化，让他们在写数据库查询语句时不用考虑过多，他们尽管写正确的查询语句，只要语法没有问题即可。所以这一部分的优化更多的是对查询语句进行调整！调整完了之后逻辑计划还是要服务于物理计划完成核心的join操作。