diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 5947e5b..d8a17a0 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -98,11 +98,13 @@ static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid); static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid, Oid indexid, List *indexqual, List *indexqualorig, List *indexorderby, List *indexorderbyorig, + List *pathkeys, bool uniquely_ordered, ScanDirection indexscandir); static IndexOnlyScan *make_indexonlyscan(List *qptlist, List *qpqual, Index scanrelid, Oid indexid, List *indexqual, List *indexorderby, List *indextlist, + List *pathkeys, bool uniquely_ordered, ScanDirection indexscandir); static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indexid, List *indexqual, @@ -150,8 +152,8 @@ static MergeJoin *make_mergejoin(List *tlist, bool *mergenullsfirst, Plan *lefttree, Plan *righttree, JoinType jointype); -static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols, - AttrNumber *sortColIdx, Oid *sortOperators, +static Sort *make_sort(PlannerInfo *root, Plan *lefttree, List *pathkeys, + int numCols, AttrNumber *sortColIdx, Oid *sortOperators, Oid *collations, bool *nullsFirst, double limit_tuples); static Plan *prepare_sort_from_pathkeys(PlannerInfo *root, @@ -750,6 +752,8 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path) plan->qual = NIL; plan->lefttree = NULL; plan->righttree = NULL; + plan->pathkeys = pathkeys; + plan->is_unique = false; /* Compute sort column info, and adjust MergeAppend's tlist as needed */ (void) prepare_sort_from_pathkeys(root, plan, pathkeys, @@ -810,7 +814,7 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path) /* Now, insert a Sort node if subplan isn't sufficiently ordered */ if (!pathkeys_contained_in(pathkeys, subpath->pathkeys)) - subplan = (Plan *) make_sort(root, subplan, numsortkeys, + subplan = (Plan *) make_sort(root, subplan, pathkeys, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst, best_path->limit_tuples); @@ -1263,6 +1267,8 @@ create_indexscan_plan(PlannerInfo *root, fixed_indexquals, fixed_indexorderbys, best_path->indexinfo->indextlist, + best_path->path.pathkeys, + false, best_path->indexscandir); else scan_plan = (Scan *) make_indexscan(tlist, @@ -1273,6 +1279,8 @@ create_indexscan_plan(PlannerInfo *root, stripped_indexquals, fixed_indexorderbys, indexorderbys, + best_path->path.pathkeys, + false, best_path->indexscandir); copy_path_costsize(&scan_plan->plan, &best_path->path); @@ -3245,6 +3253,8 @@ make_indexscan(List *qptlist, List *indexqualorig, List *indexorderby, List *indexorderbyorig, + List *pathkeys, + bool uniquely_ordered, ScanDirection indexscandir) { IndexScan *node = makeNode(IndexScan); @@ -3255,6 +3265,8 @@ make_indexscan(List *qptlist, plan->qual = qpqual; plan->lefttree = NULL; plan->righttree = NULL; + plan->pathkeys = pathkeys; + plan->is_unique = uniquely_ordered; node->scan.scanrelid = scanrelid; node->indexid = indexid; node->indexqual = indexqual; @@ -3274,6 +3286,8 @@ make_indexonlyscan(List *qptlist, List *indexqual, List *indexorderby, List *indextlist, + List *pathkeys, + bool uniquely_ordered, ScanDirection indexscandir) { IndexOnlyScan *node = makeNode(IndexOnlyScan); @@ -3284,6 +3298,8 @@ make_indexonlyscan(List *qptlist, plan->qual = qpqual; plan->lefttree = NULL; plan->righttree = NULL; + plan->pathkeys = pathkeys; + plan->is_unique = uniquely_ordered; node->scan.scanrelid = scanrelid; node->indexid = indexid; node->indexqual = indexqual; @@ -3753,8 +3769,8 @@ make_mergejoin(List *tlist, * limit_tuples is as for cost_sort (in particular, pass -1 if no limit) */ static Sort * -make_sort(PlannerInfo *root, Plan *lefttree, int numCols, - AttrNumber *sortColIdx, Oid *sortOperators, +make_sort(PlannerInfo *root, Plan *lefttree, List *pathkeys, + int numCols, AttrNumber *sortColIdx, Oid *sortOperators, Oid *collations, bool *nullsFirst, double limit_tuples) { @@ -3776,6 +3792,8 @@ make_sort(PlannerInfo *root, Plan *lefttree, int numCols, plan->qual = NIL; plan->lefttree = lefttree; plan->righttree = NULL; + plan->pathkeys = pathkeys; + plan->is_unique = false; node->numCols = numCols; node->sortColIdx = sortColIdx; node->sortOperators = sortOperators; @@ -4125,7 +4143,7 @@ make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys, &nullsFirst); /* Now build the Sort node */ - return make_sort(root, lefttree, numsortkeys, + return make_sort(root, lefttree, pathkeys, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst, limit_tuples); } @@ -4147,6 +4165,7 @@ make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree) Oid *sortOperators; Oid *collations; bool *nullsFirst; + List *pathkeys; /* Convert list-ish representation to arrays wanted by executor */ numsortkeys = list_length(sortcls); @@ -4168,7 +4187,9 @@ make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree) numsortkeys++; } - return make_sort(root, lefttree, numsortkeys, + pathkeys = make_pathkeys_for_sortclauses(root, sortcls, sub_tlist); + + return make_sort(root, lefttree, pathkeys, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst, -1.0); } @@ -4199,6 +4220,7 @@ make_sort_from_groupcols(PlannerInfo *root, Oid *sortOperators; Oid *collations; bool *nullsFirst; + List *pathkeys; /* Convert list-ish representation to arrays wanted by executor */ numsortkeys = list_length(groupcls); @@ -4220,10 +4242,17 @@ make_sort_from_groupcols(PlannerInfo *root, sortOperators[numsortkeys] = grpcl->sortop; collations[numsortkeys] = exprCollation((Node *) tle->expr); nullsFirst[numsortkeys] = grpcl->nulls_first; + + /* This tlist should not be bound with any other orderig clause */ + Assert(tle->ressortgroupref == 0); + tle->ressortgroupref = grpcl->tleSortGroupRef; + numsortkeys++; } - return make_sort(root, lefttree, numsortkeys, + pathkeys = make_pathkeys_for_sortclauses(root, groupcls, sub_tlist); + + return make_sort(root, lefttree, pathkeys, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst, -1.0); } @@ -4339,6 +4368,16 @@ make_agg(PlannerInfo *root, List *tlist, List *qual, plan->lefttree = lefttree; plan->righttree = NULL; + /* + * We can safely assume that the lefttree and therefore the result is + * sorted on group pathkeys and unique if given aggstrategy is AGG_SORTED. + */ + if (node->aggstrategy == AGG_SORTED) + plan->pathkeys = root->group_pathkeys; + else + plan->pathkeys = NIL; + plan->is_unique = true; + return node; } @@ -4448,6 +4487,13 @@ make_group(PlannerInfo *root, plan->lefttree = lefttree; plan->righttree = NULL; + /* + * We assume that lefttree is ordered on the same pathkeys with that this + * group node wants. + */ + plan->pathkeys = lefttree->pathkeys; + plan->is_unique = true; + return node; } @@ -4486,6 +4532,8 @@ make_unique(Plan *lefttree, List *distinctList) plan->qual = NIL; plan->lefttree = lefttree; plan->righttree = NULL; + plan->pathkeys = lefttree->pathkeys; + plan->is_unique = true; /* * convert SortGroupClause list into arrays of attr indexes and equality @@ -4669,6 +4717,8 @@ make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount, plan->qual = NIL; plan->lefttree = lefttree; plan->righttree = NULL; + plan->pathkeys = lefttree->pathkeys; + plan->is_unique = lefttree->is_unique; node->limitOffset = limitOffset; node->limitCount = limitCount; @@ -4717,6 +4767,10 @@ make_result(PlannerInfo *root, plan->qual = NIL; plan->lefttree = subplan; plan->righttree = NULL; + + /* this plan emits at most one row when subplan is NULL */ + if (subplan == NULL) plan->is_unique = true; + node->resconstantqual = resconstantqual; return node; diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index d8aa35d..a09d38f 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -1011,6 +1011,19 @@ inheritance_planner(PlannerInfo *root) SS_assign_special_param(root)); } +static bool +plan_is_ordered(Plan *plan, List *pathkeys) +{ + if (pathkeys_contained_in(pathkeys, plan->pathkeys)) + return true; + + if (plan->pathkeys && plan->is_unique && + pathkeys_contained_in(plan->pathkeys, pathkeys)) + return true; + + return false; +} + /*-------------------- * grouping_planner * Perform planning steps related to grouping, aggregation, etc. @@ -1039,7 +1052,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) int64 count_est = 0; double limit_tuples = -1.0; Plan *result_plan; - List *current_pathkeys; double dNumGroups = 0; bool use_hashed_distinct = false; bool tested_hashed_distinct = false; @@ -1081,15 +1093,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) &set_sortclauses); /* - * Calculate pathkeys representing the sort order (if any) of the set - * operation's result. We have to do this before overwriting the sort - * key information... - */ - current_pathkeys = make_pathkeys_for_sortclauses(root, - set_sortclauses, - result_plan->targetlist); - - /* * We should not need to call preprocess_targetlist, since we must be * in a SELECT query node. Instead, use the targetlist returned by * plan_set_operations (since this tells whether it returned any @@ -1442,15 +1445,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) tlist, &agg_costs, best_path); - if (result_plan != NULL) - { - /* - * optimize_minmax_aggregates generated the full plan, with the - * right tlist, and it has no sort order. - */ - current_pathkeys = NIL; - } - else + if (result_plan == NULL) { /* * Normal case --- create a plan according to query_planner's @@ -1459,11 +1454,10 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) bool need_sort_for_grouping = false; result_plan = create_plan(root, best_path); - current_pathkeys = best_path->pathkeys; /* Detect if we'll need an explicit sort for grouping */ if (parse->groupClause && !use_hashed_grouping && - !pathkeys_contained_in(root->group_pathkeys, current_pathkeys)) + !plan_is_ordered(result_plan, root->group_pathkeys)) { need_sort_for_grouping = true; @@ -1541,37 +1535,20 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) extract_grouping_ops(parse->groupClause), numGroups, result_plan); - /* Hashed aggregation produces randomly-ordered results */ - current_pathkeys = NIL; } else if (parse->hasAggs) { /* Plain aggregate plan --- sort if needed */ AggStrategy aggstrategy; - if (parse->groupClause) + aggstrategy = parse->groupClause ? AGG_SORTED : AGG_PLAIN; + if (aggstrategy == AGG_SORTED && need_sort_for_grouping) { - if (need_sort_for_grouping) - { - result_plan = (Plan *) - make_sort_from_groupcols(root, - parse->groupClause, - groupColIdx, - result_plan); - current_pathkeys = root->group_pathkeys; - } - aggstrategy = AGG_SORTED; - - /* - * The AGG node will not change the sort ordering of its - * groups, so current_pathkeys describes the result too. - */ - } - else - { - aggstrategy = AGG_PLAIN; - /* Result will be only one row anyway; no sort order */ - current_pathkeys = NIL; + result_plan = (Plan *) + make_sort_from_groupcols(root, + parse->groupClause, + groupColIdx, + result_plan); } result_plan = (Plan *) make_agg(root, @@ -1601,7 +1578,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) parse->groupClause, groupColIdx, result_plan); - current_pathkeys = root->group_pathkeys; } result_plan = (Plan *) make_group(root, @@ -1612,7 +1588,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) extract_grouping_ops(parse->groupClause), dNumGroups, result_plan); - /* The Group node won't change sort ordering */ } else if (root->hasHavingQual) { @@ -1722,13 +1697,14 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) result_plan, window_pathkeys, -1.0); - if (!pathkeys_contained_in(window_pathkeys, - current_pathkeys)) - { - /* we do indeed need to sort */ + + /* + * we do indeed need to sort if result_plan is not ordered + * on window_pathkeys + */ + if (!plan_is_ordered(result_plan, window_pathkeys)) result_plan = (Plan *) sort_plan; - current_pathkeys = window_pathkeys; - } + /* In either case, extract the per-column information */ get_column_info_for_window(root, wc, tlist, sort_plan->numCols, @@ -1792,12 +1768,12 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) long numDistinctRows; /* - * If there was grouping or aggregation, use the current number of - * rows as the estimated number of DISTINCT rows (ie, assume the - * result was already mostly unique). If not, use the number of + * If result_plan emits already distinct'ed rows, use the current + * number of rows as the estimated number of DISTINCT rows (ie, assume + * the result was already unique). If not, use the number of * distinct-groups calculated previously. */ - if (parse->groupClause || root->hasHavingQual || parse->hasAggs) + if (result_plan->is_unique) dNumDistinctRows = result_plan->plan_rows; else dNumDistinctRows = dNumGroups; @@ -1822,7 +1798,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) result_plan->total_cost, result_plan->startup_cost, result_plan->total_cost, - current_pathkeys, + result_plan->pathkeys, dNumDistinctRows); } @@ -1840,8 +1816,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) extract_grouping_ops(parse->distinctClause), numDistinctRows, result_plan); - /* Hashed aggregation produces randomly-ordered results */ - current_pathkeys = NIL; } else { @@ -1865,29 +1839,23 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) else needed_pathkeys = root->distinct_pathkeys; - if (!pathkeys_contained_in(needed_pathkeys, current_pathkeys)) + if (!plan_is_ordered(result_plan, needed_pathkeys)) { - if (list_length(root->distinct_pathkeys) >= - list_length(root->sort_pathkeys)) - current_pathkeys = root->distinct_pathkeys; - else - { - current_pathkeys = root->sort_pathkeys; - /* Assert checks that parser didn't mess up... */ - Assert(pathkeys_contained_in(root->distinct_pathkeys, - current_pathkeys)); - } - + /* Assert checks that parser didn't mess up... */ + Assert(pathkeys_contained_in(root->distinct_pathkeys, + needed_pathkeys)); + Assert(pathkeys_contained_in(root->sort_pathkeys, + needed_pathkeys)); result_plan = (Plan *) make_sort_from_pathkeys(root, result_plan, - current_pathkeys, + needed_pathkeys, -1.0); } - result_plan = (Plan *) make_unique(result_plan, - parse->distinctClause); + if (!result_plan->is_unique) + result_plan = (Plan *) make_unique(result_plan, + parse->distinctClause); result_plan->plan_rows = dNumDistinctRows; - /* The Unique node won't change sort ordering */ } } @@ -1897,13 +1865,12 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) */ if (parse->sortClause) { - if (!pathkeys_contained_in(root->sort_pathkeys, current_pathkeys)) + if (!plan_is_ordered(result_plan, root->sort_pathkeys)) { result_plan = (Plan *) make_sort_from_pathkeys(root, result_plan, root->sort_pathkeys, limit_tuples); - current_pathkeys = root->sort_pathkeys; } } @@ -1914,18 +1881,10 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) * ModifyTable node instead.) */ if (parse->rowMarks) - { result_plan = (Plan *) make_lockrows(result_plan, root->rowMarks, SS_assign_special_param(root)); - /* - * The result can no longer be assumed sorted, since locking might - * cause the sort key columns to be replaced with new values. - */ - current_pathkeys = NIL; - } - /* * Finally, if there is a LIMIT/OFFSET clause, add the LIMIT node. */ @@ -1942,7 +1901,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) * Return the actual output ordering in query_pathkeys for possible use by * an outer query level. */ - root->query_pathkeys = current_pathkeys; + root->query_pathkeys = result_plan->pathkeys; return result_plan; } diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h index 44ea0b7..ced07d9 100644 --- a/src/include/nodes/plannodes.h +++ b/src/include/nodes/plannodes.h @@ -101,6 +101,8 @@ typedef struct Plan */ double plan_rows; /* number of rows plan is expected to emit */ int plan_width; /* average row width in bytes */ + List *pathkeys; /* ordered on this pathkeys if any */ + bool is_unique; /* emits unique result */ /* * Common structural data for all Plan types.