【是否原创】是
【首发渠道】TiDB 社区

背景

在生产测试环境遇到这样一个场景，它的表结构 objects 大致是这样的：

这个表 objects 有一个联合前缀索引 idx(bucket_id, name(498), version_id)，之所以这么用有以下原因：

• 所有查询类似 select * from objects where bucket_id = “XXXX” and name > “xxxxy” order by name asc limit n;
• 由于业务标准属性要求，name 字段需要达到 1024 长度
• 索引有长度限制，TiDB 默认值以及 MySQL 长度都是 3072 字节（这里是字节数）

而 objects 表数据分布又有一个特点：

• bucket_id 数量极少，只有几十到几百个
• 同样 bucket_id 下，name 又极多，从几十万到几百万，甚至千万级别

关于 name 列长度，原来没有那么大，之前是把它设为普通联合索引 idx(bucket_id, name, version_id)，这时候查询速度非常快，但是增大 name 并调整 idx 为前缀索引后，执行性能突然变慢了。

在不同 bucket_id 下，随着 name 条数增多，执行耗时呈现出线性增长，当达到 661666 条记录并且机器负载很低的情况下，耗时达到 0.49 秒，对业务来说已经太慢了：

分析原因

从普通联合索引，转为前缀联合索引，执行耗时差别之大是出乎意料的，下面看看两种执行计划的差别：

普通联合索引

mysql> explain select * from objects where bucket_id="bucket_id_0" and name >= "aaaaa" order by name asc limit 1\"G
*************************** 1. row ***************************
           id: IndexLookUp_24
      estRows: 1.00
         task: root
access object: 
operator info: limit embedded(offset:0, count:1)
*************************** 2. row ***************************
           id: ├─Limit_23(Build)
      estRows: 1.00
         task: cop[tikv]
access object: 
operator info: offset:0, count:1
*************************** 3. row ***************************
           id: │ └─IndexRangeScan_21
      estRows: 1.00
         task: cop[tikv]
access object: table:objects, index:idx_tt(bucket_id, name, ver_id)
operator info: range:["bucket_id_0" "aaaaa","bucket_id_0" +inf], keep order:true
*************************** 4. row ***************************
           id: └─TableRowIDScan_22(Probe)
      estRows: 1.00
         task: cop[tikv]
access object: table:objects
operator info: keep order:false
4 rows in set (0.00 sec)

这里通过 IndexRangeScan_21 顺序扫描 Limit_23 个 rowId，然后进行回表 TableRowIDScan_22，取出数据后返回，效率非常快。

前缀联合索引

mysql> explain select * from objects where bucket_id="bucket_id_0" and name >= "aaaaa" order by name asc limit 1\"G
*************************** 1. row ***************************
           id: TopN_9
      estRows: 1.00
         task: root
access object: 
operator info: demo_prefix.objects.name, offset:0, count:1
*************************** 2. row ***************************
           id: └─IndexLookUp_21
      estRows: 1.00
         task: root
access object: 
operator info: 
*************************** 3. row ***************************
           id:   ├─IndexRangeScan_17(Build)
      estRows: 10435.77
         task: cop[tikv]
access object: table:objects, index:idx_tt(bucket_id, name, ver_id)
operator info: range:["bucket_id_0" "aaaaa","bucket_id_0" +inf], keep order:false
*************************** 4. row ***************************
           id:   └─TopN_20(Probe)
      estRows: 1.00
         task: cop[tikv]
access object: 
operator info: demo_prefix.objects.name, offset:0, count:1
*************************** 5. row ***************************
           id:     └─Selection_19
      estRows: 10435.77
         task: cop[tikv]
access object: 
operator info: ge(demo_prefix.objects.name, "aaaaa")
*************************** 6. row ***************************
           id:       └─TableRowIDScan_18
      estRows: 10435.77
         task: cop[tikv]
access object: table:objects
operator info: keep order:false
6 rows in set (0.01 sec)

这里执行计划同样选择了 idx 索引走 IndexLookUp_21 流程：

1. build 端 IndexRangeScan_17 扫描 range:[“bucket_id_0” “aaaaa”,“bucket_id_0” +inf] 范围内所有的 rowId

2. Probe 端：

   • TableRowIDScan_18 将 rowId 进行回表，检索出完整的行记录
   • Selection_19 执行 name >= “aaaaa” 的过滤
   • TopN_20 按照 name 排序，选出需要返回的 1 行

3. root 端，TopN_9 汇聚 copTask 所有的 TopN_20 结果，返回最终的结果。

从这个执行计划看，正确性没有任何值得怀疑的地方，但是在我们的数据场景中，执行性能就很低。慢就慢在将 range:[“bucket_id_0” “aaaaa”,“bucket_id_0” +inf] 范围内所有的 rowId 进行了 TableRowIDScan_18 操作，而我们的数据场景，这里可能有几十万到上千万数据记录，所以在记录数达到 27995202 条时候，耗时达到 16.35 sec。

