TiDB 的统计信息

背景

数据库运行 SQL 时需要尽量选择最优的 Plan,来保证 SQL 执行的效率

一个最主要的指标是根据不同 Plan 的 row count 来判断优劣

统计信息就是用来估算不同 plan 的 row count

一、统计信息组成部分

  • show stats_meta;
  • show stats_histograms;
  • show stats_buckets;
  • show stats_healthy;

1、表级别

  • Modify_count
  • Row_count

2、列级别

  • Histogram

直方图,主要在 range 查询场景中用到

  • Count-Min Sketch

在点查场景中使用

  • Distinct count

某一列有多少个不同的值

  • Null count

某一列有多少个 Null 值

  • Avg col size

某一列的平均大小,可以忽略掉

  • Correlation

在 master 版本新增的功能,还在改进中,目的是使 order by limit n 场景尽量走 index scan 而不是 table scan

二、直方图(Histogram)

1、概念

WX20191016-114656%402x

  • Histogram 主要用于 range 查询场景。

例如:select count(*) from t where a > 1 and a < 10

  • 在 TiDB 中我们选择的是等深的直方图,每个 bucket 的 range 不会重叠。
  • 横坐标是每个 bucket 的范围;其中复合索引的场景,横坐标是 encode 之后的值,与在 tikv 中存储的索引数据的 key 相关。
  • 纵坐标表示桶深,可以理解为是对应 bucket 的 row count。
  • 对于每一个 bucket,我们认为数据是均匀分布的。
  • 估算之后,会选择 count 值最小的 plan 来执行

2、估算逻辑

  • 当一个查询完全覆盖了一个 bucket,这个 bucket 的高度就是 row count 的值。
  • 当一个查询覆盖了一个 bucket 的一部分,我们只需要计算这个 range 占整个 bucket 的比例,然后与桶深相称即可。

比如 (2.00, 2.75) 是一个 bucket,当查询的范围是 (2.15, 2.50) 时,rowCount(2.15, 2.5.0) = (2.50 - 2.15) / (2.75 - 2.00) * rowCount(2.00, 2.75)

  • 当一个查询覆盖了多个 bucket,计算方法与上面类似。

3、Bytes 类型的估算

由于存在 Bytes 或者 String 类型的数据,不能简单的按照上面的方法计算。关于数据在 kv 中的存储这里不再赘述,可以看一下我们官网博客。以索引为例,在 TiDB 中的估算方法如下:

  • 首先将索引的 key(包含 tableID、indexID、indexColumnValue 等) 中的相同前缀去掉,这部分相同的前缀对于估算没有影响。
  • 剩余的内容还是不能直接计算,这里我们会将前 8 个 Bytes 转换成 uint64,然后再用上面的方式计算

三、Count-Min Sketch

适用于在等值查询场景下 Plan 的选择

例如:select count(*) from t where a = 1

可以理解为在 TiDB 中维护了一个 d(行) * w(列) 的表

1、Count 统计

在插入数据(这里包含表数据和索引数据)的时候,会在 d 个 Hash 函数里面对写入的 Calue 做计算,映射到每一行的 [0, w) 区间的一个格子中,然后在对应的格子上 Count + 1。

2、估算 Count

由于同一个格子的信息可能会由于其他数据的写入而更新,当做估算的时候,会以 d 个 Count 中的最小值为准,这个值也最接近真实值。

当一个 SQL 执行时,会分别对多个索引或者表数据按照上面方式进行估算(每个一个索引或者数据的估算值都是取 d 个 Count 的最小值),然后对不同索引或者数据的 Count 值作对比,选择 Count 最小的 Plan。

四、Multi-column selecttivity

目前在 TIDB 上没有多列(这里是指联合索引之外的,可以是单列索引或者无索引)的统计信息,当遇到多列条件的查询时,我们按以下方式来估算。

1、独立性假设

当查询中的多列没有联合索引时,我们认为多列之间是不相关的或者相关性很低的,这时候我们就可以用下面示例中的方式来估算。

select count(*) from t where a = 1 and b < 1 and c > 1;

表中没有 a,b,c 这三个字段任意组合的联合索引,估算方式为:

sel(a = 1 and b < 1 and c >1) = sel(a = 1) * sel(b < 1) * sel(c > 1)

2、有联合索引的多列查询

当查询中的多列存在联合索引时,我们将其转化为范围查询或者等值查询,下面举例说明。

2.1、范围查询

范围查询参考直方图(Histogram)的方式,使用联合索引 Encode 之后的范围来估算

select count(*) from t where a = 1 and b < 1;

表中存在 a,b 的联合索引,估算方式为:

sel(a = 1 and b < 1) = sel([a=1, b=-inf), [a=1, b=1))

2.2、等值查询

等值查询参考 Count-Min Sketch 的方式,通过查 Encode 之后的联合索引的 Value 对应的 Count 值来估算

select count(*) from t where a = 1 and b = 1;

表中存在 a,b 的联合索引,估算方式为:

sel(a = 1 and b < 1) = sel([a=1, b=-inf), [a=1, b=1))

五、估算不准的场景

  • 统计信息过期
  • 独立性假设场景不适用,这种估算的数值和真实值差距比较大,可能会导致选到比较差的索引,或者扫全表