Go to Qiita Advent Calendar 2024 Top
LoginSignup
4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

PostgreSQLAdvent Calendar 2024

Day 14
@yugo-n(Yugo Nagata)

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

Last updated at Posted at 2024-12-14

はじめに

この記事はPostgreSQL Advent Calendar 2024 の14日目（+ SRA Advent Calendar 2024の６日目）です。

先日の PostgreSQL Conference Japan 2024で、『PostgreSQL でインデックスはどう使われるのか』という話1をしたのですが、その中で紹介した「インデックスが使われない状況」の１つに「LIKE 演算子でインデックスが使われない」というものがありました。今回はちょっとだけこれを深堀りしてみます。

LIKE 演算子のおさらい

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

SQL の LIKE 演算子は文字列のパターンマッチングを行う演算子です。パターンの文字列には、任意の一文字との一致を意味するアンダースコア（_）と、0文字以上の並びとの一致を意味するパーセント記号（%）を含めることができます。例えば、"abc" で始まる文字列に一致する前方一致検索、"xyz" で終わる文字列に一致させる後方一致検索はそれぞれ以下のように書けます。

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

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

SELECT * FROM tbl WHERE t LIKE 'abc';

LIKE 演算子とインデックス

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

LIKE 演算子の実行計画

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

test=# CREATE TABLE tbl1(t text);
test=# INSERT INTO tbl1 SELECT md5(random()::text) FROM generate_series(1,10000);
test=# ANALYZE tbl1;

手始めに、インデックスが存在しない状態でのLIKE演算子使用時の実行計画をEXPLAINで確認してみましょう。

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演算子をそれと等価な~~演算子に変換しています。これは公式ドキュメントでも解説されている通りです。

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

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

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

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

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

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となり、インデックスが使われませんでした。

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

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でした。

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にしたテーブルを作成して、同じくインデックスが使用できるか調べてみましょう。

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' の後ろに空白文字' 'が１つ入っていることにご注意ください。）

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!' より小さい」という範囲内に含まれているはずです。実際に確かめてみましょう。

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）の場合はどうでしょう。

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

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

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

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

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

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

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

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

以下のように、text_pattern_ops 演算子クラスを指定してインデックスを作成すると、照合順序の影響を受けずに前方一致検索でインデックスが使用可能になります。

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 アクセスメソッドを使ってインデックスを作る方法もあります。

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 関数と等価なもの）で、公式ドキュメントにも明記されています。SP-Gist アクセスメソッドではこの演算子でインデックスが使用可能になるのですね。

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

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

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

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

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 システムカタログで調べてみます。

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 が指定されているのが見つかります。これは「プランナサポート関数」と呼ばれるもので、特定の関数がクエリで使われた場合の実行計画の作成に様々な形で関与しています。その詳細は公式ドキュメントで説明されていますが、今回の LIKE 演算子の振る舞いに関わる記述は以下の部分です。

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

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

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

おわりに

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

追記

続編です。

プランナサポート関数を作って自作演算子でインデックスが使えるようにする（続・LIKE 演算子とインデックスの謎を探る）

  1. カンファレンスの公式サイトでスライド資料も公開されています。 ↩

  2. この記事では話を単純にするためtext型を前提にしています。 ↩

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

  4. 詳細を知りたい方はtextlike_supportのコードをこちらからご参照ください。 ↩

4
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?