public inbox for [email protected]
help / color / mirror / Atom feedFrom: Tomas Vondra <[email protected]>
Subject: [PATCH 5/8] Consider incremental sort paths in additional places
Date: Sun, 28 Jul 2019 15:59:05 +0200
---
src/backend/optimizer/path/allpaths.c | 221 +++++++++++++++++++++++++-
src/backend/optimizer/plan/planner.c | 130 ++++++++++++++-
src/include/optimizer/paths.h | 2 +
3 files changed, 350 insertions(+), 3 deletions(-)
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index ccf46dd0aa..9a92948fe3 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);
@@ -2727,6 +2727,223 @@ 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_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;
+ 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 re-sorting 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;
+ }
+ }
+
+ /*
+ * This ends up allowing us to do incremental sort on top of an index
+ * scan all parallelized under a gather merge node.
+ */
+ if (query_pathkeys_ok)
+ useful_pathkeys_list = list_make1(list_copy(root->query_pathkeys));
+ }
+
+ 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 only at 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);
+
+ /* when incremental sort is disabled, we're done */
+ if (!enable_incrementalsort)
+ return;
+
+ /* 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;
+ }
+
+ Assert(!is_sorted);
+
+ /*
+ * 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);
+
+ /* Fall through */
+ }
+
+ /* Also consider incremental sort */
+ if (presorted_keys > 0)
+ {
+ Path *tmp;
+
+ 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.
@@ -2899,7 +3116,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/planner.c b/src/backend/optimizer/plan/planner.c
index 0e01cf8cb1..46dc355af3 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -6434,7 +6434,9 @@ 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_contained_in(root->group_pathkeys,
path->pathkeys);
@@ -6493,6 +6495,80 @@ 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;
+
+ 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);
+
+ /* 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);
+ }
}
/*
@@ -6819,7 +6895,9 @@ 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_contained_in(root->group_pathkeys,
path->pathkeys);
@@ -6854,6 +6932,56 @@ 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;
+
+ 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,
+ 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));
}
}
@@ -7235,7 +7363,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.h
index 85f5fe37ea..f6994779de 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.1
--dfcjsgdukgytabqd
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="v39-0006-fix.patch"
view thread (35+ messages) latest in thread
reply
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: [email protected]
Cc: [email protected]
Subject: Re: [PATCH 5/8] Consider incremental sort paths in additional places
In-Reply-To: <no-message-id-1882715@localhost>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox