Otimizando a consulta do MySQL para evitar a varredura de muitas linhas

O que faz você pensar que a consulta examinará um grande número de linhas?

A consulta examinará exatamente 30 registros usando o UNIQUE indexe em tag (tag, article_id) , junte o artigo a cada registro em PRIMARY KEY E pare.

Isso é exatamente o que seu plano diz.

Acabei de fazer este script de teste:

CREATE TABLE `article` (
  `id` int(11) NOT NULL auto_increment,
  `title` varchar(60) NOT NULL,
  `time_stamp` int(11) NOT NULL,
  PRIMARY KEY  (`id`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8 AUTO_INCREMENT=1000001 ;

CREATE TABLE `tag` (
  `tag` varchar(30) NOT NULL,
  `article_id` int(11) NOT NULL,
  UNIQUE KEY `tag` (`tag`,`article_id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

INSERT
INTO    article
SELECT  id, CONCAT('Article ', id), UNIX_TIMESTAMP('2011-08-17' - INTERVAL id SECOND)
FROM    t_source;

INSERT
INTO    tag
SELECT  CASE fld WHEN 1 THEN CONCAT('tag', (id - 1) div 10 + 1) ELSE tag END AS tag, id
FROM    (
        SELECT  tag,
                id,
                FIELD(tag, 'Other', 'Acer', 'Sony', 'HP', 'Dell') AS fld,
                RAND(20110817) AS rnd
        FROM    (
                SELECT  'Other' AS tag
                UNION ALL
                SELECT  'Acer' AS tag
                UNION ALL
                SELECT  'Sony' AS tag
                UNION ALL
                SELECT  'HP' AS tag
                UNION ALL
                SELECT  'Dell' AS tag
                ) t
        JOIN    t_source
        ) q
WHERE   POWER(3, -fld) > rnd;

, onde t_source é uma tabela com 1M registros nele e execute sua consulta:

SELECT  *
FROM    tag t
JOIN    article a
ON      a.id = t.article_id
WHERE   t.tag = 'acer'
ORDER BY
        t.article_id DESC
LIMIT 30;

Foi instantâneo.