Во-первых, юзай индекс. Он будет работать при полном совпадении или поиске по началу.
Во-вторых, от like %phone% можно отказаться если у тебя разные поиски. Он ищет любое вхождение. Лучше заменить отдельно на:
`phone` like "000" полное.
`phone` like "000%" по началу .
`phone` like "%000" по концу - делает фулскан, не оптимизируется индексами
Оптимизировать поиск по концу можно добавив столбцы:
1, 2, 3, 4, 5 (сколько надо), цифр с конца, с соответствующими индексами,и уже на уровне приложения искать полным равенством по нужному столбцу