I have a table with over 5 million rows and two indexed fields that are foreign keys.

But the query time is absurdly high when I try to search in the two fields at the same time.

MySQL [db]> select count(*) from table1 where (fk_1 IN (1303,0)); +----------+ | count(*) | +----------+ |   175693 | +----------+ 1 row in set (0.09 sec)  MySQL [db]> select count(*) from table1 where (fk_1 IN (1303,0) OR fk_2 IN (123,0)); +----------+ | count(*) | +----------+ |   175693 | +----------+ 1 row in set (1 min 45.62 sec) 

And I add a third condition, over another indexed field, which is not a FK, it becomes even worse.

MySQL [db]> select count(*) from table1 where (fk_1 IN (1303,0) OR fk_2 IN (123,0)) AND field_1 IS NULL; +----------+ | count(*) | +----------+ |     2867 | +----------+ 1 row in set (3 min 32.41 sec) 

am I missing something? Or this is the normal behaviour? Is there a way to improve this?

This conditions can vary and include or not the second condition (the field_1).