SELECT COUNT(*) FROM `user`

Если будет 100000 записей в таблице, сколько займет времени данный запрос?
Или можно как-то по другому подсчитать кол-во строк в таблице БД?

100000 - это не так уж и много. Выполнится ОЧЕНЬ быстро. Беспокоиться не о чем.

_____________
Mysql, Postgresql, Redis, Memcached, Unit Testing, CI, Kohana, Yii, Phalcon, Zend Framework, Joomla, Open Cart, Ymaps, VK Api