一条SQL在PG中的执行过程是：

  1. ----> SQL输入
  2. ----> 解析SQL，获取解析后的语法树
  3. ----> 分析、重写语法树，获取查询树
  4. ----> 根据重写、分析后的查询树计算各路径代价，从而选择一条成本最优的执行树
  5. ----> 根据执行树进行执行
  6. ----> 获取结果并返回

PostgreSQL的SQL优化、执行方式为代价模型。而这里的各路径的代价计算，则是依赖于系统表中的统计信息。那么这些统计信息如何得来的？就是这里要讨论的问题。

PostgreSQL是catalog-driven型的数据库，引擎运行过程中所有所需的数据、信息都存放在系统表中，统计信息不例外。这些统计信息，则是通过SQL命令vacuum和analyze分别写入pg_class和pg_statistic中的。

参考官方文档ANALYZE

pg_class && pg_statistic

pg_class的表结构如下：

  1. => \d pg_class
  2.       Table "pg_catalog.pg_class"
  3.      Column     |   Type    | Modifiers
  4. ----------------+-----------+-----------
  5.  relname        | name      | not null
  6.  ...
  7.  relpages       | integer   | not null
  8.  reltuples      | real      | not null
  9.  ...
  10.  relkind        | "char"    | not null
  11.  relnatts       | smallint  | not null
  12.  ...
  13. Indexes:
  14.     "pg_class_oid_index" UNIQUE, btree (oid)
  15.     "pg_class_relname_nsp_index" UNIQUE, btree (relname, relnamespace)
  16.     "pg_class_tblspc_relfilenode_index" btree (reltablespace, relfilenode)

这里比较关注的是relpages和reltuples两个字段，分别表示这张表占了多少磁盘页和行数。其中行数是估计值。而这两个字段的值是通过vacuum、analyze（或create index)来更新的。

参考官方文档pg_class

pg_statistic的表结构如下：

  1. => \d pg_statistic
  2.   Table "pg_catalog.pg_statistic"
  3.    Column    |   Type   | Modifiers
  4. -------------+----------+-----------
  5.  starelid    | oid      | not null
  6.  staattnum   | smallint | not null
  7.  stainherit  | boolean  | not null
  8.  stanullfrac | real     | not null
  9.  stawidth    | integer  | not null
  10.  stadistinct | real     | not null
  11.  stakind1    | smallint | not null
  12.  stakind2    | smallint | not null
  13.  stakind3    | smallint | not null
  14.  stakind4    | smallint | not null
  15.  stakind5    | smallint | not null
  16.  staop1      | oid      | not null
  17.  staop2      | oid      | not null
  18.  staop3      | oid      | not null
  19.  staop4      | oid      | not null
  20.  staop5      | oid      | not null
  21.  stanumbers1 | real[]   |
  22.  stanumbers2 | real[]   |
  23.  stanumbers3 | real[]   |
  24.  stanumbers4 | real[]   |
  25.  stanumbers5 | real[]   |
  26.  stavalues1  | anyarray |
  27.  stavalues2  | anyarray |
  28.  stavalues3  | anyarray |
  29.  stavalues4  | anyarray |
  30.  stavalues5  | anyarray |
  31. Indexes:
  32.     "pg_statistic_relid_att_inh_index" UNIQUE, btree (starelid, staattnum, stainherit)

这里的stanullfrac、stadistinct、stakindN、staopN、stanumbersN、stavaluesN等是我们所关注的值。其中：

  • stakindN

    用于表示后面number、values所表示的数据用途，被用于生成pg_stats。如1则表示是MCV的值；2表示直方图（histogram）的值；3表示相关性（correlation）的值等。kind的取值范围：1~99，內核占用；100~199，PostGIS占用；200~299，ESRI ST_Geometry几何系统占用；300~9999，公共占用。

  • staopN

    用于表示该统计值支持的操作，如’=’或’<’等。

  • stanumbersN

    如果是MCV类型（即kind=1），那么这里即是下面对应的stavaluesN出现的概率值，即MCF。

  • stavaluesN

    anyarray类型的数据，內核特殊类型，不可更改。是统计信息的值部分，与kind对应。如kind=2的时候，则这里的值表示直方图。

    这些值的更新都是通过analyze完成，N的取值是[1, 5]，由PG內核决定的。将来有可能更多。

参考官方文档pg_statistic

执行方式

vacuum和analyze的执行可以通过两种方式来触发，一种是DB用户执行，如定时脚本或人工执行；一种是autovacuum。两个操作持有相同类型的锁ShareUpdateExclusiveLock，与DDL互斥。

autovacuum是PostgreSQL提供的一个deamon进程，会在一定时间內或者DML多到一定程度时触发vacuum或analyze。这里的一定时间和一定程度可以通过autovacuum的一系列配置实现，如autovacuum_naptime、autovacuum_max_workers 、autovacuum_vacuum_threshold等；且vacuum和analyze的触发算法和依赖参数并不尽相同。

注：请参考 autovacuum_vacuum_threshold 和 The Autovacuum Daemon

