Teach tuplesort.c about "top N" sorting, in which only the first N tuples

need be returned.  We keep a heap of the current best N tuples and sift-up
new tuples into it as we scan the input.  For M input tuples this means
only about M*log(N) comparisons instead of M*log(M), not to mention a lot
less workspace when N is small --- avoiding spill-to-disk for large M
is actually the most attractive thing about it.  Patch includes planner
and executor support for invoking this facility in ORDER BY ... LIMIT
queries.  Greg Stark, with some editorialization by moi.

1 files changed, 32 insertions, 1 deletions

diff --git a/src/backend/executor/nodeLimit.c b/src/backend/executor/nodeLimit.c
index d2ecb3722f7..9d40952647d 100644
--- a/src/backend/executor/nodeLimit.c
+++ b/src/backend/executor/nodeLimit.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/executor/nodeLimit.c,v 1.29 2007/01/05 22:19:28 momjian Exp $
+ *	  $PostgreSQL: pgsql/src/backend/executor/nodeLimit.c,v 1.30 2007/05/04 01:13:43 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -280,6 +280,37 @@ recompute_limits(LimitState *node)
 	/* Reset position to start-of-scan */
 	node->position = 0;
 	node->subSlot = NULL;
+
+	/*
+	 * If we have a COUNT, and our input is a Sort node, notify it that it can
+	 * use bounded sort.
+	 *
+	 * This is a bit of a kluge, but we don't have any more-abstract way of
+	 * communicating between the two nodes; and it doesn't seem worth trying
+	 * to invent one without some more examples of special communication needs.
+	 *
+	 * Note: it is the responsibility of nodeSort.c to react properly to
+	 * changes of these parameters.  If we ever do redesign this, it'd be
+	 * a good idea to integrate this signaling with the parameter-change
+	 * mechanism.
+	 */
+	if (IsA(outerPlanState(node), SortState))
+	{
+		SortState *sortState = (SortState *) outerPlanState(node);
+		int64 tuples_needed = node->count + node->offset;
+
+		/* negative test checks for overflow */
+		if (node->noCount || tuples_needed < 0)
+		{
+			/* make sure flag gets reset if needed upon rescan */
+			sortState->bounded = false;
+		}
+		else
+		{
+			sortState->bounded = true;
+			sortState->bound = tuples_needed;
+		}
+	}
 }
 
 /* ----------------------------------------------------------------