Я бы в отдельную таблицу забил названия всех производителей.
При анализе названия товара, полученного от клиенты, сначала определяем производителя путём поочередного поиска вхождения в анализируемую строку названий производителей. Потом уже загружаем из базы все тавары этого производителя и поочередно сравниваем той же levenshtein(), но уже не 20 000 раз. Конечно, при условии, что клиенты всегда указывают производителя в названии товара. Еще можно отфильтровать по виду товара (моб. телефон, ноутбук и т.д.), если их указывают клиенты, как и с производителем.
Как альтернатива levenshtein() - такой вариант: для каждого товара вручную выделить части, которые обязательно будут в названии (например в мобильном телефоне samsung e830 обязательно будет присутствовать e830) и искать в анализируемых названиях товаров эти части. Это можно даже SQL-запросом сделать (LIKE, только не поле таблицы сравнивается с шаблоном, а наоборот), с фильтром по производителю, чтоб mySQL тоже не сравнивал все 20 000 записей