データの偏りを利用して期間を絞り込むクエリを最適化した3つの着眼点 - Cybozu Inside Out

この記事は、CYBOZU SUMMER BLOG FES '24 (Garoon Stage) DAY 1の記事です。

こんにちは、サイボウズ Garoon開発 Nozomiチーム所属の赤間です。

NozomiチームはGaroonの性能に関する問題に取り組むチームとして活動しており、2023年末に最初の改善成果がリリースされました。その内容がMySQLに格納されたデータの特性に基づいて効率的なインデックスを作成するという面白いものでしたので、本記事ではその詳細について紹介します。

以降、RDBはMySQLに限定し、単にインデックスといった場合はB-treeインデックスを指すものとします。

最適化したいクエリ

Garoonはさまざまな機能を持つグループウェアです。メッセージのやりとりや報告書の共有など、組織のチームワークに貢献するさまざまな機能が備わっています。中でもよく使われる機能がスケジュールです。名前の通り、今日の予定を確認したり複数人でのミーティングを調整できます。

佐藤さんの今週1週間の予定一覧を例に出して、Garoonのスケジュール画面の雰囲気を説明しています — Garoonのスケジュール機能

スケジュールはGaroonの中でも特に負荷の高い機能です。理由はいくつかありますが、その中のひとつが「ある期間に存在する予定を取得する」という基本的なしぼり込みをRDBで行うのが難しいからです。しかしそのようなクエリはスケジュールにまつわる以下のような機能を実装するのに必要不可欠です。

あるユーザの本日の予定をすべて表示する
ある予定の参加者のうち、他の予定とブッキングしている参加者の一覧を取得する
ある施設を予約するため、その施設が同じ時間に既に予約されていないかを確認する

例として、今日開催されるすべての予定を取得するクエリは以下のようになります。

-- クエリ1
SELECT id
  FROM events
 WHERE end_time >= (今日の00:00)
   AND start_time < (明日の00:00);

ここで、eventsテーブルは以下のような定義とします。MySQLの時刻データ型に関する説明を避けるため、時刻はすべてINT型のタイムスタンプとして扱うこととします。また、実際のテーブルに含まれる他の情報は、本記事中では簡略化のために省略しています。

CREATE TABLE events (
  id         INT NOT NULL AUTO_INCREMENT, -- 予定ID
  start_time INT NOT NULL,                -- 予定の開始タイムスタンプ
  end_time   INT NOT NULL,                -- 予定の終了タイムスタンプ
  PRIMARY KEY (id),
  INDEX index_start_end (start_time, end_time)
);

クエリ1のWHERE句の条件は「今日の00:00以降に終わり、なおかつ明日の00:00より前に始まる」と読めます。ゲームにおける矩形衝突判定と似ているといえばイメージがつきやすいでしょうか。なお、日付をまたがる予定についても取得する必要があります。

クエリ1が取得する予定を視覚的に表しています。本日中に完了する定例、および会議の2つの予定に加えて、前日から続いていた出張の予定も取得します。ただし、前日までに終了していた予定と、明日以降開始する予定は取得しません。 — クエリ1で取得する予定のイメージ

本記事の主題は、どうすればこのクエリを高速に実行することができるか？というものです。

以前のGaroonでは (start_time, end_time) のような複合インデックスを使っていました。すなわち、 start_time と end_time の2つのカラムで辞書式順序にソートされたインデックスです。しかしこれでは最大のパフォーマンスは発揮できず、インデックスフルスキャンと同程度に非効率でした。

Garoonでは1000万件以上の予定が存在するお客様環境もあるため、こういった形のクエリの実行には多くの実行時間がかかることがあり、長い間性能のボトルネックとなっていました。

このインデックスが非効率である原因は、異なるカラムに対する不等式条件が複数ある場合にインデックスを走査する範囲を十分に絞り込めないことです。

インデックスの並び順と走査範囲

