diff options
Diffstat (limited to 'src/backend/optimizer/plan/planner.c')
| -rw-r--r-- | src/backend/optimizer/plan/planner.c | 370 |
1 files changed, 362 insertions, 8 deletions
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index aeb83841d7a..a09f5e3866f 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -5090,6 +5090,68 @@ create_ordered_paths(PlannerInfo *root, add_path(ordered_rel, path); } + + /* + * Consider incremental sort with a gather merge on partial paths. + * + * We can also skip the entire loop when we only have a single-item + * sort_pathkeys because then we can't possibly have a presorted + * prefix of the list without having the list be fully sorted. + */ + if (enable_incrementalsort && list_length(root->sort_pathkeys) > 1) + { + ListCell *lc; + + foreach(lc, input_rel->partial_pathlist) + { + Path *input_path = (Path *) lfirst(lc); + Path *sorted_path = input_path; + bool is_sorted; + int presorted_keys; + double total_groups; + + /* + * We don't care if this is the cheapest partial path - we can't + * simply skip it, because it may be partially sorted in which + * case we want to consider adding incremental sort (instead of + * full sort, which is what happens above). + */ + + is_sorted = pathkeys_count_contained_in(root->sort_pathkeys, + input_path->pathkeys, + &presorted_keys); + + /* No point in adding incremental sort on fully sorted paths. */ + if (is_sorted) + continue; + + if (presorted_keys == 0) + continue; + + /* Since we have presorted keys, consider incremental sort. */ + sorted_path = (Path *) create_incremental_sort_path(root, + ordered_rel, + input_path, + root->sort_pathkeys, + presorted_keys, + limit_tuples); + total_groups = input_path->rows * + input_path->parallel_workers; + sorted_path = (Path *) + create_gather_merge_path(root, ordered_rel, + sorted_path, + sorted_path->pathtarget, + root->sort_pathkeys, NULL, + &total_groups); + + /* Add projection step if needed */ + if (sorted_path->pathtarget != target) + sorted_path = apply_projection_to_path(root, ordered_rel, + sorted_path, target); + + add_path(ordered_rel, sorted_path); + } + } } /* @@ -6444,10 +6506,14 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel, foreach(lc, input_rel->pathlist) { Path *path = (Path *) lfirst(lc); + Path *path_original = path; bool is_sorted; + int presorted_keys; + + is_sorted = pathkeys_count_contained_in(root->group_pathkeys, + path->pathkeys, + &presorted_keys); - is_sorted = pathkeys_contained_in(root->group_pathkeys, - path->pathkeys); if (path == cheapest_path || is_sorted) { /* Sort the cheapest-total path if it isn't already sorted */ @@ -6503,6 +6569,79 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel, Assert(false); } } + + /* + * Now we may consider incremental sort on this path, but only + * when the path is not already sorted and when incremental sort + * is enabled. + */ + if (is_sorted || !enable_incrementalsort) + continue; + + /* Restore the input path (we might have added Sort on top). */ + path = path_original; + + /* no shared prefix, no point in building incremental sort */ + if (presorted_keys == 0) + continue; + + /* + * We should have already excluded pathkeys of length 1 because + * then presorted_keys > 0 would imply is_sorted was true. + */ + Assert(list_length(root->group_pathkeys) != 1); + + path = (Path *) create_incremental_sort_path(root, + grouped_rel, + path, + root->group_pathkeys, + presorted_keys, + -1.0); + + /* Now decide what to stick atop it */ + if (parse->groupingSets) + { + consider_groupingsets_paths(root, grouped_rel, + path, true, can_hash, + gd, agg_costs, dNumGroups); + } + else if (parse->hasAggs) + { + /* + * We have aggregation, possibly with plain GROUP BY. Make + * an AggPath. + */ + add_path(grouped_rel, (Path *) + create_agg_path(root, + grouped_rel, + path, + grouped_rel->reltarget, + parse->groupClause ? AGG_SORTED : AGG_PLAIN, + AGGSPLIT_SIMPLE, + parse->groupClause, + havingQual, + agg_costs, + dNumGroups)); + } + else if (parse->groupClause) + { + /* + * We have GROUP BY without aggregation or grouping sets. + * Make a GroupPath. + */ + add_path(grouped_rel, (Path *) + create_group_path(root, + grouped_rel, + path, + parse->groupClause, + havingQual, + dNumGroups)); + } + else + { + /* Other cases should have been handled above */ + Assert(false); + } } /* @@ -6514,12 +6653,19 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel, foreach(lc, partially_grouped_rel->pathlist) { Path *path = (Path *) lfirst(lc); + Path *path_original = path; + bool is_sorted; + int presorted_keys; + + is_sorted = pathkeys_count_contained_in(root->group_pathkeys, + path->pathkeys, + &presorted_keys); /* * Insert a Sort node, if required. But there's no point in * sorting anything but the cheapest path. */ - if (!pathkeys_contained_in(root->group_pathkeys, path->pathkeys)) + if (!is_sorted) { if (path != partially_grouped_rel->cheapest_total_path) continue; @@ -6550,6 +6696,55 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel, parse->groupClause, havingQual, dNumGroups)); + + /* + * Now we may consider incremental sort on this path, but only + * when the path is not already sorted and when incremental + * sort is enabled. + */ + if (is_sorted || !enable_incrementalsort) + continue; + + /* Restore the input path (we might have added Sort on top). */ + path = path_original; + + /* no shared prefix, not point in building incremental sort */ + if (presorted_keys == 0) + continue; + + /* + * We should have already excluded pathkeys of length 1 because + * then presorted_keys > 0 would imply is_sorted was true. + */ + Assert(list_length(root->group_pathkeys) != 1); + + path = (Path *) create_incremental_sort_path(root, + grouped_rel, + path, + root->group_pathkeys, + presorted_keys, + -1.0); + + if (parse->hasAggs) + add_path(grouped_rel, (Path *) + create_agg_path(root, + grouped_rel, + path, + grouped_rel->reltarget, + parse->groupClause ? AGG_SORTED : AGG_PLAIN, + AGGSPLIT_FINAL_DESERIAL, + parse->groupClause, + havingQual, + agg_final_costs, + dNumGroups)); + else + add_path(grouped_rel, (Path *) + create_group_path(root, + grouped_rel, + path, + parse->groupClause, + havingQual, + dNumGroups)); } } } @@ -6821,6 +7016,64 @@ create_partial_grouping_paths(PlannerInfo *root, dNumPartialGroups)); } } + + /* + * Consider incremental sort on all partial paths, if enabled. + * + * We can also skip the entire loop when we only have a single-item + * group_pathkeys because then we can't possibly have a presorted + * prefix of the list without having the list be fully sorted. + */ + if (enable_incrementalsort && list_length(root->group_pathkeys) > 1) + { + foreach(lc, input_rel->pathlist) + { + Path *path = (Path *) lfirst(lc); + bool is_sorted; + int presorted_keys; + + is_sorted = pathkeys_count_contained_in(root->group_pathkeys, + path->pathkeys, + &presorted_keys); + + /* Ignore already sorted paths */ + if (is_sorted) + continue; + + if (presorted_keys == 0) + continue; + + /* Since we have presorted keys, consider incremental sort. */ + path = (Path *) create_incremental_sort_path(root, + partially_grouped_rel, + path, + root->group_pathkeys, + presorted_keys, + -1.0); + + if (parse->hasAggs) + add_path(partially_grouped_rel, (Path *) + create_agg_path(root, + partially_grouped_rel, + path, + partially_grouped_rel->reltarget, + parse->groupClause ? AGG_SORTED : AGG_PLAIN, + AGGSPLIT_INITIAL_SERIAL, + parse->groupClause, + NIL, + agg_partial_costs, + dNumPartialGroups)); + else + add_path(partially_grouped_rel, (Path *) + create_group_path(root, + partially_grouped_rel, + path, + parse->groupClause, + NIL, + dNumPartialGroups)); + } + } + } if (can_sort && cheapest_partial_path != NULL) @@ -6829,10 +7082,14 @@ create_partial_grouping_paths(PlannerInfo *root, foreach(lc, input_rel->partial_pathlist) { Path *path = (Path *) lfirst(lc); + Path *path_original = path; bool is_sorted; + int presorted_keys; + + is_sorted = pathkeys_count_contained_in(root->group_pathkeys, + path->pathkeys, + &presorted_keys); - is_sorted = pathkeys_contained_in(root->group_pathkeys, - path->pathkeys); if (path == cheapest_partial_path || is_sorted) { /* Sort the cheapest partial path, if it isn't already */ @@ -6864,6 +7121,55 @@ create_partial_grouping_paths(PlannerInfo *root, NIL, dNumPartialPartialGroups)); } + + /* + * Now we may consider incremental sort on this path, but only + * when the path is not already sorted and when incremental sort + * is enabled. + */ + if (is_sorted || !enable_incrementalsort) + continue; + + /* Restore the input path (we might have added Sort on top). */ + path = path_original; + + /* no shared prefix, not point in building incremental sort */ + if (presorted_keys == 0) + continue; + + /* + * We should have already excluded pathkeys of length 1 because + * then presorted_keys > 0 would imply is_sorted was true. + */ + Assert(list_length(root->group_pathkeys) != 1); + + path = (Path *) create_incremental_sort_path(root, + partially_grouped_rel, + path, + root->group_pathkeys, + presorted_keys, + -1.0); + + if (parse->hasAggs) + add_partial_path(partially_grouped_rel, (Path *) + create_agg_path(root, + partially_grouped_rel, + path, + partially_grouped_rel->reltarget, + parse->groupClause ? AGG_SORTED : AGG_PLAIN, + AGGSPLIT_INITIAL_SERIAL, + parse->groupClause, + NIL, + agg_partial_costs, + dNumPartialPartialGroups)); + else + add_partial_path(partially_grouped_rel, (Path *) + create_group_path(root, + partially_grouped_rel, + path, + parse->groupClause, + NIL, + dNumPartialPartialGroups)); } } @@ -6961,10 +7267,11 @@ create_partial_grouping_paths(PlannerInfo *root, static void gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel) { + ListCell *lc; Path *cheapest_partial_path; /* Try Gather for unordered paths and Gather Merge for ordered ones. */ - generate_gather_paths(root, rel, true); + generate_useful_gather_paths(root, rel, true); /* Try cheapest partial path + explicit Sort + Gather Merge. */ cheapest_partial_path = linitial(rel->partial_pathlist); @@ -6990,6 +7297,53 @@ gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel) add_path(rel, path); } + + /* + * Consider incremental sort on all partial paths, if enabled. + * + * We can also skip the entire loop when we only have a single-item + * group_pathkeys because then we can't possibly have a presorted + * prefix of the list without having the list be fully sorted. + */ + if (!enable_incrementalsort || list_length(root->group_pathkeys) == 1) + return; + + /* also consider incremental sort on partial paths, if enabled */ + foreach(lc, rel->partial_pathlist) + { + Path *path = (Path *) lfirst(lc); + bool is_sorted; + int presorted_keys; + double total_groups; + + is_sorted = pathkeys_count_contained_in(root->group_pathkeys, + path->pathkeys, + &presorted_keys); + + if (is_sorted) + continue; + + if (presorted_keys == 0) + continue; + + path = (Path *) create_incremental_sort_path(root, + rel, + path, + root->group_pathkeys, + presorted_keys, + -1.0); + + path = (Path *) + create_gather_merge_path(root, + rel, + path, + rel->reltarget, + root->group_pathkeys, + NULL, + &total_groups); + + add_path(rel, path); + } } /* @@ -7091,7 +7445,7 @@ apply_scanjoin_target_to_paths(PlannerInfo *root, * paths by doing it after the final scan/join target has been * applied. */ - generate_gather_paths(root, rel, false); + generate_useful_gather_paths(root, rel, false); /* Can't use parallel query above this level. */ rel->partial_pathlist = NIL; @@ -7245,7 +7599,7 @@ apply_scanjoin_target_to_paths(PlannerInfo *root, * one of the generated paths may turn out to be the cheapest one. */ if (rel->consider_parallel && !IS_OTHER_REL(rel)) - generate_gather_paths(root, rel, false); + generate_useful_gather_paths(root, rel, false); /* * Reassess which paths are the cheapest, now that we've potentially added |