From: | Peter Geoghegan <pg(at)heroku(dot)com> |
---|---|
To: | Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> |
Cc: | Pg Hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: Stating the significance of Lehman & Yao in the nbtree README |
Date: | 2014-09-07 02:58:08 |
Message-ID: | CAM3SWZTqGXPW+3SWnXx62RMHYNkY1y9AOKeeHsLUSVKurB_8oA@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
On Tue, Jul 22, 2014 at 10:49 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
>> 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.
>
> You might be right about that - perhaps I should go into more detail.
I've gone into more detail on what a high key is, and how we arguably
do not follow Lehman & Yao to the letter because we still have read
locks. L&Y's assumption of atomic page reads/writes, and cursory
handling of deletion kind of make it inevitable that read locks are
used, which I now imply. So nbtree isn't a substandard L&Y
implementation - it's a realistic one, which only needs to hold a
single read lock at a time when servicing index scans (or when finding
a place for insertion). I guess Lehman & Yao preferred to put forward
the claim "no read locks" rather than "only one read lock at a time on
internal pages, even for insertion" because there might be some uses
of their algorithm where that is actually realistic. It is really a
sympathetic way of spinning things to say that *no* read locks are
used, though.
--
Peter Geoghegan
Attachment | Content-Type | Size |
---|---|---|
btree-ly-readme.2014_09_06.patch | text/x-patch | 3.8 KB |
From | Date | Subject | |
---|---|---|---|
Next Message | Tom Lane | 2014-09-07 03:40:02 | Re: Patch for psql History Display on MacOSX |
Previous Message | David E. Wheeler | 2014-09-07 01:23:44 | Re: jsonb format is pessimal for toast compression |