diff options
| author | Tom Lane | 2007-05-04 01:13:45 +0000 |
|---|---|---|
| committer | Tom Lane | 2007-05-04 01:13:45 +0000 |
| commit | d26559dbf356736923b26704ce76ca820ff3a2b0 (patch) | |
| tree | e899e3b4eb9f0d34f598816f69a9a60379987391 /src/include/optimizer | |
| parent | 0fef38da215cdc9b01b1b623c2e37d7414b91843 (diff) | |
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.
Diffstat (limited to 'src/include/optimizer')
| -rw-r--r-- | src/include/optimizer/cost.h | 5 | ||||
| -rw-r--r-- | src/include/optimizer/planmain.h | 6 |
2 files changed, 6 insertions, 5 deletions
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, |