Postgresql で boolean のカラムにインデックスを付けてないと非常に遅くなる

boolean のカラムへのインデックスの追加は偏りが大きくなければ基本的にあまり変わらないと認識していたのですが、インデックスをはっていないと非常に(数百倍)遅くなる現象に遭遇しました。

Benchmark.measure{ Company.where(boolean_column_without_index: false).count }
#<Benchmark::Tms:0x00007fbf763319f8 @label="", @real=4.518864024430513, @cstime=0.0, @cutime=0.0, @stime=0.0, @utime=0.010000000000000675, @total=0.010000000000000675>
Benchmark.measure{ Company.where(boolean_column_with_index: false).count }
#<Benchmark::Tms:0x00007fbf75466130 @label="", @real=0.017290733754634857, @cstime=0.0, @cutime=0.0, @stime=0.0, @utime=0.009999999999999787, @total=0.009999999999999787>

DBはpsql (PostgreSQL) 9.6.9を使用しています。ローカル環境(9.6.3)では同じ内容のデータを使っても現象が再現しません。

Companyの件数は5000件ほどしかありません、falseが2,3割程度とそれほど方よりもありません。

とりあえずは必要なカラムにindexを追加することで対処したのですが、

何故このような状態に何故なってしまうのでしょうか？
またどうやって原因を調査すればよいですか？