ヘッダーをスキップ
Oracle® Database SQLチューニング・ガイド
12cリリース1(12.1)
B71277-02
  ドキュメント・ライブラリへ移動
ライブラリ
製品リストへ移動
製品
目次へ移動
目次
索引へ移動
索引

前
 
次
 

7 結合

この章の内容は次のとおりです。

結合について

結合によって、表やビューなどの2つの行ソースの出力が結合され、1つの行ソースが返されます。返される行ソースはデータ・セットです。

結合の特徴は、SQL文のWHERE (非ANSI)句内またはFROM ... JOIN (ANSI)句内に複数の表が並んでいる点です。FROM句に複数の表が指定されている場合は、必ず結合が実行されます。

結合条件によって、式を使用して2つの行ソースが比較されます。結合条件で、表間の関係が定義されます。文に結合条件が指定されていない場合は、デカルト結合が実行され(「デカルト結合」を参照)、一方の表のすべての行が他方の表のすべての行と照会されます。

http://techbus.safaribooksonline.com/book/databases/oracle/9781590599174/chapter-10-optimizing-joins/409?uicode=oracle

関連項目:

Oracle SQLにおける結合の簡潔な説明は、『Oracle Database SQL言語リファレンス』を参照してください。

結合ツリー

通常、結合ツリーは上下逆のツリー構造で表されます。図7-1に示すように、table1が左の表で、table2が右の表です。オプティマイザによって、結合は左から右に処理されます。たとえば、この図がネステッド・ループ結合を示しているならば、table1が外部ループでtable2が内部ループです。

図7-1 結合ツリー

図7-1の説明が続きます
「図7-1 結合ツリー」の説明

結合の入力は、以前の結合の結果セットの場合もあります。結合ツリーに3つ以上の分岐が含まれている場合に、最も一般的なツリーのタイプは、左側の深いツリーです(図7-2に示します)。左側の深いツリーは、すべての結合が以前の結合からの入力を有し、この入力が常に左側にくる結合ツリーです。

図7-2 左側の深い結合ツリー

図7-2の説明が続きます
「図7-2 左側の深い結合ツリー」の説明

あまり一般的でないタイプの結合ツリーが右結合ツリーで(図7-3に示します)、すべての結合が以前の結合からの入力を有し、この入力が常に右側にきます。

図7-3 右側の深い結合ツリー

図7-3の説明が続きます
「図7-3 右側の深い結合ツリー」の説明

一部の結合ツリーは左ツリーと右ツリーのハイブリッドであり、以前の結合からの入力が右側にくる結合と左側にくる結合があります。図7-4にこのタイプのツリーの例を示します。

図7-4 左結合および右結合のハイブリッド・ツリー

図7-4の説明が続きます
「図7-4 左結合および右結合のハイブリッド・ツリー」の説明

さらにもう1つのバリエーションでは、結合の両側の入力が以前の結合の結果になります。

オプティマイザによる結合文の実行方法

データベースでは、行ソースのペアが結合されます。FROM句に複数の表が指定されている場合は、各ペアにとってどの結合操作が最も効率的かが、オプティマイザによって決定されます。オプティマイザによって、次の相関的な決定が下される必要があります。

  • アクセス・パス

    単純な文では、オプティマイザは、結合文の各表からデータを取り出すアクセス・パスを選択する必要があります。たとえば、全表スキャンが選択される場合や索引スキャンが選択される場合があります。第6章「オプティマイザのアクセス・パス」を参照してください。

  • 結合方法

    行ソースの各ペアを結合するためには、いかに結合するかが決定される必要があります。いかに、とは結合方法のことです。有効な結合方法には、ネステッド・ループ結合、ソート/マージ結合およびハッシュ結合があります。デカルト結合には前述の結合方法のいずれかが必要です。それぞれの結合方法は、特定の状況において他の結合方法より優れています。「結合方法」を参照してください。

  • 結合タイプ

    結合条件によって結合タイプが決定されます。たとえば、内部結合では結合条件に一致した行のみが取得されます。外部結合では結合条件に一致しない行も取得されます。「結合タイプ」を参照してください。

  • 結合順序

    Oracle Databaseでは、3つ以上の表を結合する文を実行する場合、2つの表を結合し、その結果作成された行ソースを次の表に結合します。このプロセスは、すべての表が結合されて結果が生成されるまで続きます。たとえば、2つの表が結合され、その結果が3つ目の表に結合され、その結果が4つ目の表に結合され、これが繰り返されます。

オプティマイザによる結合の実行計画の選択方法

オプティマイザによって実行計画が選択される場合、次の要素が考慮されます。

  • 2つ以上の表を結合した結果が、最大1行の行ソースになるかどうかが最初に判断されます。

    オプティマイザは、このような状況を表のUNIQUE制約およびPRIMARY KEY制約に基づいて認識します。このような状況が存在する場合、オプティマイザはこれらの表を結合順序の最初に並べます。その後で、残りの表の結合を最適化します。

  • 外部結合条件を持つ結合文では、外部結合演算子のある表の結合順序は、通常、条件内のその他の表の後になります。

    一般には、このガイドラインに違反する結合順序が考慮されることはありませんが、特定の状況では、この順序付け条件がオーバーライドされます。同様に、副問合せがアンチ結合またはセミ結合に変換されたときは、その副問合せからの表は、それらが接続または相互に関連付けされた外部問合せブロック内の表の後に置きます。ただし、ある環境では、ハッシュ・アンチ結合およびセミ結合はこの順序条件を上書きできます。

オプティマイザは、適用可能な結合順序、結合方法および使用可能なアクセス・パスに従って実行計画のセットを生成します。次に、オプティマイザは各計画のコストを見積り、コストが最も小さいものを選択します。

オプティマイザによって、問合せ計画で実行される推定のI/Oと計画に必要な推定のCPUが計算されて、問合せ計画のコストが推定されます。これらのI/Oには、付随する固有のコストがあり、単一ブロックI/OのコストとマルチブロックI/Oのコストは違います。また、異なる関数と式には、それぞれに付随するCPUコストがあります。これらのメトリックが使用されて、問合せ計画の合計コストが決定されます。これらのメトリックは、多くの初期化パラメータやセッション設定(DB_FILE_MULTI_BLOCK_READ_COUNT設定やシステム統計など)からコンパイル時に影響を受ける可能性があります。

たとえば、オプティマイザによるコストの推定は次のように行われます。

  • ネステッド・ループ結合のコストは、外部表で選択されている各行およびその行に対する内部表の一致行をメモリーに読み取るコストによって決まります。オプティマイザは、データ・ディクショナリ内の統計を使用してこれらのコストを見積ります(「オプティマイザ統計の概要」を参照)。

  • ソート/マージ結合のコストは、主に、すべてのソースをメモリーに読み取ってソートするコストによって決まります。

  • ハッシュ結合のコストは、主に、結合への入力側の1つ上にハッシュ表を作成するコストと、それを調べるために結合のもう一方の側からの行を使用するコストによって決まります。


関連項目:

  • オプティマイザ・ヒントの詳細は、第14章「オプティマイザへの影響」を参照してください。

  • DB_FILE_MULTIBLOCK_READ_COUNTの詳細は、『Oracle Databaseリファレンス』を参照してください。


結合方法

結合方法は、2つの行ソースを結合するメカニズムです。統計に従って、推定コストの最も低い方法がオプティマイザによって選択されます。

図7-5に示すように、各結合方法には2つの子があります: 駆動(外部とも呼ばれる)行ソースおよび被駆動(内部とも呼ばれる)行ソースです。

この項の内容は次のとおりです。

ネステッド・ループ結合

ネステッド・ループは、外部データ・セットを内部データ・セットに結合します。単一表述語に一致する外部データ・セットの各行に対して、結合述語を満たす内部データ・セットのすべての行が取得されます。索引が使用可能な場合は、索引を使用して行IDで内部データ・セットにアクセス可能です。

この項の内容は次のとおりです。

オプティマイザがネステッド・ループ結合を考慮する場合

ネステッド・ループ結合は、次の条件に該当する場合に役立ちます。

  • データの小さなサブセットが結合されるか、オプティマイザ・モードがFIRST_ROWSに設定されて大きなデータ・セットが結合されます(表14-1を参照)。


    注意:

    オプティマイザの判断要因は、元になる表のサイズではなく、結合から予想される行数です。たとえば、それぞれが10億行を持つ2つの表を結合する問合せにおいても、フィルタのために、オプティマイザで予想されているデータ・セット数は各表で5行の場合があります。

  • この結合条件が内部表へのアクセスの効率的な方法です。

一般に、ネステッド・ループ結合は、結合条件の索引を持つ小さな表で最適に動作します。主キー値による等価検索(たとえば、WHERE employee_id=101など)と同様に、行ソースに1行しかない場合、この結合は単純な検索です。オプティマイザでは、常に最小の行ソースを駆動表として、その処理が最初に試みられます。

オプティマイザでネステッド・ループの使用が決定されるには、様々な要素が関係します。たとえば、1つのバッチで外部行ソースから複数行が読み取られるとします。オプティマイザで、内部行ソースに対してネステッド・ループ結合が選択されるかハッシュ結合が選択されるかは、取得される行数に基づいて決定される可能性があります(「適応計画」を参照してください)。たとえば、問合せでdepartmentsを駆動表employeesに結合し、述語にemployees.last_nameの値を指定する場合、last_nameの索引から、内部しきい値を超えたかどうかを判断するのに十分なエントリが読み取られることがあります。しきい値を超えていない場合は、departmentsに対してネステッド・ループ結合が選択され、しきい値を超えている場合は、ハッシュ結合が実行されます(つまり、employeesの残りが読み取られてメモリーにハッシュされてからdepartmentsに結合されます)。

内部ループのアクセス・パスが外部ループに依存していない場合は、結果はデカルト積になる可能性があり、外部ループの反復ごとに、内部ループで同じ行セットが生成されます。この問題を回避するには、2つの独立した行ソースの結合には、他の結合方法を使用することをお薦めします。

ネステッド・ループ結合の仕組み

ネステッド・ループを、ネストされた2つのforループだと考えてください。たとえば、問合せでemployeesdepartmentsが結合される場合、擬似コードでネステッド・ループを表すと次のようになります。

FOR erow IN (select * from employees where X=Y) LOOP
  FOR drow IN (select * from departments where erow is matched) LOOP
    output values from erow and drow
  END LOOP
END LOOP

内部ループは、外部ループの各行ごとに実行されます。employees表が外部データ・セットと呼ばれるのは、それが外側のforループであるためです。外部表は、駆動表と呼ばれることもあります。departments表が内部データ・セットと呼ばれるのは、それが内側のforループであるためです。

ネステッド・ループ結合には、次の基本手順が含まれます。

  1. オプティマイザによって駆動行ソースが決定され、これが外部ループに指定されます。

    外部ループによって、結合条件を駆動するための行のセットが生成されます。行ソースは、索引スキャン、全表スキャン、または行を生成するその他の操作を使用してアクセスされる表の可能性があります。

  2. オプティマイザによって、他方の行ソースが内部ループに指定されます。

    次のように、外部ループは実行計画の内部ループの前に表示されます。

    NESTED LOOPS 
      outer_loop
      inner_loop 
    
  3. クライアントからのフェッチ・リクエストごとの基本的なプロセスは次のとおりです。

    1. 外部行ソースから行がフェッチされます。

    2. 内部行ソースがプローブされ、述語基準に一致する行が検索されます。

    3. フェッチ・リクエストによってすべての行が取得されるまで、この手順が繰り返されます。

    より効率的なバッファ・アクセス・パターンを取得するために、行IDがソートされる場合もあります。

ネステッド・ループのネスト

ネステッド・ループの外部ループ自体を、別のネステッド・ループから生成される行ソースにすることが可能です。2つ以上の外部ループをネストして、必要なだけ表を結合できます。各ループはデータ・アクセス方法です。

