コストに基づくクエリのリライト

OceanBaseデータベースは現在、コストに基づくクエリのリライトとしてOR-Expansionのみをサポートしています。

データベース内の多くの高度なリライトルール（例えばComplex View Mergeやウィンドウ関数によるリライト）は、コストに基づいて実行される必要があります。OceanBaseデータベースの今後のバージョンでは、これらの複雑なリライトルールもサポートされる予定です。

OR-Expansion

OR-Expansionとは、あるクエリをUNIONで構成される複数のサブクエリに書き換える手法です。これにより各サブクエリに対してより優れた最適化の余地が生まれますが、同時に複数のサブクエリが実行されることになるため、書き換えるかどうかはコストに基づいて判断する必要があります。

OR-Expansionによる書き換えには主に以下の3つの役割があります：

• 各分岐で異なるインデックスを使用してクエリを高速化できるようにします。

  以下の例のように、クエリQ1はQ2の形式に書き換えられます。Q2では述語LNNVL(t1.a = 1)により、2つのサブクエリが重複した結果を生成しないように保証されています。書き換えを行わない場合、Q1は一般的に主テーブルをアクセスパスとして選択します。Q2については、t1テーブルにインデックス(a)とインデックス(b)の両方が存在する場合、この書き換えによりQ2内の各サブクエリがインデックスをアクセスパスとして選択する可能性があります。

  Q1:
  obclient> SELECT * FROM t1 WHERE t1.a = 1 OR t1.b = 1;
  Q2:
  obclient> SELECT * FROM t1 WHERE t1.a = 1 UNION ALL SELECT * FROM t1.b = 1
         AND LNNVL(t1.a = 1);
  

  完全な例は以下のとおりです：

  obclient> CREATE TABLE t1(a INT, b INT, c INT, d INT, e INT, INDEX IDX_a(a), INDEX IDX_b(b));
  Query OK, 0 rows affected
  
  /* OR-EXPANSIONによる書き換えを行わない場合、このクエリは主テーブルのアクセスパスしか使用できません */
  obclient> EXPLAIN SELECT/*+NO_REWRITE()*/ * FROM t1 WHERE t1.a = 1 OR t1.b = 1;
  +--------------------------------------------------------------+
  | Query Plan                                                                         |
  +--------------------------------------------------------------+
  | ===================================
  |ID|OPERATOR  |NAME|EST. ROWS|COST|
  -----------------------------------
  |0 |TABLE SCAN|t1  |4        |649 |
  ===================================
  
  Outputs & filters:
  -------------------------------------
    0 - output([t1.a], [t1.b], [t1.c], [t1.d], [t1.e]), filter([t1.a = 1 OR t1.b = 1]),
        access([t1.a], [t1.b], [t1.c], [t1.d], [t1.e]), partitions(p0)
  
  /* 書き換え後、各サブクエリは異なるインデックスのアクセスパスを使用できます */
  obclient>EXPLAIN SELECT * FROM t1 WHERE t1.a = 1 OR t1.b = 1;
  +------------------------------------------------------------------------+
  | Query Plan                                                                                         |
  +------------------------------------------------------------------------+
  | =========================================
  |ID|OPERATOR   |NAME     |EST. ROWS|COST|
  -----------------------------------------
  |0 |UNION ALL  |         |3        |190 |
  |1 | TABLE SCAN|t1(idx_a)|2        |94  |
  |2 | TABLE SCAN|t1(idx_b)|1        |95  |
  =========================================
  
  Outputs & filters:
  -------------------------------------
    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)
    1 - output([t1.a], [t1.b], [t1.c], [t1.d], [t1.e]), filter(nil),
        access([t1.a], [t1.b], [t1.c], [t1.d], [t1.e]), partitions(p0)
    2 - output([t1.a], [t1.b], [t1.c], [t1.d], [t1.e]), filter([lnnvl(t1.a = 1)]),
        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を選択できるため、より多くの最適化の余地が生まれます。

  Q1:
  obclient> SELECT * FROM t1, t2 WHERE t1.a = t2.a OR t1.b = t2.b;
  
  Q2:
  obclient> SELECT * FROM t1, t2 WHERE t1.a = t2.a UNION ALL
       SELECT * FROM t1, t2 WHERE t1.b = t2.b AND LNNVL(t1.a = t2.a);
  

  完全な例は以下のとおりです：

  obclient> CREATE TABLE t1(a INT, b INT);
  Query OK, 0 rows affected
  
  obclient> CREATE TABLE t2(a INT, b INT);
  Query OK, 0 rows affected
  
  /* 書き換えを行わない場合、Nested Loop Joinしか使用できません */
  obclient> EXPLAIN SELECT/*+NO_REWRITE()*/ * FROM t1, t2
         WHERE t1.a = t2.a OR t1.b = t2.b;
  +--------------------------------------------------------------------------+
  | Query Plan                                                                                          |
  +--------------------------------------------------------------------------+
  | ===========================================
  |ID|OPERATOR        |NAME|EST. ROWS|COST  |
  -------------------------------------------
  |0 |NESTED-LOOP JOIN|    |3957     |585457|
  |1 | TABLE SCAN     |t1  |1000     |499   |
  |2 | TABLE SCAN     |t2  |4        |583   |
  ===========================================
  
  Outputs & filters:
  -------------------------------------
    0 - output([t1.a], [t1.b], [t2.a], [t2.b]), filter(nil),
        conds(nil), nl_params_([t1.a], [t1.b])
    1 - output([t1.a], [t1.b]), filter(nil),
        access([t1.a], [t1.b]), partitions(p0)
    2 - output([t2.a], [t2.b]), filter([? = t2.a OR ? = t2.b]),
        access([t2.a], [t2.b]), partitions(p0)
  
  /* 書き換え後、各サブクエリはHash Joinを使用しています */
  obclient>  EXPLAIN SELECT * FROM t1, t2 WHERE t1.a = t2.a OR t1.b = t2.b;
  +--------------------------------------------------------------------------+
  | Query Plan                                                                                         |
  +--------------------------------------------------------------------------+
  |ID|OPERATOR    |NAME|EST. ROWS|COST|
  -------------------------------------
  |0 |UNION ALL   |    |2970     |9105|
  |1 | HASH JOIN  |    |1980     |3997|
  |2 |  TABLE SCAN|t1  |1000     |499 |
  |3 |  TABLE SCAN|t2  |1000     |499 |
  |4 | HASH JOIN  |    |990      |3659|
  |5 |  TABLE SCAN|t1  |1000     |499 |
  |6 |  TABLE SCAN|t2  |1000     |499 |
  =====================================
  
  Outputs & filters:
  -------------------------------------
    0 - output([UNION(t1.a, t1.a)], [UNION(t1.b, t1.b)], [UNION(t2.a, t2.a)], [UNION(t2.b, t2.b)]), filter(nil)
    1 - output([t1.a], [t1.b], [t2.a], [t2.b]), filter(nil),
        equal_conds([t1.a = t2.a]), other_conds(nil)
    2 - output([t1.a], [t1.b]), filter(nil),
        access([t1.a], [t1.b]), partitions(p0)
    3 - output([t2.a], [t2.b]), filter(nil),
        access([t2.a], [t2.b]), partitions(p0)
    4 - output([t1.a], [t1.b], [t2.a], [t2.b]), filter(nil),
        equal_conds([t1.b = t2.b]), other_conds([lnnvl(t1.a = t2.a)])
    5 - output([t1.a], [t1.b]), filter(nil),
        access([t1.a], [t1.b]), partitions(p0)
    6 - output([t2.a], [t2.b]), filter(nil),
        access([t2.a], [t2.b]), partitions(p0)
  

