数据库优化器原理 - 如何治疗选择综合症

PostgreSQL , 单列索引 , 复合索引 , 优化器 , 成本因子

---

经常听到这样的声音：“查询慢？加个索引吧。”，虽然话不专业，但是体现了早期基于RBO（基于规则）的优化器思维。

通常对业务不熟悉，或者对数据库不熟悉时，可能会凭自觉做出这样的判断。

RBO思维存在较大的问题，所以导致了CBO（基于成本）的出现。

再往后，(生成执行计划->执行这样的)静态CBO又要落伍了，紧接着会是动态的执行计划(边执行->边生成下一阶段的执行计划)。

动态执行计划好似导航软件的躲避拥堵功能，阶段性的给出最佳的线路。

PostgreSQL pro动态执行计划roadmap

https://postgrespro.com/roadmap/

https://postgrespro.com/roadmap/56513

我们回到CBO，既然是基于成本的优化，那么成本是如何算出来的呢？

数据库收到用户的SQL请求后，会经过parser, rewrite, 产生paths, 产生最优plan, execute plan, 返回结果。

• 源码参考

• https://www.postgresql.org/developer/backend/

产生paths的功能类似下图：达到目的有多少种方法；或者去往某个目的地，有多少种走法；又或者解题有多少种解法。

产生最优plan，(从多个解法中，选择成本最低的path)，生成plan。

我们看上面那张图，每一个node(小圆圈)是一次运算，运算完将数据输送给上层的node，到达顶端时计算结束返回结果给用户。

每个path的成本，取决于该path每个node的成本总和。

接下来引出今日话题，当优化器可以选择不同的索引解决同一个SQL的问题时，该选哪个呢？

例子

接下来，看完本文，不仅仅可以解答今日问题，其他优化器相关的问题也迎刃而解。

前面说了，CBO是基于成本的优化，当一条SQL可以使用多个索引，或者可以选择多种访问路径时，该如何选择呢？

这是优化器经常需要面对的问题。特别是PostgreSQL支持的访问方法很多，选择更多。

• 有哪些node可以参考 src/backend/commands/explain.c

手册中有详细的成本计算方法的例子

Chapter 67. How the Planner Uses Statistics

https://www.postgresql.org/docs/9.6/static/planner-stats-details.html

拆解后，node成本的计算实际上依赖几个东西：

1. 成本因子，详见

https://www.postgresql.org/docs/9.6/static/runtime-config-query.html#RUNTIME-CONFIG-QUERY-CONSTANTS

2. 统计信息（记录数、PAGE数、列统计信息、线性相关性、高频值、高频值的比例等），详见

pg_stats统计视图。

3. 算法。每种NODE的算法都不一样，详见

src/backend/optimizer/path/costsize.c

通过改变统计信息、成本因子、算法，可以改变NODE的成本计算结果。

1. 统计信息通过analyze收集，PostgreSQL支持列级设置柱状图bucket大小。默认是100，最大可以设置到10000。

bucket越大，统计信息越准确，但是统计耗时越长。

修改统计信息，会直接影响NODE的成本计算结果。

2. 修改成本因子，可以直接影响NODE的成本计算结果。

例如全表扫描NODE，修改seq_page_cost会影响全表扫描NODE单个PAGE的扫描成本。

3. 修改算法，也会导致成本计算结果的变化，需要动到PostgreSQL内核costsize.c，或者使用PostgreSQL内核提供的HOOK修改成本的计算结果。

有三种方法，可以让优化器最终选哪个path生成plan。

1 修改成本因子

改成本因子，实际上是改node成本的计算结果。从而让优化器改变最终的选择。

要生成准确的成本，需要三个因素都准确，1. 成本因子，2. 统计信息，3. 算法。

其中成本因子的校准，可以参考如下文章

《优化器成本因子校对 - PostgreSQL explain cost constants alignment to timestamp》

通过修改成本因子，可以达到修正对应NODE成本的目的。

例子，用成本因子治疗文章开头的例子

测试表

测试SQL1

如果要让以上SQL使用IDX2(使用IDX2)，我们只需要调大cpu_tuple_cost的开销即可(因为这部分开销是IDX1产生的，而IDX2不会产生这部分开销)。

在设大cpu_tuple_cost之前，为什么数据库选择了IDX1呢，到底什么导致了IDX2的成本高于IDX1了？

我们看到IDX2比IDX1略大（PAGE数更多），所以离散扫描的成本算进来，导致总成本比IDX2更低了。

例子

2 修改开关

通过开关，可以让优化器避免选择某些路径，这些路径不会被生成，也不会计算成本，最终也不会被选择。

PostgreSQL支持的开关如下

https://www.postgresql.org/docs/9.6/static/runtime-config-query.html#RUNTIME-CONFIG-QUERY-ENABLE

控制是否提升子查询

控制显示的JOIN（FULL JOIN除外）是否使用用户提供的JOIN顺序。

其他开关

通过设置这些开关，可以让优化器使用或者不使用某些path，从而控制最终的执行计划。

例如把所有的索引扫描，BITMAP SCAN都关掉，会变成全表扫描。

3 hint

通过hint插件（实际上就是HOOK做的），可以强制优化器使用你设定的路径。

比如告诉优化器，请使用HASH JOIN，或者使用某个索引。

HINT的使用例子如下

《关键时刻HINT出彩 - PG优化器的参数优化、执行计划固化CASE》

《PostgreSQL 特性分析 Plan Hint》

《阿里云 PostgreSQL pg_hint_plan插件的用法》

《PostgreSQL SQL HINT的使用(pg_hint_plan)》

默认情况下，数据库多表JOIN时，会使用穷举法，将所有的JOIN顺序排列出来，生成非常多的path。JOIN的表越多，path就越多，导致执行计划花费较多的时间。

如果想避免穷举法带来多表JOIN执行计划花费过多，

一种方法是使用前面提到的显示JOIN以及设置join_collapse_limit，from_collapse_limit=1。

另一种方法是使用遗传算法，当FROM中的JOIN对象大于阈值，将使用遗传算法。

遗传算法请参考

https://www.postgresql.org/docs/9.6/static/runtime-config-query.html#GUC-GEQO-THRESHOLD

1. 10.0对优化器有一些改造，比如自定义统计维度，比如JOIN循环的优化。

《PostgreSQL 10.0 preview 功能增强 - 自由定义统计信息维度》

https://www.postgresql.org/docs/devel/static/sql-createstatistics.html

自定义列统计信息例子

2. 《PostgreSQL 10.0 preview 性能增强 - hash,nestloop join优化(聪明的优化器是这样的)》

3. 更多详见10.0的release note

https://www.postgresql.org/docs/devel/static/release-10.html

E.1.3.1.4. Optimizer

• Add multi-column optimizer statistics to compute the correlation ratio and number of distinct values (Tomas Vondra, David Rowley, álvaro Herrera)

New commands are CREATE, ALTER, and DROP STATISTICS. This is helpful in estimating query memory usage and when combining the statistics from individual columns.

• Improve planner matching of boolean indexes (Tom Lane)

• Improve performance of queries referencing row-level security restrictions (Tom Lane)

• The optimizer now has more flexibility in reordering executor behavior.

《索引顺序扫描引发的堆扫描IO放大背后的统计学原理与解决办法》

《优化器成本因子校对 - PostgreSQL explain cost constants alignment to timestamp》

《PostgreSQL 嵌套循环成本估算方法 - nestloop loop cost & cost_material run_cost》