Для обычных запросов 2000 строк - ничто - даже без индекса это будет очень быстро, поскольку вся таблица может быть кэширована в памяти. 100000 строк также должны работать нормально в большинстве ситуаций, хотя, если у вас нет подходящих индексов или ваши запросы не используют доступные индексы, вы уже заметите это - запросы, которые должны занимать секунды, могут занять минуты, если они не используют индексы правильно. Но это не займет много времени, чтобы решить проблему - запустите EXPLAIN для вашего медленного запроса и посмотрите, почему он медленный, и выясните, какие индексы вам нужны.
К тому времени, когда вы доберетесь до миллионов строк или десятков миллионов строк, вам придется более тщательно продумывать свой дизайн базы данных и свою стратегию индексирования. Если вы все делаете правильно, в таблице могут быть сотни миллионов строк.