はじめに

オークファンでは大量の商品データを扱っており、MySQL、PostgreSQL、SQL Server などの RDB や、検索・分析エンジンの Elasticsearch に格納して様々なサービスで利用しています。

サービスを提供しているシステムにおいて、大量の商品から特定のカテゴリの商品だけに絞り込んで検索するというユースケースは非常に多いです。ただ、このカテゴリというのが少しくせ者で、たいていの場合は Tree 構造 (たまに Graph 構造のことも) になっています。

ここで以下のようなカテゴリと、それらに所属する商品について考えてみます。

第 1 カテゴリ	第 2 カテゴリ	第 3 カテゴリ	商品
PC パーツ (ID: `10`)	CPU (ID: `100`)	Intel (ID: `1000`)	Core i9 Core i7
		AMD (ID: `1001`)	Ryzen9 Ryzen7
	GPU (ID: `101`)	NVIDIA (ID: `1002`)	GeForce RTX30 GeForce RTX20
		AMD (ID: `1001`)	Radeon RX6000 Radeon RX5000

たとえば第 2 カテゴリの CPU カテゴリで検索した場合は、そのすべての子カテゴリ Intel と AMD に所属する商品が取得されることが期待されます。

愚直に実装すると、指定された CPU カテゴリから所属するすべての末端カテゴリを取得し、その末端カテゴリで商品を検索するという方針になると思いますが、処理が煩雑になってしまうので、お手軽に実装できる方法を RDB と Elasticsearch それぞれでご紹介しようと思います。

RDB の場合

ここでは PostgreSQL で実装する想定とします。
具体的な実装方針としては、カテゴリパスを商品ごとに持たせ、そこに対する前方一致検索でカテゴリ検索を実現します。(教科書的には「経路列挙モデル」と呼ぶようです。)

まず商品テーブル (item) を作成します。category_path カラムに対する前方一致検索を実行するので、インデックスも作成しておきます。(ただし、今回の場合はデータ量が非常に少ないので PostgreSQL はインデックスを使うという判断をしてくれませんでした )

-- テーブルを作成
CREATE TABLE item (
	id bigserial PRIMARY KEY,
	name text,
	category_path text
);

-- インデックスを作成
CREATE INDEX item_category_path_idx ON item(category_path);

前述の例の商品レコードを登録します。
カテゴリパスの値は、例えば Core i9 と Core i7 の商品の場合は、

PC パーツ (ID: 10) → CPU (ID: 100) → Intel (ID: 1000)

となるので、その ID を . で結合して

.10.100.1000.

で表すこととします。

INSERT INTO item (name, category_path) VALUES 
('Core i9', '.10.100.1000.'),
('Core i7', '.10.100.1000.'),
('Ryzen9', '.10.100.1001.'),
('Ryzen7', '.10.100.1001.'),
('GeForce RTX30', '.10.101.1002.'),
('GeForce RTX20', '.10.101.1002.'),
('Radeon RX6000', '.10.101.1001.'),
('Radeon RX5000', '.10.101.1001.');

以下のように商品レコードが登録されます。

SELECT * FROM item;

 id |     name      | category_path
----+---------------+---------------
  1 | Core i9       | .10.100.1000.
  2 | Core i7       | .10.100.1000.
  3 | Ryzen9        | .10.100.1001.
  4 | Ryzen7        | .10.100.1001.
  5 | GeForce RTX30 | .10.101.1002.
  6 | GeForce RTX20 | .10.101.1002.
  7 | Radeon RX6000 | .10.101.1001.
  8 | Radeon RX5000 | .10.101.1001.
(8 行)

まず、今回の例でのルートカテゴリである PC パーツ (ID: 10) で検索してみます。
第 1 階層のみですので、その ID のみの .10. で前方一致検索を実行します。

SELECT * FROM item WHERE category_path LIKE '.10.%';

 id |     name      | category_path
