On Wed, Jul 23, 2014 at 5:58 AM, Peter Geoghegan <p...@heroku.com> wrote: > On Mon, Jul 21, 2014 at 9:55 PM, Amit Kapila <amit.kapil...@gmail.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