Go to Qiita Advent Calendar 2024 Top
LoginSignup
1408
1260

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@yuku_t(Yuku Takahashi)

実例で学ぶ、JOIN (NLJ) が遅くなる理屈と対処法

Last updated at Posted at 2015-06-22

"Nested Loop Joinしか取り上げて無いのにタイトルが大きすぎないか" と指摘を頂いたので、タイトルを修正しました。Merge JoinとHash Joinのことはまた今度書こうと思います。

「JOINは遅い」とよく言われます。特にRDBを使い始めて間がない内にそういう言説に触れた結果「JOIN=悪」という認識で固定化されてしまっている人も多いように感じています。

たしかに、JOINを含むようなSELECT文は、含まないものに比べて重たくなる傾向があることは事実です。また、本質的に問い合わせたい内容が複雑で、対処することが難しいものも存在します。しかし、RDBの中で一体どういうことが起きているのかを知り、それに基いて対処すれば高速化できることも少なくないと考えています。

本稿では、JOINの内部動作を解説した上で、Webサービスを作っているとよく出てくるJOIN SQLを例題にして、チューニング方法を考察したいと思います。

例を単純にするために、状況設定にいびつな点もあるかと思いますが、ご容赦ください。

TL;DR

  • 駆動表と内部表のフェッチ数が計算量に影響する
  • インデックスでフェッチを速めることも大切
  • 内部表でソートすると大変なことになる

JOINのアルゴリズム

複数のテーブルを結合するSQLを実行すると、RDBは内部的にテーブルを結合する処理を実行します。そのアルゴリズムは大きく分けて3種類あり、それぞれに得意不得意な状況が異なります:

  1. Nested Loop Join(以下NLJ)
  2. Hash Join
  3. Merge Join

...なのですが、実はMySQLに関していうとNLJ（とその亜種）しか実装されていません。1

なので、ここではNLJだけを見ていきます。

Nested Loop Join

SELECT *
  FROM t1, t2
 WHERE t1.c1 = 1
   AND t1.c2 = t2.c3;

このようなJOIN SQLが与えられたとき、NLJが結合表をクライアントに返す流れを疑似コードで表すと次のようになります:

NLJの擬似コード
# 1. t1テーブルから条件にあうものを1レコードずつ取ってくる。
for row1 in fetch(t1, { "c1": 1 }):
    # 2. 1の結果に対してあうレコードをt2テーブルから1つずつ取ってくる。
    for row2 in fetch(t2, { "c3": row1.c2 }):
        # 3. それをクライアントに返す。
        send_to_client(row1 + row2)

コードを見れば分かるように、forループの中でforループが実行されています。これがNested Loop Joinと呼ばれる理由です。

この時、外側でループしているテーブルを駆動表、内側でループしているテーブルを内部表と言います。今回の疑似コードで言えば、t1が駆動表、t2が内部表です。

高速化のアプローチ

さて、t1からフェッチされるレコード数をn、それに対してt2からフェッチされるレコード数をmとすると、このアルゴリズムの計算量はO(nm)です。なのでこの処理を高速化したいとなったら、nを小さくする、mを小さくする、の2つのアプローチがまずは挙げられます。

nとmを小さくする、というのは具体的には、1000回のループの中で1000回ループするんじゃなくて、10回のループの中で1回ループすれば済むようにしましょう、ということです。

また、いくらnとmが小さくても、フェッチするのが遅かったら元も子もありません。

つまり、まとめると

  1. SQLを工夫してnとmを小さくする
  2. 適切にインデックスを作ってそのn*m個を高速にフェッチできるようにする

というのが、NLJ高速化ためにやれることになります。

駆動表と内部表の調べ方

EXPLAINを使って、JOIN時にどちらのテーブルが駆動表でどちらのテーブルが内部表になっているか調べることができます:

mysql> EXPLAIN SELECT * FROM t1, t2 WHERE t1.c1 = 1 AND t1.c2 = t2.c3\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: ref
possible_keys: index_t1_on_c1_and_c2
          key: index_t1_on_c1_and_c2
      key_len: 5
          ref: const
         rows: 10
        Extra: Using where; Using index
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: t2
         type: ref
