Как оптимизировать запрос с выборкой «равно значению одного из 2х полей»?

Есть табличка с полями С1 и С2, нужно вынуть строки где одно из этих полей соответствует заданному номеру.

Делаю запрос

select m.* from my_table m  where  (m.C1 = 123 or m.C2 =123)  and  (m.foo='bar')

этот запрос выполняется 4 сек (800 тыс строк)

Если я убираю одно из полей из запроса

select m.* from my_table m  where  m.C1 = 123  and  (m.foo='bar')

менее 0.1 сек.

По Explain понятно, что в во втором случае используется индекс, в первом - перебор. Пробовал общий индекс - не помогает. Понятно, что можно объединить 2 запроса через UNION или соединить результаты выборок после, в PHP. Но может есть более изящный способ?
MySQL 5.5.38