sortmem_grow-v4.patch

diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index ce27e40..a97e3b1 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -957,14 +957,18 @@ tuplesort_end(Tuplesortstate *state)
  * Grow the memtuples[] array, if possible within our memory constraint.
  * Return TRUE if able to enlarge the array, FALSE if not.
  *
- * At each increment we double the size of the array.  When we are short
- * on memory we could consider smaller increases, but because availMem
- * moves around with tuple addition/removal, this might result in thrashing.
- * Small increases in the array size are likely to be pretty inefficient.
+ * At each increment we double the size of the array.  When we are short on
+ * memory we do attempt one last, smaller increase.  This only happens at most
+ * once, since availMem moves around with tuple addition/removal. To do othewise
+ * might result in thrashing.  This is nothing more than a last-ditch effort to
+ * avoid exceeding allowedMem, an undesirable outcome if avoidable.
  */
 static bool
 grow_memtuples(Tuplesortstate *state)
 {
+	int			newmemtupsize;
+	long		memNowUsed = state->allowedMem - state->availMem;
+
 	/*
 	 * We need to be sure that we do not cause LACKMEM to become true, else
 	 * the space management algorithm will go nuts.  We assume here that the
@@ -974,18 +978,50 @@ grow_memtuples(Tuplesortstate *state)
 	 * enough to force palloc to treat it as a separate chunk, so this
 	 * assumption should be good.  But let's check it.)
 	 */
-	if (state->availMem <= (long) (state->memtupsize * sizeof(SortTuple)))
-		return false;
+	if (memNowUsed <= state->availMem)
+		newmemtupsize = state->memtupsize * 2;
+	else
+	{
+		int			memtupsize = state->memtupsize;
+		long		allowedMem = state->allowedMem;
+
+		/*
+		 * For this last increment, abandon doubling strategy.
+		 *
+		 * To make sure LACKMEM(state) doesn't become true, we can't increase
+		 * memtupsize by more than state->availMem/sizeof(SortTuple) elements.
+		 * In practice, we want to increase it by considerably less, because
+		 * we need to leave some space for the tuples to which the new array
+		 * slots will refer.  We assume the new tuples will be about the same
+		 * size as the tuples we've already seen, and thus use the known size
+		 * (in bytes) of the tuples seen so far to estimate an appropriate new
+		 * size for the memtuples array.  The optimal value might be higher or
+		 * lower than we estimate, but it's hard to know that in advance.
+		 *
+		 * In any case, we're definitely safe against enlarging the array so
+		 * much that LACKMEM(state) becomes true, because the memory currently
+		 * used includes the present array; thus, there would be enough
+		 * allowedMem for the new array elements even if no other memory were
+		 * currently used.
+		 */
+		newmemtupsize = memtupsize * allowedMem / memNowUsed;
+
+		Assert(newmemtupsize <= state->memtupsize * 2);
+
+		/* This may not be our first time through */
+		if (newmemtupsize <= memtupsize)
+			return false;
+	}
 
 	/*
 	 * On a 64-bit machine, allowedMem could be high enough to get us into
 	 * trouble with MaxAllocSize, too.
 	 */
-	if ((Size) (state->memtupsize * 2) >= MaxAllocSize / sizeof(SortTuple))
+	if ((Size) (newmemtupsize) >= MaxAllocSize / sizeof(SortTuple))
 		return false;
 
 	FREEMEM(state, GetMemoryChunkSpace(state->memtuples));
-	state->memtupsize *= 2;
+	state->memtupsize = newmemtupsize;
 	state->memtuples = (SortTuple *)
 		repalloc(state->memtuples,
 				 state->memtupsize * sizeof(SortTuple));