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/nodeSort.c | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-) (limited to 'src/backend/executor/nodeSort.c') 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; -- cgit v1.2.3