Claro que se hará lento .. como toda Base de datos cuanto más datos tiene .. más se le hace pesado buscar en ella.
Ahora ya depende de que optimices tu Base de datos, tus tablas .. que crees indices .. etc. Si vas a buscar en campos de "texto" para eso tienes también de forma más optima las busquedas tipo "FULL TEXT" (texto completo) de Mysql ..
Revisa estos tutoriales (que no tienen nada que ver con PHP sino con tu BBDD):
http://www.mysql-hispano.org/page.php?id=29 http://www.mysql-hispano.org/page.php?id=15
Un saludo,
PD: Esto parece "pin-pon" .. intenta hacer la pregunta en un tema concreto no lo hagas en varios aunque "salgas" de una respuesta anterior.