analyze

vacuum本身除了负责更新relpages和reltuples等之外，最主要的是：

  1. 回收被更新和删除占用的空间
  2. 回收事务id，冻结老的事务id，以防止这部分老数据丢失

而analyze则主要是收集统计信息，并存储到pg_statistic表中。其主要的步骤如下：

  • 以共享排他锁（ShareUpdateExclusiveLock）打开表

    这个锁会与DDL之上所有的操作互斥，详细的互斥关系如下，其值越大锁粒度越大：

  1. /*
  2.  * These are the valid values of type LOCKMODE for all the standard lock
  3.  * methods (both DEFAULT and USER).
  4.  */
  6. /* NoLock is not a lock mode, but a flag value meaning "don't get a lock" */
  7. #define NoLock                    0
  9. #define AccessShareLock            1        /* SELECT */
  10. #define RowShareLock            2        /* SELECT FOR UPDATE/FOR SHARE */
  11. #define RowExclusiveLock        3        /* INSERT, UPDATE, DELETE */
  12. #define ShareUpdateExclusiveLock 4        /* VACUUM (non-FULL),ANALYZE, CREATE
  13.                                          * INDEX CONCURRENTLY */
  14. #define ShareLock                5        /* CREATE INDEX (WITHOUT CONCURRENTLY) */
  15. #define ShareRowExclusiveLock    6        /* like EXCLUSIVE MODE, but allows ROW
  16.                                          * SHARE */
  17. #define ExclusiveLock            7        /* blocks ROW SHARE/SELECT...FOR
  18.                                          * UPDATE */
  19. #define AccessExclusiveLock        8        /* ALTER TABLE, DROP TABLE, VACUUM
  20.                                          * FULL, and unqualified LOCK TABLE */

  • 选择采样函数

    如果是普通表或者物化视图，则采样函数采用acquire_sample_rows；如果是外表，那么外表所用的插件需要FDW的实现，如postgres_fdw的postgresAnalyzeForeignTable。

  • 检查表的每个字段

    在真正开始分析之前，先检查每个字段，并返回VacAttrStats结构体。后面所有的分析都将在此检查之上进行。

    VacAttrStats结构体如下：

  1. typedef struct VacAttrStats
  2. {
  3.     /*
  4.      * These fields are set up by the main ANALYZE code before invoking the
  5.      * type-specific typanalyze function.
  6.      *
  7.      * Note: do not assume that the data being analyzed has the same datatype
  8.      * shown in attr, ie do not trust attr->atttypid, attlen, etc.  This is
  9.      * because some index opclasses store a different type than the underlying
  10.      * column/expression.  Instead use attrtypid, attrtypmod, and attrtype for
  11.      * information about the datatype being fed to the typanalyze function.
  12.      */
  13.     Form_pg_attribute attr;        /* copy of pg_attribute row for column */
  14.     Oid            attrtypid;        /* type of data being analyzed */
  15.     int32        attrtypmod;        /* typmod of data being analyzed */
  16.     Form_pg_type attrtype;        /* copy of pg_type row for attrtypid */
  17.     MemoryContext anl_context;    /* where to save long-lived data */
  19.     /*
  20.      * These fields must be filled in by the typanalyze routine, unless it
  21.      * returns FALSE.
  22.      */
  23.     AnalyzeAttrComputeStatsFunc compute_stats;    /* function pointer */
  24.     int            minrows;        /* Minimum # of rows wanted for stats */
  25.     void       *extra_data;        /* for extra type-specific data */
  27.     /*
  28.      * These fields are to be filled in by the compute_stats routine. (They
  29.      * are initialized to zero when the struct is created.)
  30.      */
  31.     bool        stats_valid;
  32.     float4        stanullfrac;    /* fraction of entries that are NULL */
  33.     int32        stawidth;        /* average width of column values */
  34.     float4        stadistinct;    /* # distinct values */
  35.     int16        stakind[STATISTIC_NUM_SLOTS];
  36.     Oid            staop[STATISTIC_NUM_SLOTS];
  37.     int            numnumbers[STATISTIC_NUM_SLOTS];
  38.     float4       *stanumbers[STATISTIC_NUM_SLOTS];
  39.     int            numvalues[STATISTIC_NUM_SLOTS];
  40.     Datum       *stavalues[STATISTIC_NUM_SLOTS];
  42.     /*
  43.      * These fields describe the stavalues[n] element types. They will be
  44.      * initialized to match attrtypid, but a custom typanalyze function might
  45.      * want to store an array of something other than the analyzed column's
  46.      * elements. It should then overwrite these fields.
  47.      */
  48.     Oid            statypid[STATISTIC_NUM_SLOTS];
  49.     int16        statyplen[STATISTIC_NUM_SLOTS];
  50.     bool        statypbyval[STATISTIC_NUM_SLOTS];
  51.     char        statypalign[STATISTIC_NUM_SLOTS];
  53.     /*
  54.      * These fields are private to the main ANALYZE code and should not be
  55.      * looked at by type-specific functions.
  56.      */
  57.     int            tupattnum;        /* attribute number within tuples */
  58.     HeapTuple  *rows;            /* access info for std fetch function */
  59.     TupleDesc    tupDesc;
  60.     Datum       *exprvals;        /* access info for index fetch function */
  61.     bool       *exprnulls;
  62.     int            rowstride;
  63. } VacAttrStats;

