Pattern matching with LIKE, SIMILAR TO or regular expressions in PostgreSQL

Question

I had to write a simple query where I go looking for people's name that start with a B or a D :

SELECT s.name from
spelers s 
WHERE s.name LIKE 'B%' or s.name like 'D%'
order by 1

I was wondering if there is a way to rewrite this to become more performant. So I can avoid or and / or like?

Answer 1

Your query is pretty much the optimum. Syntax won't get much shorter, query won't get much faster. I only reformat:

SELECT name
FROM   spelers
WHERE  name ~~ 'B%' OR name ~~ 'D%'
ORDER  BY 1;

If you really want to shorten the syntax a bit, use a regular expression with branches:

...
WHERE  name ~ '^(B|D).*'

Or slightly faster, yet, with a character class:

...
WHERE  name ~ '^[BD].*'

A quick test yields faster results than for SIMILAR TO in both cases for me. Either is also slightly faster than two LIKE conditions (One scan with an expensive condition is still slightly cheaper than two scans with a cheap condition.)

SIMILAR TO is a peculiar halfbreed of LIKE and regular expressions that's only included in PostgreSQL because it is in an SQL standard. I hardly ever use it myself. More about that further down.

---

Index for superior performance

If you are concerned with performance, create an index like this:

CREATE INDEX spelers_name_text_pattern_ops_idx
ON spelers (name text_pattern_ops);

Will speed up this kind of query by orders of magnitude in bigger tables. Special considerations apply for locale-specific sort order. Read more about operator classes in the manual. If you are using the standard "C" locale (most people don't), then a plain index will do.

Note, that such an index cannot be utilized for a full-text search. Only patterns anchored at the start will use it.

Note also, that SIMILAR TO or regular expressions with branches (B|D) or character classes [BD] in the pattern will also not use the index (at least in my tests on PostgreSQL 9.0).

Read about pattern matching in the manual.

---

pg_trgm

Beginning with PostgreSQL 9.1 you can facilitate the extension pg_trgm to provide index support for any LIKE / ILIKE pattern with a GIN or GiST index.

Details, example and links in this related answer.

pg_trgm also provides the "similarity" operator '%', which may be interesting in the context of pattern matching.

---

Why are regular expressions (~) faster than SIMILAR TO?

The answer is simple. SIMILAR TO expressions are rewritten into regular expressions internally. So, for every SIMILAR TO expression, there is at least one faster regular expression (that saves the overhead of rewriting the expression). There is no performance gain in using SIMILAR TO ever.

And simple expressions that can be done with LIKE (~~) are faster with LIKE anyway.

EXPLAIN ANALYZE reveals it. Just try with any table yourself!

EXPLAIN ANALYZE SELECT * FROM spelers WHERE name SIMILAR TO 'B%';

Reveals:

...  
Seq Scan on spelers  (cost= ...  
  Filter: (name ~ '^(?:B.*)$'::text)

SIMILAR TO has been rewritten with a regular expression (~).

---

Ultimate performance

But EXPLAIN ANALYZE reveals more. Try, with the afore-mentioned index in place:

EXPLAIN ANALYZE SELECT * FROM spelers WHERE name ~ '^B.*;

Reveals:

...
 ->  Bitmap Heap Scan on spelers  (cost= ...
       Filter: (name ~ '^B.*'::text)
        ->  Bitmap Index Scan on spelers_name_text_pattern_ops_idx (cost= ...
              Index Cond: ((prod ~>=~ 'B'::text) AND (prod ~<~ 'C'::text))

Internally, with an index that is not locale-aware (text_pattern_ops or using locale C) simple left-anchored expressions are rewritten with these text pattern operators: ~>=~, ~<=~, ~>~, ~<~. This is the case for ~, ~~ or SIMILAR TO alike.

The same is also the case for indexes on varchar types with varchar_pattern_ops or char with bpchar_pattern_ops.

So, applied to the original question, this is the fastest possible way:

SELECT name
FROM   spelers  
WHERE  name ~>=~ 'B' AND name ~<~ 'C'
    OR name ~>=~ 'D' AND name ~<~ 'E'
ORDER  BY 1;

Of course, if you should happen to search for adjacent Initials (Martin's question in the comments), you can further simplify:

WHERE  name ~>=~ 'B' AND name ~<~ 'D'   -- strings starting with B or C

The gain over plain use of ~ or ~~ is small. If performance isn't your paramount requirement, you might just stick with the standard operators - arriving at what you already have in the question.

Answer 2

How about adding a column to the table. Depending on your actual requirements:

person_name_start_with_B_or_D (Boolean)

person_name_start_with_char CHAR(1)

person_name_start_with VARCHAR(30)

PostgreSQL doesn't support computed columns in base tables a la SQL Server but the new column can be maintained via trigger. Obviously, this new column would be indexed.

Alternatively, an index on an expression would give you the same, cheaper. E.g.:

CREATE INDEX spelers_name_initial_idx ON spelers (left(name, 1)); 

Queries that match the expression in their conditions can utilize this index.

This way, the performance hit is taken when the data is created or amended, so may only be appropriate for a low activity environment (i.e. much fewer writes than reads).

Answer 3

You could try

SELECT s.name
FROM   spelers s
WHERE  s.name SIMILAR TO '(B|D)%' 
ORDER  BY s.name

I've no idea whether or not either the above or your original expression are sargable in Postgres though.

If you create the suggested index would also be interested to hear how this compares with the other options.

SELECT name
FROM   spelers
WHERE  name >= 'B' AND name < 'C'
UNION ALL
SELECT name
FROM   spelers
WHERE  name >= 'D' AND name < 'E'
ORDER  BY name

Answer 4

What I have done in the past, faced with a similar performance issue, is to increment the ASCII character of the last letter, and do a BETWEEN. You then get the best performance, for a subset of the LIKE functionality. Of course, it only works in certain situations, but for ultra-large datasets where you're searching on a name for instance, it makes performance go from abysmal to acceptable.