EXPLAIN EXTENDED

In the previous article, I described a query that searches for a phrase beginning with a certain letter or string, ignoring a leading article if any. This is useful in searching for movie titles.

Today, I'll add some more features to this query.

Let's pretend we are running an internationalized website which contains movie titles in many languages. We have a table showing us whether a certain word in the beginning of a title is an article, particle or any other part of speech that should be omitted when filtering:

SELECT  *
FROM    t_article

To select all titles beginning with a certain string, we can use the same approach we used when the articles were hardcoded:

SELECT  mov_title
FROM    (
        SELECT  CONCAT(art_article, ' ') AS article
        FROM    t_article
        UNION ALL
        SELECT  ''
        ) articles, t_movie
WHERE   mov_title LIKE CONCAT(article, 'Can%')

But for some reason it doesn't work as efficiently anymore.

This is because MySQL cannot use range access method in this case.

MySQL documentation states that range access can be used only when the expression used in a comparison is a constant, i. e. one of the following:

• A constant from the query string
• A column of a const or system table from the same join
• The result of an uncorrelated subquery
• Any expression composed entirely from subexpressions of the preceding types

Unfortunately, the expression we use in comparison doesn't fall under any of these categories.

For the range access method to be usable, we need to use <= and >= comparisons in the where clause. We need to find all titles that lie between the initial (that is, the searched for string prepended with an article), and some greatest value of those beginning with the initial.

In case of integers, each value has at most one unique predecessor and at most one unique successor, which we can calculate by adding or substracting a 1 to the value.

In case of strings, it's not so easy: strings are not well-ordered, that's why we cannot calculate the greatest element beginning with the initial: such an element just does not exists. Even calculating the least element which is greater than the initial and not LIKE it, may be a complex task that should take into account case and accent sensitivity.

That's why we'll just take this least unlike element from the table itself.

We will need all movie titles that lie between initial and the first value in the string order that is NOT LIKE initial:

SELECT  mov_title
FROM    (
        SELECT  'Can' AS filter
        ) vars,
        (
        SELECT  CONCAT(art_article, ' ') AS article
        FROM    t_article
        UNION ALL
        SELECT  ''
        ) articles, t_movie
WHERE   mov_title >= CONCAT(article, filter)
        AND mov_title <
        (
        SELECT  mov_title
        FROM    t_movie
        WHERE   mov_title >= CONCAT(article, filter)
                AND mov_title NOT LIKE CONCAT(article, filter, '%')
        LIMIT 1
        )

This runs even longer. This is not so surprising, as this is a well-known bug in MySQL that does not let to use range access method in dependent subqueries.

To work around this bug, we will need to create a user-defined function that returns this least unlike element:

CREATE FUNCTION fn_get_least_unlike(initial VARCHAR(200)) RETURNS VARCHAR(200)
NOT DETERMINISTIC
READS SQL DATA
BEGIN
        DECLARE _title VARCHAR(200);
        DECLARE EXIT HANDLER FOR NOT FOUND RETURN UNHEX('FFFF');
        SELECT  mov_title
        INTO    _title
        FROM    t_movie
        WHERE   mov_title >= initial
                AND mov_title NOT LIKE CONCAT(initial, '%')
        ORDER BY
                mov_title
        LIMIT 1;
        RETURN _title;
END

, and use it in the query:

SELECT mov_title
FROM (
SELECT 'Can' AS filter
) vars,
(
SELECT CONCAT(art_article, ' ') AS article
FROM t_article
UNION ALL
SELECT ''
) articles, t_movie
WHERE mov_title >= CONCAT(article, filter)
AND mov_title < fn_get_least_unlike(CONCAT(article, filter)) [/sourcecode]

Finally, it works as fast as it should.