デカルト積問題に気をつけよう

はじめに

こんにちは、GxPの福家です。
こちらはグロースエクスパートナーズ Advent Calendar 2022の6日目の記事です。

私が担当する案件で、APIのレスポンスが突然に遅くなる事象が発生しました。その原因は、ORMにおける「デカルト積問題（cartesian product problem）」という聞き慣れない問題であることが分かりました。
今回は性能問題を引き起こす「デカルト積問題」について取り上げました。デカルト積問題とは何で、どのような状況で発生するのかついて説明したいと思います。

そもそもデカルト積とは？

デカルト積問題の前に、集合論におけるデカルト積について説明します。

デカルト積とは、複数の集合の要素のすべての組み合わせを要素として持つ集合のことです。例えば、2つの集合AとBがあるとします。集合Aは数字10個の集合{0,1,2,…,9}、集合Bはアルファベット26個の集合{a,b,c,…,z}です。そのとき、集合AとBのデカルト積は、{(0,a),(0,b),(0,c)……(9,y),(9,z)}となり、260個の要素を持つ集合となります。

デカルト積は対象となる集合が増えると要素が爆発的に増えることが特徴です。集合AとBに加えて、新たに平仮名46文字の集合C(あ,い,う,…,ん)を追加したとします。そのとき、集合AとBとCのデカルト積は、10 × 26 × 46 = 11,960 の要素を持つことになります。

ORMにおけるデカルト積問題

集合指向に基づいているSQLはデカルト積とも関連があります。例えば、CROSS JOIN句を使うことでデカルト積を簡単に生み出すことが可能です。CROSS JOIN 句は2つのテーブルのすべての組み合わせを取得します。以下のクエリで取得できる行数は table_a と table_b に格納されている行数を掛けた値となります。

SELECT * FROM table_a CROSS JOIN table_b

【補足】CROSS JOIN句の挙動

CROSS JOIN句を使うとどのような結果になるのか試してみます。table_a には4行、table_b には5行のデータが入っています。（DBはMySQLを使用しています。）

mysql> SELECT * FROM table_a;
+-------+
| value |
+-------+
| a     |
| b     |
| c     |
| d     |
+-------+
4 rows in set (0.01 sec)

mysql> SELECT * FROM table_b;
+-------+
| value |
+-------+
| 1     |
| 2     |
| 3     |
| 4     |
| 5     |
+-------+
5 rows in set (0.00 sec)

mysql> SELECT * FROM table_a CROSS JOIN table_b;
+-------+-------+
| value | value |
+-------+-------+
| d     | 1     |
| c     | 1     |
| b     | 1     |
| a     | 1     |
| d     | 2     |
| c     | 2     |
| b     | 2     |
| a     | 2     |
| d     | 3     |
| c     | 3     |
| b     | 3     |
| a     | 3     |
| d     | 4     |
| c     | 4     |
| b     | 4     |
| a     | 4     |
| d     | 5     |
| c     | 5     |
| b     | 5     |
| a     | 5     |
+-------+-------+
20 rows in set (0.01 sec)

このように、4 × 5 = 20行が取得できることが分かります。

さて、本題のORMにおけるデカルト積問題についてです。ORMはクエリで取得した行をオブジェクトに変換するマッピング処理を行います。クエリで取得する行が多ければマッピング処理に多くのリソースを消費します。デカルト積問題とは、爆発的に要素が増えるデカルト積の性質によって、大量のマッピング処理が発生してしまうという性能問題なのです。

とは言え、CROSS JOIN句をWEBアプリの実装で使うことは稀だと思います。では、どのような場合にデカルト積問題が発生してしまうのでしょうか？今回は簡単な実装を事例として紹介したいと思います。

事例

とあるアイドルメンバーの紹介ページがあるとします。アイドルには属性や特技、画像の情報を複数紐づけることができ、それらの情報をページに表示することができます。アイドルの情報は以下のようなテーブルに格納されています。

事前にアイドルを1人追加し、属性・特技・画像を5件ずつ紐づけておきます。

投入したデータ

INSERT INTO idols 
VALUES
(1, 'デカルコちゃん', 'こんにちは、よろしくおねがいします。');

