SQLite で1行だけ加えてインデックスを作ることで数百倍高速化する例

# 問題設定

根付き木を考える。
この木のノード (頂点) は、親ノード (根には無い) と、値をもつ。
この木の中のノード1個を指定して、そのノードを根とするサブツリーに含まれるノードの値の合計を求める。

以下の図は、今回扱う木の例である。
丸がノードを、丸から出ている矢印が指す先のノードが親ノード、丸に書かれた数値が値である。
たとえば、赤いノード (値15) を指定したとき、そのノードを根とするサブツリーに含まれるノードは赤いノードとオレンジのノードであり、その値の合計は $15+63+6+91+29=204$ である。

![木の例](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/d4206602-9ac6-c145-5f8e-79f40dcc66da.png)

# 実装

今回用意した問題を、SQLite で表現した。
また、SQLite の呼び出しには Python を用いた。

## ノードを格納するテーブルの作成

ノードのID `id`、親ノードのID `parent`、値 `value` を格納するテーブルを作成する。

```sql
CREATE TABLE nodes(
    id INTEGER NOT NULL PRIMARY KEY,
    parent INTEGER,
    value INTEGER NOT NULL
) STRICT
```

## ノードの作成

まず、親ノードを持たない (すなわち、`parent` が `NULL` である) 根ノードを作成する。

```python
db.execute(
    "INSERT INTO nodes (id, value) VALUES (0, ?)",
    (rng.randrange(1000), )
)
```

残りのノードを作成する。
作成するノードの親ノードは、これまでに作成したノードの中からランダムに選ぶ。

```python
for i in range(1, node_num):
    db.execute(
        "INSERT INTO nodes (id, parent, value) VALUES (?, ?, ?)",
        (i, rng.randrange(i), rng.randrange(1000))
    )
```

## クエリの実行

再帰SQLを用いて指定したノードを根とするサブツリーに含まれるノードを列挙し、それらの値の合計を求める。
ノードの列挙は、以下の手順で行う。

1. 根となるノードを結果に加える
2. 前回のステップで結果に加えたノードのいずれかを親とするノードを結果に加える
3. 結果に加えるノードが無くなるまで、2 を繰り返す

```sql
WITH RECURSIVE decendents (id, value) AS (
    SELECT id, value FROM nodes WHERE id = ?
    UNION ALL
    SELECT nodes.id, nodes.value
        FROM nodes
        INNER JOIN decendents ON decendents.id = nodes.parent
)
SELECT SUM(value) FROM decendents
```

再帰SQLについて詳しくは、以下のページなどが参考になる。

