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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
