From c4eb10fecd7e517746f77154c671bb6fb6ff9500 Mon Sep 17 00:00:00 2001 From: Yao Wang Date: Tue, 9 Jul 2024 08:05:43 +0000 Subject: [PATCH 2/2] add Sort->ndistInFirstRow --- src/backend/executor/nodeSort.c | 2 + src/backend/optimizer/plan/createplan.c | 232 +++++++++++++++++++++--- src/backend/utils/sort/mk_qsort_tuple.c | 4 + src/backend/utils/sort/tuplesort.c | 15 +- src/include/nodes/plannodes.h | 3 + src/include/utils/tuplesort.h | 2 + 6 files changed, 227 insertions(+), 31 deletions(-) diff --git a/src/backend/executor/nodeSort.c b/src/backend/executor/nodeSort.c index 3fc925d7b4..c8e85568eb 100644 --- a/src/backend/executor/nodeSort.c +++ b/src/backend/executor/nodeSort.c @@ -122,6 +122,8 @@ ExecSort(PlanState *pstate) tuplesortopts); if (node->bounded) tuplesort_set_bound(tuplesortstate, node->bound); + tuplesort_set_mkqsApplicable(tuplesortstate, + plannode->mkqsApplicable); node->tuplesortstate = (void *) tuplesortstate; /* diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 6b64c4a362..1e17939f71 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -42,6 +42,8 @@ #include "parser/parsetree.h" #include "partitioning/partprune.h" #include "utils/lsyscache.h" +#include "utils/syscache.h" +#include "catalog/pg_statistic.h" /* @@ -256,12 +258,14 @@ static MergeJoin *make_mergejoin(List *tlist, bool skip_mark_restore); static Sort *make_sort(Plan *lefttree, int numCols, AttrNumber *sortColIdx, Oid *sortOperators, - Oid *collations, bool *nullsFirst); + Oid *collations, bool *nullsFirst, + bool mkqsApplicable); static IncrementalSort *make_incrementalsort(Plan *lefttree, int numCols, int nPresortedCols, AttrNumber *sortColIdx, Oid *sortOperators, Oid *collations, bool *nullsFirst); -static Plan *prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys, +static Plan *prepare_sort_from_pathkeys(PlannerInfo *root, + Plan *lefttree, List *pathkeys, Relids relids, const AttrNumber *reqColIdx, bool adjust_tlist_in_place, @@ -269,8 +273,9 @@ static Plan *prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys, AttrNumber **p_sortColIdx, Oid **p_sortOperators, Oid **p_collations, - bool **p_nullsFirst); -static Sort *make_sort_from_pathkeys(Plan *lefttree, List *pathkeys, + bool **p_nullsFirst, + bool *mkqsApplicable); +static Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys, Relids relids); static IncrementalSort *make_incrementalsort_from_pathkeys(Plan *lefttree, List *pathkeys, Relids relids, int nPresortedCols); @@ -1282,7 +1287,8 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags) * function result; it must be the same plan node. However, we then * need to detect whether any tlist entries were added. */ - (void) prepare_sort_from_pathkeys((Plan *) plan, pathkeys, + (void) prepare_sort_from_pathkeys(NULL, + (Plan *) plan, pathkeys, best_path->path.parent->relids, NULL, true, @@ -1290,7 +1296,8 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags) &nodeSortColIdx, &nodeSortOperators, &nodeCollations, - &nodeNullsFirst); + &nodeNullsFirst, + NULL); tlist_was_changed = (orig_tlist_length != list_length(plan->plan.targetlist)); } @@ -1326,7 +1333,8 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags) * don't need an explicit sort, to make sure they are returning * the same sort key columns the Append expects. */ - subplan = prepare_sort_from_pathkeys(subplan, pathkeys, + subplan = prepare_sort_from_pathkeys(NULL, + subplan, pathkeys, subpath->parent->relids, nodeSortColIdx, false, @@ -1334,7 +1342,8 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags) &sortColIdx, &sortOperators, &collations, - &nullsFirst); + &nullsFirst, + NULL); /* * Check that we got the same sort key information. We just @@ -1358,7 +1367,8 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path, int flags) { Sort *sort = make_sort(subplan, numsortkeys, sortColIdx, sortOperators, - collations, nullsFirst); + collations, nullsFirst, + NULL); label_sort_with_costsize(root, sort, best_path->limit_tuples); subplan = (Plan *) sort; @@ -1467,7 +1477,8 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path, * function result; it must be the same plan node. However, we then need * to detect whether any tlist entries were added. */ - (void) prepare_sort_from_pathkeys(plan, pathkeys, + (void) prepare_sort_from_pathkeys(NULL, + plan, pathkeys, best_path->path.parent->relids, NULL, true, @@ -1475,7 +1486,8 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path, &node->sortColIdx, &node->sortOperators, &node->collations, - &node->nullsFirst); + &node->nullsFirst, + NULL); tlist_was_changed = (orig_tlist_length != list_length(plan->targetlist)); /* @@ -1498,7 +1510,8 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path, subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST); /* Compute sort column info, and adjust subplan's tlist as needed */ - subplan = prepare_sort_from_pathkeys(subplan, pathkeys, + subplan = prepare_sort_from_pathkeys(NULL, + subplan, pathkeys, subpath->parent->relids, node->sortColIdx, false, @@ -1506,7 +1519,8 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path, &sortColIdx, &sortOperators, &collations, - &nullsFirst); + &nullsFirst, + NULL); /* * Check that we got the same sort key information. We just Assert @@ -1530,7 +1544,8 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path, { Sort *sort = make_sort(subplan, numsortkeys, sortColIdx, sortOperators, - collations, nullsFirst); + collations, nullsFirst, + NULL); label_sort_with_costsize(root, sort, best_path->limit_tuples); subplan = (Plan *) sort; @@ -1977,7 +1992,8 @@ create_gather_merge_plan(PlannerInfo *root, GatherMergePath *best_path) Assert(pathkeys != NIL); /* Compute sort column info, and adjust subplan's tlist as needed */ - subplan = prepare_sort_from_pathkeys(subplan, pathkeys, + subplan = prepare_sort_from_pathkeys(NULL, + subplan, pathkeys, best_path->subpath->parent->relids, gm_plan->sortColIdx, false, @@ -1985,7 +2001,8 @@ create_gather_merge_plan(PlannerInfo *root, GatherMergePath *best_path) &gm_plan->sortColIdx, &gm_plan->sortOperators, &gm_plan->collations, - &gm_plan->nullsFirst); + &gm_plan->nullsFirst, + NULL); /* @@ -2196,7 +2213,7 @@ create_sort_plan(PlannerInfo *root, SortPath *best_path, int flags) * relids. Thus, if this sort path is based on a child relation, we must * pass its relids. */ - plan = make_sort_from_pathkeys(subplan, best_path->path.pathkeys, + plan = make_sort_from_pathkeys(root, subplan, best_path->path.pathkeys, IS_OTHER_REL(best_path->subpath->parent) ? best_path->path.parent->relids : NULL); @@ -4526,7 +4543,7 @@ create_mergejoin_plan(PlannerInfo *root, if (best_path->outersortkeys) { Relids outer_relids = outer_path->parent->relids; - Sort *sort = make_sort_from_pathkeys(outer_plan, + Sort *sort = make_sort_from_pathkeys(NULL, outer_plan, best_path->outersortkeys, outer_relids); @@ -4540,7 +4557,7 @@ create_mergejoin_plan(PlannerInfo *root, if (best_path->innersortkeys) { Relids inner_relids = inner_path->parent->relids; - Sort *sort = make_sort_from_pathkeys(inner_plan, + Sort *sort = make_sort_from_pathkeys(NULL, inner_plan, best_path->innersortkeys, inner_relids); @@ -6067,7 +6084,8 @@ make_mergejoin(List *tlist, static Sort * make_sort(Plan *lefttree, int numCols, AttrNumber *sortColIdx, Oid *sortOperators, - Oid *collations, bool *nullsFirst) + Oid *collations, bool *nullsFirst, + bool mkqsApplicable) { Sort *node; Plan *plan; @@ -6084,6 +6102,7 @@ make_sort(Plan *lefttree, int numCols, node->sortOperators = sortOperators; node->collations = collations; node->nullsFirst = nullsFirst; + node->mkqsApplicable = mkqsApplicable; return node; } @@ -6161,7 +6180,8 @@ make_incrementalsort(Plan *lefttree, int numCols, int nPresortedCols, * or a Result stacked atop lefttree). */ static Plan * -prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys, +prepare_sort_from_pathkeys(PlannerInfo *root, + Plan *lefttree, List *pathkeys, Relids relids, const AttrNumber *reqColIdx, bool adjust_tlist_in_place, @@ -6169,7 +6189,8 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys, AttrNumber **p_sortColIdx, Oid **p_sortOperators, Oid **p_collations, - bool **p_nullsFirst) + bool **p_nullsFirst, + bool *mkqsApplicable) { List *tlist = lefttree->targetlist; ListCell *i; @@ -6179,6 +6200,33 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys, Oid *collations; bool *nullsFirst; + /* Calculation of benefit from multi-key qsort + * + * The algorithm is: + * + * mkqsBene = (sum of benefit of each sort key) - fixed cost + * (sum of benefit of each sort key) = + * weight * (duplicated value ratio of previous sort key) + * + * We get the duplicated value ratio from catalog table (pg_statistic. + * stadistinct), which is not always correct. + * In addition, the value might be unavailable sometimes because the sort + * key is not from a real table or the query to catalog table fails. For + * the case, we simply ignore the sort key for calcaulation. + * + * Enable mk qsort only when estimated benefit >= 0.05, which means + * "mk qsort is supposed to be 5% faster than classical qsort". + */ + + /* Set mkqsBene to -0.02 to indicate the fixed cost */ + double mkqsBene = -0.02; + + /* + * Duplicated value ratio of previous sort key, init to 1.0 for first sort + * key to indicate "count all value" + */ + double dupRio = 1.0; + /* * We will need at most list_length(pathkeys) sort columns; possibly less */ @@ -6188,6 +6236,9 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys, collations = (Oid *) palloc(numsortkeys * sizeof(Oid)); nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool)); + if (mkqsApplicable) + *mkqsApplicable = false; + numsortkeys = 0; foreach(i, pathkeys) @@ -6200,6 +6251,9 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys, Oid sortop; ListCell *j; + /* Init value of ndist to -1 to indicate "unknown" */ + double ndist = -1; + if (ec->ec_has_volatile) { /* @@ -6303,6 +6357,54 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys, lefttree->targetlist = tlist; /* just in case NIL before */ } + /* Get the ndist value from pg_stats */ + if (mkqsApplicable && root != NULL) + { + /* + * Calculate ndist only when SORT is based on a real table + */ + if (IsA(tle->expr, Var)) + { + Var *var = (Var *)tle->expr; + RangeTblEntry *rte = root->simple_rte_array[var->varno]; + + /* + * Try to get distinct info from pg_statistic + */ + + if (rte) + { + HeapTuple tuple = SearchSysCache3( + STATRELATTINH, + ObjectIdGetDatum(rte->relid), + Int16GetDatum(var->varattno), + BoolGetDatum(false)); + if (HeapTupleIsValid(tuple)) + { + /* Use the pg_statistic entry */ + Form_pg_statistic stats; + + stats = (Form_pg_statistic) GETSTRUCT(tuple); + /* + * If stats->stadistinct < 0, it means a fraction of + * distinct tuple ratio; if it > 0, it means the number + * of distinct tuples; 0 means "unknown". + */ + if (stats->stadistinct < 0) + ndist = -stats->stadistinct; + else + { + RelOptInfo *rel = root->simple_rel_array[var->varno]; + ndist = stats->stadistinct / rel->tuples; + } + } + + if (tuple) + ReleaseSysCache(tuple); + } + } + } + /* * Look up the correct sort operator from the PathKey's slightly * abstracted representation. @@ -6321,6 +6423,61 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys, sortOperators[numsortkeys] = sortop; collations[numsortkeys] = ec->ec_collation; nullsFirst[numsortkeys] = pathkey->pk_nulls_first; + + /* + * If ndist is valid, calculate benefit for mk qsort + */ + if (ndist != -1) + { + double bene = 0; + SortSupportData sortKey; + + sortKey.comparator = NULL; + sortKey.ssup_cxt = CurrentMemoryContext; + sortKey.ssup_collation = collations[numsortkeys]; + sortKey.ssup_nulls_first = nullsFirst[numsortkeys]; + sortKey.ssup_attno = sortColIdx[numsortkeys]; + PrepareSortSupportFromOrderingOp(sortop, &sortKey); + + /* + * For data type with/without specialized comparator, use different + * weights. The weights are determined by some experiments and may + * be not accurate for all possible cases. + */ + if (sortKey.comparator == ssup_datum_unsigned_cmp || +#if SIZEOF_DATUM >= 8 + sortKey.comparator == ssup_datum_signed_cmp || +#endif + sortKey.comparator == ssup_datum_int32_cmp) + { + /* + * For data type with specialized comparator, ignore the first + * sort key because there is no benefit from duplciated values + * for first sort key. + */ + if (numsortkeys > 0) + bene += dupRio * 0.05; + } + else + { + /* + * For data type without specialized comparator, mksort is + * faster than classical qsort even there is no duplicate. So + * add 1 to dupRio for the extra benefit from no-duplicate + * values. + */ + bene += (dupRio + 1) * 0.05; + } + mkqsBene += bene; + } + + /* + * Remember duplicated value ratio of current sort key for + * calculation by next sort key + */ + if (ndist != -1) + dupRio *= (1 - ndist); + numsortkeys++; } @@ -6331,6 +6488,13 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys, *p_collations = collations; *p_nullsFirst = nullsFirst; + /* Enable mk qsort only when estimated benefit >= 0.05 */ + if (mkqsBene >= 0.05) + { + Assert(mkqsApplicable); + *mkqsApplicable = true; + } + return lefttree; } @@ -6343,16 +6507,19 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys, * 'relids' is the set of relations required by prepare_sort_from_pathkeys() */ static Sort * -make_sort_from_pathkeys(Plan *lefttree, List *pathkeys, Relids relids) +make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, + List *pathkeys, Relids relids) { int numsortkeys; AttrNumber *sortColIdx; Oid *sortOperators; Oid *collations; bool *nullsFirst; + bool mkqsApplicable; /* Compute sort column info, and adjust lefttree as needed */ - lefttree = prepare_sort_from_pathkeys(lefttree, pathkeys, + lefttree = prepare_sort_from_pathkeys(root, + lefttree, pathkeys, relids, NULL, false, @@ -6360,12 +6527,13 @@ make_sort_from_pathkeys(Plan *lefttree, List *pathkeys, Relids relids) &sortColIdx, &sortOperators, &collations, - &nullsFirst); + &nullsFirst, + &mkqsApplicable); /* Now build the Sort node */ return make_sort(lefttree, numsortkeys, sortColIdx, sortOperators, - collations, nullsFirst); + collations, nullsFirst, mkqsApplicable); } /* @@ -6388,7 +6556,8 @@ make_incrementalsort_from_pathkeys(Plan *lefttree, List *pathkeys, bool *nullsFirst; /* Compute sort column info, and adjust lefttree as needed */ - lefttree = prepare_sort_from_pathkeys(lefttree, pathkeys, + lefttree = prepare_sort_from_pathkeys(NULL, + lefttree, pathkeys, relids, NULL, false, @@ -6396,7 +6565,8 @@ make_incrementalsort_from_pathkeys(Plan *lefttree, List *pathkeys, &sortColIdx, &sortOperators, &collations, - &nullsFirst); + &nullsFirst, + NULL); /* Now build the Sort node */ return make_incrementalsort(lefttree, numsortkeys, nPresortedCols, @@ -6444,7 +6614,8 @@ make_sort_from_sortclauses(List *sortcls, Plan *lefttree) return make_sort(lefttree, numsortkeys, sortColIdx, sortOperators, - collations, nullsFirst); + collations, nullsFirst, + NULL); } /* @@ -6498,7 +6669,8 @@ make_sort_from_groupcols(List *groupcls, return make_sort(lefttree, numsortkeys, sortColIdx, sortOperators, - collations, nullsFirst); + collations, nullsFirst, + NULL); } static Material * diff --git a/src/backend/utils/sort/mk_qsort_tuple.c b/src/backend/utils/sort/mk_qsort_tuple.c index f8588df54b..cb6f409bdd 100644 --- a/src/backend/utils/sort/mk_qsort_tuple.c +++ b/src/backend/utils/sort/mk_qsort_tuple.c @@ -163,12 +163,14 @@ mkqs_compare_datum_by_shortcut(SortTuple *tuple1, tuple2->datum1, tuple2->isnull1, sortKey); +#if SIZEOF_DATUM >= 8 else if (compFuncType == MKQS_COMP_FUNC_SIGNED) ret = ApplySignedSortComparator(tuple1->datum1, tuple1->isnull1, tuple2->datum1, tuple2->isnull1, sortKey); +#endif else if (compFuncType == MKQS_COMP_FUNC_INT32) ret = ApplyInt32SortComparator(tuple1->datum1, tuple1->isnull1, @@ -387,8 +389,10 @@ mkqs_compare_tuple(SortTuple *a, SortTuple *b, Tuplesortstate *state) if (compFuncType == MKQS_COMP_FUNC_UNSIGNED) ret = qsort_tuple_unsigned_compare(a, b, state); +#if SIZEOF_DATUM >= 8 else if (compFuncType == MKQS_COMP_FUNC_SIGNED) ret = qsort_tuple_signed_compare(a, b, state); +#endif else if (compFuncType == MKQS_COMP_FUNC_INT32) ret = qsort_tuple_int32_compare(a, b, state); else diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c index 6dd21a2710..ea55113dc3 100644 --- a/src/backend/utils/sort/tuplesort.c +++ b/src/backend/utils/sort/tuplesort.c @@ -341,6 +341,9 @@ struct Tuplesortstate /* Whether multi-key quick sort is used */ bool mkqsUsed; + + /* Should multi-key quick be used or not? Determined by optimizer */ + bool mkqsApplicable; }; /* @@ -2736,6 +2739,9 @@ tuplesort_sort_memtuples(Tuplesortstate *state) * type is supported by mk qsort. (By now only Heap tuple and Btree * Index tuple are supported, and more types may be supported in * future.) + * 4. state->mkqsApplicable is true, which is determined by optimizer + * and means "mk qsort is supposed to be faster than qsort" for + * current case. * * A summary of tuple types supported by mk qsort: * @@ -2749,7 +2755,8 @@ tuplesort_sort_memtuples(Tuplesortstate *state) */ if (enable_mk_sort && state->base.nKeys > 1 && - state->base.mkqsGetDatumFunc != NULL) + state->base.mkqsGetDatumFunc != NULL && + state->mkqsApplicable) { /* * Set relevant Datum Sort Comparator according to concrete data type @@ -3275,3 +3282,9 @@ ssup_datum_int32_cmp(Datum x, Datum y, SortSupport ssup) else return 0; } + +void tuplesort_set_mkqsApplicable(Tuplesortstate *state, + bool mkqsApplicable) +{ + state->mkqsApplicable = mkqsApplicable; +} diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h index e025679f89..2e1c22701a 100644 --- a/src/include/nodes/plannodes.h +++ b/src/include/nodes/plannodes.h @@ -946,6 +946,9 @@ typedef struct Sort /* NULLS FIRST/LAST directions */ bool *nullsFirst pg_node_attr(array_size(numCols)); + + /* Should multi-key quick be used or not? Determined by optimizer */ + bool mkqsApplicable; } Sort; /* ---------------- diff --git a/src/include/utils/tuplesort.h b/src/include/utils/tuplesort.h index 60eb77ee01..cfcfdd6354 100644 --- a/src/include/utils/tuplesort.h +++ b/src/include/utils/tuplesort.h @@ -507,6 +507,8 @@ extern BrinTuple *tuplesort_getbrintuple(Tuplesortstate *state, Size *len, bool forward); extern bool tuplesort_getdatum(Tuplesortstate *state, bool forward, bool copy, Datum *val, bool *isNull, Datum *abbrev); +extern void tuplesort_set_mkqsApplicable(Tuplesortstate *state, + bool mkqsApplicable); #endif /* TUPLESORT_H */ -- 2.25.1