by Hayato Matsuura.

大なり、小なり、BETWEEN


INDEX RANGE SCANにおいて、パフォーマンスへの影響が最も大きいのは、リーフノードの走査です。インデックスをスキャンする範囲をできる限り小さく保つのは、インデックスを作る上での黄金則です。インデックスのスキャンがどこから始まってどこで終わるのか、自分に問いかけて確認しましょう。

SQL文内で、始点と終点の条件が明示的に書かれているなら、答えは簡単です。

SELECT first_name, last_name, date_of_birth
  FROM employees
 WHERE date_of_birth >= TO_DATE(?, 'YYYY-MM-DD')
   AND date_of_birth <= TO_DATE(?, 'YYYY-MM-DD')

指定された範囲内で、DATE_OF_BIRTHのインデックスがスキャンされます。スキャンは、最初の日付から始まり、2番目の日付で終わります。これ以上、スキャンされるインデックスの範囲を狭めることはできません。

2つ目の列が登場すると、始点と終点がだんだん分からなくなってきます。

SELECT first_name, last_name, date_of_birth
  FROM employees
 WHERE date_of_birth >= TO_DATE(?, 'YYYY-MM-DD')
   AND date_of_birth <= TO_DATE(?, 'YYYY-MM-DD')
   AND subsidiary_id  = ?

もちろん、理想的なインデックスはどちらの列も扱えるものでなければなりませんが、その時の列の並び順はどうなるのでしょうか?

次の図は、インデックスを範囲検索する際の列の順番の影響を 表しています。この図では、IDが27の子会社に在籍する、1971年1月1日から1月9日に生まれた従業員を全て検索しています。

図2.2 では、DATE_OF_BIRTHSUBSIDIARY_IDの 順に並んだインデックスの詳細を図示しています。リーフノードチェーンをたどり始めるのはどこでしょうか?言い換えると、ツリーの走査はどこで終わるのでしょうか?

図2.2DATE_OF_BIRTHSUBSIDIARY_IDの インデックスに対する範囲検索

インデックスは、まず誕生日の順に並んでいます。同じ日に生まれた 従業員が2人いる時だけ、そのレコードを並び替えるのにSUBSIDIARY_ID が使われます。一方で、クエリは日付の範囲を 指定していますので、SUBSIDIARY_IDの順番は、インデックス ツリーの走査には必要ありません。リーフノードには子会社ID 27のエントリがあるけれど、ブランチノードにはないことからも、これは 明らかでしょう。DATE_OF_BIRTHに対するフィルタだけが、 スキャンするインデックスの範囲を制限する条件なのです。図2.2にある5つのリーフノードにまたがる、日付が最初に一致するエントリから、 最後に一致するエントリがスキャンの範囲になります。

協力してください

この記事が気に入ったら、私の書いた本「SQLパフォーマンス詳解」や私によるトレーニングもきっと気にいるはず。

インデックスの列の順番を反対にした時は、全く違った図になります。図2.3は、 インデックスがSUBSIDIARY_ID列から始まっている時のスキャンを表したものです。

図2.3SUBSIDIARY_IDDATE_OF_BIRTHの インデックスに対する範囲検索

等号によって、インデックスの最初の列が1つの値に定まっているのが違いです。SUBSIDIARY_ID 27の範囲内では、2番目の列、つまり誕生日でインデックスが並んでいますので、ブランチノードを見れば子会社ID 27で、かつ誕生日が1969年6月25日以降の従業員が最初のリーフノードにいないことが分かります。

ツリーの走査は、直接2番目のリーフノードから始まります。この場合、where句の全ての条件によって、スキャンされるインデックスの範囲が決まりますので、スキャンは同じリーフノードで終わりになります。

ヒント

大ざっぱに言うと、インデックスはまず等価性を確認するためにあり、それから範囲を調べるために使われます。

実際のパフォーマンスの違いは、データとそれに対する検索の基準によって現れます。DATE_OF_BIRTHに対するフィルタの選択性が高い場合は、パフォーマンスの違いは無視できるものになる可能性もあります。日付の範囲が広がれば広がるほど、パフォーマンスの違いは大きくなるということです。

この例では、最も選択性の高い列をインデックスの一番左に 置けばよいという都市伝説を反証してみせることができます。図を見て、最初の列の選択性を考えた時、どちらの条件でも13レコードに一致することが わかります。今回は、DATE_OF_BIRTHのみあるいは SUBSIDIARY_IDのみのどちらでフィルタしても変わらないの です。選択性はここでは何の意味もなく、列の並び順を変えればよいだけなのです。

