PostgreSQLでは（Oracleでの）インデックススキップスキャンは使えない

# INDEX SKIP SCAN（インデックススキップスキャン）とは

Oracleでは、複合インデックスで第1キーが条件指定がなくても、第2キーが条件指定があった場合にインデックスが使われることがあります。これをINDEX SKIP SCAN（インデックススキップスキャン）と呼びます。

例えば、(id, insert_time)の2つのキーからなる複合インデックスで、where句にinsert_timeだけを指定した場合にインデックスが使用されるということです。
ただし、第1キーのカーディナリティが低い場合であり、カーディナリティが高い場合はテーブルフルスキャンが選択されやすくなります。

Oracle12cで実際に第2キーのみを条件指定して、インデックスが使用されるかを確認してみます。

まずは、テーブル等の準備をします。

```sql
create table test_tbl
 (
 id number NOT NULL,
 insert_time timestamp,
 msg1 varchar2(128)
 );

insert into test_tbl select mod(rownum, 5), to_date('2020-02-11 00:00:00', 'yyyy-mm-dd hh24:mi:ss') + 1/24, 'TEST DATA' || rownum from dual connect by level <= 100000;
commit;

create index idx_test_tbl01 on test_tbl(id, insert_time);

exec DBMS_STATS.GATHER_TABLE_STATS(ownname => 'hr', tabname => 'test_tbl', cascade => FALSE);

```

実際にSELECT文を発行して、実行計画を確認すると、以下のようにINDEX SKIP SCANが選択されています。

```sql
set lines 200
set autotrace on
select * from test_tbl where insert_time between to_date('2020-02-11 08:00:00', 'yyyy-mm-dd hh24:mi:ss') and to_date('2020-02-11 09:00:00', 'yyyy-mm-dd hh24:mi:ss');

～省略～
------------------------------------------------------------------------------------------------------
| Id  | Operation                           | Name           | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |                |     1 |    29 |    38   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| TEST_TBL       |     1 |    29 |    38   (0)| 00:00:01 |
|*  2 |   INDEX SKIP SCAN                   | IDX_TEST_TBL01 |     1 |       |    37   (0)| 00:00:01 |
------------------------------------------------------------------------------------------------------

～省略～
```


# PostgreSQLでインデックススキップスキャンは使用できるのか？

結論から書くと、PostgreSQLでインデックススキップスキャンは使用できません（存在しないから当たり前ですが）。

PostgreSQLのCommitFestを見ると、レビュー対象になっているので今後対応するかもしれません。

https://commitfest.postgresql.org/19/1741/

先ほどのOracleと同じテーブルを使用して、インデックススキップスキャンが使用されないことを確認してみます。
PostgreSQL11を用いて試しています。

```sql
create table test_tbl
 (
 id numeric NOT NULL,
 insert_time timestamp,
 msg1 varchar(128)
 );

insert into test_tbl select mod(i, 5), to_date('2020-02-11 00:00:00', 'yyyy-mm-dd hh24:mi:ss') + cast(i || 'hour' AS INTERVAL), 'TEST DATA' || i from generate_series(1,100000) as i;
create index idx_test_tbl01 on test_tbl(id, insert_time);
```

実行計画は以下のようになりました。
「Seq Scan」となっており、テーブルフルスキャンが発生していることが分かります。

```sql
postgres=# explain (analyze, buffers) select * from test_tbl where insert_time between to_date('2020-02-11 08:00:00', 'yyyy-mm-dd hh24:mi:ss') and to_date('2020-02-11 09:00:00', 'yyyy-mm-dd hh24:mi:ss');
                                                                                        QUERY PLAN                                                                                         
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Seq Scan on test_tbl  (cost=0.00..2958.72 rows=1 width=26) (actual time=214.055..214.055 rows=0 loops=1)
   Filter: ((insert_time >= to_date('2020-02-11 08:00:00'::text, 'yyyy-mm-dd hh24:mi:ss'::text)) AND (insert_time <= to_date('2020-02-11 09:00:00'::text, 'yyyy-mm-dd hh24:mi:ss'::text)))
   Rows Removed by Filter: 100000
   Buffers: shared hit=736
 Planning Time: 0.069 ms
 Execution Time: 214.067 ms
(6 rows)
```


# インデックススキップスキャンは使用できないとどうなる？

