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.

Can anyone explain how the LIKE operator is implemented in current database systems (e.g. MySQL or Postgres)? or point me to some references that explain it?

The naive approach would be to inspect each record, executing a regular expression or partial string match on the field of interest, but I have a feeling (hope) that these systems do something smarter.

share|improve this question
add comment

3 Answers 3

up vote 10 down vote accepted

No, that's pretty much what they're doing. Now, if there is not a leading wildcard and the field is indexed, which is the usual situation, the database engine can apply the regular expression to the index. So, for example, if you write

SELECT *
  FROM employees
 WHERE last_name LIKE 'Cav%'

the database can use the index on LAST_NAME to find all the rows where the last name begins 'Cav'. On the other hand, if you had something like

SELECT *
  FROM employees
 WHERE last_name LIKE '%av%'

the database would have to scan the entire table (or the entire index) and evaluate the expression against the full LAST_NAME value. Obviously, that's very expensive.

Most of the better relational databases have facilities to do full-text search in a more efficient manner by constructing different sorts of indexes and text catalogs but these don't use the LIKE keyword. For example, here's a nice article that discusses full-text search in PostgreSQL.

share|improve this answer
3  
Oracle can use an index even with a leading percent. If the data being searched for represents a small subset of the rows then hint can force it to use an index and make the execution faster. See laurentschneider.com/wordpress/2009/07/…;. –  Leigh Riffel Apr 15 '11 at 13:04
1  
"scan the entire table... Obviously, that's very expensive" -- that rather depends on the table ;) p.s. do you agree LAST_NAME be a candidate for (the first column in) the clustered index? p.p.s. to what extent does this answer assume the database system is based on contiguous storage on disk and B-tree indexes? –  onedaywhen Jan 18 '12 at 13:34
add comment

In addition to what Justin Cave already wrote about PostgreSQL, there is a new feature in PostgreSQL 9.1 to speed up any search with LIKE (~~) or ILIKE (~~*). You can now use the operator classes provided by the module pg_trgm with a GIN or GiST index to speed up LIKE expressions that are not left-anchored. To install the extension, run once per database:

CREATE EXTENSION pg_trgm;

Create an index of the form

CREATE INDEX tbl_col_gin_trgm_idx ON tbl USING gin (col gin_trgm_ops);

Or:

CREATE INDEX tbl_col_gist_trgm_idx ON tbl USING gist (col gist_trgm_ops);

Creating and maintaining a GIN or GiST index carries a cost, but if your table is not heavily written, this is a great feature for you.

Depesz has written an excellent article in his blog about the new feature.

GIN or GiST?

These two quotes from the manual should provide some guidance

The choice between GiST and GIN indexing depends on the relative performance characteristics of GiST and GIN, which are discussed elsewhere. As a rule of thumb, a GIN index is faster to search than a GiST index, but slower to build or update; so GIN is better suited for static data and GiST for often-updated data.

But, when working with the similarity operator <-> or similarity():

This can be implemented quite efficiently by GiST indexes, but not by GIN indexes.

share|improve this answer
1  
Reading this I wondered whether to use GIN or GiST. According to what I read, GIN indexes are more expensive to maintain but faster to search, while a GiST index is cheaper to maintain but slower to search. This means GIN indexes should generally be used on relatively static data while GiST indexes are preferred on more heavily mutating tables. –  Colin 't Hart Nov 6 '13 at 9:08
1  
@Colin'tHart: That's generally true, but there are exceptions to the rule. Consider the addendum above. –  Erwin Brandstetter Nov 6 '13 at 15:35
add comment

Speaking about MySQL, the position of the wild-card character (%) makes a difference. If the first part of the text is specified like where first_name like 'Sta%', then the DB engine will search only a smaller subset of words staring with S, then going to St, and then Sta, etc. If you do something like where first_name like '%stan%', then and entire scan of the column will be required. You can also look into full-text indexes that also does natural language searches. Check out the MySQL docs here.

share|improve this answer
1  
Why would it start searching "S%" when the substring is defined to 3 characters (i.e. we know the string isn't "Sr%")? Or were you assuming the DB has a prefix tree over the attributes and providing an example of traversing this tree? –  Nick Apr 15 '11 at 18:38
add comment

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.