Re: [GENERAL] Backwards index scan

Tom Lane <tgl@sss.pgh.pa.us> writes:
> Dmitry Tkach <dmitry@openratings.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