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.

2 files changed, 42 insertions, 3 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;
+		}
+	}
 }
 
 /* ----------------------------------------------------------------
diff --git a/src/backend/executor/nodeSort.c b/src/backend/executor/nodeSort.c
index 97b5c4ff150..5b18235258f 100644
--- a/src/backend/executor/nodeSort.c
+++ b/src/backend/executor/nodeSort.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/executor/nodeSort.c,v 1.60 2007/01/09 02:14:11 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/executor/nodeSort.c,v 1.61 2007/05/04 01:13:44 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -89,6 +89,8 @@ ExecSort(SortState *node)
 											  plannode->nullsFirst,
 											  work_mem,
 											  node->randomAccess);
+		if (node->bounded)
+			tuplesort_set_bound(tuplesortstate, node->bound);
 		node->tuplesortstate = (void *) tuplesortstate;
 
 		/*
@@ -119,6 +121,8 @@ ExecSort(SortState *node)
 		 * finally set the sorted flag to true
 		 */
 		node->sort_Done = true;
+		node->bounded_Done = node->bounded;
+		node->bound_Done = node->bound;
 		SO1_printf("ExecSort: %s\n", "sorting done");
 	}
 
@@ -167,6 +171,7 @@ ExecInitSort(Sort *node, EState *estate, int eflags)
 										 EXEC_FLAG_BACKWARD |
 										 EXEC_FLAG_MARK)) != 0;
 
+	sortstate->bounded = false;
 	sortstate->sort_Done = false;
 	sortstate->tuplesortstate = NULL;
 
@@ -307,11 +312,14 @@ ExecReScanSort(SortState *node, ExprContext *exprCtxt)
 
 	/*
 	 * If subnode is to be rescanned then we forget previous sort results; we
-	 * have to re-read the subplan and re-sort.
+	 * have to re-read the subplan and re-sort.  Also must re-sort if the
+	 * bounded-sort parameters changed or we didn't select randomAccess.
 	 *
 	 * Otherwise we can just rewind and rescan the sorted output.
 	 */
 	if (((PlanState *) node)->lefttree->chgParam != NULL ||
+		node->bounded != node->bounded_Done ||
+		node->bound != node->bound_Done ||
 		!node->randomAccess)
 	{
 		node->sort_Done = false;