Wildspeed extension provides GIN index support for wildcard search for LIKE operator.
Online version of this document is available http://www.sai.msu.su/~megera/wiki/wildspeed
- Oleg Bartunov oleg@sai.msu.su, Moscow, Moscow University, Russia
- Teodor Sigaev teodor@sigaev.ru, Moscow, Moscow University,Russia
Stable version, included into PostgreSQL distribution, released under BSD license. Development version, available from this site, released under the GNU General Public License, version 2 (June 1991)
Stable version of wildspeed is available from http://www.sigaev.ru/cvsweb/cvsweb.cgi/wildspeed/
% make USE_PGXS=1
% make install
% make installcheck
% psql DB -c 'CREATE EXTENSION wildspeed'
Wildspeed provides opclass (wildcard_ops) and uses partial match feature of GIN, available since 8.4. Also, it supports full index scan.
The size of index can be very big, since it contains entries for all permutations of the original word, see [1] for details. For example, word hello will be indexed as well as its all permutations:
=# select permute('hello');
permute
--------------------------------------
{hello$,ello$h,llo$he,lo$hel,o$hell}
Notice, symbol '$' is used only for visualization, in actual
implementation null-symbol '\0' is used.
Search query rewritten as prefix search:
*X -> X$*
X*Y -> Y$X*
*X* -> X*
For example, search for 'hel*o' will be rewritten as 'o$hel'.
Special function permute(TEXT), which returns all permutations of
argument, provided for test purposes.
Performance of wildspeed depends on search pattern. Basically, wildspeed is less effective than btree index with text_pattern_ops for prefix search (the difference is greatly reduced for long prefixes) and much faster for wildcard search.
Wildspeed by default uses optimization (skip short patterns if there
are long one), which can be turned off in Makefile by removing define
-DOPTIMIZE_WILDCARD_QUERY.
- http://www.cs.wright.edu/~tkprasad/courses/cs499/L05TolerantIR.ppt
- http://nlp.stanford.edu/IR-book/html/htmledition/permuterm-indexes-1.html
Table words contains 747358 records, w1 and w2 columns contains the same data in order to test performance of Btree (w1) and GIN (w2) indexes:
Table "public.words"
Column | Type | Modifiers
--------+------+-----------
w1 | text |
w2 | text |
words=# create index bt_idx on words using btree (w1 text_pattern_ops);
CREATE INDEX
Time: 1885.195 ms
words=# create index gin_idx on words using gin (w2 wildcard_ops);
vacuum analyze;
CREATE INDEX
Time: 530351.223 ms
Size:
words=# select pg_relation_size('words');
pg_relation_size
------------------
43253760
words=# select pg_relation_size('gin_idx');
pg_relation_size
------------------
417816576
(1 row)
words=# select pg_relation_size('bt_idx');
pg_relation_size
------------------
23437312
(1 row)
Prefix search:
words=# select count(*) from words where w1 like 'a%';
count
-------
15491
(1 row)
Time: 7.502 ms
words=# select count(*) from words where w2 like 'a%';
count
-------
15491
(1 row)
Time: 31.152 ms
Wildcard search:
words=# select count(*) from words where w1 like '%asd%';
count
-------
26
(1 row)
Time: 147.308 ms
words=# select count(*) from words where w2 like '%asd%';
count
-------
26
(1 row)
Time: 0.339 ms
Full index scan:
words=# set enable_seqscan to off;
words=# explain analyze select count(*) from words where w2 like '%';
QUERY PLAN
--------------------------------------------------------------------------------------------------------------
-----------------------------
Aggregate (cost=226274.98..226274.99 rows=1 width=0) (actual time=2218.709..2218.709 rows=1 loops=1)
-> Bitmap Heap Scan on words (cost=209785.73..224406.77 rows=747283 width=0) (actual time=1510.516..1913.
430 rows=747358 loops=1)
Filter: (w2 ~~ '%'::text)
-> Bitmap Index Scan on gin_idx (cost=0.00..209598.91 rows=747283 width=0) (actual time=1509.358..1
509.358 rows=747358 loops=1)
Index Cond: (w2 ~~ '%'::text)
Total runtime: 2218.747 ms
(6 rows)