先ほどの例ではSeq Scanが使用されており、全データを読み込むことになり遅い処理になってしまいます。
Oracleでインデックススキップスキャンが使われているSQLをPostgreSQLに移行する場合は、注意が必要ですね。

今回の場合ですと
- 複合インデックスのキーの順番を入れ替える
- 第2キーにインデックスを作成する
- pg_hint_planでヒント句をつける
などの対策が考えられます。


# おまけ（pg_hint_planを用いてIndex ScanとBitmap Index Scanを実行）

pg_hint_planを用いてIndex ScanとBitmap Index Scanを実行した場合の実行計画は以下のようになりました。

コストはSeq Scanの"cost=0.00..2736.00"と比較して、"cost=3656.42..3660.44"と高くなっています。
しかし、Execution TimeはSeq Scanの208.919 msと比較して、それぞれ10.746 ms、7.447 msと早くなっています。
この結果を見ると、ケースによってはヒント句を用いるのも検討の余地がありそうです。

※Bitmap Index Scanは、全てのインデックスを読み込んで一旦ビットマップにしてスキャンする方法です。テーブルフルスキャンよりは軽そうですが、それなりに重い処理のように思えます。


```sql
postgres=# /*+ BitmapScan(test_tbl) */
postgres-# explain (analyze, buffers) select * from test_tbl where insert_time between to_date('2020-02-11 08:00:00', 'yyyy-mm-dd hh24:mi:ss') and to_date('2020-02-11 09:00:00', 'yyyy-mm-dd hh24:mi:ss');
                                                                                             QUERY PLAN                                                                                              
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on test_tbl  (cost=3656.42..3660.44 rows=1 width=26) (actual time=10.727..10.727 rows=0 loops=1)
   Recheck Cond: ((insert_time >= to_date('2020-02-11 08:00:00'::text, 'yyyy-mm-dd hh24:mi:ss'::text)) AND (insert_time <= to_date('2020-02-11 09:00:00'::text, 'yyyy-mm-dd hh24:mi:ss'::text)))
   Buffers: shared hit=661
   ->  Bitmap Index Scan on idx_test_tbl01  (cost=0.00..3656.42 rows=1 width=0) (actual time=10.723..10.724 rows=0 loops=1)
         Index Cond: ((insert_time >= to_date('2020-02-11 08:00:00'::text, 'yyyy-mm-dd hh24:mi:ss'::text)) AND (insert_time <= to_date('2020-02-11 09:00:00'::text, 'yyyy-mm-dd hh24:mi:ss'::text)))
         Buffers: shared hit=661
 Planning Time: 0.194 ms
 Execution Time: 10.746 ms
(8 rows)

postgres=# 
postgres=# /*+ IndexScan(test_tbl idx_test_tbl01) */
postgres-# explain (analyze, buffers) select * from test_tbl where insert_time between to_date('2020-02-11 08:00:00', 'yyyy-mm-dd hh24:mi:ss') and to_date('2020-02-11 09:00:00', 'yyyy-mm-dd hh24:mi:ss');
                                                                                          QUERY PLAN                                                                                           
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using idx_test_tbl01 on test_tbl  (cost=0.42..3660.43 rows=1 width=26) (actual time=7.429..7.430 rows=0 loops=1)
   Index Cond: ((insert_time >= to_date('2020-02-11 08:00:00'::text, 'yyyy-mm-dd hh24:mi:ss'::text)) AND (insert_time <= to_date('2020-02-11 09:00:00'::text, 'yyyy-mm-dd hh24:mi:ss'::text)))
   Buffers: shared hit=661
 Planning Time: 0.368 ms
 Execution Time: 7.447 ms
(5 rows)

```


# 2020/06/10補足

PostgreSQLではインデックススキップスキャンはありませんが、"Index Scan Backward"というのがありました。
ケースによっては"Index Scan Backward"が選択されることがあるかと思います。"Index Scan Backward"はインデックススキップスキャンとは仕組みが違いますが、テーブルフルスキャンより早く処理されることが期待できます。


# 参考

- [PostgreSQL で ヒント句を使う](https://ja.osdn.net/projects/pghintplan/)
- [pg_hint_plan (PostgreSQL 実行計画制御ツール)](https://www.sraoss.co.jp/tech-blog/pgsql/pg_hint_plan/)
- [ヒント句一覧](http://pghintplan.osdn.jp/hint_list-ja.html)