Собственно по сабжу, кто чем пользуется, с учетом что 4-5КК записей (поле от 5 до 30 символов), и нужно возвращать первые 10-100 отсортированных результатов в приемлемые сроки, то есть очень быстро, поиск идет только по первым 2-5 символам.
ну сделай "партиционирование" по первым двум символам, разнеси по поисковым таблицам.
не модно наверное, но иногда может оказаться действенным, если данные окажутся более-менее равномерно распределенными.