Загугли "селективность". Нужно сделать индекс на колонку с наибольшей селективностью (отсекающую наибольшее количество записей). Или составной индекс на несколько таких колонок в порядке убывания селективности, но это иногда не дает большой эффективности, надо тестировать каждый конкретный случай.
Если "наборов условий" несколько, то возможно потребуется несколько индексов.
Плюс важно соблюдение баланса - увеличиваются затраты на вставку и используемое место (вплоть до того, что индексы занимают больше, чем сами данные). В отдельных случаях (под особо часто используемые и при этом ресурсоемкие запросы) можно создавать покрывающие индексы, когда к индексу добавляются колонки, участвующие в select. Для select * ,естественно, неприменимо.