the bitmap heap scan is not bad

what is bad is that the bitmap is becoming lossy

here's how it works:

We scan an index, marking in a bitmap a '1' for every tuple (page+offset) that matches the conditional

those are 'exact' because it's a specific tuple

HOWEVER

the bitmap is only allowed to be "work_mem" size

SO, when we run out of space for 'exact' entries in the bitmap, we fall back to 'lossy'

that is- we make the bitmap be less specific

instead of a '1' meaning "this tuple", we say that a '1' means "this set of tuples", where that set can end up being as large as whole pages or possibly even more

and THEN we build another bitmap for the other index, doing the same thing

and then we AND those together

BUT- once we've got any lossy entries, we have to do a Recheck, because maybe index #1 had 'page 10, offset 5' and index #2 had 'page 10, offset 3', and that's it for page 10