Skip to content

Commit d26559d

Browse files
tglsfdctglsfdc
committed
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.
1 parent 0fef38d commit d26559d

File tree

13 files changed

+464
-58
lines changed

13 files changed

+464
-58
lines changed

‎src/backend/executor/nodeLimit.c

Lines changed: 32 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/executor/nodeLimit.c,v 1.29 2007/01/05 22:19:28 momjian Exp $
11+
* $PostgreSQL: pgsql/src/backend/executor/nodeLimit.c,v 1.30 2007/05/04 01:13:43 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -280,6 +280,37 @@ recompute_limits(LimitState *node)
280280
/* Reset position to start-of-scan */
281281
node->position = 0;
282282
node->subSlot = NULL;
283+
284+
/*
285+
* If we have a COUNT, and our input is a Sort node, notify it that it can
286+
* use bounded sort.
287+
*
288+
* This is a bit of a kluge, but we don't have any more-abstract way of
289+
* communicating between the two nodes; and it doesn't seem worth trying
290+
* to invent one without some more examples of special communication needs.
291+
*
292+
* Note: it is the responsibility of nodeSort.c to react properly to
293+
* changes of these parameters. If we ever do redesign this, it'd be
294+
* a good idea to integrate this signaling with the parameter-change
295+
* mechanism.
296+
*/
297+
if (IsA(outerPlanState(node), SortState))
298+
{
299+
SortState *sortState = (SortState *) outerPlanState(node);
300+
int64 tuples_needed = node->count + node->offset;
301+
302+
/* negative test checks for overflow */
303+
if (node->noCount || tuples_needed < 0)
304+
{
305+
/* make sure flag gets reset if needed upon rescan */
306+
sortState->bounded = false;
307+
}
308+
else
309+
{
310+
sortState->bounded = true;
311+
sortState->bound = tuples_needed;
312+
}
313+
}
283314
}
284315

285316
/* ----------------------------------------------------------------

‎src/backend/executor/nodeSort.c

Lines changed: 10 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/executor/nodeSort.c,v 1.60 2007/01/09 02:14:11 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/executor/nodeSort.c,v 1.61 2007/05/04 01:13:44 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -89,6 +89,8 @@ ExecSort(SortState *node)
8989
plannode->nullsFirst,
9090
work_mem,
9191
node->randomAccess);
92+
if (node->bounded)
93+
tuplesort_set_bound(tuplesortstate, node->bound);
9294
node->tuplesortstate = (void *) tuplesortstate;
9395

9496
/*
@@ -119,6 +121,8 @@ ExecSort(SortState *node)
119121
* finally set the sorted flag to true
120122
*/
121123
node->sort_Done = true;
124+
node->bounded_Done = node->bounded;
125+
node->bound_Done = node->bound;
122126
SO1_printf("ExecSort: %s\n", "sorting done");
123127
}
124128

@@ -167,6 +171,7 @@ ExecInitSort(Sort *node, EState *estate, int eflags)
167171
EXEC_FLAG_BACKWARD |
168172
EXEC_FLAG_MARK)) != 0;
169173

174+
sortstate->bounded = false;
170175
sortstate->sort_Done = false;
171176
sortstate->tuplesortstate = NULL;
172177

@@ -307,11 +312,14 @@ ExecReScanSort(SortState *node, ExprContext *exprCtxt)
307312

