Dmitry T.

Пробовали ли использовать разные IO планировщики?
Если есть свап на сервере, сколько страниц mysql в свапе? Попробовали провести тест с выключенным свапом?

Используйте SQL_CALC_FOUND_ROWS при селекте с лимитом, MySQL посчитает все записи подходящие под параметры.

SELECT SQL_CALC_FOUND_ROWS * FROM TABLE1 WHERE .... LIMIT 40;
SELECT FOUND_ROWS()

SELECT GET_LOCK('GET_MY_ID', 10);
BEGIN;
SELECT @id_to_update:=`id` FROM `table` ORDER BY `last_use` LIMIT 1;
UPDATE `table` SET `last_use` = NOW() WHERE `id` = @id_to_update;
COMMIT;
SELECT RELASE_LOCK('GET_MY_ID');

Если ID не пересекаются, то просто делайте INSERT INTO SELECT. Счетчик автоинкримента увеличиться сам и будет больше чем значение самого большого PK.

CREATE TABLE `t1` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `date` datetime(6) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

insert into t1 values (null, now());
insert into t1 values (null, now());
insert into t1 values (null, now());
insert into t1 values (null, now());
insert into t1 values (null, now());
insert into t1 values (null, now());

show create table t1;
| t1    | CREATE TABLE `t1` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `date` datetime(6) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=7 DEFAULT CHARSET=utf8 |

> insert into t1 values (25, now());

> show create table t1;
| t1    | CREATE TABLE `t1` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `date` datetime(6) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=26 DEFAULT CHARSET=utf8 |

Если PK int.

select min(id),max(id) from table where ... ; // если данные меняются не часто можно кешировать значения
$rand = get_rand($min_id, $max_id);
select * from table where id => $rand and ... limit 1;

одним запросом это сильно «дорого» :(
лучше сделать скрипт который каждые сутки будет делать

insert into stat_table select date_sub(current_date, 1), sum(sum) from table where date < current_date;

create table stat_table (
 to_day date,
 big_sum int,
 primary key(to_day)
)

либо если уж совсем хочется делать все динамически тогда можно попробовать вот такую красоту:

set @prev_day_sum:=0;
select
    day, 
    @prev_day_sum:=d_sum + @prev_day_sum as sum_from_month_begin, 
    d_sum 
from
    (select 
        date(date) as day, 
        sum(sum) as d_sum
    from 
        table 
    group by 
        day;
    ) as day_sum; 

day — день
sum_from_month_begin — сумма от начала месяца
d_sum — за конкретный день

В какой-то момент пришли к использованию Sphinx, а дальше все проще, большая часть запросов к данным идет по PK. Вся выборка и поиск идет через Sphinx.
Индекс не содержит данных с флагом deleted.

Если вы хотите использовать только БД, то можно сделать тригер.
Будет удалять все записи из таблицы старше 2х месяцев.

delimiter //
CREATE TRIGGER ins_logtable AFTER INSERT ON logtable
FOR EACH ROW
BEGIN
    SELECT NOW() - interval 2 month INTO @rotate_date;
    DELETE FROM logtable WHERE added_date < @rotate_date;
END;//
delimiter ;

Этот тригер будет выполнятся при каждом INSERT в таблицу и удалять все из таблицы старше 2-х месяцев.
Хотя я бы сделал все же скрипт запускаемый по крону, т.к. чистка через тригер может повлиять на производительность. :(