WIP: Split of hash index bucket

I've read proposal [1] and also major part of thread [2]. [1] encouraged me to
try an alternative approach, which does not require flags at tuple
level. After thinking about it for some time, I decided to code something -
see attachment of this mail. (I was not sure whether I should write some kind
of pseudocode, but was too eager to try whether my idea works :-) )

The idea is that new bucket is initialized as an empty primary page, whose
'hasho_nextblkno' points at the first page of the "old bucket" (the one being
split). Then, tuples belonging to the new bucket are copied there and the link
at the end of the new bucket is redirected to the 2nd page of the old
bucket. And so on. When the last page of the old bucket is processed, the link
from the new to the old bucket is broken.

Any bucket participating in a split (whether the original one or the one being
created) has a flag on its primary page, so that its split-in-progress status
does not require access to the index metapage.

This logic should ensure that the split can be performed in small steps, w/o
blocking scans and inserts at bucket level (of course, contention still exists
at page level).

I'm still testing it. especially the concurrent access. There are probably
bugs in the code, but it can help understand what I mean.

If this split algorithm proves to be viable, an important question about the
role of bucket-level locks (implemented currently as "heavyweight" lock of the
bucket's primary page) remains.

(Note that "squeeze bucket" functionality is not implemented in this version.)

References:

[1] http://www.postgresql.org/message-id/CA+TgmoZyMoJSrFxHXQ06G8jhjXQcsKvDiHB_8z_7nc7hj7iHYQ@mail.gmail.com
[2]
http://www.postgresql.org/message-id/CA+TgmoY4X7VKyC4dAwujuTuBoyxE2qSJF9aybhWZjxXWoc6J8w@mail.gmail.co

--
Antonin Houska
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt
Web: http://www.postgresql-support.de, http://www.cybertec.at