このようなクエリがなぜ効率的に実行できないかを説明するために、(start_time, end_time) で貼ったインデックスのエントリはどのような順で並ぶか考えます。このインデックスでは、まず start_time の順でソートされ、start_time が同じである列は end_time でさらに並べられます。以下の表に並べられたエントリの例を挙げます。

取得するか？	`start_time`	`end_time`
	2024-03-01 10:00	2024-03-01 11:00
✅	2024-03-01 10:00	2024-05-01 10:00
	2024-03-01 12:00	2024-03-01 13:00
	…	…
✅	2024-04-01 10:00	2024-04-01 11:00
✅	2024-04-01 13:00	2024-04-01 15:00
✅	2024-04-01 23:00	2024-04-02 10:00
	2024-04-02 12:00	2024-04-02 13:00

表の中で、印は4月1日を検索対象とした際にクエリ1が返すべき行を表しています。注目してもらいたいのが、2行目に3月から5月までの2ヶ月間にわたって取られた予定があることです。このように、長い予定はstart_time順に並んだインデックス上では離れた位置に存在することがあり得ますが、条件に当てはまるため結果に含まれます。したがって MySQLはこのインデックスにおいてstart_timeが最も古いものから明日の00:00までのエントリをすべて走査したのち、end_time >= (今日の00:00) の条件に合わないエントリを取り除くことにより、このクエリを実行することになります。すなわち、start_timeはMySQLがアクセスするインデックスの範囲を限定するためにはうまく利用できず、end_timeによる制約も活用できない結果、読み取るべきエントリの範囲が広くなってしまいます。

2024年4月1日を含む、非常に長い予定があります。このような予定を考慮しなければならないために、その日よりも前に終了している予定についても取得しなければなりません。 — 非常に長い予定が存在する可能性を考慮して、すでに終了した予定も取得する必要がある

B-treeインデックスは木構造のデータ構造ですが、エントリは一列に並んでいます。そのため走査範囲指定の条件は1つのカラムに対してのみしか原理的に利用することができません。

測定のためのデータセット

ここから先はNozomiチームで実際に行った性能改善のアイディアを紹介していきます。その前に、Nozomiチームではどのようにして開発環境で性能を測定しているかを紹介します。

cybozu.comのお客様の入力情報は自社クラウド基盤にて厳重に管理されています。そのためお客様のデータを直接使用して性能を測ることはできません。そこでクラウドデータポリシーに基づき、適切な形で統計処理を行った結果のみを参照し、データ量や分布から擬似的にデータを作成した環境で性能の測定をしています。

本記事で記載する測定値については、実際の性能改善業務で利用したデータを改変して利用しており、eventsテーブルの行数は1000万行としました。なお本記事での測定はMacBook Pro (M2 Pro, 32GB) 上のDockerで行っています。

現状のクエリ1の実行速度を測定したところ、1.22秒となり、4285行の結果が返却されました。

-- クエリ1 (再掲)
SELECT id
  FROM events
 WHERE end_time >= (今日の00:00)
   AND start_time < (明日の00:00);

ここから改善を進めていきます。

アイディア1：データの偏りを考慮に入れる

B-treeインデックスの構造上、複数のカラムに対する不等式を含むようなクエリを一般的な方法で高速化するのは不可能だと分かりました。そこでeventsテーブルがユーザによってどのように利用されるかに着目しました。

ユーザがスケジュール機能を使う上で気にするのは、今日やその先の未来の予定です。数ヶ月前、ましてや数年前の予定を参照することはそれほど多くありません。そのためeventsテーブルの参照範囲は未来に偏っています。一方、時間は絶えず流れるのでeventsテーブルには未来の予定よりも過去の予定の方が多く存在します。すると、start_time < (明日の00:00)よりも end_time >= (今日の00:00) の条件式を用いてインデックスの走査範囲を指定する方が走査する行が減る可能性が高いです。したがって、 (start_time, end_time) のようにstart_timeを先頭にする代わりに、end_timeを複合インデックスの最初の列にすることが望ましいだろうと考えました。

