Brain dump: btree collapsing

I've been thinking hard for the last few days about how to do space
reclamation in b-tree indexes, i.e., recycle pages that are in
no-longer-useful portions of the tree structure. We know we need this to
solve the "index bloat" problem that occurs when the distribution of keys
changes over time. I feel that it's critical that the reclamation be doable
by plain VACUUM, ie, without acquiring exclusive lock on the index as a
whole. This discussion therefore assumes that page deletion must be able
to operate in parallel with insertions and searches.

Issues
------

We need to get rid of parent links in btree pages; otherwise removal of a
non-leaf page implies we must find and update all parent links that lead
to it. This is messy enough that it would be better to do without. The
only thing the parent link is really needed for is to find the new parent
level after a root split, and we can handle that (very infrequent) case by
re-descending from the new root.

Instead of storing parent links, label all pages with level (counting
levels up from zero = leaf, so that a page's level doesn't change in a
root split). Then, if we find ourselves needing to re-descend, we can be
sure of finding the correct parent level, one above where we were, even if
there's been multiple root splits meanwhile. The level will also make for
a useful cross-check on link validity: we will always know the level of
the page we expect to arrive at when following a link, so we can check
that the page has the right level.

Unfortunately this means tossing out most of the FixBtree code Vadim wrote
2 years ago, because it seems critically dependent on having parent links.
But I don't really see why we need it if we rely on WAL to maintain btree
consistency. That will require some improvements in WAL-logging for
btrees, however. (Details below.)

When a page is deleted, it can't actually be recycled until there are no
more potentially in-flight references to it (ie, readers that intend to
visit the page but have not yet acquired a lock on it). Those readers
must be able to find the page, realize it's dead, and follow the correct
sidelink from it. [Lanin&Shasha86] describe the "drain technique", which
they define as "delay freeing the empty page until the termination of all
processes whose locate phase began when pointers to the page still
existed". We can conveniently implement this by reference to
transactions: after removing all links to the page, label the now-dead
page with the current contents of the next-transaction-ID counter. VACUUM
can recycle the page when this is older than the oldest open transaction.

Instead of an actively maintained freelist on disk as per Alvaro Herrera's
patch, I plan to use the FSM to remember where recyclable pages are, much
as we do for tables. The FSM space requirements would be small, since
we'd not be needing to enter any data about partially-full pages; only
truly empty, recyclable pages would need to be stored. (Is it worth
having an alternate representation in the FSM for indexes, so that we only
store page numbers and not the useless amount-free statistic?)

Without a freelist on disk, VACUUM would need to scan indexes linearly to
find dead pages, but that seems okay; I'm thinking of doing that anyway to
look for empty pages to turn into dead ones.

Restructuring the tree during page deletion
-------------------------------------------

We will delete only completely-empty pages. If we were to merge nearly-empty
pages by moving data items from one page to an adjacent one, this would
imply changing the parent's idea of the bounding key between them ---
which is okay if we are just deleting an internal key in the parent, but
what if the pages have different parent pages? We'd have to adjust the
parents' own bounding key, meaning the parents' parent changes, perhaps
all the way to the root. (Not to mention that with variable-size keys,
there's no guarantee we can make such changes without splitting the
upper-level pages.) And, since we support both forward and backward
index scans, we can't move leaf items in either direction without risking
having a concurrent scan miss them. This is way too messy, especially for
something that has only minimal return according to the literature
[Johnson89]. So, no merging.

Deletion of an empty page only requires removal of the parent's item
linking to it (plus fixing side pointers, which is pretty trivial). We
also remove the next higher key in the parent, which is the parent's upper
bound for data that would have belonged on the target page. Therefore,
the page's right sibling becomes responsible for storing the key range
that used to belong on the deleted page.

