访问路径选择 - 基于规则的路径选择 - 《OceanBase v1.4 官方教程》

本文主要介绍Oceanbase路径选择的规则体系。目前Oceanbase路径选择的规则体系分为前置规则（正向规则）和Skyline剪枝规则(反向规则)。前置规则直接决定了一个查询使用什么样的索引，是一个强匹配的规则体系。Skyline剪枝规则会两两比较两个索引，如果一个索引在一些定义的维度上优于(dominate)另外一个索引，那么被dominated的那个索引会被剪掉，最后没有被剪掉的索引会进行代价比较，从而选出最优的计划。目前Oceanbase的优化器会优先使用前置规则选择索引，如果没有匹配的索引，那么Skyline剪枝规则会剪掉一些被dominated的索引，最后代价模型会在没有被剪掉的索引中选择代价最低的路径。

Oceanbase的计划展示中会输出相应的路径选择的规则信息，如下图所示。

OceanBase (root@test)> create table t1(a int primary key, b int, c int, d int, e int, unique index k1(b), index k2(b,c), index k3(c,d));
Query OK, 0 rows affected (0.38 sec)
OceanBase (root@test)> explain extended select * from t1 where b = 1;
| =====================================
|ID|OPERATOR  |NAME  |EST. ROWS|COST|
-------------------------------------
|0 |TABLE SCAN|t1(k1)|2        |94  |
=====================================
Outputs & filters:
-------------------------------------
  0 - output([t1.a(0x7f3178058bf0)], [t1.b(0x7f3178058860)], [t1.c(0x7f3178058f80)], [t1.d(0x7f3178059310)], [t1.e(0x7f31780596a0)]), filter(nil),
      access([t1.b(0x7f3178058860)], [t1.a(0x7f3178058bf0)], [t1.c(0x7f3178058f80)], [t1.d(0x7f3178059310)], [t1.e(0x7f31780596a0)]), partitions(p0),
      is_index_back=true,
      range_key([t1.b(0x7f3178058860)], [t1.shadow_pk_0(0x7f31780784b8)]), range(1,MIN ; 1,MAX),
      range_cond([t1.b(0x7f3178058860) = 1(0x7f31780581d8)])
Optimization Info:
-------------------------------------
t1:optimization_method=rule_based, heuristic_rule=unique_index_with_indexback
OceanBase (root@test)> explain extended select * from t1 where c < 5 order by c;
| ====================================
|ID|OPERATOR   |NAME|EST. ROWS|COST|
------------------------------------
|0 |SORT       |    |200      |1054|
|1 | TABLE SCAN|t1  |200      |666 |
====================================
Outputs & filters:
-------------------------------------
  0 - output([t1.a(0x7f3178059220)], [t1.b(0x7f31780595b0)], [t1.c(0x7f3178058e90)], [t1.d(0x7f3178059940)], [t1.e(0x7f3178059cd0)]), filter(nil), sort_keys([t1.c(0x7f3178058e90), ASC])
  1 - output([t1.c(0x7f3178058e90)], [t1.a(0x7f3178059220)], [t1.b(0x7f31780595b0)], [t1.d(0x7f3178059940)], [t1.e(0x7f3178059cd0)]), filter([t1.c(0x7f3178058e90) < 5(0x7f3178058808)]),
      access([t1.c(0x7f3178058e90)], [t1.a(0x7f3178059220)], [t1.b(0x7f31780595b0)], [t1.d(0x7f3178059940)], [t1.e(0x7f3178059cd0)]), partitions(p0),
      is_index_back=false, filter_before_indexback[false],
      range_key([t1.a(0x7f3178059220)]), range(MIN ; MAX)always true
t1:optimization_method=cost_based, avaiable_index_name[t1,k3], pruned_index_name[k1,k2]

其中optimization_method展示了具体的规则信息，它有以下两种形式:

如果optimization_method=rule_based, 那么就是命中了前置规则，同时会展示出具体命中的规则名称，下图中的unique_index_with_indexback 表示命中了前置规则的第三条规则(唯一性索引全匹配+回表+回表数量少于一定的阈值)。
如果optimization_method=cost_based, 那么就是基于代价选择出来的，同时会展示出来skyline剪枝规则剪掉了那些访问路径(pruned_index_name)以及剩下了那些访问路径(avaiable_index_name)。

前置规则

目前Oceanbase的前置规则只使用在简单的单表扫描上，因为前置规则是一个强匹配的规则体系，一旦命中，就直接选择命中的索引，所以要限制它的使用场景，以防选错计划。目前Oceanbase根据查询条件是否能覆盖所有索引键以及使用该索引是否需要回表这两个信息把前置规则按照优先级划分成如下三个匹配：

