I've moved this to the hackers list, and added Teodor and Alexander of the bloom extension, as I would like to hear their opinions on the costing.
My previous patch had accidentally included a couple lines of a different thing I was working on (memory leak, now-committed), so this patch removes that diff.
I'm adding it to the commitfest targeting v13. I'm more interested in feedback on the conceptual issues rather than stylistic ones, as I would probably merge the two functions together before proposing something to actually be committed.
Should we be trying to estimate the false positive rate and charging cpu_tuple_cost and cpu_operator_cost the IO costs for visiting the table to recheck and reject those? I don't think other index types do that, and I'm inclined to think the burden should be on the user not to create silly indexes that produce an overwhelming number of false positives.