インデックスを使ったgroup by


Applies to
DB2Yes
MySQLYes
OracleYes
PostgreSQLYes
SQL ServerYes

SQLデータベースは、全く異なる2つのgroup byの アルゴリズムを使用します。1つ目はハッシュアルゴリズムで、 入力されたレコードを一時的なハッシュテーブル上でまとめ上げます。 全てのレコードが処理されたら、ハッシュテーブルが結果として返されます。 2つ目は、ソート・グループアルゴリズムで、入力されたデータをグループキーで ソートすることで、各グループを順番に処理できるようにします。その後、 それらをデータベースがまとめます。一般的には、どちらのアルゴリズムも 中間結果をマテリアライズする必要があるので、パイプライン的に処理されることは ありません。しかし、ソート・グループアルゴリズムでは、ソート処理を しないためにインデックスを使えるので、パイプライン化された group by処理が可能になります。

注記

MySQL 5.6はハッシュアルゴリズムを使いません。しかし、これから述べるソート・グループ アルゴリズムの最適化手法は適用できます。

次のような、PRODUCT_IDごとの昨日の利益を得るための クエリを考えてみましょう。

SELECT product_id, sum(eur_value)
  FROM sales
 WHERE sale_date = TRUNC(sysdate) - INTERVAL '1' DAY
 GROUP BY product_id

前の節で定義した SALE_DATEPRODUCT_IDのインデックスを知っていると、 INDEX RANGE SCANが自動的に必要な順序に並んだ状態で結果を 出してくれるので、ソート・グループアルゴリズムが適していると 分かるでしょう。つまり、明示的なソートは不要で、パイプライン化された group byとして実行されるので、マテリアライズが 必要なくなるのです。

DB2
Explain Plan
------------------------------------------------------------
ID | Operation             |                     Rows | Cost
 1 | RETURN                |                          |  675
 2 |  GRPBY (COMPLETE)     |      25 of 387 (  6.46%) |  675
 3 |   FETCH SALES         |     387 of 387 (100.00%) |  675
 4 |    IXSCAN SALES_DT_PR | 387 of 1009326 (   .04%) |   24

Predicate Information
 4 - START (Q1.SALE_DATE = (CURRENT DATE - 1 DAYS))
      STOP (Q1.SALE_DATE = (CURRENT DATE - 1 DAYS))
Oracle
---------------------------------------------------------------
|Id |Operation                    | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT             |             |   17 |  192 |
| 1 | SORT GROUP BY NOSORT        |             |   17 |  192 |
| 2 |  TABLE ACCESS BY INDEX ROWID| SALES       |  321 |  192 |
|*3 |   INDEX RANGE SCAN          | SALES_DT_PR |  321 |    3 |
---------------------------------------------------------------

Oracleの実行計画では、パイプライン化されたSORT GROUP BYに、 NOSORTという補足がついています。他のデータベースの実行計画では、 ソート処理については特に言及されません。

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

パイプライン化されたgroup byは、 ASCあるいはDESCがない時以外は、 パイプライン化されたorder byと同じ前提条件があります。 つまり、ASCDESC修飾語を付けてインデックスを 定義した場合は、パイプライン化されたgroup byの実行には 影響しないはずということです。同じことが、NULLS FIRSTLASTにも言えます。しかし、 パイプライン化されたgroup byに、ASCDESC付きのインデックスを正しく使えないデータベースも 存在します。

警告

PostgreSQLでは、パイプライン化されたgroup byNULLS LASTのソート条件がついたインデックスを使うには、 order byを追加する必要があります。

Oracleでは、後にorder byがある パイプライン化されたgroup byでは、 インデックスを逆順に読めません。

詳しくは付録のPostgreSQLOracleの項を参照してください。

パイプライン化されたorder byの例でのように、 昨日からの全ての売上を取得するようクエリを 拡張する場合、前と同じ理由でパイプライン化されたgroup byができません。INDEX RANGE SCANが、グループキー(図 6.1と比較してみましょう)の順に 並んだ状態になっていないのです。

SELECT product_id, sum(eur_value)
  FROM sales
 WHERE sale_date >= TRUNC(sysdate) - INTERVAL '1' DAY
 GROUP BY product_id
DB2
Explain Plan
--------------------------------------------------------------------
ID | Operation                   |                      Rows |  Cost
 1 | RETURN                      |                           | 12527
 2 |  GRPBY (FINAL)              |        25 of 25 (100.00%) | 12527
 3 |   TBSCAN                    |        25 of 25 (100.00%) | 12527
 4 |    SORT (INTERMEDIATE)      |        25 of 25 (100.00%) | 12527
 5 |     GRPBY (HASHED PARTIAL)  |      25 of 8050 (   .31%) | 12527
 6 |      FETCH SALES            |    8050 of 8050 (100.00%) | 12526
 7 |       RIDSCN                |    8050 of 8050 (100.00%) |   375
 8 |        SORT (UNQIUE)        |    8050 of 8050 (100.00%) |   375
 9 |         IXSCAN SALES_DT_PR  | 8050 of 1009326 (   .80%) |   372

結果の取得には次のwhere句が必要です。 WHERE sale_date >= CURRENT_DATE - 1 MONTH

Oracleの実行計画と比べるとかなり複雑ですが、これには 次の2つの背景があります。

  • DB2では、インデックスアクセスとテーブルアクセスの間の 物理的なストレージ位置の違いによるソート処理を 明示的に表示しています(7と8の間)。

  • DB2は、データのグルーピングを2段階で行っています。 最初に、できるだけ早い段階でソートされるデータの量を減らすために、 一次的なグルーピングを行っています(Operation 5)。それから、 通常のSORT + GRPBYを実行しています。

Oracle
---------------------------------------------------------------
|Id |Operation                    | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT             |             |   24 |  356 |
| 1 | HASH GROUP BY               |             |   24 |  356 |
| 2 |  TABLE ACCESS BY INDEX ROWID| SALES       |  596 |  355 |
|*3 |   INDEX RANGE SCAN          | SALES_DT_PR |  596 |    4 |
---------------------------------------------------------------

Oracleは、ハッシュアルゴリズムを使います。ハッシュアルゴリズムの利点は、 まとめられた結果だけをバッファすれば良い点です。一方で ソート・グループアルゴリズムは全ての入力セットを マテリアライズします。つまり、ハッシュアルゴリズムの方が メモリを使わずに済みます。

パイプライン化されたorder byと同じく、 パイプライン化されたgroup byでは、高速に実行できる事が 最も重要だというわけではありません。データベースがパイプライン化された 方法で実行ができ、全ての入力を待つ前に結果を出力できる事の方が、 より重要視されます。これは、次の章で説明する、 高度な最適化方法の前提条件でもあります。

この説明が気に入れば、きっと この本も 気に入るはず。

考えてみよう

ソートやグルーピングの他に、 ソートをしないためにインデックスが使えるデータベース処理は あるでしょうか?

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