LIKE 演算子とインデックスの謎を探る

# はじめに
この記事は[PostgreSQL Advent Calendar 2024](https://qiita.com/advent-calendar/2024/postgresql) の14日目（+ [SRA Advent Calendar 2024](https://qiita.com/advent-calendar/2024/sra)の６日目）です。

先日の [PostgreSQL Conference Japan 2024](https://www.postgresql.jp/jpug-pgcon2024)で、『PostgreSQL でインデックスはどう使われるのか』という話[^slide]をしたのですが、その中で紹介した「インデックスが使われない状況」の１つに「LIKE 演算子でインデックスが使われない」というものがありました。今回はちょっとだけこれを深堀りしてみます。

[^slide]:カンファレンスの[公式サイト](https://www.postgresql.jp/jpug-pgcon2024)で[スライド資料](https://www.postgresql.jp/sites/default/files/2024-12/T3_JPUG_2024_index_final.pdf)も公開されています。

# LIKE 演算子のおさらい

まず前提として LIKE 演算子についてのおさらいです。

SQL の [LIKE 演算子](https://www.postgresql.jp/document/16/html/functions-matching.html#FUNCTIONS-LIKE)は文字列のパターンマッチングを行う演算子です。パターンの文字列には、任意の一文字との一致を意味するアンダースコア（`_`）と、0文字以上の並びとの一致を意味するパーセント記号（`%`）を含めることができます。例えば、"abc" で始まる文字列に一致する前方一致検索、"xyz" で終わる文字列に一致させる後方一致検索はそれぞれ以下のように書けます。

```sql
SELECT * FROM tbl WHERE t LIKE 'abc%';
SELECT * FROM tbl WHERE t LIKE '%xyz';
```

パターンに `_` と `%` のいずれも含まない場合は、指定された文字列と完全に等しい値を検索する完全一致検索となります。

```sql
SELECT * FROM tbl WHERE t LIKE 'abc';
```

# LIKE 演算子とインデックス

PostgreSQL では LIKE 演算子を使った文字列検索[^text]でも、前方一致または完全一致の場合には、インデックスを使用可能です。しかし、いくつか条件があり、以下ではそれを確認していきます。

[^text]:この記事では話を単純にするためtext型を前提にしています。

### LIKE 演算子の実行計画

まず、`text`型カラムを含むテーブルを適当に作成して、ランダムな文字列で初期化しておきます。

```sql
test=# CREATE TABLE tbl1(t text);
test=# INSERT INTO tbl1 SELECT md5(random()::text) FROM generate_series(1,10000);
test=# ANALYZE tbl1;
```
手始めに、インデックスが存在しない状態での`LIKE`演算子使用時の実行計画を`EXPLAIN`で確認してみましょう。

```sql
test=# EXPLAIN (COSTS off) SELECT * FROM tbl1 WHERE t LIKE 'abc%';
          QUERY PLAN           
-------------------------------
 Seq Scan on tbl1
   Filter: (t ~~ 'abc%'::text)
(2 rows)
```

インデックスを作成していないので実行プランが`Seq Scan`となるのは想定済として、実行計画の条件式に現れる演算子が`LIKE`ではなく`~~`となっています。これは何でしょう？

実は、PostgreSQL は構文解析の段階で、`LIKE`演算子をそれと等価な`~~`演算子に変換しています。これは[公式ドキュメント](https://www.postgresql.jp/document/16/html/functions-matching.html#FUNCTIONS-LIKE)でも解説されている通りです。

> \~~演算子はLIKE式と等価で、\~~*はILIKEに対応します。 またNOT LIKEおよびNOT ILIKEを表す!\~~および!\~~*演算子があります。 これら全ての演算子はPostgreSQL固有のものです。 パーサは実際にはLIKEなどをこれらの演算子に変換するため、こうした演算子名はEXPLAINの出力などで見ることができます。

`LIKE`演算子が`~~`演算子に変換されるのは、完全一致検索の場合でも同じです。

```sql
test=# EXPLAIN (COSTS off) SELECT * FROM tbl1 WHERE t LIKE 'abc';
          QUERY PLAN          
------------------------------
 Seq Scan on tbl1
   Filter: (t ~~ 'abc'::text)
(2 rows)
```

### インデックスを作成してみる

つぎに、このテーブルにインデックスを作成した状態で、LIKE演算子の前方一致検索でインデックスが使われるかどうかを確認してみましょう。

```sql
test=# CREATE INDEX ON tbl1(t);
test=# EXPLAIN (COSTS off) SELECT * FROM tbl1 WHERE t LIKE 'abc%';
          QUERY PLAN           
-------------------------------
 Seq Scan on tbl1
   Filter: (t ~~ 'abc%'::text)
(2 rows)
```

すると、インデックス作成前と同じように実行プランが`Seq Scan`となり、インデックスが使われませんでした。

では、完全一致検索の場合はどうなるでしょう。

```sql
test=# EXPLAIN (COSTS off) SELECT * FROM tbl1 WHERE t LIKE 'abc';
                QUERY PLAN                
------------------------------------------
 Index Only Scan using tbl1_t_idx on tbl1
   Index Cond: (t = 'abc'::text)
   Filter: (t ~~ 'abc'::text)
(3 rows)
```

今度はインデックスが使われました。しかし、何故かインデックスの検索条件は `t = 'abc'::text` となり、`~~`演算子ではなく`=`演算子（等号演算子）が使用されています。

この時点での「謎」は以下の２つです。

1. なぜ前方一致検索でインデックスが使われなかったのか
2. なぜ完全一致検索ではインデックスの条件式で `=` 演算子を使われるようになったのか

### 照合順序の影響

先程の謎の解明はひとまず置いておいて、先にインデックスを使用するための解決方法を１つ紹介します。

実は、先程のテーブルを作成したデータベースのデフォルトの照合順序(collate)は`ja_JP.UTF-8`でした。

```sql
test=# \l test
                                                List of databases
 Name | Owner  | Encoding | Locale Provider |   Collate   |    Ctype    | Locale | ICU Rules | Access privileges 
------+--------+----------+-----------------+-------------+-------------+--------+-----------+-------------------
 test | yugo-n | UTF8     | libc            | ja_JP.UTF-8 | ja_JP.UTF-8 |        |           | 
(1 row)
```

そこで、カラムの照合順序を`C`にしたテーブルを作成して、同じくインデックスが使用できるか調べてみましょう。

```sql
test=# CREATE TABLE tbl2(t text COLLATE "C");
test=# INSERT INTO tbl2 SELECT md5(random()::text) FROM generate_series(1,10000);
test=# CREATE INDEX ON tbl2(t);
test=# ANALYZE tbl2;

test=# EXPLAIN (COSTS off) SELECT * FROM tbl2 WHERE t LIKE 'abc%';
                        QUERY PLAN                        
----------------------------------------------------------
 Index Only Scan using tbl2_t_idx on tbl2
   Index Cond: ((t >= 'abc'::text) AND (t < 'abd'::text))
   Filter: (t ~~ 'abc%'::text)
(3 rows)
```

今度は前方一致検索でもインデックスが使用されました。しかし、今回はインデックスの検索条件が `(t >= 'abc'::text) AND (t < 'abd'::text)` と、`>=`演算子と`<`演算子が使用されるようになりました。これは一体何を表しているのでしょうか？新しい謎がでてきました。

### 前方一致検索のための範囲検索

インデックス検索の条件式は「`'abc'`以上で、かつ、`'abd'`より小さい文字列」の範囲検索です。よく見ると、これは「'abc'から始まる文字列」を含む範囲を表しているであろうことがわかってきます。

単純にアルファベット順で考えると、`'abc'` から始まる文字列は、`'abc'` 以降に現れる（つまり、`'abc'` 以上である）ことは明らかです。そして、`'abd'` は `'abc'` より後に現れる（すなわち、大きい）文字列であり、それ以降には`'abc'`から始まる文字列は現れないでしょう。そのため、「`'abc'`から始まる文字列」は確かに検索範囲「`'abc'` 以上で `'abd'` より小さい」の中に含まれているように思えます。これが「範囲検索が何を表しているか」の謎の説明です。

しかし、実はこのような範囲検索の考え方は、照合順序が`C`で比較した場合にしか保証されません。例えば、 「`'abc '` から始まる文字列」の検索を考えてみましょう。（`'abc'` の後ろに空白文字`' '`が１つ入っていることにご注意ください。）

```sql
test=# EXPLAIN (COSTS off) SELECT * FROM tbl2 WHERE t LIKE 'abc %';
                         QUERY PLAN                         
------------------------------------------------------------
 Index Only Scan using tbl2_t_idx on tbl2
   Index Cond: ((t >= 'abc '::text) AND (t < 'abc!'::text))
   Filter: (t ~~ 'abc %'::text)
(3 rows)
```

インデックス検索の条件式は「`'abc '`以上で、かつ、`'abc!'`より小さい文字列」となっています。空白文字 `' '` と `'!'` の ASCII 値はそれぞれ 0x20、0x21 なので、`'abc ' < 'abc!'` という関係が成り立つのは問題なさそうです。

次に`'abc def'`という文字列を考えてみましょう。これは `'abc '` から始まっているので、上の範囲検索の考え方が正しければ、「`'abc '` 以上で `'abc!'` より小さい」という範囲内に含まれているはずです。実際に確かめてみましょう。

```sql
test=# SELECT 'abc def' >= 'abc ' COLLATE "C";
 ?column? 
----------
 t
(1 row)

test=# SELECT 'abc def' < 'abc!' COLLATE "C";
 ?column? 
----------
 t
(1 row)
```

照合順序 `C` の場合には当然成り立っています。しかし、照合順序が英語（`en_US`）の場合はどうでしょう。

```sql
test=# SELECT 'abc def' >= 'abc ' COLLATE "en_US";
 ?column? 
----------
 t
(1 row)

test=# SELECT 'abc def' < 'abc!' COLLATE "en_US";
 ?column? 
----------
 f
(1 row)
```

以上のように、２番目の条件が成り立ちません[^locale]。そのため、この照合順序の下では`'abc '`で始まる文字列`'abc def'`は範囲検索の条件式 `(t >= 'abc '::text) AND (t < 'abc!'::text)`を満たしていません。

このように、使用される照合順序によっては、上で述べた範囲検索への変換の正しさが保証されないのです。これが、インデックスの照合順序が`C`以外の場合には、前方一致検索でインデックスが使用されない理由です。

[^locale]:これはアルファベット圏において「複数単語からなる熟語」の辞書的順序は、単語間の空白文字等を無視して比較されるためのようです。具体的な熟語の例でいうと、`'ad-hoc'`と`'add on'` の文字列の大小比較が照合順序 `C`および`ja_JP` の場合と、`en_US`,`de_DE`,`fr_FR`などの場合で異なってきます。（参考:https://exlight.net/devel/locale/collation.html）

一方で、完全一致検索の場合は範囲検索が必要ないので、照合順序に関わらず等号演算子 `=` でインデックス検索が使用できるわけです。

以上が、先立って挙げた２つの謎に対する「なぜそうするのか」という方面からの答えとなります。

### 照合順序 `C` 以外でも前方一致検索でインデックスを使う

では、照合順序 `C` 以外を使っている場合は `LIKE` の前方一致検索でインデックスが使えないのかというと、そういうわけではありません。

以下のように、`text_pattern_ops` [演算子クラス](https://www.postgresql.jp/document/16/html/indexes-opclass.html)を指定してインデックスを作成すると、照合順序の影響を受けずに前方一致検索でインデックスが使用可能になります。

```sql
test=# CREATE INDEX ON tbl3(t text_pattern_ops);

test=# EXPLAIN (COSTS off) SELECT * FROM tbl3 WHERE t LIKE 'abc%';
                          QUERY PLAN                          
--------------------------------------------------------------
 Index Only Scan using tbl3_t_idx on tbl3
   Index Cond: ((t ~>=~ 'abc'::text) AND (t ~<~ 'abd'::text))
   Filter: (t ~~ 'abc%'::text)
(3 rows)
```

このときの実行計画に現れるインデックスの検索条件は、照合順序が `C` の場合と似ているのですが、ちょっと違っていて、演算子 `>=`、`<` の代わりに、それぞれ `~>=~`, `~<~` が使われています。実はこの比較演算子は、「照合順序に関わらず文字列をバイナリ比較」する演算子なので、照合順序 `C` のときと同じように範囲検索ができるのです。

これとは別に、デフォルトの B-Treeではなく SP-Gist アクセスメソッドを使ってインデックスを作る方法もあります。

```sql
test=# CREATE INDEX ON tbl4 USING spgist (t);

test=# EXPLAIN (COSTS off) SELECT * FROM tbl4 WHERE t LIKE 'abc%';
                QUERY PLAN                
------------------------------------------
 Index Only Scan using tbl4_t_idx on tbl4
   Index Cond: (t ^@ 'abc'::text)
   Filter: (t ~~ 'abc%'::text)
(3 rows)
```

ここでインデックスの検索条件で使用されている演算子は `^@` です。これは「最初の文字列が2番目の文字列で始まる場合に真を返す」演算子（`starts_with` 関数と等価なもの）で、[公式ドキュメント](https://www.postgresql.jp/document/16/html/functions-string.html)にも明記されています。SP-Gist アクセスメソッドではこの演算子でインデックスが使用可能になるのですね。

# インデックス可能な演算子への変換

ここまで `LIKE` 演算子の前方一致検索でインデックスを使用する方法をいくつか説明してきました。いずれの場合も共通しているのは、`LIKE` 演算子、あるいはそれと等価な `~~` 演算子「そのもの」ではインデックスが使えず、インデックスを使うためには等価演算子（`=`）や、比較演算子（`>=`, `<`, `~>=~`, `~<~`）、あるいは`starts_with` と等価な演算子（`^@`）を使った別の条件式に変換される必要があったということです。また、その変換のしかたは、`LIKE` に指定された文字列パターンや、インデックスの照合順序、使用する演算子クラスやアクセスメソッドで決まっていました。

しかし、この変換はどこで行われているのでしょうか？それが、今回最後の謎です。

それを探るために、`~~` 演算子の詳細を `psql` の `\do+` メタコマンドで調べてみましょう。

```sql
test=# \do+ ~~ text text
                                           List of operators
   Schema   | Name | Left arg type | Right arg type | Result type | Function |       Description       
------------+------+---------------+----------------+-------------+----------+-------------------------
 pg_catalog | ~~   | text          | text           | boolean     | textlike | matches LIKE expression
(1 row)
```

出力の `Function` 欄から、この演算子を実装する関数の名前が `textlike` であるとわかります。次に、この関数の情報を `pg_proc` システムカタログで調べてみます。

```sql
test=# select * from pg_proc where proname = 'textlike';
-[ RECORD 1 ]---+-----------------
oid             | 850
proname         | textlike
pronamespace    | 11
proowner        | 10
prolang         | 12
procost         | 1
prorows         | 0
provariadic     | 0
prosupport      | textlike_support
prokind         | f
prosecdef       | f
proleakproof    | f
proisstrict     | t
proretset       | f
provolatile     | i
proparallel     | s
pronargs        | 2
pronargdefaults | 0
prorettype      | 16
proargtypes     | 25 25
proallargtypes  | 
proargmodes     | 
proargnames     | 
proargdefaults  | 
protrftypes     | 
prosrc          | textlike
probin          | 
prosqlbody      | 
proconfig       | 
proacl          | 
```
すると、`prosupport` に別の関数 `textlike_support` が指定されているのが見つかります。これは「プランナサポート関数」と呼ばれるもので、特定の関数がクエリで使われた場合の実行計画の作成に様々な形で関与しています。その詳細は[公式ドキュメント](https://www.postgresql.jp/document/16/html/xfunc-optimization.html)で説明されていますが、今回の `LIKE` 演算子の振る舞いに関わる記述は以下の部分です。

> booleanを返す対象関数に対しては、WHERE句に現れる関数呼び出しをインデックス可能な演算子句に変換できる場合があります。（中略） そのような条件を作るには、サポート関数はSupportRequestIndexConditionリクエスト型を実装しなければなりません。

PostgreSQL のプランナは、条件式の中の演算子そのままではインデックスが使えない場合には、サポート関数を呼び出してインデックス可能な演算子句への変換を試みます。つまり、`~~` 演算子そのものに対してはインデックスが使えないので、サポート関数 `textlike_support` を呼び出し、その中でインデックス使用可能な形の条件式に変換されていたのです。そのときに、与えられた文字列パターンや、インデックスの照合順序、使用する演算子クラスなどをチェックして、それぞれの場合で適切な条件式を生成していたのですね[^code]。

[^code]:詳細を知りたい方は`textlike_support`のコードを[こちら](https://github.com/postgres/postgres/blob/master/src/backend/utils/adt/like_support.c)からご参照ください。

これで最後の謎がとけました。

# おわりに

`LIKE`演算子でインデックスを使う方法については、他にも説明している記事がいくつかありますが、今回は少し深堀して、内部の動作の理由やしくみにも言及して解説してみました。 [PostgreSQL Conference Japan 2024](https://www.postgresql.jp/jpug-pgcon2024)で話せなかった小ネタを文章にしてまとめておきたい、というのがこの記事を書いた最初の動機でしたが、これにより皆様の PostgreSQL life に少しでも貢献できれば幸いです。

### 追記

続編です。

[プランナサポート関数を作って自作演算子でインデックスが使えるようにする（続・LIKE 演算子とインデックスの謎を探る）](https://qiita.com/yugo-n/items/83f9ac77af13ea846b52)