既存のインデックスを消し、新しいインデックスを作成します。

ALTER TABLE events DROP INDEX index_start_end;
ALTER TABLE events ADD INDEX index_end_start (end_time, start_time);

そしてクエリ1をそのまま測定すると0.20秒となりました。

アイディア2：予定の長さに対して仮定を入れる

ところで皆さんはランチの時間をだいたい何分くらい取るでしょうか？早い人なら数分、長い人でも1〜2時間でしょうか。でもランチに2日もかける人はそんなにいないですし、3日間続くミーティングもあまりないでしょう。Garoonに長い予定を登録するとしても数日から数週間の出張などで、定例会や昼食の頻度と比べたらずっと低いはずです。

スケジュールの登録状況からも同じことが言えます。調査したところ、登録された99%の予定は1日以内に終わることが分かっています。先ほど挙げたような数ヶ月もの長さを持つ予定はレアケースだと言えます。

そこで、全ての予定が1日以内で終了すると仮定してみます。すなわち、end_time - start_time <= 1日 です。変形すると end_time <= start_time + 1日です。ここでクエリの条件から start_time < (明日の00:00) であり、start_timeの上限が与えられていると読めば、end_time < (明日の00:00) + 1日が得られます。すると、(今日の00:00) <= end_time < (明日の00:00) + 1日という条件をクエリに付加しても結果は変化しません。

これによって end_time に関しては今日の00:00から明後日の00:00までという2日間に絞ることができました。すると end_time の上限と下限が与えられたことにより、比較的狭い範囲の index range scan が可能になります。この工夫を加えたクエリは以下のようになります。

-- クエリ2
SELECT id
  FROM events
 WHERE start_time < (明日の00:00)
   AND end_time >= (今日の00:00)
   AND end_time < (明日の00:00) + 1日

このクエリはend_timeでインデックスの走査範囲を絞り込んだあと、start_time の条件を使って当てはまらない行をフィルタするという挙動をします。これでかなりピンポイントに絞れました。しかし、1日以内に全ての予定が終了するという仮定があるため、このままでは正しいクエリとはいえません。

参考までにクエリ2の実行速度を測ると0.01秒まで高速化できました。しかし当然ながら一部の行が欠けており、4285行が得られるべきところ、4205行しかありませんでした。

アイディア3：インデックスの中でデータを隔離する

アイディア2はかなりスマートな方法ですがそれだけでは十分ではありません。なんとかして活用できないかと考えた結果、「予定が丸一日よりも長いかどうか」を表すフラグを用意し、それを複合インデックスの先頭に配置することで、1日よりも長い予定を短い予定から隔離することを考えました。まずはクエリで説明します。

-- クエリ3
SELECT id
  FROM events
 WHERE start_time < (明日の00:00)
   AND (is_longer_than_1day = FALSE AND end_time >= (今日の00:00)
                                    AND end_time < (明日の00:00) + 1日
     OR is_longer_than_1day = TRUE AND end_time >= (今日の00:00)
   )

新しいカラム is_longer_than_1day が新しいフラグです。このフラグはある予定に対し、長さが1日以内であればFALSEを、1日を超える場合はTRUEを取ります。そしてクエリの条件をORで合成することにより、1日以内に終わる予定とそうでない予定の2つの範囲に対する index range scan となります。

また、インデックスも新しく定義する必要があります。(is_longer_than_1day, end_time) のように、新しいフラグをend_time の前に置くと、予定全体が is_longer_than_1day で並び替えられた上で end_time の順番で整列するため、予定の長さによる分類で2つの領域に分割することができました。

新しく作成したインデックスでは、99%の長さが1日以内の予定と1%の長さが1日よりも長い予定が隔離されていることのイメージ — 新しいインデックスの視覚的イメージ

