SQLite3 で EAV を使うとどのくらい効率が落ちるか実験してみた

# はじめに

リレーショナルデータベースにおいて、プロパティの名前と値の組をテーブルに格納するのは **EAV (Entity-Atribute-Value)** というアンチパターンであることを学んだ。

[SQLアンチパターン勉強会　第五回：EAV(エンティティ・アトリビュート・バリュー) #SQLServer - Qiita](https://qiita.com/skyc_lin/items/37365a36416d0dc42431)

そこで、具体的にどの程度効率が悪くなるのか実験してみた。

# 実験

今回は、「整数値のうち、関連付けられたチェック対象のプロパティがすべて0であるものの和を求める」クエリを実行し、それにかかる時間を測定した。
以下の4種類の実装を用意した。

* 単一テーブル
* プロパティごとのテーブル
* EAV (サブクエリ)
* EAV (ANDを用いたJOIN)

## 実装

### normal：単一テーブル

以下のテーブルを扱う。

```sql
CREATE TABLE test (
    id INTEGER NOT NULL PRIMARY KEY,
    value INTEGER NOT NULL,
    param1 INTEGER,
    param2 INTEGER,
    param3 INTEGER
) STRICT
```

以下のようにして和を求める。

```sql
SELECT SUM(value) AS s
FROM test
WHERE param1=0 AND param2=0
```

<details><summary>コード全体</summary>

```python:normal.py
import sqlite3
import random
import time

num_rows = 10000000
param1_prob = 0.7
param2_prob = 0.7
param3_prob = 0.7

random.seed(998244353)

print("SQLite version = " +  sqlite3.sqlite_version)
con = sqlite3.connect(":memory:")
cur = con.cursor()

print("inserting data")
start_time = time.monotonic_ns()
cur.execute("""
    CREATE TABLE test (
        id INTEGER NOT NULL PRIMARY KEY,
        value INTEGER NOT NULL,
        param1 INTEGER,
        param2 INTEGER,
        param3 INTEGER
    ) STRICT
""")

for i in range(num_rows):
    value = random.randrange(1 << 32)
    param1 = None
    param2 = None
    param3 = None
    if random.random() < param1_prob:
        param1 = random.randrange(2)
    if random.random() < param2_prob:
        param2 = random.randrange(2)
    if random.random() < param3_prob:
        param3 = random.randrange(2)
    cur.execute("""
        INSERT INTO test (id, value, param1, param2, param3) VALUES (?, ?, ?, ?, ?)
    """, (i, value, param1, param2, param3))

con.commit()
end_time = time.monotonic_ns()
print("time = %d ms" % ((end_time - start_time) // 1000000))

print("0 params")
start_time = time.monotonic_ns()
res = con.execute("""
    SELECT SUM(value) AS s
    FROM test
""")
result = res.fetchone()
end_time = time.monotonic_ns()

print("result = " + str(result))
print("time = %d ms" % ((end_time - start_time) // 1000000))

print("1 param")
start_time = time.monotonic_ns()
res = con.execute("""
    SELECT SUM(value) AS s
    FROM test
    WHERE param1=0
""")
result = res.fetchone()
end_time = time.monotonic_ns()

print("result = " + str(result))
print("time = %d ms" % ((end_time - start_time) // 1000000))

print("2 params")
start_time = time.monotonic_ns()
res = con.execute("""
    SELECT SUM(value) AS s
    FROM test
    WHERE param1=0 AND param2=0
""")
result = res.fetchone()
end_time = time.monotonic_ns()

print("result = " + str(result))
print("time = %d ms" % ((end_time - start_time) // 1000000))

print("3 params")
start_time = time.monotonic_ns()
res = con.execute("""
    SELECT SUM(value) AS s
    FROM test
    WHERE param1=0 AND param2=0 AND param3=0
""")
result = res.fetchone()
end_time = time.monotonic_ns()

print("result = " + str(result))
print("time = %d ms" % ((end_time - start_time) // 1000000))
```

</details>

### tables：プロパティごとのテーブル

以下のテーブルを扱う。

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

CREATE TABLE param1 (
    id INTEGER NOT NULL PRIMARY KEY,
    value INTEGER NOT NULL
) STRICT

CREATE TABLE param2 (
    id INTEGER NOT NULL PRIMARY KEY,
    value INTEGER NOT NULL
) STRICT

CREATE TABLE param3 (
    id INTEGER NOT NULL PRIMARY KEY,
    value INTEGER NOT NULL
) STRICT
```

以下のようにして和を求める。

```sql
SELECT SUM(test.value) AS s
FROM test
LEFT OUTER JOIN param1 ON test.id=param1.id
LEFT OUTER JOIN param2 ON test.id=param2.id
WHERE param1.value=0 AND param2.value=0
```

<details><summary>コード全体</summary>

```python:tables.py
import sqlite3
import random
import time

num_rows = 10000000
param1_prob = 0.7
param2_prob = 0.7
param3_prob = 0.7

random.seed(998244353)

print("SQLite version = " +  sqlite3.sqlite_version)
con = sqlite3.connect(":memory:")
cur = con.cursor()

print("inserting data")
start_time = time.monotonic_ns()
cur.execute("""
    CREATE TABLE test (
        id INTEGER NOT NULL PRIMARY KEY,
        value INTEGER NOT NULL
    ) STRICT
""")

cur.execute("""
    CREATE TABLE param1 (
        id INTEGER NOT NULL PRIMARY KEY,
        value INTEGER NOT NULL
    ) STRICT
""")

cur.execute("""
    CREATE TABLE param2 (
        id INTEGER NOT NULL PRIMARY KEY,
        value INTEGER NOT NULL
    ) STRICT
""")

cur.execute("""
    CREATE TABLE param3 (
        id INTEGER NOT NULL PRIMARY KEY,
        value INTEGER NOT NULL
    ) STRICT
""")

for i in range(num_rows):
    value = random.randrange(1 << 32)
    cur.execute("""
        INSERT INTO test (id, value) VALUES (?, ?)
    """, (i, value))
    if random.random() < param1_prob:
        param1 = random.randrange(2)
        cur.execute("""
            INSERT INTO param1 (id, value) VALUES (?, ?)
        """, (i, param1))
    if random.random() < param2_prob:
        param2 = random.randrange(2)
        cur.execute("""
            INSERT INTO param2 (id, value) VALUES (?, ?)
        """, (i, param2))
    if random.random() < param3_prob:
        param3 = random.randrange(2)
        cur.execute("""
            INSERT INTO param3 (id, value) VALUES (?, ?)
        """, (i, param3))

con.commit()
end_time = time.monotonic_ns()
print("time = %d ms" % ((end_time - start_time) // 1000000))

print("0 params")
start_time = time.monotonic_ns()
res = con.execute("""
    SELECT SUM(test.value) AS s
    FROM test
""")
result = res.fetchone()
end_time = time.monotonic_ns()

print("result = " + str(result))
print("time = %d ms" % ((end_time - start_time) // 1000000))

print("1 param")
start_time = time.monotonic_ns()
res = con.execute("""
    SELECT SUM(test.value) AS s
    FROM test
    LEFT OUTER JOIN param1 ON test.id=param1.id
    WHERE param1.value=0
""")
result = res.fetchone()
end_time = time.monotonic_ns()

print("result = " + str(result))
print("time = %d ms" % ((end_time - start_time) // 1000000))

print("2 params")
start_time = time.monotonic_ns()
res = con.execute("""
    SELECT SUM(test.value) AS s
    FROM test
    LEFT OUTER JOIN param1 ON test.id=param1.id
    LEFT OUTER JOIN param2 ON test.id=param2.id
    WHERE param1.value=0 AND param2.value=0
""")
result = res.fetchone()
end_time = time.monotonic_ns()

print("result = " + str(result))
print("time = %d ms" % ((end_time - start_time) // 1000000))

print("3 params")
start_time = time.monotonic_ns()
res = con.execute("""
    SELECT SUM(test.value) AS s
    FROM test
    LEFT OUTER JOIN param1 ON test.id=param1.id
    LEFT OUTER JOIN param2 ON test.id=param2.id
    LEFT OUTER JOIN param3 ON test.id=param3.id
    WHERE param1.value=0 AND param2.value=0 AND param3.value=0
""")
result = res.fetchone()
end_time = time.monotonic_ns()

print("result = " + str(result))
print("time = %d ms" % ((end_time - start_time) // 1000000))
```

</details>

### eav：EAV (サブクエリ)

以下のテーブルを扱う。

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

CREATE TABLE params (
    id INTEGER NOT NULL,
    name TEXT NOT NULL,
    value any,
    PRIMARY KEY(id, name)
) STRICT
```

以下のようにして和を求める。

```sql
SELECT SUM(test.value) AS s
FROM test
LEFT OUTER JOIN (SELECT * FROM params WHERE name='param1') AS param1 ON test.id=param1.id
LEFT OUTER JOIN (SELECT * FROM params WHERE name='param2') AS param2 ON test.id=param2.id
WHERE param1.value=0 AND param2.value=0
```

<details><summary>コード全体</summary>

```python:eav.py
import sqlite3
import random
import time

num_rows = 10000000
param1_prob = 0.7
param2_prob = 0.7
param3_prob = 0.7

random.seed(998244353)

print("SQLite version = " +  sqlite3.sqlite_version)
con = sqlite3.connect(":memory:")
cur = con.cursor()

print("inserting data")
start_time = time.monotonic_ns()
cur.execute("""
    CREATE TABLE test (
        id INTEGER NOT NULL PRIMARY KEY,
        value INTEGER NOT NULL
    ) STRICT
""")

cur.execute("""
    CREATE TABLE params (
        id INTEGER NOT NULL,
        name TEXT NOT NULL,
        value any,
        PRIMARY KEY(id, name)
    ) STRICT
""")

for i in range(num_rows):
    value = random.randrange(1 << 32)
    cur.execute("""
        INSERT INTO test (id, value) VALUES (?, ?)
    """, (i, value))
    if random.random() < param1_prob:
        param1 = random.randrange(2)
        cur.execute("""
            INSERT INTO params (id, name, value) VALUES (?, 'param1', ?)
        """, (i, param1))
    if random.random() < param2_prob:
        param2 = random.randrange(2)
        cur.execute("""
            INSERT INTO params (id, name, value) VALUES (?, 'param2', ?)
        """, (i, param2))
    if random.random() < param3_prob:
        param3 = random.randrange(2)
        cur.execute("""
            INSERT INTO params (id, name, value) VALUES (?, 'param3', ?)
        """, (i, param3))

con.commit()
end_time = time.monotonic_ns()
print("time = %d ms" % ((end_time - start_time) // 1000000))

print("0 params")
start_time = time.monotonic_ns()
res = con.execute("""
    SELECT SUM(test.value) AS s
    FROM test
""")
result = res.fetchone()
end_time = time.monotonic_ns()

print("result = " + str(result))
print("time = %d ms" % ((end_time - start_time) // 1000000))

print("1 param")
start_time = time.monotonic_ns()
res = con.execute("""
    SELECT SUM(test.value) AS s
    FROM test
    LEFT OUTER JOIN (SELECT * FROM params WHERE name='param1') AS param1 ON test.id=param1.id
    WHERE param1.value=0
""")
result = res.fetchone()
end_time = time.monotonic_ns()

print("result = " + str(result))
print("time = %d ms" % ((end_time - start_time) // 1000000))

print("2 params")
start_time = time.monotonic_ns()
res = con.execute("""
    SELECT SUM(test.value) AS s
    FROM test
    LEFT OUTER JOIN (SELECT * FROM params WHERE name='param1') AS param1 ON test.id=param1.id
    LEFT OUTER JOIN (SELECT * FROM params WHERE name='param2') AS param2 ON test.id=param2.id
    WHERE param1.value=0 AND param2.value=0
""")
result = res.fetchone()
end_time = time.monotonic_ns()

print("result = " + str(result))
print("time = %d ms" % ((end_time - start_time) // 1000000))

print("3 params")
start_time = time.monotonic_ns()
res = con.execute("""
    SELECT SUM(test.value) AS s
    FROM test
    LEFT OUTER JOIN (SELECT * FROM params WHERE name='param1') AS param1 ON test.id=param1.id
    LEFT OUTER JOIN (SELECT * FROM params WHERE name='param2') AS param2 ON test.id=param2.id
    LEFT OUTER JOIN (SELECT * FROM params WHERE name='param3') AS param3 ON test.id=param3.id
    WHERE param1.value=0 AND param2.value=0 AND param3.value=0
""")
result = res.fetchone()
end_time = time.monotonic_ns()

print("result = " + str(result))
print("time = %d ms" % ((end_time - start_time) // 1000000))
```

</details>

### eav2：EAV (ANDを用いたJOIN)

以下のテーブルを扱う。

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

CREATE TABLE params (
    id INTEGER NOT NULL,
    name TEXT NOT NULL,
    value any,
    PRIMARY KEY(id, name)
) STRICT
```

以下のようにして和を求める。

```sql
SELECT SUM(test.value) AS s
FROM test
LEFT OUTER JOIN params AS param1 ON test.id=param1.id AND param1.name='param1'
LEFT OUTER JOIN params AS param2 ON test.id=param2.id AND param2.name='param2'
WHERE param1.value=0 AND param2.value=0
```

<details><summary>コード全体</summary>

```python:eav2.py
import sqlite3
import random
import time

num_rows = 10000000
param1_prob = 0.7
param2_prob = 0.7
param3_prob = 0.7

random.seed(998244353)

print("SQLite version = " +  sqlite3.sqlite_version)
con = sqlite3.connect(":memory:")
cur = con.cursor()

print("inserting data")
start_time = time.monotonic_ns()
cur.execute("""
    CREATE TABLE test (
        id INTEGER NOT NULL PRIMARY KEY,
        value INTEGER NOT NULL
    ) STRICT
""")

cur.execute("""
    CREATE TABLE params (
        id INTEGER NOT NULL,
        name TEXT NOT NULL,
        value any,
        PRIMARY KEY(id, name)
    ) STRICT
""")

for i in range(num_rows):
    value = random.randrange(1 << 32)
    cur.execute("""
        INSERT INTO test (id, value) VALUES (?, ?)
    """, (i, value))
    if random.random() < param1_prob:
        param1 = random.randrange(2)
        cur.execute("""
            INSERT INTO params (id, name, value) VALUES (?, 'param1', ?)
        """, (i, param1))
    if random.random() < param2_prob:
        param2 = random.randrange(2)
        cur.execute("""
            INSERT INTO params (id, name, value) VALUES (?, 'param2', ?)
        """, (i, param2))
    if random.random() < param3_prob:
        param3 = random.randrange(2)
        cur.execute("""
            INSERT INTO params (id, name, value) VALUES (?, 'param3', ?)
        """, (i, param3))

con.commit()
end_time = time.monotonic_ns()
print("time = %d ms" % ((end_time - start_time) // 1000000))

print("0 params")
start_time = time.monotonic_ns()
res = con.execute("""
    SELECT SUM(test.value) AS s
    FROM test
""")
result = res.fetchone()
end_time = time.monotonic_ns()

print("result = " + str(result))
print("time = %d ms" % ((end_time - start_time) // 1000000))

print("1 param")
start_time = time.monotonic_ns()
res = con.execute("""
    SELECT SUM(test.value) AS s
    FROM test
    LEFT OUTER JOIN params AS param1 ON test.id=param1.id AND param1.name='param1'
    WHERE param1.value=0
""")
result = res.fetchone()
end_time = time.monotonic_ns()

print("result = " + str(result))
print("time = %d ms" % ((end_time - start_time) // 1000000))

print("2 params")
start_time = time.monotonic_ns()
res = con.execute("""
    SELECT SUM(test.value) AS s
    FROM test
    LEFT OUTER JOIN params AS param1 ON test.id=param1.id AND param1.name='param1'
    LEFT OUTER JOIN params AS param2 ON test.id=param2.id AND param2.name='param2'
    WHERE param1.value=0 AND param2.value=0
""")
result = res.fetchone()
end_time = time.monotonic_ns()

print("result = " + str(result))
print("time = %d ms" % ((end_time - start_time) // 1000000))

print("3 params")
start_time = time.monotonic_ns()
res = con.execute("""
    SELECT SUM(test.value) AS s
    FROM test
    LEFT OUTER JOIN params AS param1 ON test.id=param1.id AND param1.name='param1'
    LEFT OUTER JOIN params AS param2 ON test.id=param2.id AND param2.name='param2'
    LEFT OUTER JOIN params AS param3 ON test.id=param3.id AND param3.name='param3'
    WHERE param1.value=0 AND param2.value=0 AND param3.value=0
""")
result = res.fetchone()
end_time = time.monotonic_ns()

print("result = " + str(result))
print("time = %d ms" % ((end_time - start_time) // 1000000))
```

</details>

## 環境

* 13th Gen Intel(R) Core(TM) i7-13700H   2.40 GHz
* Windows 11 Home 23H2
* Python 3.11.4
* SQLite 3.42.0

## 結果

それぞれの実装において、データの挿入にかかった時間と、チェック対象のプロパティの数ごとの和を求めるクエリの実行にかかった時間 [ms] を示す。
これらは、それぞれ3回実行した平均である。

||insert|0 params|1 param|2 params|3 params|
|---|--:|--:|--:|--:|--:|
|normal|20552|255|297|323|329|
|tables|35463|255|537|791|938|
|eav|40354|261|1182|2104|2432|
|eav2|40234|250|1130|2036|2401|

![データ挿入にかかった時間](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/2deb62f6-dfa1-406d-47e9-8800d52c30d3.png)

![クエリにかかった時間](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/2d8a8209-29b6-4e6b-9260-f4f345cd3030.png)

### データ挿入

1個のテーブルにデータとプロパティを格納する場合 (normal) よりも、プロパティを別のテーブルに格納する場合 (tables・eav・eav2) のほうが、約2倍の時間がかかっている。
さらに、各プロパティをそれぞれ別のテーブルに格納する場合 (tables) より、1個のテーブルに名前付きで格納する場合 (eav・eav2) のほうが、多めに時間がかかっている。

:::note info
「データ挿入にかかる時間」には、Pythonのループ自体にかかる時間も含まれる。
Pythonのループにかかる時間とSQLiteの処理にかかる時間を分離したり、tables より eav・eav2 のほうが処理時間が長くなった原因を調べたりするには、さらに別の実験が必要だろう。
:::

### クエリ

1個のテーブルにデータとプロパティを格納している normal では、チェックするプロパティの数を増やしても実行時間の伸びは少なかった。

プロパティを個別のテーブルに格納し、JOIN を用いて結合しながら処理を行う tables では、チェックするプロパティの数を増やすと実行時間が長くなったが、その増え方は EAV を用いる場合よりは少なかった。
プロパティ3個をチェックする場合、実行時間は1個のテーブルに格納した場合の約3倍になった。

EAV を用いた場合、実行時間が大幅に長くなり、プロパティ3個をチェックする場合の実行時間は1個のテーブルに格納した場合の約8倍になった。
サブクエリを用いた eav とANDを用いた eav2 では、実行時間はあまり変わらなかった。

今回の実験の範囲では、どの方式でも、チェックするプロパティの数が多いほうがチェックするプロパティの数を増やしたときの実行時間の伸び方が少なくなっているようである。
これは、プロパティのチェックを進めると、その分条件を満たさずに消える行が増え、チェックを行う行が減っていくからであると予想できる。
少なくとも、[前述の記事](https://qiita.com/skyc_lin/items/37365a36416d0dc42431)にある

> 属性数の増加に伴い結合数が増加するため、クエリの実行コストも指数関数的に増加していきます。

という記述は、ここでは成り立っていないようである。

# 結論

今回の実験では、EAV を用いると、単にテーブルを分割して JOIN するよりも数倍効率が悪くなった。
決まったプロパティしか用いず、実行時に動的にプロパティを増やさないのであれば、EAV を用いる (プロパティの名前と値を組にして1個のテーブルで管理する) よりも、各プロパティ用のテーブルを作ったほうがマシになりそうである。
さらに、ALTER TABLE などを用いてもとのテーブルに列を追加できるのであれば、直接プロパティを追加して1個のテーブルで管理したほうがさらに効率が良くなりそうである。

これはあくまで今回の実験の結果であり、効率はデータベースの種類やバージョンによって変わる可能性がある。