Skip to content

Commit 22f0ac2

Browse files
knizhnikknizhnik
committed
Use partial sort optimizatiob only for bounded sort
1 parent 91224ee commit 22f0ac2

File tree

10 files changed

+48
-28
lines changed

10 files changed

+48
-28
lines changed

‎src/backend/executor/nodeAgg.c

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -520,7 +520,9 @@ initialize_phase(AggState *aggstate, int newphase)
520520
sortnode->collations,
521521
sortnode->nullsFirst,
522522
work_mem,
523-
false);
523+
false,
524+
sortnode->prefix
525+
);
524526
}
525527

526528
aggstate->current_phase = newphase;
@@ -597,7 +599,7 @@ initialize_aggregate(AggState *aggstate, AggStatePerTrans pertrans,
597599
pertrans->sortOperators,
598600
pertrans->sortCollations,
599601
pertrans->sortNullsFirst,
600-
work_mem, false);
602+
work_mem, false, 0);
601603
}
602604

603605
/*

‎src/backend/executor/nodeSort.c

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -89,7 +89,9 @@ ExecSort(SortState *node)
8989
plannode->collations,
9090
plannode->nullsFirst,
9191
work_mem,
92-
node->randomAccess);
92+
node->randomAccess,
93+
plannode->prefix
94+
);
9395
if (node->bounded)
9496
tuplesort_set_bound(tuplesortstate, node->bound);
9597
node->tuplesortstate = (void *) tuplesortstate;
@@ -98,15 +100,14 @@ ExecSort(SortState *node)
98100
* Scan the subplan and feed all the tuples to tuplesort.
99101
*/
100102

101-
for (;;)
103+
do
102104
{
103105
slot = ExecProcNode(outerNode);
104106

105107
if (TupIsNull(slot))
106108
break;
107109

108-
tuplesort_puttupleslot(tuplesortstate, slot);
109-
}
110+
} while (tuplesort_puttupleslot(tuplesortstate, slot));
110111

111112
/*
112113
* Complete the sort.

‎src/backend/nodes/copyfuncs.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -827,6 +827,7 @@ _copySort(const Sort *from)
827827
CopyPlanFields((const Plan *) from, (Plan *) newnode);
828828

829829
COPY_SCALAR_FIELD(numCols);
830+
COPY_SCALAR_FIELD(prefix);
830831
COPY_POINTER_FIELD(sortColIdx, from->numCols * sizeof(AttrNumber));
831832
COPY_POINTER_FIELD(sortOperators, from->numCols * sizeof(Oid));
832833
COPY_POINTER_FIELD(collations, from->numCols * sizeof(Oid));

‎src/backend/nodes/outfuncs.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -778,6 +778,7 @@ _outSort(StringInfo str, const Sort *node)
778778
_outPlanInfo(str, (const Plan *) node);
779779

780780
WRITE_INT_FIELD(numCols);
781+
WRITE_INT_FIELD(prefix);
781782

782783
appendStringInfoString(str, " :sortColIdx");
783784
for (i = 0; i < node->numCols; i++)

‎src/backend/nodes/readfuncs.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1951,6 +1951,7 @@ _readSort(void)
19511951
ReadCommonPlan(&local_node->plan);
19521952

19531953
READ_INT_FIELD(numCols);
1954+
READ_INT_FIELD(prefix);
19541955
READ_ATTRNUMBER_ARRAY(sortColIdx, local_node->numCols);
19551956
READ_OID_ARRAY(sortOperators, local_node->numCols);
19561957
READ_OID_ARRAY(collations, local_node->numCols);

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

Lines changed: 9 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1811,7 +1811,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
18111811
/* Presorted path is a loser */
18121812
sorted_path = NULL;
18131813
}
1814-
} else if (partial_sorted_path != NULL) {
1814+
} else if (partial_sorted_path != NULL && limit_tuples > 0.0 && limit_tuples < path_rows) {
18151815
Path sort_path;
18161816
Path partial_sort_path;
18171817

@@ -1826,7 +1826,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
18261826
0.0, work_mem, root->limit_tuples);
18271827

18281828
partial_sort_path.total_cost -= partial_sort_path.startup_cost;
1829-
partial_sort_path.startup_cost /= partial_sorted_path->pathkeys->length+1;
1829+
partial_sort_path.startup_cost /= path_rows/limit_tuples;
18301830
partial_sort_path.total_cost += partial_sort_path.startup_cost;
18311831

18321832

