Oceanbase目前只实现了一个基于代价的查询改写（or-expansion）。其实数据库中很多高级的改写规则（比如complex view merge和窗口函数改写）都需要基于代价进行改写，Oceanbase后续会实现这些复杂的改写规则。

    或展开（Or-Expansion）

    Or-expansion把一个查询改写成若干个用union组成的子查询，这个改写可能会给每个子查询提供更优的优化空间，但是也会导致多个子查询的执行，所以这个改写需要基于代价去判断。通常来说，Or-expansion的改写主要有如下三个作用:

    • 允许每个分支使用不同的索引来加速查询

    如下图所示，Q1会被改写成Q2的形式，其中Q2中的谓词lnnvl(t1.a = 1)保证了这两个子查询不会生成重复的结果。如果不进 行改写，Q1一般来说会选择主表作为访问路径，对于Q2来说，如果t1上存在索引（a）和索引（b），那么该改写可能会让Q2中的每一个子查询选择索引作为访问路径。

    1. Q1: select * from t1 where t1.a = 1 or t1.b = 1;
    2. Q2: select * from t1 where t1.a = 1 union all select * from t1.b = 1 and lnnvl(t1.a = 1);
    1. OceanBase (root@test)> create table t1(a int, b int, c int, d int, e int, index idx_a(a), index idx_b(b));
    2. --- 如果不进行or-expansion的改写，该查询只能使用主表访问路径
    3. OceanBase (root@test)> explain select/*+NO_REWRITE()*/ * from t1 where t1.a = 1 or t1.b = 1;
    4. +-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
    5. | Query Plan                                                                                                                                                                                                                                                                                                                                                                                                  |
    6. +-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
    7. | ===================================
    8. |ID|OPERATOR  |NAME|EST. ROWS|COST|
    9. -----------------------------------
    10. |0 |TABLE SCAN|t1  |4        |649 |
    11. ===================================
    13. Outputs & filters:
    14. -------------------------------------
    15.   0 - output([t1.a], [t1.b], [t1.c], [t1.d], [t1.e]), filter([t1.a = 1 OR t1.b = 1]),
    16.       access([t1.a], [t1.b], [t1.c], [t1.d], [t1.e]), partitions(p0)
    17. --- 改写之后，每个子查询能使用不同的索引访问路径
    18. OceanBase (root@test)> explain select * from t1 where t1.a = 1 or t1.b = 1;
    19. +------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
    20. | Query Plan                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           |
    21. +------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
    22. | =========================================
    23. |ID|OPERATOR   |NAME     |EST. ROWS|COST|
    24. -----------------------------------------
    25. |0 |UNION ALL  |         |3        |190 |
    26. |1 | TABLE SCAN|t1(idx_a)|2        |94  |
    27. |2 | TABLE SCAN|t1(idx_b)|1        |95  |
    28. =========================================
    30. Outputs & filters:
    31. -------------------------------------
    32.   0 - output([UNION(t1.a, t1.a)], [UNION(t1.b, t1.b)], [UNION(t1.c, t1.c)], [UNION(t1.d, t1.d)], [UNION(t1.e, t1.e)]), filter(nil)
    33.   1 - output([t1.a], [t1.b], [t1.c], [t1.d], [t1.e]), filter(nil),
    34.       access([t1.a], [t1.b], [t1.c], [t1.d], [t1.e]), partitions(p0)
    35.   2 - output([t1.a], [t1.b], [t1.c], [t1.d], [t1.e]), filter([lnnvl(t1.a = 1)]),
    36.       access([t1.a], [t1.b], [t1.c], [t1.d], [t1.e]), partitions(p02
    • 允许每个分支使用不同的连接算法来加速查询，避免使用笛卡尔连接

    如下图所示，Q1会被改写成Q2的形式。对于Q1来说，它的连接方式只能是nested loop join(笛卡尔乘积)， 但是被改写之后，每个子查询都可以选择nested loop join，hash join或者merge join，这样会有更多的优化空间。

    1. Q1: select * from t1, t2 where t1.a = t2.a or t1.b = t2.b;
    2. Q2: select * from t1, t2 where t1.a = t2.a union all
    3.     select * from t1, t2 where t1.b = t2.b and lnnvl(t1.a = t2.a)
    1. OceanBase (root@test)> create table t1(a int, b int);
    2. Query OK, 0 rows affected (0.17 sec)
    3. OceanBase (root@test)> create table t2(a int, b int);
    4. Query OK, 0 rows affected (0.13 sec)
    5. ---如果不进行改写，只能使用nested loop join
    6. OceanBase (root@test)> explain select/*+NO_REWRITE()*/ * from t1, t2 where t1.a = t2.a or t1.b = t2.b;
    7. | ===========================================
    8. |ID|OPERATOR        |NAME|EST. ROWS|COST  |
    9. -------------------------------------------
    10. |0 |NESTED-LOOP JOIN|    |3957     |585457|
    11. |1 | TABLE SCAN     |t1  |1000     |499   |
    12. |2 | TABLE SCAN     |t2  |4        |583   |
    13. ===========================================
    15. Outputs & filters:
    16. -------------------------------------
    17.   0 - output([t1.a], [t1.b], [t2.a], [t2.b]), filter(nil),
    18.       conds(nil), nl_params_([t1.a], [t1.b])
    19.   1 - output([t1.a], [t1.b]), filter(nil),
    20.       access([t1.a], [t1.b]), partitions(p0)
    21.   2 - output([t2.a], [t2.b]), filter([? = t2.a OR ? = t2.b]),
    22.       access([t2.a], [t2.b]), partitions(p0)
    23. ---被改写之后，每个子查询都使用了hash join
    24. OceanBase (root@test)> explain select * from t1, t2 where t1.a = t2.a or t1.b = t2.b;
    25. |ID|OPERATOR    |NAME|EST. ROWS|COST|
    26. -------------------------------------
    27. |0 |UNION ALL   |    |2970     |9105|
    28. |1 | HASH JOIN  |    |1980     |3997|
    29. |2 |  TABLE SCAN|t1  |1000     |499 |
    30. |3 |  TABLE SCAN|t2  |1000     |499 |
    31. |4 | HASH JOIN  |    |990      |3659|
    32. |5 |  TABLE SCAN|t1  |1000     |499 |
    33. |6 |  TABLE SCAN|t2  |1000     |499 |
    34. =====================================
    36. Outputs & filters:
    37. -------------------------------------
    38.   0 - output([UNION(t1.a, t1.a)], [UNION(t1.b, t1.b)], [UNION(t2.a, t2.a)], [UNION(t2.b, t2.b)]), filter(nil)
    39.   1 - output([t1.a], [t1.b], [t2.a], [t2.b]), filter(nil),
    40.       equal_conds([t1.a = t2.a]), other_conds(nil)
    41.   2 - output([t1.a], [t1.b]), filter(nil),
    42.       access([t1.a], [t1.b]), partitions(p0)
    43.   3 - output([t2.a], [t2.b]), filter(nil),
    44.       access([t2.a], [t2.b]), partitions(p0)
    45.   4 - output([t1.a], [t1.b], [t2.a], [t2.b]), filter(nil),
    46.       equal_conds([t1.b = t2.b]), other_conds([lnnvl(t1.a = t2.a)])
    47.   5 - output([t1.a], [t1.b]), filter(nil),
    48.       access([t1.a], [t1.b]), partitions(p0)
    49.   6 - output([t2.a], [t2.b]), filter(nil),
    50.       access([t2.a], [t2.b]), partitions(p0)
    • 允许每个分支分别消除排序，更加快速的获取top-k结果

    如下图所示，Q1会被改写成Q2。对于Q1来说，执行方式是只能把满足条件的行数找出来，然后进行排序，最终取top-10结果。对于Q2来说，如果存在索引(a,b), 那么Q2中的两个子查询都可以使用索引把排序消除，每个子查询取top-10结果，然后最终对这20行数据排序一下取出最终的top-10行。

    1. Q1: select * from t1 where t1.a = 1 or t1.a = 2 order by b limit 10;
    2. Q2: select * from 
    3.     (select * from t1 where t1.a = 1 order by b limit 10 union all
    4.      select * from t1 where t1.a = 2 order by b limit 10) as temp
    5.     order by temp.b limit 10;
    1. OceanBase (root@test)> create table t1(a int, b int, index idx_a(a, b));
    2. Query OK, 0 rows affected (0.20 sec)
    3. ---不改写的话，需要排序最终获取top-k结果
    4. OceanBase (root@test)> explain select/*+NO_REWRITE()*/ * from t1 where t1.a = 1 or t1.a = 2 order by b limit 10;
    5. | ==========================================
    6. |ID|OPERATOR    |NAME     |EST. ROWS|COST|
    7. ------------------------------------------
    8. |0 |LIMIT       |         |4        |77  |
    9. |1 | TOP-N SORT |         |4        |76  |
    10. |2 |  TABLE SCAN|t1(idx_a)|4        |73  |
    11. ==========================================
    13. Outputs & filters:
    14. -------------------------------------
    15.   0 - output([t1.a], [t1.b]), filter(nil), limit(10), offset(nil)
    16.   1 - output([t1.a], [t1.b]), filter(nil), sort_keys([t1.b, ASC]), topn(10)
    17.   2 - output([t1.a], [t1.b]), filter(nil),
    18.       access([t1.a], [t1.b]), partitions(p0)
    19. --- 进行改写的话，排序算子可以被消除，最终获取top-k结果
    20. OceanBase (root@test)> explain select * from t1 where t1.a = 1 or t1.a = 2 order by b limit 10;
    21. | ===========================================
    22. |ID|OPERATOR     |NAME     |EST. ROWS|COST|
    23. -------------------------------------------
    24. |0 |LIMIT        |         |3        |76  |
    25. |1 | TOP-N SORT  |         |3        |76  |
    26. |2 |  UNION ALL  |         |3        |74  |
    27. |3 |   TABLE SCAN|t1(idx_a)|2        |37  |
    28. |4 |   TABLE SCAN|t1(idx_a)|1        |37  |
    29. ===========================================
    31. Outputs & filters:
    32. -------------------------------------
    33.   0 - output([UNION(t1.a, t1.a)], [UNION(t1.b, t1.b)]), filter(nil), limit(10), offset(nil)
    34.   1 - output([UNION(t1.a, t1.a)], [UNION(t1.b, t1.b)]), filter(nil), sort_keys([UNION(t1.b, t1.b), ASC]), topn(10)
    35.   2 - output([UNION(t1.a, t1.a)], [UNION(t1.b, t1.b)]), filter(nil)
    36.   3 - output([t1.a], [t1.b]), filter(nil),
    37.       access([t1.a], [t1.b]), partitions(p0),
    38.       limit(10), offset(nil)
    39.   4 - output([t1.a], [t1.b]), filter([lnnvl(t1.a = 1)]),
    40.       access([t1.a], [t1.b]), partitions(p0),
    41.       limit(10), offset(nil)