NAV_MENU
賽は投げられた。人事尽くして天命待つと言うか、転がりだした物は止められないというか。まぁ、ちょとは覚悟しとけよ。
基本的に毎日更新。出来なかったときは遡ってやります。多分。きっと。出来たら良いな

現在、移転作業中に付き、縮退運転中!。過去ログへのリンクはデータ移行後に何とかします

PostgreSQLで後方一致LIKE検索でインデックスを使わせる

とりあえずテストデータ作成

test=# CREATE TABLE test (id TEXT,value TEXT);
CREATE TABLE
test=# INSERT INTO test (id,value) SELECT uuid_generate_v1mc() ,GENERATE_SERIES(0,1000000);
INSERT 0 1000001
test=# INSERT INTO test (id,value) SELECT uuid_generate_v1mc() ,GENERATE_SERIES(0,1000000);
INSERT 0 1000001


とりあえず、前方一致のLIKE句付き、後方一致のLIKE句付きのクエリを流してみる


test=# EXPLAIN ANALYZE SELECT id FROM test WHERE id LIKE '5e1f%';
QUERY PLAN

---------------------------------------------------------------------------------------------------------
Seq Scan on test (cost=0.00..43692.03 rows=200 width=37) (actual time=0.327..186.813 rows=354 loops=1)
Filter: (id ~~ '5e1f%'::text)
Rows Removed by Filter: 1999648
Total runtime: 188.301 ms
(4 行)

test=# EXPLAIN ANALYZE SELECT id FROM test WHERE id LIKE '%5e1f';
QUERY PLAN

---------------------------------------------------------------------------------------------------------
Seq Scan on test (cost=0.00..43692.03 rows=200 width=37) (actual time=16.878..297.931 rows=28 loops=1)
Filter: (id ~~ '%5e1f'::text)
Rows Removed by Filter: 1999974
Total runtime: 298.472 ms
(4 行)


インデックスを作る
LIKE検索でもインデックスが使えるようにvarchar_pattern_ops付なのが味噌。
後者は後方一致を実現するための関数インデックス


test=# CREATE INDEX test_id_ptn_idx ON test (id varchar_pattern_ops);
CREATE INDEX
test=# CREATE INDEX test_id_ptn_reverse_idx ON test (reverse(id) varchar_pattern_ops);
CREATE INDEX


前方一致のLIKEを投げる

test=# EXPLAIN ANALYZE SELECT id FROM test WHERE id LIKE '5e1f%';
QUERY PLAN

-----------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on test (cost=4.88..113.98 rows=200 width=37) (actual time=0.597..2.106 rows=354 loops=1)
Filter: (id ~~ '5e1f%'::text)
-> Bitmap Index Scan on test_id_ptn_idx (cost=0.00..4.83 rows=28 width=0) (actual time=0.559..0.559 rows=354 loops=1)
Index Cond: ((id ~>=~ '5e1f'::text) AND (id ~<~ '5e1g'::text))
Total runtime: 3.718 ms
(5 行)

インデックスが利いた。

後方一致の場合

test=# EXPLAIN ANALYZE SELECT id FROM test WHERE id LIKE '%5e1f';
QUERY PLAN

---------------------------------------------------------------------------------------------------------
Seq Scan on test (cost=0.00..43692.03 rows=200 width=37) (actual time=20.272..305.338 rows=28 loops=1)
Filter: (id ~~ '%5e1f'::text)
Rows Removed by Filter: 1999974
Total runtime: 305.948 ms
(4 行)

当然利かない

関数インデックスを使うように下記のクエリを投げる

test=# EXPLAIN ANALYZE SELECT id FROM test WHERE reverse(id) LIKE reverse('%5e1f');
QUERY PLAN

---------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on test (cost=395.06..16726.74 rows=10000 width=37) (actual time=0.211..0.451 rows=28 loops=1)
Filter: (reverse(id) ~~ 'f1e5%'::text)
-> Bitmap Index Scan on test_id_ptn_reverse_idx (cost=0.00..392.56 rows=10000 width=0) (actual time=0.070..0.070 rows=28 loops=1)
Index Cond: ((reverse(id) ~>=~ 'f1e5'::text) AND (reverse(id) ~<~ 'f1e6'::text))
Total runtime: 0.644 ms
(5 行)

インデックスが使われた

解説

関数インデックスってのは、値を関数で処理した結果をインデックスとして作成するので
同一関数表記でWHERE句に定義されれば、その関数を処理することなく、関数インデックスに作成された値が検索される

よくある使い方は、下記のような大文字小文字の区別なしに検索するときに使う
式インデックス

当然入力値に対して、同じ値を返さない関数は使えない

で、今回reverse()関数で文字列の前後を入れ替えたインデックスを作っているので
内部的には前方一致になって後方一致のLIKE検索にもかかわらず、インデックスが使えるというわけでした


変な使い方だと
長い文字列をキーとする様なテーブルで
小さくコンパクトなインデックスを作りたい場合にも使える

CREATE INDEX test_id_md5s_idx ON test (decode(substring(md5(id),1,8),'hex'));


使うときは下記のようにする

SELECT * FROM test WHERE decode(substring(md5(id),1,8),'hex') = decode(substring(md5('ID-TEXT'),1,8),'hex') AND id = 'ID-TEXT';

md5ハッシュの前方32bit分だけをインデックス化してるので、インデックスサイズは小さい
これを検索すると、オプティマイザは、値をハッシュ化したインデックスで絞り込んだ後、
id = 'ID-TEXT' で再チェックして値を出力する

ハッシュを使って絞り込んだ段階で32bitなので、42億分の1まで絞り込めてるので、読み込むブロックは比較的少なく意外と高速です

md5をそのまま使うなら

CREATE INDEX test_id_md5s_idx ON test (decode(md5(id),'hex'));


SELECT * FROM test WHERE decode(md5(id),'hex') = decode(md5('ID-TEXT'),'hex') AND id = 'ID-TEXT';

こういう感じで

decode(md5(),'hex')としているのは、md5の戻り値がbase16なので、これをデコードしてバイナリ値とした方がインデックスでの占める量が半分になるため
そのままインデックス化すると16進数32バイトテキストだけど、decodeすると16バイトで済む
substringで先頭8バイト切り出した場合は32bitなので4バイト、INTEGERのインデックスと大差なくなる(厳密にいうとBYTEAなのでちょっと違う)

欠点はユニークインデックスとかプライマリキーに設定できないので
ユニークを求める場合は、別の手段でユニーク性を確保する必要があるってことかな
INSERTするときに NOT EXISTS を使って下記のようにしてやるとか

INSERT INTO test (id,value) SELECT 'ID-TEXT',1234567890 WHERE NOT EXISTS (SELECT true FROM test WHERE decode(substring(md5(id),1,8),'hex') = decode(substring(md5('ID-TEXT'),1,8),'hex') AND id = 'ID-TEXT');


DBの正規化してUUIDとかIDを振ってやる場合に同一のValueのレコードを持ちたくない場合に有用。Valueと同じ容量のIndex持ちたくない