表扫描方式

表扫描方式主要包含顺序扫描、索引扫描以及Tid扫描等方式，不同的扫描方式

  • Seq scan，顺序扫描物理数据页
  • Index scan，先通过索引值获得物理数据的位置，再到物理页读取
  2.                              QUERY PLAN
  3. --------------------------------------------------------------------
  4.  Index Scan using t1_a1_key on t1  (cost=0.28..8.29 rows=1 width=8)
  5.    Index Cond: (a1 = 10)
  • Tid scan，通过page号和item号直接定位到物理数据
  1. postgres=> explain select * from t1 where ctid='(1,10)';
  2.                     QUERY PLAN
  3. --------------------------------------------------
  4.  Tid Scan on t1  (cost=0.00..4.01 rows=1 width=8)
  5.    TID Cond: (ctid = '(1,10)'::tid)

选择度计算

  • 全表扫描选择度计算

全表扫描时每条记录都会返回，所以选择度为1，所以rows=10000

  1. EXPLAIN SELECT * FROM tenk1;
  3.                          QUERY PLAN
  4. -------------------------------------------------------------
  5.  Seq Scan on tenk1  (cost=0.00..458.00 rows=10000 width=244)
  9.  relpages | reltuples
  11.       358 |     10000
  • 整型大于或者小于选择度计算
  • 字符串等值选择度计算
  1. EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'CRAAAA';
  3.                         QUERY PLAN
  4. ----------------------------------------------------------
  5.  Seq Scan on tenk1  (cost=0.00..483.00 rows=30 width=244)
  6.    Filter: (stringu1 = 'CRAAAA'::name)
  7. SELECT null_frac, n_distinct, most_common_vals, most_common_freqs FROM pg_stats
  8. WHERE tablename='tenk1' AND attname='stringu1';
  9. null_frac         | 0
  10. n_distinct        | 676
  11. most_common_vals|{EJAAAA,BBAAAA,CRAAAA,FCAAAA,FEAAAA,GSAAAA,JOAAAA,MCAAAA,NAAAAA,WGAAAA}
  12. most_common_freqs | {0.00333333,0.003,0.003,0.003,0.003,0.003,0.003,0.003,0.003,0.003}
  13. selectivity = mcf[3]
  14.             = 0.003
  15. rows = 10000 * 0.003
  16.      = 30

备注：如果值不在most_common_vals里面，计算公式为：

  1. selectivity = (1 - sum(mvf))/(num_distinct - num_mcv)
  • cost计算

代价模型:总代价=CPU代价+IO代价+启动代价

  2. -----------------------------------------------------
  3.  Seq Scan on t1  (cost=0.00..16.90 rows=942 width=8)
  4.    Filter: (a1 > 10)
  5. (2 rows)
  6. 其中：
  7. postgres=> select relpages, reltuples from pg_class where relname = 't1';
  8.  relpages | reltuples
  9. ----------+-----------
  10.         5 |       952
  11. (1 row)
  12. cpu_operator_cost=0.0025
  13. cpu_tuple_cost=0.01
  14. seq_page_cost=1
  15. random_page_cost=4

总cost = cpu_tuple_cost * 952 + seq_page_cost * 5 + cpu_operator_cost * 952 = 16.90 其他扫描方式cost计算可以参考如下函数：

表组合方式

  • Nest Loop

  1. SELECT  * FROM     t1 L, t2 R WHERE  L.id=R.id

M = 20000 pages in L, pL = 40 rows per page, N = 400 pages in R, pR = 20 rows per page.

  1. select relpages, reltuples from pg_class where relname=‘t1’

L和R进行join

  1. for l in L do
  2.   for r in R do
  3.     if rid == lid  then ret += (r, s)

对于外表L每一个元组扫描内表R所有的元组 总IO代价: M + (pL * M) * N = 20000 + (4020000)400
\= 320020000

  • MergeJoin

screenshot.png

主要分为3步:

(1) Sort L on lid 代价MlogM

(3) Merge the sorted L and R on lid and rid 代价M+N

  • HashJoin

使用HashJoin的前提是其中假设一个表可以完全放在内存中，实际过程中可能统计信息有偏差，优化器认为一个表可以放到内存中，事实上数据在内存中放不下，需要使用临时文件，这样会降低性能。

表的组合顺序

不同的组合顺序将会产生不同的代价，想要获得最佳的组合顺序，如果枚举所有组合顺序，那么将会有N!的排列组合，计算量对于优化器来说难以承受。PG优化器使用两种算法计算更优的组合顺序，动态规划和遗传算法。对于连接比较少的情况使用动态规划，否则使用遗传算法。

  • 动态规划求解过程

PG优化器主要考虑将执行计划树生成以下三种形式:

screenshot.png