Apenas para esclarecer várias outras respostas aqui, já que, na minha experiência, aqueles que analisam perguntas como essa estão no mesmo barco que nós, todos ouvimos que a indexação de campos booleanos é inútil e, no entanto ...

Temos uma tabela com cerca de 4 milhões de linhas, apenas cerca de 1000 por vez terão uma opção booleana sinalizada e é isso que procuramos. A adição de um índice em nosso campo booleano acelerou as consultas em ordens de magnitude, passou de cerca de 9+ segundos para uma fração de segundo.