入れ子ループ結合(nested-loop join)は、最も基本的な結合アルゴリズムです。 これは、2つの入れ子になったクエリを使うような動作をします。外部あるいは駆動クエリが あるテーブルから結果を取り出し、2つ目のクエリがその結果のそれぞれの 行に対して、別のテーブルの対応するデータを取り出します。
入れ子ループアルゴリズムを自分で実装してみるなら、実際には「入れ子の select」を使うことになるでしょう。しかしこれは、ディスクのレイテンシを 上回る勢いでネットワークのレイテンシが増えるので、全体のレスポンスタイムがさらに悪くなってしまうという、厄介なアプローチです。それでも「入れ子の select」は、そういった問題を気にしなければ一番簡単に実装できるので、 非常によく使われる方法ではあります。ORM(Object-relational mapping)ツールは この観点では特に「便利な」ものです。いわゆるN+1問題が、 この分野で悪名の高いものでしょう。
協力してください
この記事が気に入ったら、私の書いた本「SQLパフォーマンス詳解」や私によるトレーニングもきっと気にいるはず。
以下は、各ORMツールによって生成された「意図しない入れ子のselect」に
よる結合の例です。ここでは、姓が'WIN'
で始まっている従業員を
検索し、それぞれの従業員の売上(SALES
)を取得する例になっています。
- Java
JPAの例では、CriteriaBuilder インタフェースを使用しています。
CriteriaBuilder queryBuilder = em.getCriteriaBuilder(); CriteriaQuery<Employees> query = queryBuilder.createQuery(Employees.class); Root<Employees> r = query.from(Employees.class); query.where( queryBuilder.like( queryBuilder.upper(r.get(Employees_.lastName)), "WIN%" ) ); List<Employees> emp = em.createQuery(query).getResultList(); for (Employees e: emp) { // process Employee for (Sales s: e.getSales()) { // process sale for Employee } }
Hibernate JPA 3.6.0は、N+1
select
のクエリを生成してしまいます。select employees0_.subsidiary_id as subsidiary1_0_ -- MORE COLUMNS from employees employees0_ where upper(employees0_.last_name) like ?
select sales0_.subsidiary_id as subsidiary4_0_1_ -- MORE COLUMNS from sales sales0_ where sales0_.subsidiary_id=? and sales0_.employee_id=?
select sales0_.subsidiary_id as subsidiary4_0_1_ -- MORE COLUMNS from sales sales0_ where sales0_.subsidiary_id=? and sales0_.employee_id=?
- Perl
以下の例では、PerlのDBIx::Class フレームワークの動作を表しています。
my @employees = $schema->resultset('Employees') ->search({'UPPER(last_name)' => {-like=>'WIN%'}}); foreach my $employee (@employees) { # process Employee foreach my $sale ($employee->sales) { # process Sale for Employee } }
DBIx::Class 0.08192は、N+1
select
のクエリを発行してしまいます。SELECT me.employee_id, me.subsidiary_id , me.last_name, me.first_name, me.date_of_birth FROM employees me WHERE ( UPPER(last_name) LIKE ? )
SELECT me.sale_id, me.employee_id, me.subsidiary_id , me.sale_date, me.eur_value FROM sales me WHERE ( ( me.employee_id = ? AND me.subsidiary_id = ? ) )
SELECT me.sale_id, me.employee_id, me.subsidiary_id , me.sale_date, me.eur_value FROM sales me WHERE ( ( me.employee_id = ? AND me.subsidiary_id = ? ) )
- PHP
Doctrineのサンプルでは、 クエリビルダインタフェースを使用しています。
$qb = $em->createQueryBuilder(); $qb->select('e') ->from('Employees', 'e') ->where("upper(e.last_name) like :last_name") ->setParameter('last_name', 'WIN%'); $r = $qb->getQuery()->getResult(); foreach ($r as $row) { // process Employee foreach ($row->getSales() as $sale) { // process Sale for Employee } }
Doctrine 2.0.5は、N+1
select
クエリを生成してしまいます。SELECT e0_.employee_id AS employee_id0 -- MORE COLUMNS FROM employees e0_ WHERE UPPER(e0_.last_name) LIKE ?
SELECT t0.sale_id AS SALE_ID1 -- MORE COLUMNS FROM sales t0 WHERE t0.subsidiary_id = ? AND t0.employee_id = ?
SELECT t0.sale_id AS SALE_ID1 -- MORE COLUMNS FROM sales t0 WHERE t0.subsidiary_id = ? AND t0.employee_id = ?
SALES
テーブルをselectの入れ子で検索します。このような動作を、
「N+1選択問題」あるいは単に「N+1問題」といいます。駆動クエリがN行を返す時に、N+1回のselectが実行されてしまうためです。SQLのロギングを有効にする
開発中はSQLのロギングを有効にし、 生成されたSQL文のレビューをしましょう。
- DBIx::Class
export DBIC_TRACE=1
をシェルで 実行。- Doctrine
ソースコードレベルでのみ設定可。本番環境で出力しないようにするのを忘れずに。設定変更可能なロガーを自分で 実装することも考えた方がよいでしょう。
$logger = new \Doctrine\DBAL\Logging\EchoSqlLogger; $config->setSQLLogger($logger);
- Hibernate (ネイティブ)
App.config
あるいはhibernate.cfg.xml
で、<property name="show_sql">true</property>
を設定。- JPA
eclipselink, Hibernate and OpenJPAといった JPAプロバイダに依存しますが、
persistence.xml
で以下を設定。<property name="eclipselink.logging.level" value="FINE"/> <property name="hibernate.show_sql" value="TRUE"/> <property name="openjpa.Log" value="SQL=TRACE"/>
ほとんどのORMでは、SQLロギングを有効にするのはプログラミング的な 方法で提供されています。意図せずこの設定が本番にデプロイされてしまう可能性があります。
「入れ子のselect」のアプローチはアンチパターンではありますが、
入れ子ループ結合の仕組みをうまく表したものでもあります。
データベースは、上のORMツールの生成した通りに結合を実行します。入れ子ループ結合用のインデックスは、上に出てきたようなselect
文に対する
インデックスとほぼ同じになります。つまり、EMPLOYEES
テーブルに対する関数インデックスと、SALES
テーブルの結合述語に対する
複合インデックスです。
CREATE INDEX emp_up_name ON employees (UPPER(last_name))
CREATE INDEX sales_emp ON sales (subsidiary_id, employee_id)
SQLの結合処理は、入れ子のselectのアプローチよりは多少効率的です。 同じようにインデックスの走査を行いますが、ネットワーク上の通信は大部分がなくなるからです。 売上に対して従業員の属性が重複しているので、転送されるデータの総量が大きくなっていても、 結合の方が高速でしょう。これには、パフォーマンスの2つの側面である、レスポンスタイムとスループット、 ネットワークの世界で言う、レイテンシと 帯域が関係しています。帯域はレスポンスタイムに対しては大きく 影響しませんが、レイテンシには多大な影響を及ぼします。つまり、レスポンスタイムに 対しては、データ転送量より、データベースとのやりとりの回数の方が大きな影響があるということです。
ヒント
結合はデータベース上で実行しましょう。
多くのORMでは、結合を行うSQLを生成する方法が提供されて
います。いわゆるイーガーフェッチ(eager fetching)モードは
最も重要なものです。これは、エンティティのマッピングを行う際のプロパティ
レベルで、つまり例えばSales
クラスのemployees
プロパティに
対して設定されるのが一般的です。これにより、ORMツールはSALES
テーブルにアクセスする時、常にEMPLOYEES
テーブルとの結合を
行うようになります。売上の情報を見る時いつも従業員の情報も必要になる場合にのみ、エンティティのマッピングの際にイーガーフェッチを設定する
意味があります。
親オブジェクトにアクセスする時、常に子のレコードも必要になるので ない限り、イーガーフェッチは逆効果になります。電話帳アプリケーションで、従業員の詳細を表示する際に、売上の情報も表示する必要はないでしょう。 ある時は売上の情報が必要になるかもしれませんが、常に必須な訳ではないので、静的に設定してしまうのは解決策にはなりません。
パフォーマンス最適化のためには、結合処理を完全な制御下に置く必要があります。以下の例では、実行時に結合の動作を制御することで、最高の 柔軟性を得るための方法を示します。
- Java
JPAの
CriteriaBuilder
インタフェースでは、結合の制御にRoot<>.fetch()
メソッドが 提供されています。これにより、メインクエリの中で対象のオブジェクトを いつどのように結合するかを指定できるようになります。この例では、 売上を持っていない者も含めて全従業員を得るために、左外部結合(left join)しています。警告
JPAとHibernateは、各売上に対する従業員を 返します。
つまり、30の売上を持つ従業員は30回出現してしまうという ことです。これはかなり厄介ではありますが、既定の動作です(EJB 3.0 persistencyの4.4.5.3「Fetch Joins」)。
CriteriaBuilder qb = em.getCriteriaBuilder(); CriteriaQuery<Employees> q = qb.createQuery(Employees.class); Root<Employees> r = q.from(Employees.class); q.where(queryBuilder.like( queryBuilder.upper(r.get(Employees_.lastName)), "WIN%") ); r.fetch("sales", JoinType.LEFT); // needed to avoid duplication of Employee records q.distinct(true); List<Employees> emp = em.createQuery(q).getResultList();
Hibernate 3.6.0は、以下のSQL文を生成します。
select distinct employees0_.subsidiary_id as subsidiary1_0_0_ , employees0_.employee_id as employee2_0_0_ -- MORE COLUMNS , sales1_.sale_id as sale1_0__ from employees employees0_ left outer join sales sales1_ on employees0_.subsidiary_id=sales1_.subsidiary_id and employees0_.employee_id=sales1_.employee_id where upper(employees0_.last_name) like ?
クエリは予想通り左外部結合になっていますが、必要のない
distinct
キーワードも含んでいます。残念ながら、JPAでは子のレコードの 重複を排除せずに親の重複エントリをフィルタする個別のAPIコールは用意されていません。ほとんどのデータベースは重複したレコードを フィルタするので、SQLクエリにdistinct
キーワードが あるのは気になるところです。このケースでは、一部のデータベースだけが、 プライマリキーによって一意性が保たれているという判断ができます。ネイティブなHibernate APIは、結果セットの変換の仕組みを使って クライアントサイドでこの問題を解決します。
Criteria c = session.createCriteria(Employees.class); c.add(Restrictions.ilike("lastName", 'Win%')); c.setFetchMode("sales", FetchMode.JOIN); c.setResultTransformer(Criteria.DISTINCT_ROOT_ENTITY); List<Employees> result = c.list();
これは以下のクエリを 生成します。
select this_.subsidiary_id as subsidiary1_0_1_ , this_.employee_id as employee2_0_1_ -- MORE this_ columns on employees , sales2_.sale_id as sale1_3_ -- MORE sales2_ columns on sales from employees this_ left outer join sales sales2_ on this_.subsidiary_id=sales2_.subsidiary_id and this_.employee_id=sales2_.employee_id where lower(this_.last_name) like ?
この 方法だと、意図しない句を含まないストレートなSQL文が生成されます。Hibernateは大文字小文字を区別しない クエリに
lower()
を使うことに注意しましょう。重要な詳細は関数インデックスに書かれています。- Perl
以下は、PerlのDBIx::Class フレームワークを使った例です。
my @employees = $schema->resultset('Employees') ->search({ 'UPPER(last_name)' => {-like => 'WIN%'} , {prefetch => ['sales']} });
DBIx::Class 0.0819は、以下のSQL文を生成します。
SELECT me.employee_id, me.subsidiary_id, me.last_name -- MORE COLUMNS FROM employees me LEFT JOIN sales sales ON (sales.employee_id = me.employee_id AND sales.subsidiary_id = me.subsidiary_id) WHERE ( UPPER(last_name) LIKE ? ) ORDER BY sales.employee_id, sales.subsidiary_id
アプリケーションでは要求していない
order by
句があることに注意しましょう。データベースは結果セットを並べ替えする 必要があり、それにはある程度の時間がかかることになります。- PHP
以下は、PHPのDoctrine フレームワークを使った例です。
$qb = $em->createQueryBuilder(); $qb->select('e,s') ->from('Employees', 'e') ->leftJoin('e.sales', 's') ->where("upper(e.last_name) like :last_name") ->setParameter('last_name', 'WIN%'); $r = $qb->getQuery()->getResult();
Doctrine 2.0.5は、以下のSQL文を生成します。
SELECT e0_.employee_id AS employee_id0 -- MORE COLUMNS FROM employees e0_ LEFT JOIN sales s1_ ON e0_.subsidiary_id = s1_.subsidiary_id AND e0_.employee_id = s1_.employee_id WHERE UPPER(e0_.last_name) LIKE ?
実行計画には、NESTED LOOPS OUTER
の処理が行われていると出ています。
- Db2 (LUW)
Explain Plan --------------------------------------------------------------- ID | Operation | Rows | Cost 1 | RETURN | | 10501 2 | NLJOIN (LEFT) | 5745 of 57 | 10501 3 | FETCH EMPLOYEES | 57 of 57 (100.00%) | 49 4 | RIDSCN | 57 of 57 (100.00%) | 6 5 | SORT (UNIQUE) | 57 of 57 (100.00%) | 6 6 | IXSCAN EMP_NAME | 57 of 10000 ( .57%) | 6 7 | FETCH SALES | 101 of 101 (100.00%) | 183 8 | IXSCAN SALES_SUB_EMP | 101 of 1011118 ( .01%) | 13 Predicate Information 2 - JOIN (Q2.EMPLOYEE_ID = Q3.EMPLOYEE_ID) JOIN (Q2.SUBSIDIARY_ID = Q3.SUBSIDIARY_ID) 3 - SARG (Q1.LAST_NAME LIKE ?) 6 - START ($INTERNAL_FUNC$() <= Q1.LAST_NAME) STOP (Q1.LAST_NAME <= $INTERNAL_FUNC$()) SARG (Q1.LAST_NAME LIKE ?) 8 - START (Q2.SUBSIDIARY_ID = Q3.SUBSIDIARY_ID) START (Q2.EMPLOYEE_ID = Q3.EMPLOYEE_ID) STOP (Q2.SUBSIDIARY_ID = Q3.SUBSIDIARY_ID) STOP (Q2.EMPLOYEE_ID = Q3.EMPLOYEE_ID)
欲しい結果を得るために、
UPPER
はwhere
から削除されています。- Oracle
--------------------------------------------------------------- |Id |Operation | Name | Rows | Cost | --------------------------------------------------------------- | 0 |SELECT STATEMENT | | 822 | 38 | | 1 | NESTED LOOPS OUTER | | 822 | 38 | | 2 | TABLE ACCESS BY INDEX ROWID| EMPLOYEES | 1 | 4 | |*3 | INDEX RANGE SCAN | EMP_UP_NAME | 1 | | | 4 | TABLE ACCESS BY INDEX ROWID| SALES | 821 | 34 | |*5 | INDEX RANGE SCAN | SALES_EMP | 31 | | --------------------------------------------------------------- Predicate Information (identified by operation id): --------------------------------------------------- 3 - access(UPPER("LAST_NAME") LIKE 'WIN%') filter(UPPER("LAST_NAME") LIKE 'WIN%') 5 - access("E0_"."SUBSIDIARY_ID"="S1_"."SUBSIDIARY_ID"(+) AND "E0_"."EMPLOYEE_ID" ="S1_"."EMPLOYEE_ID"(+))
データ ベースは、EMP_UP_NAME
を使ってEMPLOYEES
テーブルから
結果を取り出し、その後、SALES
テーブルから各従業員に対する対応するレコードを抽出しています。
ヒント
使用しているORMをよく知って、結合をコントロールしましょう。
ORMが違えば、結合を制御する方法も違います。 イーガーフェッチは、あらゆるORMで提供されている例というわけでは ありません。使っているORMの機能を調べる、小さなサンプルを作ってみるのは よい試みだと言えるでしょう。単なる練習に留まらず、開発中のリファレンスと しても役立ってくれるでしょうし、結合を使う時の副作用、例えば親レコードの重複と言った、予期せぬ動作を洗い出す意味もあります。サンプルを ダウンロードして、試してみましょう。
入れ子のループ結合は、駆動クエリが小さな結果セットを返す時には、 よいパフォーマンスを発揮します。オプティマイザが、次の節で解説するハッシュ 結合のような全く別のアルゴリズムを選択することもあるでしょう。しかし、それはアプリケーションがデータベースに、何のデータが必要なのかを伝えた場合に のみ限ります。
関連情報
サンプル用の
CREATE
及びINSERT
文「レイテンシ : セキュリティ vs. パフォーマンス」ネットワークレイテンシと SQLのパフォーマンスに関するブログ記事