Indexing varchar column to search for first letter

Question

I'm trying to optimize a legacy web-app where users can ask for a list of all records whose name starts with a given character.

The query to optimize is:

SELECT oggetto.id_oggetto, titolo, anno, specifiche from oggetto inner join oggetto_formato on (oggetto.id_oggetto = oggetto_formato.id_oggetto)
            where attivato=1 and oggetto.titolo like 'C%' and id_formato IN ('6', '7', '4') order by titolo LIMIT 650,50;

Sorry for the italian.... oggetto means item and titolo is title. I want to speed up the lookup on oggetto.titolo.

EXPLAIN EXTENDED tells me the following:

+----+-------------+-----------------+-------+-----------------------------------------+-----------------+---------+------------------------------+------+----------+-----------------------------+
| id | select_type | table           | type  | possible_keys                           | key             | key_len | ref                          | rows | filtered | Extra                       |
+----+-------------+-----------------+-------+-----------------------------------------+-----------------+---------+------------------------------+------+----------+-----------------------------+
|  1 | SIMPLE      | oggetto         | ALL   | PRIMARY                                 | NULL            | NULL    | NULL                         | 42585|   100.00 | Using where; Using filesort |
|  1 | SIMPLE      | oggetto_formato | ref   | PRIMARY,FK_oggetto_formato_2,id_oggetto | PRIMARY         | 4       | agorateca.oggetto.id_oggetto |    1 |   100.00 | Using where; Using index    |
+----+-------------+-----------------+-------+-----------------------------------------+-----------------+---------+------------------------------+------+----------+-----------------------------+

I created the following index:

CREATE INDEX title_initial ON item (title(2));

The result of EXPLAIN EXTENDED for the above query after creating the index is:

    +----+-------------+-----------------+-------+-----------------------------------------+-----------------+---------+------------------------------+------+----------+-----------------------------+
    | id | select_type | table           | type  | possible_keys                           | key             | key_len | ref                          | rows | filtered | Extra                       |
    +----+-------------+-----------------+-------+-----------------------------------------+-----------------+---------+------------------------------+------+----------+-----------------------------+
    |  1 | SIMPLE      | oggetto         | range | PRIMARY,iniziale_titolo                 | iniziale_titolo | 9       | NULL                         | 2880 |   100.00 | Using where; Using filesort |
    |  1 | SIMPLE      | oggetto_formato | ref   | PRIMARY,FK_oggetto_formato_2,id_oggetto | PRIMARY         | 4       | agorateca.oggetto.id_oggetto |    1 |   100.00 | Using where; Using index    |
    +----+-------------+-----------------+-------+-----------------------------------------+-----------------+---------+------------------------------+------+----------+-----------------------------+

Could anyone confirm my opinion that the index is set up correctly and is doing its job?

Answer 1

I'm not sure what DBMS you are using but in general yes. It looks like your index is doing what it is supposed to. As a general case the optimizers can take advantage of an index in a "like" query if there are no pattern (_%[] etc) characters on the left hand side.

So this will use an index

oggetto.titolo like 'C%'

But this could not

oggetto.titolo like '%C'

Answer 2

You need to see how distributed the two-character combinations are.

You should run this query:

SELECT IFNULL(TwoChar,'All Combinations'),RowCount FROM 
(
    SELECT LEFT(titolo,2) TwoChar,COUNT(1) RowCount
    FROM oggetto GROUP BY LEFT(titolo,2) WITH ROLLUP
) A
ORDER BY RowCount;

Afterwards, look at the two character keys with the highest RowCount.

If you can lookup those keys fast, then all the other keys can be looked up quickly as well.