Improve some O(N^2) behavior in window function evaluation.

Repositioning the tuplestore seek pointer in window_gettupleslot() turns
out to be a very significant expense when the window frame is sizable and
the frame end can move.  To fix, introduce a tuplestore function for
skipping an arbitrary number of tuples in one call, parallel to the one we
introduced for tuplesort objects in commit 8d65da1f.  This reduces the cost
of window_gettupleslot() to O(1) if the tuplestore has not spilled to disk.
As in the previous commit, I didn't try to do any real optimization of
tuplestore_skiptuples for the case where the tuplestore has spilled to
disk.  There is probably no practical way to get the cost to less than O(N)
anyway, but perhaps someone can think of something later.

Also fix PersistHoldablePortal() to make use of this API now that we have
it.

Based on a suggestion by Dean Rasheed, though this turns out not to look
much like his patch.

1 files changed, 43 insertions, 14 deletions

diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c
index 046637fb092..2fcc630a925 100644
--- a/src/backend/executor/nodeWindowAgg.c
+++ b/src/backend/executor/nodeWindowAgg.c
@@ -2371,31 +2371,56 @@ window_gettupleslot(WindowObject winobj, int64 pos, TupleTableSlot *slot)
 	tuplestore_select_read_pointer(winstate->buffer, winobj->readptr);
 
 	/*
-	 * There's no API to refetch the tuple at the current position. We have to
-	 * move one tuple forward, and then one backward.  (We don't do it the
-	 * other way because we might try to fetch the row before our mark, which
-	 * isn't allowed.)  XXX this case could stand to be optimized.
+	 * Advance or rewind until we are within one tuple of the one we want.
 	 */
-	if (winobj->seekpos == pos)
+	if (winobj->seekpos < pos - 1)
 	{
+		if (!tuplestore_skiptuples(winstate->buffer,
+								   pos - 1 - winobj->seekpos,
+								   true))
+			elog(ERROR, "unexpected end of tuplestore");
+		winobj->seekpos = pos - 1;
+	}
+	else if (winobj->seekpos > pos + 1)
+	{
+		if (!tuplestore_skiptuples(winstate->buffer,
+								   winobj->seekpos - (pos + 1),
+								   false))
+			elog(ERROR, "unexpected end of tuplestore");
+		winobj->seekpos = pos + 1;
+	}
+	else if (winobj->seekpos == pos)
+	{
+		/*
+		 * There's no API to refetch the tuple at the current position.  We
+		 * have to move one tuple forward, and then one backward.  (We don't
+		 * do it the other way because we might try to fetch the row before
+		 * our mark, which isn't allowed.)  XXX this case could stand to be
+		 * optimized.
+		 */
 		tuplestore_advance(winstate->buffer, true);
 		winobj->seekpos++;
 	}
 
-	while (winobj->seekpos > pos)
+	/*
+	 * Now we should be on the tuple immediately before or after the one we
+	 * want, so just fetch forwards or backwards as appropriate.
+	 */
+	if (winobj->seekpos > pos)
 	{
 		if (!tuplestore_gettupleslot(winstate->buffer, false, true, slot))
 			elog(ERROR, "unexpected end of tuplestore");
 		winobj->seekpos--;
 	}
-
-	while (winobj->seekpos < pos)
+	else
 	{
 		if (!tuplestore_gettupleslot(winstate->buffer, true, true, slot))
 			elog(ERROR, "unexpected end of tuplestore");
 		winobj->seekpos++;
 	}
 
+	Assert(winobj->seekpos == pos);
+
 	MemoryContextSwitchTo(oldcontext);
 
 	return true;
@@ -2478,16 +2503,20 @@ WinSetMarkPosition(WindowObject winobj, int64 markpos)
 	if (markpos < winobj->markpos)
 		elog(ERROR, "cannot move WindowObject's mark position backward");
 	tuplestore_select_read_pointer(winstate->buffer, winobj->markptr);
-	while (markpos > winobj->markpos)
+	if (markpos > winobj->markpos)
 	{
-		tuplestore_advance(winstate->buffer, true);
-		winobj->markpos++;
+		tuplestore_skiptuples(winstate->buffer,
+							  markpos - winobj->markpos,
+							  true);
+		winobj->markpos = markpos;
 	}
 	tuplestore_select_read_pointer(winstate->buffer, winobj->readptr);
-	while (markpos > winobj->seekpos)
+	if (markpos > winobj->seekpos)
 	{
-		tuplestore_advance(winstate->buffer, true);
-		winobj->seekpos++;
+		tuplestore_skiptuples(winstate->buffer,
+							  markpos - winobj->seekpos,
+							  true);
+		winobj->seekpos = markpos;
 	}
 }