Walking a BTREE index as far as possible in MySQL
If you really want to walk just the b-tree index, using the innodb_ruby project can help
http://blog.jcole.us/2013/01/14/efficiently-traversing-innodb-btrees-with-the-page-directory/



I think your logic is reversed in your query. It'll start with the shortest word.

How I would handle it is this

DROP PROCEDURE IF EXISTS `find_longest_prefix`;

DELIMITER $$

CREATE PROCEDURE `find_longest_prefix`(IN `word` varchar(255), OUT `word_prefix` varchar(255))
BEGIN
    SET max_sp_recursion_depth = 255;
    SET @nextWord = LEFT(`word`, LENGTH(`word`)-1);

    SELECT COUNT(DISTINCT `words`) FROM `myTABLE` WHERE `words` LIKE CONCAT(`word`, '%') INTO @word_count;

    IF (@word_count &gt; 0)
    THEN
        SET `word_prefix` = `word`;
    ELSE
        IF (LENGTH(@nextWord) &gt; 0)
        THEN
            Call `find_longest_prefix`(@nextWord, `word_prefix`);
        ELSE
            SET `word_prefix` = '';
        END IF;
    END IF;
END$$

DELIMITER ;


This uses the fact that finding a miss on a btree is fast so we just loop around calling recursively until we have a hit.

Examples

No results

mysql&gt; CALL find_longest_prefix(';autobon', @prefix);
Query OK, 1 row affected (0.01 sec)

mysql&gt; SELECT @prefix;
+---------+
| @prefix |
+---------+
|         |
+---------+
1 row in set (0.00 sec)


A few results

mysql&gt; CALL find_longest_prefix('autobon', @prefix);
Query OK, 1 row affected (0.00 sec)

mysql&gt; SELECT @prefix;
+---------+
| @prefix |
+---------+
| auto    |
+---------+
1 row in set (0.00 sec)


And as you can see, the data is correct:

mysql&gt; SELECT * FROM myTable WHERE words LIKE 'auto%' OR words LIKE ';auto%';
+----+-----------------+
| id | words           |
+----+-----------------+
| 19 | AUTOCOMMIT      |
| 20 | AUTOEXTEND_SIZE |
+----+-----------------+
2 rows in set (0.00 sec)


This method should be much faster then actually checking every step before the longest and getting a lot more returned data.

It should be easy for you to have the stored proc SELECT the rows once it finds the correct prefix and return them if you'd prefer.