优化器里的概率学 - 性能抖动原理分析
背景
数据库的优化器大量的使用了概率学的知识，例如高频词的频率，数据分布柱状图，评估某个VALUE有多少行，评估物理存储与列的线性相关性等等。
PostgreSQL 里面的统计学知识：
《用PostgreSQL了解一些统计学术语以及计算方法和表示方法 - 1》
《PostgreSQL数据库监控中的统计学 - 对象SIZE的数据分布图》
《PostgreSQL 统计信息之 - 逻辑与物理存储的线性相关性》
本文提到的CASE也和统计学有关，用户同样的SQL，更换条件后查询的响应时间差别比较大。
我们来分析一下问题出在哪里？
例子
tbl这张表，有两个相关字段，xxx, val。xxx, val都包含一个btree索引。
create table tbl (xxx int, val int);
create index idx_tbl_xxx on tbl using btree (xxx);
create index idx_tbl_val on tbl using btree (val);
tbl约9.1千万记录。(来自统计信息)
postgres=# select * from pg_class where relname = 'tbl';
-[ RECORD 1 ]--+---------------------------------------------------------------------------
...
relpages | 8257667
reltuples | 9.18266e+07
...
val字段的统计信息，柱状分布
postgres=# select * from pg_stats where tablename = 'tbl' and (attname = 'val');
-[ RECORD 1 ]----------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
schemaname | public
tablename | tbl
attname | val
inherited | f
null_frac | 0
avg_width | 4
n_distinct | 23472
most_common_vals | {11321542,9590084,9534670,11472095,9576467,9545491,11477451,10989530,11207289,11366499,11478550,11507267,10147621,10915696,11265877,11397691,10943926,11299197,11375631,11382656,11383293,11397909,11433126,11440696,11455808,11502873,9309452,9419251,9831208,10915491,10954298,10968050,10971601,10971856,11350206,11365070,11418452,11424692,11453932,11455400,11456117,11462578,11477841,11495983,11499188,11519466,11526843,11538523,9309313,9507528,9570697,9589957,9848424,10211296,10403265,10740134,10851181,10905772,10925615,10942712,10988994,10991227,10997731,10999386,11365698,11370643,11401522,11415268,11418400,11420980,11431494,11432202,11432813,11440231,11450771,11452106,11474915,11475542,11501297,11505822,11507072,11512290,11541832,9516436,9571509,9572190,9576510,9869955,9870066,10760447,10760491,10890296,10898933,10902740,10905208,10907293,10916731,10917591,10927390,10933657}
most_common_freqs | {0.000633333,0.000566667,0.000533333,0.000533333,0.000466667,0.000433333,0.000433333,0.0004,0.0004,0.0004,0.0004,0.0004,0.000366667,0.000366667,0.000366667,0.000366667,0.000333333,0.000333333,0.000333333,0.000333333,0.000333333,0.000333333,0.000333333,0.000333333,0.000333333,0.000333333,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.0003,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000266667,0.000233333,0.000233333,0.000233333,0.000233333,0.000233333,0.000233333,0.000233333,0.000233333,0.000233333,0.000233333,0.000233333,0.000233333,0.000233333,0.000233333,0.000233333,0.000233333,0.000233333}
histogram_bounds | {-1,7558107,7828127,8112859,9046149,9241826,9379468,9541732,9576599,9672961,9846871,9860375,9870728,10060192,10351217,10740412,10856432,10893866,10902117,10906515,10913106,10918910,10925204,10931076,10938203,10944727,10950843,10958976,10963704,10969886,10972265,10975634,10980061,10985045,10988826,10993407,10997844,10999535,11000963,11087834,11109438,11118360,11127807,11282790,11299113,11321740,11341584,11355644,11359298,11363485,11365828,11367262,11371057,11372356,11376100,11382254,11383472,11387734,11398387,11403238,11414003,11419357,11420978,11421807,11424546,11428043,11430424,11434838,11438052,11440476,11442560,11450686,11453180,11455088,11455714,11461724,11472384,11473771,11474364,11474986,11476815,11480406,11483760,11486407,11489680,11492521,11497577,11503852,11507380,11509618,11512309,11515497,11518366,11522532,11525500,11526789,11529964,11534552,11540765,11544743,11559885}
correlation | 0.523764
most_common_elems |
most_common_elem_freqs |
elem_count_histogram |
一条响应时间会抖动的SQL如下（更改val的值，某些值会导致抖动）。
postgres=# explain SELECT min(xxx) from tbl where val=11546671;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
Result (cost=4164.53..4164.54 rows=1 width=0)
InitPlan 1 (returns $0)
-> Limit (cost=0.57..4164.53 rows=1 width=8)
-> Index Scan using idx_tbl_xxx_1 on tbl (cost=0.57..15860545.10 rows=3809 width=8)
Index Cond: (xxx IS NOT NULL)
Filter: (val = 11546671)
(6 rows)
诊断
1、15860545.10是如何评估得到的？
index scan的成本取决于索引的BLOCK的数量乘以random_page_cost再加上记录数乘以cpu_index_tuple_cost，乘以输入参数的估值比例。
(pg_class.relpages*random_page_cost + pg_class.reltuples*cpu_index_tuple_cost) * (3809/(9.18266e+07))
2、rows=3809 是如何评估得到的？
首先val=11546671，这个值不在val的高频词(most_common_vals)里面，因此多少行可能出现一次呢？
= (reltuples * (1-sum(most_common_freqs))) / (n_distinct-100) = ((9.18266e+07) * (1-0.0303)) / (23472-100)
= 3809.8688182440527126
3、cost=4164.53..4164.54是如何评估出来的？
由于每3809行就可能有一个val=11546671的记录，因此index scan的总成本除以它就是最终min(xxx)的成本
15860545.10 / 3809.8688182440527126
=
4163.0160660781062716
4、为什么会选择xxx列的索引？
因为是基于成本的优化，所以最终会选择成本最低的。
假如使用val列的索引，并从heap table get tuples，因此需要扫描整个val列的索引，才能得到min(xxx)。还不如直接全表扫描。
5、为什么更换val条件性能会抖动？
因为前面提到的3809只是一个概率，不一定扫描3809行就能遇到一条 val=??? 的值，当 val=??? 分布在xxx索引的末端时，性能就会非常非常差。
优化方法 1
这个CASE使用复合索引就可以解决。
create index idx_tbl_val_xxx on tbl using btree (val,xxx);
为了达到最好的效果，驱动列建议只进行 = 或者 in 的查询，不要使用范围扫描。（最开始的扫描量越少越好，和多表JOIN的优化一个道理，最开始就将结果集降到最低）
优化方法 2
实际上从优化器的角度，还有优化的余地，让优化器选择val而非xxx的单独列索引。
例如数据按xxx索引进行cluster，然后统计连续的数据块的val的边界值。(类似brin索引)
评估出按xxx列排序扫描时，需要扫多少个数据块才能扫到 val=? 的值。