@@ -2399,15 +2399,18 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
23992399
{
24002400
if (!pathkeys_contained_in(root->sort_pathkeys, current_pathkeys))
24012401
{
2402+
double numRows = result_plan->plan_rows;
24022403
result_plan = (Plan *) make_sort_from_pathkeys(root,
24032404
result_plan,
2404-
root->sort_pathkeys,
2405+
root->sort_pathkeys,
24052406
limit_tuples);
2406-
if (partial_sorted_path && best_path == partial_sorted_path)
2407-
{
2407+
/* check if input data was partially sorted and there is limit clause */
2408+
if (partial_sorted_path && best_path == partial_sorted_path && limit_tuples > 0.0 && limit_tuples < numRows)
2409+
{
24082410
result_plan->total_cost -= result_plan->startup_cost;
2409-
result_plan->startup_cost /= partial_sorted_path->pathkeys->length+1;
2411+
result_plan->startup_cost /= numRows/limit_tuples;
24102412
result_plan->total_cost += result_plan->startup_cost;
2413+
((Sort*)result_plan)->prefix = partial_sorted_path->pathkeys->length;
24112414
}
24122415
current_pathkeys = root->sort_pathkeys;
24132416
}

‎src/backend/utils/adt/orderedsetaggs.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -276,7 +276,7 @@ ordered_set_startup(FunctionCallInfo fcinfo, bool use_tuples)
276276
qstate->sortOperators,
277277
qstate->sortCollations,
278278
qstate->sortNullsFirsts,
279-
work_mem, false);
279+
work_mem, false, 0);
280280
else
281281
osastate->sortstate = tuplesort_begin_datum(qstate->sortColType,
282282
qstate->sortOperator,

‎src/backend/utils/sort/tuplesort.c

Lines changed: 23 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -219,6 +219,8 @@ struct Tuplesortstate
219219
* tuples to return? */
220220
bool boundUsed; /* true if we made use of a bounded heap */
221221
int bound; /* if bounded, the maximum number of tuples */
222+
int prefix; /* number of prefix keys by which input data is already sorted */
223+
int matchedKeys; /* number of matched keys */
222224
int64 availMem; /* remaining memory available, in bytes */
223225
int64 allowedMem; /* total memory allowed, in bytes */
224226
int maxTapes; /* number of tapes (Knuth's T) */
@@ -458,7 +460,7 @@ struct Tuplesortstate
458460

459461

460462
static Tuplesortstate *tuplesort_begin_common(int workMem, bool randomAccess);
461-
static void puttuple_common(Tuplesortstate *state, SortTuple *tuple);
463+
static bool puttuple_common(Tuplesortstate *state, SortTuple *tuple);
462464
static bool consider_abort_common(Tuplesortstate *state);
463465
static void inittapes(Tuplesortstate *state);
464466
static void selectnewtape(Tuplesortstate *state);
@@ -575,7 +577,7 @@ tuplesort_begin_common(int workMem, bool randomAccess)
575577
state->availMem = state->allowedMem;
576578
state->sortcontext = sortcontext;
577579
state->tapeset = NULL;
578-
580+
state->prefix = 0;
579581
state->memtupcount = 0;
580582

581583
/*
@@ -613,7 +615,7 @@ tuplesort_begin_heap(TupleDesc tupDesc,
613615
int nkeys, AttrNumber *attNums,
614616
Oid *sortOperators, Oid *sortCollations,
615617
bool *nullsFirstFlags,
616-
int workMem, bool randomAccess)
618+
int workMem, bool randomAccess, int prefix)
617619
{
618620
Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
619621
MemoryContext oldcontext;
@@ -648,6 +650,7 @@ tuplesort_begin_heap(TupleDesc tupDesc,
648650

649651
/* Prepare SortSupport data for each column */
650652
state->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
653+
state->prefix = prefix;
651654

652655
for (i = 0; i < nkeys; i++)
653656
{
@@ -1202,21 +1205,22 @@ grow_memtuples(Tuplesortstate *state)
12021205
*
12031206
* Note that the input data is always copied; the caller need not save it.
12041207
*/
1205-
void
1208+
bool
12061209
tuplesort_puttupleslot(Tuplesortstate *state, TupleTableSlot *slot)
12071210
{
12081211
MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
12091212
SortTuple stup;
1210-
1213+
bool needmore;
12111214
/*
12121215
* Copy the given tuple into memory we control, and decrease availMem.
12131216
* Then call the common code.
12141217
*/
12151218
COPYTUP(state, &stup, (void *) slot);
12161219

1217-
puttuple_common(state, &stup);
1220+
needmore = puttuple_common(state, &stup);
12181221

12191222
MemoryContextSwitchTo(oldcontext);
1223+
return needmore;
12201224
}
12211225

12221226
/*
@@ -1397,7 +1401,7 @@ tuplesort_putdatum(Tuplesortstate *state, Datum val, bool isNull)
13971401
/*
13981402
* Shared code for tuple and datum cases.
13991403
*/
1400-
static void
1404+
static bool
14011405
puttuple_common(Tuplesortstate *state, SortTuple *tuple)
14021406
{
14031407
switch (state->status)
@@ -1441,14 +1445,14 @@ puttuple_common(Tuplesortstate *state, SortTuple *tuple)
14411445
pg_rusage_show(&state->ru_start));
14421446
#endif
14431447
make_bounded_heap(state);
1444-
return;
1448+
break;
14451449
}
14461450

14471451
/*
14481452
* Done if we still fit in available memory and have array slots.
14491453
*/
14501454
if (state->memtupcount < state->memtupsize && !LACKMEM(state))
1451-
return;
1455+
break;
14521456

14531457
/*
14541458
* Nope; time to switch to tape-based operation.
@@ -1475,6 +1479,9 @@ puttuple_common(Tuplesortstate *state, SortTuple *tuple)
14751479
{
14761480
/* new tuple <= top of the heap, so we can discard it */
14771481
free_sort_tuple(state, tuple);
1482+
if (state->prefix > state->matchedKeys && state->memtupcount >= state->bound) {
1483+
return false;
1484+
}
14781485
CHECK_FOR_INTERRUPTS();
14791486
}
14801487
else
@@ -1517,6 +1524,7 @@ puttuple_common(Tuplesortstate *state, SortTuple *tuple)
15171524
elog(ERROR, "invalid tuplesort state");
15181525
break;
15191526
}
1527+
return true;
15201528
}
15211529

