diff options
| author | Tom Lane <tgl@sss.pgh.pa.us> | 2007-05-04 01:13:45 +0000 |
|---|---|---|
| committer | Tom Lane <tgl@sss.pgh.pa.us> | 2007-05-04 01:13:45 +0000 |
| commit | d26559dbf356736923b26704ce76ca820ff3a2b0 (patch) | |
| tree | e899e3b4eb9f0d34f598816f69a9a60379987391 /src/backend/optimizer/plan/planmain.c | |
| 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/backend/optimizer/plan/planmain.c')
| -rw-r--r-- | src/backend/optimizer/plan/planmain.c | 13 |
1 files changed, 10 insertions, 3 deletions
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index f12e388d723..c31f7d5aa65 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -14,7 +14,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/planmain.c,v 1.100 2007/04/21 21:01:45 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/planmain.c,v 1.101 2007/05/04 01:13:44 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -47,6 +47,8 @@ * tlist is the target list the query should produce * (this is NOT necessarily root->parse->targetList!) * tuple_fraction is the fraction of tuples we expect will be retrieved + * limit_tuples is a hard limit on number of tuples to retrieve, + * or -1 if no limit * * Output parameters: * *cheapest_path receives the overall-cheapest path for the query @@ -74,9 +76,13 @@ * from the plan to be retrieved * tuple_fraction >= 1: tuple_fraction is the absolute number of tuples * expected to be retrieved (ie, a LIMIT specification) + * Note that a nonzero tuple_fraction could come from outer context; it is + * therefore not redundant with limit_tuples. We use limit_tuples to determine + * whether a bounded sort can be used at runtime. */ void -query_planner(PlannerInfo *root, List *tlist, double tuple_fraction, +query_planner(PlannerInfo *root, List *tlist, + double tuple_fraction, double limit_tuples, Path **cheapest_path, Path **sorted_path, double *num_groups) { @@ -354,7 +360,8 @@ query_planner(PlannerInfo *root, List *tlist, double tuple_fraction, /* Figure cost for sorting */ cost_sort(&sort_path, root, root->query_pathkeys, cheapestpath->total_cost, - final_rel->rows, final_rel->width); + final_rel->rows, final_rel->width, + limit_tuples); } if (compare_fractional_path_costs(sortedpath, &sort_path, |