Which Composite Index would make this simple MySQL query faster?

Question

Which Composite Index would make this simple MySQL query faster, and how would I create that Composite Index?

SELECT * 
FROM  `Table1` 
WHERE  `col1` =  '145307'
AND  `col2` =  '0'
AND col3 NOT 
IN ( 130209, 130839 ) 
ORDER BY col4 DESC 
LIMIT 0 , 5

There is already an individual index on each column above (col1 to col4).

---

EDIT:

Results of SHOW CREATE TABLE:

CREATE TABLE `Table1` (  
 `primaryCol` int(11) NOT NULL AUTO_INCREMENT,
 `col3` int(11) DEFAULT '0',
 `col5` varchar(20) COLLATE utf8_bin DEFAULT NULL,
 `col1` int(11) DEFAULT '0',
 `col6` varchar(80) COLLATE utf8_bin DEFAULT NULL,
 `col7` text CHARACTER SET utf8,
 `col4` int(11) DEFAULT '0',
 `col8` char(1) COLLATE utf8_bin DEFAULT 'N',
 `col9` char(1) COLLATE utf8_bin DEFAULT 'N',
 `col2` tinyint(1) NOT NULL,
 `col10` tinyint(1) NOT NULL,
 `col11` smallint(6) NOT NULL,
 PRIMARY KEY (`primaryCol`),
 KEY `col5` (`col5`),
 KEY `col1` (`col1`),
 KEY `col3` (`col3`),
 KEY `col4` (`col4`),
 KEY `col8` (`col8`),
 KEY `col9` (`col9`),
 KEY `CompIndex1` (`col1`,`col8`,`col4`),
 KEY `col2` (`col2`),
 KEY `col10` (`col10`),
 KEY `col11` (`col11`),
 FULLTEXT KEY `col7` (`col7`)
) ENGINE=MyISAM AUTO_INCREMENT=4575350 DEFAULT CHARSET=utf8 COLLATE=utf8_bin

Results of EXPLAIN EXTENDED:

id  select_type table   type    possible_keys   key key_len ref rows    filtered    Extra
1   SIMPLE  Table1  ref col1,col3,CompIndex1,col2   CompIndex1  5   const   226 100 Using where; Using filesort

Answer 1

I would suggest an index on (col1, col2, col3).

mysql> CREATE INDEX NewIndex ON Table1 (col1,col2,col3);

mysql> EXPLAIN SELECT *  FROM  `Table1`  WHERE  `col1` =  '145307' 
AND  `col2` =  '0' AND col3 NOT  IN ( 130209, 130839 )  
ORDER BY col4 DESC  LIMIT 0 , 5\G

           id: 1
  select_type: SIMPLE
        table: Table1
         type: ref
possible_keys: col1,col3,CompIndex1,col2,NewIndex
          key: NewIndex
      key_len: 6
          ref: const,const
         rows: 1
        Extra: Using where; Using filesort

Your condition on col3 is not an equality comparison, it's a range comparison, and that should be the last column in the index.

Unfortunately, this means that you can't get rid of the "using filesort" in the EXPLAIN plan. In general, you can't optimizing sorting with indexes if you also have a range comparison on a different column.

But you can at least use the three-column index to narrow down the search so the filesort will have to do work on a smaller set of rows, and then it'll probably be able to do it in memory.

See also my presentation How to Design Indexes, Really.