Mysql cobrindo vs composto vs índice de coluna

Um índice de cobertura não é o mesmo que um índice composto.

Se eu tiver 2 índices separados um em col3 e outro em col4, qual deles será usado nesta consulta?

O índice com a maior cardinalidade.
MySQL mantém estatísticas sobre qual índice tem quais propriedades.
O índice que tem o maior poder de discriminação (como fica evidente nas estatísticas do MySQL) será usado.

Li em algum lugar que para cada tabela na consulta apenas um índice é usado. Isso significa que não há como a consulta usar os dois índices?

Você pode usar uma subseleção.
Ou melhor ainda usar um índice composto que inclui col3 e col4.

Em segundo lugar, se eu criar um índice composto usando col3 e col4 juntos, mas usado apenas col3 na cláusula WHERE, isso será pior para o desempenho? exemplo:

Índice composto
O termo correto é compound índice, não composto.
Somente o mais à esquerda parte do índice composto será usado.
Então, se o índice for definido como

index myindex (col3, col4)  <<-- will work with your example.
index myindex (col4, col3)  <<-- will not work.

Veja:http://dev.mysql.com /doc/refman/5.0/en/multiple-column-indexes.html

Observe que, se você selecionar um campo mais à esquerda, poderá não usar essa parte do índice em sua cláusula where.
Imagine que temos um índice composto

Myindex(col1,col2)

SELECT col1 FROM table1 WHERE col2 = 200  <<-- will use index, but not efficiently
SELECT * FROM table1 where col2 = 200     <<-- will NOT use index.

A razão pela qual isso funciona é que a primeira consulta usa o índice de cobertura e faz uma varredura nele.
A segunda consulta precisa acessar a tabela e, por esse motivo, a varredura do índice não faz sentido.
Isso só funciona no InnoDB.

O que é um índice de cobertura
Um índice de cobertura refere-se ao caso em que todos os campos selecionados em uma consulta são covered por um índice, nesse caso o InnoDB (não o MyISAM) nunca lerá os dados na tabela, mas apenas usará os dados no índice, acelerando significativamente o select.
Observe que no InnoDB a chave primária está incluída em todos os índices secundários, então de certa forma todos os índices secundários são índices compostos.
Isso significa que se você executar a seguinte consulta no InnoDB:

SELECT indexed_field FROM table1 WHERE pk = something

~~O MySQL sempre usará um índice de cobertura e não acessará a tabela real.~~ Embora possa usar um índice de cobertura, ele preferirá a PRIMARY KEY porque ele só precisa atingir uma única linha.