• 各分岐で個別にソートを排除し、より迅速にTOP-K結果を取得できるようにします。

  以下の例のように、クエリQ1はQ2に書き換えられます。Q1については、実行方法は条件を満たす行数を見つけ出してからソートし、最終的にTOP-10結果を取得することしかできません。Q2については、インデックス(a,b)が存在する場合、Q2内の2つのサブクエリはインデックスを使用してソートを排除でき、各サブクエリがTOP-10結果を取得し、最終的にこの20行のデータを一度ソートして最終的なTOP-10行を取得します。

  Q1:
  obclient> SELECT * FROM t1 WHERE t1.a = 1 OR t1.a = 2 ORDER BY b LIMIT 10;
  
  Q2:
  obclient> SELECT * FROM
      (SELECT * FROM  t1 WHERE t1.a = 1 ORDER BY b LIMIT 10 UNION ALL
       SELECT * FROM  t1 WHERE t1.a = 2 ORDER BY b LIMIT 10) AS TEMP
      ORDER BY temp.b LIMIT 10;
  

  完全な例は以下のとおりです：

  obclient> CREATE TABLE t1(a INT, b INT, INDEX IDX_a(a, b));
  Query OK, 0 rows affected
  
  /* 書き換えを行わない場合、ソートして最終的にTOP-K結果を取得する必要があります */
  obclient> EXPLAIN SELECT/*+NO_REWRITE()*/ * FROM t1 WHERE t1.a = 1 OR t1.a = 2 ORDER BY b LIMIT 10;
  +-------------------------------------------------------------------------+
  | Query Plan                                                                                         |
  +-------------------------------------------------------------------------+
  | ===========================================
  |ID|OPERATOR    |NAME     |EST. ROWS|COST|
  ------------------------------------------
  |0 |LIMIT       |         |4        |77  |
  |1 | TOP-N SORT |         |4        |76  |
  |2 |  TABLE SCAN|t1(idx_a)|4        |73  |
  ==========================================
  
  Outputs & filters:
  -------------------------------------
    0 - output([t1.a], [t1.b]), filter(nil), limit(10), offset(nil)
    1 - output([t1.a], [t1.b]), filter(nil), sort_keys([t1.b, ASC]), topn(10)
    2 - output([t1.a], [t1.b]), filter(nil),
        access([t1.a], [t1.b]), partitions(p0)
  
  /* 書き換えを行うと、ソート演算子を排除して最終的にTOP-K結果を取得できます */
  obclient>EXPLAIN SELECT * FROM t1 WHERE t1.a = 1 OR t1.a = 2
          ORDER BY b LIMIT 10;
  +-------------------------------------------------------------------------+
  | Query Plan                                                                                          |
  +-------------------------------------------------------------------------+
  | ===========================================
  |ID|OPERATOR     |NAME     |EST. ROWS|COST|
  -------------------------------------------
  |0 |LIMIT        |         |3        |76  |
  |1 | TOP-N SORT  |         |3        |76  |
  |2 |  UNION ALL  |         |3        |74  |
  |3 |   TABLE SCAN|t1(idx_a)|2        |37  |
  |4 |   TABLE SCAN|t1(idx_a)|1        |37  |
  ===========================================
  
  Outputs & filters:
  -------------------------------------
    0 - output([UNION(t1.a, t1.a)], [UNION(t1.b, t1.b)]), filter(nil), limit(10), offset(nil)
    1 - output([UNION(t1.a, t1.a)], [UNION(t1.b, t1.b)]), filter(nil), sort_keys([UNION(t1.b, t1.b), ASC]), topn(10)
    2 - output([UNION(t1.a, t1.a)], [UNION(t1.b, t1.b)]), filter(nil)
    3 - output([t1.a], [t1.b]), filter(nil),
        access([t1.a], [t1.b]), partitions(p0),
        limit(10), offset(nil)
    4 - output([t1.a], [t1.b]), filter([lnnvl(t1.a = 1)]),
        access([t1.a], [t1.b]), partitions(p0),
        limit(10), offset(nil)