これによって is_longer_than_1day = 0 となる範囲に対してアイディア2が実現可能となりました。1日以内に終わる予定の割合が99%であるならば、このクエリはアイディア2のクエリと同じような実行時間になると期待できます。そして1日よりも長い予定に対しては、アイディア1を適用することを狙います。

Generated column を利用したフラグの追加

さて、次に問題となるのがこのようなカラムを既存のテーブルにどのように追加するかです。cybozu.comで稼働しているGaroonはすでに運用を開始してから10年以上経過しているため、スケジュールのデータ量は膨大です。このテーブルに対してメンテナンスでのダウンタイムとして許容できる時間内にカラムを追加できなければなりません。

検討した結果、MySQL 5.7系から追加されたgenerated columnという機能を利用することにしました。generated columnはその行の他のカラムの値によって自身の値が決まるカラムです。generated columnにはさらにstoredとvirtualの2種類がありますが、今回は実際の値を保存しないvirtualを選択しました。理由は生成されたカラムの値をインデックスにのみ含めれば十分だからです。

さらに、MySQL 8.0.12 から instant DDLが利用できるようになりました。これによりテーブルの再構築をせずにカラムの追加が可能です。すると1000万行あるテーブルに対しても1分程度でカラムとインデックスの追加が完了しました。

ALTER TABLE events
  ADD COLUMN is_longer_than_1day BOOLEAN GENERATED ALWAYS AS
  (CASE WHEN end_time - start_time > 24 * 60 * 60 THEN 1 ELSE 0 END) VIRTUAL,
  ADD INDEX index_is_longer_than_1day (is_longer_than_1day, end_time, start_time);

なお、複合インデックスの最後にstart_timeを含めているのは、クエリ3で使うeventsのカラムすべてを含めることでカバリングインデックスになることを期待するためです。カバリングインデックスを利用できればインデックスを読み取るだけでクエリの実行が可能となり、テーブル本体の読み込みを省略できるためより高速に動作します。Garoonで実際に使用しているテーブルには他のカラムもたくさんあるため、効果が期待できると考えました。

この新しいインデックスを追加してクエリ3の実行時間を測定するとアイディア2と変わらず0.01秒でした。

テーブル結合時の考慮点

本記事で紹介した手法によって、eventsテーブルからある期間に開催される予定を取得するクエリは大幅に改善しました。しかしこれでもパフォーマンスに関する問題が全て解決したわけではありません。というのも現実的にはある一定期間の全ての予定を取得することはほとんどなく、基本的にはテーブル結合によってさらに条件を絞った上でレコードを取得するためです。

実用的なクエリには結合操作が欠かせません。例えば Garoon にはグループ週表示という、自分自身が所属する組織やグループの他のユーザの1週間の予定を確認できる便利な機能があります。さらに、自分の1ヶ月の予定をまとめて閲覧する月表示という機能も存在します。

これらの機能には「1人または複数人のユーザに対して、そのユーザたちがある期間の中で参加する予定」を取得するといったクエリが求められます。これには eventsテーブルと「ユーザが参加する予定のリレーション」のテーブルを結合することが必要です。

このクエリを使って、テーブル結合時にどのようなトレードオフが発生するか解説します。attendanceテーブルを event_id と user_id をカラムとして持つ、ユーザが参加する予定のリレーションとします。本記事の手法をそのまま利用し、attendanceテーブルを結合をすると以下のようなクエリになります。

-- クエリ4
SELECT attendance.event_id, attendance.user_id
  FROM events
  JOIN attendance
    ON event.id = attendance.event_id
 WHERE attendance.user_id IN (ユーザIDのリスト)
   AND events.start_time < (期間の終了時点のタイムスタンプ)
   AND (events.is_longer_than_1day = FALSE AND events.end_time >= (期間の開始時点のタイムスタンプ)
                                           AND events.end_time < (期間の終了時点のタイムスタンプ) + 1日
     OR events.is_longer_than_1day = TRUE AND events.end_time >= (期間の開始時点のタイムスタンプ)
   )