次のテンプレートで、3つのネステッド・ループが反復処理される方法を示します。

SELECT STATEMENT
  NESTED LOOPS 3
    NESTED LOOPS 2          - Row source becomes OUTER LOOP 3.1
      NESTED LOOPS 1        - Row source becomes OUTER LOOP 2.1
        OUTER LOOP 1.1
        INNER LOOP 1.2  
      INNER LOOP 2.2
    INNER LOOP 3.2

次の順序でループが行われます。

  1. NESTED LOOPS 1が反復されます。

    NESTED LOOPS 1 
      OUTER LOOP 1.1
      INNER LOOP 1.2
    

    NESTED LOOP 1の出力は行ソースです。

  2. NESTED LOOPS 1で生成された行ソースを外部ループに使用して、NESTED LOOPS 2が反復されます。

    NESTED LOOPS 2       
      OUTER LOOP 2.1         - Row source generated by NESTED LOOPS 1
      INNER LOOP 2.2 
    

    NESTED LOOP 2の出力は別の行ソースです。

  3. NESTED LOOPS 2で生成された行ソースを外部ループに使用して、NESTED LOOPS 3が反復されます。

    NESTED LOOPS 3      
      OUTER LOOP 3.1         - Row source generated by NESTED LOOPS 2
      INNER LOOP 3.2
    

例7-1 ネステッド・ループ結合のネスト

次のようにemployees表とdepartments表を結合するとします。

SELECT /*+ ORDERED USE_NL(d) */ e.last_name, e.first_name, d.department_name
FROM   employees e, departments d
WHERE  e.department_id=d.department_id
AND    e.last_name like 'A%';

計画からは、オプティマイザによって2つのネステッド・ループ(手順1および手順2)が、データへのアクセスに選択されることがわかります。

SQL_ID  ahuavfcv4tnz4, child number 0
-------------------------------------
SELECT /*+ ORDERED USE_NL(d) */ e.last_name, d.department_name FROM
employees e, departments d WHERE  e.department_id=d.department_id AND
 e.last_name like 'A%'
 
Plan hash value: 1667998133
 
----------------------------------------------------------------------------------
|Id| Operation                             |Name      |Rows|Bytes|Cost(%CPU)|Time|
----------------------------------------------------------------------------------
| 0| SELECT STATEMENT                      |             |  |   |5 (100)|        |
| 1|  NESTED LOOPS                         |             |  |   |       |        |
| 2|   NESTED LOOPS                        |             | 3|102|5   (0)|00:00:01|
| 3|    TABLE ACCESS BY INDEX ROWID BATCHED| EMPLOYEES   | 3| 54|2   (0)|00:00:01|
|*4|     INDEX RANGE SCAN                  | EMP_NAME_IX | 3|   |1   (0)|00:00:01|
|*5|    INDEX UNIQUE SCAN                  | DEPT_ID_PK  | 1|   |0   (0)|        |
| 6|   TABLE ACCESS BY INDEX ROWID         | DEPARTMENTS | 1| 16|1   (0)|00:00:01|
----------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   4 - access("E"."LAST_NAME" LIKE 'A%')
       filter("E"."LAST_NAME" LIKE 'A%')
   5 - access("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")

この例では、基本的なプロセスは次のとおりです。

  1. 内部ネステッド・ループの反復処理(手順2)が、次のように開始されます。

    1. Aで始まるすべての姓の行IDが、emp_name_ixで検索されます(手順4)。

      次に例を示します。

      Abel,employees_rowid
      Ande,employees_rowid
      Atkinson,employees_rowid
      Austin,employees_rowid
      
    2. 前の手順で検索された行IDを使用して、employees表から行バッチが取得されます(手順3)。次に例を示します。

      Abel,Ellen,80
      Abel,John,50
      

      これらの行が、最も内部のネステッド・ループの外部行ソースになります。

      バッチ手順は、通常、適応実行計画に含まれます。ネステッド・ループがハッシュ結合より適しているかどうかを判断するには、行ソースから多くの行が返されるかどうかを判断する必要があります。返される行が多すぎる場合は、オプティマイザによって別の結合方法に切り替えられます。

    3. 外部行ソースの各行について、一致する部門IDのdepartmentsにおける行IDを取得するためにdept_id_pk索引がスキャンされ(手順5)、それがemployees行に結合されます。次に例を示します。

      Abel,Ellen,80,departments_rowid
      Ande,Sundar,80,departments_rowid
      Atkinson,Mozhe,50,departments_rowid
      Austin,David,60,departments_rowid
      

      これらの行が、外部ネステッド・ループの外部行ソースになります(手順1)。

  2. 外部ネステッド・ループは、次のように反復処理されます。

    1. 外部行ソースの最初の行が読み取られます。

      次に例を示します。

      Abel,Ellen,80,departments_rowid
      
    2. departments行IDが使用されてdepartmentsから該当する行が取得され(手順6)、その結果が結合されてリクエストされた値が取得されます(手順1)。

      次に例を示します。

      Abel,Ellen,80,Sales
      
    3. 外部行ソースから次の行が読み取られ、departments行IDが使用されてdepartmentsから該当する行が取得され(手順6)、すべての行が取得されるまでこのループが反復されます。

      結果セットは次の形式になります。

      Abel,Ellen,80,Sales
      Ande,Sundar,80,Sales
      Atkinson,Mozhe,50,Shipping
      Austin,David,60,IT
      

ネステッド・ループ結合の現在の実装

Oracle Database 11gでは、新しいネステッド・ループ結合の実装が導入され、物理I/Oの全体の待機時間が短縮されました。バッファ・キャッシュに索引または表ブロックが存在せず、結合の処理に必要な場合、物理I/Oが必要となります。一度に1つのリクエストではなく、ベクターI/Oを使用して複数の物理I/Oリクエストをまとめて処理できます。ベクターは配列です。データベースで行IDのセットが取得され、配列としてオペレーティング・システムに送信され、そこで読取りが行われます。

新規の実装の一環として、NESTED LOOPS結合の2つの行ソースが実行計画に表示されます(以前のリリースでは1行のみが表示されていました)。この場合、Oracle Databaseでは結合の外部側の表の値と内部側の索引とを結合するためにNESTED LOOPS結合の1つの行ソースを割り当てます。もう1つの行ソースは、最初の結合の結果を結合するために割り当てられます。これにより、索引に格納されている行IDが含まれ、結合の内部側に表が存在します。

「ネステッド・ループ結合の従来の実装」の問合せについて考えます。現在の実装では、この問合せの実行計画は次のようになります。

------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name              | Rows  | Bytes | Cost(%CPU)| Time      |
-------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                   |    19 |   722 |     3   (0)| 00:00:01 |
|   1 |  NESTED LOOPS                |                   |       |       |            |          |
|   2 |   NESTED LOOPS               |                   |    19 |   722 |     3   (0)| 00:00:01 |
|*  3 |    TABLE ACCESS FULL         | DEPARTMENTS       |     2 |    32 |     2   (0)| 00:00:01 |
|*  4 |    INDEX RANGE SCAN          | EMP_DEPARTMENT_IX |    10 |       |     0   (0)| 00:00:01 |
|   5 |   TABLE ACCESS BY INDEX ROWID| EMPLOYEES         |    10 |   220 |     1   (0)| 00:00:01 |
-------------------------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
   3 - filter("D"."DEPARTMENT_NAME"='Marketing' OR "D"."DEPARTMENT_NAME"='Sales')
   4 - access("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")

この場合は、hr.departments表の行が内部ネステッド・ループ(手順2)の外部行ソース(手順3)を形成します。索引emp_department_ixは、内部ネステッド・ループの内部行ソース(手順4)です。内部ネステッド・ループの結果が、外部ネステッド・ループ(Row 1)の外部行ソース(Row 2)を形成します。hr.employees表は、外部ネステッド・ループの外部行ソース(Row 5)です。

フェッチ・リクエストごとの基本的なプロセスは次のとおりです。

  1. フェッチでリクエストされた行を取得するために、内部ネステッド・ループが反復処理されます(手順2)。

    1. departmentsの最初の行が読み取られ、MarketingまたはSalesという部門の部門IDが取得されます(手順3)。次に例を示します。

      Marketing,20
      

      この行セットは、外部ループです。データはPGAにキャッシュされます。

    2. emp_department_ix(employees表の索引)のスキャンによって、この部門IDに該当するemployees行IDが検索され(手順4)、その結果が結合されます(手順2)。

      結果セットは次の形式になります。

      Marketing,20,employees_rowid
      Marketing,20,employees_rowid
      Marketing,20,employees_rowid
      
    3. departmentsの次の行が読み取られ、emp_department_ixのスキャンによって、この部門IDに該当するemployees行IDが検索され(手順4)、クライアント・リクエストが満たされるまでこのループが反復されます。

      この例では、departmentsで述語フィルタに一致するのは2行のみのため、外部ループは2回のみ反復されます。概念上、結果セットは次の形式をとります。

      Marketing,20,employees_rowid
      Marketing,20,employees_rowid
      Marketing,20,employees_rowid
      .
      .
      .
      Sales,80,employees_rowid
      Sales,80,employees_rowid
      Sales,80,employees_rowid
      .
      .
      .
      

      これらの行が、外部ネステッド・ループの外部行ソースになります(手順1)。この行セットはPGAにキャッシュされます。

  2. 前の手順で取得された行IDは、キャッシュでより効率的にアクセスできるように整理されます。

  3. 外部ネステッド・ループの反復処理が、次のように開始されます。

    1. 前の手順で取得された行セットの最初の行が、次の例のように取得されます。

      Marketing,20,employees_rowid
      
    2. リクエストされた値を取得するために、行IDを使用してemployeesの行が、次の例のように取得されます(手順1)。

      Michael,Hartstein,13000,Marketing
      
    3. 行セットから次の行が取得され、行IDを使用してemployeesで一致する行がプローブされ、すべての行が取得されるまでこのループが反復されます。

      結果セットは次の形式になります。

      Michael,Hartstein,13000,Marketing
      Pat,Fay,6000,Marketing
      John,Russell,14000,Sales
      Karen,Partners,13500,Sales
      Alberto,Errazuriz,12000,Sales
      .
      .
      .
      

場合によっては、2番目の結合の行ソースが割り当てられないことがあります。この場合、実行計画はOracle Database 11g以前と同様に表示されます。次にこのような状況について説明します。

  • 結合の内部側で必要なすべての列が索引に存在するため、表にアクセスする必要がない。この場合、Oracle Databaseでは結合の1つの行ソースのみが割り当てられます。

  • 返される行の順序は、Oracle Database 12cより前のリリースで返される順序とは異なる場合があります。したがって、Oracle Databaseで行の特定の順序を予約しようとする場合(たとえばORDER BYソートを行う必要がない場合など)、Oracle Databaseではネステッド・ループ結合の従来の実装が使用されます。

  • OPTIMIZER_FEATURES_ENABLE初期化パラメータが、Oracle Database 11gより前のリリースに設定されている。この場合、Oracle Databaseではネステッド・ループ結合の従来の実装が使用されます。

ネステッド・ループ結合の従来の実装

現在のリリースでは、新しい実装と従来の実装のいずれも使用可能です。従来の実装の例として、次にhr.employees表とhr.departments表の結合を検討してみます。

SELECT e.first_name, e.last_name, e.salary, d.department_name
FROM   hr.employees e, hr.departments d
WHERE  d.department_name IN ('Marketing', 'Sales')
AND    e.department_id = d.department_id;

Oracle Database 11gより前のリリースでは、この問合せの実行計画は次のようになります。

