Re: GIN indexscans versus equality selectivity estimation

Robert Haas <robertmhaas@gmail.com> writes:
> On Mon, Jan 10, 2011 at 10:25 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I'm currently
>> leaning to the idea of tweaking the logic in indxpath.c; in particular,
>> why wouldn't it be a good idea to force consideration of the bitmap path
>> if the index type hasn't got amgettuple? �If we don't, then we've
>> completely wasted the effort spent up to that point inside
>> find_usable_indexes.

> I guess the obvious question is: why wouldn't it be a good idea to
> force consideration of the bitmap path even if the index type DOES
> have amgettuple?

Well, the motivation is what the code comment said: not to waste time
uselessly considering the bitmap form of an indexscan whose only reason
to live was to produce output sorted in a particular way.  That's
irrelevant for GIN of course, but it's entirely relevant for btree.

It might be just useless over-optimization, but I don't think so --
choose_bitmap_and is O(N^2) in the number of paths submitted to it,
so adding a lot of uninteresting paths doesn't seem smart.

A small variant of the approach would be to only reject paths that have
non-empty pathkeys.  That's not a *sufficient* condition, because a path
could have both pathkeys and good selectivity --- but it could be added
onto the selectivity test.
        regards, tom lane