Toss; it is totally redundant.
KEY `col1_index` (`col1`)
But, to speed up the query will take more serious surgery.
See how fast this runs. I don't know for sure that it will be faster.
SELECT col1
FROM (
SELECT col1 FROM tbl WHERE col2 = 'val1'
UNION ALL
SELECT col1 FROM tbl WHERE col2 = 'val2'
) x
GROUP BY col1
HAVING COUNT(*) = 2
Here's the logic...
* Each inner SELECT should be quite efficient because of INDEX(col2), plus the fact that InnoDB puts the PRIMARY KEY into each secondary key. That is, it is searching a BTree composed of (col2, col1) for col1='...'.
* No DISTINCT is needed in the inner SELECTs because we know (col1, col2) is unique, hence col2, col1 is unique.
* ALL and COUNT(*) (plus the requisite GROUP BY) are required so that we can discover which col1s show up in both subSELECTs
Why the original is not all that efficient --
* It will pick one of the col2s to start with.
* Then it will (efficiently, as above) find the col1s that match it.
* But now it has to probe the table again to see if there is a (col1, 'val2') pair in the table. By itself, this is quite efficient. But it is a random probe, so it is jumping around.
* Finally, there is an unnecessary (I think) DISTINCT pass. Please do EXPLAIN SELECT.
I'm curious to know what version of MySQL you are running. Later versions might try to use "index merge" on your SELECT. Does the EXPLAIN say so?
How much RAM do you have?
SHOW VARIABLES LIKE 'innodb_buffer_pool_size';
Consider making that variable 70% of available RAM.
Increasing the buffer pool might make your SELECT run tolerable fast, but I suspect mine may run fast even with a too-small buffer pool.