From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: James Coleman <jtc331@gmail.com>
Cc: Peter Geoghegan <pg@bowt.ie>
Cc: Simon Riggs <simon@2ndquadrant.com>
Cc: Rafia Sabih <rafia.pghackers@gmail.com>
Cc: Shaun Thomas <shaun.thomas@2ndquadrant.com>
Cc: Dmitry Dolgov <9erthalion6@gmail.com>
Cc: Alexander Korotkov <a.korotkov@postgrespro.ru>
Cc: Tom Lane <tgl@sss.pgh.pa.us>
Cc: PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>
Subject: Re: [PATCH] Incremental sort (was: PoC: Partial sort)
Date: Tue, 9 Jul 2019 14:11:25 +0200
Message-ID: <20190709121125.5bpaxgtd5wl7aghy@development> (raw)
In-Reply-To: <20190709013703.3mbdhsv2gyxtjc42@development>
References: <CAAaqYe8PVSO3dzysZZ-RB8HRMAZ_JMOPwW--veY9ZEuTCcbe8A@mail.gmail.com>
<20190707123449.w3b2vetwv4y42evj@development>
<CAAaqYe9gvGoo=wZMqMjmOrMu2m_cPyPEsbxZnsMOBSDn=VN14Q@mail.gmail.com>
<20190707210205.4lxkbq6tpjcj2hlk@development>
<CAAaqYe9LWNYik9E0ndiNc_AQ9TzEFKPSSs-0HU8PjOJXWm9Ldw@mail.gmail.com>
<20190708135933.oco3gyloeacdj7yy@development>
<CAAaqYe_5+as+Mn7MedyVCb3WBXLfhBucEPFHa+g_sN4yXPfBtQ@mail.gmail.com>
<20190708145853.x2doaqcyj3enol2e@development>
<CAAaqYe_VMCbq2+mNsMr8NtmDCBWNfHHDHHYppM12JDkudQjPhQ@mail.gmail.com>
<20190709013703.3mbdhsv2gyxtjc42@development>
On Tue, Jul 09, 2019 at 03:37:03AM +0200, Tomas Vondra wrote:
>
> ...
>
>Notice that cost of the second plan is almost double the first one. That
>means 0004 does not even generate the first plan, i.e. there are cases
>where we don't try to add the explicit sort before passing the path to
>generate_gather_paths().
>
>And I think I know why is that - while gather_grouping_paths() tries to
>add explicit sort below the gather merge, there are other places that
>call generate_gather_paths() that don't do that. In this case it's
>probably apply_scanjoin_target_to_paths() which simply builds
>
> parallel (seq|index) scan + gather merge
>
>and that's it. The problem is likely the same - the code does not know
>which pathkeys are "interesting" at that point. We probably need to
>teach planner to do this.
>
I've looked into this again, and yes - that's the reason. I've added
generate_useful_gather_paths() which is a wrapper on top of
generate_gather_paths(). It essentially does what 0001 patch did directly
in generate_gather_paths() so it's more like create_grouping_paths().
And that does the trick - we now generate the cheaper paths, and I don't
see any crashes in regression tests etc.
I still suspect we already have code doing similar checks whether pathkeys
might be useful somewhere. I've looked into pathkeys.c and elsewhere but
no luck.
Attached is a slightly modified patch series:
1) 0001 considers incremental sort paths in various places (adds the new
generate_useful_gather_paths and modifies places calling create_sort_path)
2) 0002 and 0003 are fixes I mentioned before
3) 0004 adds a new GUC force_incremental_sort that (when set to 'on')
tries to nudge the optimizer into using incremental sort by essentially
making it free (i.e. using startup/total costs of the subpath). I've found
this useful when trying to force incremental sorts into plans where it may
not be the best strategy.
I won't have time to hack on this over the next ~2 weeks, but I'll try to
respond to questions when possible.
>
>FWIW tweaking all the create_sort_path() places to also consider adding
>incremental sort is a bit tedious and invasive, and it almost doubles
>the amount of repetitive code. It's OK for experiment like this, but we
>should try handling this in a nicer way (move to a separate function
>that does both, or something like that).
>
This definitely needs more work. We need to refactor it in some way, e.g.
have a function that would consider both explicit sort (on the cheapest
path) and incremental sort (on all paths), and call it from all those
places. Haven't tried it, though.
There's also a couple more places where we do create_sort_path() and don't
consider incremental sort yet - window functions, distinct etc.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
From e7e97daf447a91e090809be4f07a5eee650eb5e7 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Tue, 9 Jul 2019 00:12:45 +0200
Subject: [PATCH 1/4] fix pathkey processing in generate_gather_paths
---
src/backend/optimizer/path/allpaths.c | 365 +++++++++++++++++++++++-
src/backend/optimizer/plan/createplan.c | 10 +-
src/backend/optimizer/plan/planner.c | 301 ++++++++++++++++++-
src/include/optimizer/paths.h | 2 +
4 files changed, 673 insertions(+), 5 deletions(-)
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.cindex 3efc807164..acddbef064 100644--- a/src/backend/optimizer/path/allpaths.c+++ b/src/backend/optimizer/path/allpaths.c@@ -556,7 +556,7 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
*/
if (rel->reloptkind == RELOPT_BASEREL &&
bms_membership(root->all_baserels) != BMS_SINGLETON)
- generate_gather_paths(root, rel, false);+ generate_useful_gather_paths(root, rel, false);
/* Now find the cheapest of the paths for this rel */
set_cheapest(rel);
@@ -2730,6 +2730,367 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
}
}
+/*+ * Find an equivalence class member expression, all of whose Vars, come from+ * the indicated relation.+ */+static Expr *+find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel)+{+ ListCell *lc_em;++ foreach(lc_em, ec->ec_members)+ {+ EquivalenceMember *em = lfirst(lc_em);++ if (bms_is_subset(em->em_relids, rel->relids) &&+ !bms_is_empty(em->em_relids))+ {+ /*+ * If there is more than one equivalence member whose Vars are+ * taken entirely from this relation, we'll be content to choose+ * any one of those.+ */+ return em->em_expr;+ }+ }++ /* We didn't find any suitable equivalence class expression */+ return NULL;+}++/*+ * get_useful_ecs_for_relation+ * Determine which EquivalenceClasses might be involved in useful+ * orderings of this relation.+ *+ * This function is in some respects a mirror image of the core function+ * pathkeys_useful_for_merging: for a regular table, we know what indexes+ * we have and want to test whether any of them are useful. For a foreign+ * table, we don't know what indexes are present on the remote side but+ * want to speculate about which ones we'd like to use if they existed.+ *+ * This function returns a list of potentially-useful equivalence classes,+ * but it does not guarantee that an EquivalenceMember exists which contains+ * Vars only from the given relation. For example, given ft1 JOIN t1 ON+ * ft1.x + t1.x = 0, this function will say that the equivalence class+ * containing ft1.x + t1.x is potentially useful. Supposing ft1 is remote and+ * t1 is local (or on a different server), it will turn out that no useful+ * ORDER BY clause can be generated. It's not our job to figure that out+ * here; we're only interested in identifying relevant ECs.+ */+static List *+get_useful_ecs_for_relation(PlannerInfo *root, RelOptInfo *rel)+{+ List *useful_eclass_list = NIL;+ ListCell *lc;+ Relids relids;++ /*+ * First, consider whether any active EC is potentially useful for a merge+ * join against this relation.+ */+ if (rel->has_eclass_joins)+ {+ foreach(lc, root->eq_classes)+ {+ EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc);++ if (eclass_useful_for_merging(root, cur_ec, rel))+ useful_eclass_list = lappend(useful_eclass_list, cur_ec);+ }+ }++ /*+ * Next, consider whether there are any non-EC derivable join clauses that+ * are merge-joinable. If the joininfo list is empty, we can exit+ * quickly.+ */+ if (rel->joininfo == NIL)+ return useful_eclass_list;++ /* If this is a child rel, we must use the topmost parent rel to search. */+ if (IS_OTHER_REL(rel))+ {+ Assert(!bms_is_empty(rel->top_parent_relids));+ relids = rel->top_parent_relids;+ }+ else+ relids = rel->relids;++ /* Check each join clause in turn. */+ foreach(lc, rel->joininfo)+ {+ RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);++ /* Consider only mergejoinable clauses */+ if (restrictinfo->mergeopfamilies == NIL)+ continue;++ /* Make sure we've got canonical ECs. */+ update_mergeclause_eclasses(root, restrictinfo);++ /*+ * restrictinfo->mergeopfamilies != NIL is sufficient to guarantee+ * that left_ec and right_ec will be initialized, per comments in+ * distribute_qual_to_rels.+ *+ * We want to identify which side of this merge-joinable clause+ * contains columns from the relation produced by this RelOptInfo. We+ * test for overlap, not containment, because there could be extra+ * relations on either side. For example, suppose we've got something+ * like ((A JOIN B ON A.x = B.x) JOIN C ON A.y = C.y) LEFT JOIN D ON+ * A.y = D.y. The input rel might be the joinrel between A and B, and+ * we'll consider the join clause A.y = D.y. relids contains a+ * relation not involved in the join class (B) and the equivalence+ * class for the left-hand side of the clause contains a relation not+ * involved in the input rel (C). Despite the fact that we have only+ * overlap and not containment in either direction, A.y is potentially+ * useful as a sort column.+ *+ * Note that it's even possible that relids overlaps neither side of+ * the join clause. For example, consider A LEFT JOIN B ON A.x = B.x+ * AND A.x = 1. The clause A.x = 1 will appear in B's joininfo list,+ * but overlaps neither side of B. In that case, we just skip this+ * join clause, since it doesn't suggest a useful sort order for this+ * relation.+ */+ if (bms_overlap(relids, restrictinfo->right_ec->ec_relids))+ useful_eclass_list = list_append_unique_ptr(useful_eclass_list,+ restrictinfo->right_ec);+ else if (bms_overlap(relids, restrictinfo->left_ec->ec_relids))+ useful_eclass_list = list_append_unique_ptr(useful_eclass_list,+ restrictinfo->left_ec);+ }++ return useful_eclass_list;+}++/*+ * get_useful_pathkeys_for_relation+ * Determine which orderings of a relation might be useful.+ *+ * Getting data in sorted order can be useful either because the requested+ * order matches the final output ordering for the overall query we're+ * planning, or because it enables an efficient merge join. Here, we try+ * to figure out which pathkeys to consider.+ */+static List *+get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel)+{+ List *useful_pathkeys_list = NIL;+ List *useful_eclass_list;+ EquivalenceClass *query_ec = NULL;+ ListCell *lc;++ /*+ * Pushing the query_pathkeys to the remote server is always worth+ * considering, because it might let us avoid a local sort.+ */+ if (root->query_pathkeys)+ {+ bool query_pathkeys_ok = true;++ foreach(lc, root->query_pathkeys)+ {+ PathKey *pathkey = (PathKey *) lfirst(lc);+ EquivalenceClass *pathkey_ec = pathkey->pk_eclass;+ Expr *em_expr;++ /*+ * The planner and executor don't have any clever strategy for+ * taking data sorted by a prefix of the query's pathkeys and+ * getting it to be sorted by all of those pathkeys. We'll just+ * end up resorting the entire data set. So, unless we can push+ * down all of the query pathkeys, forget it.+ *+ * is_foreign_expr would detect volatile expressions as well, but+ * checking ec_has_volatile here saves some cycles.+ */+ if (pathkey_ec->ec_has_volatile ||+ !(em_expr = find_em_expr_for_rel(pathkey_ec, rel)))+ {+ query_pathkeys_ok = false;+ break;+ }+ }++ if (query_pathkeys_ok)+ useful_pathkeys_list = list_make1(list_copy(root->query_pathkeys));+ }++ /* Get the list of interesting EquivalenceClasses. */+ useful_eclass_list = get_useful_ecs_for_relation(root, rel);++ /* Extract unique EC for query, if any, so we don't consider it again. */+ if (list_length(root->query_pathkeys) == 1)+ {+ PathKey *query_pathkey = linitial(root->query_pathkeys);++ query_ec = query_pathkey->pk_eclass;+ }++ /*+ * As a heuristic, the only pathkeys we consider here are those of length+ * one. It's surely possible to consider more, but since each one we+ * choose to consider will generate a round-trip to the remote side, we+ * need to be a bit cautious here. It would sure be nice to have a local+ * cache of information about remote index definitions...+ */+ foreach(lc, useful_eclass_list)+ {+ EquivalenceClass *cur_ec = lfirst(lc);+ Expr *em_expr;+ PathKey *pathkey;++ /* If redundant with what we did above, skip it. */+ if (cur_ec == query_ec)+ continue;++ /* If no pushable expression for this rel, skip it. */+ em_expr = find_em_expr_for_rel(cur_ec, rel);+ if (em_expr == NULL)+ continue;++ /* Looks like we can generate a pathkey, so let's do it. */+ pathkey = make_canonical_pathkey(root, cur_ec,+ linitial_oid(cur_ec->ec_opfamilies),+ BTLessStrategyNumber,+ false);+ useful_pathkeys_list = lappend(useful_pathkeys_list,+ list_make1(pathkey));+ }++ return useful_pathkeys_list;+}++/*+ * generate_useful_gather_paths+ * Generate parallel access paths for a relation by pushing a Gather or+ * Gather Merge on top of a partial path.+ *+ * Unlike generate_gather_paths, this does not look just as pathkeys of the+ * input paths (aiming to preserve the ordering). It also considers ordering+ * that might be useful by nodes above the gather merge node, and tries to+ * add a sort (regular or incremental) to provide that.+ */+void+generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)+{+ ListCell *lc;+ double rows;+ double *rowsp = NULL;+ List *useful_pathkeys_list = NIL;+ Path *cheapest_partial_path = NULL;++ /* If there are no partial paths, there's nothing to do here. */+ if (rel->partial_pathlist == NIL)+ return;++ /* Should we override the rel's rowcount estimate? */+ if (override_rows)+ rowsp = &rows;++ /* generate the regular gather merge paths */+ generate_gather_paths(root, rel, override_rows);++ /* consider incremental sort for interesting orderings */+ useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel);++ /* used for explicit sort paths */+ cheapest_partial_path = linitial(rel->partial_pathlist);++ /*+ * Consider incremental sort paths for each interesting ordering.+ *+ * XXX I wonder if we need to consider adding a projection here, as+ * create_ordered_paths does.+ */+ foreach(lc, useful_pathkeys_list)+ {+ List *useful_pathkeys = lfirst(lc);+ ListCell *lc2;+ bool is_sorted;+ int presorted_keys;++ foreach(lc2, rel->partial_pathlist)+ {+ Path *subpath = (Path *) lfirst(lc2);+ GatherMergePath *path;++ /* path has no ordering at all, can't use incremental sort */+ if (subpath->pathkeys == NIL)+ continue;++ is_sorted = pathkeys_common_contained_in(useful_pathkeys,+ subpath->pathkeys,+ &presorted_keys);++ if (is_sorted)+ {+ path = create_gather_merge_path(root, rel, subpath, rel->reltarget,+ subpath->pathkeys, NULL, rowsp);++ add_path(rel, &path->path);+ continue;+ }++ /* now we know is_sorted == false */++ /*+ * consider regular sort for cheapest partial path (for each+ * useful pathkeys)+ */+ if (cheapest_partial_path == subpath)+ {+ Path *tmp;++ tmp = (Path *) create_sort_path(root,+ rel,+ subpath,+ useful_pathkeys,+ -1.0);++ rows = tmp->rows * tmp->parallel_workers;++ path = create_gather_merge_path(root, rel,+ tmp,+ rel->reltarget,+ tmp->pathkeys,+ NULL,+ rowsp);++ add_path(rel, &path->path);++ /* continue */+ }++ /* finally, consider incremental sort */+ if (presorted_keys > 0)+ {+ Path *tmp;++ /* Also consider incremental sort. */+ tmp = (Path *) create_incremental_sort_path(root,+ rel,+ subpath,+ useful_pathkeys,+ presorted_keys,+ -1);++ path = create_gather_merge_path(root, rel,+ tmp,+ rel->reltarget,+ tmp->pathkeys,+ NULL,+ rowsp);++ add_path(rel, &path->path);+ }+ }+ }+}+
/*
* make_rel_from_joinlist
* Build access paths using a "joinlist" to guide the join path search.
@@ -2902,7 +3263,7 @@ standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels)
* once we know the final targetlist (see grouping_planner).
*/
if (lev < levels_needed)
- generate_gather_paths(root, rel, false);+ generate_useful_gather_paths(root, rel, false);
/* Find and save the cheapest paths for this rel */
set_cheapest(rel);
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.cindex bfb52f21ab..c2877942cb 100644--- a/src/backend/optimizer/plan/createplan.c+++ b/src/backend/optimizer/plan/createplan.c@@ -5932,7 +5932,10 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
}
}
if (!j)
- elog(ERROR, "could not find pathkey item to sort");+ {+ elog(WARNING, "could not find pathkey item to sort");+ Assert(false);+ }
/*
* Do we need to insert a Result node?
@@ -6491,7 +6494,10 @@ make_unique_from_pathkeys(Plan *lefttree, List *pathkeys, int numCols)
}
if (!tle)
- elog(ERROR, "could not find pathkey item to sort");+ {+ elog(WARNING, "could not find pathkey item to sort");+ Assert(false);+ }
/*
* Look up the correct equality operator from the PathKey's slightly
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.cindex 16996b1bc2..0939f2f7b9 100644--- a/src/backend/optimizer/plan/planner.c+++ b/src/backend/optimizer/plan/planner.c@@ -5068,6 +5068,48 @@ create_ordered_paths(PlannerInfo *root,
add_path(ordered_rel, path);
}
++ /* also consider incremental sorts on all partial paths */+ {+ 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;++ /* already handled above */+ if (input_path == cheapest_partial_path)+ continue;++ 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)+ {+ /* Also consider incremental sort. */+ sorted_path = (Path *) create_incremental_sort_path(root,+ ordered_rel,+ input_path,+ root->sort_pathkeys,+ presorted_keys,+ limit_tuples);++ /* 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);+ }+ }++ }
}
/*
@@ -6484,6 +6526,80 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
}
}
++ /*+ * Use any available suitably-sorted path as input, with incremental+ * sort path.+ */+ 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);++ if (is_sorted)+ continue;++ if (presorted_keys == 0)+ continue;++ 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);+ }+ }+
/*
* Instead of operating directly on the input relation, we can
* consider finalizing a partially aggregated path.
@@ -6530,6 +6646,53 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
havingQual,
dNumGroups));
}
++ /* incremental sort */+ foreach(lc, partially_grouped_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);++ if (is_sorted)+ continue;++ 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));+ }+
}
}
@@ -6798,6 +6961,57 @@ create_partial_grouping_paths(PlannerInfo *root,
dNumPartialGroups));
}
}
++ /*+ * Use any available suitably-sorted path as input, and also consider+ * sorting the cheapest partial path.+ */+ 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)
@@ -6842,6 +7056,52 @@ create_partial_grouping_paths(PlannerInfo *root,
dNumPartialPartialGroups));
}
}
++ /* consider incremental sort */+ foreach(lc, input_rel->partial_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);++ if (is_sorted)+ continue;++ if (presorted_keys == 0)+ continue;++ 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));+ }
}
if (can_hash && cheapest_total_path != NULL)
@@ -6938,6 +7198,7 @@ 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. */
@@ -6967,6 +7228,44 @@ gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel)
add_path(rel, path);
}
++ /* also consider incremental sort on all partial paths */+ 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);+ }+
}
/*
@@ -7222,7 +7521,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
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.hindex e7a40cec3f..20fa94281b 100644--- a/src/include/optimizer/paths.h+++ b/src/include/optimizer/paths.h@@ -54,6 +54,8 @@ extern RelOptInfo *standard_join_search(PlannerInfo *root, int levels_needed,
extern void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel,
bool override_rows);
+extern void generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel,+ bool override_rows);
extern int compute_parallel_worker(RelOptInfo *rel, double heap_pages,
double index_pages, int max_workers);
extern void create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel,
--
2.21.0
From 3a7bcb8940911029ba5927e9993a93f86139f7f4 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Tue, 9 Jul 2019 00:13:04 +0200
Subject: [PATCH 2/4] fix costing in cost_incremental_sort
---
src/backend/optimizer/path/costsize.c | 12 ++----------
1 file changed, 2 insertions(+), 10 deletions(-)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.cindex 7f820e7351..c6aa17ba67 100644--- a/src/backend/optimizer/path/costsize.c+++ b/src/backend/optimizer/path/costsize.c@@ -1875,16 +1875,8 @@ cost_incremental_sort(Path *path,
limit_tuples);
/* If we have a LIMIT, adjust the number of groups we'll have to return. */
- if (limit_tuples > 0 && limit_tuples < input_tuples)- {- output_tuples = limit_tuples;- output_groups = floor(output_tuples / group_tuples) + 1;- }- else- {- output_tuples = input_tuples;- output_groups = input_groups;- }+ output_tuples = input_tuples;+ output_groups = input_groups;
/*
* Startup cost of incremental sort is the startup cost of its first group
--
2.21.0
From 6a439153321e40777d791b70424424a501485408 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Tue, 9 Jul 2019 00:13:34 +0200
Subject: [PATCH 3/4] fix explain in parallel mode
---
src/backend/commands/explain.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.cindex d3f855a12a..925e8236ba 100644--- a/src/backend/commands/explain.c+++ b/src/backend/commands/explain.c@@ -2775,7 +2775,7 @@ show_incremental_sort_info(IncrementalSortState *incrsortstate,
fullsort_spaceUsed, fullsort_group_count);
if (prefixsort_instrument)
appendStringInfo(es->str,
- ", Prefix Sort Method: %s %s: %ldkB Groups: %ld",+ ", Prefix Sort Method: %s %s: %ldkB Groups: %ld\n",
prefixsort_sortMethod, prefixsort_spaceType,
prefixsort_spaceUsed, prefixsort_group_count);
else
--
2.21.0
From 9dc5530429083195e90129b3eb18f8d7a5f78451 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Tue, 9 Jul 2019 13:36:42 +0200
Subject: [PATCH 4/4] add force_incremental_sort GUC
---
src/backend/optimizer/path/costsize.c | 8 ++++++++
src/backend/utils/misc/guc.c | 10 ++++++++++
src/include/optimizer/cost.h | 1 +
3 files changed, 19 insertions(+)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.cindex c6aa17ba67..ee4487b158 100644--- a/src/backend/optimizer/path/costsize.c+++ b/src/backend/optimizer/path/costsize.c@@ -140,6 +140,8 @@ bool enable_parallel_append = true;
bool enable_parallel_hash = true;
bool enable_partition_pruning = true;
+bool force_incremental_sort = true;+
typedef struct
{
PlannerInfo *root;
@@ -1907,6 +1909,12 @@ cost_incremental_sort(Path *path,
path->rows = input_tuples;
path->startup_cost = startup_cost;
path->total_cost = startup_cost + run_cost;
++ if (force_incremental_sort)+ {+ path->startup_cost = input_startup_cost;+ path->total_cost = input_total_cost;+ }
}
/*
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.cindex f922ee66a0..d2cc5b56b5 100644--- a/src/backend/utils/misc/guc.c+++ b/src/backend/utils/misc/guc.c@@ -941,6 +941,16 @@ static struct config_bool ConfigureNamesBool[] =
true,
NULL, NULL, NULL
},
+ {+ {"force_incremental_sort", PGC_USERSET, QUERY_TUNING_METHOD,+ gettext_noop("Makes the incremental sort look like no-cost."),+ NULL,+ GUC_EXPLAIN+ },+ &force_incremental_sort,+ false,+ NULL, NULL, NULL+ },
{
{"enable_incrementalsort", PGC_USERSET, QUERY_TUNING_METHOD,
gettext_noop("Enables the planner's use of incremental sort steps."),
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.hindex b9d7a77e65..bad1d5a330 100644--- a/src/include/optimizer/cost.h+++ b/src/include/optimizer/cost.h@@ -66,6 +66,7 @@ extern PGDLLIMPORT bool enable_parallel_append;
extern PGDLLIMPORT bool enable_parallel_hash;
extern PGDLLIMPORT bool enable_partition_pruning;
extern PGDLLIMPORT int constraint_exclusion;
+extern PGDLLIMPORT bool force_incremental_sort;
extern double index_pages_fetched(double tuples_fetched, BlockNumber pages,
double index_pages, PlannerInfo *root);
--
2.21.0
Attachments:
[text/plain] 0001-fix-pathkey-processing-in-generate_gather_p-20190709.patch (23.6K, ../20190709121125.5bpaxgtd5wl7aghy@development/2-0001-fix-pathkey-processing-in-generate_gather_p-20190709.patch)
download | inline diff:
From e7e97daf447a91e090809be4f07a5eee650eb5e7 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Tue, 9 Jul 2019 00:12:45 +0200
Subject: [PATCH 1/4] fix pathkey processing in generate_gather_paths
---
src/backend/optimizer/path/allpaths.c | 365 +++++++++++++++++++++++-
src/backend/optimizer/plan/createplan.c | 10 +-
src/backend/optimizer/plan/planner.c | 301 ++++++++++++++++++-
src/include/optimizer/paths.h | 2 +
4 files changed, 673 insertions(+), 5 deletions(-)
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.cindex 3efc807164..acddbef064 100644--- a/src/backend/optimizer/path/allpaths.c+++ b/src/backend/optimizer/path/allpaths.c@@ -556,7 +556,7 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
*/
if (rel->reloptkind == RELOPT_BASEREL &&
bms_membership(root->all_baserels) != BMS_SINGLETON)
- generate_gather_paths(root, rel, false);+ generate_useful_gather_paths(root, rel, false);
/* Now find the cheapest of the paths for this rel */
set_cheapest(rel);
@@ -2730,6 +2730,367 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
}
}
+/*+ * Find an equivalence class member expression, all of whose Vars, come from+ * the indicated relation.+ */+static Expr *+find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel)+{+ ListCell *lc_em;++ foreach(lc_em, ec->ec_members)+ {+ EquivalenceMember *em = lfirst(lc_em);++ if (bms_is_subset(em->em_relids, rel->relids) &&+ !bms_is_empty(em->em_relids))+ {+ /*+ * If there is more than one equivalence member whose Vars are+ * taken entirely from this relation, we'll be content to choose+ * any one of those.+ */+ return em->em_expr;+ }+ }++ /* We didn't find any suitable equivalence class expression */+ return NULL;+}++/*+ * get_useful_ecs_for_relation+ * Determine which EquivalenceClasses might be involved in useful+ * orderings of this relation.+ *+ * This function is in some respects a mirror image of the core function+ * pathkeys_useful_for_merging: for a regular table, we know what indexes+ * we have and want to test whether any of them are useful. For a foreign+ * table, we don't know what indexes are present on the remote side but+ * want to speculate about which ones we'd like to use if they existed.+ *+ * This function returns a list of potentially-useful equivalence classes,+ * but it does not guarantee that an EquivalenceMember exists which contains+ * Vars only from the given relation. For example, given ft1 JOIN t1 ON+ * ft1.x + t1.x = 0, this function will say that the equivalence class+ * containing ft1.x + t1.x is potentially useful. Supposing ft1 is remote and+ * t1 is local (or on a different server), it will turn out that no useful+ * ORDER BY clause can be generated. It's not our job to figure that out+ * here; we're only interested in identifying relevant ECs.+ */+static List *+get_useful_ecs_for_relation(PlannerInfo *root, RelOptInfo *rel)+{+ List *useful_eclass_list = NIL;+ ListCell *lc;+ Relids relids;++ /*+ * First, consider whether any active EC is potentially useful for a merge+ * join against this relation.+ */+ if (rel->has_eclass_joins)+ {+ foreach(lc, root->eq_classes)+ {+ EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc);++ if (eclass_useful_for_merging(root, cur_ec, rel))+ useful_eclass_list = lappend(useful_eclass_list, cur_ec);+ }+ }++ /*+ * Next, consider whether there are any non-EC derivable join clauses that+ * are merge-joinable. If the joininfo list is empty, we can exit+ * quickly.+ */+ if (rel->joininfo == NIL)+ return useful_eclass_list;++ /* If this is a child rel, we must use the topmost parent rel to search. */+ if (IS_OTHER_REL(rel))+ {+ Assert(!bms_is_empty(rel->top_parent_relids));+ relids = rel->top_parent_relids;+ }+ else+ relids = rel->relids;++ /* Check each join clause in turn. */+ foreach(lc, rel->joininfo)+ {+ RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);++ /* Consider only mergejoinable clauses */+ if (restrictinfo->mergeopfamilies == NIL)+ continue;++ /* Make sure we've got canonical ECs. */+ update_mergeclause_eclasses(root, restrictinfo);++ /*+ * restrictinfo->mergeopfamilies != NIL is sufficient to guarantee+ * that left_ec and right_ec will be initialized, per comments in+ * distribute_qual_to_rels.+ *+ * We want to identify which side of this merge-joinable clause+ * contains columns from the relation produced by this RelOptInfo. We+ * test for overlap, not containment, because there could be extra+ * relations on either side. For example, suppose we've got something+ * like ((A JOIN B ON A.x = B.x) JOIN C ON A.y = C.y) LEFT JOIN D ON+ * A.y = D.y. The input rel might be the joinrel between A and B, and+ * we'll consider the join clause A.y = D.y. relids contains a+ * relation not involved in the join class (B) and the equivalence+ * class for the left-hand side of the clause contains a relation not+ * involved in the input rel (C). Despite the fact that we have only+ * overlap and not containment in either direction, A.y is potentially+ * useful as a sort column.+ *+ * Note that it's even possible that relids overlaps neither side of+ * the join clause. For example, consider A LEFT JOIN B ON A.x = B.x+ * AND A.x = 1. The clause A.x = 1 will appear in B's joininfo list,+ * but overlaps neither side of B. In that case, we just skip this+ * join clause, since it doesn't suggest a useful sort order for this+ * relation.+ */+ if (bms_overlap(relids, restrictinfo->right_ec->ec_relids))+ useful_eclass_list = list_append_unique_ptr(useful_eclass_list,+ restrictinfo->right_ec);+ else if (bms_overlap(relids, restrictinfo->left_ec->ec_relids))+ useful_eclass_list = list_append_unique_ptr(useful_eclass_list,+ restrictinfo->left_ec);+ }++ return useful_eclass_list;+}++/*+ * get_useful_pathkeys_for_relation+ * Determine which orderings of a relation might be useful.+ *+ * Getting data in sorted order can be useful either because the requested+ * order matches the final output ordering for the overall query we're+ * planning, or because it enables an efficient merge join. Here, we try+ * to figure out which pathkeys to consider.+ */+static List *+get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel)+{+ List *useful_pathkeys_list = NIL;+ List *useful_eclass_list;+ EquivalenceClass *query_ec = NULL;+ ListCell *lc;++ /*+ * Pushing the query_pathkeys to the remote server is always worth+ * considering, because it might let us avoid a local sort.+ */+ if (root->query_pathkeys)+ {+ bool query_pathkeys_ok = true;++ foreach(lc, root->query_pathkeys)+ {+ PathKey *pathkey = (PathKey *) lfirst(lc);+ EquivalenceClass *pathkey_ec = pathkey->pk_eclass;+ Expr *em_expr;++ /*+ * The planner and executor don't have any clever strategy for+ * taking data sorted by a prefix of the query's pathkeys and+ * getting it to be sorted by all of those pathkeys. We'll just+ * end up resorting the entire data set. So, unless we can push+ * down all of the query pathkeys, forget it.+ *+ * is_foreign_expr would detect volatile expressions as well, but+ * checking ec_has_volatile here saves some cycles.+ */+ if (pathkey_ec->ec_has_volatile ||+ !(em_expr = find_em_expr_for_rel(pathkey_ec, rel)))+ {+ query_pathkeys_ok = false;+ break;+ }+ }++ if (query_pathkeys_ok)+ useful_pathkeys_list = list_make1(list_copy(root->query_pathkeys));+ }++ /* Get the list of interesting EquivalenceClasses. */+ useful_eclass_list = get_useful_ecs_for_relation(root, rel);++ /* Extract unique EC for query, if any, so we don't consider it again. */+ if (list_length(root->query_pathkeys) == 1)+ {+ PathKey *query_pathkey = linitial(root->query_pathkeys);++ query_ec = query_pathkey->pk_eclass;+ }++ /*+ * As a heuristic, the only pathkeys we consider here are those of length+ * one. It's surely possible to consider more, but since each one we+ * choose to consider will generate a round-trip to the remote side, we+ * need to be a bit cautious here. It would sure be nice to have a local+ * cache of information about remote index definitions...+ */+ foreach(lc, useful_eclass_list)+ {+ EquivalenceClass *cur_ec = lfirst(lc);+ Expr *em_expr;+ PathKey *pathkey;++ /* If redundant with what we did above, skip it. */+ if (cur_ec == query_ec)+ continue;++ /* If no pushable expression for this rel, skip it. */+ em_expr = find_em_expr_for_rel(cur_ec, rel);+ if (em_expr == NULL)+ continue;++ /* Looks like we can generate a pathkey, so let's do it. */+ pathkey = make_canonical_pathkey(root, cur_ec,+ linitial_oid(cur_ec->ec_opfamilies),+ BTLessStrategyNumber,+ false);+ useful_pathkeys_list = lappend(useful_pathkeys_list,+ list_make1(pathkey));+ }++ return useful_pathkeys_list;+}++/*+ * generate_useful_gather_paths+ * Generate parallel access paths for a relation by pushing a Gather or+ * Gather Merge on top of a partial path.+ *+ * Unlike generate_gather_paths, this does not look just as pathkeys of the+ * input paths (aiming to preserve the ordering). It also considers ordering+ * that might be useful by nodes above the gather merge node, and tries to+ * add a sort (regular or incremental) to provide that.+ */+void+generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)+{+ ListCell *lc;+ double rows;+ double *rowsp = NULL;+ List *useful_pathkeys_list = NIL;+ Path *cheapest_partial_path = NULL;++ /* If there are no partial paths, there's nothing to do here. */+ if (rel->partial_pathlist == NIL)+ return;++ /* Should we override the rel's rowcount estimate? */+ if (override_rows)+ rowsp = &rows;++ /* generate the regular gather merge paths */+ generate_gather_paths(root, rel, override_rows);++ /* consider incremental sort for interesting orderings */+ useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel);++ /* used for explicit sort paths */+ cheapest_partial_path = linitial(rel->partial_pathlist);++ /*+ * Consider incremental sort paths for each interesting ordering.+ *+ * XXX I wonder if we need to consider adding a projection here, as+ * create_ordered_paths does.+ */+ foreach(lc, useful_pathkeys_list)+ {+ List *useful_pathkeys = lfirst(lc);+ ListCell *lc2;+ bool is_sorted;+ int presorted_keys;++ foreach(lc2, rel->partial_pathlist)+ {+ Path *subpath = (Path *) lfirst(lc2);+ GatherMergePath *path;++ /* path has no ordering at all, can't use incremental sort */+ if (subpath->pathkeys == NIL)+ continue;++ is_sorted = pathkeys_common_contained_in(useful_pathkeys,+ subpath->pathkeys,+ &presorted_keys);++ if (is_sorted)+ {+ path = create_gather_merge_path(root, rel, subpath, rel->reltarget,+ subpath->pathkeys, NULL, rowsp);++ add_path(rel, &path->path);+ continue;+ }++ /* now we know is_sorted == false */++ /*+ * consider regular sort for cheapest partial path (for each+ * useful pathkeys)+ */+ if (cheapest_partial_path == subpath)+ {+ Path *tmp;++ tmp = (Path *) create_sort_path(root,+ rel,+ subpath,+ useful_pathkeys,+ -1.0);++ rows = tmp->rows * tmp->parallel_workers;++ path = create_gather_merge_path(root, rel,+ tmp,+ rel->reltarget,+ tmp->pathkeys,+ NULL,+ rowsp);++ add_path(rel, &path->path);++ /* continue */+ }++ /* finally, consider incremental sort */+ if (presorted_keys > 0)+ {+ Path *tmp;++ /* Also consider incremental sort. */+ tmp = (Path *) create_incremental_sort_path(root,+ rel,+ subpath,+ useful_pathkeys,+ presorted_keys,+ -1);++ path = create_gather_merge_path(root, rel,+ tmp,+ rel->reltarget,+ tmp->pathkeys,+ NULL,+ rowsp);++ add_path(rel, &path->path);+ }+ }+ }+}+
/*
* make_rel_from_joinlist
* Build access paths using a "joinlist" to guide the join path search.
@@ -2902,7 +3263,7 @@ standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels)
* once we know the final targetlist (see grouping_planner).
*/
if (lev < levels_needed)
- generate_gather_paths(root, rel, false);+ generate_useful_gather_paths(root, rel, false);
/* Find and save the cheapest paths for this rel */
set_cheapest(rel);
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.cindex bfb52f21ab..c2877942cb 100644--- a/src/backend/optimizer/plan/createplan.c+++ b/src/backend/optimizer/plan/createplan.c@@ -5932,7 +5932,10 @@ prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
}
}
if (!j)
- elog(ERROR, "could not find pathkey item to sort");+ {+ elog(WARNING, "could not find pathkey item to sort");+ Assert(false);+ }
/*
* Do we need to insert a Result node?
@@ -6491,7 +6494,10 @@ make_unique_from_pathkeys(Plan *lefttree, List *pathkeys, int numCols)
}
if (!tle)
- elog(ERROR, "could not find pathkey item to sort");+ {+ elog(WARNING, "could not find pathkey item to sort");+ Assert(false);+ }
/*
* Look up the correct equality operator from the PathKey's slightly
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.cindex 16996b1bc2..0939f2f7b9 100644--- a/src/backend/optimizer/plan/planner.c+++ b/src/backend/optimizer/plan/planner.c@@ -5068,6 +5068,48 @@ create_ordered_paths(PlannerInfo *root,
add_path(ordered_rel, path);
}
++ /* also consider incremental sorts on all partial paths */+ {+ 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;++ /* already handled above */+ if (input_path == cheapest_partial_path)+ continue;++ 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)+ {+ /* Also consider incremental sort. */+ sorted_path = (Path *) create_incremental_sort_path(root,+ ordered_rel,+ input_path,+ root->sort_pathkeys,+ presorted_keys,+ limit_tuples);++ /* 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);+ }+ }++ }
}
/*
@@ -6484,6 +6526,80 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
}
}
++ /*+ * Use any available suitably-sorted path as input, with incremental+ * sort path.+ */+ 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);++ if (is_sorted)+ continue;++ if (presorted_keys == 0)+ continue;++ 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);+ }+ }+
/*
* Instead of operating directly on the input relation, we can
* consider finalizing a partially aggregated path.
@@ -6530,6 +6646,53 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
havingQual,
dNumGroups));
}
++ /* incremental sort */+ foreach(lc, partially_grouped_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);++ if (is_sorted)+ continue;++ 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));+ }+
}
}
@@ -6798,6 +6961,57 @@ create_partial_grouping_paths(PlannerInfo *root,
dNumPartialGroups));
}
}
++ /*+ * Use any available suitably-sorted path as input, and also consider+ * sorting the cheapest partial path.+ */+ 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)
@@ -6842,6 +7056,52 @@ create_partial_grouping_paths(PlannerInfo *root,
dNumPartialPartialGroups));
}
}
++ /* consider incremental sort */+ foreach(lc, input_rel->partial_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);++ if (is_sorted)+ continue;++ if (presorted_keys == 0)+ continue;++ 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));+ }
}
if (can_hash && cheapest_total_path != NULL)
@@ -6938,6 +7198,7 @@ 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. */
@@ -6967,6 +7228,44 @@ gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel)
add_path(rel, path);
}
++ /* also consider incremental sort on all partial paths */+ 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);+ }+
}
/*
@@ -7222,7 +7521,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
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.hindex e7a40cec3f..20fa94281b 100644--- a/src/include/optimizer/paths.h+++ b/src/include/optimizer/paths.h@@ -54,6 +54,8 @@ extern RelOptInfo *standard_join_search(PlannerInfo *root, int levels_needed,
extern void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel,
bool override_rows);
+extern void generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel,+ bool override_rows);
extern int compute_parallel_worker(RelOptInfo *rel, double heap_pages,
double index_pages, int max_workers);
extern void create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel,
--
2.21.0
[text/plain] 0002-fix-costing-in-cost_incremental_sort-20190709.patch (1.1K, ../20190709121125.5bpaxgtd5wl7aghy@development/3-0002-fix-costing-in-cost_incremental_sort-20190709.patch)
download | inline diff:
From 3a7bcb8940911029ba5927e9993a93f86139f7f4 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Tue, 9 Jul 2019 00:13:04 +0200
Subject: [PATCH 2/4] fix costing in cost_incremental_sort
---
src/backend/optimizer/path/costsize.c | 12 ++----------
1 file changed, 2 insertions(+), 10 deletions(-)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.cindex 7f820e7351..c6aa17ba67 100644--- a/src/backend/optimizer/path/costsize.c+++ b/src/backend/optimizer/path/costsize.c@@ -1875,16 +1875,8 @@ cost_incremental_sort(Path *path,
limit_tuples);
/* If we have a LIMIT, adjust the number of groups we'll have to return. */
- if (limit_tuples > 0 && limit_tuples < input_tuples)- {- output_tuples = limit_tuples;- output_groups = floor(output_tuples / group_tuples) + 1;- }- else- {- output_tuples = input_tuples;- output_groups = input_groups;- }+ output_tuples = input_tuples;+ output_groups = input_groups;
/*
* Startup cost of incremental sort is the startup cost of its first group
--
2.21.0
[text/plain] 0003-fix-explain-in-parallel-mode-20190709.patch (945B, ../20190709121125.5bpaxgtd5wl7aghy@development/4-0003-fix-explain-in-parallel-mode-20190709.patch)
download | inline diff:
From 6a439153321e40777d791b70424424a501485408 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Tue, 9 Jul 2019 00:13:34 +0200
Subject: [PATCH 3/4] fix explain in parallel mode
---
src/backend/commands/explain.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.cindex d3f855a12a..925e8236ba 100644--- a/src/backend/commands/explain.c+++ b/src/backend/commands/explain.c@@ -2775,7 +2775,7 @@ show_incremental_sort_info(IncrementalSortState *incrsortstate,
fullsort_spaceUsed, fullsort_group_count);
if (prefixsort_instrument)
appendStringInfo(es->str,
- ", Prefix Sort Method: %s %s: %ldkB Groups: %ld",+ ", Prefix Sort Method: %s %s: %ldkB Groups: %ld\n",
prefixsort_sortMethod, prefixsort_spaceType,
prefixsort_spaceUsed, prefixsort_group_count);
else
--
2.21.0
[text/plain] 0004-add-force_incremental_sort-GUC-20190709.patch (2.3K, ../20190709121125.5bpaxgtd5wl7aghy@development/5-0004-add-force_incremental_sort-GUC-20190709.patch)
download | inline diff:
From 9dc5530429083195e90129b3eb18f8d7a5f78451 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Tue, 9 Jul 2019 13:36:42 +0200
Subject: [PATCH 4/4] add force_incremental_sort GUC
---
src/backend/optimizer/path/costsize.c | 8 ++++++++
src/backend/utils/misc/guc.c | 10 ++++++++++
src/include/optimizer/cost.h | 1 +
3 files changed, 19 insertions(+)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.cindex c6aa17ba67..ee4487b158 100644--- a/src/backend/optimizer/path/costsize.c+++ b/src/backend/optimizer/path/costsize.c@@ -140,6 +140,8 @@ bool enable_parallel_append = true;
bool enable_parallel_hash = true;
bool enable_partition_pruning = true;
+bool force_incremental_sort = true;+
typedef struct
{
PlannerInfo *root;
@@ -1907,6 +1909,12 @@ cost_incremental_sort(Path *path,
path->rows = input_tuples;
path->startup_cost = startup_cost;
path->total_cost = startup_cost + run_cost;
++ if (force_incremental_sort)+ {+ path->startup_cost = input_startup_cost;+ path->total_cost = input_total_cost;+ }
}
/*
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.cindex f922ee66a0..d2cc5b56b5 100644--- a/src/backend/utils/misc/guc.c+++ b/src/backend/utils/misc/guc.c@@ -941,6 +941,16 @@ static struct config_bool ConfigureNamesBool[] =
true,
NULL, NULL, NULL
},
+ {+ {"force_incremental_sort", PGC_USERSET, QUERY_TUNING_METHOD,+ gettext_noop("Makes the incremental sort look like no-cost."),+ NULL,+ GUC_EXPLAIN+ },+ &force_incremental_sort,+ false,+ NULL, NULL, NULL+ },
{
{"enable_incrementalsort", PGC_USERSET, QUERY_TUNING_METHOD,
gettext_noop("Enables the planner's use of incremental sort steps."),
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.hindex b9d7a77e65..bad1d5a330 100644--- a/src/include/optimizer/cost.h+++ b/src/include/optimizer/cost.h@@ -66,6 +66,7 @@ extern PGDLLIMPORT bool enable_parallel_append;
extern PGDLLIMPORT bool enable_parallel_hash;
extern PGDLLIMPORT bool enable_partition_pruning;
extern PGDLLIMPORT int constraint_exclusion;
+extern PGDLLIMPORT bool force_incremental_sort;
extern double index_pages_fetched(double tuples_fetched, BlockNumber pages,
double index_pages, PlannerInfo *root);
--
2.21.0
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: tomas.vondra@2ndquadrant.com, jtc331@gmail.com, pg@bowt.ie, simon@2ndquadrant.com, rafia.pghackers@gmail.com, shaun.thomas@2ndquadrant.com, 9erthalion6@gmail.com, a.korotkov@postgrespro.ru, tgl@sss.pgh.pa.us, pgsql-hackers@lists.postgresql.org
Subject: Re: [PATCH] Incremental sort (was: PoC: Partial sort)
In-Reply-To: <20190709121125.5bpaxgtd5wl7aghy@development>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox