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

On 09/11/2014 11:47 PM, Peter Geoghegan wrote:
> On Tue, Sep 9, 2014 at 12:01 AM, Heikki Linnakangas
> <hlinnakangas(at)vmware(dot)com> wrote:
>>> + Although it could be argued that Lehman and Yao isn't followed to the
>>> + letter because single pages are read locked as the tree is descended,
>>> + this is at least necessary to support deletion, a common requirement
>>> + which L&Y hardly acknowledge. Read locks also ensure that B-tree
>>> + pages are self-consistent (L&Y appear to assume atomic page reads and
>>> + writes).
>>
>> This is just duplicating the existing paragraph. I don't see the point of
>> this.
>
> The point is to make clear the reason for the differences - evidently,
> Amit felt it was unclear why we don't follow L&Y. I am suggesting that
> L&Y's talk of having no read locks is unrealistic (it might be
> realistic in the 21st century, but that's a whole other story).

IMHO the existing paragraph does a much better job explaining that:

> Lehman and Yao don't require read locks, but assume that in-memory
> copies of tree pages are unshared. Postgres shares in-memory buffers
> among backends. As a result, we do page-level read locking on btree
> pages in order to guarantee that no record is modified while we are
> examining it.

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?

- Heikki