Status primeiro. O truque é, então, se você só precisa consultar por categoria, você pode.
SELECT * from table where status in (1,0) and category = 'whatever'
e ainda obter suporte de índice. Claro que se todas as suas consultas usarem ambas as colunas, é a mesma coisa, mas neste caso, se você usar apenas o status, é muito melhor, e apenas a categoria apenas um pouco pior, se for o caso.
Se você também estiver vendo muitas inserções, deseja minimizar o número de índices, portanto, essa é sua melhor aposta, em vez de ter vários índices.
