大なり、小なり、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.2 DATE_OF_BIRTHSUBSIDIARY_IDの インデックスに対する範囲検索


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

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

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

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


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

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

Tweet this tip

ヒント

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

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

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

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

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は フィルタ述語になります。詳しくは、2.3を参照してください。

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のそれぞれに おいて、アクセス述語情報を知る方法について解説しています。

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

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の範囲条件の後に別の列のフィルタが ないので、全ての条件がアクセス述語になります。詳しくは、2.3を参照してください。

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