1. Тег "Оптимизация SQL-запросов", значит у тебя СУБД? Какая?
2. Ты придумал себе проблему на ровном месте, 5 миллионов не сильно много, можно поднять тестовый стенд и проверить как будет работать без индексов, потом добавить индекс по умолчанию
3. Если поиск по полному номеру, то практически любой индекс будет работать очень быстро, если по подстроке, то начинается куча нюансов, тут уже надо отталкиваться от user story
4. Если не устраивает, то читаешь какие виды индекса есть у данной СУБД, экспериментируешь, смотришь планы запросов, оптимизируешь и т.п