INSERT INTO attributes 
VALUES
(1, '家電屋店長系')
,(1, 'オタク系')
,(1, 'SP系')
,(1, '患者系')
,(1, '主人公系');

INSERT INTO skills
VALUES
(1, '将棋')
,(1, '食べる')
,(1, 'ライター')
,(1, 'ラクガキ')
,(1, 'ロボ乗り');

INSERT INTO images
VALUES
(1, 'http://www.idolhakken.co.jp/aaaaaa.ping')
,(1, 'http://www.idolhakken.co.jp/bbbbbb.ping')
,(1, 'http://www.idolhakken.co.jp/cccccc.ping')
,(1, 'http://www.idolhakken.co.jp/dddddd.ping')
,(1, 'http://www.idolhakken.co.jp/eeeeee.ping');
-- 参考 "「系VTuberの名称一覧【VTuberの系統まとめ】" https://jindopia.com/vtuber-type/

デカルト積問題の実装

テーブルから行を取得し、ORMでIdolオブジェクトを生成したいと思います。
Idolクラスを以下のように実装します。コレクションのフィールドを複数持っているところがポイントです。

public class Idol {
    private int id;
    private String name;
    private String description;
    private List<String> attributes; //属性
    private List<String> skills;     //特技
    private List<String> imageUrls;  //画像のURL
}

クラスが実装出来たら、ORMでマッピング処理を実装します。

MyBatisで実装するならXMLはこんな感じです

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE mapper
        PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN"
        "http://mybatis.org/dtd/mybatis-3-mapper.dtd">
<mapper namespace="jp.co.gxp.idolhakken.mapper.IdolMapper">
    <select id="selectAllIdols" resultMap="idolResultMap">
        SELECT idols.idol_id
             , idols.name
             , idols.description
             , attributes.value attribute
             , skills.value skill
             , images.image_url
        FROM idols
        LEFT OUTER JOIN attributes ON idols.idol_id = attributes.idol_id
        LEFT OUTER JOIN skills ON idols.idol_id = skills.idol_id
        LEFT OUTER JOIN images ON idols.idol_id = images.idol_id
    </select>
    <resultMap id="idolResultMap" type="jp.co.gxp.idolhakken.model.Idol">
        <id property="id" column="idol_id" />
        <result property="name" column="name"/>
        <result property="description" column="description"/>
        <collection property="attributes" ofType="java.lang.String">
            <result column="attribute"/>
        </collection>
        <collection property="skills" ofType="java.lang.String">
            <result column="skill"/>
        </collection>
        <collection property="imageUrls" ofType="java.lang.String">
            <result column="image_url"/>
        </collection>
    </resultMap>
</mapper>

動作検証

実装が完了したので、ORMで生成されたクエリと取得される行を確認してみます。

生成されたクエリ

SELECT idols.idol_id 
    , idols.name 
    , idols.description 
    , attributes.value attribute 
    , skills.value skill 
    , images.image_url 
FROM idols 
LEFT OUTER JOIN attributes ON idols.idol_id = attributes.idol_id 
LEFT OUTER JOIN skills ON idols.idol_id = skills.idol_id 
LEFT OUTER JOIN images ON idols.idol_id = images.idol_id

クエリで取得される行数

125 rows in set (0.01 sec)

事前に登録していた属性5件 × 特技5件 × 画像5件 = 125行を取得しました。
これはアイドルに紐づく属性・特技・画像URLのデカルト積となっています。もし、ユーザーが特技や画像を自由に追加できたら、このクエリで取得される行は爆発的に増えてしまいます。

このように、ORMで複数のコレクションを持つオブジェクトを生成しようとすると、デカルト積が発生することが分かりました。

デカルト積問題を解消してみる

この事例でデカルト積を解消するにはどうすればよいのでしょうか？
方法はシンプルで、コレクションのマッピングを別のクエリに切り出し、コード側で結合するように修正するだけです。

まずはクラスを分割します。すべてのクラスにidolIdを持たせているのは、IdolをList型で取得したいときに、IDをkeyとして紐づけられるようにするためです。

public class IdolDto {
    private int idolId;
    private String name;
    private String description;
    
