SQL syntax nuances make a big difference. I have a table defined this way (details omitted for brevity):

create table stripe (
  stripeid     int not null primary key,
  all_healthy  boolean not null default true,
  enough_online  boolean not null default true,
  in_batch   boolean not null default false
);

I also have an index on this table:

create index stripe_schedule_helper on stripe (all_healthy, enough_online, in_batch);

The following query takes a long time because it performs a sequential scan on the whole table.

select stripeid from stripe
where not all_healthy and enough_online and not in_batch

The following query returns the same results but takes a tiny fraction of the time of the above query, because it uses the index:

select stripeid from stripe
where all_healthy = false and enough_online and in_batch = false

So, it turns out that the query optimizer perceives a major difference between the conditions "not x" and "x = false", even when x is a non-null boolean. I used 'explain analyze' to discover this. It's rather surprising, but at least there's a workaround.