possible_keys: index_t2_on_c3
          key: index_t2_on_c3
      key_len: 5
          ref: sample.t1.c2
         rows: 1
        Extra: Using index

このとき1つ目が駆動表、2つ目が内部表になります。tableの項目を見るとテーブル名が分かります。つまり、今回の場合、t1が駆動表、t2が内部表です。

nとmの実際の値は実行してみなければ分からないのですが、RDBMSは実行計画を立てるためにテーブルの統計情報から概算値を見積もってrowsで見せてくれます。今回の例ならn=10、m=1なので10回くらいフェッチされることが分かります。

また、それぞれのテーブルからフェッチするのにどのインデックスが使われているか、などが分かります。

フェッチする数も少ないしインデックスも適切に効いているので、このSQLは十分高速に動きそうです。

例: ブログサービス

では具体例を使って見ていきましょう。ここでは、ブログサービスを作ってるとします。ブログには沢山の記事があり、個々の記事には複数のタグを付けられます。つまり記事とタグは多対多の関係にあります。

データを永続化するために、記事とタグ、さらにタグ付け関係を表すための中間テーブルを作ります。2

CREATE TABLE tags (
  id INT PRIMARY KEY
);
CREATE TABLE articles (
  id INT PRIMARY KEY,
  created_at DATETIME
);
CREATE TABLE taggings (
  tag_id INT,
  article_id INT
);

簡単に高速化できるJOIN SQLの例

記事に紐付いたタグ一覧を取ってきたいです。1つの記事につけられるタグの数はアプリケーションの側で5個に制限されているとしましょう。

ある記事（ID=1とする）のタグ一覧を取ってくるSQLはこんな感じで表現されます:

ある記事のタグ一覧
SELECT tags.*
  FROM taggings, tags
 WHERE taggings.tag_id = tags.id
   AND taggings.article_id = 1;

このSQLはまず間違いなくtaggingsが駆動表になります。なぜならarticle_id=1という制約があるので、nを小さくできるからです。今回の場合、nは高々5です。

その高々5個のレコードを取ってくるのを高速化するには、以下のインデックスを用意すればいいですね:

CREATE INDEX index_taggings_on_article_id
  ON taggings(article_id);

また、tag_idと比較しているtags.idは主キーなので各taggingsレコードに対して高々1つしか存在しない、言い方を変えるならm=1であることが保障されます。主キーを使ったフェッチは高速です。

カバリングインデックス

...まぁ確かにNLJの観点で言えば、今回のSQLの場合はarticle_idのインデックスで十分なんですが、実際は以下の複合インデックスの方がより高速です:

CREATE INDEX index_taggings_on_article_id_and_tag_id
  ON taggings(article_id, tag_id);

複合インデックスについてさしあたり知っていて欲しいことは、大雑把に言えば、左側のカラムの値を定めたときに、右側のカラム3の値を効率よく、しかもソートした状態で取り出すことができる、ということです。

つまりarticle_idだけのインデックスの場合は5個のレコードを取ってきてtag_idを見て回る必要が生じる。その一方、複合インデックスの場合は、インデックスを調べた時ついでにtag_idの値も取得できてしまうので、その分高速なのです。

このようにSQLの中で必要になる全てのカラムを含むインデックスをカバリングインデックスといいます。

ところで、レコードを単純にとってくるだけなのに、それを短縮したくらいでどうして高速化されるのでしょう？

その理由はレコードの実際のデータはそれぞれ全く別の場所に格納されているため、ストレージに対するランダムアクセスが発生するからです。

特にHDDの場合、1回のランダムアクセスにミリ秒単位で時間がかかります。たとえ高々5回だったとしても、その影響は無視できません。

一方、高速なランダムアクセスができるSSDやFusion-ioなどをDBサーバのストレージに使っている場合、カバリングインデックスによる高速化の効果はHDDを使っている時と比較して小さくなります。複合インデックスは更新に手間がかかるしサイズも大きくなるので、カバリングインデックスを使わない方がむしろいいという場合も十分にありえるのではないでしょうか。

