From: | Heikki Linnakangas <hlinnakangas(at)vmware(dot)com> |
---|---|
To: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
Cc: | pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: Race condition in b-tree page deletion |
Date: | 2013-11-09 17:18:10 |
Message-ID: | 527E6E52.5060402@vmware.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
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...
- Heikki
From | Date | Subject | |
---|---|---|---|
Next Message | Heikki Linnakangas | 2013-11-09 17:40:29 | Re: Race condition in b-tree page deletion |
Previous Message | Heikki Linnakangas | 2013-11-09 16:49:00 | Re: Race condition in b-tree page deletion |