理解原理的重要性 - 论PostgreSQL merge join 成本评估陷阱 含case

postgresql支持三种join的方法，nestloop, merge, hash。

这三种join方法的差别和原理可以参考

<a href="https://www.postgresql.org/docs/devel/static/planner-optimizer.html">https://www.postgresql.org/docs/devel/static/planner-optimizer.html</a>

<a href="https://github.com/digoal/blog/blob/master/201205/20120521_02.md">《postgresql nestloop/hash/merge join讲解》</a>

nested loop join:

merge join:

hash join:

对于merge join，在估算成本时，如果join列有索引，那么会扫描索引，获取该列的最大值和最小值。

(注意，数据库的统计信息中并没有最大值和最小值)

那么问题来了，如果索引出现了剧烈倾斜（或者没有及时释放空页），那么在评估merge join的执行计划时，可能导致执行计划时间过长。

下面看一个例子。

创建两张测试表，关闭表级autovacuum，以免影响结果

往两张表分别插入1000万记录

检查mergejoin已打开

打开时间记录

查看执行计划，目前生成执行计划的耗时很正常

收集统计信息，生成表对应的vm, fsm文件。

再次生成执行计划，强制使用merge join，执行计划的时间依旧正常

当没有索引时，评估merge join的成本不需要获取最大值和最小值

创建tbl1的join字段id的索引

当前索引大小214 mb

删除tbl1表的前9999999条记录

重新生成执行计划，发现现在执行计划耗时变长了很多很多

再一次生成执行计划，耗时还是不正常，但是略有好转，可能因为索引页的数据已经在内存中了。

执行计划的时间与通过索引查询join列的最大最小值的时间基本一致

没有评估到merge join的时候，执行计划是正常的

将优化器的enable_mergejoin关闭，执行计划的耗时恢复正常，所以问题的根源是merge join执行计划本身的问题，后面会有更细致的分析

目前索引大小依旧是214 mb

使用pageinspect插件，检查一下当前索引

首先，从metapage，查到索引的root page id

查询root page有多少条目，可以看到虽然数据都删了，但是索引还没有清理，这些条目依旧存在索引页中。

这也是为什么使用这个索引查找min, max会很慢的原因，因为它不知道这些数据已经被删除了，必须通过索引条目访问到heap page对应的tuple后，才知道。

查找root page索引条目的明细

接下来使用vacuum tbl1 回收垃圾页，这个动作同样会回收tbl1的索引垃圾页，对于全部dead的索引也，会置为empty page。

现在，使用索引又很快了

那么现在merge join执行计划的耗时恢复正常了吗？

恢复了

虽然现在索引大小没有变化，但是实际上没有引用的index page都置为empty page了

具体详见btree的readme

src/backend/access/nbtree/readme

观察vacuum后索引页的变化

首先获取metapage的信息，得到root page id，注意索引的层次并没有变化，依旧是2层，也就是说有第一层是branch节点，第二层是leaf节点。

读取root page的信息，显然现在root page只有一个条目，即一级branch的某个page

查看第一级，branch的信息，找到第二级，leaf节点。

查看第二级，leaf节点的信息

leaf节点，对应的是heap table的行号，所以通过行号，可以直接访问数据

从以上分析可以得到一个结论

在数据库中执行多表join时，如果没有设置enable_mergejoin=off，那么数据库可能会选择merge join，或者说数据库需要评估merge join的成本。

当join列有索引存在，为了算出更精确的cost值，评估merge join的成本会用到该列的min, max值（通过扫描join列的索引得到）。

不管任何原因，扫描索引得到min,max 比较慢的话，执行计划的时间都会被拉长。

某个业务，每天会从几千万数据中清除几十万，然后就发现某些join的sql执行计划时间变得好长（虽然最后选择的是nest loop join，但是评估过程依旧需要评估merge join的成本）。

如何发现的？

1. 使用perf

2. 使用gdb, 或者打印进程的 pstack

某个场景得到的bt

当系统关闭了autovacuum后，如果批量删除或更新数据，可能会导致索引出现大量引用dead tuple的页面，从而评估与这些列有关的join可能时间会变长（指merge join）

1. 当使用了绑定变量时，可能能解决以上问题，但是也可能无法解决以上问题，因为postgresql绑定变量有一个避免执行计划倾斜的算法，会记录custom plan的次数和平均成本，根据plan cache和传入的参数，调用choose custom plan，评估generic plan的成本，和custem plan平均成本进行比较，以此判断是否需要custom plan.

如果需要custom plan，那么会重新评估各种执行计划的成本。生成一次custom plan。

原理详见本文末尾的几篇参考文档。

2. autovacuum设置的阈值太大（autovacuum_vacuum_scale_factor=0.2），默认是20%，也就是说只有数据发送了20%变化后，才会自动清理。

如何避免呢？

1. 不要关闭表的autovacuum。

2. 对于大表，可以设置表级autovacuum 阈值，比如1%，或者更小一点。

create table 或者 alter table都可以，语法详见postgresql手册。

3. 开启系统级autovacuum, 并设置合理的autovacuum_vacuum_scale_factor，不要太大。

4. 在大量删除数据或者更新数据后，人为的对这些表执行vacuum analyze table;, 避免以上问题。

当join列有索引存在，并且优化器允许merge join时，评估merge join的成本时需要用到该列的min,max值，min,max值通过索引获得。

当join列都没有索引存在时，评估merge join的成本，不需要min,max值。因此评估merge join的执行计划很快。

从索引获取min,max值，直接影响了产生执行计划的耗时。

当数据被批量删除后，如果没有触发vacuum垃圾回收，评估merge join的成本就可能比较耗时，也就是本文提到的case。

执行vacuum后，index的垃圾也会被清理，优化器评估merge join成本时用到的min,max值可以很快获得。

<a href="https://github.com/digoal/blog/blob/master/201606/20160617_02.md">《为什么用 postgresql 绑定变量 没有 oracle pin s 等待问题》</a>

<a href="https://github.com/digoal/blog/blob/master/201606/20160617_01.md">《postgresql plan cache 源码浅析 - 如何确保不会计划倾斜》</a>

<a href="https://github.com/digoal/blog/blob/master/201212/20121224_01.md">《执行计划选择算法 与 绑定变量 - postgresql prepared statement: spi_prepare, prepare|execute command, pl/pgsql style: custom &amp; generic plan cache》</a>