EXPLAIN EXTENDED

From Stack Overflow:

I would like to produce a character list of all of the first letters of column in my database.

Is there a way to do this in MySQL?

Let's create a sample table of 1,000,000 records and fill it with random data:

Table creation details

CREATE TABLE filler (
id INT NOT NULL PRIMARY KEY AUTO_INCREMENT
) ENGINE=Memory;

CREATE TABLE t_names (
id INT NOT NULL PRIMARY KEY,
name VARCHAR(50) NOT NULL,
KEY ix_names_name (name)
) ENGINE=InnoDB DEFAULT CHARSET=UTF8;

DELIMITER $$

CREATE PROCEDURE prc_filler(cnt INT)
BEGIN
DECLARE _cnt INT;
SET _cnt = 1;
WHILE _cnt <= cnt DO
                INSERT
                INTO    filler
                SELECT  _cnt;
                SET _cnt = _cnt + 1;
        END WHILE;
END
$$

DELIMITER ;

START TRANSACTION;
CALL prc_filler(1000000);
COMMIT;

SET @l_vowels = 'aeiouy';
SET @u_vowels = UPPER(@l_vowels);
SET @l_consonants = 'bcdfghjklmnpqrstvwxz';
SET @u_consonants = UPPER(@l_consonants);

INSERT
INTO    t_names(id, name)
SELECT  id,
        (
        SELECT  GROUP_CONCAT(
                IF(
                (slen - id) % 2 = 0,
                SUBSTR(IF(l.id = 1, @u_vowels, @l_vowels), FLOOR(RAND(20090508 << 2) * LENGTH(@l_vowels) + 1), 1), 
                SUBSTR(IF(l.id = 1, @u_consonants, @l_consonants), FLOOR(RAND(20090508 << 3) * LENGTH(@l_consonants) + 1), 1)
                )
                ORDER BY l.id
                SEPARATOR '')
        FROM    (
                SELECT  *
                FROM    filler
                LIMIT 20
                ) l
        WHERE   l.id <= slen
        )
FROM    (
        SELECT  id,
                RAND(20090508) AS rnd,
                FLOOR(RAND(20090508 << 1) * 10) + 4 AS slen
        FROM    filler
        ) q;

Now, there is a nice simple query to do this:

SELECT  DISTINCT(SUBSTRING(name, 1, 1))
FROM    t_names

This query, however, cannot use the indexes and, thus, is quite iinefficient: it runs for 1600 ms.

To make it more efficient, we need to uses indexes. Actually, we just need to jump from the first index key to key starting with a letter next to the given, and so on. Thus, will will visit only one index leaf per letter.

Unfortunately, MySQL does not allow using indexes on condtions like SUBSTRING(name, 1, 1), despite the fact that only first letters matter in this case.

That's why we'll need to emulate this behavior.

The query we are going to use will perform the following steps:

1. The query will use the table itself (t_names) as a dummy rowsource (i. e. only for generating a set of rows, ignoring the values)
2. A session variable will be assigned with a code of the first letter of current MIN(name)
3. On each row in the dummy rowset, the variable will be assigned with a new value: the code of the letter next to the current one in the table.
4. As soon nothing more is returned, the query should be stopped

Due to the bug in MySQL, range access method is never being chosen for a correlated subquery if the range condition comes from the outside.

To work around this, we will need to create a function, which, given a code of a letter, returns the code of the letter next to the given one.

Here's the function:

CREATE FUNCTION fn_get_next_code(initial INT) RETURNS INT
NOT DETERMINISTIC
READS SQL DATA
BEGIN
DECLARE _next VARCHAR(200);
DECLARE EXIT HANDLER FOR NOT FOUND RETURN NULL;
SELECT  ORD(SUBSTRING(name, 1, 1))
INTO    _next
FROM    t_names
WHERE   name >= CHAR(initial + 1)
ORDER BY
name
LIMIT 1;
RETURN _next;
END

, and here's the query:

SELECT  current
FROM    (
SELECT  CHAR(@r) AS current,
@r := fn_get_next_code(@r)
FROM    (
SELECT  @r := ORD(SUBSTRING(MIN(name), 1, 1))
FROM    t_names
) vars,
(
SELECT  1
FROM  t_names
LIMIT 100
) q
WHERE   @r IS NOT NULL
) qo

The query is now instant (4 ms).

This, of course, pays for itself only when choosing first value a very large dataset (similar to one described above). On smaller dataset, DISTINCT is almost instant too.

But since DISTINCT uses filesort which is quite memory- and CPU-intensive, this approach may be useful even for smaller datasets in a highly-concurrent environment.