select lento - between

Pessoal, tenho uma tabela com logs de atividades, que vem acumulando registros ao longo de vários anos. Hoje são mais de 150 milhões de registros.

O que ocorre é que existe um sistema que permite gerar relatórios por período, mas a consulta por data é extremamente exaustiva, chegando a levar horas para imprimir um relatório as vezes não muito extenso... 1 ou 2 mil registros.

A linha que uso para trazer esse relatório é:

SELECT * FROM tb_historico WHERE ClientID = "& ClientID &" AND UserID = "& UserID &" AND str_to_date(data, '%d/%m/%Y') BETWEEN '"& IniData &"' AND '"& FimData &"'

A tabela é InnoDB e possui índices para os campos ClientID, UserID e Data.

Alguém tem alguma idéia de como melhorar a performance dessa consulta?