具体的针对字段检查的步骤如下：

  • 确定这个字段是否可以分析，如果不可以，则返回NULL。 一般有两种情况致使这个字段不进行分析：字段已被删除（已删除的字段还存在于系统表中，只是作了标记）；用户指定了字段。

  • 获取数据类型，并决定针对该类型的采样数据量和统计函数 不同的类型，其分析函数也不同，比如array_typanalyze。如果该类型没有对应的分析函数，则采用标准的分析函数std_typanalyze。 以标准分析函数为例，其确定了两个地方：采样后用于统计的函数（compute_scalar_stats或compute_minimal_stats，和采样的记录数（现在默认是300 * 100）。

  • 索引 索引在PG中，是以与表类似的方式存在的。当analyze没有指定字段，或者是继承表的时候，也会对索引进行统计信息的计算。以AccessShareLock打开该表上所有的锁，同样的检查索引的每个字段是否需要统计、如何统计等。

  • 采样 选择表所有字段所需采样数据量的最大值作为最终采样的数据量。当前PG采取的两阶段采样的算法：

    • 先获取所需数据量的文件块
    • 遍历这些块，根据Vitter算法，选择出所需数据量的记录时以页为单位，尽量读取该页中所有的完整记录，以减少IO；按照物理存储的位置排序，后续会用于计算相关性（correlation）。

    这里的采样并不会处理事务中的记录，如正在插入或删除的记录。但如果删除或插入操作是在当前analyze所在的事务执行的，那么插入的是被记为live_tuples并且加入统计的；删除的会被记为dead_tuples而不加入统计。

    由此会可能产生两个问题：

    • 当有另外一个连接正好也在进行统计的时候，自然会产生不同的统计值，且后来者会直接覆盖前者。当统计期间有较多的事务在执行，且很快结束，那么结果与实际情况可能有点差别。
    • 当有超长的事务出现，当事务结束时，统计信息与实际情况可能有较大的差距。

    以上两种情况，重复执行analyze即可。但有可能因统计信息不准确导致的执行计划异常而造成短时间的性能波动，需要注意！这里也说明了长事务的部分危害。

  • 统计、计算 在获取到相应样本数据后，针对每个字段分别进行分析。 首先会依据当前字段的值，对记录进行排序。因在取出样本数据的时候，按照tuple在磁盘中的位置顺序取出的，因此对值进行排序后即可计算得出相关性。另外，在排序后，也更容易计算统计值的频率，从而得出MCV和MCF。这里采用的快速排序！ 之后，会根据每个值进行分析：

    • 如果是NULL，则计数 NULL概率的计算公式是：stanullfrac = null_number / sample_row_number。

    • 如果是变长字段，如text等，则需要计算平均宽度

    • 计算出现最多的值，和相应频率

    • 基数的计算 该部分计算稍微复杂一些，分为以下三种情况：

      1. 当采样中的值没有重复的时候，则认为所有的值唯一，stadistinct = -1。
      2. 当采样中的每个值都出现重复的时候，则认为基数有限，则stadistinct = distinct_value_number

      3. 当采样中的值中，存在有唯一值并且存在不唯一值的时候，则依据以下的公式（by Haas and Stokes in IBM Research Report RJ 10025）：

        1.  n * d / (n - f1 + f1 * n/N)

      其中，N是指所有的记录数，即pg_class.reltuples；n是指sample_row_number，即采样的记录数；f1则是只出现一次的值的数据；d则是采样中所有的值的数量。

    • MCV / MCF 并不是所有采样的值都会被列入MCV/MCF。首先是如果可以，则将所有采样的记录放到MCV中，如表所有的记录都已经取作采样的时候；其次，则是选取那些出现频率超过平均值的值，事实上是超过平均值的25%；那些出现频率大于直方图的个数的倒数的时候等。

    • 直方图 计算直方图，会首先排除掉MCV中的值。 意思是直方图中的数据不包含MCV/MCF的部分，两者的值是补充关系而且不会重合，但不一定互补（两种加起来未必是全部数据）。这个也与成本的计算方式有关系，请参考row-estimation-examples 。 其计算公式相对比较简单，如下：

      values[(i * (nvals - 1)) / (num_hist - 1)]

      i指直方图中的第几列；nvals指当前还有多少个值；num_hist则指直方图中还有多少列。计算完成后，kind的值会被置为2。 到此，采样的统计基本结束。

完成采样的计算后，通过內部函数更新相关的统计信息到pg_statistic，更新relpages和totale rows到pg_class中。即完成了一次统计信息的收集。

原文：http://mysql.taobao.org/monthly/2016/05/09/