优化思考

普通的联合索引执行计划，在 order by indexColA, indexColB limit N 时候，直接顺序扫描 N 条记录即可。

但是在前缀索引的情况，索引中列不包括全部的列的值，这时候没办法直接按照顺序扫描的 keys 保证有序，所以在当前的执行计划中是进行了所有 rowId 的回表，然后取出完整的列进行 topN 排序返回的。

但是即使在前缀联合索引情况下，索引值在某种意义下，仍然是有序的，比如 idx(a, b(32))：

1. 那么 idx 是按照 a 列严格有序的
2. 对于 b 列，会根据 b 的前 31 个字符严格有序

而对于前缀索引 order by indexColA, indexColB limit N 时候，基于上述有序性，是可以根据数据的情况，确定要查询的数据在一定的范围的。

假设我们有下面一条 sql，而表 t 有个前缀索引 idx(a, b[3]) :

select * from t where a= "a", b>= "dddd" order by a, b asc limit 5; 

表 t 的数据如下，col_a 代表 a 列的值，col_b 代表 b 列的值，keyNum 是这里标注的一个序号，代表当前列的值在 idx 索引上的虚拟序号：

keyNum                col_a               col_b
1                     a                   ddda
2                     a                   dddf
3                     a                   dddc
4                     a                   e
5                     a                   f
6                     a                   f
7                     a                   g			
8                     a                   hadf
9                     a                   hadc
10                    a                   hadgs
11                    a                   j
12                    a                   k
13                    a                   l
...                   ...                 ...
...                   ...                 ...

我们的 sql 希望返回的数据行数为 5 条，我们根据上述的有序性，顺序扫描 idx，根据数据情况，可以确定要返回的记录一定位于某个范围内。

满足我们查询结果的数据记录集为：

keyNum                col_a               col_b
2                     a                   dddf
4                     a                   e
5                     a                   f
6                     a                   f
7                     a                   g

我们以 cnt 代表需要扫描的 idx keys，cnt = cn1 + cn2 + cn3，最终扫描返回以下行的 rowId 即可停止，因为后面的行是一定不满足的：

keyNum                col_a               col_b
1                     a                   ddda
2                     a                   dddf
3                     a                   dddc
4                     a                   e
5                     a                   f
6                     a                   f
7                     a                   g			
8                     a                   hadf
9                     a                   hadc
10                    a                   hadgs

cnt = cn1 + cn2 + cn3 计算：

• cn1: 因为查询条件 b>= “dddd” 是被截断的，那么对于截断的 “ddd”，相同的记录 rowId 要返回，这里是前三条
• cn2: cn1 查询来的记录有可能都满足，有可能都不满足，那么按照都不满足的情况，扫描后面四条
• cn3: 由于cn1 + cn2 至少有 4 条是满足的，那么期望再扫描一条，由于 8、9、10 三条前缀都是 “had”， 那么把这三条也扫描出来

最后返回的 rowId 个数为 3 + 4 + 3 = 10 个，也就是说我们的查询结果数据集，一定在这 10 个 rowId 的记录内。

数据同上，查询条件为 select * from t where a= “a”, b>= “e” order by a, b asc limit 5;

cn1 + cn2 + cn3 三个值：

• cn1：由于 b>=“e” 没有被截断，那么 keyNum 为 4 扫描出来就是满足的，这个记录数为 1.
• cn2:为 5、6、7的记录三条
• cn3:目前cn1 + cn2 = 4 条，需要再扫描后面连续的具有相同前缀“had”的三条。

最后返回的 rowId 个数为 1 + 3 + 3 = 7 个。

优化尝试

当前的执行计划，因为扫描了 range:[“bucket_id_0” “aaaaa”,“bucket_id_0” +inf] 范围内的 rowId 进行 TableRowIDScan_22 回表导致耗时较长。

在上一节，通过顺序扫描 idx，根据数据集情况，可以提前终止扫描过程，极大的减少了 rowId 数量。

进行一个如下的优化尝试，生成如下的执行计划：

mysql> explain select * from objects where bucket_id="bucket_id_0" and name >= "aaaaa" order by name asc limit 1\"G
*************************** 1. row ***************************
           id: Like_TopN_9
      estRows: 1.00
         task: root
access object: 
operator info: test.objects.name, offset:0, count:1
*************************** 2. row ***************************
           id: └─IndexLookUp_17
      estRows: 33.33
         task: root
access object: 
operator info: 
*************************** 3. row ***************************
           id:   ├─Like_Limit_16(Build)
      estRows: 1.00
         task: cop[tikv]
access object: 
operator info: offset:0, count:1
*************************** 4. row ***************************
           id:   │ └─IndexRangeScan_13
      estRows: 33.33
         task: cop[tikv]
