Re: [GENERAL] Backwards index scan

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:
> Dmitry Tkach <dmitry(at)openratings(dot)com> writes:
>> 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.

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

> 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.

I have committed a fix into 7.5devel to do this properly. I think this
is the last case wherein btree is unnecessarily inefficient for large
numbers of equal keys.

regards, tom lane