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@vmware.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