From d26559dbf356736923b26704ce76ca820ff3a2b0 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Fri, 4 May 2007 01:13:45 +0000 Subject: 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. --- src/backend/executor/nodeLimit.c | 33 ++++++++++++++++++++++++++++++++- 1 file changed, 32 insertions(+), 1 deletion(-) (limited to 'src/backend/executor/nodeLimit.c') 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; + } + } } /* ---------------------------------------------------------------- -- cgit v1.2.3