Re: Stating the significance of Lehman & Yao in the nbtree README

On Wed, Jul 23, 2014 at 5:58 AM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> On Mon, Jul 21, 2014 at 9:55 PM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com>
wrote:
> > The above indicates 2 things:
> > a. L & Y doesn't need to hold read locks concurrently.
> > b. Advantage of right-links at all levels and "high-key".
> >
> > As per my understanding, we are not following point (a) in our code,
> > so what is the benefit we get by having a reference of same in README?
>
> The major reason that we don't completely avoid read locks, is, I
> suppose, the need for self-consistent pages (but also because it would
> break page deletion - I'm pretty sure that L&Y don't consider page
> deletion, and the page deletion logic is entirely based on the Lanin
> and Shasha paper and original research, but I didn't check). I think
> that the sentence "Lehman and Yao don't require read locks, but assume
> that in-memory copies of tree pages are unshared" is intended to
> convey the point on the self-consistency of pages. Of course, Lehman
> and Yao must assume that the B-Tree is in some sense in shared memory.
> Otherwise, there wouldn't be much point to their elaborate locking
> protocol. :-)

Okay, but how does this justify to add below new text in README.
+ Even with these read locks, Lehman and Yao's approach obviates the
+ need of earlier schemes to hold multiple read locks concurrently when
+ descending the tree as part of servicing index scans (pessimistic lock
+ coupling).

Actually I think putting it can lead to inconsistency in the README.
Currently it indicates that our algorithm is different from L&Y w.r.t taking
Read Locks and has given explanation for same.

> > Isn't it better if we mention how the point (b) is used in our code and
> > it's advantage together rather than keeping it at top of README?
>
> Maybe it deserves more prominent mention in the code too.
>
> > Already README mentions in brief about right-link and how it is used
> > as below:
> > ".. The scan must remember the page's right-link at the time it was
scanned,
> > since that is the page to move right to; if we move right to the current
> > right-link then we'd re-scan any items moved by a page split. ..."
>
> This is talking about how index scans interlock against VACUUM while
> going to the heap, by keeping a leaf page pinned (this prevents "super
> exclusive lock" acquisition). This is after the tree has been
> descended. This is really just a detail (albeit one that follows
> similar principles, since pages split right and it similarly exploits
> that fact), whereas the use of right links and high keys while
> descending the tree, and in particular the fact that the "move right"
> L&Y technique obviates the prior need for "lock coupling" is pretty
> much the whole point of L&Y.
>
> In more concrete terms, _bt_search() releases and only then acquires
> read locks during a descent of the tree (by calling
> _bt_relandgetbuf()), and, perhaps counterintuitively, that's just
> fine.

So don't you think that it needs bit more explanation than you have
quoted in below text.
+ The addition of right-links at all levels, as well as the
+ addition of a page "high key" allows detection of, and dynamic
+ recovery from concurrent page splits (that is, splits between
+ unlocking an internal page, and subsequently locking its child page
+ during a descent).

Basically I think it will be better if you can explain in bit more detail
that
how does "right-links at all levels and high-key" helps to detect and
recover from concurrent page splits.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com