Re: Race condition in b-tree page deletion

On 09.11.2013 19:18, Heikki Linnakangas wrote:
> On 09.11.2013 18:49, Heikki Linnakangas wrote:
>> We could just punt if more than X pages would need to be changed. That
>> would mean that we never delete pages at the top (h - X) levels of the
>> tree. In practice that should be fine if X is high enough.
>> As a data point, GIN list page deletion holds 16 pages locked at once
>> (GIN_NDELETE_AT_ONCE). Normally, a 16-level deep B-tree is pretty huge.
>> As another data point, in the worst case the keys are so wide that only
>> 2 keys fit on each B-tree page. With that assumption, the tree can be at
>> most 32 levels deep if you just insert into it with no deletions, since
>> MaxBlockNumber ~= 2^32 (I may be off by one in either direction, not
>> sure). Deletions make it more complicated, but I would be pretty
>> surprised if you can construct a B-tree tallers than, say 40 levels.
>
> On further thought, it's worse than that. To delete a page, you need to
> lock the left and right siblings, so you need 3 pages locked per each
> level you delete...

On further further thought, we don't need to unlink the pages
immediately. It's enough to mark them as half-dead and remove the
downlink to the upmost half-dead page. Marking a page as half-dead is as
good as deleting it outright as far as searches and insertions are
concerned. Actually unlinking the pages from the left and right siblings
can be done at any later time, and doesn't need to be done in any
particular order.

So, my original musings about the number of concurrent locks needed
still holds.

- Heikki