agora inbox for [email protected]help / color / mirror / Atom feed
[PATCH 5/5] A couple more places for incremental sort 3+ messages / 2 participants [nested] [flat]
* [PATCH 5/5] A couple more places for incremental sort @ 2019-07-28 14:03 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Tomas Vondra @ 2019-07-28 14:03 UTC (permalink / raw) --- src/backend/optimizer/geqo/geqo_eval.c | 2 +- src/backend/optimizer/plan/planner.c | 218 ++++++++++++++++++++++++- 2 files changed, 216 insertions(+), 4 deletions(-) diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c index 6d897936d7..ff33acc7b6 100644 --- a/src/backend/optimizer/geqo/geqo_eval.c +++ b/src/backend/optimizer/geqo/geqo_eval.c @@ -274,7 +274,7 @@ merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, int num_gene, * grouping_planner). */ if (old_clump->size + new_clump->size < num_gene) - generate_gather_paths(root, joinrel, false); + generate_useful_gather_paths(root, joinrel, false); /* Find and save the cheapest paths for this joinrel */ set_cheapest(joinrel); diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 84ed69ec5e..15223017c0 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -5070,6 +5070,67 @@ create_ordered_paths(PlannerInfo *root, add_path(ordered_rel, path); } + + /* + * Consider incremental sort with a gather merge on partial paths. + * + * XXX This is probably duplicate with the paths we already generate + * in generate_useful_gather_paths in apply_scanjoin_target_to_paths. + */ + if (enable_incrementalsort) + { + 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 incremental sort on top + * of it (instead of full sort, which is what happens above). + */ + + is_sorted = pathkeys_common_contained_in(root->sort_pathkeys, + input_path->pathkeys, + &presorted_keys); + + /* also ignore already sorted paths */ + if (is_sorted) + continue; + + if (presorted_keys == 0) + continue; + + /* Also 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); + } + } } /* @@ -6570,12 +6631,18 @@ 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_contained_in(root->group_pathkeys, + path->pathkeys); /* * 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; @@ -6606,6 +6673,56 @@ 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 addes Sort on top). */ + path = path_original; + + is_sorted = pathkeys_common_contained_in(root->group_pathkeys, + path->pathkeys, + &presorted_keys); + + /* We've already skipped fully sorted paths above. */ + Assert(!is_sorted); + + /* no shared prefix, not point in building incremental sort */ + if (presorted_keys == 0) + continue; + + 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)); } } } @@ -6875,6 +6992,60 @@ create_partial_grouping_paths(PlannerInfo *root, dNumPartialGroups)); } } + + /* + * Also consider incremental sort on all partially sorted paths. + */ + if (enable_incrementalsort) + { + foreach(lc, input_rel->pathlist) + { + Path *path = (Path *) lfirst(lc); + bool is_sorted; + int presorted_keys; + + is_sorted = pathkeys_common_contained_in(root->group_pathkeys, + path->pathkeys, + &presorted_keys); + + /* also ignore already sorted paths */ + if (is_sorted) + continue; + + if (presorted_keys == 0) + continue; + + /* add 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) @@ -7067,10 +7238,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); @@ -7096,6 +7268,46 @@ gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel) add_path(rel, path); } + + if (!enable_incrementalsort) + 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_common_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); + } } /* @@ -7197,7 +7409,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; -- 2.21.1 --xvcuvgto6w2bcqjv-- ^ permalink raw reply [nested|flat] 3+ messages in thread
* [PATCH 7/8] A couple more places for incremental sort @ 2019-07-28 14:03 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Tomas Vondra @ 2019-07-28 14:03 UTC (permalink / raw) --- src/backend/optimizer/geqo/geqo_eval.c | 2 +- src/backend/optimizer/plan/planner.c | 220 ++++++++++++++++++++++++- 2 files changed, 217 insertions(+), 5 deletions(-) diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c index 6d897936d7..ff33acc7b6 100644 --- a/src/backend/optimizer/geqo/geqo_eval.c +++ b/src/backend/optimizer/geqo/geqo_eval.c @@ -274,7 +274,7 @@ merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, int num_gene, * grouping_planner). */ if (old_clump->size + new_clump->size < num_gene) - generate_gather_paths(root, joinrel, false); + generate_useful_gather_paths(root, joinrel, false); /* Find and save the cheapest paths for this joinrel */ set_cheapest(joinrel); diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 46dc355af3..2880fcabe8 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -5080,6 +5080,67 @@ create_ordered_paths(PlannerInfo *root, add_path(ordered_rel, path); } + + /* + * Consider incremental sort with a gather merge on partial paths. + * + * XXX This is probably duplicate with the paths we already generate + * in generate_useful_gather_paths in apply_scanjoin_target_to_paths. + */ + if (enable_incrementalsort) + { + 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 incremental sort on top of + * it (instead of full sort, which is what happens above). + */ + + is_sorted = pathkeys_common_contained_in(root->sort_pathkeys, + input_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. */ + 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); + } + } } /* @@ -6580,12 +6641,18 @@ 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_contained_in(root->group_pathkeys, + path->pathkeys); /* * 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; @@ -6616,6 +6683,56 @@ 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; + + is_sorted = pathkeys_common_contained_in(root->group_pathkeys, + path->pathkeys, + &presorted_keys); + + /* We've already skipped fully sorted paths above. */ + Assert(!is_sorted); + + /* no shared prefix, not point in building incremental sort */ + if (presorted_keys == 0) + continue; + + 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)); } } } @@ -6887,6 +7004,60 @@ create_partial_grouping_paths(PlannerInfo *root, dNumPartialGroups)); } } + + /* + * Also consider incremental sort on all partially sorted paths. + */ + if (enable_incrementalsort) + { + foreach(lc, input_rel->pathlist) + { + Path *path = (Path *) lfirst(lc); + bool is_sorted; + int presorted_keys; + + is_sorted = pathkeys_common_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) @@ -6951,10 +7122,10 @@ create_partial_grouping_paths(PlannerInfo *root, /* We've already skipped fully sorted paths above. */ Assert(!is_sorted); - /* no shared prefix, not point in building incremental sort */ if (presorted_keys == 0) continue; + /* Since we have presorted keys, consider incremental sort. */ path = (Path *) create_incremental_sort_path(root, partially_grouped_rel, path, @@ -7079,10 +7250,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); @@ -7108,6 +7280,46 @@ gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel) add_path(rel, path); } + + if (!enable_incrementalsort) + 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_common_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); + } } /* @@ -7209,7 +7421,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; -- 2.21.1 --dfcjsgdukgytabqd Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="v39-0008-fix.patch" ^ permalink raw reply [nested|flat] 3+ messages in thread
* [PATCH 2/5] Add va_header field to the varattrib_4b union. @ 2026-03-11 13:53 Antonin Houska <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Antonin Houska @ 2026-03-11 13:53 UTC (permalink / raw) Since VARSIZE_ANY() may call VARSIZE_4B(), it's possible that the compiler (when invoked with -Warray-bounds) complains if the argument of VARSIZE_ANY() is actually smaller than what VARSIZE_4B() expects. With the new field, VARSIZE_4B() can check the size w/o dereferencing varattrib_4b pointer. The problem does not exist in the tree at the moment since the current users of VARSIZE_ANY() pass a pointer to a dynamically allocated memory, so the compiler has no idea about the memory available. However, in an upcoming patch, it makes sense to pass a pointer to a local variable of "varlena" type. In such a case, the compiler warning might appear because sizeof(varlena) is lower than sizeof(varattrib_4b). --- src/include/varatt.h | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) diff --git a/src/include/varatt.h b/src/include/varatt.h index 000bdf33b92..c54d5160c22 100644 --- a/src/include/varatt.h +++ b/src/include/varatt.h @@ -137,6 +137,10 @@ typedef union * compression method; see va_extinfo */ char va_data[FLEXIBLE_ARRAY_MEMBER]; /* Compressed data */ } va_compressed; + uint32 va_header; /* Without this, compiler might raise warning + * (-Warray-bounds) if the argument of + * VARSIZE_ANY() is smaller than + * varattrib_4b */ } varattrib_4b; typedef struct @@ -207,7 +211,7 @@ typedef struct /* VARSIZE_4B() should only be used on known-aligned data */ #define VARSIZE_4B(PTR) \ - (((const varattrib_4b *) (PTR))->va_4byte.va_header & 0x3FFFFFFF) + (*((const uint32 *) (PTR)) & 0x3FFFFFFF) #define VARSIZE_1B(PTR) \ (((const varattrib_1b *) (PTR))->va_header & 0x7F) #define VARTAG_1B_E(PTR) \ @@ -240,7 +244,7 @@ typedef struct /* VARSIZE_4B() should only be used on known-aligned data */ #define VARSIZE_4B(PTR) \ - ((((const varattrib_4b *) (PTR))->va_4byte.va_header >> 2) & 0x3FFFFFFF) + ((*((const uint32 *) (PTR)) >> 2) & 0x3FFFFFFF) #define VARSIZE_1B(PTR) \ ((((const varattrib_1b *) (PTR))->va_header >> 1) & 0x7F) #define VARTAG_1B_E(PTR) \ -- 2.47.3 --=-=-= Content-Type: text/plain Content-Disposition: attachment; filename=v41-0003-Add-CONCURRENTLY-option-to-REPACK-command.patch ^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2026-03-11 13:53 UTC | newest] Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2019-07-28 14:03 [PATCH 5/5] A couple more places for incremental sort Tomas Vondra <[email protected]> 2019-07-28 14:03 [PATCH 7/8] A couple more places for incremental sort Tomas Vondra <[email protected]> 2026-03-11 13:53 [PATCH 2/5] Add va_header field to the varattrib_4b union. Antonin Houska <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox