В mysql ищи по теме LIKE, там можно легко сделать аналог *?
* - любое кол-во символов
? - один символ.
Базу лучше как-то по умному разбить и пользоваться кешированием. А то миллионы номеров гонять трудновато))

Вообще когда-то такое делал, правда очень давно. Исходники потерялись.
Проблемы и примерно как это делалось писал тут https://forum.antichat.ru/threadnav11882-1-10.html