rakot

Попробуйте составной ключ checked, taken, task_id. Именно в таком порядке, может помочь. А вообще какая таблица InnoDB?

Храните сессии в Redis

ALTER TABLE `table` ADD INDEX ( ` A`) — этот бесполезен, т.к. вместо него можно использовать ALTER TABLE `table` ADD INDEX ( ` A,B,C`) или ALTER TABLE `table` ADD INDEX ( ` A,C,D`), а вообще вы занимаетесь преждевременной оптимизацией.

Возникает пара вопросов, кто вам настраивал MySQL и какой тип таблиц вы используете?

Всё же навскидку могу сказать, что память уходит скорее всего из-за скортировок по неключевым полям. MySQL выделяет память под сортировку на каждое соединение, по умолчанию 8 мегабайт, память выделяется как только приходит запрос с сортировкой, причем выделяется сразу вся порция внезависимости от того, надо вам 100кб под данную операцию или все 8 мегабайт.

Во время нагрузки посмотрите SHOW FULL PROCESSLIST.
По сложным запросам посмотрите EXPLAIN.

Несколько стратегий:
1. Добавлять ключи для выборок и сортировок, если это приемлимо и их еще нет.
2. Увеличивать шансы на попадание запросов в кеш MySQL.
3. Кешировать данные на уровне приложения.
4. Перенести некоторые операции на уровнь приложения.