----+---------------+---------------
  1 | Core i9       | .10.100.1000.
  2 | Core i7       | .10.100.1000.
  3 | Ryzen9        | .10.100.1001.
  4 | Ryzen7        | .10.100.1001.
  5 | GeForce RTX30 | .10.101.1002.
  6 | GeForce RTX20 | .10.101.1002.
  7 | Radeon RX6000 | .10.101.1001.
  8 | Radeon RX5000 | .10.101.1001.
(8 行)

登録した商品レコードすべてが取得できました。

次に、CPU (ID: 100) カテゴリで検索してみます。
CPU カテゴリのカテゴリパスの値は .10.100. となるので、こちらで前方一致検索を実行します。

SELECT * FROM item WHERE category_path LIKE '.10.100.%';

 id |  name   | category_path
----+---------+---------------
  1 | Core i9 | .10.100.1000.
  2 | Core i7 | .10.100.1000.
  3 | Ryzen9  | .10.100.1001.
  4 | Ryzen7  | .10.100.1001.
(4 行)

CPU が検索できました。

さらに、末端カテゴリの NVIDIA (ID: 1002) でも検索してみます。
この場合のカテゴリパスの値は .10.101.1002. です。

SELECT * FROM item WHERE category_path LIKE '.10.101.1002.%';

 id |     name      | category_path
----+---------------+---------------
  5 | GeForce RTX30 | .10.101.1002.
  6 | GeForce RTX20 | .10.101.1002.
(2 行)

NVIDIA の GPU が検索できました。

最後に、CPU と GPU 両方生産している AMD (ID: 1001) で検索してみます。ここで、CPU の場合と GPU の場合で AMD のカテゴリパスが異なっているので、.1002. 単体の部分一致検索を実行します。

SELECT * FROM item WHERE category_path LIKE '%.1001.%';

 id |     name      | category_path
----+---------------+---------------
  3 | Ryzen9        | .10.100.1001.
  4 | Ryzen7        | .10.100.1001.
  7 | Radeon RX6000 | .10.101.1001.
  8 | Radeon RX5000 | .10.101.1001.
(4 行)

AMD の CPU と GPU が検索できました。

しかしながら、今回 category_path に作成したインデックスでは、部分一致検索に使用できないので、必ずフルテーブルスキャンとなってしまい、商品レコードが増えた場合に著しい性能劣化が起こります。実運用のシステムではこのままでは使用しないほうがよいです。(商品レコードが少ない場合は前方一致検索でもフルテーブルスキャンが RDBMS によって選択される場合があります。)

Elasticsearch の場合

