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