[再帰SQL -図解- #Database - Qiita](https://qiita.com/Shoyu_N/items/f1786f99545fa5053b75)

## インデックスの作成

今回は指定のノードを親ノードとするノードを検索したいので、親ノードを表す列 `parent` に対してインデックスを作成する。

```sql
CREATE INDEX parent_index ON nodes (parent)
```

# コード全体

乱数系列を固定し、同じパラメータであれば処理内容が同じになるようにした。
[`time.perf_counter()`](https://docs.python.org/ja/3.7/library/time.html#time.perf_counter) を用いてノードの作成およびクエリの実行にかかった時間を計測した。
(参考：[[Python][Tips] 処理時間の計測 #Python3 - Qiita](https://qiita.com/pepe_nari/items/5fbcecdd4bb1ab75f685))

```python
import random
import sqlite3
import sys
import time

def test(use_index, node_num, query_num):
    rng = random.Random(3141592)
    db = sqlite3.connect(":memory:")

    db.execute("""
        CREATE TABLE nodes(
            id INTEGER NOT NULL PRIMARY KEY,
            parent INTEGER,
            value INTEGER NOT NULL
        ) STRICT
    """)
    if use_index:
        print("using index")
        db.execute("CREATE INDEX parent_index ON nodes (parent)")
    else:
        print("not using index")

    start_time = time.perf_counter()

    db.execute(
        "INSERT INTO nodes (id, value) VALUES (0, ?)",
        (rng.randrange(1000), )
    )
    for i in range(1, node_num):
        db.execute(
            "INSERT INTO nodes (id, parent, value) VALUES (?, ?, ?)",
            (i, rng.randrange(i), rng.randrange(1000))
        )

    insert_end_time = time.perf_counter()

    all_sum = 0
    for _ in range(query_num):
        res = db.execute(
            """
                WITH RECURSIVE decendents (id, value) AS (
                    SELECT id, value FROM nodes WHERE id = ?
                    UNION ALL
                    SELECT nodes.id, nodes.value
                        FROM nodes
                        INNER JOIN decendents ON decendents.id = nodes.parent
                )
                SELECT SUM(value) FROM decendents
            """,
            (rng.randrange(node_num), )
        )
        res_row = res.fetchone()
        all_sum += res_row[0]

    query_end_time = time.perf_counter()

    print("sum = " + str(all_sum))
    print("insert time = " + str(insert_end_time - start_time) + " sec.")
    print("query time = " + str(query_end_time - insert_end_time) + " sec.")
    print("total time = " + str(query_end_time - start_time) + " sec.")

node_num = int(sys.argv[1]) if len(sys.argv) > 1 else 10000
query_num = int(sys.argv[2]) if len(sys.argv) > 2 else node_num

test(True, node_num, query_num)
test(False, node_num, query_num)
```

# 実行結果

クエリを実行する回数はノードの数によらず 10,000 回で固定し、作成するノードの数を変えて実行した。
以下に、それぞれの処理にかかった時間 [ms] を示す。
測定はそれぞれ5回行い、平均をとった。

|ノード数|ｲﾝﾃﾞｯｸｽあり<br>ノード作成|ｲﾝﾃﾞｯｸｽあり<br>クエリ実行|ｲﾝﾃﾞｯｸｽなし<br>ノード作成|ｲﾝﾃﾞｯｸｽなし<br>クエリ実行|
|--:|--:|--:|--:|--:|
| 1000| 1.500|61.847| 1.302| 2250.769|
| 2000| 3.179|62.895| 2.397| 5097.825|
| 3000| 4.610|69.825| 3.771| 8241.450|
| 4000| 6.286|73.178| 4.875|11370.362|
| 5000| 7.923|76.783| 6.146|14641.931|
| 6000| 9.481|80.560| 7.651|17587.348|
| 7000|11.966|86.474| 8.704|20948.993|
| 8000|12.780|90.250| 9.680|24705.844|
| 9000|14.302|87.841|10.993|27794.540|
|10000|15.784|90.407|11.942|30919.401|

## ノードの作成にかかった時間の比較

ノード数にかかわらず、インデックスありでの処理のほうがインデックスなしでの処理よりも長時間かかった。

![ノードの作成にかかった時間のグラフ](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/a9006e2f-b8e9-4992-412a-b8fe7bcd9f53.png)

インデックスありでの処理時間をインデックスなしでの処理時間で割った比を求めてみると、どのノード数でもだいたいインデックスありでの処理にはインデックスなしでの処理の**約1.3倍**の時間がかかっていることがわかった。

![ノードの作成にかかった時間の比のグラフ](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/6d6e6ac7-6698-2325-edb3-2b77d2d5f294.png)

## クエリの実行にかかった時間の比較

インデックスなしの処理はインデックスありの処理に比べて**圧倒的**に長時間かかり、かかる時間はノード数が増えるにつれてどんどん長くなっていった。

![クエリの実行にかかった時間のグラフ](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/1e344255-27ef-9dee-b7dd-b561179daa11.png)

インデックスありの処理にかかる時間もノード数が増えるにつれて長くなる傾向にあるが、その増え方はインデックスなしの処理に比べて穏やかである。

![クエリの実行にかかった時間のグラフ (インデックスありのみ)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/9794db31-6e54-76ca-f647-ba24ce85e1a3.png)

インデックスなしでの処理時間をインデックスありでの処理時間で割った比 (長い方を割られる数にするため、ノードの作成にかかった時間の比とは逆である) を求めてみると、これもまたノード数が増えるにつれてどんどん大きくなっていった。

![クエリの実行にかかった時間の比のグラフ](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/ea0e82c8-b717-f2af-7fc0-a196b860795e.png)

# 結論

今回の問題設定と実装では、インデックスを作ったときは、作っていないときに比べてノードの作成のコストは**約1.3倍と大きくなる**が、そのかわりクエリの実行のコストは数十～数百分の1と**大幅に小さくなる**ことがわかった。
ノードの作成や更新の回数に比べて参照の回数が十分多い場合は、参照時に「この列が特定の値である行が欲しい」となる列のインデックスを作っておくことで、処理の効率を上げる効果が期待できる。

# おまけ

「SQLite インデックス」でググったら出てきた先行研究。より単純な例を扱っている。

[DBにインデックスを貼るとどれくらい速くなるのか #SQL - Qiita](https://qiita.com/T45K/items/faad11c65473cb55da5d)

# 蛇足

インデックスが**CV：井口裕香**だという噂があったかもしれない…？
井口裕香といえば、柳冨美子役、園田優役、ミミ・ウリエ・フォン・シュヴァルツラング役などがあるよね…。