パフォーマンス最適化を考える時は、スキャンされるインデックスの範囲を知ることがとても重要です。多くのデータベースでは、実行計画で これを知ることができます。どこを見ればよいかを知っておかなくては なりません。以下に示すOracleの実行計画は、EMP_TEST インデックスがDATE_OF_BIRTH列から始まっていることを明確に表しています。

DB2
Explain Plan
----------------------------------------------------
ID | Operation         |                 Rows | Cost
 1 | RETURN            |                      |   26
 2 |  FETCH EMPLOYEES  |     3 of 3 (100.00%) |   26
 3 |   IXSCAN EMP_TEST | 3 of 10000 (   .03%) |    6

Predicate Information
 3 - START ( TO_DATE(?, 'YYYY-MM-DD') <= Q1.DATE_OF_BIRTH)
     START (Q1.SUBSIDIARY_ID = ?)
      STOP (Q1.DATE_OF_BIRTH <= TO_DATE(?, 'YYYY-MM-DD'))
      STOP (Q1.SUBSIDIARY_ID = ?)
      SARG (Q1.SUBSIDIARY_ID = ?)

DB2では、アクセス述語にはSTART あるいはSTOPのラベルが付けられます。一方、フィルタ述語には SARGの表示が付きます。

Oracle
--------------------------------------------------------------
|Id | Operation                    | Name      | Rows | Cost |
--------------------------------------------------------------
| 0 | SELECT STATEMENT             |           |    1 |    4 |
|*1 |  FILTER                      |           |      |      |
| 2 |   TABLE ACCESS BY INDEX ROWID| EMPLOYEES |    1 |    4 |
|*3 |    INDEX RANGE SCAN          | EMP_TEST  |    2 |    2 |
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter(:END_DT >= :START_DT)
3 - access(DATE_OF_BIRTH >= :START_DT 
       AND DATE_OF_BIRTH <= :END_DT)
    filter(SUBSIDIARY_ID  = :SUBS_ID)
PostgreSQL
                            QUERY PLAN
-------------------------------------------------------------------
Index Scan using emp_test on employees
  (cost=0.01..8.59 rows=1 width=16)
  Index Cond: (date_of_birth >= to_date('1971-01-01','YYYY-MM-DD'))
          AND (date_of_birth <= to_date('1971-01-10','YYYY-MM-DD'))
          AND (subsidiary_id = 27::numeric)

PostgreSQLでは、インデックスアクセスとフィルタの述語 情報を実行計画では表示しません。Index Cond セクションで、インデックスの定義にしたがった列の順序を 表示します。この場合、最初に2つのDATE_OF_BIRTHの 述語情報を表示し、その後SUBSIDIARY_IDの 表示があります。範囲指定の条件の後に、単一の行を対象と する条件が来ることはできないので、SUBSIDIARY_IDは フィルタ述語になります。詳しくは、アクセス述語とフィルタ述語の見分け方を参照してください。

SQL Server
|--Nested Loops(Inner Join)
   |--Index Seek(OBJECT:emp_test,
   |               SEEK:       (date_of_birth, subsidiary_id)
   |                        >= ('1971-01-01', 27)
   |                    AND    (date_of_birth, subsidiary_id)
   |                        <= ('1971-01-10', 27),
   |              WHERE:subsidiary_id=27
   |            ORDERED FORWARD)
   |--RID Lookup(OBJECT:employees,
                   SEEK:Bmk1000=Bmk1000
                 LOOKUP ORDERED FORWARD)

