How to find string that completely matches total or part of input

I will like to write a query to search a table containing millions of records for a value that totally and best matches the search string or its substring only from the beginning. Performance is of most importance.

It’s like a reverse of:

SELECT * FROM table_name WHERE column_name LIKE '$input%' LIMIT 1

As an example, I will like to search the table below for foobar. If foobar doesn’t exist, search for fooba until the last character f and return the row with a total match.

+------------------+
|    column_name   |
+------------------+
|    foobar        |
+------------------+
|    fooba         |
+------------------+
|    foob          |
+------------------+
|    foo           |
+------------------+
|    fo            |
+------------------+
|    foobarrrrr    |
+------------------+
|    foooooooooooo |
+------------------+
|    barfoo        |
+------------------+

Answer

You can use the column value to construct a LIKE pattern dynamically.

SELECT column_name
FROM table_name
WHERE 'foobar' LIKE CONCAT(column_name, '%')
ORDER BY LENGTH(column_name) DESC
LIMIT 1

Note that this will be slow if the table is large, as I don’t think it can make use of an index. If that’s a problem, building the query dynamically would better.