Борьба с базой данных MySQL номеров телефона

Мое приложение хочет сохранить список международного телефонного номера в mysql базе данных. Затем приложение должно было бы запросить базу данных и искать определенное число. Звучит простым, но это - на самом деле огромная проблема.

Поскольку пользователи могут искать то число в другом формате, мы должны будем сделать полное сканирование к базе данных каждый раз.

Например. Нам можно было бы сохранить номер 17162225555 в базе данных (наряду с еще 5 миллионами записей). Теперь пользователь приезжает и попытка искать использование 7162225555. Другой пользователь мог бы попытаться искать с 2225555. и т.д. и т.д. Так, другими словами, база данных должны выпустить SQL-запрос с помощью "как %number %", который привел бы к полному сканированию.

Как мы должны разработать это приложение? Там некоторый путь состоит в том, чтобы написать о Mysql в Твиттере для обработки этого лучше? Или разве мы не должны использовать SQL вообще?

PS. У нас есть миллионы записей, и 10-е их поисковый запрос в секунду.