Re: GIN indexscans versus equality selectivity estimation

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> On Mon, Jan 10, 2011 at 10:25 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)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