308313
/*
309314
* If subnode is to be rescanned then we forget previous sort results; we
310-
* have to re-read the subplan and re-sort.
315+
* have to re-read the subplan and re-sort. Also must re-sort if the
316+
* bounded-sort parameters changed or we didn't select randomAccess.
311317
*
312318
* Otherwise we can just rewind and rescan the sorted output.
313319
*/
314320
if (((PlanState *) node)->lefttree->chgParam != NULL ||
321+
node->bounded != node->bounded_Done ||
322+
node->bound != node->bound_Done ||
315323
!node->randomAccess)
316324
{
317325
node->sort_Done = false;

‎src/backend/optimizer/path/costsize.c

Lines changed: 60 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -54,7 +54,7 @@
5454
* Portions Copyright (c) 1994, Regents of the University of California
5555
*
5656
* IDENTIFICATION
57-
* $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.181 2007/04/21 21:01:44 tgl Exp $
57+
* $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.182 2007/05/04 01:13:44 tgl Exp $
5858
*
5959
*-------------------------------------------------------------------------
6060
*/
@@ -922,6 +922,10 @@ cost_valuesscan(Path *path, PlannerInfo *root, RelOptInfo *baserel)
922922
* disk traffic = 2 * relsize * ceil(logM(p / (2*work_mem)))
923923
* cpu = comparison_cost * t * log2(t)
924924
*
925+
* If the sort is bounded (i.e., only the first k result tuples are needed)
926+
* and k tuples can fit into work_mem, we use a heap method that keeps only
927+
* k tuples in the heap; this will require about t*log2(k) tuple comparisons.
928+
*
925929
* The disk traffic is assumed to be 3/4ths sequential and 1/4th random
926930
* accesses (XXX can't we refine that guess?)
927931
*
@@ -932,6 +936,7 @@ cost_valuesscan(Path *path, PlannerInfo *root, RelOptInfo *baserel)
932936
* 'input_cost' is the total cost for reading the input data
933937
* 'tuples' is the number of tuples in the relation
934938
* 'width' is the average tuple width in bytes
939+
* 'limit_tuples' is the bound on the number of output tuples; -1 if no bound
935940
*
936941
* NOTE: some callers currently pass NIL for pathkeys because they
937942
* can't conveniently supply the sort keys. Since this routine doesn't
@@ -942,11 +947,14 @@ cost_valuesscan(Path *path, PlannerInfo *root, RelOptInfo *baserel)
942947
*/
943948
void
944949
cost_sort(Path *path, PlannerInfo *root,
945-
List *pathkeys, Cost input_cost, double tuples, int width)
950+
List *pathkeys, Cost input_cost, double tuples, int width,
951+
double limit_tuples)
946952
{
947953
Cost startup_cost = input_cost;
948954
Cost run_cost = 0;
949-
double nbytes = relation_byte_size(tuples, width);
955+
double input_bytes = relation_byte_size(tuples, width);
956+
double output_bytes;
957+
double output_tuples;
950958
long work_mem_bytes = work_mem * 1024L;
951959

952960
if (!enable_sort)
@@ -959,23 +967,39 @@ cost_sort(Path *path, PlannerInfo *root,
959967
if (tuples < 2.0)
960968
tuples = 2.0;
961969

962-
/*
963-
* CPU costs
964-
*
965-
* Assume about two operator evals per tuple comparison and N log2 N
966-
* comparisons
967-
*/
968-
startup_cost += 2.0 * cpu_operator_cost * tuples * LOG2(tuples);
970+
/* Do we have a useful LIMIT? */
971+
if (limit_tuples > 0 && limit_tuples < tuples)
972+
{
973+
output_tuples = limit_tuples;
974+
output_bytes = relation_byte_size(output_tuples, width);
975+
}
976+
else
977+
{
978+
output_tuples = tuples;
979+
output_bytes = input_bytes;
980+
}
969981

970-
/* disk costs */
971-
if (nbytes > work_mem_bytes)
982+
if (output_bytes > work_mem_bytes)
972983
{
973-
double npages = ceil(nbytes / BLCKSZ);
974-
double nruns = (nbytes / work_mem_bytes) * 0.5;
984+
/*
985+
* We'll have to use a disk-based sort of all the tuples
986+
*/
987+
double npages = ceil(input_bytes / BLCKSZ);
988+
double nruns = (input_bytes / work_mem_bytes) * 0.5;
975989
double mergeorder = tuplesort_merge_order(work_mem_bytes);
976990
double log_runs;
977991
double npageaccesses;
978992

993+
/*
994+
* CPU costs
995+
*
996+
* Assume about two operator evals per tuple comparison and N log2 N
997+
* comparisons
998+
*/
999+
startup_cost += 2.0 * cpu_operator_cost * tuples * LOG2(tuples);
1000+
1001+
/* Disk costs */
1002+
9791003
/* Compute logM(r) as log(r) / log(M) */
9801004
if (nruns > mergeorder)
9811005
log_runs = ceil(log(nruns) / log(mergeorder));
@@ -986,10 +1010,27 @@ cost_sort(Path *path, PlannerInfo *root,
9861010
startup_cost += npageaccesses *
9871011
(seq_page_cost * 0.75 + random_page_cost * 0.25);
9881012
}
1013+
else if (tuples > 2 * output_tuples || input_bytes > work_mem_bytes)
1014+
{
1015+
/*
1016+
* We'll use a bounded heap-sort keeping just K tuples in memory,
1017+
* for a total number of tuple comparisons of N log2 K; but the
1018+
* constant factor is a bit higher than for quicksort. Tweak it
1019+
* so that the cost curve is continuous at the crossover point.
1020+
*/
1021+
startup_cost += 2.0 * cpu_operator_cost * tuples * LOG2(2.0 * output_tuples);
1022+
}
1023+
else
1024+
{
1025+
/* We'll use plain quicksort on all the input tuples */
1026+
startup_cost += 2.0 * cpu_operator_cost * tuples * LOG2(tuples);
1027+
}
9891028

9901029
/*
9911030
* Also charge a small amount (arbitrarily set equal to operator cost) per
992-
* extracted tuple.
1031+
* extracted tuple. Note it's correct to use tuples not output_tuples
1032+
* here --- the upper LIMIT will pro-rate the run cost so we'd be double
1033+
* counting the LIMIT otherwise.
9931034
*/
9941035
run_cost += cpu_operator_cost * tuples;
9951036

@@ -1431,7 +1472,8 @@ cost_mergejoin(MergePath *path, PlannerInfo *root)
14311472
outersortkeys,
14321473
outer_path->total_cost,
14331474
outer_path_rows,
1434-
outer_path->parent->width);
1475+
outer_path->parent->width,
1476+
-1.0);
14351477
startup_cost += sort_path.startup_cost;
14361478
run_cost += (sort_path.total_cost - sort_path.startup_cost)
14371479
* outerscansel;
@@ -1450,7 +1492,8 @@ cost_mergejoin(MergePath *path, PlannerInfo *root)
14501492
innersortkeys,
14511493
inner_path->total_cost,
14521494
inner_path_rows,
1453-
inner_path->parent->width);
1495+
inner_path->parent->width,
1496+
-1.0);
14541497
startup_cost += sort_path.startup_cost;
14551498
run_cost += (sort_path.total_cost - sort_path.startup_cost)
14561499
* innerscansel * rescanratio;

