【Postgres】WITH子查询优化介绍（一）

    WITH子查询是一种常见的SQL编程技巧，利用它可以清晰地展示查询语句的“物理含义“信息，便于理解。但是，WITH子查询有一个不足的地方在于缺少统计信息，如果查询语句涉及join关联，可能会出现由于估算信息的偏差导致生成错误的执行计划。

测试数据

    生成测试表和数据如下

create table test1(a int);
create table test2(a int);

insert into test1 select generate_series(1,100000);
insert into test2 select generate_series(1,201);

analyze test1;
analyze test2;

    下面语句在PG11.5上获取的执行计划信息如下

postgres=# explain with t as (select * from test2) select * from test1 where a in (select * from t);
                             QUERY PLAN
---------------------------------------------------------------------
 Hash Join  (cost=12.03..2273.78 rows=50000 width=4)
   Hash Cond: (test1.a = t.a)
   CTE t
     ->  Seq Scan on test2  (cost=0.00..3.01 rows=201 width=4)
   ->  Seq Scan on test1  (cost=0.00..1443.00 rows=100000 width=4)
   ->  Hash  (cost=6.52..6.52 rows=200 width=4)
         ->  HashAggregate  (cost=4.52..6.52 rows=200 width=4)
               Group Key: t.a
               ->  CTE Scan on t  (cost=0.00..4.02 rows=201 width=4)
(9 rows)

postgres=# explain with t as (select * from test2 where a <= 200) select * from test1 where a in (select * from t);
                            QUERY PLAN
-------------------------------------------------------------------
 Hash Semi Join  (cost=10.01..1722.49 rows=200 width=4)
   Hash Cond: (test1.a = t.a)
   CTE t
     ->  Seq Scan on test2  (cost=0.00..3.51 rows=200 width=4)
           Filter: (a <= 200)
   ->  Seq Scan on test1  (cost=0.00..1443.00 rows=100000 width=4)
   ->  Hash  (cost=4.00..4.00 rows=200 width=4)
         ->  CTE Scan on t  (cost=0.00..4.00 rows=200 width=4)
(8 rows)

    从上面的执行计划可以看出，WITH子查询是单独计算的，并且经过聚合去重之后，得到的不重数个数都是200，即使第一个语句中子查询子句的查询结果包含有201条不重复记录，且优化器对第一条语句的估算返回结果是50000，对第二条语句的估算返回结果是200。

行数估计

    先简单介绍下，WITH子查询语句下的满足条件行的估计。由于WITH子查询是单独计算的，因此不存在实际的统计信息，在PostgreSQL中针对这一类情况按照下面情况计算其唯一值个数

/src/include/utils/selfuncs.h

/* default number of distinct values in a table */
#define DEFAULT_NUM_DISTINCT  200

     从上面可以看出优化器默认认为的不重复值个数是200，这个值是固定的，而不是通过分析采样获取的。

     返回行数的估计中，最重要的就是选择率的计算。从执行计划上看，这里采用的是hash semi join（由于采用有in子查询），因此选择率计算函数为  eqjoinsel_semi，由于构造的元组都是数字，因此最终采用下面的函数片段计算选择率

/*
 * Without MCV lists for both sides, we can only use the heuristic
 * about nd1 vs nd2.
 */
 double		nullfrac1 = stats1 ? stats1->stanullfrac : 0.0;
 // 是否采用默认值，在get_variable_numdistinct中指定，由于WITH没有任何统计信息，采用默认
 // 值，同时在该函数前面也会进行检查判断是否是默认采样值（主要依据是获取的结果是否大于等于实际
 // 值，这里实际值201,因此这里采用默认值，true
 if (!isdefault1 && !isdefault2)
 {
    if (nd1 <= nd2 || nd2 < 0)
        selec = 1.0 - nullfrac1;
    else
	selec = (nd2 / nd1) * (1.0 - nullfrac1);
  }
  else
  // 计算最终选择率，这里nullfrac是0，因此最终结果是0.5
      selec = 0.5 * (1.0 - nullfrac1);

    如果将查询语句修改后，计算选择率的函数进入上半部分，在该例中采用的是均匀分布估算方式，最终估算的结果没有偏差。这里的测试用例比较简单，主要是想说明估算误差的情况，如果遇到比较特殊的语句，采用WITH后，可能性能会发生变化，这一点需要注意。

改进

    在PostgreSQL12版本中，支持对子查询的内联处理，将对满足条件的查询语句直接进行下推处理，从而避免了中间一层的行数估计，避免了因为默认值导致的估算偏差，在最新版本执行计划如下：

postgres=# explain with t as (select * from test2) select * from test1 where a in (select * from t);
                            QUERY PLAN
-------------------------------------------------------------------
 Hash Semi Join  (cost=5.52..1713.26 rows=201 width=4)
   Hash Cond: (test1.a = test2.a)
   ->  Seq Scan on test1  (cost=0.00..1443.00 rows=100000 width=4)
   ->  Hash  (cost=3.01..3.01 rows=201 width=4)
         ->  Seq Scan on test2  (cost=0.00..3.01 rows=201 width=4)
(5 rows)

postgres=# explain with t as (select * from test2 where a <= 200) select * from test1 where a in (select * from t);
                            QUERY PLAN
-------------------------------------------------------------------
 Hash Semi Join  (cost=6.01..1713.74 rows=200 width=4)
   Hash Cond: (test1.a = test2.a)
   ->  Seq Scan on test1  (cost=0.00..1443.00 rows=100000 width=4)
   ->  Hash  (cost=3.51..3.51 rows=200 width=4)
         ->  Seq Scan on test2  (cost=0.00..3.51 rows=200 width=4)
               Filter: (a <= 200)
(6 rows)

    可以看到，执行计划中没有对WITH子查询的单独操作，而是转化为表TEST1和TEST2的之间关联操作。不是所有的WITH子查询在数据库内部都会进行改写，下面四种情况目前不支持

/*		
 * Consider inlining the CTE (creating RTE_SUBQUERY RTE(s)) instead of
 * implementing it as a separately-planned CTE.
 *
 * We cannot inline if any of these conditions hold:
 *
 * 1. The user said not to (the CTEMaterializeAlways option).
 *
 * 2. The CTE is recursive.
 *
 * 3. The CTE has side-effects; this includes either not being a plain
 * SELECT, or containing volatile functions.  Inlining might change
 * the side-effects, which would be bad.
 *
 * 4. The CTE is multiply-referenced and contains a self-reference to
 * a recursive CTE outside itself.  Inlining would result in multiple
 * recursive self-references, which we don't support.
 */

  if ((cte->ctematerialized == CTEMaterializeNever ||
 	 (cte->ctematerialized == CTEMaterializeDefault &&
 	  cte->cterefcount == 1)) &&
 	!cte->cterecursive &&
 	cmdType == CMD_SELECT &&
 	!contain_dml(cte->ctequery) &&
 	(cte->cterefcount <= 1 ||
 	 !contain_outer_selfref(cte->ctequery)) &&
 	!contain_volatile_functions(cte->ctequery))
 {
 	inline_cte(root, cte);
 	/* Make a dummy entry in cte_plan_ids */
 	root->cte_plan_ids = lappend_int(root->cte_plan_ids, -1);
 	continue;
 }

目前有几种情况的WITH子查询不支持内联处理，后面博客将详细介绍该优化patch详细内容。优化patch如下

Allow user control of CTE materialization, and change the default behavior