Over on the -bugs list we had a report [1] of a seg fault with
incremental sort. The short of the investigation there was that a
subplan wasn't being serialized since it wasn't parallel safe, and
that attempting to initialize that subplan resulted in the seg fault.
Tom pushed a change to raise an ERROR when this occurs so that at
least we don't crash the server.
There was some small amount of discussion about this on a thread about
a somewhat similar issue [2] (where volatile expressions were the
issue), but that thread resulted in a committed patch, and beyond that
it seems that this issue deserves its own discussion.
I've been digging further into the problem, and my first question was
"why doesn't this result in a similar error but with a full sort when
incremental sort is disabled?" After all, we have code to consider a
gather merge + full sort on the cheapest partial path in
generate_useful_gather_paths(), and the plan that I get on Luis's test
case with incremental sort disabled has an full sort above a gather,
which presumably it'd be cheaper to push down into the parallel plan
(using gather merge instead of gather).
It turns out that there's a separate bug here: I'm guessing that in
the original commit of generate_useful_gather_paths() we had a
copy/paste thinko in this code:
/*
* If the path has no ordering at all, then we can't use either
* incremental sort or rely on implicit sorting with a gather
* merge.
*/
if (subpath->pathkeys == NIL)
continue;
The comment claims that we should skip subpaths that aren't sorted at
all since we can't possibly use a gather merge directly or with an
incremental sort applied first. It's true that we can't do either of
those things unless the subpath is already at least partially sorted.
But subsequently we attempt to construct a gather merge path on top of
a full sort (for the cheapest path), and there's no reason to limit
that to partially sorted paths (indeed in the presence of incremental
sort it seems unlikely that that would be the cheapest path).
We still don't want to build incremental sort paths if the subpath has
no pathkeys, but that will imply presorted_keys = 0, which we already
check.
So 0001 removes that branch entirely. And, as expected, we now get a
gather merge + full sort the resulting error about subplan not being
initialized.
With that oddity out of the way, I started looking at the actually
reported problem, and nominally issue is that we have a correlated
subquery (in the final target list and the sort clause), and
correlated subqueries (not sure why exactly in this case; see [3])
aren't considered parallel-safe.
As to why that's happening:
1. find_em_expr_usable_for_sorting_rel doesn't exclude that
expression, and arguably correctly so in the general case since one
might (though we don't now) use this same kind of logic for
non-parallel plans.
2. generate_useful_pathkeys_for_relation is noting that it'd be useful
to sort on that expression and sees it as safe in part due to the (1).
3. We create a sort node that includes that expression in its output.
That seems pretty much the same (in terms of safety given generalized
input paths/plans, not in terms of what Robert brought up in [4]) as
what would happen in the prepare_sort_from_pathkeys call in
create_gather_merge_plan.
So to fix this problem I've added the option to find_em_expr_for_rel
to restrict to parallel-safe expressions in 0002.
Given point 3 above (and the discussion with Robert earlier) above it
seems to me that there's a bigger problem here that just hasn't
happened to have been exposed yet: in particular the
prepare_sort_from_pathkeys call in create_gather_merge_plan seems
suspect to me. But it's also possible other usages of
prepare_sort_from_pathkeys could be suspect given other seemingly
unrelated changed to path generation, since nothing other than
implicit knowledge about the conventions here prevents us from
introducing paths generating sorts with expressions not in the target
list (in fact a part of the issue here IMO is that non-var expression
pathkeys are added to the target list after path generation and
selection is completed).
Alternatively we could "fix" this by being even more conservative in
find_em_expr_usable_for_sorting_rel and disregard any expressions not
currently found in the target list. But that seems unsatisfactory to
me since, given we know that there are cases where
prepare_sort_from_paths is explicitly intended to add pathkey
expressions to the target list, we'd be excluding possible useful
cases (and indeed we already have, albeit contrived, test cases that
fail if that change is made).
There exists a very similar path in the postgres fdw code (in fact the
function name is the same: get_useful_pathkeys_for_relation) since
find_em_expr_for_rel is much simpler (it doesn't do many safety checks
at all like we do in find_em_expr_usable_for_sorting_rel), but I think
that's safe (though I haven't thought about it a ton) because I
believe those are sort keys we're going to send to the foreign server
anyway, as opposed to sorting ourselves (but I haven't verified that
that's the case and that we never create sort nodes there).
James
1:
https://www.postgresql.org/message-id/622580997.37108180.1604080457319.JavaMail.zimbra%40siscobra.com.br
2:
https://www.postgresql.org/message-id/CAJGNTeNaxpXgBVcRhJX%2B2vSbq%2BF2kJqGBcvompmpvXb7pq%2BoFA%40mail.gmail.com
3:
https://www.postgresql.org/message-id/CAAaqYe_vihKjc%2B8LuQa49EHW4%2BKfefb3wHqPYFnCuUqozo%2BLFg%40mail.gmail.com
4:
https://www.postgresql.org/message-id/CA%2BTgmobX2079GNJWJVFjo5CmwTg%3DoQQOybFQL2CyZxMY59P6BA%40mail.gmail.com
From 11cb504dca05d93e40a97fa4fe13202a59664950 Mon Sep 17 00:00:00 2001
From: James Coleman <jtc...@gmail.com>
Date: Fri, 20 Nov 2020 20:29:51 -0500
Subject: [PATCH v1 2/2] Enforce parallel safety of pathkeys in
generate_useful_gather_paths
If, for example, a pathkey expression (e.g., a correlated subquery which
is currently always treated this way) is unsafe for parallel query then
we must not generate a gather merge path with either incremental or full
sort including that pathkey.
---
src/backend/optimizer/path/allpaths.c | 13 ++++--
src/backend/optimizer/path/equivclass.c | 8 +++-
src/include/optimizer/paths.h | 2 +-
.../regress/expected/incremental_sort.out | 40 +++++++++++++++++++
src/test/regress/sql/incremental_sort.sql | 11 +++++
5 files changed, 69 insertions(+), 5 deletions(-)
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 672a20760c..ac21b08801 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2802,6 +2802,9 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
* This allows us to do incremental sort on top of an index scan under a gather
* merge node, i.e. parallelized.
*
+ * If the parallel argument is true then we'll require that pathkey expressions
+ * be parallel safe.
+ *
* XXX At the moment this can only ever return a list with a single element,
* because it looks at query_pathkeys only. So we might return the pathkeys
* directly, but it seems plausible we'll want to consider other orderings
@@ -2809,7 +2812,7 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
* merge joins.
*/
static List *
-get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel)
+get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel, bool parallel)
{
List *useful_pathkeys_list = NIL;
@@ -2839,8 +2842,12 @@ get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel)
* meet criteria of EC membership in the current relation, we
* enable not just an incremental sort on the entirety of
* query_pathkeys but also incremental sort below a JOIN.
+ *
+ * By passing true for the final argument
+ * find_em_expr_usable_for_sorting_rel will ensure the chosen
+ * expression is parallel safe.
*/
- if (!find_em_expr_usable_for_sorting_rel(pathkey_ec, rel))
+ if (!find_em_expr_usable_for_sorting_rel(root, pathkey_ec, rel, true))
break;
npathkeys++;
@@ -2894,7 +2901,7 @@ generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_r
generate_gather_paths(root, rel, override_rows);
/* consider incremental sort for interesting orderings */
- useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel);
+ useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel, true);
/* used for explicit (full) sort paths */
cheapest_partial_path = linitial(rel->partial_pathlist);
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index f98fd7b3eb..456ab04f33 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -801,9 +801,12 @@ find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel)
* Find an equivalence class member expression that can be safely used by a
* sort node on top of the provided relation. The rules here must match those
* applied in prepare_sort_from_pathkeys.
+ *
+ * If parallel is set to true, then we'll also enforce that the chosen
+ * expression is parallel safe.
*/
Expr *
-find_em_expr_usable_for_sorting_rel(EquivalenceClass *ec, RelOptInfo *rel)
+find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel, bool parallel)
{
ListCell *lc_em;
@@ -833,6 +836,9 @@ find_em_expr_usable_for_sorting_rel(EquivalenceClass *ec, RelOptInfo *rel)
if (!bms_is_subset(em->em_relids, rel->relids))
continue;
+ if (parallel && !is_parallel_safe(root, (Node *) em->em_expr))
+ continue;
+
/*
* As long as the expression isn't volatile then
* prepare_sort_from_pathkeys is able to generate a new target entry,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 8a4c6f8b59..afe1b41a4d 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -135,7 +135,7 @@ extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root,
Relids rel,
bool create_it);
extern Expr *find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel);
-extern Expr *find_em_expr_usable_for_sorting_rel(EquivalenceClass *ec, RelOptInfo *rel);
+extern Expr *find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel, bool parallel);
extern void generate_base_implied_equalities(PlannerInfo *root);
extern List *generate_join_implied_equalities(PlannerInfo *root,
Relids join_relids,
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 51471ae92d..d316a7c4b9 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1551,6 +1551,46 @@ order by 1, 2;
-> Function Scan on generate_series
(7 rows)
+-- Parallel sort but with expression (correlated subquery) that
+-- is prohibited in parallel plans.
+explain (costs off) select distinct
+ unique1,
+ (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
+from tenk1 t, generate_series(1, 1000);
+ QUERY PLAN
+---------------------------------------------------------------------------------
+ Unique
+ -> Sort
+ Sort Key: t.unique1, ((SubPlan 1))
+ -> Gather
+ Workers Planned: 2
+ -> Nested Loop
+ -> Parallel Index Only Scan using tenk1_unique1 on tenk1 t
+ -> Function Scan on generate_series
+ SubPlan 1
+ -> Index Only Scan using tenk1_unique1 on tenk1
+ Index Cond: (unique1 = t.unique1)
+(11 rows)
+
+explain (costs off) select
+ unique1,
+ (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
+from tenk1 t, generate_series(1, 1000)
+order by 1, 2;
+ QUERY PLAN
+---------------------------------------------------------------------------
+ Sort
+ Sort Key: t.unique1, ((SubPlan 1))
+ -> Gather
+ Workers Planned: 2
+ -> Nested Loop
+ -> Parallel Index Only Scan using tenk1_unique1 on tenk1 t
+ -> Function Scan on generate_series
+ SubPlan 1
+ -> Index Only Scan using tenk1_unique1 on tenk1
+ Index Cond: (unique1 = t.unique1)
+(10 rows)
+
-- Parallel sort but with expression not available until the upper rel.
explain (costs off) select distinct sub.unique1, stringu1 || random()::text
from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index cb48f200ce..ff3af0fd16 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -250,6 +250,17 @@ from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
explain (costs off) select sub.unique1, md5(stringu1)
from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
order by 1, 2;
+-- Parallel sort but with expression (correlated subquery) that
+-- is prohibited in parallel plans.
+explain (costs off) select distinct
+ unique1,
+ (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
+from tenk1 t, generate_series(1, 1000);
+explain (costs off) select
+ unique1,
+ (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
+from tenk1 t, generate_series(1, 1000)
+order by 1, 2;
-- Parallel sort but with expression not available until the upper rel.
explain (costs off) select distinct sub.unique1, stringu1 || random()::text
from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
--
2.17.1
From b378e8c2bb76d61da11ce834d55939987ffa1289 Mon Sep 17 00:00:00 2001
From: jcoleman <jtc...@gmail.com>
Date: Fri, 20 Nov 2020 16:19:00 +0000
Subject: [PATCH v1 1/2] generate_useful_gather_paths shouldn't skip unsorted
subpaths
This appears to be a copy/paste thinko from when we added this function.
Here's the issue: the comment claims that we should skip subpaths that
aren't sorted at all since we can't possibly use a gather merge directly
or with an incremental sort applied first. It's true that we can't do
either of those things unless the subpath is already at least partially
sorted. But subsequently we attempt to construct a gather merge path on
top of a full sort (for the cheapest path), and there's no reason to
limit that to partially sorted paths (indeed in the presence of
incremental sort it seems unlikely that that would be the cheapest path).
We still don't want to build incremental sort paths if the subpath has
no pathkeys, but that will imply presorted_keys = 0, which we already
check.
---
src/backend/optimizer/path/allpaths.c | 8 --------
src/test/regress/expected/incremental_sort.out | 13 +++++++++++++
src/test/regress/sql/incremental_sort.sql | 4 ++++
3 files changed, 17 insertions(+), 8 deletions(-)
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 84a69b064a..672a20760c 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2914,14 +2914,6 @@ generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_r
Path *subpath = (Path *) lfirst(lc2);
GatherMergePath *path;
- /*
- * If the path has no ordering at all, then we can't use either
- * incremental sort or rely on implicit sorting with a gather
- * merge.
- */
- if (subpath->pathkeys == NIL)
- continue;
-
is_sorted = pathkeys_count_contained_in(useful_pathkeys,
subpath->pathkeys,
&presorted_keys);
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 7cf2eee7c1..51471ae92d 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1468,6 +1468,19 @@ explain (costs off) select * from t union select * from t order by 1,3;
-> Parallel Seq Scan on t t_1
(13 rows)
+-- Full sort, not just incremental sort can be pushed below a gather merge path
+-- by generate_useful_gather_paths.
+explain (costs off) select distinct a,b from t;
+ QUERY PLAN
+------------------------------------------
+ Unique
+ -> Gather Merge
+ Workers Planned: 2
+ -> Sort
+ Sort Key: a, b
+ -> Parallel Seq Scan on t
+(6 rows)
+
drop table t;
-- Sort pushdown can't go below where expressions are part of the rel target.
-- In particular this is interesting for volatile expressions which have to
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index 3ee11c394b..cb48f200ce 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -220,6 +220,10 @@ explain (costs off) select a,b,sum(c) from t group by 1,2 order by 1,2,3 limit 1
set enable_hashagg to off;
explain (costs off) select * from t union select * from t order by 1,3;
+-- Full sort, not just incremental sort can be pushed below a gather merge path
+-- by generate_useful_gather_paths.
+explain (costs off) select distinct a,b from t;
+
drop table t;
-- Sort pushdown can't go below where expressions are part of the rel target.
--
2.17.1
