Seu estilo é muito incomum.

A maioria das pessoas provavelmente escreveria WHERE began_at < NOW() AND finished_at > NOW()

No entanto. Eu recomendaria colocar um índice em ambos os campos.

Uma chave combinada não será útil para você porque só aceleraria o buscador para combinações de datas específicas.

Bem, isso não é totalmente verdade, porque se você usar betree uma chave combinada irá ajudá-lo, mas não tão bom quanto se você indexá-las separadamente. Chaves combinadas são muito boas se você pesquisar combinações de campos com operador de igualdade (=). Índices de campo único têm melhor desempenho em solicitações de intervalo.

Você pode pesquisar um pouco no Google por "pesquisa de intervalo multidimensional".

A razão é que todos os campos correspondentes em um campo podem ser encontrados basicamente no tempo log(n) em btrees.

As consultas de intervalo multidimensional têm um tempo de execução de O(sqrt(n)), que é maior. No entanto, existem implementações melhores que também atingem o tempo de execução logarítmico. No entanto, elas não são totalmente implementadas no mysql, então será pior ou terrível dependendo da versão.

Então deixe-me resumir:

• 
  Comparações de igualdade em campos únicos:índice de hash (tempo de execução O(1))
  
• 
  Pesquisa de intervalo em campos únicos:índice btree em campos únicos ( O(log(n)) )
  
• 
  Pesquisa de igualdade em vários campos:chave de hash combinada (tempo de execução O(1))
  

esses casos são uma coisa clara...

• Pesquisa de intervalo em vários campos:índices btree separados ( O(log(n)) )

este é o lugar onde não é tão claro. com as versões atuais é claramente melhor indexar separadamente por causa das razões dadas acima. você precisa para isso) desde a versão 5.0, mas apenas muito limitado e o otimizador de consultas os utiliza apenas em casos raros afaik. não sei sobre as versões mais recentes como 5.3 ou algo assim.

no entanto, com o mysql implementando índices soltos, chaves combinadas em campos onde você faz solicitações de intervalo ou ordenação em diferentes direções tornam-se cada vez mais relevantes.