Slow query with multiple where and order by clauses

Question

I'm trying to find a way to speed up a slow (filesort) MySQL query.

Tables:

categories (id, lft, rgt)
questions (id, category_id, created_at, votes_up, votes_down)

Example query:

SELECT * FROM questions q 
INNER JOIN categories c ON (c.id = q.category_id)
WHERE c.lft > 1 AND c.rgt < 100
ORDER BY q.created_at DESC, q.votes_up DESC, q.votes_down ASC
LIMIT 4000, 20

If I remove the ORDER BY clause, it's fast. I know MySQL doesn't like both DESC and ASC orders in the same clause, so I tried adding a composite (created_at, votes_up) index to the questions table and removed q.votes_down ASC from the ORDER BY clause. That didn't help and it seems that the WHERE clause gets in the way here because it filters by columns from another (categories) table. However, even if it worked, it wouldn't be quite right since I do need the q.votes_down ASC condition.

What are good strategies to improve performance in this case? I'd rather avoid restructuring the tables, if possible.

EDIT:

CREATE TABLE `categories` (
  `id` int(11) NOT NULL auto_increment,
  `lft` int(11) NOT NULL,
  `rgt` int(11) NOT NULL,
  PRIMARY KEY  (`id`),
  KEY `lft_idx` (`lft`),
  KEY `rgt_idx` (`rgt`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

CREATE TABLE `questions` (
  `id` int(11) NOT NULL auto_increment,
  `category_id` int(11) NOT NULL,
  `votes_up` int(11) NOT NULL default '0',
  `votes_down` int(11) NOT NULL default '0',
  `created_at` datetime NOT NULL,
  PRIMARY KEY  (`id`),
  KEY `questions_FI_1` (`category_id`),
  KEY `votes_up_idx` (`votes_up`),
  KEY `votes_down_idx` (`votes_down`),
  KEY `created_at_idx` (`created_at`),
  CONSTRAINT `questions_FK_1` FOREIGN KEY (`category_id`) REFERENCES `categories` (`id`) ON DELETE CASCADE
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

id select_type table type   possible_keys           key     key_len ref                 rows  Extra
1  SIMPLE      q     ALL    questions_FI_1          NULL    NULL    NULL                31774 Using filesort
1  SIMPLE      c     eq_ref PRIMARY,lft_idx,rgt_idx PRIMARY 4       ttt.q.category_id 1       Using where

Answer 1

Try a subquery to get the desired categories:

SELECT * FROM questions 
WHERE category_id IN ( SELECT id FROM categories WHERE lft > 1 AND rgt < 100 )
ORDER BY created_at DESC, votes_up DESC, votes_down ASC
LIMIT 4000, 20