Re: btree split logic is fragile in the presence of lar ge index items

"Mikheev, Vadim" <vmikheev(at)SECTORBASE(dot)COM> writes:
>> Currently the page contains the leftmost key is the target page of
>> insertion and is locked exclusively but it may be different in extra
>> TID implementation. There may be a very rare deadlock possibility.

> But anyway while we hold lock on a page we are able to go right
> and lock pages (and we do this now). There is no possibility for
> deadlock here: backward scans always unlock page before reading/locking
> left page.

Readers can only hold one page read lock at a time (they unlock before
trying to lock next page). Writers can hold more than one page lock
at a time, but they always step in the same direction (right or up)
so no deadlock is possible. It looks fine to me.

I have been studying the btree code all day today and finally understand
that the equal-key performance problems don't really have anything to do
with the Lehman-Yao assumption of no equal keys. The L-Y algorithm
really only needs unique keys so that a writer who's split a page can
return to the parent page and find the right place to insert the link
for the new righthand page. As Vadim says, you can use the downlinks
themselves to determine which entry is for the page you split; at worst
you have to do some linear instead of binary search when there are lots
of equal keys. That should be OK, since we only have to do this when we
split a page.

I believe that the equal-key performance problem largely comes from the
bogus way we've been handling duplicates, in particular the fact that
findsplitloc has to worry about choosing a "legal split point" for a
series of duplicates. Once we get rid of that, I think findsplitloc
can use a binary search.

regards, tom lane