Slow query searching for contribution amount & date range

We are seeing exceptionally slow performance on a large database doing contribution searches where only a small number of results are returned out of a large date range. The criteria is a combination of a date range and a minimum contribution amount and it turns out there is no index on contribution amount.

Also note this should ideally be removed from the query, as the join to the option_value table is not indexed by virtue of civicrm_option_value.value not being the same data type as civicrm_contribution.contribution_status_id

LEFT JOIN civicrm_option_group option_group_contribution_status ON (option_group_contribution_status.name = 'contribution_status')
LEFT JOIN civicrm_option_value contribution_status ON (civicrm_contribution.contribution_status_id = contribution_status.value
AND option_group_contribution_status.id = contribution_status.option_group_id )