入れ子ループ


Applies to
DB2Yes
MySQLYes
OracleYes
PostgreSQLYes
SQL ServerYes

入れ子ループ結合(nested-loop join)は、最も基本的な結合アルゴリズムです。 これは、2つの入れ子になったクエリを使うような動作をします。外部あるいは駆動クエリが あるテーブルから結果を取り出し、2つ目のクエリがその結果のそれぞれの 行に対して、別のテーブルの対応するデータを取り出します。

入れ子ループアルゴリズムを自分で実装してみるなら、実際には「入れ子の select」を使うことになるでしょう。しかしこれは、ディスクのレイテンシを 上回る勢いでネットワークのレイテンシが増えるので、全体のレスポンスタイムが さらに悪くなってしまうという、厄介なアプローチです。それでも「入れ子の select」は、そういった問題を気にしなければ一番簡単に実装できるので、 非常によく使われる方法ではあります。ORM(Object-relational mapping)ツールは この観点では特に「便利な」ものです。いわゆるN+1問題が、 この分野で悪名の高いものでしょう。

このウェブサイトにぴったりのカップは僕たちのショップにあります。
#見た目もいい感じだし、ここでの僕の仕事を支えてくれています

以下は、各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 = ?;

ORMは結合を行うSQLは生成しませんが、代わりに SALESテーブルをselectの入れ子で検索します。このような動作を、 「N+1選択問題」あるいは単に「N+1問題」といいます。駆動クエリがN行を返す時に、N+1回のselectが 実行されてしまうためです。

Tweet this tip

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つの側面である、レスポンスタイムとスループット、 ネットワークの世界で言う、レイテンシ帯域が関係しています。帯域はレスポンスタイムに対しては大きく 影響しませんが、レイテンシには多大な影響を及ぼします。つまり、レスポンスタイムに 対しては、データ転送量より、データベースとのやりとりの回数の方が大きな影響が あるということです。

Tweet this tip

ヒント

結合はデータベース上で実行しましょう。

多くの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
query.distinct(true);

List<Employees> emp = em.createQuery(query).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
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 (UNQIUE)       |       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)

欲しい結果を得るために、UPPERwhereから削除されています。

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テーブルから各従業員に対する 対応するレコードを抽出しています。

Tweet this tip

ヒント

使用しているORMをよく知って、結合を コントロールしましょう。

ORMが違えば、結合を制御する方法も違います。 イーガーフェッチは、あらゆるORMで提供されている例というわけでは ありません。使っているORMの機能を調べる、小さなサンプルを作ってみるのは よい試みだと言えるでしょう。単なる練習に留まらず、開発中のリファレンスと しても役立ってくれるでしょうし、結合を使う時の副作用、例えば親レコードの重複と 言った、予期せぬ動作を洗い出す意味もあります。サンプルを ダウンロードして、試してみましょう。

入れ子のループ結合は、駆動クエリが小さな結果セットを返す時には、 よいパフォーマンスを発揮します。オプティマイザが、次の節で解説するハッシュ 結合のような全く別のアルゴリズムを選択することもあるでしょう。しかし、それは アプリケーションがデータベースに、何のデータが必要なのかを伝えた場合に のみ限ります。

Photo of Markus Winand
Markus Winand氏は、開発者がSQLパフォーマンスを改善するお手伝いをしています。 彼は、SQL Performance Explainedの 著者でもあり、出張トレーニングhttp://winand.at/での リモート講義も 行っています。