SQL Server 2012は、検索の述語情報(= アクセス述語を行値文法で表示します。

INDEX RANGE SCANに対する述語情報は、 重要なヒントになります。where句の条件に関して、 アクセスのパターンとフィルタの 両方の述語情報を表示しています。これにより、データベースがどのように条件を使うのかを教えてくれます。

注記

実行計画は、明確化のために単純化されています。アクセス述語とフィルタ述語の見分け方では、Oracleの実行計画の「Predicate Information」セクションを詳細に解説しています。

DATE_OF_BIRTH列に対する条件が、唯一アクセスパターンの 述語情報に書かれており、これがスキャンするインデックスの範囲を 決めています。DATE_OF_BIRTHは、EMP_TEST インデックスの最初の列です。SUBSIDIARY_ID列は、フィルタとしてだけ使われます。

重要

アクセス述語は、インデックス操作の始めと終わりを決める条件です。 つまり、インデックスをスキャンする範囲を定義します。

フィルタ述語は、リーフノードの走査時にのみ 適用されます。インデックスをスキャンする範囲を狭めるためには使われません。

付録では、MySQLSQL ServerPostgreSQLのそれぞれに おいて、アクセス述語情報を知る方法について解説しています。

インデックスの定義を逆にすると、全ての条件をアクセス述語として使うようになります。

DB2
-----------------------------------------------------
ID | Operation          |                 Rows | Cost
 1 | RETURN             |                      |   13
 2 |  FETCH EMPLOYEES   |     3 of 3 (100.00%) |   13
 3 |   IXSCAN EMP_TEST2 | 3 of 10000 (   .03%) |    6

Predicate Information
 3 - START (Q1.SUBSIDIARY_ID = ?)
     START ( TO_DATE(?, 'YYYY-MM-DD') <= Q1.DATE_OF_BIRTH)
      STOP (Q1.SUBSIDIARY_ID = ?)
      STOP (Q1.DATE_OF_BIRTH <= TO_DATE(?, 'YYYY-MM-DD'))
Oracle
---------------------------------------------------------------
| Id | Operation                    | Name      | Rows | Cost |
---------------------------------------------------------------
|  0 | SELECT STATEMENT             |           |    1 |    3 |
|* 1 |  FILTER                      |           |      |      |
|  2 |   TABLE ACCESS BY INDEX ROWID| EMPLOYEES |    1 |    3 |
|* 3 |    INDEX RANGE SCAN          | EMP_TEST2 |    1 |    2 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter(:END_DT >= :START_DT)
3 - access(SUBSIDIARY_ID  = :SUBS_ID
       AND DATE_OF_BIRTH >= :START_DT
       AND DATE_OF_BIRTH <= :END_T)
PostgreSQL
                            QUERY PLAN
-------------------------------------------------------------------
Index Scan using emp_test on employees
   (cost=0.01..8.29 rows=1 width=17)
   Index Cond: (subsidiary_id = 27::numeric)
           AND (date_of_birth >= to_date('1971-01-01', 'YYYY-MM-DD'))
           AND (date_of_birth <= to_date('1971-01-10', 'YYYY-MM-DD'))

PostgreSQLでは、インデックスアクセスとフィルタの述語情報を実行計画では表示しません。Index Cond セクションで、インデックスの定義にしたがった列の順序を 表示します。この場合、SUBSIDIARY_IDの述語情報が 先に表示され、その後DATE_OF_BIRTHの表示があります。 DATE_OF_BIRTHの範囲条件の後に別の列のフィルタが ないので、全ての条件がアクセス述語になります。詳しくは、アクセス述語とフィルタ述語の見分け方を参照してください。

SQL Server
|--Nested Loops(Inner Join)
   |--Index Seek(OBJECT:emp_test,
   |               SEEK: subsidiary_id=27
   |                 AND date_of_birth >= '1971-01-01'
   |                 AND date_of_birth <= '1971-01-10'
   |            ORDERED FORWARD)
   |--RID Lookup(OBJECT:employees),
                   SEEK:Bmk1000=Bmk1000
                 LOOKUP ORDERED FORWARD)

最後に、between演算子を取り上げましょう。 これにより、1つの条件式で上限と下限を指定することができます。

DATE_OF_BIRTH BETWEEN '01-JAN-71'
                  AND '10-JAN-71'

betweenでは、必ず指定された値が含まれることに 注意しましょう。, つまり、以下(<=)あるいは以上(>=)の演算子を使うのと 同じになります。

    DATE_OF_BIRTH >= '01-JAN-71' 
AND DATE_OF_BIRTH <= '10-JAN-71'

著者について

Markus Winandの写真

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

彼の本

カバー『SQLパフォーマンス詳解』

核心をわかりやすく 解説。

Markusから購入します
(送料無料+PDF)

Amazonで購入
(印刷版のみ)

Do not use offset for pagination

Learn why

Visit my sibling!A lot changed since SQL-92!

Use The Index, Luke のカップは

ステッカー、コースター、本、コーヒーマグ。 学習に必要なものすべて。

今すぐ購入

Connect with Markus Winand

Markus Winand on LinkedInMarkus Winand on XINGMarkus Winand on Twitter
“Use The Index, Luke!” by Markus Winand is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
法律上の通知 | お問い合わせ | 無保証 | 商標 | プライバシーとGDPR | CC-BY-NC-ND 3.0 license