-------------------------------------------------------------------------------------------------
| Id  | Operation                   | Name              | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |                   |    19 |   722 |     3  (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| EMPLOYEES         |    10 |   220 |     1  (0)| 00:00:01 |
|   2 |   NESTED LOOPS              |                   |    19 |   722 |     3  (0)| 00:00:01 |
|*  3 |    TABLE ACCESS FULL        | DEPARTMENTS       |     2 |    32 |     2  (0)| 00:00:01 |
|*  4 |    INDEX RANGE SCAN         | EMP_DEPARTMENT_IX |    10 |       |     0  (0)| 00:00:01 |
-------------------------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
   3 - filter("D"."DEPARTMENT_NAME"='Marketing' OR "D"."DEPARTMENT_NAME"='Sales')
   4 - access("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")

フェッチ・リクエストごとの基本的なプロセスは次のとおりです。

  1. フェッチでリクエストされた行を取得するために、ループが反復処理されます。

    1. departmentsの最初の行が読み取られ、MarketingまたはSalesという部門の部門IDが取得されます(手順3)。次に例を示します。

      Marketing,20
      

      この行セットは、外部ループです。行はPGAにキャッシュされます。

    2. emp_department_ix(employees.department_id列の索引)のスキャンによって、この部門IDに該当するemployees行IDが検索され(手順4)、その結果が結合されます(手順2)。

      概念上、結果セットは次の形式をとります。

      Marketing,20,employees_rowid
      Marketing,20,employees_rowid
      Marketing,20,employees_rowid
      
    3. departmentsの次の行が読み取られ、emp_department_ixのスキャンによって、この部門IDに該当するemployees行IDが検索され(手順4)、クライアント・リクエストが満たされるまでこのループが反復されます。

      この例では、departmentsで述語フィルタに一致するのは2行のみのため、外部ループは2回のみ反復されます。概念上、結果セットは次の形式をとります。

      Marketing,20,employees_rowid
      Marketing,20,employees_rowid
      Marketing,20,employees_rowid
      .
      .
      .
      Sales,80,employees_rowid
      Sales,80,employees_rowid
      Sales,80,employees_rowid
      .
      .
      .
      
  2. 状況に応じ、前の手順で取得されたキャッシングされた行IDは、より効率的にアクセスできるように整理されます。

  3. ネステッド・ループで生成された結果セットの各employees行IDについて、リクエストされた値を取得するためにemployeesから行が取得されます(手順1)。

    このように、基本的なプロセスでは、行IDが読み取られて一致するemployees行が取得され、次の行IDが読み取られて一致するemployees行が取得され、これが繰り返されます。概念上、結果セットは次の形式をとります。

    Michael,Hartstein,13000,Marketing
    Pat,Fay,6000,Marketing
    John,Russell,14000,Sales
    Karen,Partners,13500,Sales
    Alberto,Errazuriz,12000,Sales
    .
    .
    .
    

ネステッド・ループの制御

データが十分に小さいSQL例の場合は、オプティマイザは全表スキャンとハッシュ結合を優先します。ただし、USE_NLを追加してオプティマイザに指示し、結合方法をネステッド・ループに変更できます。このヒントは、指定された表を内部表として使用し、指定された各表をネストしたループ結合とともに別の行のソースに結合するようオプティマイザに指示します。

関連するヒントUSE_NL_WITH_INDEX (表索引)ヒントによって、指定された表を内部表に使用して、ネステッド・ループループ結合で別の行のソースに結合するよう、オプティマイザに指示されます。索引はオプションです。索引を指定しない場合、ネステッド・ループ結合では、結合述語を1つ以上含む索引が索引キーとして使用されます。

例7-2 ネステッド・ループのヒント

次の問合せにおいて、オプティマイザでハッシュ結合が選択されたとします。

SELECT e.last_name, d.department_name
FROM   employees e, departments d
WHERE  e.department_id=d.department_id;

計画は次のようになります。

----------------------------------------------------------------------------------
| Id  | Operation          | Name        | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |             |       |       |     5 (100)|          |
|*  1 |  HASH JOIN         |             |   106 |  2862 |     5  (20)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| DEPARTMENTS |    27 |   432 |     2   (0)| 00:00:01 |
|   3 |   TABLE ACCESS FULL| EMPLOYEES   |   107 |  1177 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------------

departmentsを内部表として使用して強制的にネステッド・ループを行うには、次の問合せのようにUSE_NLヒントを追加します。

SELECT /*+ ORDERED USE_NL(d) */ e.last_name, d.department_name
FROM   employees e, departments d
WHERE  e.department_id=d.department_id;

計画は次のようになります。

----------------------------------------------------------------------------------
| Id  | Operation          | Name        | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |             |       |       |    34 (100)|          |
|   1 |  NESTED LOOPS      |             |   106 |  2862 |    34   (3)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| EMPLOYEES   |   107 |  1177 |     2   (0)| 00:00:01 |
|*  3 |   TABLE ACCESS FULL| DEPARTMENTS |     1 |    16 |     0   (0)|          |
----------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
 
   3 - filter("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")

結果セットは次のように取得されます。

  1. ネステッド・ループで、従業員の姓および部門IDを取得するために、employeesが読み取られます(手順2)。次に例を示します。

    De Haan,90
    
  2. 前の手順で取得された各行について、departmentsのスキャンによってemployees部門IDに一致する部門名が検索されて(手順3)、その結果が結合されます(手順1)。次に例を示します。

    De Haan,Executive
    
  3. employeesの次の行が取得され、departmentsから一致する行が取得され、すべての行が取得されるまでこのプロセスが反復されます。

    結果セットは次の形式になります。

    De Haan,Executive
    Kochnar,Executive
    Baer,Public Relations
    King,Executive
    .
    .
    .
    

関連項目:


ハッシュ結合

ハッシュ結合は、大きなデータ・セットの結合に使用されます。オプティマイザによって、2つのデータ・セットの小さい方が使用されてメモリー内に結合キーのハッシュ表が作成され、決定的ハッシュ関数によって、ハッシュ表内で各行を格納する場所が指定されます。次に、大きい方のデータ・セットがスキャンされ、ハッシュ表を調べて結合条件を満たす行が検索されます。

オプティマイザがハッシュ結合を考慮する場合

一般に、次の条件に該当する場合に、オプティマイザにおいてハッシュ結合が考慮されます。

  • 比較的大量のデータを結合する必要があるか、小規模な表の大部分を結合する必要があります。

  • 結合が等価結合です。

ハッシュ結合は、小さい方のデータ・セットがメモリーに収まる場合に、コスト効率が非常に高くなります。この場合、コストは2つのデータ・セットに対する1回のリード・パスに限定されます。

ハッシュ表がPGA内に存在するため、行をラッチすることなく、アクセスが可能です。この手法によって、データベース・バッファ・キャッシュでブロックのラッチと読取りを繰り返す必要性が回避されて、論理I/Oが低減されます。

データ・セットがメモリーに収まらない場合は、行ソースがパーティション分割されて、パーティションごとに結合が行われます。この場合は、ソート領域メモリー、および一時表領域へのI/Oが、大量に使用される可能性があります。この手法でも、特にパラレル問合せサーバーが使用される場合には、非常にコスト効率が高い場合があります。

ハッシュ結合の仕組み

ハッシュ・アルゴリズムでは、入力のセットに決定的ハッシュ関数を適用して、1とn間のハッシュ値を生成します(nはハッシュ表のサイズです)。ハッシュ結合において、入力値は結合キーです。出力値は配列形式の索引(スロット)であり、これがハッシュ表です。

ハッシュ表

ハッシュ表について説明するために、departmentsemployeesの結合において、hr.departmentsがハッシュされると想定します。結合キー列は、department_idです。部門の最初の5行は、次のとおりです。

SQL> select * from departments where rownum < 6;
 
DEPARTMENT_ID DEPARTMENT_NAME                MANAGER_ID LOCATION_ID
------------- ------------------------------ ---------- -----------
           10 Administration                        200        1700
           20 Marketing                             201        1800
           30 Purchasing                            114        1700
           40 Human Resources                       203        2400
           50 Shipping                              121        1500

表の各department_idに対してハッシュ関数が適用され、それぞれのハッシュ値が生成されます。この説明では、ハッシュ表には5つのスロットがあります(これより多い可能性も少ない可能性もあります)。n5であるため、可能なハッシュ値は、1から5の範囲です。ハッシュ関数によって、部門IDに対して次の値が生成されるとします。

f(10) = 4
f(20) = 1
f(30) = 4
f(40) = 2
f(50) = 5

ハッシュ関数によって、たまたま部門10と部門30に対して同じハッシュ値4が生成されています。これは、ハッシュ衝突と呼ばれます。この場合、部門10と部門30のレコードは、リンク済リストを使用して同じスロットに格納されます。概念上、ハッシュ表は次のようになります。

1    20,Marketing,201,1800
2    40,Human Resources,203,2400
3
4    10,Administration,200,1700 -> 30,Purchasing,114,1700
5    50,Shipping,121,1500
ハッシュ結合: 基本手順

2つの行ソースのハッシュ結合においては、次の基本手順が実行されます。

  1. 小さい方のデータ・セットの全体スキャンが実行された後、各行の結合キーに対してハッシュ関数が適用されて、PGAにハッシュ表が作成されます。

    擬似コードでは、アルゴリズムは次のようになります。

    FOR small_table_row IN (SELECT * FROM small_table)
    LOOP
      slot_number := HASH(small_table_row.join_key);
      INSERT_HASH_TABLE(slot_number,small_table_row);
    END LOOP;
      
    
  2. 最少コストのアクセス・メカニズムを使用して、2番目のデータ・セットがプローブされます。

    通常は、小さい方と大きい方の両データ・セットの全体スキャンが実行されます。擬似コードによるアルゴリズムは次のようになります。

    FOR large_table_row IN (SELECT * FROM large_table)
    LOOP
       slot_number := HASH(large_table_row.join_key);
       small_table_row = LOOKUP_HASH_TABLE(slot_number,large_table_row.join_key);
       IF small_table_row FOUND
       THEN
          output small_table_row + large_table_row;
       END IF;
    END LOOP;
    

    大きい方のデータ・セットから取得した各行に対して、次の手順が実行されます。

    1. 結合列に対して同じハッシュ関数が適用され、ハッシュ表で該当するスロット番号が計算されます。

      たとえば、ハッシュ表で部門ID 30がプローブされる場合、ハッシュ関数が30に適用され、ハッシュ値4が生成されます。

    2. ハッシュ表がプローブされ、行がスロットに存在するかどうかが判定されます。

      行が存在しない場合は、大きい方のデータ・セットの次の行が処理されます。行が存在する場合は、次の手順に進みます。

    3. 結合列で一致がチェックされます。一致が検出された場合は、行が報告されるか、計画の次の手順に渡された後、大きい方のデータ・セットの次の行が処理されます。

      ハッシュ表のスロットに複数の行が存在する場合は、行のリンク済リストの各行が順にチェックされます。たとえば、部門30がスロット4にハッシュされた場合、30が見つかるまで各行がチェックされます。

例7-3 ハッシュ結合

アプリケーションでoe.orders表とoe.order_items表に対してorder_id列を結合する問合せが行われるとします。

SELECT o.customer_id, l.unit_price * l.quantity
FROM   orders o, order_items l
WHERE  l.order_id = o.order_id;

実行計画は次のようになります。

--------------------------------------------------------------------------
| Id  | Operation            |  Name        | Rows  | Bytes | Cost (%CPU)|
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT     |              |   665 | 13300 |     8  (25)|
|*  1 |  HASH JOIN           |              |   665 | 13300 |     8  (25)|
|   2 |   TABLE ACCESS FULL  | ORDERS       |   105 |   840 |     4  (25)|
|   3 |   TABLE ACCESS FULL  | ORDER_ITEMS  |   665 |  7980 |     4  (25)|
--------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("L"."ORDER_ID"="O"."ORDER_ID")

orders表はorder_items表に比べて小さいため(6倍の大きさ)、ordersがハッシュされます。ハッシュ結合では、ハッシュ表のデータ・セットは常に操作リストの最初に表示されます(手順2)。手順3で、大きい方のorder_itemsの全体スキャンが後で行われ、各行についてハッシュ表がプローブされます。

ハッシュ表がPGAに収まらない場合のハッシュ結合の仕組み

ハッシュ表全体がPGAに収まらない場合は、別の手法が使用される必要があります。この場合は、一時領域にハッシュ表の一部(パーティションと呼ばれる)が保持され、そこにハッシュ表をプローブする大きい方の表の一部が保持される場合もあります。

基本的なプロセスは次のとおりです。

  1. 小さい方のデータ・セットの全体スキャンが実行された後、PGAとディスクの両方にハッシュ・バケットの配列が作成されます。

    PGAのハッシュ領域が一杯になると、ハッシュ表内で最も大きなパーティションが検索され、それがディスク上の一時領域に書き込まれます。このオンディスク・パーティションに属するあらゆる新規の行はディスク上に格納され、他のすべての行はPGAに格納されます。このため、ハッシュ表の一部はメモリーに、一部はディスク上に保持されます。

  2. まず、もう一方のデータ・セットが読み取られます

    各行に対して、次の処理が行われます。

    1. 結合列に対して同じハッシュ関数が適用され、該当するハッシュ・バケットの番号が計算されます。

    2. ハッシュ表がプローブされ、メモリー内のバケットに行が存在するかどうかが判定されます。

      ハッシュ値がメモリー内の行を指している場合は、結合が行われて、その行が返されます。ただし、値がディスク上のハッシュ・パーティションを指している場合、この行は、元のデータ・セットで使用されたものと同じパーティション・スキームを使用して一時表領域に格納されます。

  3. 各オンディスク一時パーティションが1つずつ読み取られます。

  4. 各パーティション行が、対応するオンディスク一時パーティション内の行に結合されます。

ハッシュ結合の制御

USE_HASHヒントによって、2つの表を結合するときにハッシュ結合を使用するよう、オプティマイザに指示します。「結合順序のヒントのガイドライン」を参照してください。

ソート/マージ結合

ソート/マージ結合は、ネステッド・ループ結合のバリエーションです。2つのデータ・セットがソートされていない場合にソートされます(SORT JOIN操作)。1つ目のデータ・セットの各行ごとに、2つ目のデータ・セットが、前回の反復処理で得られた一致を基準とした開始位置からプローブされ、一致した行が結合されます(MERGE JOIN操作)。

tgsql_vm_081.pngの説明は次にあります
図tgsql_vm_081.pngの説明

オプティマイザがソート/マージ結合を考慮する場合

ハッシュ結合には、1つのハッシュ表とこの表の1回のプローブが必要ですが、ソート/マージ結合には2回のソートが必要です。オプティマイザでは、次の条件に該当する場合に、大量のデータの結合にハッシュ結合よりソート/マージ結合が選択されます。

  • 2つの表の結合条件が等価結合ではありません、つまり、非等価条件(<<=>>=など)が使用されます。

    ソート/マージと異なり、ハッシュ結合には等価条件が必要です。

  • 他の操作でソートが必要なため、オプティマイザによってソート/マージを使用する方がコストが低いと判断されました。

    索引が存在する場合は、1つ目のデータ・セットのソートが回避されます。ただし、2つ目のデータ・セットは索引に関係なく常にソートされます。

ソート/マージには、ハッシュ結合と同じくネステッド・ループ結合に勝る利点があります。行はSGAよりもPGAでアクセスされるため、データベース・バッファ・キャッシュでブロックのラッチと読取りを繰り返す必要性が回避されて、論理I/Oが低減されます。ソートはコストが高いため、一般に、ハッシュ結合はソート/マージ結合よりもパフォーマンスが優れています。ただし、ソート/マージ結合にはハッシュ結合より優れた次のような利点があります。

  • 初期ソートの後、マージ・フェーズが最適化されて、出力行の生成速度が上がります。

  • ハッシュ表がメモリー内に完全に収まらない場合、ソート/マージはハッシュ結合よりもコスト効率が上がります。

    ハッシュ結合においてメモリーが不十分な場合は、ハッシュ表ともう一方のデータ・セットがディスクにコピーされる必要があります。この場合は、ディスクから複数回の読取りが必要になることがあります。ソート/マージでは、メモリに2つのデータ・セットを保持できない場合に両方がディスクに書き込まれますが、各データ・セットが複数回読み取られることはありません。

ソート/マージ結合の仕組み

ネステッド・ループ結合と同様に、ソート/マージ結合では2つのデータ・セットが読み取られますが、ソートは、すでに行われていない場合に行われます。1つ目のデータ・セットの各行ごとに、2つ目のデータ・セットの開始行が検索され、一致しない行が見つかるまで2つ目のデータ・セットが読み取られます。擬似コードで上位レベルのアルゴリズムを表すと、次のようになります。

READ data_set_1 SORT BY JOIN KEY TO temp_ds1
READ data_set_2 SORT BY JOIN KEY TO temp_ds2
 
READ ds1_row FROM temp_ds1
READ ds2_row FROM temp_ds2

WHILE NOT eof ON temp_ds1,temp_ds2
LOOP
    IF ( temp_ds1.key = temp_ds2.key ) OUTPUT JOIN ds1_row,ds2_row
    ELSIF ( temp_ds1.key <= temp_ds2.key ) READ ds1_row FROM temp_ds1
    ELSIF ( temp_ds1.key => temp_ds2.key ) READ ds2_row FROM temp_ds2
END LOOP

たとえば、1つ目のデータ・セットは次のようにソートされます。

10,20,30,40,50,60,70

2つ目のデータ・セットは次のようにソートされます。

20,20,40,40,40,40,40,60,70,70

まず、1つ目のデータ・セットの10が読み取られ、次にデータ・セット2の先頭から処理が開始されます。

20 too high, stop, get next ds1_row

次に、データ・セット1の2行目(20)に進みます。2つ目のデータ・セットの処理は次のように進みます。

20 match, proceed
20 match, proceed
40 too high, stop, get next ds1_row

データ・セット1の次の行が取得されます(30です)。前回一致した数値から読取りが開始され(20でした)、データ・セット2で一致が順に検索されていきます。

20 too low, proceed
20 too low, proceed
40 too high, stop, get next ds1_row 

データ・セット1の次の行が取得されます(40です)。前回に一致した数値から読取りが開始され(20でした)、データ・セット2で一致が順に検索されていきます。

20 too low, proceed
20 too low, proceed
40 match, proceed
40 match, proceed
40 match, proceed
40 match, proceed
40 match, proceed
60 too high, stop, get next ds1_row

データ・セット1の読取りが進行する過程で、データ・セット2のすべての行が読み取られる必要はありません。これが、ネステッド・ループ結合に勝る利点です。

例7-4 索引を使用したソート/マージ結合

次の問合せでは、employees表とdepartments表がdepartment_id列で結合され、次のように行がdepartment_idによって順序付けられます。

SELECT e.employee_id, e.last_name, e.first_name, e.department_id, 
       d.department_name
FROM   employees e, departments d
WHERE  e.department_id = d.department_id
ORDER BY department_id;

DBMS_XPLAN.DISPLAY_CURSORの問合せによって、計画でソート/マージ結合が使用されていることがわかります。

----------------------------------------------------------------------------------
|Id | Operation                    | Name        | Rows|Bytes |Cost (%CPU)| Time |
----------------------------------------------------------------------------------
| 0 | SELECT STATEMENT             |             |     |      | 5(100)|          |
| 1 |  MERGE JOIN                  |             | 106 | 4028 | 5 (20)| 00:00:01 |
| 2 |   TABLE ACCESS BY INDEX ROWID| DEPARTMENTS |  27 |  432 | 2  (0)| 00:00:01 |
| 3 |    INDEX FULL SCAN           | DEPT_ID_PK  |  27 |      | 1  (0)| 00:00:01 |
|*4 |   SORT JOIN                  |             | 107 | 2354 | 3 (34)| 00:00:01 |
| 5 |    TABLE ACCESS FULL         | EMPLOYEES   | 107 | 2354 | 2  (0)| 00:00:01 |
----------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   4 - access("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")
       filter("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")

2つのデータ・セットは、departments表とemployees表です。索引でdepartments表は、department_idによって順序付けられるため、この索引を読み取ることでソート(手順3)を回避できます。必要なのはemployees表のソート(手順4)のみであり、これが最もCPUの負荷が高い操作です。

例7-5 索引を使用しないソート/マージ結合

employees表とdepartments表がdepartment_id列で結合され、次のように行がdepartment_idによって順序付けられます。この例では、NO_INDEXおよびUSE_MERGEを指定することによって、オプティマイザにソート/マージの選択を強制します。

SELECT /*+ USE_MERGE(d e) NO_INDEX(d) */ e.employee_id, e.last_name, e.first_name, 
       e.department_id, d.department_name
FROM   employees e, departments d
WHERE  e.department_id = d.department_id
ORDER BY department_id;

DBMS_XPLAN.DISPLAY_CURSORの問合せによって、計画でソート/マージ結合が使用されていることがわかります。

----------------------------------------------------------------------------------
| Id  | Operation           | Name        | Rows  | Bytes | Cost (%CPU)| Time    |
----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |             |       |       |     6 (100)|         |
|   1 |  MERGE JOIN         |             |   106 |  9540 |     6  (34)| 00:00:01|
|   2 |   SORT JOIN         |             |    27 |   567 |     3  (34)| 00:00:01|
|   3 |    TABLE ACCESS FULL| DEPARTMENTS |    27 |   567 |     2   (0)| 00:00:01|
|*  4 |   SORT JOIN         |             |   107 |  7383 |     3  (34)| 00:00:01|
|   5 |    TABLE ACCESS FULL| EMPLOYEES   |   107 |  7383 |     2   (0)| 00:00:01|
----------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   4 - access("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")
       filter("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")

departments.department_id索引が無視されるため、オプティマイザによってソートが実行されて、手順2と手順3を合わせたコストが67%増加します(3から5まで)。

ソート/マージ結合の制御

USE_MERGEヒントによって、ソート/マージ結合を使用するようオプティマイザに指示します。状況によっては、USE_MERGEヒントを使用してオプティマイザを上書きすることが適切な場合もあります。たとえば、オプティマイザは表に対する全体スキャンを選択して問合せ内でのソート操作を回避できます。ただし、大きい表は全表スキャンによる高速アクセスの場合とは異なり、索引および単一ブロック読取りでアクセスされるため、コストがかかります。


関連項目:

USE_MERGEヒントの詳細は、『Oracle Database SQL言語リファレンス』を参照してください。

デカルト結合

文に他の表との結合条件のない表が1つ以上存在する場合、デカルト結合が使用されます。オプティマイザは、データ・ソースにあるすべての行を、2つのセットのデカルト積を作成しながら、別のデータ・ソースにあるすべての行と結合します。したがって、結合で生成される行の合計数は、次の式で計算されます(rs1は、1つ目の行セットの行数で、rs2は、2つ目の行セットの行数です)。

rs1 X rs2 = total rows in result set

オプティマイザがデカルト結合を考慮する場合

オプティマイザでは、次のいずれかの状況に該当する2つの行ソースに対して、デカルト結合が使用されます。

  • 結合条件が存在しません。

    場合によっては、2つの表の間に共通のフィルタ条件が、可能な結合条件として採用されることがあります。


    注意:

    結合条件が誤って省略されたために、問合せ計画にデカルト結合が出現する場合があります。一般に、問合せでn個の表が結合される場合、デカルト結合を回避するにはn-1個の結合条件が必要です。

  • デカルト結合が効率的です。

    たとえば、オプティマイザによって、同じ大きい表に結合されている、非常に小さい2つの表のデカルト積を生成するように決定される場合もあります。

  • 結合表が指定される前に、ORDEREDヒントによって表が指定されています。

デカルト結合の仕組み

上位レベルにおいて、デカルト結合のアルゴリズムは次のようになります(ds1が、通常小さい方のデータセットで、ds2が大きい方のデータ・セットです)。

FOR ds1_row IN ds1 LOOP
  FOR ds2_row IN ds2 LOOP
    output ds1_row and ds2_row
  END LOOP
END LOOP

例7-6 デカルト結合

この例では、ユーザーはemployees表とdepartments表の内部結合を実行しようとして、誤って結合条件を省略しています。

SELECT e.last_name, d.department_name
FROM   employees e, departments d

実行計画は次のようになります。

----------------------------------------------------------------------------------
| Id  | Operation              | Name        | Rows  | Bytes |Cost (%CPU)| Time  |
----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT       |             |       |       |11 (100)|          |
|   1 |  MERGE JOIN CARTESIAN  |             |  2889 | 57780 |11   (0)| 00:00:01 |
|   2 |   TABLE ACCESS FULL    | DEPARTMENTS |    27 |   324 | 2   (0)| 00:00:01 |
|   3 |   BUFFER SORT          |             |   107 |   856 | 9   (0)| 00:00:01 |
|   4 |    INDEX FAST FULL SCAN| EMP_NAME_IX |   107 |   856 | 0   (0)|          |
----------------------------------------------------------------------------------

この計画では、手順1のCARTESIANキーワードによって、デカルト結合が行われることが示されています。行数(2889)は、27と107の積です。

手順3のBUFFER SORT操作は、emp_name_ixのスキャンで取得されたデータ・ブロックが、SGAからPGAにコピーされることを意味しています。この方法によって、データベース・バッファ・キャッシュにおける同一ブロックの複数回スキャンが回避される結果、多数の論理読取りが生成されて、リソース競合が生じる可能性があります。

デカルト結合の制御

ORDEREDヒントによって、FROM句に現れる順序で表を結合するようオプティマイザに指示します。直接関係のない2つの表を強制的に結合させることにより、デカルト結合が実行されます。

例7-7 ORDEREDヒント

次の例では、ORDEREDヒントによって、オプティマイザにemployees表とlocations表を結合するよう指示しますが、これら2つの行ソースをつなぐ結合条件はありません。

SELECT /*+ORDERED*/ e.last_name, d.department_name, l.country_id, l.state_province
FROM   employees e, locations l, departments d
WHERE  e.department_id = d.department_id
AND    d.location_id = l.location_id

次の実行計画ではlocations (手順6)とemployees (手順4)とのデカルト積(手順3)が行われ、次にそれがdepartments表に結合されます(手順2)。

----------------------------------------------------------------------------------
| Id  | Operation             | Name        | Rows  | Bytes |Cost (%CPU)|Time    |
----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |             |       |       | 37 (100)|          |
|*  1 |  HASH JOIN            |             |   106 |  4664 | 37   (6)| 00:00:01 |
|   2 |   TABLE ACCESS FULL   | DEPARTMENTS |    27 |   513 |  2   (0)| 00:00:01 |
|   3 |   MERGE JOIN CARTESIAN|             |  2461 | 61525 | 34   (3)| 00:00:01 |
|   4 |    TABLE ACCESS FULL  | EMPLOYEES   |   107 |  1177 |  2   (0)| 00:00:01 |
|   5 |    BUFFER SORT        |             |    23 |   322 | 32   (4)| 00:00:01 |
|   6 |     TABLE ACCESS FULL | LOCATIONS   |    23 |   322 |  0   (0)|          |
----------------------------------------------------------------------------------

関連項目:

ORDEREDヒントの詳細は、『Oracle Database SQL言語リファレンス』を参照してください。

結合タイプ

結合タイプは、結合条件のタイプによって決定されます。この項の内容は次のとおりです。

内部結合

内部結合(単純結合とも呼ばれる)は、結合条件を満たす行のみが返される結合です。内部結合は、等価結合または非等価結合です。

等価結合

等価結合は、結合条件に等価演算子が含まれる内部結合です。次の例は、結合条件に等価演算子のみが含まれているため、等価結合です。

SELECT e.employee_id, e.last_name, d.department_name
FROM   employees e, departments d
WHERE  e.department_id=d.department_id;

この問合せにおける結合条件はe.department_id=d.department_idです。employees表に、departments表の行の部門IDに一致する値を持つ行があれば、結合結果が返され、そうでない場合、結果は返されません。

非等価結合

非等価結合は、結合条件に等価演算子ではない演算子が含まれる内部結合です。次の問合せでは、従業員176がこの企業で働いていた間に、雇用日が発生したすべての従業員が示されます(従業員176は2007年に転職したため、job_historyに記載されています)。

SELECT e.employee_id, e.first_name, e.last_name, e.hire_date
FROM   employees e, job_history h
WHERE  h.employee_id = 176
AND    e.hire_date BETWEEN h.start_date AND h.end_date;

この例では、employeesjob_historyを結合する条件に等価演算子が含まれないため、非等価結合です。非等価結合は、比較的まれです。

ハッシュ結合には、少なくとも部分等価結合が必要です。次のSQLスクリプトには、等価結合条件(e1.empno = e2.empno)および非等価条件が含まれています。

SET AUTOTRACE TRACEONLY EXPLAIN
SELECT *
FROM   scott.emp e1 JOIN scott.emp e2
ON     ( e1.empno = e2.empno
AND      e1.hiredate BETWEEN e2.hiredate-1 AND e2.hiredate+1 )

次の計画で示されているように、オプティマイザでは、この問合せに対してハッシュ結合が選択されます。

Execution Plan
----------------------------------------------------------
Plan hash value: 3638257876
 
---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |     1 |   174 |     5  (20)| 00:00:01 |
|*  1 |  HASH JOIN         |      |     1 |   174 |     5  (20)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| EMP  |    14 |  1218 |     2   (0)| 00:00:01 |
|   3 |   TABLE ACCESS FULL| EMP  |    14 |  1218 |     2   (0)| 00:00:01 |
---------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   1 - access("E1"."EMPNO"="E2"."EMPNO")
       filter("E1"."HIREDATE">=INTERNAL_FUNCTION("E2"."HIREDATE")-1 AND
              "E1"."HIREDATE"<=INTERNAL_FUNCTION("E2"."HIREDATE")+1)

外部結合

外部結合では、結合条件に一致するすべての行、および結合条件が他方の表のどの行とも一致しない、一方の表の一部またはすべての行が返されます。したがって、外部結合では単純結合の結果が拡張されます。

ANSI構文では、OUTER JOIN句で外部結合を指定します。FROM句において、左表OUTER JOINキーワードの左に表示され、右表はこのキーワードの右に表示されます。左表は外部表とも呼ばれ、右表は内部表とも呼ばれます。たとえば、次の文において、employees表は左表または外部表です。

SELECT employee_id, last_name, first_name
FROM   employees LEFT OUTER JOIN departments
ON     (employees.department_id=departments.departments_id);

外部結合では、外部結合表が駆動表となる必要があります。この例では、employeesが駆動表で、departments被駆動表です。

この項の内容は次のとおりです。

ネステッド・ループ外部結合

この操作は、2つの表の外部結合をループ処理する場合に使用されます。外部結合は、内部(オプション)表に対応する行がない場合でも、外部(保存されている)表の行を戻します。

標準的なネステッド・ループでは、表の順序(どちらが駆動表で、どちら被駆動表か)は、コストに基づいて決定されます。ただし、ネステッド・ループ外部結合では、結合条件によって表の順序が決まります。外部表(行が格納される表)によって、内部表が駆動されます。

オプティマイザは、ネステッド・ループ結合を使用し、次の状況で外部結合を処理します。

  • 外部表から内部表を駆動できる。

  • データ量が少なく、ネステッド・ループ方法が効果的と判断できる。

ネステッド・ループ外部結合の例の場合は、USE_NLヒントを例7-8に追加して、ネステッド・ループを使用するようにオプティマイザに指示できます。次に例を示します。

SELECT /*+ USE_NL(c o) */ cust_last_name,
       SUM(NVL2(o.customer_id,0,1)) "Count"
FROM   customers c, orders o
WHERE  c.credit_limit > 1000
AND    c.customer_id = o.customer_id(+)
GROUP BY cust_last_name;

ハッシュ結合外部結合

オプティマイザでは、次の条件のいずれか該当する場合に、外部結合の処理にハッシュ結合が使用されます。

  • データ量が十分に多く、ハッシュ結合法が効果的である。

  • 外部表から内部表まで起動することができない。

表の順序はコストによって決まります。外部表は、保存された行も含めて、ハッシュ表を作成する場合に使用されるか、またはハッシュ表を調べるときに使用される場合があります。

例7-8に、一般的なハッシュ結合外部結合の問合せおよびその実行計画を示します。この例では、与信限度が1000を超えるすべての顧客が問い合されます。問合せで注文のない顧客を取得するには、外部結合が必要です。

例7-8 ハッシュ結合外部結合

SELECT cust_last_name, SUM(NVL2(o.customer_id,0,1)) "Count"
FROM   customers c, orders o
WHERE  c.credit_limit > 1000
AND    c.customer_id = o.customer_id(+)
GROUP BY cust_last_name;

---------------------------------------------------------------------------------
| Id  | Operation           | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------
 
PLAN_TABLE_OUTPUT
---------------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |           |       |       |     7 (100)|          |
|   1 |  HASH GROUP BY      |           |   168 |  3192 |     7  (29)| 00:00:01 |
|*  2 |   HASH JOIN OUTER   |           |   318 |  6042 |     6  (17)| 00:00:01 |
|*  3 |    TABLE ACCESS FULL| CUSTOMERS |   260 |  3900 |     3   (0)| 00:00:01 |
|*  4 |    TABLE ACCESS FULL| ORDERS    |   105 |   420 |     2   (0)| 00:00:01 |
---------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   2 - access("C"."CUSTOMER_ID"="O"."CUSTOMER_ID")
 
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------
   3 - filter("C"."CREDIT_LIMIT">1000)
   4 - filter("O"."CUSTOMER_ID">0)

この問合せは、様々な条件に一致する顧客を検索します。内部表に対応する行が見つからないと、外部結合は外部(保たれている)表の行とともに内部表の列に対してNULLを戻します。この操作で、orders行も持たないcustomers行がすべて検索されます。

この場合、外部結合条件は次のとおりです。

customers.customer_id = orders.customer_id(+)

この条件の構成要素を次に示します。

  • 外部表はcustomersです。

  • 内部表はordersです。

  • この結合は、orders内に対応する行を持たない行を含むcustomers行を保存します。

行を戻すには、NOT EXISTS副問合せを使用できます。ただし、表の全行の問合せを行っているため、ハッシュ結合の方がパフォーマンスが優れています(NOT EXISTS副問合せがネストされていない場合を除く)。

例7-9では、外部結合はマルチ表ビューに対して行われます。オプティマイザは通常の結合のようにビューを操作したり、述語をプッシュできないので、ビューの行セット全体を作成します。

例7-9 マルチ表ビューへの外部結合

SELECT c.cust_last_name, sum(revenue)
FROM   customers c, v_orders o
WHERE  c.credit_limit > 2000
AND    o.customer_id(+) = c.customer_id
GROUP BY c.cust_last_name;

----------------------------------------------------------------------------
| Id  | Operation              |  Name        | Rows  | Bytes | Cost (%CPU)|
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT       |              |   144 |  4608 |    16  (32)|
|   1 |  HASH GROUP BY         |              |   144 |  4608 |    16  (32)|
|*  2 |   HASH JOIN OUTER      |              |   663 | 21216 |    15  (27)|
|*  3 |    TABLE ACCESS FULL   | CUSTOMERS    |   195 |  2925 |     6  (17)|
|   4 |    VIEW                | V_ORDERS     |   665 | 11305 |            |
|   5 |     HASH GROUP BY      |              |   665 | 15960 |     9  (34)|
|*  6 |      HASH JOIN         |              |   665 | 15960 |     8  (25)|
|*  7 |       TABLE ACCESS FULL| ORDERS       |   105 |   840 |     4  (25)|
|   8 |       TABLE ACCESS FULL| ORDER_ITEMS  |   665 | 10640 |     4  (25)|
----------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("O"."CUSTOMER_ID"(+)="C"."CUSTOMER_ID")
   3 - filter("C"."CREDIT_LIMIT">2000)
   6 - access("O"."ORDER_ID"="L"."ORDER_ID")
   7 - filter("O"."CUSTOMER_ID">0)

ビュー定義は、次のようになります。

CREATE OR REPLACE view v_orders AS
SELECT l.product_id, SUM(l.quantity*unit_price) revenue, 
       o.order_id, o.customer_id
FROM   orders o, order_items l
WHERE  o.order_id = l.order_id
GROUP BY l.product_id, o.order_id, o.customer_id;

ソート/マージ外部結合

外部結合で、外部(保たれている)表から内部(オプション)表への駆動ができない場合、外部結合ではハッシュ結合またはネステッド・ループ結合が使用できません。この場合は、ソート/マージ外部結合が使用されます。

オプティマイザは、次の場合に外部結合にソート/マージを使用します。

  • ネステッド・ループ結合の効率が悪い場合。データ量により、ネステッド・ループ結合は効率が悪い場合があります。

  • 他の操作でソートが必要であるため、ハッシュ結合よりソート/マージを使用するほうがコストが低いと判断した場合。

完全外部結合

完全外部結合は、左および右外部結合の組合せです。内部結合では、内部結合の結果で戻されなかった両方の表からの行は保たれており、NULLで拡張されます。つまり、完全外部結合を使用すると、表をまとめて結合できますが、結合される表内に対応する行を持たない行も示すことができます。

例7-10では、全部門と、その各部門に属する全社員が取得されますが、これには次の内容も含まれます。

  • 部門に属さない全社員

  • 社員のいない全部門

例7-10 完全外部結合

SELECT d.department_id, e.employee_id
FROM   employees e FULL OUTER JOIN departments d
ON     e.department_id = d.department_id
ORDER BY d.department_id;

文からは、次の出力が作成されます。

DEPARTMENT_ID EMPLOYEE_ID
------------- -----------
           10         200
           20         201
           20         202
           30         114
           30         115
           30         116
...
          270
          280
                      178
                      207

125 rows selected.

Oracle Database 11g以上では、可能なかぎり、完全外部結合を実行する場合、ハッシュ結合に基づいたネイティブの実行方法が自動的に使用されます。新しい方法を使用して完全外部結合を実行する場合、問合せの実行計画にはHASH JOIN FULL OUTERが含まれます。例7-11に、例7-10の問合せの実行計画を示します。

例7-11 完全外部結合の実行計画

---------------------------------------------------------------------------------------
| Id  | Operation               | Name       | Rows  | Bytes | Cost (%CPU)| Time      |
---------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |            |   122 |  4758 |     6  (34)| 00:0 0:01 |
|   1 |  SORT ORDER BY          |            |   122 |  4758 |     6  (34)| 00:0 0:01 |
|   2 |   VIEW                  | VW_FOJ_0   |   122 |  4758 |     5  (20)| 00:0 0:01 |
|*  3 |    HASH JOIN FULL OUTER |            |   122 |  1342 |     5  (20)| 00:0 0:01 |
|   4 |     INDEX FAST FULL SCAN| DEPT_ID_PK |    27 |   108 |     2   (0)| 00:0 0:01 |
|   5 |     TABLE ACCESS FULL   | EMPLOYEES  |   107 |   749 |     2   (0)| 00:0 0:01 |
---------------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
   3 - access("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")

計画にはHASH JOIN FULL OUTERが含まれており(手順3)、問合せでハッシュ完全外部結合の実行方法が使用されることがわかります。2つの表の完全外部結合条件が等価結合の場合、通常はハッシュ完全外部結合の実行方法が可能であるため、Oracle Databaseでは自動的にこの方法が使用されます。

ハッシュ完全外部結合の実行方法の使用を考慮するようにオプティマイザに指示するには、NATIVE_FULL_OUTER_JOINヒントを適用します。ハッシュ完全外部結合の実行方法の使用を考慮しないようにオプティマイザに指示するには、NO_NATIVE_FULL_OUTER_JOINヒントを適用します。NO_NATIVE_FULL_OUTER_JOINヒントでは、オプティマイザに対して、指定した各表を結合する際にネイティブの実行方法を除外するように指示します。かわりに、左外部結合とアンチ結合を組み合せたものとして完全外部結合が実行されます。

左側に複数の表がある外部結合

Oracle Database 12cでは、外部結合された表の左側に複数の表を配置できます。この拡張により、複数の表を含み、外部結合の左側に表示されるビューをマージできるようになりました。

Oracle Database 12c以前のリリースでは、次のような問合せは無効であり、ORA-01417エラー・メッセージが表示されます。

SELECT t1.d, t3.c
FROM   t1, t2, t3
WHERE  t1.z = t2.z 
AND    t1.x = t3.x (+) 
AND    t2.y = t3.y (+);

Oracle Database 12c以降では、前述の問合せは有効です。

セミ結合

セミ結合は、副問合せデータ・セットに一致する行が存在する場合に、1つ目のデータ・セットから行が返される、2つのデータ・セット間の結合です。最初の一致が検出された時点で、2つ目のデータ・セットの処理が停止されます。そのため、最適化により、2つ目のデータ・セットの複数の行が副問合せ基準に一致する場合に、1つ目のデータ・セットの行が複製されることはありません。


注意:

セミ結合とアンチ結合は、それらを実行するSQL構文が副問合せであっても、結合タイプとして考慮されます。これらは、副問合せ構文を結合形式で解決できるようにフラット化するため、オプティマイザによって使用される内部アルゴリズムです。

オプティマイザによってセミ結合が考慮される場合

一致が存在するかどうかさえ判別できればよい場合は、セミ結合によって大量の行が返されることを回避できます。大きなデータ・セットでは、この最適化によって、外部問合せのすべての行への内部問合せから返されるすべてのレコードを反復処理する必要があるネステッド・ループ結合で、大きな時間の節約が可能です。セミ結合は、ネステッド・ループ結合、ハッシュ結合、ソート/マージ結合に適用できます。

次の状況では、オプティマイザによってセミ結合が選択される可能性があります。

  • 文でIN句またはEXISTS句を使用します。

  • 文のIN句またはEXISTS句に、副問合せを含みます。

  • IN句またはEXISTS句が、OR分岐の内部に含まれません。

セミ結合の仕組み

セミ結合による最適化は、使用される結合のタイプに応じて実装が異なります。次の擬似コードで、ネステッド・ループ結合のセミ結合を示します。

FOR ds1_row IN ds1 LOOP
  match := false;
  FOR ds2_row IN ds2 LOOP
    IF (ds1_row matches ds2_row) THEN
      match := true;
      EXIT -- stop processing second data set when a match is found
    END IF
  END LOOP
  IF (match = true) THEN 
    RETURN ds1_row
  END IF
END LOOP

この擬似コードでは、ds1が1つ目のデータ・セットで、ds2が副問合せデータ・セットです。このコードでは、1つ目のデータ・セットの最初の行が取得され、次に副問合せデータ・セットの反復処理によって一致が検索されます。一致が見つかった時点で内部ループを抜けて、1つ目のデータ・セットの次の行の処理が開始されます。

例7-12 WHERE EXISTSを使用したセミ結合

次の例では、WHERE EXISTS句を使用して、従業員を含む部門のみが表示されます。

SELECT department_id, department_name 
FROM   departments
WHERE EXISTS (SELECT 1
              FROM   employees 
              WHERE  employees.department_id = departments.department_id)

実行計画では、手順1にNESTED LOOPS SEMI操作が示されています。

----------------------------------------------------------------------------------
| Id| Operation          | Name              |Rows| Bytes |Cost (%CPU)| Time     |
----------------------------------------------------------------------------------
| 0 | SELECT STATEMENT   |                   |    |       |    2 (100)|          |
| 1 |  NESTED LOOPS SEMI |                   | 11 |   209 |    2   (0)| 00:00:01 |
| 2 |   TABLE ACCESS FULL| DEPARTMENTS       | 27 |   432 |    2   (0)| 00:00:01 |
|*3 |   INDEX RANGE SCAN | EMP_DEPARTMENT_IX | 44 |   132 |    0   (0)|          |
----------------------------------------------------------------------------------

外部ループを形成するdepartmentsの各行ごとに部門IDが取得されて、employees.department_id索引で一致するエントリが検索されます。概念上、索引は次のようになります。

10,rowid
10,rowid
10,rowid
10,rowid
30,rowid
30,rowid
30,rowid
...

departments表の最初のエントリが部門30の場合、最初の30のエントリが見つかるまで索引のレンジ・スキャンが行われ、見つかった時点で索引の読取りが停止され、一致した行がdepartmentsから返されます。外部ループの次の行が部門20の場合、索引で20のエントリが検索されますが一致は見つからず、外部ループの次の反復処理に移ります。こうして、一致するすべての行が返されるまで処理が行われます。

例7-13 INを使用したセミ結合

次の問合せでは、IN句が使用されて、従業員を含む部門のみが表示されます。

SELECT department_id, department_name
FROM   departments
WHERE  department_id IN 
       (SELECT department_id 
        FROM   employees); 

実行計画では、手順1にNESTED LOOPS SEMI操作が示されています。

----------------------------------------------------------------------------------
| Id| Operation          | Name              |Rows| Bytes |Cost (%CPU)| Time     |
----------------------------------------------------------------------------------
| 0 | SELECT STATEMENT   |                   |    |       |    2 (100)|          |
| 1 |  NESTED LOOPS SEMI |                   | 11 |   209 |    2   (0)| 00:00:01 |
| 2 |   TABLE ACCESS FULL| DEPARTMENTS       | 27 |   432 |    2   (0)| 00:00:01 |
|*3 |   INDEX RANGE SCAN | EMP_DEPARTMENT_IX | 44 |   132 |    0   (0)|          |
----------------------------------------------------------------------------------

この計画は、例7-12「WHERE EXISTSを使用したセミ結合」の計画と同一です。

アンチ結合

アンチ結合は、副問合せデータ・セットに一致する行が存在しない場合に、1つ目のデータ・セットから行が返される、2つのデータ・セット間の結合です。セミ結合と同様、アンチ結合でも、最初の一致が見つかった時点で副問合せデータ・セットの処理が停止されます。セミ結合と異なり、アンチ結合では一致が見つからなかった場合のみ行が返されます。

オプティマイザによってアンチ結合が考慮される場合

アンチ結合を使用すると、一致が存在しない場合のみ行を返す必要がある場合に、不必要な処理が避けられます。大きなデータ・セットでは、この最適化によって、外部問合せのすべての行への内部問合せから返されるすべてのレコードを反復処理する必要があるネステッド・ループ結合で、大きな時間の節約が可能です。アンチ結合による最適化は、ネステッド・ループ結合、ハッシュ結合、ソート/マージ結合に適用できます。

次の状況では、オプティマイザによってアンチ結合が選択される可能性があります。

  • 文でNOT IN句またはNOT EXISTS句を使用します。

  • 文のNOT IN句またはNOT EXISTS句に、副問合せが含まれます。

  • NOT IN句またはNOT EXISTS句が、OR分岐の内部に含まれません。

  • 次の例のように、外部結合を実行し、IS NULL条件を結合列に適用します。

    SET AUTOTRACE TRACEONLY EXPLAIN
    SELECT emp.*
    FROM   emp, dept
    WHERE  emp.deptno = dept.deptno(+)
    AND    dept.deptno IS NULL
    
    Execution Plan
    ----------------------------------------------------------
    Plan hash value: 1543991079
     
    ---------------------------------------------------------------------------
    | Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
    ---------------------------------------------------------------------------
    |   0 | SELECT STATEMENT   |      |    14 |  1400 |     5  (20)| 00:00:01 |
    |*  1 |  HASH JOIN ANTI    |      |    14 |  1400 |     5  (20)| 00:00:01 |
    |   2 |   TABLE ACCESS FULL| EMP  |    14 |  1218 |     2   (0)| 00:00:01 |
    |   3 |   TABLE ACCESS FULL| DEPT |     4 |    52 |     2   (0)| 00:00:01 |
    ---------------------------------------------------------------------------
     
    Predicate Information (identified by operation id):
    ---------------------------------------------------
     
       1 - access("EMP"."DEPTNO"="DEPT"."DEPTNO")
     
    Note
    -----
       - dynamic statistics used: dynamic sampling (level=2)
    

アンチ結合の仕組み

アンチ結合による最適化は、使用される結合のタイプに応じて実装が異なります。次の擬似コードで、ネステッド・ループ結合のアンチ結合を示します。

FOR ds1_row IN ds1 LOOP
  match := true;
  FOR ds2_row IN ds2 LOOP
    IF (ds1_row matches ds2_row) THEN
      match := false;
      EXIT -- stop processing second data set when a match is found
    END IF
  END LOOP
  IF (match = true) THEN 
    RETURN ds1_row
  END IF
END LOOP

この擬似コードでは、ds1が1つ目のデータ・セットで、ds2が2つ目のデータ・セットです。このコードでは、1つ目のデータ・セットの最初の行が取得され、次に2つ目のデータ・セットの反復処理によって一致が検索されます。一致が見つかった時点で内部ループを抜けて、1つ目のデータ・セットの次の行の処理が開始されます。

例7-14 WHERE EXISTSを使用したセミ結合

次の例では、WHERE EXISTS句を使用して、従業員を含む部門のみが表示されます。

SELECT department_id, department_name 
FROM   departments
WHERE EXISTS (SELECT 1
              FROM   employees 
              WHERE  employees.department_id = departments.department_id)

実行計画では、手順1にNESTED LOOPS SEMI操作が示されています。

----------------------------------------------------------------------------------
| Id| Operation          | Name              |Rows| Bytes |Cost (%CPU)| Time     |
----------------------------------------------------------------------------------
| 0 | SELECT STATEMENT   |                   |    |       |    2 (100)|          |
| 1 |  NESTED LOOPS SEMI |                   | 11 |   209 |    2   (0)| 00:00:01 |
| 2 |   TABLE ACCESS FULL| DEPARTMENTS       | 27 |   432 |    2   (0)| 00:00:01 |
|*3 |   INDEX RANGE SCAN | EMP_DEPARTMENT_IX | 44 |   132 |    0   (0)|          |
----------------------------------------------------------------------------------

外部ループを形成するdepartmentsの各行ごとに部門IDが取得されて、employees.department_id索引で一致するエントリが検索されます。概念上、索引は次のようになります。

10,rowid
10,rowid
10,rowid
10,rowid
30,rowid
30,rowid
30,rowid
...

departments表の最初のレコードが部門30の場合、最初の30のエントリが見つかるまで索引のレンジ・スキャンが行われ、見つかった時点で索引の読取りが停止され、一致した行がdepartmentsから返されます。外部ループの次の行が部門20の場合、索引で20のエントリが検索されますが一致は見つからず、外部ループの次の反復処理に移ります。こうして、一致するすべての行が返されるまで処理が行われます。

アンチ結合でNULLが処理される仕組み

セミ結合では、INEXISTSは、機能的に同じです。ただし、NOT INNOT EXISTSは、機能的に同等ではありません。この違いはNULLが原因です。NULL値がNOT IN演算子に返される場合、文からはレコードが返されません。この理由を理解するために、次のWHERE句を検討します。

WHERE department_id NOT IN (null, 10, 20)

この式は次のようにテストされます。

WHERE (department_id != null) AND (department_id != 10) AND (department_id != 20)

式全体がtrueになるには、各条件がtrueになる必要があります。ただし、NULL値は他の値と比較することができないためにdepartment_id !=null条件がtrueになることはできず、したがって式全体がtrueになることができません。次の手法を使用すると、文のNOT IN演算子にNULLが返された場合でも、レコードを返させることができます。

  • 副問合せから返された列にNVL関数を適用します。

  • 副問合せにIS NOT NULL述語を追加します。

  • NOT NULL制約を実装します。

NOT INとは異なり、NOT EXISTS句では、一致の存在を返す述語のみが考慮され、一致のない行やNULLのために判定不可能な行は無視されます。副問合せにおいて、少なくとも1行が外部問合せの行と一致している場合、NOT EXISTSによってfalseが返されます。一致しているタプルが存在しない場合、NOT EXISTSによってtrueが返されます。副問合せにおけるNULLの存在は、一致レコードの検索に影響しません。

Oracle Database 11gより前のリリースでは、副問合せでNULLが返される可能性がある場合に、オプティマイザでアンチ結合による最適化を使用することができませんでした。ただし、Oracle Database 11gからは、次の項で説明するANTI NA (およびANTI SNA)最適化によって、NULLが返される可能性がある場合でも、オプティマイザによるアンチ結合の使用が可能になりました。

例7-15 NOT INを使用したアンチ結合

ユーザーは、NOT IN句を使用した次の問合せを発行して、従業員を含まない部門を表示するとします。

SELECT department_id, department_name
FROM   departments
WHERE  department_id NOT IN 
       (SELECT department_id 
        FROM   employees);

この問合せでは、たとえ従業員を含まない部門が複数存在しても、行が返されません。ユーザーの意図とは異なるこのような結果が生じるのは、employees.department_id列がNULL値可能なためです。

実行計画では、手順2にNESTED LOOPS ANTI SNA操作が示されています。

----------------------------------------------------------------------------------
| Id| Operation              | Name              |Rows|Bytes| Cost (%CPU) | Time |
----------------------------------------------------------------------------------
| 0 | SELECT STATEMENT       |                   |    |     |  4 (100)|          |
|*1 |  FILTER                |                   |    |     |         |          |
| 2 |   NESTED LOOPS ANTI SNA|                   | 17 | 323 |  4  (50)| 00:00:01 |
| 3 |    TABLE ACCESS FULL   | DEPARTMENTS       | 27 | 432 |  2   (0)| 00:00:01 |
|*4 |    INDEX RANGE SCAN    | EMP_DEPARTMENT_IX | 41 | 123 |  0   (0)|          |
|*5 |   TABLE ACCESS FULL    | EMPLOYEES         |  1 |   3 |  2   (0)| 00:00:01 |
----------------------------------------------------------------------------------
 
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter( IS NULL)
   4 - access("DEPARTMENT_ID"="DEPARTMENT_ID")
   5 - filter("DEPARTMENT_ID" IS NULL)

ANTI SNAは、NULL認識単一アンチ結合を表します。ANTI NAは、NULL認識アンチ結合を表します。NULL認識操作が使用されると、NULL値可能列に対してもセミ結合の使用が可能になります。Oracle Database 11gより前のリリースでは、NULL値が可能な場合にNOT IN問合せでアンチ結合が実行できませんでした。

このユーザーが問合せを書き換えて、副問合せにIS NOT NULL条件を適用するとします。

SELECT department_id, department_name
FROM   departments
WHERE  department_id NOT IN 
       (SELECT department_id 
        FROM   employees
        WHERE  department_id IS NOT NULL);

この問合せでは16行が返され、意図した結果が得られます。計画の手順1には、ANTI NA結合やANTI SNA結合のかわりに、標準のNESTED LOOPS ANTI結合が示されています。

----------------------------------------------------------------------------------
| Id | Operation          | Name              | Rows| Bytes | Cost (%CPU)| Time  |
----------------------------------------------------------------------------------
|  0 | SELECT STATEMENT   |                   |     |       |  2 (100)|          |
|  1 |  NESTED LOOPS ANTI |                   |  17 |   323 |  2   (0)| 00:00:01 |
|  2 |   TABLE ACCESS FULL| DEPARTMENTS       |  27 |   432 |  2   (0)| 00:00:01 |
|* 3 |   INDEX RANGE SCAN | EMP_DEPARTMENT_IX |  41 |   123 |  0   (0)|          |
----------------------------------------------------------------------------------
 
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
 
   3 - access("DEPARTMENT_ID"="DEPARTMENT_ID")
       filter("DEPARTMENT_ID" IS NOT NULL)

例7-16 NOT EXISTSを使用したアンチ結合

ユーザーは、NOT EXISTS句を使用した次の問合せを発行して、従業員を含まない部門を表示するとします。

SELECT department_id, department_name
FROM   departments d
WHERE  NOT EXISTS
       (SELECT null
        FROM   employees e
        WHERE  e.department_id = d.department_id)

この問合せでは、NOT IN句のNULL問題を回避できます。そのため、たとえemployees.department_id列がNULL値可能な場合でも、意図した結果が得られます。

実行計画の手順1には、ANTI NAバリアントではなく、NESTED LOOPS ANTI操作が示されています(これはNULL値が可能な場合、NOT INに必要です)。

----------------------------------------------------------------------------------
| Id  | Operation          | Name              | Rows  | Bytes | Cost (%CPU)|Time|
----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |                   |       |       | 2 (100)|        |
|   1 |  NESTED LOOPS ANTI |                   |    17 |   323 | 2   (0)|00:00:01|
|   2 |   TABLE ACCESS FULL| DEPARTMENTS       |    27 |   432 | 2   (0)|00:00:01|
|*  3 |   INDEX RANGE SCAN | EMP_DEPARTMENT_IX |    41 |   123 | 0   (0)|        |
----------------------------------------------------------------------------------
 
PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
 
   3 - access("E"."DEPARTMENT_ID"="D"."DEPARTMENT_ID")

結合の最適化

この項では、一般的な結合の最適化について説明します。

ブルーム・フィルタ

作成者Burton Bloomにちなんで名付けられたブルーム・フィルタは、集合の要素かどうかをテストする、低メモリーのデータ構造です。ブルーム・フィルタでは、ある要素が集合に属していない場合は正確に示されますが、ある要素が集合に属している場合は誤って示される場合があります。つまり、偽陰性の可能性はありませんが、擬陽性の可能性があります。

ブルーム・フィルタの目的

ブルーム・フィルタは、データ・セットのデータ量に比べて、フィルタの格納に必要なメモリー量が小さく、かつほとんどのデータが要素テストに落ちると予想される場合に、特に便利です。

Oracle Databaseでは、次のような様々な目的のためにブルーム・フィルタが使用されます。

  • パラレル問合せにおいて、特にほとんどの行が結合条件に一致しないため破棄される場合に、スレーブ・プロセスに転送されるデータ量を低減します。

  • パーティション・プルーニングと呼ばれる結合においてパーティション・アクセス・リストを作成する場合に、不必要なパーティションを排除します。

  • サーバーの結果キャッシュにデータが存在するかどうかをテストして、ディスクの読取りを回避します。

  • 特にスター・スキーマで大きなファクト表と小さなディメンション表を結合する場合に、Exadataセルの要素をフィルタします。

ブルーム・フィルタは、パラレル処理とシリアル処理の両方で実行される可能性があります。

ブルーム・フィルタの仕組み

ブルーム・フィルタでは、集合に含まれるかどうかを示すためにビット配列が使用されます。たとえば、最初は配列の8要素が0に設定されています(8要素は、この例で使用する任意の数です)。

e1 e2 e3 e4 e5 e6 e7 e8
 0  0  0  0  0  0  0  0

この配列は集合を表しています。この配列で入力値iを表すために、3つの独立したハッシュ関数が、iに適用され(3つというのは、この例で使用する任意の数です)、それぞれの関数で1から8のハッシュ値が生成されます。

f1(i) = h1
f2(i) = h2
f3(i) = h3

この配列に値17を格納するために、2つのハッシュ関数でi17に設定されて、次のハッシュ値が返されます。

f1(17) = 5
f2(17) = 3
f3(17) = 5

この例では、2つのハッシュ関数でたまたま同じ値5が返されました(ハッシュ衝突と呼ばれます)。個別のハッシュ値は53であるため、配列の5番目と3番目の要素に1が設定されます。

e1 e2 e3 e4 e5 e6 e7 e8
 0  0  1  0  1  0  0  0

17がこの集合の要素かどうかをテストするには、逆の手順が実行されます。値17がこの集合から除外されることをテストするには、要素3または要素50が入る必要があります。どちらかの要素に0が入る場合、集合に17が含まれる可能性はありません。偽陰性はありえません。

17がこの集合に包含されることをテストするには、要素3と要素5の両方に1が入る必要があります。ただし、テストで両方の要素に1が入ることが示されても、集合に17が含まれない可能性は残ります。偽陽性はありえます。たとえば、次の配列も要素3と要素5はともに1ですが、値22が表されている可能性があります。

e1 e2 e3 e4 e5 e6 e7 e8
 1  0  1  0  1  0  0  0

ブルーム・フィルタの制御

ブルーム・フィルタを使用するかどうかは、オプティマイザで自動的に決定されます。オプティマイザの決定をオーバーライドするには、PX_JOIN_FILTERヒントとNO_PX_JOIN_FILTERヒントを使用します。


関連項目:

ブルーム・フィルタのヒントの詳細は、『Oracle Database SQL言語リファレンス』を参照してください。

ブルーム・フィルタのメタデータ

次の動的パフォーマンス・ビューには、ブルーム・フィルタのメタデータが含まれています。

  • V$SQL_JOIN_FILTER

    このビューでは、アクティブなブルーム・フィルタで除外された行数(FILTERED列)およびテストされた行数(PROBED列)が表示されます。

  • V$PQ_TQSTAT

    このビューでは、実行ツリーの各段階ごとに、各パラレル実行サーバーで処理される行数が表示されます。このビューを使用して、パラレル・プロセス間のデータ転送が、ブルーム・フィルタによってどの程度削減されているかが監視できます。

実行計画において、ブルーム・フィルタはOperation列のキーワードJOIN FILTERおよびName列の接頭辞:BFで示されます(次の計画のスニペットの手順9に示されているとおりです)。

----------------------------------------------------------------------------
| Id  | Operation                  | Name     |    TQ  |IN-OUT| PQ Distrib |
----------------------------------------------------------------------------
...
|   9 |      JOIN FILTER CREATE    | :BF0000  |  Q1,03 | PCWP |            |

計画のPredicate Information項において、文字列SYS_OP_BLOOM_FILTERで始まる関数を含むフィルタは、ブルーム・フィルタが使用されていることを示しています。

ブルーム・フィルタ: シナリオ

次のパラレル問合せでは、salesファクト表がproductsディメンション表およびtimesディメンション表に結合されて、営業週18でフィルタ処理されます。

SELECT /*+ parallel(s) */ p.prod_name, s.quantity_sold
FROM   sh.sales s, sh.products p, sh.times t 
WHERE  s.prod_id = p.prod_id
AND    s.time_id = t.time_id
AND    t.fiscal_week_number = 18;

DBMS_XPLAN.DISPLAY_CURSORの問合せによって、次の出力が得られます。

SELECT * FROM
  TABLE(DBMS_XPLAN.DISPLAY_CURSOR(format => 'BASIC,+PARALLEL,+PREDICATE'));

EXPLAINED SQL STATEMENT:
------------------------
SELECT /*+ parallel(s) */ p.prod_name, s.quantity_sold FROM sh.sales s,
sh.products p, sh.times t WHERE s.prod_id = p.prod_id AND s.time_id =
t.time_id AND t.fiscal_week_number = 18
 
Plan hash value: 1183628457
 
----------------------------------------------------------------------------
| Id  | Operation                  | Name     |    TQ  |IN-OUT| PQ Distrib |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT           |          |        |      |            |
|   1 |  PX COORDINATOR            |          |        |      |            |
|   2 |   PX SEND QC (RANDOM)      | :TQ10003 |  Q1,03 | P->S | QC (RAND)  |
|*  3 |    HASH JOIN BUFFERED      |          |  Q1,03 | PCWP |            |
|   4 |     PX RECEIVE             |          |  Q1,03 | PCWP |            |
|   5 |      PX SEND BROADCAST     | :TQ10001 |  Q1,01 | S->P | BROADCAST  |
|   6 |       PX SELECTOR          |          |  Q1,01 | SCWC |            |
|   7 |        TABLE ACCESS FULL   | PRODUCTS |  Q1,01 | SCWP |            |
|*  8 |     HASH JOIN              |          |  Q1,03 | PCWP |            |
|   9 |      JOIN FILTER CREATE    | :BF0000  |  Q1,03 | PCWP |            |
|  10 |       BUFFER SORT          |          |  Q1,03 | PCWC |            |
|  11 |        PX RECEIVE          |          |  Q1,03 | PCWP |            |
|  12 |         PX SEND HYBRID HASH| :TQ10000 |        | S->P | HYBRID HASH|
|* 13 |          TABLE ACCESS FULL | TIMES    |        |      |            |
|  14 |      PX RECEIVE            |          |  Q1,03 | PCWP |            |
|  15 |       PX SEND HYBRID HASH  | :TQ10002 |  Q1,02 | P->P | HYBRID HASH|
|  16 |        JOIN FILTER USE     | :BF0000  |  Q1,02 | PCWP |            |
|  17 |         PX BLOCK ITERATOR  |          |  Q1,02 | PCWC |            |
|* 18 |          TABLE ACCESS FULL | SALES    |  Q1,02 | PCWP |            |
----------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   3 - access("S"."PROD_ID"="P"."PROD_ID")
   8 - access("S"."TIME_ID"="T"."TIME_ID")
  13 - filter("T"."FISCAL_WEEK_NUMBER"=18)
  18 - access(:Z>=:Z AND :Z<=:Z)
       filter(SYS_OP_BLOOM_FILTER(:BF0000,"S"."TIME_ID"))

シングル・サーバー・プロセスでtimes表がスキャンされ(手順13)、次にハイブリッド・ハッシュ分散方法を使用して、行がパラレル実行サーバーに送信されます(手順12)。セットQ1,03のプロセスによって、ブルーム・フィルタが作成されます(手順9)。セットQ1,02のプロセスによってsalesがパラレルでスキャンされ(手順18)、次にハイブリッド・ハッシュ分散によって行がセットQ1,03に送信される(手順15)前に、ブルーム・フィルタの使用によって行がsalesから破棄されます(手順16)。セットQ1,03のプロセスによって、times行がフィルタ処理済のsales行にハッシュ結合されます(手順8)。セットQ1,01のプロセスによってproductsがスキャンされた後(手順7)、行がQ1,03に送信されます(手順5)。最後にQ1,03のプロセスによって、products行が前回のハッシュ結合で生成された行に結合されます(手順3)。

基本的なプロセスは次のとおりです。

tgsql_vm_082.pngの説明は次にあります
図tgsql_vm_082.pngの説明

パーティション・ワイズ結合

パーティション・ワイズ結合は、2つの表の大規模な結合を分割する結合最適化です(一方の表が、結合キーで複数の小規模な結合にパーティション化されている必要があります)。パーティション・ワイズ結合は、次のいずれかです。

  • フル・パーティション・ワイズ結合

    両方の表が、結合キーによって同一レベル・パーティション化されているか、参照パーティション化されている(つまり、参照制約によって関連付けられている)必要があります。2つのパーティション間で2つの結合済表から、大きな結合が小さな結合に分割されます。

  • パーシャル・パーティション・ワイズ結合

    1つの表のみが、結合キーでパーティション化されます。もう一方の表は、パーティション化してもしなくてもかまいません。


関連項目:

『Oracle Database VLDBおよびパーティショニング・ガイド』には、パーティション・ワイズ結合の詳細な説明があります。

パーティション・ワイズ結合の目的

パーティション・ワイズ結合では、結合がパラレルで実行されるときにパラレル実行サーバー間で交換されるデータ量が最小限に抑えられ、問合せのレスポンス時間が短縮されます。この手法により、レスポンス時間は大幅に短縮され、CPUとメモリーの使用率が改善されます。Oracle Real Application Clusters (Oracle RAC)環境では、パーティション・ワイズ結合でも、インターコネクトでのデータ・トラフィックが回避されるか、少なくとも制限されます。これは、大規模な結合操作で優れたスケーラビリティを実現するために重要です。

パーティション・ワイズ結合の仕組み

2つのパーティション化された表が、パーティション・ワイズ結合を使用することなくシリアル結合される場合は、図7-6に示されるように、シングル・サーバー・プロセスによって結合が実行されます。この例では、シングル・サーバー・プロセスによって表 t1のすべてのパーティションが表t2のすべてのパーティションに結合されているため、結合はパーティション・ワイズではありません

図7-6 パーティション・ワイズではない結合

図7-6の説明が続きます
「図7-6 パーティション・ワイズではない結合」の説明

フル・パーティション・ワイズ結合の仕組み

図7-7は、パラレルで実行されたフル・パーティション・ワイズ結合を示しています(シリアルでも実行可能です)。この場合、並列度のグラニュルはパーティションです。各パラレル実行サーバーにおいて、パーティションが対になって結合されます。たとえば、1つ目のパラレル実行サーバーでは、t1の1つ目のパーティションがt2の1つ目のパーティションと結合されます。その結果が、パラレル実行コーディネータで組み合わされます。

図7-7 パラレルでのフル・パーティション・ワイズ結合

図7-7の説明が続きます
「図7-7 パラレルでのフル・パーティション・ワイズ結合」の説明

フル・パーティション・ワイズ結合によって、パーティションをサブパーティションに結合することも可能です(各表で異なるパーティション化の方法が使用されている場合に有益です)。たとえば、customersはハッシュでパーティション化されていますが、salesは、レンジでパーティション化されているとします。salesをハッシュでサブパーティション化すると、customersのハッシュ・パーティションとsalesのハッシュ・サブパーティションとの間でフル・パーティション・ワイズ結合を実行できます。

次のスニペットのように、実行計画において結合前にパーティション操作が実行される場合は、フル・パーティション・ワイズ結合が実行されることを示唆しています。

|   8 |         PX PARTITION HASH ALL|
|*  9 |          HASH JOIN           |

関連項目:

『Oracle Database VLDBおよびパーティショニング・ガイド』には、パーティション・ワイズ結合の詳細な説明があり、いくつかの例が紹介されています。

パーシャル・パーティション・ワイズ結合の仕組み

これに対し、図7-8の例は、パーティション化されているt1とパーティション化されていないt2の間のパーシャル・パーティション・ワイズ結合を示しています。フル・パーティション・ワイズ結合と異なり、パーシャル・パーティション・ワイズ結合はパラレルで実行される必要があります。

t2はパーティション化されていないため、必要に応じ、パラレル実行サーバーのセットによって、t2からパーティションが生成される必要があります。次に、別のパラレル実行サーバーのセットによって、t1のパーティションが、動的に生成されるパーティションに結合されます。その結果が、パラレル実行コーディネータで組み合わされます。

図7-8 パーシャル・パーティション・ワイズ結合

図7-8の説明が続きます
「図7-8 パーシャル・パーティション・ワイズ結合」の説明

次のスニペットのように、実行計画におけるPX SEND PARTITION (KEY)操作は、パーシャル・パーティション・ワイズ結合が実行されることを示唆しています。

|  11 |            PX SEND PARTITION (KEY)    |

関連項目:

『Oracle Database VLDBおよびパーティショニング・ガイド』には、パーティション・ワイズ結合の詳細な説明があり、いくつかの例が紹介されています。