Does anyone know what the complexity is for the SQL LIKE operator for the most popular databases?
views:
249answers:
3
+1
A:
Depends on the RDBMS, the data (and possibly size of data), indexes and how the LIKE is used (with or without prefix wildcard)!
You are asking too general a question.
Mitch Wheat
2009-04-29 11:48:24
Yeah, I figured, but it's a question for a friend, and he didn't tell me more.
Kronikarz
2009-04-29 18:58:10
+1
A:
If you are asking about the performance impact:
The problem of like is that it keeps the database from using an index. On Oracle I think it doesn't use indexes anymore (but I'm still on Oracle 9). SqlServer uses indexes if the wildcard is only at the end. I don't know about other databases.
Stefan Steinegger
2009-04-29 11:50:52
Prevent random access on an index, but surely not scanning of an index (although it might change which indexes it uses)?
Tom Hawtin - tackline
2009-05-28 00:35:48
Not sure what you mean. Scanning the whole index (and joining to the table afterwards) isn't faster then scanning the real table, is it?
Stefan Steinegger
2009-05-28 07:00:57
Scanning the whole index and joining to the table afterwards can be MUCH faster than scanning the real table. Indexes are typically narrower than tables and more "records" fit on a database page.
David B
2009-10-31 17:29:03
+5
A:
For MySQL:
LIKE 'foo%' is quite fast if run on an indexed column. Descending the B-tree to the correct position is a very fast operation. After that it depends on how long the range is.
LIKE '%foo%' has O(n) complexity. If it's your only criteria that means a full table scan. If you have other criterias that can by executed using indices, it will only scan the the rows that remain after the initial filtering.
A hack that sometime is used to speed things up is to store the column in reverse as well:
col LIKE 'foo%' OR col_reverse LIKE 'oof%'
This approach combined with smart usage of clustered indices can cause a major speedup. This only works for short fields, though, since MySQL has a maximum index length of 1024 bytes (if I remember correctly).
Emil H
2009-04-29 11:54:51
Don't you need 'oof%' on col_reverse? Also, the second query fragment answers a different question from the first.
Jonathan Leffler
2009-04-29 12:14:40
"col LIKE '%foo%'" will match occurrences of "foo" anywhere in the field. "col LIKE 'foo%' OR col_reverse LIKE 'oof%'" will only match a subset of those results (ie, where the field begins or ends with "foo").
LukeH
2009-04-29 12:30:55
Yep. It's not a silver bullet. Just thought it'd be worth mentioning considering the general nature of the question. :)
Emil H
2009-04-29 13:04:46