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/include/optimizer/cost.h | 5 +++-- src/include/optimizer/planmain.h | 6 +++--- 2 files changed, 6 insertions(+), 5 deletions(-) (limited to 'src/include/optimizer') diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h index ef92d685eb..641555b706 100644 --- a/src/include/optimizer/cost.h +++ b/src/include/optimizer/cost.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/cost.h,v 1.85 2007/02/22 22:00:26 tgl Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/cost.h,v 1.86 2007/05/04 01:13:45 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -73,7 +73,8 @@ extern void cost_functionscan(Path *path, PlannerInfo *root, extern void cost_valuesscan(Path *path, PlannerInfo *root, RelOptInfo *baserel); extern void cost_sort(Path *path, PlannerInfo *root, - List *pathkeys, Cost input_cost, double tuples, int width); + List *pathkeys, Cost input_cost, double tuples, int width, + double limit_tuples); extern void cost_material(Path *path, Cost input_cost, double tuples, int width); extern void cost_agg(Path *path, PlannerInfo *root, diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h index b5ad4b3c3b..319c38c66b 100644 --- a/src/include/optimizer/planmain.h +++ b/src/include/optimizer/planmain.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/planmain.h,v 1.100 2007/02/22 22:00:26 tgl Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/planmain.h,v 1.101 2007/05/04 01:13:45 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -21,7 +21,7 @@ * prototypes for plan/planmain.c */ extern void query_planner(PlannerInfo *root, List *tlist, - double tuple_fraction, + double tuple_fraction, double limit_tuples, Path **cheapest_path, Path **sorted_path, double *num_groups); @@ -39,7 +39,7 @@ extern SubqueryScan *make_subqueryscan(List *qptlist, List *qpqual, Index scanrelid, Plan *subplan, List *subrtable); extern Append *make_append(List *appendplans, bool isTarget, List *tlist); extern Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, - List *pathkeys); + List *pathkeys, double limit_tuples); extern Sort *make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree); extern Sort *make_sort_from_groupcols(PlannerInfo *root, List *groupcls, -- cgit v1.2.1