Re: Performance optimization of btree binary search

On Wed, Dec 4, 2013 at 5:28 PM, Peter Geoghegan <pg@heroku.com> wrote:
> I'm also curious about the impact on insertion into primary key
> indexes. Presently, we hold an exclusive buffer lock for the duration
> of a couple of operations when checkUnique != UNIQUE_CHECK_NO.
> _bt_binsrch() is one such operation. The other one there,
> _bt_check_unique(), is likely to be a lot cheaper than _bt_binsrch()
> on average, I think, so I'm cautiously optimistic that it'll be
> noticeable. I better go and check it out.

Depending on how well this goes, I might also teach _bt_doinsert() to
hint to _bt_binsrch() (or as I'm calling it, _bt_page_search()) that
it should look to the end of the page when searching, using a similar
mechanism to the mechanism for hinting that the main Datum-compare
optimization is applicable (this strategy would be abandoned if it
didn't work immediately - as soon as the last item on the page turned
out to be greater than or equal to the scankey value). This is
something that I think would help with SERIAL columns, where it's
possible in principle to pass that kind of insight around -- if you
can live with making SERIAL more than mere syntactic sugar.

-- 
Peter Geoghegan