高速化が難しいJOIN SQL

続いて、あるタグの新着記事を取ってくるSQLを考えてみます。

タグの記事数はサービスが成長するに従ってどこまでも増えます。全てを取ってくるのではなく、一部を表示するのが普通でしょう:

あるタグの新着記事10件（内部表で並べ替え版）
  SELECT articles.*
    FROM taggings, articles
   WHERE taggings.article_id = articles.id
     AND taggings.tag_id = 1
ORDER BY articles.created_at DESC
   LIMIT 10;

このSQLはどんなインデックスを使っていても重たくなる危険があります。理由は ORDER BYに指定しているのが内部表であるということです。ORDER BYそのものに問題があるのではないので注意してください。

では何故ORDER BYに内部表が使われると遅くなるのか。その理屈は擬似コードを見た方が分かりやすいかも知れません:

join_table = []

# どれが対応するか分からないからtag_id=1なtaggingsを全て取ってくる
for row1 in fetch(taggings, { "tag_id": 1 }):
    for row2 in fetch(articles, { "id": row1.id }):
        # 一旦joinテーブルを作って
        join_table.append([row1, row2])
        
# articlesの値でソートしてから10件だけクライアントに返す
for row1, row2 in sort(join_table)[0:10]:
    send_to_client(row2)

仮にtag_id=1なtaggingsが100万件あったとすると

  1. 大きさ100万のテーブルを一時的に作る。
  2. それをソートする。

という処理が発生する訳です。このことはEXPLAINで確かめることができます:

EXPLAIN結果の抜粋
mysql> EXPLAIN ... ORDER BY articles.created_at ...
*************************** 1. row ***************************
        table: taggings
        Extra: Using where; Using temporary; Using filesort
*************************** 2. row ***************************
        table: articles

擬似コードではjoin_table変数に一時的にデータを格納していましたが、Using temporaryがそのことを表しています。そしてUsing filesortがインデックスではなく、クイックソートを使ってソートされたことを表します。

駆動表でORDER BY

ORDER BYが内部表にかかっているので、一旦全てのデータを作ってから並べ替える必要が生じるので遅くなるのでした。では駆動表にORDER BYがかかる場合はどうなのでしょう？

ここでは仮にtaggingsテーブルにarticle_created_atというカラムが存在したとします:

ALTER TABLE taggings ADD article_created_at DATETIME;

名前からも分かるように、対応するarticlesレコードのcreated_atと同じ値が格納されているとします。

すると、先ほどのSQLは次のように書き換えることができます:

あるタグの新着記事10件（駆動表で並べ替え版）
  SELECT articles.*
    FROM taggings, articles
   WHERE taggings.article_id = articles.id
     AND taggings.tag_id = 1
ORDER BY taggings.article_created_at DESC /* ここが変わった */
   LIMIT 10;

これを擬似コードにすると:

# taggingsを並べ替えて10件取得
for row1 in sort(fetch(taggings, { "tag_id": 1 }))[0:10]:
    # それぞれに対応するarticlesを取得する
    for row2 in fetch(articles, { "id": row1.id }):
        send_to_client(row2)

つまり、たとえタグ付けされた記事が100万件あっても、最新のもの10件だけを取り出せばいいので、forループが10回しか回らなくなるわけです。つまりn=10になります。

EXPLAINをみて確かめてみましょう:

EXPLAIN結果の抜粋
mysql> EXPLAIN ... ORDER BY taggings.article_created_at ...
*************************** 1. row ***************************
        table: taggings
        Extra: Using index condition; Using where; Using filesort
*************************** 2. row ***************************
        table: articles

ExtraにUsing temporaryが出てこないことから、一時テーブルが作られていないことが分かります。ただし、Using filesortがあるので、並べ替えにインデックスが使われていないことが分かります。

並べ替えの高速化

インデックスを追加して並べ替えを高速化しましょう。今回やりたいのはtag_idで絞り込んで、article_created_atで並べ替えることなので、必要になるインデックスは:

