gistchoose-2.patch

diff --git a/src/backend/access/gist/gistutil.c b/src/backend/access/gist/gistutil.c
index 8b60774..75778f6 100644
--- a/src/backend/access/gist/gistutil.c
+++ b/src/backend/access/gist/gistutil.c
@@ -379,6 +379,7 @@ gistchoose(Relation r, Page p, IndexTuple it,	/* it has compressed entry */
 	GISTENTRY	entry,
 				identry[INDEX_MAX_KEYS];
 	bool		isnull[INDEX_MAX_KEYS];
+	int			look_further_on_equal = -1;
 
 	Assert(!GistPageIsLeaf(p));
 
@@ -446,6 +447,8 @@ gistchoose(Relation r, Page p, IndexTuple it,	/* it has compressed entry */
 
 				if (j < r->rd_att->natts - 1)
 					best_penalty[j + 1] = -1;
+
+				look_further_on_equal = -1;
 			}
 			else if (best_penalty[j] == usize)
 			{
@@ -468,12 +471,46 @@ gistchoose(Relation r, Page p, IndexTuple it,	/* it has compressed entry */
 		}
 
 		/*
-		 * If we find a tuple with zero penalty for all columns, there's no
-		 * need to examine remaining tuples; just break out of the loop and
-		 * return it.
+		 * If we find a tuple that's exactly as good as the currently best
+		 * one, we could use either one. When inserting a lot of tuples with
+		 * the same or similar keys, it's preferable to descend down the same
+		 * path when possible, as that's more cache-friendly. On the other
+		 * hand, if all inserts land on the same leaf page, after a split,
+		 * we're never going to insert anything to the other half of the
+		 * split, and end up using only 50% of the available space.
+		 * Distributing the inserts evenly would lead to better usage, 75%,
+		 * but that destroys cache-locality. To get the best of both worlds,
+		 * when we find  a tuple that's equally good as the previous best, choose
+		 * whether to stick to the old best, or use the new one. Once we
+		 * decide to stick to the old best, we stick to that for any
+		 * subsequent equally good tuples we might find. This heavily favors
+		 * tuples with low offsets, but still allows some inserts to go to
+		 * other subtrees.
+		 */
+		if (j == r->rd_att->natts && result != i)
+		{
+			if (look_further_on_equal == -1)
+				look_further_on_equal = (random() <= (MAX_RANDOM_VALUE / 2)) ? 1 : 0;
+			if (look_further_on_equal == 1)
+			{
+				result = i;
+				look_further_on_equal = -1;
+			}
+		}
+
+		/*
+		 * If we find a tuple with zero penalty for all columns, and we've
+		 * decided we don't want to search for another tuple with equal
+		 * penalty, there's no need to examine remaining tuples; just break
+		 * out of the loop and return it.
 		 */
 		if (zero_penalty)
-			break;
+		{
+			if (look_further_on_equal == -1)
+				look_further_on_equal = (random() <= (MAX_RANDOM_VALUE / 2)) ? 1 : 0;
+			if (look_further_on_equal == 0)
+				break;
+		}
 	}
 
 	return result;