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_BIRTH
とSUBSIDIARY_ID
の
順に並んだインデックスの詳細を図示しています。リーフノードチェーンをたどり始めるのはどこでしょうか?言い換えると、ツリーの走査はどこで終わるのでしょうか?
図2.2DATE_OF_BIRTH
とSUBSIDIARY_ID
の
インデックスに対する範囲検索
インデックスは、まず誕生日の順に並んでいます。同じ日に生まれた
従業員が2人いる時だけ、そのレコードを並び替えるのにSUBSIDIARY_ID
が使われます。一方で、クエリは日付の範囲を
指定していますので、SUBSIDIARY_ID
の順番は、インデックス
ツリーの走査には必要ありません。リーフノードには子会社ID 27のエントリがあるけれど、ブランチノードにはないことからも、これは
明らかでしょう。DATE_OF_BIRTH
に対するフィルタだけが、
スキャンするインデックスの範囲を制限する条件なのです。図2.2にある5つのリーフノードにまたがる、日付が最初に一致するエントリから、
最後に一致するエントリがスキャンの範囲になります。
協力してください
この記事が気に入ったら、私の書いた本「SQLパフォーマンス詳解」や私によるトレーニングもきっと気にいるはず。
インデックスの列の順番を反対にした時は、全く違った図になります。図2.3は、
インデックスがSUBSIDIARY_ID
列から始まっている時のスキャンを表したものです。
図2.3SUBSIDIARY_ID
とDATE_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 (LUW)
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
列は、フィルタとしてだけ使われます。
重要
アクセス述語は、インデックス操作の始めと終わりを決める条件です。 つまり、インデックスをスキャンする範囲を定義します。
フィルタ述語は、リーフノードの走査時にのみ 適用されます。インデックスをスキャンする範囲を狭めるためには使われません。
付録では、MySQL、SQL Server、PostgreSQLのそれぞれに おいて、アクセス述語情報を知る方法について解説しています。
インデックスの定義を逆にすると、全ての条件をアクセス述語として使うようになります。
- Db2 (LUW)
----------------------------------------------------- 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'