Corner cases with GiST n-way splits

GiST page splitting has the peculiarity that it sometimes needs to split
a single page into more than two pages. It happens rarely in practice,
but it possible (*). With a bad picksplit function, it happens more often.

While testing with a custom gist opclass with truly evil helper
functions, I found two corner cases with the current implementation when
a page is split into many halves:

1. If a page is split into more than 100 pages, you run into the same
limit of 100 simultaneous lwlocks that Tom Forbes reported with a
pathological intarray index. This time it's not because we hold locks on
many different levels, but because of a single split.

2. When the root page is split, there is no parent page to update, so we
just create a new root page with the downlinks. However, when you split
a page into a lot of siblings, it's possible that all the downlinks
don't fit on a single page. The code is prepared for that situation. You
get an error, when it tries to add more downlinks on a single page than
fit there.

I'm not sure what to do about these. Neither issue is something you'd
actually bump into in an index that's doing something useful; there's
been no user complaints about these.

(*) What follows is an explanation of how a page can be split into more
than two halves, to help you (and me!) understand this:

In a very pathological case, it's possible for a single insertion to
cause a page to be split into hundreds of pages. Imagine that you have a
page full of very small tuples (let's imagine that a page can hold 8
letters, and ignore all tuple overhead for now):

A B C D E F G H

Now you insert one large tuple on the page, DDDD. picksplit algorithm
can choose to split this as:

A - B C D E F G H DDDD

The right side is still too large to on a single page, so it's
iteratively split again:

A - B - C D E F G H DDDD

And again:

A - B - C - D E F G H DDDD

And again:

A - B - C - D - E F G H DDDD

In this example, the page was split into 5 halves, but in reality a page
can hold many more tuples, and the difference between a small and a
large tuple can be much greater, so you can end up with many more
siblings in one split.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com