CREATE INDEX index_taggings_on_tag_id_and_article_created_at
  ON taggings(tag_id, article_created_at);

これを追加した上で改めてEXPLAINしてみると:

EXPLAIN結果の抜粋
mysql> EXPLAIN ... ORDER BY taggings.article_created_at ...
*************************** 1. row ***************************
        table: taggings
          key: index_taggings_on_tag_id_and_article_created_at
        Extra: Using where
*************************** 2. row ***************************
        table: articles

この場合も、以下のようなインデックスを作ることでカバリングインデックスにすることができます:

CREATE INDEX index_taggings_on_tag_id_and_article_created_at_and_article_id
  ON taggings(tag_id, article_created_at, article_id);

非正規化の是非

今回taggings.article_created_atを追加しましたが、これには問題があります。

article_idが同じtaggingsのレコードは全てarticle_created_atも同じになります。詳しくは専門書にゆずりますが、リレーショナルモデル的に言うならtaggingsデーブルには推移関数従属性があるといい、このようなテーブルを含むことを第2正規形といいます。

推移関数従属性があると更新不整合が生じる危険があります。端的に言えば、articles.created_atを更新したら、対応するtaggings.article_created_atも忘れずに更新しないとデータがおかしくなる、ということです。

なので、リレーショナルモデルを忠実に守ろうと思うと、article_created_atを追加することは悪となります。その一方で、速度を犠牲にはできないので、どこかに落とし所を探る必要があります。

一つの考え方として、MySQL界隈で著名な奥野幹也さんが最近ブログで書いていたのは

高速化のための非正規化という間違いだ。非正規化をしてしまうと当然ながら更新異常が発生するようになり、RDB本来の旨味が失われてしまう。RDB上のデータは正規化してナンボである。そもそも実装のために設計を捻じ曲げるようなことはするべきではない。

（中略）元の正規化したテーブルを捨て去って非正規化するのではなく、元の正規化したテーブルを残したまま、非正規化したデータを中間的なデータ、すなわちキャッシュとして新たに追加するというやり方である。

漢(オトコ)のコンピュータ道: RDBにおけるキャッシュという考え方

この考えに従うなら、taggingsにカラムを追加するのではなく、検索用途のための中間テーブルを別途用意するということになります。

それとは別に、個人として考えているのは、更新不整合が起こることが問題なのであれば、更新しないカラムは重複させてもいいのではないか、ということです。

created_atは挿入時に決定されてその後更新されないので、まぁいいんじゃないの？という気分です。だけどupdated_atはダメ、みたいな。

実際、参考文献にもある「データベース実践入門」の12章においてキャッシュが可能なデータの一例として長期に渡り変更される予定がないデータが挙げられています。（それでも非正規化は :no_good: と言われるかも知れませんが...）

おわりに

実際のJOIN SQLを例に、それが遅くなる理屈と対処法を見てみました。

実業務の中で扱うSQLは今回取り上げたように単純なものばかりではないと思いますが、そのような場合でも、内部動作に思いを馳せることでチューニングのとっかかりをつかむことができるのではないでしょうか。

参考URL・文献

3つのJoinアルゴリズムがそれぞれ説明してあって便利。絵を眺めてアルゴリズムの雰囲気つかみたい。

奥野さんの記事。NLJがどうこう、EXPLAINがうんぬんという話が丁寧に書いてある。

推移関数従属性とか正規形の話は第3章と第4章。大学時代にデータベースの講義を受けたことがある人なら「あーこんなこと勉強したなー」っていう気分に終始浸り続けられる。RDBの理論的背景に興味がある人にもオススメ。

  1. OracleとPostgreSQLは3つとも実装されています。 ↩

  2. ここでは関心のあるカラムだけを抽出して表示しています ↩

  3. と主キーもしくはストレージ上での位置の組。どちらになるかはRDBの実装次第。例えばMySQLのInnoDBだったら主キーが取得できます。なぜこうなっているかについては「クラスタインデックス」などで検索すると調べることができます。 ↩

1408
1260
8

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1408
1260

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?