Indices work best when the number of matching entries is low. There is a metric called index selectivity which is the number of distinct values of the indexed columns divided by the total number of records. For a boolean value, this would be 2/N records, effectively the worst possible index. For a perfect index, it would be 1 (every row has a unique entry in the index). It could be possible for the query planner to get the answer wrong for which index to use if it happens to be wrong about the selectivity of your particular query, because the selectivity must be approximated.
See for example PostgreSQL's (a fantastic database) documentation on these approximations and imagine a number of ways it could fail [1].
> Assuming a linear distribution of values inside each bucket, [...]
> This amounts to assuming that the fraction of the column that is not any of the MCVs is evenly distributed among all the other distinct values.
> Using some rather cheesy assumptions about the frequency of different characters
See for example PostgreSQL's (a fantastic database) documentation on these approximations and imagine a number of ways it could fail [1].
> Assuming a linear distribution of values inside each bucket, [...]
> This amounts to assuming that the fraction of the column that is not any of the MCVs is evenly distributed among all the other distinct values.
> Using some rather cheesy assumptions about the frequency of different characters
[1] https://www.postgresql.org/docs/current/row-estimation-examp...