shagguboy

вот такой индекс. если будет сильно большой, или селективность у полей сильно разная, можно ограничится самым селективным полем.
CREATE INDEX idx1 ON doctors (name_first, name_last)
запрос с OR индексы не использует, надо переписать на UNION

покажите explain и ddl таблиц с индексами

а расскажите характеристики сервера, раз вам одного ящика не хватает

хранить в вертикальной таблице — EAV. индекс нужен будет всего один. перейти на innodb и сделать его первичным ключем, чтобы сэкономить место.

переходите наконец на bind параметры. кроме отсутствия вот таких проблем в плюс еще не будет повторного разбора запроса при каждом выполении.