Запрос:

SELECT d.id, d.ip, d.p, d.uid, d.cat, d.region, d.date_add, d.user_id, d.status, d.email, d.user, d.title, d.text, d.f_94 images, d.active, d.counter, d.date_del, d.nosend, d.subdomain ,(SELECT count(1) 
FROM site_comments WHERE message_id = d.id) comments_count FROM site_db as d WHERE status = 1 AND catfull like 'Zhivotnye-pticy-ryby-tovary-dlya-zhivotnyh%' ORDER by raised desc, date_add desc LIMIT 78360, 30 

где ststus - int1
catfull - varchar
date_add - int11

ALTER TABLE `dbname`.`site_db` ADD INDEX `status_catfull_urifull` (`status`, `catfull`, `date_add`) USING BTREE;

Первая проблема в составном индексе, если задать индекс вида status+catfull+date_add используется только статус, почемуто составной индекс не работает, из него берется только первое значение.

Вторая проблема в сартировке. Вышеуказаный запрос с выполняется примерно 1,5 - 2,5 секунды. Если его выполнить без сартировки то он выполнится примерно за 0,007 сек.

Попробуй поиграть с планом выполнения (EXPLAIN). Например, я не уверен, что тебе нужен составной индекс на три поля.

_____________

echo '<pre>',print_r($var, 1);die;

root@server# make love && war

Структура индекса малоэффективна, покрыть запрос индексом врят ли удастся как ни крути. Если сортировки нельзя избежать, то лучше попробовать покрутить размеры буфера сортировки СУБД.
P.S. Данный индекс в помойку.

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