読者です 読者をやめる 読者になる 読者になる

kagamihogeの日記

kagamihogeの日記です。

ネステッドループジョインと反復連結

反復連結(Loop query)という単語はデータベースパフォーマンスアップの教科書 基本原理編から借りたもの。これは、JOINを使うのではなく、手続き的にテーブル間を連結するもの。親テーブルをフェッチしながら、子テーブルにキーで順次アクセスするやり方のことを指している。場合によってはその方が各種ジョイン方式よりも優れていることもある、らしい。

このエントリでは、ごくごく単純な状況下を想定して、ネステッドループジョインと反復連結にどの程度速度差が出るかを確かめる。

準備

検索対象となる適当なテーブルを作る。customerとordersが一対多を想定。

drop table customer purge;
create table customer 
(
  customer_id integer
, customer_name varchar2(10 byte) 
);

drop table orders purge;
create table orders 
(
  order_id integer 
, customer_id integer 
, amount integer 
);

データを作る。customer1件に対し、ordersが5件持たせることにする。下記のクエリ例は、customerに100万、ordersに500万件入れた場合の例。実テーブル内の行順序が、同一のcustomer_idが連続5件ずつ並び続けている。これはやや現実離れしたものだが、細かいことは気にしないことにする。

insert into customer
  select rownum, DBMS_RANDOM.STRING('X', 10)
    from 
      (select rownum from all_catalog where rownum <= 1000),
      (select rownum from all_catalog where rownum <= 1000)
commit;

insert into orders
  select rownum, CEIL(rownum/5), FLOOR(DBMS_RANDOM.VALUE(1, 100000))
    from 
      (select rownum from all_catalog where rownum <= 1000),
      (select rownum from all_catalog where rownum <= 1000),
      (select rownum from all_catalog where rownum <= 5);
commit;

非一意インデックスをordersテーブルのcustomer_idに作る。ネステッドループジョインの結合に使用する。

create index ind_orders_cust_id on orders (customer_id);

後述する速度検証用のJavaのコードにも再度出てくるが、重要なのはSELECTのSQLだけなのでここで抜粋しておく。

ネステッドループジョインのクエリ。ヒントによってジョイン方式は固定している。結合条件以外は何も無いので、両方のテーブルを全件アクセスすることになる。

select /*+ USE_NL(c o) */
       c.customer_id, c.customer_name, o.order_id, o.amount
from   customer c join orders o on c.customer_id = o.customer_id;

反復連結のクエリ。上側のクエリの結果をループで回してフェッチしながら、下側のクエリを実行して結果を取得する。

select customer_id, customer_name from customer;
select order_id, customer_id, amount from orders where customer_id = 1;

擬似コードで書けばこんな雰囲気。

curA = select c_id from customer
while (cursorA)
  curB = select .. from orders where c_id = curA.c_id
  while (curB)
    curB.fetch
    process..
  end
end

各検証用プログラムを走らせる前に、バッファキャッシュをクリアしておく。

alter system flush buffer_cache;

ネステッドループジョインの速度検証用プログラムはこんな感じ。ジョインしてるSQLを流してるだけ。

public class SelectJoin {

    private static final String sqlNLJoinCustOrders = 
          "select /*+ USE_NL(c o) */ "
        + "       c.customer_id, c.customer_name, o.order_id, o.amount "
        + "from   customer c join orders o on c.customer_id = o.customer_id";

    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        try (Connection connection = DriverManager.getConnection(
            "jdbc:oracle:thin:@192.168.0.12:1521:XE", "kagamihoge", "xxxx");
            PreparedStatement sqlCustStmt = connection.prepareStatement(sqlNLJoinCustOrders);) {

            ResultSet custToOrders = sqlCustStmt.executeQuery();
            while (custToOrders.next()) {
                System.out.println(custToOrders.getInt(1) + " " + custToOrders.getString(2) + " "
                    + custToOrders.getInt(3) + " " + custToOrders.getInt(4));
            }
        } catch (SQLException e) {
            e.printStackTrace();
        }

        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }
}

反復連結の速度検証用プログラムはこんな感じ。

public class SelectLoopJoin {

    private static final String sqlAllCustomer = 
        "select customer_id, customer_name from customer";
    private static final String sqlOrdersByCustId =
        "select order_id, customer_id, amount from orders where customer_id = ?";
    
    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        try (Connection connection = DriverManager.getConnection(
            "jdbc:oracle:thin:@192.168.0.12:1521:XE", "kagamihoge", "xxxx");
            PreparedStatement sqlCustStmt = connection.prepareStatement(sqlAllCustomer);
            PreparedStatement sqlOrdStmt = connection.prepareStatement(sqlOrdersByCustId);) {

            ResultSet custs = sqlCustStmt.executeQuery();
            while (custs.next()) {
                int id = custs.getInt(1);
                String name = custs.getString(2);
                System.out.println(id + " " + name);
                accessOrdersByCustomerId(sqlOrdStmt, id);
            }

        } catch (SQLException e) {
            e.printStackTrace();
        }

        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }

    private static void accessOrdersByCustomerId(PreparedStatement sqlStmt, int id)
        throws SQLException {
        sqlStmt.setInt(1, id);

        ResultSet orders = sqlStmt.executeQuery();
        while (orders.next()) {
            System.out.println(orders.getInt(1) + " " + orders.getInt(2) + " " + orders.getInt(3));
        }
        orders.close();
    }
}

実行結果

上側がネステッドループ、下側が反復連結のもの。

CUSTOMERの件数 1 2 3 AVG
1000 1218 1110 969 1099
  1438 1422 1437 1432
10000 4765 4797 4594 4719
  8187 8266 8313 8255
100000 29750 34593 33031 32458
  65109 65000 64828 64979
1000000 325831 358781 354375 346329
  679489 690063 695325 688292

まぁさすがにこんだけカンタンな比較だと、フツーにジョインしたほうが速い。反復連結の方が遅いのは、クエリの発行回数分だけ足かせになってる感じ。