‎src/backend/optimizer/plan/createplan.c

Lines changed: 20 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@
1010
*
1111
*
1212
* IDENTIFICATION
13-
* $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.229 2007/04/21 21:01:44 tgl Exp $
13+
* $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.230 2007/05/04 01:13:44 tgl Exp $
1414
*
1515
*-------------------------------------------------------------------------
1616
*/
@@ -122,7 +122,8 @@ static MergeJoin *make_mergejoin(List *tlist,
122122
Plan *lefttree, Plan *righttree,
123123
JoinType jointype);
124124
static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
125-
AttrNumber *sortColIdx, Oid *sortOperators, bool *nullsFirst);
125+
AttrNumber *sortColIdx, Oid *sortOperators, bool *nullsFirst,
126+
double limit_tuples);
126127

127128

128129
/*
@@ -1579,7 +1580,8 @@ create_mergejoin_plan(PlannerInfo *root,
15791580
outer_plan = (Plan *)
15801581
make_sort_from_pathkeys(root,
15811582
outer_plan,
1582-
best_path->outersortkeys);
1583+
best_path->outersortkeys,
1584+
-1.0);
15831585
outerpathkeys = best_path->outersortkeys;
15841586
}
15851587
else
@@ -1591,7 +1593,8 @@ create_mergejoin_plan(PlannerInfo *root,
15911593
inner_plan = (Plan *)
15921594
make_sort_from_pathkeys(root,
15931595
inner_plan,
1594-
best_path->innersortkeys);
1596+
best_path->innersortkeys,
1597+
-1.0);
15951598
innerpathkeys = best_path->innersortkeys;
15961599
}
15971600
else
@@ -2589,11 +2592,13 @@ make_mergejoin(List *tlist,
25892592
* make_sort --- basic routine to build a Sort plan node
25902593
*
25912594
* Caller must have built the sortColIdx, sortOperators, and nullsFirst
2592-
* arrays already.
2595+
* arrays already. limit_tuples is as for cost_sort (in particular, pass
2596+
* -1 if no limit)
25932597
*/
25942598
static Sort *
25952599
make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
2596-
AttrNumber *sortColIdx, Oid *sortOperators, bool *nullsFirst)
2600+
AttrNumber *sortColIdx, Oid *sortOperators, bool *nullsFirst,
2601+
double limit_tuples)
25972602
{
25982603
Sort *node = makeNode(Sort);
25992604
Plan *plan = &node->plan;
@@ -2603,7 +2608,8 @@ make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
26032608
cost_sort(&sort_path, root, NIL,
26042609
lefttree->total_cost,
26052610
lefttree->plan_rows,
2606-
lefttree->plan_width);
2611+
lefttree->plan_width,
2612+
limit_tuples);
26072613
plan->startup_cost = sort_path.startup_cost;
26082614
plan->total_cost = sort_path.total_cost;
26092615
plan->targetlist = lefttree->targetlist;
@@ -2664,6 +2670,8 @@ add_sort_column(AttrNumber colIdx, Oid sortOp, bool nulls_first,
26642670
*
26652671
* 'lefttree' is the node which yields input tuples
26662672
* 'pathkeys' is the list of pathkeys by which the result is to be sorted
2673+
* 'limit_tuples' is the bound on the number of output tuples;
2674+
* -1 if no bound
26672675
*
26682676
* We must convert the pathkey information into arrays of sort key column
26692677
* numbers and sort operator OIDs.
@@ -2675,7 +2683,8 @@ add_sort_column(AttrNumber colIdx, Oid sortOp, bool nulls_first,
26752683
* adding a Result node just to do the projection.
26762684
*/
26772685
Sort *
2678-
make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys)
2686+
make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
2687+
double limit_tuples)
26792688
{
26802689
List *tlist = lefttree->targetlist;
26812690
ListCell *i;
@@ -2810,7 +2819,7 @@ make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys)
28102819
Assert(numsortkeys > 0);
28112820

