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

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

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

環境

Oracle Database Express Edition 11g Release 2をWindows上で動作
Oracle SQL Developer 3.2

準備

検索対象となる適当なテーブルを作る。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