15221530
static bool
@@ -3071,19 +3079,20 @@ comparetup_heap(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
30713079
HeapTupleData rtup;
30723080
TupleDesc tupDesc;
30733081
int nkey;
3074-
int32 compare;
3082+
int32 compare = 0;
30753083
AttrNumber attno;
30763084
Datum datum1,
30773085
datum2;
30783086
bool isnull1,
30793087
isnull2;
30803088

3089+
state->matchedKeys = 0;
30813090

30823091
/* Compare the leading sort key */
30833092
compare = ApplySortComparator(a->datum1, a->isnull1,
30843093
b->datum1, b->isnull1,
30853094
sortKey);
3086-
if (compare != 0)
3095+
if (compare != 0)
30873096
return compare;
30883097

30893098
/* Compare additional sort keys */
@@ -3119,10 +3128,11 @@ comparetup_heap(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
31193128
datum2, isnull2,
31203129
sortKey);
31213130
if (compare != 0)
3122-
return compare;
3131+
break;
31233132
}
3133+
state->matchedKeys = nkey;
31243134

3125-
return 0;
3135+
return compare;
31263136
}
31273137

31283138
static void

‎src/include/nodes/plannodes.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -679,6 +679,7 @@ typedef struct Sort
679679
{
680680
Plan plan;
681681
int numCols; /* number of sort-key columns */
682+
int prefix; /* sorted prefix: number of keys by which input stream is already sorted */
682683
AttrNumber *sortColIdx; /* their indexes in the target list */
683684
Oid *sortOperators; /* OIDs of operators to sort them by */
684685
Oid *collations; /* OIDs of collations */

‎src/include/utils/tuplesort.h

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -62,7 +62,7 @@ extern Tuplesortstate *tuplesort_begin_heap(TupleDesc tupDesc,
6262
int nkeys, AttrNumber *attNums,
6363
Oid *sortOperators, Oid *sortCollations,
6464
bool *nullsFirstFlags,
65-
int workMem, bool randomAccess);
65+
int workMem, bool randomAccess, int prefix);
6666
extern Tuplesortstate *tuplesort_begin_cluster(TupleDesc tupDesc,
6767
Relation indexRel,
6868
int workMem, bool randomAccess);
@@ -81,7 +81,7 @@ extern Tuplesortstate *tuplesort_begin_datum(Oid datumType,
8181

8282
extern void tuplesort_set_bound(Tuplesortstate *state, int64 bound);
8383

84-
extern void tuplesort_puttupleslot(Tuplesortstate *state,
84+
extern bool tuplesort_puttupleslot(Tuplesortstate *state,
8585
TupleTableSlot *slot);
8686
extern void tuplesort_putheaptuple(Tuplesortstate *state, HeapTuple tup);
8787
extern void tuplesort_putindextuplevalues(Tuplesortstate *state,

0 commit comments

Comments
 (0)