What if there is no next-higher key, you ask? Well, I'm going to punt.
It is critical that the key space associated with a parent page match the key
space associated with its children (eg, the high key of the rightmost child
must match the parent's high key). There is no way to atomically modify a
parent's key space --- this would mean simultaneously changing keys in upper
levels, perhaps all the way up to the root. To avoid needing to do that, we
must put a couple of restrictions on deletion:

1. The rightmost page in any tree level is never deleted, period. (This rule
also simplifies traversal algorithms, as we'll see below.)

2. The rightmost child of a non-rightmost parent page can't be deleted, either,
unless it is the last child of that parent. If it is the last child then the
parent is *immediately* marked as half-dead, meaning it can never acquire any
new children; its key space implicitly transfers to its right sibling. (The
parent can then be deleted in a later, separate atomic action. Note that if
the parent is itself a rightmost child of a non-rightmost parent, it will have
to stay in the half-dead state until it becomes the only child; then it can be
deleted and its parent becomes half-dead.)

(Note that while leaf pages can be empty and still alive, upper pages
can't: they must have children to delegate their key range to.)

With these restrictions, there is no need to alter the "high key" fields of
either the parent or the siblings of a page being deleted. The key space of
the page itself transfers to its right sibling, and the key space of the
parent does not change (except in the case where the parent loses all its key
space to its right sibling and becomes half-dead).

Restriction 1 is not a significant one in terms of space wastage. Restriction
2 is more annoying, but it should not increase overhead drastically. The
parent would not be deleted or merged anyway as long as it has other children,
so the worst-case overhead from this restriction is one extra page per
parent page --- and parent levels are normally much smaller than child levels.

The notion of a half-dead page means that the key space relationship between
the half-dead page's level and its parent's level may be a little out of
whack: key space that appears to belong to the half-dead page's parent on the
parent level may really belong to its right sibling. We can tolerate this,
however, because insertions and deletions on upper tree levels are always
done by reference to child page numbers, not keys. The only cost is that
searches may sometimes descend to the half-dead page and then have to move
right, rather than going directly to the sibling page.

Page deletion procedure
-----------------------

Assume we know the target page, but hold no locks. The locks must be
gotten in this order to avoid deadlock against inserters:

1. Obtain W lock on left sibling of target page (this may require searching
right if left sibling splits concurrently; same as for backwards scan case).
Skip this if target is leftmost.
2. Obtain super-exclusive lock on target page; check it is still empty,
else abandon deletion.
3. Obtain W lock on right sibling (there must be one, else we can't delete).
4. Find and W-lock the target's current parent page. Check that target is
not rightmost child of a parent with other children, else abandon deletion.
5. Update all four pages at once, write single WAL record describing all
updates. (I believe we can extend WAL to allow 4 page references in a
single record, if not it may be okay to cheat and not store all of the
adjacent pages. Certainly need not record contents of the target page
itself, so 3 is enough.) Note parent is marked half-dead here if this
was its last child. Release locks.
6. The update to the target page makes it empty and marked dead, but preserves
its sibling links. It can't actually be recycled until later (see above).

The deletion procedure could be triggered immediately upon removal of the
last item in a page, or when the next VACUUM scan finds an empty page.
Not sure yet which way is better.

Having to exclusive-lock four pages is annoying, but I think we must do
this procedure as a single atomic operation to ensure consistency.

Search/scan rules in presence of deletion
-----------------------------------------

Since page deletion takes a superexclusive lock, a stopped scan will never
find the page it's on deleted when it resumes. What we do have to worry about
is arriving at a dead page after following a link. There are several cases:

During initial search for a key, if arrive at a dead or half-dead page, chain
right. (The key space must have moved to the right.)

During forward scan: likewise chain right. (Note: because scans operate
only on the leaf level, they should never see half-dead pages.)

During backwards scan: chain right until a live page is found, and step left
from there in the usual way. We cannot use the dead page's left-link because
its left neighbor may have split since the page was deleted. (There is
certain to be at least one live page to the right, since we never delete the
rightmost page of a level.)
Also, "step left in the usual way" used to mean this:
A backwards scan has one additional bit of complexity: after
following the left-link we must account for the possibility that the
left sibling page got split before we could read it. So, we have to
move right until we find a page whose right-link matches the page we
came from.
But if the "page we came from" is now dead, perhaps there is no
page with a matching right-link (if updater got to it before we did)!
Probably the best policy, if we fail to find a match, is to return to
the page we were previously on, verify that it's now dead (else error),
then chain right and left as in the case where we've linked to a dead page
(see above). This means a backwards scan must always remember the last
live page it was on. Again, this is greatly simplified by the fact that
there must be a live page somewhere to the right.

Insertion changes
-----------------

The basic insertion algorithm doesn't change (but see above notes about
the search part).

bt_getstackbuf is a little trickier in the presence of deletion. First
issue is that removal of an earlier downlink in the returned-to parent
page may cause the target item to move left by some number of slots
(though not into a previous page). We can deal with this by searching
left after we fail to find the item by searching right, before we move on
to the next page. Next is that the whole parent page may be dead or
half-dead --- but it can't be physically deleted, so we can recover by
following its rightlink. The nasty part is that the target item could
perhaps not be there; this would imply that someone deleted the page we
are trying to split, or hasn't fully finished inserting it. But L&Y
already require holding a lock on that page until we have re-located and
locked the parent item, so this is not possible. (Note this implies that
we must search for exactly the downlink to the page we are splitting, but
that's true anyway.)

If we need to split on a level that was the root when we descended, but
is no longer the root, then our stack doesn't tell us how to find the next
level up. As discussed above, handle this case by re-descending and
checking level fields, rather than depending on parent links as before.
We will simply descend on the left edge of the tree and scan the whole
parent level to find where to insert --- it's highly unlikely that the
parent level has yet grown large enough for this to be slow, so there's
not much value in trying to use a keyed search.

WAL issues
----------

A page split operation can't really be atomic. We can handle the actual split
("half-split") operation as an atomic update:

1. We have W lock on page that needs to be split.
2. Find a free page (from FSM, or make it by extending rel), W-lock it.
3. W-lock page's right sibling (if any), so that we can fix its left-link.
4. Update all three pages, make WAL log entry describing same, write pages.
5. We can now release the W-lock on the right sibling page, but we must keep
the W-locks on the two split pages until we have made the parent entry;
else it's conceivable for someone else to try to split or delete these
pages and get confused because the parent link isn't in place yet.
(See L&Y.)

(Note that since this is driven by an insert, the half-split WAL log entry
may as well include the new key insertion step; so this entry substitutes
for the plain insertion WAL entry we'd otherwise make.)

(So far this is the same as the existing code.)

But now we must find the parent page and enter the new key and downlink
(possibly causing a split at that level). If crash occurs before we can
do so, how to recover? The existing code has a lot of ad-hoc logic that
tries to reconstruct the tree on-the-fly when inconsistency is detected.
But it would be a lot better if we could expect WAL playback to fix things.

The WAL entry describing the half-split includes enough info to re-execute
the parent key insertion. While replaying log, we can remember this
insertion as pending. If we see a matching insertion event in the log,
discard the remembered pending insertion. At end of log, execute all
still-pending insertions. (There should not be very many pending
insertions at any one time, so the resources for this are not onerous.)
Note however that this implies making more log entries to describe these
additional updates; might complicate WAL, but I see no fundamental
difficulty.

Also, if we are splitting a root page, it seems best to merge creation of
the new root page and updating of the metapage into the same atomic action
that does the split. This won't make the WAL entry materially larger, and
it will avoid problems with concurrent root splits. Need to look at
deadlock issues for trying to update metapage --- is it okay to grab W
lock on meta while holding it on old root? (Sure, why not? Nothing will
go the other way.) We do need to update metapage as part of the atomic
root-split operation, else other updaters trying to find the new root may
fail because link not there yet.

VACUUM mechanics
----------------

We will institute an explicit "vacuuming an index" phase in VACUUM (this
is distinct from deleting index entries during vacuuming of a table, and
will be done after we've finished vacuuming the associated table). In
this phase, we can scan the index linearly (ie, in storage order not
index order) to take advantage of sequential I/O optimizations. We scan
looking for pages that are empty (if leaf pages) or half-dead (if parent
pages), as well as pages that are already dead and have been so long
enough to be recycled. The latter are simply reported to the FSM.
Empty and half-dead pages are deleted per the previously-described
mechanism. (It seems best to gather the page IDs of target pages in
memory, and do the deletions only after we've finished the seqscan, so
as not to confuse the kernel about whether it should read-ahead.)

One step that's not explicit above is how to find the parent of a page we
intend to delete. It seems most efficient to perform a search for the
page's high key (it must have one, since we don't delete rightmost pages)
stopping when we reach the level above the page itself. This will give
us a good pointer to the parent. We should do this before starting to
acquire exclusive locks for the deletion.

In theory, if we find recyclable page(s) at the physical end of the index,
we could truncate the file (ie, give the space back to the filesystem)
instead of reporting these pages to FSM. I am not sure if this is worth
doing --- in most cases it's likely that little space can be released this
way, and there may be some tricky locking issues.

Tree depth
----------

Because we never relabel pages' levels, the tree depth cannot be reduced (we'd
have to do that by removing the current root page, which seems impractical
without an exclusive lock on the whole index). So after massive shrinkage
we could end up with a "thin" tree in which there are levels below the root
with only one page apiece. The space wastage doesn't seem like a big issue,
but the extra time to traverse these useless levels could be annoying.

This could be ignored in first implementation (there's always REINDEX).
Later, possibly handle it via Lanin&Shasha's notion of a critic (think
VACUUM) that sets a fast pointer to the current effective root level.
(Actually I think we wouldn't need a separate critic process; split and
delete steps could be programmed to update the fast pointer for
themselves, in a separate atomic action, when they split a one-page level
or delete the next-to-last page of a level.)

Any comments before I plunge into implementing this?

regards, tom lane