База может быть хоть сто терабайт размером, дело не в этом. Она-ж не в одной таблице, как я думаю. И запросы выборку не по всей базе делают. Дело в оптимизации структуры базы и запросов в ней. Некоторые нетипичные примеры, которые у меня тормозили сервер, правда mysql:
1. Создание многочисленных временных таблиц множеством пользователей
2. Одновременные многочисленные INSERTы и SELECTы на одну таблицу или связную совокупность таблиц
3. Одновременные многочисленные INSERTы на таблицу(ы) со сложными и объемными индексами
4. Блокировки на таблицу отдельными пользователями
Из типичных примеров:
1. Недостаточное индексирование
2. Различные типы(размеры) у связных ключей (например, у ключа - int, а у ссылки на него - bigint)
В любом случае, очень помогает анализ логов, а именно - анализ времени выполнения отдельных запросов. Если для этого есть инструментарий - хорошо, но в принципе, толковой головы и текстового редактора вполне достаточно.
Что-то еще посоветовать не могу, слишком мало исходной информации, схему БД не видел, логов запросов - тоже, о структуре индексов - не осведомлен.
P.S. Ах да, у Вас еще триггеры могут беспорядочно срабатывать и узкое место образовывать. Например, delete (insert) на каждой записи заставляет срабатывать триггер, который сохраняет данные удаляемой (вставляемой) записи в файл, по достижению определенного объема отправляемый по сетевому каналу связи конкурентам Вашей компании
. Шутка, конечно, но подобные узкие места могут тормозить всю систему, ведь во время дозаписи данных к файлу он для всех остальных блокируется.
P.P.S. Еще момент - если используется масса хранимых процедур, то дело наверняка в них. Вернее, дело в вышеизложенном, но генератором тормозов являются скорее всего они, прямо или косвенно. Например, вместо того, чтобы получить одним запросом полную информацию о некой сущности, осуществив выборку из нескольких таблиц, Вы вызываете хранимую процедуру, которую кто-то в свое время писал на коленке и которая генерирует множество запросов, выбирая из результатов нужную информацию, отбрасывая лишнюю и возвращая Вам тот-же результат, что Вы-бы получили единственным запросом, но за десятикратное время и стократное задействование ресурсов сервера.