OR条件よりもUNIONの方が速い！

SQL 実験

一週間悩んで、やっと分かったのでメモ。


こういうSQLの場合、前者よりも後者の方が速いです。

SELECT 
  *
FROM 
  FooTable 
    LEFT OUTER JOIN BarTable1 ON FooTable.ID = BarTable1.ID 
      LEFT OUTER JOIN BarTable2 ON BarTable1.F_ID = BarTable2.ID 
        LEFT OUTER JOIN BarTable3 ON BarTable2.F_ID = BarTable3.ID 
          LEFT OUTER JOIN BarTable4 ON BarTable3.F_ID = BarTable4.ID 
            LEFT OUTER JOIN BarTable5 ON BarTable4.F_ID = BarTable5.ID 
WHERE 
  FooTable.Name = ? OR
  BarTable5.Name = ?

( SELECT 
    *
  FROM 
    FooTable 
      LEFT OUTER JOIN BarTable1 ON FooTable.ID = BarTable1.ID 
        LEFT OUTER JOIN BarTable2 ON BarTable1.F_ID = BarTable2.ID 
          LEFT OUTER JOIN BarTable3 ON BarTable2.F_ID = BarTable3.ID 
            LEFT OUTER JOIN BarTable4 ON BarTable3.F_ID = BarTable4.ID 
              LEFT OUTER JOIN BarTable5 ON BarTable4.F_ID = BarTable5.ID 
  WHERE 
    FooTable.Name = ?
) UNION (
  SELECT 
    *
  FROM 
    FooTable 
      LEFT OUTER JOIN BarTable1 ON FooTable.ID = BarTable1.ID 
        LEFT OUTER JOIN BarTable2 ON BarTable1.F_ID = BarTable2.ID 
          LEFT OUTER JOIN BarTable3 ON BarTable2.F_ID = BarTable3.ID 
            LEFT OUTER JOIN BarTable4 ON BarTable3.F_ID = BarTable4.ID 
              LEFT OUTER JOIN BarTable5 ON BarTable4.F_ID = BarTable5.ID 
  WHERE 
    BarTable5.Name = ?
)

（FooTableが約一万行、BarTable1以降が約千行、環境はPostgreSQL 8.2）
（BarTable1以降のF_IDはNULLのことがあり、結合順序は入れ替えられない）


意外なことに、OR条件で1回SELECTするよりも、2回SELECTしてUNIONでマージした方が速いという結果になりました。

なんで？

実は、やっていて気付いたのですが前者のSQLではインデックスが使われません。
解析した結果、

  1. BarTable1〜BarTable5までを全行シーケンシャルで読んでハッシュ結合
  2. 1で生成したテーブルとFooTableを全行シーケンシャルで読んでハッシュ結合
  3. 行を選択

という動作をしているようです。

動作の理由

IDの部分にはインデックスが貼ってあるのでそれを使った入れ子反復結合(Nested Loop Join)になるかと思ったんですが、全行結合するので、ハッシュ結合の方が効率がいいと判断した模様。
また、FooTable.Nameにインデックス貼っても、選択は結合した後のテーブルに対してなので使用されませんでした。


FooTableから順にJOINしていないのは、順にすると約一万行の結合が5回になってしまうからです。
対して、BarTable1以降を先にすると、約千行の結合が4回に約一万行の結合が1回になるので、こちらの方が少ない行数ですみます。
（SQLを変えて無理やりFooTableから順に結合させたら、逆に遅くなりました）
早い段階で行を選択していないで最後にやってるのは、ORだからどっちに引っかかるか分からないためです。

改良結果

以上を踏まえて改良したのが後者です。


こうすることにより、前半のSQLは結合するまで選択できないということが無くなったので、
最初にFooTableに対する選択が行われるようになりました。
また、この選択は結合前のテーブルで行われるので、FooTable.Nameへのインデックスも使用します。
選択の結果、FooTableの行数が少なくなるので、あとのテーブルとは入れ子反復結合で結ばれていきます。


後半のSQLは、真っ先にBarTable5の選択をして、それからBarTable4〜1と結合されていきます。
こちらもインデックスが使用されるので高速。


最終的に、今回のケースでは約10倍(80ms -> 8ms)速くなりました。


感想

当初は、FooTable.Nameにインデックス張ればいいんだぐらいに考えていたんですが・・・甘かった。
SQLは奥が深いですね。


まだまだ力量不足です　orz




(2010/02/17 追記)
当初、後半のSQLは動作に変わりがないと書いたんですが、改めて調べたらインデックスが使われていました。
また速度もUNIONを使うことにより4倍速くなると書いていましたが、10倍になったことを確認しました。
この部分について、記述を修正しました。