今度は Elasticsearch で同じことを実装してみます。ここではローカル (http://localhost:9200) で実行している Elasticsearch を使用する想定とします。(実運用では Kibana からコマンドを実行していますが、Kibana の説明をするのがめんどいのでw ここでは cURL でコマンドを実行します。)

まず商品インデックス (item) を作成します。category_path フィールドにカテゴリ ID のリストを登録する想定です。ここで、カテゴリ ID は文字列で登録する前提ですが、完全一致検索をする場合は type で keyword を指定してください。text にしてしまうと、インデックスに設定されている analyzer によって処理された結果がインデックスされ、想定していない挙動となることがあります。ここの場合ではデフォルトの standard analyzer が適用されます。

$ curl -X PUT 'http://localhost:9200/item?pretty' -H 'Content-Type: application/json' -d'
> {
>     "settings": {
>         "index": {
>             "number_of_shards": 1,
>             "number_of_replicas": 0
>         }
>     },
>     "mappings": {
>         "properties": {
>             "name": { "type": "text" },
>             "category_path": { "type": "keyword" }
>         }
>     }
> }
> '
{
  "acknowledged" : true,
  "shards_acknowledged" : true,
  "index" : "item"
}

item インデックスが作成されたことを確認しておきます。

$ curl 'http://localhost:9200/_cat/indices?v&s=index'
health status index uuid                   pri rep docs.count docs.deleted store.size pri.store.size
green  open   item  jZ7e8nKKRX6OHpXal_9Fxw   1   0          0            0       230b           230b

続いて、商品ドキュメントをインデックスします。ここでは 1 件ずつ PUT するのではなく、バルク処理でインデックスしてします。

$ curl -X POST "http://localhost:9200/_bulk?pretty" -H 'Content-Type: application/json' -d'
> { "index" : { "_index" : "item" } }
> { "name" : "Core i9", "category_path": [ "10", "100", "1000" ] }
> { "index" : { "_index" : "item" } }
> { "name" : "Core i7", "category_path": [ "10", "100", "1000" ] }
> { "index" : { "_index" : "item" } }
> { "name" : "Ryzen9", "category_path": [ "10", "100", "1001" ] }
> { "index" : { "_index" : "item" } }
> { "name" : "Ryzen7", "category_path": [ "10", "100", "1001" ] }
> { "index" : { "_index" : "item" } }
> { "name" : "GeForce RTX30", "category_path": [ "10", "101", "1002" ] }
> { "index" : { "_index" : "item" } }
> { "name" : "GeForce RTX20", "category_path": [ "10", "101", "1002" ] }
> { "index" : { "_index" : "item" } }
> { "name" : "Radeon RX6000", "category_path": [ "10", "101", "1001" ] }
> { "index" : { "_index" : "item" } }
> { "name" : "Radeon RX5000", "category_path": [ "10", "101", "1001" ] }
> '
{
  "took" : 39,
  "errors" : false,
  "items" : [
    {
      "index" : {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "2QIEHnYBFE4rMf6myF4v",
        "_version" : 1,
        "result" : "created",
        "_shards" : {
          "total" : 1,
          "successful" : 1,
          "failed" : 0
        },
        "_seq_no" : 0,
        "_primary_term" : 1,
        "status" : 201
      }
    },
    ...
    (中略)
    ...
    {
      "index" : {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "4AIEHnYBFE4rMf6myF4v",
        "_version" : 1,
        "result" : "created",
        "_shards" : {
          "total" : 1,
          "successful" : 1,
          "failed" : 0
        },
        "_seq_no" : 7,
        "_primary_term" : 1,
        "status" : 201
      }
    }
  ]
}

インデックスされた商品ドキュメントを確認しておきます。

$ curl 'http://localhost:9200/item/_search?pretty'
{
  "took" : 4,
  "timed_out" : false,
  "_shards" : {
    "total" : 1,
    "successful" : 1,
    "skipped" : 0,
    "failed" : 0
  },
  "hits" : {
    "total" : {
      "value" : 8,
      "relation" : "eq"
    },
    "max_score" : 1.0,
    "hits" : [
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "2QIEHnYBFE4rMf6myF4v",
        "_score" : 1.0,
        "_source" : {
          "name" : "Core i9",
          "category_path" : [
            "10",
            "100",
            "1000"
          ]
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "2gIEHnYBFE4rMf6myF4v",
        "_score" : 1.0,
        "_source" : {
          "name" : "Core i7",
          "category_path" : [
            "10",
            "100",
            "1000"
          ]
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "2wIEHnYBFE4rMf6myF4v",
        "_score" : 1.0,
        "_source" : {
          "name" : "Ryzen9",
          "category_path" : [
            "10",
            "100",
            "1001"
          ]
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "3AIEHnYBFE4rMf6myF4v",
        "_score" : 1.0,
        "_source" : {
          "name" : "Ryzen7",
          "category_path" : [
            "10",
            "100",
            "1001"
          ]
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "3QIEHnYBFE4rMf6myF4v",
        "_score" : 1.0,
        "_source" : {
          "name" : "GeForce RTX30",
          "category_path" : [
            "10",
            "101",
            "1002"
          ]
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "3gIEHnYBFE4rMf6myF4v",
        "_score" : 1.0,
        "_source" : {
          "name" : "GeForce RTX20",
          "category_path" : [
            "10",
            "101",
            "1002"
          ]
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "3wIEHnYBFE4rMf6myF4v",
        "_score" : 1.0,
        "_source" : {
          "name" : "Radeon RX6000",
          "category_path" : [
            "10",
            "101",
            "1001"
          ]
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "4AIEHnYBFE4rMf6myF4v",
        "_score" : 1.0,
        "_source" : {
          "name" : "Radeon RX5000",
          "category_path" : [
            "10",
            "101",
            "1001"
          ]
        }
      }
    ]
  }
}

まず、ルートカテゴリの PC パーツ (ID: 10) で検索してみます。category_path フィールドのリスト内のどれかの要素が 10 に一致するかどうかの検索で実現できます。(取得結果がの JSON が長くなってしまうので、name フィールドのみ取得するようにしています。)

$ curl 'http://localhost:9200/item/_search?q=category_path:10&_source=name&pretty'
{
  "took" : 2,
  "timed_out" : false,
  "_shards" : {
    "total" : 1,
    "successful" : 1,
    "skipped" : 0,
    "failed" : 0
  },
  "hits" : {
    "total" : {
      "value" : 8,
      "relation" : "eq"
    },
    "max_score" : 0.07859282,
    "hits" : [
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "2QIEHnYBFE4rMf6myF4v",
        "_score" : 0.07859282,
        "_source" : {
          "name" : "Core i9"
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "2gIEHnYBFE4rMf6myF4v",
        "_score" : 0.07859282,
        "_source" : {
          "name" : "Core i7"
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "2wIEHnYBFE4rMf6myF4v",
        "_score" : 0.07859282,
        "_source" : {
          "name" : "Ryzen9"
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "3AIEHnYBFE4rMf6myF4v",
        "_score" : 0.07859282,
        "_source" : {
          "name" : "Ryzen7"
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "3QIEHnYBFE4rMf6myF4v",
        "_score" : 0.07859282,
        "_source" : {
          "name" : "GeForce RTX30"
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "3gIEHnYBFE4rMf6myF4v",
        "_score" : 0.07859282,
        "_source" : {
          "name" : "GeForce RTX20"
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "3wIEHnYBFE4rMf6myF4v",
        "_score" : 0.07859282,
        "_source" : {
          "name" : "Radeon RX6000"
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "4AIEHnYBFE4rMf6myF4v",
        "_score" : 0.07859282,
        "_source" : {
          "name" : "Radeon RX5000"
        }
      }
    ]
  }
}

登録した商品ドキュメントすべてが取得できました。

次に、CPU (ID: 100) カテゴリで検索してみます。こちらも同様に category_path に 100 が含まれているかどうかを検索します。

$ curl 'http://localhost:9200/item/_search?q=category_path:100&_source=name&pretty'
{
  "took" : 3,
  "timed_out" : false,
  "_shards" : {
    "total" : 1,
    "successful" : 1,
    "skipped" : 0,
    "failed" : 0
  },
  "hits" : {
    "total" : {
      "value" : 4,
      "relation" : "eq"
    },
    "max_score" : 0.9530773,
    "hits" : [
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "2QIEHnYBFE4rMf6myF4v",
        "_score" : 0.9530773,
        "_source" : {
          "name" : "Core i9"
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "2gIEHnYBFE4rMf6myF4v",
        "_score" : 0.9530773,
        "_source" : {
          "name" : "Core i7"
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "2wIEHnYBFE4rMf6myF4v",
        "_score" : 0.9530773,
        "_source" : {
          "name" : "Ryzen9"
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "3AIEHnYBFE4rMf6myF4v",
        "_score" : 0.9530773,
        "_source" : {
          "name" : "Ryzen7"
        }
      }
    ]
  }
}

CPU が検索できました。

さらに、末端カテゴリの NVIDIA (ID: 1002) でも検索してみます。

$ curl 'http://localhost:9200/item/_search?q=category_path:1002&_source=name&pretty'
{
  "took" : 2,
  "timed_out" : false,
  "_shards" : {
    "total" : 1,
    "successful" : 1,
    "skipped" : 0,
    "failed" : 0
  },
  "hits" : {
    "total" : {
      "value" : 2,
      "relation" : "eq"
    },
    "max_score" : 1.761284,
    "hits" : [
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "3QIEHnYBFE4rMf6myF4v",
        "_score" : 1.761284,
        "_source" : {
          "name" : "GeForce RTX30"
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "3gIEHnYBFE4rMf6myF4v",
        "_score" : 1.761284,
        "_source" : {
          "name" : "GeForce RTX20"
        }
      }
    ]
  }
}

NVIDIA の GPU が検索できました。

最後に、CPU と GPU 両方生産している AMD (ID: 1001) で検索してみます。

$ curl 'http://localhost:9200/item/_search?q=category_path:1001&_source=name&pretty'
{
  "took" : 2,
  "timed_out" : false,
  "_shards" : {
    "total" : 1,
    "successful" : 1,
    "skipped" : 0,
    "failed" : 0
  },
  "hits" : {
    "total" : {
      "value" : 4,
      "relation" : "eq"
    },
    "max_score" : 0.9530773,
    "hits" : [
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "2wIEHnYBFE4rMf6myF4v",
        "_score" : 0.9530773,
        "_source" : {
          "name" : "Ryzen9"
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "3AIEHnYBFE4rMf6myF4v",
        "_score" : 0.9530773,
        "_source" : {
          "name" : "Ryzen7"
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "3wIEHnYBFE4rMf6myF4v",
        "_score" : 0.9530773,
        "_source" : {
          "name" : "Radeon RX6000"
        }
      },
      {
        "_index" : "item",
        "_type" : "_doc",
        "_id" : "4AIEHnYBFE4rMf6myF4v",
        "_score" : 0.9530773,
        "_source" : {
          "name" : "Radeon RX5000"
        }
      }
    ]
  }
}

AMD の CPU と GPU が検索できました。

Elasticsearch の場合は RDB と異なり、category_path のインテックスから 1001 の値を検索するだけでなので、ドキュメント数が増えても性能が著しく劣化することはありません。

おわりに

今回は RDB の PostgreSQL と、検索・分析エンジンの Elasticsearch で同じカテゴリ絞り込み検索を実現してみました。(RDB がグループで Elasticsearch が 1 製品なので対等ではありませんが、あえてこの対比としました...)

RDB が「経路列挙モデル」を知ったうえで、自前でカテゴリパスの文字列を操作するのに対し、Elasticsearch ではシンプルにカテゴリ ID のリストに対する検索で機能要件を満たすことができました。(「検索」の実現において元々検索エンジンとして開発された Elasticsearch のほうが向いているのは当然なのですがw)

ただし、Elasticsearch が万能といわけではないので、それぞれの長所と短所を以下に簡単にまとめます。

RDB

長所
- ロックやトランザクションなどの、操作のアトミック性や一貫性を保証する仕組みがある
  - これができないエンジンもあるので、用途次第ではあります...
- データの不整合を起こさないようにするための制約を設定できる
- 長い歴史があり、多くのエンジニアが扱い方を知っている
- (方言はあるものの) 基本的な操作であれば、どの製品でも共通的な SQL で実行できる
短所
- データ量が多くなると性能が劣化しやすい
- ハードウェアのスケールに対して性能がスケールしにくい
- 往々にしてオブジェクト指向プログラミングとの間でインピーダンスミスマッチが発生する
  - これが悔しかったのか？ Document DB の機能を内包する製品もちらほら...
- 一般的に全文検索は苦手

Elasticsearch

長所
- 内部で使用されている Lucene の I/O と検索が爆速
- ハードウェアをスケールすると性能のスケールが追随する
- アプリケーションプログラミングで使用するオブジェクト構造をそのまま JSON 形式で永続化することも可能
- 最近は検索エンジンよりは分析エンジンとしての開発に力が入っているので、分析用のクエリが充実している
短所
- ドキュメントをインデックスしてから検索ができるようになるまでにタイムラグがあり、データの不整合が発生する場合がある
- インデックス間の JOIN はできない
- 扱えるエンジニアが RDB に比べて圧倒的に少ない
  - これが問題だと思ったのか、最近のバージョンでは SQL での操作が可能に

オークファンで扱うデータでは Elasticsearch のほうが向いている場合が多いと個人的には感じています。しかしながら、上記の「短所」にもあるように、アサインされるエンジニアのスキルセットに合わせて RDB が選択されるということもしばしばあるので、引き続き社内での Elasticsearch 布教活動を続けていこうと思いますw