access object: table:objects, index:idx_tt(bucket_id, name, ver_id)
operator info: range:["bucket_id_0" "aaaaa","bucket_id_0" +inf], keep order:true, stats:pseudo
*************************** 5. row ***************************
           id:   └─Selection_15(Probe)
      estRows: 33.33
         task: cop[tikv]
access object: 
operator info: ge(test.objects.name, "aaaaa")
*************************** 6. row ***************************
           id:     └─TableRowIDScan_14
      estRows: 33.33
         task: cop[tikv]
access object: table:objects
operator info: keep order:false, stats:pseudo
6 rows in set (0.02 sec)

执行流程如下：

1. Build 端：

   • IndexRangeScan_13 顺序扫描 idx keys
   • Like_Limit_16 根据 idx 的数据集返回 rowIds

2. Probe 端：

   • TableRowIDScan_14 对 rowId 进行回表检索完整的行记录
   • Selection_15 用过滤条件 name >= “aaaaa” 过滤数据

3. root 端执行 Like_TopN_9 提取前 n 条返回

说明：

• Like_Limit_16 实现了类似 Limit 下推算子的语法功能，但它会根据扫描出来的值的特征决定是否已经获取足够的数据，判断方法如之前描述。
• Like_TopN_9 同样实现类似 TopN 算子的语法功能，他会根据 tikv 返回的记录的值的特征决定是否已经获取足够的数据，判断方法如之前描述。

正确性证明

• Like_Limit 算子保证了正确记录的 rowId 一定会被扫描到
• Selection 算子将不符合的记录过滤掉
• 由于 IndexRangeScan 的 keep order:true， IndexLookUp 返回的记录，按照 idx 索引顺序（keyNum ）有序
• Like_TopN 收到的记录按照 bucket_id, name(498) 有序，但是不能说按照 bucket_id，name 有序，这里进行一次 heap 排序，使其按照 bucket_id，name 有序，最后返回正确的记录

归纳

上述的执行计划，它可以直接针对以下类型场景：

create table t (id bigint, a varchar(8), b varchar(32), c int, idx(b(16)) );
select * from where b > "xxxx"  order by b limit n;
select * from where b > "xxxx"  order by b limit m, n; 

create table t (id bigint, a varchar(8), b varchar(32), c int, idx(a, b(16)) );
select * from where a = "xxxxx" and b > "xxxx"  order by b limit n;
select * from where a = "xxxxx" and b > "xxxx"  order by b limit m, n; 

create table t (id bigint, a varchar(8), b varchar(32), c varchar(32), idx(a, b, c(16)));
select * from where a = "xxxxx" and b = "xxxx" and c > "xxxx" order by c limit n;
select * from where a = "xxxxx" and b = "xxxx" and c > "xxxx" order by c limit m, n;

特点如下：

• 索引 index ( a, b, c, d, … , z[k] )
• 查询条件 select XXX, XXX from t where a=“XXX” and b=“xxx”, c = “xxx”, … , and z > “XXX” limit m, n;

它利用了前缀索引按照 z[k - 1] 绝对有序的特点，将正确的记录数的 rowId 确定在一个范围内，减少 rowId 的扫描，从而达到跟普通索引上执行的效率。

延伸一

create table t (id bigint, a varchar(8), b varchar(32), c varchar(32), idx(a, b, c(16)));
select * from t where a > "xxxx" and  b > "xxx" and c > "xxxx" order by a, b, c limit n;

这个 sql 也是可以的，执行计划在 IndexRangeScan 的 Build 改为：

• IndexRangeScan，range:[“xxx” “xxx” “xxxx”, +inf]
• Selection 过滤掉 b > “xxx”
• Like_Limit 对 a，b, c > “xxxx” 进行判断

create table t (id bigint, a varchar(8), b varchar(32), c varchar(32), idx(a, b(16), c));
select * from t where a > "xxxx" and  b > "xxx" and c > "xxxx" order by a, b, c limit n;

执行计划在 IndexRangeScan 的 Build 改为：

• IndexRangeScan，range:[“xxx” “xxx” , +inf]，不带 c 的参数
• Selection 过滤掉 c > “xxxx”
• Like_Limit 对 a，b(16) 进行评估

延伸二

对于普通索引，差不多也是有效的：

create table t (id bigint, a varchar(8), b varchar(32), c varchar(32), idx(a, b, c));
select * from t where a > "xxxx" and c > "xxxx" order by a, c limit n;

执行计划在 IndexRangeScan 的 Build 改为：

• IndexRangeScan，range:[“xxx” , +inf]，不带 c 的参数
• Selection 过滤掉 c > “xxxx”
• Like_Limit 对 a 评估

create table t (id bigint, a varchar(8), b varchar(32), c varchar(32), idx(a, b));
select * from t where a > "xxxx" order by a, c limit n;

