openGauss 3.1.0的新型选择率模型大解密 王天庆20221012

当前经典数据库优化器对于等值查询估计的缺点

例如，目前形如a = 1的等值谓词选择率估算可以有以下几种方法：

1. 利用统计信息估算：
   • 对查询语句中的等值条件，可分为 MCV 值和非 MCV 值进行估算：
   • 对 MCV 值，使用 MCV 对应的频率统计信息作为选择率；
   • 对非 MCV 值，使用如下经验公式： $$eq_{selectivity}=\frac{1-sum_mcv-num_nulls}{ndv}$$
   • 直接对所有值做均匀假设，不考虑 MCV： $$eq_{selectivity}=\frac{num_rows-num_nulls}{ndv}/num_rows$$
2. 在线计算：
   • 使用 Count-Mean-Min Sketch 等频率估算方法，在线计算每个常量值的选择率。

在上述方法中，方法 1 对全部或者部分数据做均匀分布假设，计算量小，优化器负担轻，但估算粗略，对大多数常量选择率估值不准确；方法 2 对每个常量值都进行单独的计算，计算结果较为准确，但是优化器的计算负担大，将对性能产生影响。

openGauss 的新型选择率模型

基于上述经典优化器的缺点，在该版本的 openGauss 数据库中，我们通过调整等值谓词选择率的估算方法，构造出 openGauss 的新型选择率模型，可以在兼顾准确率与计算量的前提下，进行选择率的估计。该模型原理如下：

• 对 MCV 值，使用 MCV 对应的频率统计信息作为选择率；
• 对不落入 MCV 也不落入直方图的值，使用如下公式： $$eq_{selectivity}=\frac{1}{rows}$$
• 对落入直方图的值
  • 桶左右边界相等，使用桶的数量估算常量选择率： $$eq_selectivity=height_of_histogram * num_eq_slot$$ $$ eq_selectivity=\frac{1-null_fraction-sum_mcv}{num_slot}*num_eq_slot $$
  • 桶左右边界不等，使用插值方法，估算常量选择率： $$eq_selectivity=height_of_histogram * freq_of_const_in_slot$$ $$eq_selectivity=\frac{1-null_fraction-sum_mcv}{num_slot}\frac{(high-low)}{distinct(right-left)}$$

新型选择率模型平衡计算量与准确性，充分考虑数据分布情况，通过轻量的计算，能够使得优化器生成更优的执行计划，该特性可通过 GUC 参数 var_eq_const_selectivity 控制。

使用示例

假设在数据库中表 t1 由 2 列组成，分别为列 a 和列 b，其类型均为整型（INT）。向其插入数据，a 值为 101 的数据共有 300 行，a 值为 1 到 100 的数据各有 100 行，a 值为 150 的数据 150,000 行，a 值为 200 的数据有 1 行。则表 t1 由数据库得到的统计信息可如下：

当查询语句为SELECT * FROM t1 WHERE a = 101; 时，可知 a 落入直方图桶[101,101)中，且与当前桶左右边界相同的桶的总个数为 2，则 a 的选择率为(1 – 0 – 0. 9369) / 100 * 2 = 3.9816e-7。

当查询为SELECT * FROM t1 WHERE a = 11;时，可知 a 落入直方图桶[11,12)中，该桶在均匀假设的前提下，分配到的 distinct 值数量为103 / (101 - 1) * (12 – 11) ，则a的选择率为(1 – 0 – 0. 9369) / 100 /(103 / (101 - 1) * (12 – 11) ) = 6.1262e-4。

当查询为SELECT * FROM t1 WHERE a = 200;时，常量值 200 没有落入 MCV，也没有落入直方图的任何一个桶中，则利用 t1 的总行数 160301 来预估其选择率，则 a 的选择率为1 / 160301 = 6.2383e-6。

从上面的示例可以看出，使用新型选择率模型，充分考虑了不同常量值的选择率，其选择率估算能够更加贴近实际值。此外，openGauss 还会在数据库的查询优化领域进一步努力，构造业内顶尖的数据库查询优化能力。