In MySql, find strings with a given prefix

Question

In MySql, I want to locate records where the string value in one of the columns begins with (or is the same as) a query string. The column is indexed with the appropriate collation order. There is no full-text search index on the column though.

A good solution will:

1. Use the index on the column. Solutions that need to iterate over all the records in the table aren't good enough (several million records in the table)

2. Work with strings with any character values. Some of the column values contain punctuation characters. The query string might too. Keep this in mind if your solution includes regex characters or similar. The strings are UTF-8 encoded, but if your solution only works with ASCII it could still be useful.

The closest I have at this point is

SELECT * FROM TableName WHERE ColumnName BETWEEN query AND <<query+1>>

Where <<query+1>> is pre-computed to lexicographically follow query in the collation order. For example, if query is "o hai" then <<query+1>> is "o haj".

Answer 1

Surprisingly, a LIKE query will use an index just fine if you're doing a prefix search.

SELECT * from TableName Where ColumnName LIKE 'o hai%'

will indeed use an index since it does not begin with a wildcard character.

This (and other behavior) is documented in the "How MySQL uses Indexes" doc: http://dev.mysql.com/doc/refman/5.0/en/mysql-indexes.html

You will need to escape the '%' character and follow normal quoting rules, but other than that any utf-8 input prefix ought to work and do the job. Run an EXPLAIN query to make sure, sometimes other reasons can preclude indexes from working such as needing to do an OPTIMIZE TABLE to update index cardinalities (though this can take ages and locks your table)

Answer 2

Try this:

SELECT * FROM tablename WHERE columname LIKE CONCAT(query, '%');