在这里 c 并不是索引列，执行计划在 IndexRangeScan 的 Build 改为：

• IndexRangeScan，range:[“xxx” , +inf]，不带 c 的参数
• Like_Limit 对 a 评估

create table t (id bigint, a varchar(8), b varchar(32), c varchar(32), primary id);
select * from t where order by id, a limit n;

由于 id 是主键，那么 order by id, a 等价于 order by id，这里其实逻辑优化就可以去掉，这个 sql 本身很奇葩，但是 tidb 也没有很好地优化掉。

执行计划在 IndexRangeScan 的 Build 改为：

• IndexRangeScan，range:[-inf , +inf]，不带 c 的参数
• Like_Limit 对 id 评估

总结与扩展

select * from t where [col_a condition, con_b condition, col_c condition] order by col_a, col_b, col_c limit m, n

t 有索引 idx (col_a, [col_b, col_c])

这类 sql 有个特点：

• 特点1，order by 的列和 idx 的列，具有前面公有的、连续的一部分相同列，假设公有部分是 col_common

• 特点2，where condition 中，只包含 col_common 的列的 condition 条件

  说明：col_common 遇到不同的列或者具有前缀索引的列时终止

说明：

• col_common 遇到不同的列或者具有前缀索引的列时终止
• 如果是遇到不同的列，那么此列不属于 col_common
• 如果遇到前缀索引，那么此列前缀长度属于 col_common

特点 2 的约束是为了通过 IndexRangeScan 检索的结果，能判断某个值一定不属于查询的正确值

对于上面的 sql 特点，如果出现以下情况：

• 特点 1，col_common 是完整的 order by 的列
• where condition 只跟 order by 的列有关

那么 tidb 可以完美的使用 idx 索引，通过 IndexRangeScan 的 keep order:true 高效的完成数据检索。

func (ds *DataSource) isMatchProp(path *util.AccessPath, prop *property.PhysicalProperty) bool {
   var isMatchProp bool
   ...
   all, _ := prop.AllSameOrder()
   // When the prop is empty or `all` is false, `isMatchProp` is better to be `false` because
   // it needs not to keep order for index scan.

   // Basically, if `prop.SortItems` is the prefix of `path.IdxCols`, then `isMatchProp` is true. However, we need to consider
   // the situations when some columns of `path.IdxCols` are evaluated as constant. For example:
   // ```
   // create table t(a int, b int, c int, d int, index idx_a_b_c(a, b, c), index idx_d_c_b_a(d, c, b, a));
   // select * from t where a = 1 order by b, c;
   // select * from t where b = 1 order by a, c;
   // select * from t where d = 1 and b = 2 order by c, a;
   // select * from t where d = 1 and b = 2 order by c, b, a;
   // ```
   // In the first two `SELECT` statements, `idx_a_b_c` matches the sort order. In the last two `SELECT` statements, `idx_d_c_b_a`
   // matches the sort order. Hence, we use `path.ConstCols` to deal with the above situations.
   if !prop.IsEmpty() && all && len(path.IdxCols) >= len(prop.SortItems) {
      isMatchProp = true
      i := 0
      for _, sortItem := range prop.SortItems {
         found := false
         for ; i < len(path.IdxCols); i++ {
            if path.IdxColLens[i] == types.UnspecifiedLength && sortItem.Col.Equal(nil, path.IdxCols[i]) {
               found = true
               i++
               break
            }
            if path.ConstCols == nil || i >= len(path.ConstCols) || !path.ConstCols[i] {
               break
            }
         }
         if !found {
            isMatchProp = false
            break
         }
      }
   }
   return isMatchProp
}

但是对于这种类型 sql 其他的情况，tidb 并没有一个较好的执行计划，尤其对于以下场景，性能较差：

• limit m, n; 其中 m+n 值很小
• where 条件要过滤的 range 很大（扫描的 keys 特别多）

所以针对这种类型 sql，利用 col_common，通过走 idx 索引的 IndexRangeScan 的 keep order:true，减少 rowId （聚簇索引时候为主键）的扫描，从而减少 TableRowIDScan_的回表，将能极大的提高查询的性能。

通过将 col_common 下推，实现 tikv server 的 Like_Limit 与 tidb server 的 Like_TopN，实现跟 isMatchProp 为 true 时差不多的查询效率。

TiDB Hackathon

我们以此为主题，参加本届 Hackathon，四个非专业内核人员，抱着以学习为主的心态，进行一些简单的摸索与尝试。

队名：摸鱼不

口号：摸鱼不对，向大佬学习才对

队员：

• chenyf 电信云-后端开发
• liuke 杭州网易-后端开发
• zhaoxugang 深圳顺丰-后端开发
• jiyf 电信云-后端开发

队长：jiyf