pgsql: Add some randomness to the choice of which GiST page to insert t

Add some randomness to the choice of which GiST page to insert to.

When descending the tree for an insert, and there are multiple equally good
pages we could insert to, make the choice in random. Previously, we would
always choose the tuple with lowest offset number. That meant that when two
non-leaf pages overlap - in the extreme case they might have exactly the same
key - all but the first such page went unused. That wasn't optimal for space
usage; if you deleted some tuples from the non-first pages, the space would
never be reused.

With this patch, the other pages are sometimes chosen too, although there's
still a heavy bias towards low-offset tuples, so that we don't lose cache
locality when doing a lot of inserts with similar keys.

Original idea by Alexander Korotkov, although this patch version was written
by me and copy-edited by Tom Lane.

Branch
------
master

Details
-------
http://git.postgresql.org/pg/commitdiff/ba1cc6501e98aee7d43098b032d6656f243bca5b

Modified Files
--------------
src/backend/access/gist/gistutil.c | 66 +++++++++++++++++++++++++++++++++--
1 files changed, 62 insertions(+), 4 deletions(-)