On Mon, Jul 08, 2019 at 12:07:06PM -0400, James Coleman wrote:
On Mon, Jul 8, 2019 at 10:58 AM Tomas Vondra
<tomas.von...@2ndquadrant.com> wrote:
On Mon, Jul 08, 2019 at 10:32:18AM -0400, James Coleman wrote:
>On Mon, Jul 8, 2019 at 9:59 AM Tomas Vondra
><tomas.von...@2ndquadrant.com> wrote:
>>
>> On Mon, Jul 08, 2019 at 09:22:39AM -0400, James Coleman wrote:
>> >On Sun, Jul 7, 2019 at 5:02 PM Tomas Vondra
>> ><tomas.von...@2ndquadrant.com> wrote:
>> >> We're running query like this:
>> >>
>> >> SELECT a, sum(b), count(*) FROM pagg_tab_ml GROUP BY a HAVING avg(b) <
3 ORDER BY 1, 2, 3
>> >>
>> >> but we're trying to add the incremental sort *before* the aggregation,
>> >> because the optimizer also considers group aggregate with a sorted
>> >> input. And (a) is a prefix of (a,sum(b),count(b)) so we think we
>> >> actually can do this, but clearly that's nonsense, because we can't
>> >> possibly know the aggregates yet. Hence the error.
>> >>
>> >> If this is the actual issue, we need to ensure we actually can evaluate
>> >> all the pathkeys. I don't know how to do that yet. I thought that maybe
>> >> we should modify pathkeys_common_contained_in() to set presorted_keys to
>> >> 0 in this case.
>> >>
>> >> But then I started wondering why we don't see this issue even for
>> >> regular (non-incremental-sort) paths built in create_ordered_paths().
>> >> How come we don't see these failures there? I've modified costing to
>> >> make all incremental sort paths very cheap, and still nothing.
>> >
>> >I assume you mean you modified costing to make regular sort paths very
cheap?
>> >
>>
>> No, I mean costing of incremental sort paths, so that they end up being
>> the cheapest ones. If some other path is cheaper, we won't see the error
>> because it only happens when building plan from the cheapest path.
>
>Ah, I misunderstood as you trying to figure out a way to try to cause
>the same problem with a regular sort.
>
>> >> So presumably there's a check elsewhere (either implicit or explicit),
>> >> because create_ordered_paths() uses pathkeys_common_contained_in() and
>> >> does not have the same issue.
>> >
>> >Given this comment in create_ordered_paths():
>> >
>> > generate_gather_paths() will have already generated a simple Gather
>> > path for the best parallel path, if any, and the loop above will have
>> > considered sorting it. Similarly, generate_gather_paths() will also
>> > have generated order-preserving Gather Merge plans which can be used
>> > without sorting if they happen to match the sort_pathkeys, and the loop
>> > above will have handled those as well. However, there's one more
>> > possibility: it may make sense to sort the cheapest partial path
>> > according to the required output order and then use Gather Merge.
>> >
>> >my understanding is that generate_gather_paths() only considers paths
>> >that already happen to be sorted (not explicit sorts), so I'm
>> >wondering if it would make more sense for the incremental sort path
>> >creation for this case to live alongside the explicit ordered path
>> >creation in create_ordered_paths() rather than in
>> >generate_gather_paths().
>> >
>>
>> How would that solve the issue? Also, we're building a gather path, so
>> I think generate_gather_paths() is the right place where to do it. And
>> we're not changing the semantics of generate_gather_paths() - the result
>> path should be sorted "correctly" with respect to sort_pathkeys.
>
>Does that imply what the explicit sort in create_ordered_paths() is in
>the wrong spot?
>
I think those are essentially the right places where to do this sort of
stuff. Maybe there's a better place, but I don't think those places are
somehow wrong.
>Or, to put it another way, do you think that both kinds of sorts
>should be added in the same place? It seems confusing to me that
>they'd be split between the two methods (unless I'm completely
>misunderstanding how the two work).
>
The paths built in those two places were very different in one aspect:
1) generate_gather_paths only ever looked at pathkeys for the subpath, it
never even looked at ordering expected by paths above it (or the query as
a whole). Plain Gather ignores pathkeys entirely, Gather Merge only aims
to maintain ordering of the different subpaths.
2) create_oredered_paths is meant to enforce ordering needed by upper
parts of the plan - either by using a properly sorted path, or adding an
explicit sort.
We want to extend (1) to also look at ordering expected by the upper parts
of the plan, and consider incremental sort if applicable. (2) already does
that, and it already has the correct pathkeys to enforce.
I guess I'm still not following. If (2) is responsible (currently) for
adding an explicit sort, why wouldn't adding an incremental sort be an
example of that responsibility? The subpath that either a Sort or
IncrementalSort is being added on top of (to then feed into the
GatherMerge) is the same in both cases right?
Unless you're saying that the difference is that since we have a
partial ordering already for incremental sort then incremental sort
falls into the category of "maintaining" existing ordering of the
subpath?
Oh, I think I understand what you're saying. Essentially, we should not
be making generate_gather_paths responsible for adding the incremental
sort. Instead, we should be looking at places than are adding explicit
sort (using create_sort_path) and also consider adding incremental sort.
I definitely agree with the second half - we should look at all places
that create explicit sorts and make them also consider incremental
sorts. That makes sense.
But I'm not sure it'll address all cases - the problem is that those
places add the explicit sort because they need sorted input. Gather
Merge does not do that, it only preserves existing ordering of paths.
So it's possible the path does not have an explicit sort on to, and
gather merge will not know to add it. And once we have the gather merge
in place, we can't push place "under" it.
In fact, we already have code dealing with this "issue" for a special
case - see gather_grouping_paths(). It generates plain gather merge
paths, but then also considers building one with explicit sort. But it
only does that for grouping paths (when it's clear we need to be looking
at grouping_pathkeys), and there are generate_gather_paths() that don't
have similar treatment.
But looking at root->sort_pathkeys in (1) seems to be the wrong thing :-(
The thing is, we don't have just sort_pathkeys, there's distinct_pathkeys
and group_pathkeys too, so maybe we should be looking at those too?
I don't know enough yet to answer, but I'd like to look at (in the
debugger) the subpaths considered in each function to try to get a
better understanding of why we don't try to explicitly sort the aggs
(which we know we can't sort yet) but do for incremental sort. I
assume that means a subpath has to be present in one but not the other
since they both use the same pathkey checking function.
I've been wondering if we have some other code that needs to consider
interesting pathkeys "candidates" (instead of just getting the list
interesting in that place). Because then we could look at that code and
use it here ...
And guess what - postgres_fdw needs to do pretty much exactly that, when
building paths for remote relations. AFAIK we can't easily request all
plans from the remote node and then look at their pathkeys (like we'd do
with local node), so instead we deduce "interesting pathkeys" and then
request best plans for those. And deducing "interesing" pathkeys is
pretty much what get_useful_pathkeys_for_relation() is about.
So I've copied this function (and two more, called from it), whacked it
a bit until it removed (shakespeare-writing chimp comes to mind) and
voila, it seems to be working. The errors you reported are gone, and the
plans seems to be reasonable.
Attached is a sequence of 4 patches:
0001-fix-pathkey-processing-in-generate_gather_paths.patch
----------------------------------------------------------
This is the fixed version of my previous patch, with the stuff stolen
from postgres_fdw.
0002-fix-costing-in-cost_incremental_sort.patch
-----------------------------------------------
This is the costing fix, I mentioned before.
0003-fix-explain-in-parallel-mode.patch
---------------------------------------
Minor bug in explain, when incremental sort ends up being in the
parallel part of the plan (missing newline on per-worker line)
0004-rework-where-incremental-sort-paths-are-created.patch
----------------------------------------------------------
This undoes the generate_gather_paths() changes from 0001, and instead
modifies a bunch of places that call create_sort_path() to also consider
incremental sorts. There are a couple remaining, but those should not be
relevant to the queries I've been looking at.
Essentially, 0002 and 0003 are bugfixes. 0001 and 0004 are the two
different aproaches to building incremental sort + gather merge.
Now, consider this example:
create table t (a int, b int, c int);
insert into t select mod(i,100),mod(i,100),i from generate_series(1,10000000)
s(i);
create index on t (a);
analyze t;
explain select a,b,sum(c) from t group by 1,2 order by 1,2,3 limit 1;
With 0001+0002+0003 pathes, I get a plan like this:
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
Limit (cost=10375.39..10594.72 rows=1 width=16)
-> Incremental Sort (cost=10375.39..2203675.71 rows=10000 width=16)
Sort Key: a, b, (sum(c))
Presorted Key: a, b
-> GroupAggregate (cost=10156.07..2203225.71 rows=10000 width=16)
Group Key: a, b
-> Gather Merge (cost=10156.07..2128124.39 rows=10000175
width=12)
Workers Planned: 2
-> Incremental Sort (cost=9156.04..972856.05 rows=4166740
width=12)
Sort Key: a, b
Presorted Key: a
-> Parallel Index Scan using t_a_idx on t
(cost=0.43..417690.30 rows=4166740 width=12)
(12 rows)
and with 0004, I get this:
QUERY PLAN
------------------------------------------------------------------------------------------------------
Limit (cost=20443.84..20665.32 rows=1 width=16)
-> Incremental Sort (cost=20443.84..2235250.05 rows=10000 width=16)
Sort Key: a, b, (sum(c))
Presorted Key: a, b
-> GroupAggregate (cost=20222.37..2234800.05 rows=10000 width=16)
Group Key: a, b
-> Incremental Sort (cost=20222.37..2159698.74 rows=10000175
width=12)
Sort Key: a, b
Presorted Key: a
-> Index Scan using t_a_idx on t (cost=0.43..476024.65
rows=10000175 width=12)
(10 rows)
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.
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).
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
>From 56fc55058ca44f18a4a3c878a5588b01c67df0e0 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <to...@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 | 269 ++++++++++++++++++++++++
src/backend/optimizer/plan/createplan.c | 10 +-
2 files changed, 277 insertions(+), 2 deletions(-)
diff --git a/src/backend/optimizer/path/allpaths.c
b/src/backend/optimizer/path/allpaths.c
index 3efc807164..34a0fb4d32 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2665,6 +2665,242 @@ set_worktable_pathlist(PlannerInfo *root, RelOptInfo
*rel, RangeTblEntry *rte)
add_path(rel, create_worktablescan_path(root, rel, required_outer));
}
+
+
+/*
+ * 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_gather_paths
* Generate parallel access paths for a relation by pushing a
Gather or
@@ -2719,6 +2955,10 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo
*rel, bool override_rows)
{
Path *subpath = (Path *) lfirst(lc);
GatherMergePath *path;
+ bool is_sorted;
+ int presorted_keys;
+ List *useful_pathkeys_list = NIL; /* List of all pathkeys
*/
+ ListCell *lc;
if (subpath->pathkeys == NIL)
continue;
@@ -2727,6 +2967,35 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo
*rel, bool override_rows)
path = create_gather_merge_path(root, rel, subpath,
rel->reltarget,
subpath->pathkeys, NULL, rowsp);
add_path(rel, &path->path);
+
+ /* consider incremental sort for interesting orderings */
+ useful_pathkeys_list = get_useful_pathkeys_for_relation(root,
rel);
+
+ foreach(lc, useful_pathkeys_list)
+ {
+ List *useful_pathkeys = lfirst(lc);
+
+ is_sorted =
pathkeys_common_contained_in(useful_pathkeys,
+
subpath->pathkeys,
+
&presorted_keys);
+
+ if (!is_sorted && (presorted_keys > 0))
+ {
+ /* Also consider incremental sort. */
+ subpath = (Path *)
create_incremental_sort_path(root,
+
rel,
+
subpath,
+
useful_pathkeys,
+
presorted_keys,
+
-1);
+
+ path = create_gather_merge_path(root, rel,
subpath, rel->reltarget,
+
subpath->pathkeys, NULL, rowsp);
+
+ add_path(rel, &path->path);
+ }
+ }
+
}
}
diff --git a/src/backend/optimizer/plan/createplan.c
b/src/backend/optimizer/plan/createplan.c
index 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
--
2.20.1
>From e6894cf4dd0c7c6db0fe11089fff4cf05794b97f Mon Sep 17 00:00:00 2001
From: Tomas Vondra <to...@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.c
index 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.20.1
>From 3ab9a075e7569abda2cf717e06e27d0ec258b59c Mon Sep 17 00:00:00 2001
From: Tomas Vondra <to...@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.c
index 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.20.1
>From 091627c63cfb7ab47bfb76f6a96f94370aeea28d Mon Sep 17 00:00:00 2001
From: Tomas Vondra <to...@2ndquadrant.com>
Date: Tue, 9 Jul 2019 02:14:18 +0200
Subject: [PATCH 4/4] rework where incremental sort paths are created
---
src/backend/optimizer/path/allpaths.c | 269 -----------------------
src/backend/optimizer/plan/planner.c | 299 ++++++++++++++++++++++++++
2 files changed, 299 insertions(+), 269 deletions(-)
diff --git a/src/backend/optimizer/path/allpaths.c
b/src/backend/optimizer/path/allpaths.c
index 34a0fb4d32..3efc807164 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2665,242 +2665,6 @@ set_worktable_pathlist(PlannerInfo *root, RelOptInfo
*rel, RangeTblEntry *rte)
add_path(rel, create_worktablescan_path(root, rel, required_outer));
}
-
-
-/*
- * 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_gather_paths
* Generate parallel access paths for a relation by pushing a
Gather or
@@ -2955,10 +2719,6 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo
*rel, bool override_rows)
{
Path *subpath = (Path *) lfirst(lc);
GatherMergePath *path;
- bool is_sorted;
- int presorted_keys;
- List *useful_pathkeys_list = NIL; /* List of all pathkeys
*/
- ListCell *lc;
if (subpath->pathkeys == NIL)
continue;
@@ -2967,35 +2727,6 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo
*rel, bool override_rows)
path = create_gather_merge_path(root, rel, subpath,
rel->reltarget,
subpath->pathkeys, NULL, rowsp);
add_path(rel, &path->path);
-
- /* consider incremental sort for interesting orderings */
- useful_pathkeys_list = get_useful_pathkeys_for_relation(root,
rel);
-
- foreach(lc, useful_pathkeys_list)
- {
- List *useful_pathkeys = lfirst(lc);
-
- is_sorted =
pathkeys_common_contained_in(useful_pathkeys,
-
subpath->pathkeys,
-
&presorted_keys);
-
- if (!is_sorted && (presorted_keys > 0))
- {
- /* Also consider incremental sort. */
- subpath = (Path *)
create_incremental_sort_path(root,
-
rel,
-
subpath,
-
useful_pathkeys,
-
presorted_keys,
-
-1);
-
- path = create_gather_merge_path(root, rel,
subpath, rel->reltarget,
-
subpath->pathkeys, NULL, rowsp);
-
- add_path(rel, &path->path);
- }
- }
-
}
}
diff --git a/src/backend/optimizer/plan/planner.c
b/src/backend/optimizer/plan/planner.c
index 16996b1bc2..ecad427c40 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);
+ }
+
}
/*
--
2.20.1
