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

On Fri, Sep 12, 2014 at 2:45 PM, Heikki Linnakangas <hlinnakangas(at)vmware(dot)com>
wrote:
>
> 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?

Yeah, I have noticed and even discussed in this thread that
it might be better to add new text after that paragraph.

> 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?

The paragraph is quite clear to me and the only thing, I have
mentioned above is that if you (Peter) want to add anything
new in that regard, then it is about an additional point why
read locks are taken during traversal of tree which is something
he is trying to say in his new patch as below:
"this is at least necessary to support deletion,"

However it could have been added in the existing text as well.

Having said that, I think that was just a very minor thing which is
generally obvious and was not at all the main feedback for patch.
The main point was to explain about how does "right-links at all
levels and high-key" helps to detect and recover from concurrent
page splits which I think the patch has tried to explain, but honestly
the wording you have posted (under heading
"The basic Lehman & Yao Algorithm
================================") is more clear to me.

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