TiDBソースコード輪読会補遺: Left Deep Join Tree(1)

TiDBソースコード輪読会でよくわからなかったところをちゃんと考えるシリーズをやっていきます！
最初はLeft Deep Join Tree。 最初に見た時、次のような疑問を抱きました。

• 最適化の中での位置づけ(System R???)
• Bushy Treeとの違いがよくわからない（どんだけ違うの）
• Right Deepでも計算量は一緒では？

こういった疑問について、理解していったことを記載していこうと思います。

最初に: なぜ木(Tree)の話になっているのか

データベースでは、ユーザーが入力したSQLを解析し、それを実際に検索するための一連の演算を考えます。これを実行計画と呼びますが、これが木構造になっているのです。具体例を考えてみます。

次のようなSQLを入力にしたとします。

SELECT e.id, e.name, s.salary
FROM employees e JOIN salaries s ON e.id = s.emp_id
WHERE s.salary > 5000000

これを実際にデータベースから検索するときに、下記の演算が必要です

• テーブルからレコードを取得する
• JOINを行う
• WHERE条件でレコードを選択する (Selection)
• 出力列を絞る (Projection)

これを次のような形で表します。大文字の英単語が演算です。

       PROJECTION(e.id, e.name, s.salary)
               |
        SELECTION(s.salary > 5000000)
               |
       JOIN(e.id = s.emp_id)
          /           \
  employees         salary

これを論理実行計画（Logical Query Plan、ソースコード中ではLogicalPlan)と呼んでいます。

ところで、実際にこのSQLの実行計画（EXPLAINで見えるもの）を確認しておきましょう。(※テーブル名やカラム名は実際のテーブル名に修正しました）

TiDBの場合、出力結果が横に長くなるので、PAGER LESS -S としておくと見やすくなります。

EXPLAIN SELECT e.emp_no, e.first_name, s.salary FROM employees e JOIN salaries s ON e.emp_no = s.emp_no WHERE s.salary > 5000000;

+--------------------------------+------------+-----------+---------------+-------------------------------------------------------------------------->
| id                             | estRows    | task      | access object | operator info                                                            >
+--------------------------------+------------+-----------+---------------+-------------------------------------------------------------------------->
| Projection_10                  | 0.00       | root      |               | employees.employees.emp_no, employees.employees.first_name, employees.sal>
| └─IndexJoin_16                 | 0.00       | root      |               | inner join, inner:TableReader_13, outer key:employees.salaries.emp_no, in>
|   ├─TableReader_41(Build)      | 0.00       | root      |               | data:Selection_40                                                        >
|   │ └─Selection_40             | 0.00       | cop[tikv] |               | gt(employees.salaries.salary, 5000000)                                   >
|   │   └─TableFullScan_39       | 3998061.00 | cop[tikv] | table:s       | keep order:false                                                         >
|   └─TableReader_13(Probe)      | 0.00       | root      |               | data:TableRangeScan_12                                                   >
|     └─TableRangeScan_12        | 0.00       | cop[tikv] | table:e       | range: decided by [employees.salaries.emp_no], keep order:false          >
+--------------------------------+------------+-----------+---------------+-------------------------------------------------------------------------->

似ているようで結構違います。違いは、

• JOINの方法が指定されている (IndexJoin)
• SELECTIONがJOINの上ではなく下で実行されている
• テーブルの結合順（salariesが主(Build)でemployeesが子(Probe))が指定されている

などですが、これら実装の選択肢は様々あることが想像できます。例として、WHERE句の5000000の部分を色々変えてみてください。SELECTIONだけではなく、JOINも変わるのが見て取れます。

このように、実行する上で効率が良くなるように実行順を検討して変更していくプロセスを（クエリ）最適化と呼んでいて、この過程で先程のLogical Plan TreeがEXPLAINのような実行計画（実際はこれはPhysical Plan Treeです）に変換されていきます。

System Rとの関連は？

TiDBの中でこの最適化を行っているのがプランナーと呼ばれるコンポーネントで、そこではSystem Rの最適化法を参考にしていると表明しています。(https://zenn.dev/articles/8eb4bf2a50d7a3 参照)

System RはIBMのデータベースで、SQLを初めて実装したと言われています。このシステムの中ではテーブルの統計情報を利用したコストベースの最適化手法が使われており、この類似手法がTiDBを含め様々なデータベースでも使われている、という背景です。

コストベース とは何を意味しているのでしょうか。これは演算の実行に複数の選択肢があるときに、事前に取得してあるなんらかの情報を元に、演算の実行コスト（≒処理にかかるであろう時間）を計算して、その情報を元に選択するということを意味しています。

例えばテーブルの行数や結合したときの結果行数が推定できれば、どちらのテーブルを主表にするか、JOINのアルゴリズムをなんにするかといった手がかりになります。このような事前に収集しておく情報を統計情報と呼んでいます。

輪読会で話題にしているSystem Rの最適化手法は、主にテーブルの結合順序に関するものです。上記の例ではテーブルが２つと少ないので、どちらを主にするかくらいしか選択肢がありませんでしたが、例えば[A,B,C,D,E]の５つのテーブルをJOINするとき、どのようにJOINするのが良いのでしょうか？

JOIN                             JOIN                             JOIN
├── JOIN                         ├── JOIN                         ├── JOIN 
│   ├── JOIN                     │   ├── A                        │   ├── A
│   │   ├── A                    │   └── B                        │   └── B
│   │   └── B                    └── JOIN                         └── JOIN
│   └── C                             ├── JOIN                         ├── C
└── JOIN                              │   ├── C                        └── JOIN
    ├── D                             │   └── D                            ├── D
    └── E                             └── E                                └── E

まず論理実行計画を作る段階で、複数の選択肢があるのがわかると思います。全部の選択肢を虱潰しに調査するのか、なんらかの基準で選ぶのか。そこにLeft Deep Plan Treeという話が関係してきます。

このテーブルの並び順の検討を、TiDBの最適化では Join Reorder と呼んでいます

というところで次回に続きます。

参考文献

1. kumagiさんのスライド https://www.docswell.com/s/kumagi/KENNPE-selinger-optimizer
2. Query Optimizer Implementation 1 (CMU Advanced Database Systems)
3. Database System Implementation Chapter 7: The Query Compiler