MySQLでのテーブル結合は多くの場合Nested Loop アルゴリズムによって実現されます。これは2重のfor-loopのようなもので、外側のループのテーブル（駆動表）の行1つに対して、もう片方のテーブル（内部表）から結合条件に一致する行を探すような動作をします。

JOINを含むクエリを実行する際、どのテーブルを駆動表にするかはMySQLにより選択されますが、オプティマイザヒントとして与えることもできます。そして駆動表の選択によりパフォーマンスは大きく変わります。おおむね駆動表に選択されたテーブルがよく絞り込めており、ループの回数が少なくなるほど結合を含むクエリは高速に実行できます。

クエリ4においてパフォーマンスに関わる変数としては主に以下の2つがあります。

ユーザIDの数
期間の長さ

eventsテーブルを駆動表にした場合は、指定された期間 + 1日の間に存在する予定をすべて取得してから event_id によってattendanceテーブルを引き、与えられたユーザが参加しているかどうかを判定します。そのため、おおむね期間の長さに比例した実行時間になるといえます。

反対に、attendanceテーブルを駆動表にした場合は、attendanceテーブルから各々のユーザが参加する予定をすべて読み出し、その予定が指定された期間に開催されるかを判定します。こちらの場合は大まかに見ればユーザIDの数に比例した実行時間となります。

仮に eventsテーブルを駆動表にして1ヶ月の期間を指定した場合はユーザ全員の1ヶ月の予定を走査するため大きなコストがかかってしまいますが、ユーザIDが1つならば駆動表はattendanceテーブルにすることができます。これにより1人のユーザが過去に参加したすべての予定を走査することにはなりますが、こちらの方が高速なことが多いです。

そのため、Garoonではグループ週表示のように多数のユーザの予定を表示する際は駆動表をeventsテーブルに、月表示のようにログインユーザの1ヶ月の予定にアクセスする場合は駆動表をattendanceテーブルにするといった使い分けをしています。

ちなみに attendanceテーブルが駆動表になった場合は、内部表のeventsテーブルは主キーで引けるため、is_longer_than_1dayのフラグは不要になります。

このように、テーブルを結合する際は絞り込みの条件に応じて適した駆動表が変わるため、駆動表をオプティマイザヒントにより明示的に指定することにしました。

本番環境に適用した成果

この記事で紹介した性能改善手法はすでにcybozu.com上で稼働しているGaroonに一部適用されています。

予定登録時に施設の空き状況を確認するリクエストにおいては、最も遅い環境での応答時間の90%tileが約2800msほどかかっていたのが100msを切るほどに高速化できました。

また同じ環境で、予定の詳細画面を表示する際に他のユーザに予定のブッキングがあるかを確認する処理を改善した結果、応答時間の90%tile を約3000ms から約380msに、おおむね8倍の高速化を達成しました。

今後も本手法を水平展開していき、スケジュールの他の機能についても改善を進めていきます。Garoonの他のアプリケーションについても性能を向上させ、よりユーザの方々がストレスなく利用できるよう、Nozomiチームでは性能を改善する活動を続けていきます。

まとめ

Garoonのスケジュール機能における、指定した期間内の予定を検索するクエリの性能改善を行いました。このクエリには異なるカラムに対する不等式条件が複数あるため、既存のインデックスでは走査する範囲を効率的に絞り込むことができませんでした。そこで2種類のデータの偏り、すなわち過去に比べて未来に存在する予定が少ないことと、開始時間と終了時間が大きく離れた予定が少ないことに着目して効率的なインデックスを設計しました。

実装にはgenerated columnとinstant addの2つのMySQLの機能を利用し、蓄積された巨大なデータを持つテーブルに対して効率的にインデックスを与えることに成功しました。ただし、本記事で紹介した手法ではテーブル結合を行う際に適切でない駆動表が選択されるリスクがあるため、オプティマイザヒントをパラメータに応じて適切に与えて、明示的に駆動表を指定して運用しています。