Shoeisha Technology Media

EnterpriseZine(エンタープライズジン)

EnterpriseZine(エンタープライズジン)

テーマ別に探す

001 MySQLにおけるJOINのチューニングの定石

edited by DB Online   2011/10/18 07:00

つい最近、最新の開発版であるMySQL 5.6.3 m6がリリースされたが、このバージョンにはBatched Key Access JOIN(以下BKA JOIN)という新しいJOINのアルゴリズムが組み込まれている。その他にもMySQL 5.6ではいくつかオプティマイザの改良が行われているので、条件に合致すれば同じクエリを実行した場合でも、以前のバージョンより効率的な実行計画になるだろう。データベースエンジニアにとって、クエリのチューニングは必須スキルであるが、BKA JOINについて理解するためには、MySQLがどのようにJOINを実行するかということについて知っておく必要がある。そこで、本エントリではまずMySQLにおけるJOINのチューニングの定石について解説する。

Nested Loop Join

 実は、MySQLが実装しているJOINのアルゴリズムは、Nested Loop Join(以下NLJ)とその変化形だけである。MySQL 5.6.3で新たに加わったBKA JOINも、ある条件下においてNLJを高速化したアルゴリズムであると見做すことができる。他のRDBMSではマージソートJOINやハッシュJOINといったアルゴリズムが実装されているものが多いが、MySQLはそれらのアルゴリズムには今のところ無縁である。

 NLJとは一体いかなるアルゴリズムであるか。本稿の読者の多くはご存知のことだろうが、JOINの最適化を考える上でアルゴリズムの理解は欠かせないので、ここで改めて解説しよう。NLJについて熟知している人は読み飛ばして頂いて結構だ。

 NLJはその名が示すように、基本となるアルゴリズムはループである。t1とt2という2つのテーブルを条件を指定せずに結合する場合、つまり直積(Product)を実行する場合のアルゴリズムは次のようになる。

for each row in t1 {
  for each row in t2 {
    send joined row to client
  }
}

 このようにNLJの処理はループになっており、テーブル数が増えればループのネストがどんどん深くなる。通常、直積が必要となるケースは稀であり、結合の条件を指定したり、それぞれのテーブルからフェッチする行について条件を指定するため、NLJのアルゴリズムは次のようになる。

for each row in t1 matching where condition {
  for each row in t2 matching join and where condition {
    send joined row to client
  }
}


著者プロフィール

バックナンバー

連載:MySQLチューニング虎の巻
All contents copyright © 2007-2019 Shoeisha Co., Ltd. All rights reserved. ver.1.5