нужен совет по оптимизации базы данных

[Андрей911]

В одном из моих приложений для соцсети, заметил, что при увеличении размера таблицы в БД mysql с данными пользователей от 500 тыс до 4.5 миллионов записей время выборки для одинаковых запросов увеличивается с 0,1 до 4 секунд.
Вопрос - время выборки из БД зависит от количества записей в таблице или же от количества записей всей БД?
Если разбить таблицу на 10 таблиц, то это поможет уменьшить время запроса или же надо по нескольким базам информацию раскидывать?
Хочу так сделать в первой все uid начинаются с 0, во второй с 1, и т.д. до 9.