Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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?

share|improve this question
    
Why are you trying to rewrite? Performance? Neatness? Is s.name indexed? –  Martin Smith Jan 15 '12 at 11:29
    
I want to write for performance, s.name is not indexed. –  Lucas Kauffman Jan 15 '12 at 11:36
6  
Well as you are searching without leading wild cards and not selecting any additional columns an index on name could be useful here if you care about performance. –  Martin Smith Jan 15 '12 at 11:39

4 Answers 4

up vote 37 down vote accepted

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

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

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

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

Or slightly faster, with a character class:

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

A quick test without index yields faster results than for SIMILAR TO in either case for me.
With an appropriate B-Tree index in place, LIKE wins this race by orders of magnitude.

Read the basics about pattern matching in the manual.


Index for superior performance

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

CREATE INDEX spelers_name_special_idx ON spelers (name text_pattern_ops);

Makes this kind of query faster by orders of magnitude. 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), a plain index (with default operator class) will do.

Such an index is only good for left-anchored patterns (matching from the start of the string).

SIMILAR TO or regular expressions with basic left-anchored expressions can use this index, too. But not with branches (B|D) or character classes [BD] (at least in my tests on PostgreSQL 9.0).

Trigram matches or text search use special GIN or GiST indexes.

Overview of pattern matching operators

  • LIKE (~~) is simple and fast but limited in its capabilities.
    ILIKE (~~*) the case insensitive variant.
    pg_trgm extends index support for both.

  • ~ (regular expression match) is powerful but more complex and may be slow for anything more than basic expressions.

  • SIMILAR TO is just pointless. A peculiar halfbreed of LIKE and regular expressions. I never use it. Explanation below.

  • % is the "similarity" operator, provided by the additional module pg_trgm.

  • @@ is the text search operator.

pg_trgm - trigram matching

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:

pg_trgm also provides the "similarity" operator %

Text search

Is a special type of pattern matching with separate infrastructure and index types. It uses dictionaries and stemming and is a great tool to find words in documents, especially for natural languages.

Consider the introduction in the manual and the overview of operators and functions.

The additional module fuzzystrmatch offers some more options, but performance is generally inferior to all of the above.

Why are regular expressions (~) always 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.

SIMILAR TO is only supported in PostgreSQL because it ended up in early drafts of the SQL standard. They still haven't gotten rid of it. But there are plans to remove it and include regexp matches instead - or so I heard.

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 for this particular case

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 true 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, you can simplify further:

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 should just stick with the standard operators - arriving at what you already have in the question.

share|improve this answer
    
The OP doesn't have an index on name but do you happen to know, if they did, would their original query involve 2 range seeks and similar a scan? –  Martin Smith Jan 15 '12 at 11:43
1  
@MartinSmith: A quick test with EXPLAIN ANALYZE shows 2 bitmap index scans. Multiple bitmap index scans can be combined rather quickly. –  Erwin Brandstetter Jan 15 '12 at 11:46
    
Thanks. So would there be any milage with replacing the OR with UNION ALL or replacing name LIKE 'B%' with name >= 'B' AND name <'C' in Postgres? –  Martin Smith Jan 15 '12 at 11:59
1  
@MartinSmith: UNION won't but, yes, combining the ranges into one WHERE clause will speed up the query. I have added more to my answer. Of course, you have to take your locale into account. Locale-aware search is always slower. –  Erwin Brandstetter Jan 15 '12 at 12:29
1  
@a_horse_with_no_name: I expect not. The new capabilities of pg_tgrm with GIN indexes are a treat for generic text search. A search anchored at the start is already faster than that. –  Erwin Brandstetter Jan 17 '12 at 22:44

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
share|improve this answer
1  
It worked and I got a cost of 1.19 where I had 1.25. Thanks ! –  Lucas Kauffman Jan 15 '12 at 11:41

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).

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.