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

On Fri, Sep 12, 2014 at 2:15 AM, Heikki Linnakangas
<hlinnakangas(at)vmware(dot)com> wrote:
> Amit: did you notice that paragraph in the README? If not, and now that you
> have read it, does that paragraph make things clear? If that's not enough,
> what do you think is missing?

Amit raised the fact that L&Y say that no read locks are required, so
clearly he read that paragraph. We don't try and justify that right
now, and trying to explain the whole point of L&Y without first
explaining this satisfactorily seems odd. The current text reads:

"""
Lehman and Yao don't require read locks, but assume that in-memory
copies of tree pages are unshared.
"""

If they assume that they're unshared, uh, then why bother with all
that locking stuff? Or does this mean that page reads and writes are
(dubiously) assumed atomic without locks? If you take a step back, you
can see how confusing that is. L&Y don't get around to explaining
this, but it's pretty clear that this is what's going on. If L&Y did a
better job of explaining their algorithm, they'd just say that the
"latch coupling" (coupling, or "crabbing", of what we'd call buffer
locks) previously required is no longer required, but single shared
locks are required. As I pointed out, it looks like someone figured
out a way to make that true much, much later [1]. I think page-level
MVCC designs might have also been used, but basically our
interpretation of L&Y is the standard one. We cannot really be
considered to have deviated from L&Y, since AFAICT everyone else went
with the same interpretation.

FWIW, in recent years Stonebraker has used "latch coupling" as an
example of the (implicitly no longer acceptable) overhead of designs
influenced by System R and ARIES. This is unfounded, but plenty of
bright people still at least believe that "latch coupling" is common.

[1] http://www.vldb.org/conf/2001/P181.pdf
--
Peter Geoghegan