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

Left Deep Join Treeについて考えるブログの第二回です。
前回はこちら

Left Deep と Bushy

前回、複数のテーブルの結合順には複数の選択肢が考えられるというところで終わりました。
この結合順は論理実行計画では木構造で表されているので、木の形＝結合順になります。Left DeepやBushyというのはその木の形を表しています。

• Left DeepはJOINの右側が必ずテーブルになるような構造を表しています。上の例のように、JOINの子供が２つともJOINだったりすることないという構造です。
• 逆に左側が必ずテーブルになるような構造をRight Deepと呼びます。
• そういった制限のない、両側がJOINでも構わない構造をBushyと呼びます。

このように分類します。Bushyに制限を加えたのがLeft DeepやRight Deepなわけですから、当然Bushyの中にはLeft DeepやRight Deepも含まれています。

Left Deep(Right Deep)の良い点は木の形が一意に定まるというところです。JOINの右側は必ずテーブルでJOINを含まないため、最初に2つのテーブルをJOINして、次にその結果と別の1つのテーブルをJOINして・・・という形で、ボトムアップに構築し全部のテーブルを使い切ったら自動的にLeft Deepな構造になります。

検索効率のよい結合順を考える上ではBushyの構造をすべて洗い出し、どれが一番効率が良いか（コストが低いか）を考える必要がありそうですが、System RではLeft Deepのみを考えており、TiDBもそれに倣っています。

数え上げの比較

Left Deepのみを考えることで、どのくらい組み合わせの候補が減るのでしょうか。結合するテーブルの組み合わせを考えます。先の例、A〜Eの５つのテーブルを結合するケースを考えます。

Left Deepは木の形は一意に定まりますから、A〜Eのすべての組み合わせを考えれば良いです。したがって、5! になります。

Bushyの場合はどうでしょうか。A〜Eのすべての組み合わせを考えるのはどんな木の形であれ同じですから、 木のパターン数*5! ということになりそうです。木のパターンは、根(Root)の一つ下だけを考えても、５つのテーブルの分け方として [1,4],[2,3],[3,2],[4,1] の4通りがあります。これが更に再帰的に分かれていくので、漸化式で

$$T(n) = \begin{cases} 1 & \text{if } n = 1 \\ \sum_{i=1}^{n-1} T(i) \cdot T(n-i) & \text{if } n > 1 \end{cases}$$

と表せます。これはカタラン数と呼ばれています。n=5のとき、14になります。

そんなに大きく思えないかもしれませんが、階乗もカタラン数も急速に増加します。計算してみます。

left_deep.py

import math
import pandas as pd

# 階乗の計算
def factorial(n):
    return math.factorial(n)

# カタラン数の計算
def catalan(n):
    return 1 if n == 1 else sum([catalan(i)*catalan(n-i) for i in range(1,n)])

# 1から10までのLeft Deep TreeとBushy Treeの比較
data = {
    "Num Of Table": list(range(1, 11)),
    "Left Deep": [factorial(i) for i in range(1, 11)],
    "Bushy": [catalan(i)*factorial(i) for i in range(1, 11)]
}

# データを表形式で表示
df = pd.DataFrame(data).set_index("Num Of Table")
print(df.map("{:,}".format))

結果は

              Left Deep           Bushy
Num Of Table
1                     1               1
2                     2               2
3                     6              12
4                    24             120
5                   120           1,680
6                   720          30,240
7                 5,040         665,280
8                40,320      17,297,280
9               362,880     518,918,400
10            3,628,800  17,643,225,600

テーブル数5あたりから顕著に違いが出てきます。

Left Deep vs Right Deep

このようにLeft DeepとBushyはテーブル数が多くなればなるほど大きな差が出ることが分かったのですが、組み合わせの数が同じであるLeft DeepとRight Deepに優劣はあるのでしょうか？

左側のテーブルを駆動表として結合するというルールにした場合に、Left Deepの場合は常に結合後のデータが駆動表になるのに対して、Right Deepの場合は駆動表が毎回変わる（＝メモリの入れ替えが発生する）というような違いが出てきます。

Left Deepのみを考える方針は、主に可能な組み合わせの数を減らすという観点と、実装上のメリットの２つの面から来ていると言えます。

次回

次回は、Left Deepの論理実行計画を作るアルゴリズムのうち、TiDBでメインで使われているGreedyアルゴリズムについて見ていきます。次回からはソースも見ていきます。