    // Idolオブジェクトを生成する処理
    public Idol generate(List<String> attributes, List<String> skills, List<String> imageUrls){
        return new Idol(
            // 省略
        )       
    }
}

public class IdolAattributeDto {
    private int idolId;
    private List<String> attributes;
}

public class IdolSkillDto {
    private int idolId;
    private List<String> skills; 
}

public class IdolImageUrlsDto {
    private int idolId;
    private List<String> imageUrls;
}

次に上記の4つのクラスをマッピングできるようにORMで実装します。

MyBatisで実装するならXMLはこんな感じです

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE mapper
        PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN"
        "http://mybatis.org/dtd/mybatis-3-mapper.dtd">
<mapper namespace="jp.co.gxp.idolhakken.mapper.IdolMapperV2">
    <select id="selectAllIdols" resultMap="idolResultMap">
        SELECT idols.idol_id
             , idols.name
             , idols.description
        FROM idols
    </select>
    <select id="selectAllAttributes" resultMap="attributeResultMap">
        SELECT idol_id, value attribute
        FROM attributes
    </select>
    <select id="selectAllSkills" resultMap="skillResultMap">
        SELECT idol_id, value skill
        FROM skills
    </select>
    <select id="selectAllImageUrls" resultMap="imageResultMap">
        SELECT idol_id, image_url
        FROM images
    </select>

    <resultMap id="idolResultMap" type="jp.co.gxp.idolhakken.repository.dto.IdolDto">
        <id property="id" column="idol_id" />
        <result property="name" column="name"/>
        <result property="description" column="description"/>
    </resultMap>

    <resultMap id="attributeResultMap" type="jp.co.gxp.idolhakken.repository.dto.IdolAttributeDto">
        <id property="id" column="idol_id" />
        <collection property="attributes" ofType="java.lang.String">
            <result column="attribute"/>
        </collection>
    </resultMap>

    <resultMap id="skillResultMap" type="jp.co.gxp.idolhakken.repository.dto.IdolSkillDto">
        <id property="id" column="idol_id" />
        <collection property="skills" ofType="java.lang.String">
            <result column="skill"/>
        </collection>
    </resultMap>

    <resultMap id="imageResultMap" type="jp.co.gxp.idolhakken.repository.dto.IdolImageUrlDto">
        <id property="id" column="idol_id" />
        <collection property="imageUrls" ofType="java.lang.String">
            <result column="image_url"/>
        </collection>
    </resultMap>
</mapper>

（IdolをList型で取得したいときは、IN句でIDを条件にして取得するなどの工夫が必要です。）

動作検証

修正が終わったので、ORMで生成されたクエリと、クエリで取得される行数を確認してみます。

生成されたクエリ

-- IdolDto
SELECT idols.idol_id , idols.name , idols.description 
FROM idols;

-- IdolAattributeDto
SELECT idol_id, value attribute 
FROM attributes;

-- IdolSkillDto
SELECT idol_id, value skill 
FROM skills;

-- IdolImageUrlsDto
SELECT idol_id, image_url 
FROM images;

クエリで取得される行数

-- IdolDto
1 rows in set (0.01 sec)

-- IdolAattributeDto
5 rows in set (0.01 sec)

-- IdolSkillDto
5 rows in set (0.01 sec)

-- IdolImageUrlsDto
5 rows in set (0.01 sec)

アイドル1件 + 属性5件 + 特技5件 + 画像5件 = 計16行を取得しました。改修前の125行に比べると行数を大幅に削減することができました。
これで大量のデータをアイドルに紐づけられても性能が悪化しにくくなります。仮に、属性20件、特技20件、画像20件を紐づけた場合でも、改修前は8000行を取得するのに対して、改修後は計61行の取得で済みます。

おわりに

複雑なクエリを書いていると気づかぬうちにデカルト積問題が生じてしまう可能性があります。私の案件では機能追加を繰り返し、クエリが複雑化していました。その結果、いつの間にかデカルト積問題が紛れ込み、性能問題を引き起こしてしまいました。クエリはシンプルに保つことが大事だなと思った今日この頃でした。

参考

Hibernate Cartesian Product Problem