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.

Answer 2

If you're going to create a composite index, then it would be redundant to have indexes on individual columns which are members of the composite index. Figure out which queries you're going to most often run, the cardinality of each column involved in the queries, the approximate number of rows the queries will return, total rows in the table, is the table oftenly updated, etc. Remember that indexes cost against insertions and updates.

Answer 3

The current best answer is the most horrible one. Everytime you see a "filesort" in EXPLAIN, it's going to be horribly slow, because MySQL has to create temporary files and doesn't use the index for sorting!

Indexes are like phone books. In your case, the correct index would be:

(col4, col1, col2, col3, primaryCol)

The order matters! The leftmost part of your composite index must always be the columns that you want to order by. Then, add other columns that you use in your WHERE clause. Finally, for MyISAM, you need to add the primary key, too (InnoDB does that automatically).

Also, you need to change your query so the ordering/filtering, and getting full details, are seperated:

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

Checking this with EXPLAIN, you will see proper index usage, for the ordering and filtering. The result ids are then joined again with the table (in another fast index operation) to get the full details.