July 30th, 2007 by depesz | Tags: , | 8 comments »
Did it help? If yes - maybe you can help me?

for the long time everybody knew that you can't use index on “LIKE" operations.

then came text_pattern_ops, so we could use indexes for prefix searches:

# \d depesz_test
Table "public.depesz_test"
Column | Type | Modifiers
--------+---------+----------------------------------------------------------
id | integer | not null default nextval('depesz_test_id_seq'::regclass)
email | text | not null
Indexes:
"depesz_test_pkey" PRIMARY KEY, btree (id)
"x" UNIQUE, btree (email text_pattern_ops)

# explain analyze select count(*) from depesz_test where email like 'dep%';
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------
Aggregate (cost=96.71..96.72 rows=1 width=0) (actual time=0.983..0.985 rows=1 loops=1)
-> Bitmap Heap Scan on depesz_test (cost=4.68..96.65 rows=24 width=0) (actual time=0.184..0.641 rows=155 loops=1)
Filter: (email ~~ 'dep%'::text)
-> Bitmap Index Scan on x (cost=0.00..4.67 rows=24 width=0) (actual time=0.158..0.158 rows=155 loops=1)
Index Cond: ((email ~>=~ 'dep'::text) AND (email ~<~ 'deq'::text))
Total runtime: 1.067 ms
(6 rows)

but what if i'd like to search for ‘%something'? not prefix, but suffix. in my example – what can i do to use indexes when searching for people from given domain?

sanity check – perhaps it works now :):

# explain analyze select count(*) from depesz_test where email like '%pl';
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------
Aggregate (cost=19881.37..19881.38 rows=1 width=0) (actual time=602.059..602.061 rows=1 loops=1)
-> Seq Scan on depesz_test (cost=0.00..19776.34 rows=42011 width=0) (actual time=3.803..601.456 rows=282 loops=1)
Filter: (email ~~ '%pl'::text)
Total runtime: 602.131 ms
(4 rows)

ok. seq scan, so at least we're sure that environment is sane 🙂

one possible approach to do it would be to add another field, and copy domain from email to have it there.

but then – some pople have emails like @poczta.onet.pl. and if i'd like to count them also when looking for onet.pl? i would be still at the same problem.

fortunatelly there is a very simple solution. let's modify the search so it will not be suffix search, but prefix search. after all – it's just another end of string.

so, instead of: field like ‘%domain' i would have to write: reversed-field like ‘niamod%';

seems simple.

how do i reverse field? in sql there is no function to do it. i could technically use plpgsql to write reversing function, but hey, we've got pl/perl 🙂

this small function does reversing:

create function text_reverse(text) returns text as $BODY$
return scalar reverse shift;
$BODY$ language plperl immutable;

if you dont understand it, don't worry. it works:

# select text_reverse('depesz');
text_reverse
--------------
zseped
(1 row)

one important thing – please notice ‘immutable' word at the end of function
definition. this flag makes it possible to create functional index. and we like
functional indexes because with them we dont need another field in table 🙂

so, now, let's create the index:

# create unique index rev_x on depesz_test ( text_reverse(email) text_pattern_ops );

index created, let's see if it will be used:

# explain analyze select count(*) from depesz_test where text_reverse(email) like text_reverse('%pl');
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=8098.19..8098.20 rows=1 width=0) (actual time=9.225..9.227 rows=1 loops=1)
-> Bitmap Heap Scan on depesz_test (cost=146.76..8085.06 rows=5251 width=0) (actual time=0.583..8.468 rows=282 loops=1)
Filter: (text_reverse(email) ~~ 'lp%'::text)
-> Bitmap Index Scan on rev_x (cost=0.00..145.44 rows=5251 width=0) (actual time=0.314..0.314 rows=282 loops=1)
Index Cond: ((text_reverse(email) ~>=~ 'lp'::text) AND (text_reverse(email) ~<~ 'lq'::text))
Total runtime: 9.307 ms
(6 rows)

works nicely 🙂

instead of writing “like text_reverse(‘%pl')" i could have written “like ‘lp%'", but this extra call doesn't cost me much, and it makes it more readable.

UPDATE

just after writing this dim from #postgresql told me that there was article on this in french. sorry. didn't know it. in case you'd like to check the french article please follow this link.

dim also suggested to do a small benchmark of plpgsql and plperl versions.

so i did on my test dataset:

# select count(*), sum(length(email)) from depesz_test;
count | sum
---------+----------
1050267 | 17935093
(1 row)

i used my plperl function and plpgsql function from this french article, and did test – first plperl version:

first try:

# explain analyze select *, text_reverse(email) from depesz_test;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
Seq Scan on depesz_test (cost=0.00..279717.42 rows=1050267 width=22) (actual time=0.099..11762.904 rows=1050267 loops=1)
Total runtime: 13899.248 ms
(2 rows)

second try:

# explain analyze select *, text_reverse(email) from depesz_test;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
Seq Scan on depesz_test (cost=0.00..279717.42 rows=1050267 width=22) (actual time=0.103..11759.954 rows=1050267 loops=1)
Total runtime: 13990.475 ms
(2 rows)

now plpgsql:

# explain analyze select *, reverse(email) from depesz_test;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------
Seq Scan on depesz_test (cost=0.00..279717.42 rows=1050267 width=22) (actual time=124.767..51294.990 rows=1050267 loops=1)
Total runtime: 53241.475 ms
(2 rows)

# explain analyze select *, reverse(email) from depesz_test;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
Seq Scan on depesz_test (cost=0.00..279717.42 rows=1050267 width=22) (actual time=0.199..54151.088 rows=1050267 loops=1)
Total runtime: 56177.876 ms
(2 rows)

as we can see – perl is much faster when it comes to text operations. of course you will not see this difference on select time, but it will influence index creation/update times.

  1. 8 comments

  2. # Thomas Reiss
    Jul 31, 2007

    Hello,
    I’m the author of the french article. It’s really amazing to see that you had the same idea at the same time 😉
    Thanks for the comparison, it’s very interesting. I’m aware of this speed issue and I’m writing a C function for reverse, it may be worth a bench ?
    Also, did you test your reverse function while using a multi-byte encoding like UTF-8 ?

  3. Aug 1, 2007

    @Thomas Reiss:
    actually it was utf-8. on the other hand dataset didn’t contain any multi-byte characters (it was all emails).
    i’ll redo the test with utf-8 characters, but i think i’ll wait and make the test with also your custom c function – or if you will do the test, i’ll just link to it.

  4. # Phil Endecott
    Aug 1, 2007

    When I needed to match on email domains, rather than addr like ‘%@example.com’ I used this:

    split_part(addr,’@’,2)=’example.com’

    You can then create an index like this:

    create index messages by addr_domain on messages (split_part(addr,’@’,2));

    The main problem that I have had with this is that I may want to includes john@support.example.com in my “all @ example.com” query. For that, the reversing approach that you have described is better.

    Phil.

  5. # Fomsninia
    Dec 20, 2008

    Much the interesting has found here

  1. 4 Trackback(s)

  2. Jul 30, 2007: Umlaute und Performance? - PG-Forum.de
  3. Sep 15, 2007: </depesz> » Blog Archive » indexable “field like ‘%something’” - update
  4. Sep 15, 2007: </depesz> » Blog Archive » speeding up like ‘%xxx%’
  5. Sep 10, 2010: Почему мой индекс не используется | Личная трибуна Димки

Leave a comment