Как часто есть смысл перестраивать индексы и обновлять статистику на таблицах в БД?

Никто Вам точно не скажет - зависит от нагрузки на БД (удаления/создания записей), структуры БД, объёма данных.
Вообще иногда делать стоит. Н-р перестройка индексов может привести к серьезному росту производительности в больших базах.
Для кучи посмотрите ещё OPTIMIZE TABLE (если речь идет про MySQL) - иногда наиболее полезно =) Есс-но сначала стоит посмотреть фрагментацию таблицы.

P.S:
У нас н-р есть довольно большая база (в режиме 24/7/365 =) - раз в год где-то перестраиваю индексы в самых нагруженных таблицах и перемещаю эти таблицы (у Oracle есть проблемы с дефрагментацией таблиц) - разница весьма ощутима.