28122821
return make_sort(root, lefttree, numsortkeys,
2813-
sortColIdx, sortOperators, nullsFirst);
2822+
sortColIdx, sortOperators, nullsFirst, limit_tuples);
28142823
}
28152824

28162825
/*
@@ -2859,7 +2868,7 @@ make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)
28592868
Assert(numsortkeys > 0);
28602869

28612870
return make_sort(root, lefttree, numsortkeys,
2862-
sortColIdx, sortOperators, nullsFirst);
2871+
sortColIdx, sortOperators, nullsFirst, -1.0);
28632872
}
28642873

28652874
/*
@@ -2919,7 +2928,7 @@ make_sort_from_groupcols(PlannerInfo *root,
29192928
Assert(numsortkeys > 0);
29202929

29212930
return make_sort(root, lefttree, numsortkeys,
2922-
sortColIdx, sortOperators, nullsFirst);
2931+
sortColIdx, sortOperators, nullsFirst, -1.0);
29232932
}
29242933

29252934
Material *

‎src/backend/optimizer/plan/planmain.c

Lines changed: 10 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@
1414
*
1515
*
1616
* IDENTIFICATION
17-
* $PostgreSQL: pgsql/src/backend/optimizer/plan/planmain.c,v 1.100 2007/04/21 21:01:45 tgl Exp $
17+
* $PostgreSQL: pgsql/src/backend/optimizer/plan/planmain.c,v 1.101 2007/05/04 01:13:44 tgl Exp $
1818
*
1919
*-------------------------------------------------------------------------
2020
*/
@@ -47,6 +47,8 @@
4747
* tlist is the target list the query should produce
4848
* (this is NOT necessarily root->parse->targetList!)
4949
* tuple_fraction is the fraction of tuples we expect will be retrieved
50+
* limit_tuples is a hard limit on number of tuples to retrieve,
51+
* or -1 if no limit
5052
*
5153
* Output parameters:
5254
* *cheapest_path receives the overall-cheapest path for the query
@@ -74,9 +76,13 @@
7476
* from the plan to be retrieved
7577
* tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
7678
* expected to be retrieved (ie, a LIMIT specification)
79+
* Note that a nonzero tuple_fraction could come from outer context; it is
80+
* therefore not redundant with limit_tuples. We use limit_tuples to determine
81+
* whether a bounded sort can be used at runtime.
7782
*/
7883
void
79-
query_planner(PlannerInfo *root, List *tlist, double tuple_fraction,
84+
query_planner(PlannerInfo *root, List *tlist,
85+
double tuple_fraction, double limit_tuples,
8086
Path **cheapest_path, Path **sorted_path,
8187
double *num_groups)
8288
{
@@ -354,7 +360,8 @@ query_planner(PlannerInfo *root, List *tlist, double tuple_fraction,
354360
/* Figure cost for sorting */
355361
cost_sort(&sort_path, root, root->query_pathkeys,
356362
cheapestpath->total_cost,
357-
final_rel->rows, final_rel->width);
363+
final_rel->rows, final_rel->width,
364+
limit_tuples);
358365
}
359366

360367
if (compare_fractional_path_costs(sortedpath, &sort_path,

0 commit comments

Comments
 (0)