（1）唯一性索引全匹配+不需要回表(主键被当成唯一性索引来处理)，那么选择该索引。如果存在多个这样的索引，选择索引列数最小的一个。
（2）普通索引全匹配+不需要回表，那么选择该索引。如果存在多个这样的索引，选择索引列数最小的一个。
（3）唯一性索引全匹配+回表+回表数量少于一定的阈值，那么选择该索引。如果存在多个这样的索引，选择回表数量最小的一个。

这里需要注意的是索引全匹配是指在索引键上都存在等值条件(对应于get or multi-get)。举个例子，对于如下schema和查询，对于查询Q1，它命中了索引uk1(唯一性索引全匹配+不需要回表)。对于查询Q2，它命中了索引uk2（唯一性索引全匹配+回表+回表行数最多4行）。

    create table test(
        a int primary key, 
        b int, 
        c int, 
        d int, 
        e int, 
        unique key uk1(b,c), 
        unique key uk2(c,d)
        ）
    Q1: select b,c from test where (b = 1 or b = 2) and (c = 1 or c =2)
    Q2: select * from test where (c = 1 or c =2) or (d = 1 or d = 2）

Skyline剪枝规则

Skyline算子是学术界在2001年提出的一个新的数据库算子(它并不是标准的SQL算子)。自此之后，学术界对Skyline算子有大量的研究(包括语法，语义和执行等)。Skyline从字面上的理解是指天空中的一些边际点，这些点组成我们搜索空间中最优解的集合。例如我们要寻找价格最低并且路途最短的一家旅馆，想象一个二维空间，有两个维度，横轴表示价格，纵轴表示距离，二维空间上的每个点表示一个旅馆。从下图钟我们可以看到，不论最后的选择咋样，最优的解肯定是在这一条天空的边际线上。假设点A不在Skyline上，那么肯定能够在Skyline上找到在两个维度上都比他好的点B，在这个场景中就是距离更近，价格更便宜的旅馆，我们称点B dominate A。所以Skyline一个重要应用场景就是用户没办法去衡量多个维度的比重，或者多个维度不能综合量化(如果可以综合量化，我们可以使用SQL函数+order by就可以解决了)。

Skyline操作是在给定对象集O中找出不被别的对象所dominate的对象集合。若一个对象A在所有维度都不被另一个对象B所dominate，并且A至少在一个维度上dominate B，则称A dominate B。所以在Skyline操作中比较重要的是维度的选择以及在每个维度上的dominate的关系定义。对于优化器来讲，假设我们有N个索引的路径可以选择<idx_1，idx_2，idx_3…idx_n>，如果我们发现对于查询Q，索引idx_x在我们定义的维度上dominate idx_y。那我们就可以提前把索引idx_y剪掉，不让它参与最终代价的运算。

维度的定义

针对Skyline剪枝，我们对每个索引(主键也是一种索引)定义了三个维度:

（1）是否回表
（2）是否存在intersting order
（3）索引前缀能否抽取query range

简单解释一下，例如对于表：

    create table skyline(
        pk int primary key, a int, b int, c int,
        key idx_a_b(a, b),
        key idx_b_c(b, c),
        key idx_c_a(c, a));

回表：该查询是否需要需要回查主表

例如:

// 走索引idx_a_b的话就需要回查主表，因为索引idx_a_b没有列c。 
select /*+index(skyline idx_a_b)*/ * from skyline;

interesting order: 是否有合适的序可以利用

例如:

// 索引 idx_b_c 可以把order by语句消除。 
select pk, b from skyline order by b;

索引前缀能否抽取query range

例如:

//可以看到走索引idx_c_a 就可以快速定位到需要的行的范围，不用全表扫描。
select pk, b from skyline where c > 100 and c < 2000;

基于这三个维度，我们定义了索引之间的dominate关系，如果索引A在三个维度上都不比索引B差，并且其中至少有一个维度比B好，那么我们就可以直接把B索引剪掉，因为基于索引B最后生成的计划肯定不会比索引A好。

回表

如果索引idx_A 不需要回表，而索引idx_B需要回表，那么在这个维度上索引 idx_A dominate idx_B。

这个维度初看比较简单，就是查询的需要列在索引中有没有。但是其实有一些有意思的Case需要特殊考虑，例如当主表和索引表都没有Interesting order和抽取不了Query range的情况下，直接走主表不一定是最优解：


create table t1 (
    pk int primary key, a int, b int, c int,
    v1 varchar(1000), v2 varchar(1000), v3 varchar(1000), v4 varchar(1000)
    idx_a_b(a, b));
//考虑这一条查询
select a, b,c from t1 where b = 100;

索引	Index Back	Interesting Order	Query Range
primary	no	no	no
idx_a_b	yes	no	no

主表很宽，而索引表很窄，虽然从维度上主表 dominate 索引idx_a_b，然而，索引扫描加回表的代价不一定会比主表全表扫描来的慢。简单来说，索引表可能只需要读一个宏块，而主表可能需要十个宏块。这种情况下，需要对规则做一些放宽，考虑具体的过滤条件。

Interesting order

如果在索引 idx_A上抽取出来的intersting order是向量 Va<a1, a2, a3 …an>，在索引idx_B上抽出来的interesting order是向量Vb<b1, b2, b3…bm>, 如果n > m , 并且对于ai = bi （i=1..m）, 那么在这个维度上索引 idx_A dominate idx_B。

对于interesting order 这个维度，其实是有很多东西可以考虑的。Interesting Order像是优化器“借力打力”的过程，只要能利用底层的序，那我就不需要对底层扫描的行做排序，还可以消除Order by, 做Merge group by，提高Pipeline（不用物化）等等。

例如：

create table skyline (
    pk int primary key, v1 int, v2 int, v3 int, v4 int, v5 int,
    key idx_v1_v3_v5(v1, v3, v5),
    key idx_v3_v4(v3, v4));
create table tmp (c1 int primary key, c2 int, c3 int);
(select distinct v1, v3 from skyline join tmp where skyline.v1 = tmp.c1 order by v1, v3) union (select c1, c2 from tmp);

从执行计划我们可以看到，order by被消除了，同时使用了MERGE DISTINCT，UNION也没有做sort。可以看到，从底层TABLE SCAN 吐出来的序，可以被上层的算子使用。换句话说，保留idx_v1_v3_v5吐出来的行的顺序，可以让后面的算子在保序的情况下执行更优的操作。优化器在识别这些序的情况下，才能生成更优的执行计划。

所以Skyline剪枝对Interesting order的判断，需要充分考虑各个索引能够最大利用的序，例如上述最大的序其实是v1,v3 而不仅仅是v1，它从MERGE JOIN吐出来的序(v1, v3) 可以到MERGE DISINCT算子, 再到最后的UNISON DISTINCT 算子。优化器的“借力打力”的武功越高级，生成的计划就越好。

Query Range

如果在索引idx_A能用来抽取的query range的列集合是Sa<a1, a2, a3 …an>，在索引idx_B上能用来抽取query range的列集合是Sb <b1, b2, b3…bm>, 如果 Sa是Sb的super set, 那么在这个维度上索引idx_A dominate idx_B。

Query Range的抽取可以方便底层直接根据抽取出来的range定位到具体的宏块，而从减少存储层的IO。例如 select * from t1 where pk < 100 and pk > 0 就可以直接根据一级索引的信息定位到具体的宏块，加速查询，越精确的query range能够让数据库扫描更少的行。

示例:

    create table t1 (pk int primary key, a int, b int，c int,
        key idx_b_c(b, c),
        key idx_a_b(a, b));
    select b from t1 where a = 100 and b > 2000;

对于索引 idx_b_c 它能抽出query range的索引前缀是 (b)，对于索引 idx_a_b 它能抽出query range的索引前缀是 (a, b)，所以在这个维度上，索引 idx_a_b dominate idx_b_c

综合示例

create table skyline (
    pk int primary key, v1 int, v2 int, v3 int, v4 int, v5 int,
    key idx_v1_v3_v5(v1, v3, v5),
    key idx_v3_v4(v3, v4));
create table tmp (c1 int primary key, c2 int, c3 int);
select max(v5) from skyline where v1 = 100 and v3 > 200 group by v1;

索引	Index Back	Interesting order	Query range
primary	Not need	No	No
idx_v1_v3_v5	Not need	(v1)	(v1, v3)
idx_v3_v4	Need	No	(v3)

可以看到索引idx_v1_v3_v5 在三个维度上都不比主键索引或索引idx_v3_v4差。所以在我们的规则系统下，我们会直接剪掉主键索引和索引idx_v3_v4。维度的合理定义，决定了Skyline剪枝是否合理。错误的维度，将会导致该索引提前被剪掉，从而导致永远生成不了最优的计划。规则的应用是一把双刃剑，既要把不优的索引剪掉，更不能错杀。