Re: [GENERAL] Backwards index scan

[ reply redirected to a more appropriate list ]

Dmitry Tkach <dmitry(at)openratings(dot)com> writes:
> I am not sure if this is really a bug, but it certainly looks like one
> to me...

It's not a bug, but I agree that _bt_first can be inefficient if there
are lots of matching keys.

> This is because there are *lots* (a few million) of matches for x=10,
> and _bt_first () scans through them *all* sequentually to get to the
> last one.
> I understand that with the generic approach to operators in postgres it
> is, probably, not very feasible to try and teach _bt_first () to handle
> this situation automatically (it would need to know how to get
> next/previous value for every indexable type)...

I think what we'd want is variant versions of _bt_search and _bt_binsrch
that locate the first entry greater than the specified target key,
rather than the first entry greater than or equal to it. Given such
positioning, all the _bt_first cases that involve stepping over more
than one entry could be improved to require no more than one step.

Not sure whether it'd be better to make clone versions of these
functions, or to add a parameter to tell them which behavior is wanted.

regards, tom lane