Re: UNION ALL on partitioned tables won't use indices.

Hello, Sorry that it's been a while..

1. Observed symptom

As you know, UNION ALL accompanied with ORDER BY uses indexes if
available.

> uniontest=# EXPLAIN SELECT * FROM c11 UNION ALL SELECT * FROM c12 ORDER BY a;
> QUERY PLAN
> ---------------------------------------------------------------------------
> Merge Append (cost=0.59..10214.10 rows=200000 width=16)
> Sort Key: c11.a
> -> Index Scan using ... on c11 (cost=0.29..3857.04 rows=100000 width=16)
> -> Index Scan using ... on c12 (cost=0.29..3857.04 rows=100000 width=16)

So do simple queries on partitioned (inheritance) tables.

> uniontest=# EXPLAIN SELECT * FROM p1 ORDER BY a;
> QUERY PLAN
> ------------------------------------------------------------------------------
> Merge Append (cost=0.73..11392.19 rows=200001 width=16)
> Sort Key: p1.a
> -> Index Scan using ... on p1 (cost=0.12..8.14 rows=1 width=44)
> -> Index Scan using ... on c11 (cost=0.29..3857.04 rows=100000 width=16)
> -> Index Scan using ... on c12 (cost=0.29..3857.04 rows=100000 width=16)

Nevertheless, UNION ALL on partitioned tables doesn't. This is
quite unfavourable behavior especially having LIMIT.

>uniontest=# EXPLAIN ANALYZE SELECT * FROM p1
> UNION ALL SELECT * FROM p2 ORDER BY a LIMIT 10;
> QUERY PLAN
>------------------------------------------------------------------------
> Limit (actual time=182.732..182.735 rows=10 loops=1)
> -> Sort (actual time=182.729..182.730 rows=10 loops=1)
> Sort Key: p1.a
> Sort Method: top-N heapsort Memory: 25kB
> -> Append (actual time=0.029..108.109 rows=400000 loops=1)
> -> Seq Scan on p1 (actual time=0.001..0.001 rows=0 loops=1)
> -> Seq Scan on c11 (actual time=0.027..19.074 rows=100000 loops=1)
> -> Seq Scan on c12 (actual time=0.014..16.653 rows=100000 loops=1)
> -> Seq Scan on p2 (actual time=0.000..0.000 rows=0 loops=1)
> -> Seq Scan on c21 (actual time=0.012..16.677 rows=100000 loops=1)
> -> Seq Scan on c22 (actual time=0.012..16.794 rows=100000 loops=1)
> Total runtime: 182.857 ms

2. The cause

In grouping_planner, flattern_simple_union_all creates
appendrelinfos for each subqueries then expand_inherited_tables
furthur expands the parent tables in each subqueries. Finally,
this sequence leaves following structure. Where rte[2] and [3]
are subqueries abandoned on the way pulling up rte[4] and [5].

rte[1] Subquery "SELECT*1", inh = 1
+- appinfo[0] - rte[4] Relation "p1", inh = 1
| +- appinfo[2] - rte[6] Relation "p1", inh = 0
| +- appinfo[3] - rte[7] Relation "c11", inh = 0
| +- appinfo[4] - rte[8] Relation "c12", inh = 0
+- appinfo[1] - rte[5] Relation "p2", inh = 1
+- appinfo[5] - rte[9] Relation "p1", inh = 0
+- appinfo[6] - rte[10] Relation "c11", inh = 0
+- appinfo[7] - rte[11] Relation "c12", inh = 0

On the other hand, ec member finally has exprs only for varno =
1, 4 and 5, in other words, it lacks the members for the most
descendant RTEs. This is because add_child_rel_equivalences()
always inhibits add_eq_member from registering the child_rel's
relid on EC. Conequently these grandchild relations does not find
index pathkeys for themselves.

3. Measures

I could thought up three approaches for the problem.

One is to simplly modifying here to give child flag in the
parameters of add_eq_member accordig to whether the child_rel is
inh or not. This seems to work fine although leaves two levels of
MergeAppends (PATCH-1). So the additional patch is attached to
collapse these MergeAppends (PATCH-2). This gives the same plan
as PATCH-3.

> uniontest=# explain analyze select * from p1 union all
> select * from p2 order by a limit 10;
> QUERY PLAN
> ------------------------------------------------------------------------
> Limit (actual time=0.208..0.224 rows=10 loops=1)
> -> Merge Append (actual time=0.205..0.218 rows=10 loops=1)
> Sort Key: p1.a
> -> Merge Append (actual time=0.110..0.120 rows=10 loops=1)
> Sort Key: p1.a
> -> Index Scan .. on p1 (actual time=0.006..0.006 rows=0 loops=1)
> -> Index Scan .. on c11 (actual time=0.054..0.060 rows=10 loops=1)
> -> Index Scan .. on c12 (actual time=0.046..0.046 rows=1 loops=1)
> -> Merge Append (actual time=0.093..0.093 rows=1 loops=1)
> Sort Key: p2.a
> -> Index Scan .. on p2 (actual time=0.002..0.002 rows=0 loops=1)
> -> Index Scan .. on c21 (actual time=0.047..0.047 rows=1 loops=1)
> -> Index Scan .. on c22 (actual time=0.043..0.043 rows=1 loops=1)
> Total runtime: 0.448 ms

The second is to collapse the appendrel structure shown above to
have only single level inheritance. This also seems to work
fine. This makes the plan with single level
MergeAppend. (PATCH-3)

> uniontest=# EXPLAIN ANALYZE SELECT * FROM p1 UNION ALL
> SELECT * FROM p2 ORDER BY a LIMIT 10;
> QUERY PLAN
> -------------------------------------------------------------------
> Limit (actual time=0.095..0.107 rows=10 loops=1)
> -> Merge Append (actual time=0.092..0.102 rows=10 loops=1)
> Sort Key: p1.a
> -> Index Scan ... on p1 (actual time=0.005..0.005 rows=0 loops=1)
> -> Index Scan ... on c11 (actual time=0.023..0.030 rows=10 loops=1)
> -> Index Scan ... on c12 (actual time=0.020..0.020 rows=1 lops=1)
> -> Index Scan ... on p2 (actual time=0.001..0.001 rows=0 loops=1)
> -> Index Scan ... on c21 (actual time=0.019..0.019 rows=1 loops=1)
> -> Index Scan ... on c22 (actual time=0.019..0.019 rows=1 loops=1)
> Total runtime: 0.241 ms

The last one is most strait-forward in some sense, and conversely
is most ad hoc measure. Modifying expand_inherited_rtentry() to
pull up adding appendrels if needed, using the similar manner to
PATCH-3. This is added as PATCH-4.

what do you think about this?

Four patches following are attached to this message.

1. union_inh_idx_typ1_v1_20131024.patch .. PATCH-1 described above.
2. union_inh_idx_typ1_add_v1_20131024.patch .. PATCH-2 described above.
3. union_inh_idx_typ2_v1_20131024.patch .. PATCH-3 described above.
4. union_inh_idx_typ3_v1_20131024.patch .. PATCH-4 described above.

regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center

On Thu, Oct 24, 2013 at 6:39 AM, Kyotaro HORIGUCHI
<horiguchi(dot)kyotaro(at)lab(dot)ntt(dot)co(dot)jp> wrote:
> Hello, Sorry that it's been a while..
>
> 1. Observed symptom
>
> As you know, UNION ALL accompanied with ORDER BY uses indexes if
> available.
>
>> uniontest=# EXPLAIN SELECT * FROM c11 UNION ALL SELECT * FROM c12 ORDER BY a;
>> QUERY PLAN
>> ---------------------------------------------------------------------------
>> Merge Append (cost=0.59..10214.10 rows=200000 width=16)
>> Sort Key: c11.a
>> -> Index Scan using ... on c11 (cost=0.29..3857.04 rows=100000 width=16)
>> -> Index Scan using ... on c12 (cost=0.29..3857.04 rows=100000 width=16)
>
> So do simple queries on partitioned (inheritance) tables.
>
>> uniontest=# EXPLAIN SELECT * FROM p1 ORDER BY a;
>> QUERY PLAN
>> ------------------------------------------------------------------------------
>> Merge Append (cost=0.73..11392.19 rows=200001 width=16)
>> Sort Key: p1.a
>> -> Index Scan using ... on p1 (cost=0.12..8.14 rows=1 width=44)
>> -> Index Scan using ... on c11 (cost=0.29..3857.04 rows=100000 width=16)
>> -> Index Scan using ... on c12 (cost=0.29..3857.04 rows=100000 width=16)
>
> Nevertheless, UNION ALL on partitioned tables doesn't. This is
> quite unfavourable behavior especially having LIMIT.
>
>>uniontest=# EXPLAIN ANALYZE SELECT * FROM p1
>> UNION ALL SELECT * FROM p2 ORDER BY a LIMIT 10;
>> QUERY PLAN
>>------------------------------------------------------------------------
>> Limit (actual time=182.732..182.735 rows=10 loops=1)
>> -> Sort (actual time=182.729..182.730 rows=10 loops=1)
>> Sort Key: p1.a
>> Sort Method: top-N heapsort Memory: 25kB
>> -> Append (actual time=0.029..108.109 rows=400000 loops=1)
>> -> Seq Scan on p1 (actual time=0.001..0.001 rows=0 loops=1)
>> -> Seq Scan on c11 (actual time=0.027..19.074 rows=100000 loops=1)
>> -> Seq Scan on c12 (actual time=0.014..16.653 rows=100000 loops=1)
>> -> Seq Scan on p2 (actual time=0.000..0.000 rows=0 loops=1)
>> -> Seq Scan on c21 (actual time=0.012..16.677 rows=100000 loops=1)
>> -> Seq Scan on c22 (actual time=0.012..16.794 rows=100000 loops=1)
>> Total runtime: 182.857 ms
>
>
> 2. The cause
>
> In grouping_planner, flattern_simple_union_all creates
> appendrelinfos for each subqueries then expand_inherited_tables
> furthur expands the parent tables in each subqueries. Finally,
> this sequence leaves following structure. Where rte[2] and [3]
> are subqueries abandoned on the way pulling up rte[4] and [5].
>
> rte[1] Subquery "SELECT*1", inh = 1
> +- appinfo[0] - rte[4] Relation "p1", inh = 1
> | +- appinfo[2] - rte[6] Relation "p1", inh = 0
> | +- appinfo[3] - rte[7] Relation "c11", inh = 0
> | +- appinfo[4] - rte[8] Relation "c12", inh = 0
> +- appinfo[1] - rte[5] Relation "p2", inh = 1
> +- appinfo[5] - rte[9] Relation "p1", inh = 0
> +- appinfo[6] - rte[10] Relation "c11", inh = 0
> +- appinfo[7] - rte[11] Relation "c12", inh = 0
>
> On the other hand, ec member finally has exprs only for varno =
> 1, 4 and 5, in other words, it lacks the members for the most
> descendant RTEs. This is because add_child_rel_equivalences()
> always inhibits add_eq_member from registering the child_rel's
> relid on EC. Conequently these grandchild relations does not find
> index pathkeys for themselves.
>
>
> 3. Measures
>
> I could thought up three approaches for the problem.
>
> One is to simplly modifying here to give child flag in the
> parameters of add_eq_member accordig to whether the child_rel is
> inh or not. This seems to work fine although leaves two levels of
> MergeAppends (PATCH-1). So the additional patch is attached to
> collapse these MergeAppends (PATCH-2). This gives the same plan
> as PATCH-3.
>
>> uniontest=# explain analyze select * from p1 union all
>> select * from p2 order by a limit 10;
>> QUERY PLAN
>> ------------------------------------------------------------------------
>> Limit (actual time=0.208..0.224 rows=10 loops=1)
>> -> Merge Append (actual time=0.205..0.218 rows=10 loops=1)
>> Sort Key: p1.a
>> -> Merge Append (actual time=0.110..0.120 rows=10 loops=1)
>> Sort Key: p1.a
>> -> Index Scan .. on p1 (actual time=0.006..0.006 rows=0 loops=1)
>> -> Index Scan .. on c11 (actual time=0.054..0.060 rows=10 loops=1)
>> -> Index Scan .. on c12 (actual time=0.046..0.046 rows=1 loops=1)
>> -> Merge Append (actual time=0.093..0.093 rows=1 loops=1)
>> Sort Key: p2.a
>> -> Index Scan .. on p2 (actual time=0.002..0.002 rows=0 loops=1)
>> -> Index Scan .. on c21 (actual time=0.047..0.047 rows=1 loops=1)
>> -> Index Scan .. on c22 (actual time=0.043..0.043 rows=1 loops=1)
>> Total runtime: 0.448 ms
>
>
> The second is to collapse the appendrel structure shown above to
> have only single level inheritance. This also seems to work
> fine. This makes the plan with single level
> MergeAppend. (PATCH-3)
>
>> uniontest=# EXPLAIN ANALYZE SELECT * FROM p1 UNION ALL
>> SELECT * FROM p2 ORDER BY a LIMIT 10;
>> QUERY PLAN
>> -------------------------------------------------------------------
>> Limit (actual time=0.095..0.107 rows=10 loops=1)
>> -> Merge Append (actual time=0.092..0.102 rows=10 loops=1)
>> Sort Key: p1.a
>> -> Index Scan ... on p1 (actual time=0.005..0.005 rows=0 loops=1)
>> -> Index Scan ... on c11 (actual time=0.023..0.030 rows=10 loops=1)
>> -> Index Scan ... on c12 (actual time=0.020..0.020 rows=1 lops=1)
>> -> Index Scan ... on p2 (actual time=0.001..0.001 rows=0 loops=1)
>> -> Index Scan ... on c21 (actual time=0.019..0.019 rows=1 loops=1)
>> -> Index Scan ... on c22 (actual time=0.019..0.019 rows=1 loops=1)
>> Total runtime: 0.241 ms
>
>
>
> The last one is most strait-forward in some sense, and conversely
> is most ad hoc measure. Modifying expand_inherited_rtentry() to
> pull up adding appendrels if needed, using the similar manner to
> PATCH-3. This is added as PATCH-4.
>
>
> what do you think about this?
>
>
> Four patches following are attached to this message.
>
> 1. union_inh_idx_typ1_v1_20131024.patch .. PATCH-1 described above.
> 2. union_inh_idx_typ1_add_v1_20131024.patch .. PATCH-2 described above.
> 3. union_inh_idx_typ2_v1_20131024.patch .. PATCH-3 described above.
> 4. union_inh_idx_typ3_v1_20131024.patch .. PATCH-4 described above.

Please add your patches to the currently-open CommitFest so that we
don't lose track of them.

https://commitfest.postgresql.org/action/commitfest_view/open

I'm not sure which approach to this problem is best, but I agree that
it is worth solving.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Hello,

> Please add your patches to the currently-open CommitFest so that we
> don't lose track of them.
>
> https://commitfest.postgresql.org/action/commitfest_view/open
>
> I'm not sure which approach to this problem is best, but I agree that
> it is worth solving.

Thank you, I've regsitered this on CF3.

--
Kyotaro Horiguchi
NTT Open Source Software Center

On 10/29/13, 11:05 PM, Kyotaro HORIGUCHI wrote:
> Hello,
>
>> Please add your patches to the currently-open CommitFest so that we
>> don't lose track of them.
>>
>> https://commitfest.postgresql.org/action/commitfest_view/open
>>
>> I'm not sure which approach to this problem is best, but I agree that
>> it is worth solving.
>
> Thank you, I've regsitered this on CF3.

Your patch doesn't apply anymore. Please rebase it.

Umm. I might be working on a bit unstable place..

> Your patch doesn't apply anymore. Please rebase it.

Thank you. I rebased all patches to current master.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

On Thu, Oct 24, 2013 at 07:39:53PM +0900, Kyotaro HORIGUCHI wrote:
> 1. Observed symptom
>
> As you know, UNION ALL accompanied with ORDER BY uses indexes if
> available.

> So do simple queries on partitioned (inheritance) tables.

> Nevertheless, UNION ALL on partitioned tables doesn't. This is
> quite unfavourable behavior especially having LIMIT.
>
> >uniontest=# EXPLAIN ANALYZE SELECT * FROM p1
> > UNION ALL SELECT * FROM p2 ORDER BY a LIMIT 10;
> > QUERY PLAN
> >------------------------------------------------------------------------
> > Limit (actual time=182.732..182.735 rows=10 loops=1)
> > -> Sort (actual time=182.729..182.730 rows=10 loops=1)
> > Sort Key: p1.a
> > Sort Method: top-N heapsort Memory: 25kB
> > -> Append (actual time=0.029..108.109 rows=400000 loops=1)
> > -> Seq Scan on p1 (actual time=0.001..0.001 rows=0 loops=1)
> > -> Seq Scan on c11 (actual time=0.027..19.074 rows=100000 loops=1)
> > -> Seq Scan on c12 (actual time=0.014..16.653 rows=100000 loops=1)
> > -> Seq Scan on p2 (actual time=0.000..0.000 rows=0 loops=1)
> > -> Seq Scan on c21 (actual time=0.012..16.677 rows=100000 loops=1)
> > -> Seq Scan on c22 (actual time=0.012..16.794 rows=100000 loops=1)
> > Total runtime: 182.857 ms

That is indeed surprising.

> 2. The cause
>
> In grouping_planner, flattern_simple_union_all creates
> appendrelinfos for each subqueries then expand_inherited_tables
> furthur expands the parent tables in each subqueries. Finally,
> this sequence leaves following structure. Where rte[2] and [3]
> are subqueries abandoned on the way pulling up rte[4] and [5].
>
> rte[1] Subquery "SELECT*1", inh = 1
> +- appinfo[0] - rte[4] Relation "p1", inh = 1
> | +- appinfo[2] - rte[6] Relation "p1", inh = 0
> | +- appinfo[3] - rte[7] Relation "c11", inh = 0
> | +- appinfo[4] - rte[8] Relation "c12", inh = 0
> +- appinfo[1] - rte[5] Relation "p2", inh = 1
> +- appinfo[5] - rte[9] Relation "p1", inh = 0
> +- appinfo[6] - rte[10] Relation "c11", inh = 0
> +- appinfo[7] - rte[11] Relation "c12", inh = 0
>
> On the other hand, ec member finally has exprs only for varno =
> 1, 4 and 5, in other words, it lacks the members for the most
> descendant RTEs. This is because add_child_rel_equivalences()
> always inhibits add_eq_member from registering the child_rel's
> relid on EC. Conequently these grandchild relations does not find
> index pathkeys for themselves.

I'm unclear on the key ideas behind distinguishing em_is_child members from
ordinary EC members. src/backend/optimizer/README says "These members are
*not* full-fledged members of the EquivalenceClass and do not affect the
class's overall properties at all." Is that an optimization to avoid futile
planner work, or is it necessary for correctness? If the latter, what sort of
query might give wrong answers if an EquivalenceMember were incorrectly added
as em_is_child = false?

> 3. Measures
>
> I could thought up three approaches for the problem.

Thanks for writing up multiple options. My tentative preference is for (3),
then (2), then (1):

> One is to simplly modifying here to give child flag in the
> parameters of add_eq_member accordig to whether the child_rel is
> inh or not. This seems to work fine although leaves two levels of
> MergeAppends (PATCH-1). So the additional patch is attached to
> collapse these MergeAppends (PATCH-2). This gives the same plan
> as PATCH-3.

Revising the append graph this late in planning (create_merge_append_path())
seems like the wrong location. Changing add_child_rel_equivalences() in this
way adds further subtlety to the meaning of em_is_child, and I haven't
comprehended the full implications. Neither of those objections are fatal,
but let's focus on the other two approaches, which avoid those objections.

> The second is to collapse the appendrel structure shown above to
> have only single level inheritance. This also seems to work
> fine. This makes the plan with single level
> MergeAppend. (PATCH-3)

> The last one is most strait-forward in some sense, and conversely
> is most ad hoc measure. Modifying expand_inherited_rtentry() to
> pull up adding appendrels if needed, using the similar manner to
> PATCH-3. This is added as PATCH-4.

The choice between (2) and (3) should depend on the extent of ways in which we
can end up with a nested AppendRelInfo graph. If expand_inherited_rtentry()
is the only place that can introduce nesting, modifying it to stop doing that
makes sense. Otherwise, adding a generic collapse_appendrels() step might
help more situations. expand_inherited_rtentry() is the only culprit I can
identify, so I lean toward approach-3/PATCH-4. For a data point corroborating
that hypothesis, "make check" issues no queries that trigger this warning:

--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -1924,6 +1924,9 @@ add_child_rel_equivalences(PlannerInfo *root,
{
ListCell *lc1;

+ if (root->simple_rte_array[child_rel->relid]->inh)
+ elog(WARNING, "unexpected nested append");
+
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);

On Wed, Nov 13, 2013 at 05:38:11PM +0900, Kyotaro HORIGUCHI wrote:

[Approach (3): union_inh_idx_typ3_v2_20131113.patch]

> @@ -1210,6 +1217,34 @@ expand_inherited_tables(PlannerInfo *root)
> }
> }
>
> +static Node *
> +transvars_merge_mutator(Node *node, transvars_merge_context *ctx)
> +{
> + if (node == NULL)
> + return NULL;
> +
> + if (IsA(node, Var))
> + {
> + Var *oldv = (Var*)node;
> +
> + if (!oldv->varlevelsup && oldv->varno == ctx->target_rti)
> + {
> + if (oldv->varattno >
> + list_length(ctx->child_appinfo->translated_vars))
> + elog(ERROR,
> + "attribute %d of relation \"%s\" does not exist",
> + oldv->varattno,
> + get_rel_name(ctx->child_appinfo->parent_reloid));
> +
> + return (Node*)copyObject(
> + list_nth(ctx->child_appinfo->translated_vars,
> + oldv->varattno - 1));
> + }
> + }
> + return expression_tree_mutator(node,
> + transvars_merge_mutator, (void*)ctx);
> +}

This has roughly the same purpose as adjust_appendrel_attrs_mutator(), but it
propagates the change to far fewer node types. Why can it be so much simpler?
The translated_vars of parent_appinfo may bear mostly-arbitrary expressions.

> + appinfo->translated_vars = (List*)expression_tree_mutator(
> + parent_appinfo->translated_vars,
> + transvars_merge_mutator, &ctx);

I get this warning:

prepunion.c: In function `expand_inherited_rtentry':
prepunion.c:1450: warning: passing argument 1 of `expression_tree_mutator' from incompatible pointer type

I filled out your test case as follows to reproduce your results:

create table p1 (a int, b int);
create table c11 () inherits (p1);
create table c12 () inherits (p1);
create table p2 (a int, b int);
create table c21 () inherits (p2);
create table c22 () inherits (p2);
alter table p1 add primary key (a);
alter table c11 add primary key (a);
alter table c12 add primary key (a);
alter table p2 add primary key (a);
alter table c21 add primary key (a);
alter table c22 add primary key (a);
EXPLAIN ANALYZE SELECT * FROM p1 UNION ALL SELECT * FROM p2 ORDER BY a LIMIT 10;

However, adding a qual to one of the inheritance queries once again defeated
MergeAppend with the patches for approaches (2) and (3). The approach-1 patch
gives a segfault. Test queries:

-- uses MergeAppend for p1
EXPLAIN ANALYZE SELECT * FROM p1 WHERE b <> 0 ORDER BY a;
-- no MergeAppend for p1
EXPLAIN ANALYZE SELECT * FROM p1 WHERE b <> 0 UNION ALL SELECT * FROM p2 ORDER BY a;

I did not study this further to identify the cause. However, I am suspicious
that we're missing much of the work in set_append_rel_size(), notably the
transfer of baserestrictinfo to the child. set_append_rel_size() identifies
the need to do that work based on AppendRelId parent_relid connectivity, but
we can now flatten that graph in an earlier step.

Approaches (2) and (3) leave the inheritance parent with rte->inh == true
despite no AppendRelInfo pointing to it as their parent. Until now,
expand_inherited_rtentry() has been careful to clear rte->inh in such cases.
My gut feeling is that we should retain that property; what do you think?

Finally, the patch should add test cases.

Thanks,
nm

--
Noah Misch
EnterpriseDB http://www.enterprisedb.com

Noah Misch <noah(at)leadboat(dot)com> writes:
> I'm unclear on the key ideas behind distinguishing em_is_child members from
> ordinary EC members. src/backend/optimizer/README says "These members are
> *not* full-fledged members of the EquivalenceClass and do not affect the
> class's overall properties at all." Is that an optimization to avoid futile
> planner work, or is it necessary for correctness? If the latter, what sort of
> query might give wrong answers if an EquivalenceMember were incorrectly added
> as em_is_child = false?

See commit dd4134ea, which added that text. IIRC, the key point is that
among "real" EC members, there will never be duplicates: a Var "x.y"
for instance cannot appear in two different ECs, because we'd have merged
the two ECs into one instead. However, this property does *not* hold for
child EC members. The problem is that two completely unrelated UNION ALL
child subselects might have, say, constant "1" in their tlists. This
should not lead to concluding that we can merge ECs that mention their
UNION ALL parent variables.

I've not looked at these patches yet, but if they're touching equivclass.c
at all, I'd guess that it's wrong. I think what we want is for appendrel
formation to take care of flattening nested appendrels. The core of the
problem is that pull_up_simple_union_all handles that for nested
UNION ALLs, and expand_inherited_rtentry sees to it by letting
find_all_inheritors do the recursion, but the two cases don't know about
each other.

My gut feeling after two minutes' thought is that the best fix is for
expand_inherited_rtentry to notice when the parent table is already an
appendrel member, and enlarge that appendrel instead of making a new one.
(This depends on the assumption that pull_up_simple_union_all always
happens first, but that seems OK.) I'm not sure if that concept exactly
corresponds to either PATCH-3 or PATCH-4, but that's the way I'd think
about it.

> However, adding a qual to one of the inheritance queries once again defeated
> MergeAppend with the patches for approaches (2) and (3).

That's an independent limitation, see is_safe_append_member:

* Also, the child can't have any WHERE quals because there's no place to
* put them in an appendrel. (This is a bit annoying...)

It'd be nice to fix that, but it's not going to be easy, and it should
be a separate patch IMO. It's pretty much unrelated to the question at
hand here.

> Approaches (2) and (3) leave the inheritance parent with rte->inh == true
> despite no AppendRelInfo pointing to it as their parent. Until now,
> expand_inherited_rtentry() has been careful to clear rte->inh in such cases.
> My gut feeling is that we should retain that property; what do you think?

Yes. IIRC, failing to clear rte->inh doesn't actually break anything,
but it will lead to wasted work later in the planner.

> Finally, the patch should add test cases.

Agreed, at least one example showing that flattening does happen.

regards, tom lane

On Sat, Nov 23, 2013 at 01:35:32PM -0500, Tom Lane wrote:
> Noah Misch <noah(at)leadboat(dot)com> writes:
> > I'm unclear on the key ideas behind distinguishing em_is_child members from
> > ordinary EC members. src/backend/optimizer/README says "These members are
> > *not* full-fledged members of the EquivalenceClass and do not affect the
> > class's overall properties at all." Is that an optimization to avoid futile
> > planner work, or is it necessary for correctness? If the latter, what sort of
> > query might give wrong answers if an EquivalenceMember were incorrectly added
> > as em_is_child = false?
>
> See commit dd4134ea, which added that text. IIRC, the key point is that
> among "real" EC members, there will never be duplicates: a Var "x.y"
> for instance cannot appear in two different ECs, because we'd have merged
> the two ECs into one instead. However, this property does *not* hold for
> child EC members. The problem is that two completely unrelated UNION ALL
> child subselects might have, say, constant "1" in their tlists. This
> should not lead to concluding that we can merge ECs that mention their
> UNION ALL parent variables.

Thanks for the pointer; I found things clearer after reviewing the ECs from
the test case queries from commits dd4134ea and 57664ed2.

> I've not looked at these patches yet, but if they're touching equivclass.c
> at all, I'd guess that it's wrong.

Only PATCH-1 touched equivclass.c.

> My gut feeling after two minutes' thought is that the best fix is for
> expand_inherited_rtentry to notice when the parent table is already an
> appendrel member, and enlarge that appendrel instead of making a new one.
> (This depends on the assumption that pull_up_simple_union_all always
> happens first, but that seems OK.) I'm not sure if that concept exactly
> corresponds to either PATCH-3 or PATCH-4, but that's the way I'd think
> about it.

PATCH-4 does approximately that. I agree that's the right general direction.

> > However, adding a qual to one of the inheritance queries once again defeated
> > MergeAppend with the patches for approaches (2) and (3).
>
> That's an independent limitation, see is_safe_append_member:
>
> * Also, the child can't have any WHERE quals because there's no place to
> * put them in an appendrel. (This is a bit annoying...)
>
> It'd be nice to fix that, but it's not going to be easy, and it should
> be a separate patch IMO. It's pretty much unrelated to the question at
> hand here.

After further study, I agree. It would still be good to understand why that
test case crashed PATCH-1, then ensure that the other patches don't have a
similar lurking bug.

An alternative to extending our ability to pull up UNION ALL subqueries,
having perhaps broader applicability, would be to push down the
possibly-useful sort order to subqueries we can't pull up. We'd sometimes
have two levels of MergeAppend, but that could still handily beat the
explicit-sort plan. In any case, it is indeed a separate topic. For the sake
of the archives, you can get such plans today by manually adding the ORDER BY
to the relevant UNION ALL branch:

EXPLAIN (ANALYZE) (SELECT oid, * FROM pg_proc WHERE protransform = 0 ORDER BY oid)
UNION ALL SELECT oid, * FROM pg_proc ORDER BY 1 LIMIT 5;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.57..1.31 rows=5 width=544) (actual time=0.102..0.155 rows=5 loops=1)
-> Merge Append (cost=0.57..748.25 rows=5084 width=544) (actual time=0.095..0.130 rows=5 loops=1)
Sort Key: pg_proc_1.oid
-> Index Scan using pg_proc_oid_index on pg_proc pg_proc_1 (cost=0.28..332.83 rows=2538 width=544) (actual time=0.058..0.069 rows=3 loops=1)
Filter: ((protransform)::oid = 0::oid)
-> Index Scan using pg_proc_oid_index on pg_proc (cost=0.28..326.47 rows=2546 width=544) (actual time=0.029..0.036 rows=3 loops=1)

--
Noah Misch
EnterpriseDB http://www.enterprisedb.com

Thank you.

I'll soon come up with regress for the patch 3, 4.

=====
> > See commit dd4134ea, which added that text. IIRC, the key point is that
> > among "real" EC members, there will never be duplicates: a Var "x.y"
> > for instance cannot appear in two different ECs, because we'd have merged
> > the two ECs into one instead. However, this property does *not* hold for
> > child EC members. The problem is that two completely unrelated UNION ALL
> > child subselects might have, say, constant "1" in their tlists. This
> > should not lead to concluding that we can merge ECs that mention their
> > UNION ALL parent variables.
> Thanks for the pointer; I found things clearer after reviewing the ECs from
> the test case queries from commits dd4134ea and 57664ed2.

Is it correct that ec-members are parted into two groups one of
which is 'full-fledged' and never duplicate among different ECs
so as to be useful for forming pathkeys (parent) and another is
immatured and might be duplicate which could not form
pathkeys. Thus the new-in-patch-1 third group which is not
duplicate (because they should be always be Var "x.y" (for this
case)) but immatured (child) currently can not be adequately
classified?

My PATCH-1 which make them in the third group forcibly
classified as 'parent' instead of 'child' as before therefore
makes 'broken' ec member?

> > I've not looked at these patches yet, but if they're touching equivclass.c
> > at all, I'd guess that it's wrong.
>
> Only PATCH-1 touched equivclass.c.

Surely.

> > My gut feeling after two minutes' thought is that the best fix is for
> > expand_inherited_rtentry to notice when the parent table is already an
> > appendrel member, and enlarge that appendrel instead of making a new one.
> > (This depends on the assumption that pull_up_simple_union_all always
> > happens first, but that seems OK.) I'm not sure if that concept exactly
> > corresponds to either PATCH-3 or PATCH-4, but that's the way I'd think
> > about it.
>
> PATCH-4 does approximately that. I agree that's the right
> general direction.

Ok, I'll provide regress for the patches 3 and 4.

> An alternative to extending our ability to pull up UNION ALL subqueries,
> having perhaps broader applicability, would be to push down the
> possibly-useful sort order to subqueries we can't pull up. We'd sometimes
> have two levels of MergeAppend, but that could still handily beat the
> explicit-sort plan. In any case, it is indeed a separate topic. For the sake
> of the archives, you can get such plans today by manually adding the ORDER BY
> to the relevant UNION ALL branch:

Yes, but this seems could be done in path-generation phase or
earlier (that's mere a smattering).

--
Kyotaro Horiguchi
NTT Open Source Software Center

Hello,

> I'll soon come up with regress for the patch 3, 4.

New version patches added with regression tests are attached.

I'll show you pulling-up-in-expand_inherited_rtentry version
later.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Kyotaro HORIGUCHI <horiguchi(dot)kyotaro(at)lab(dot)ntt(dot)co(dot)jp> writes:
> My PATCH-1 which make them in the third group forcibly
> classified as 'parent' instead of 'child' as before therefore
> makes 'broken' ec member?

If you marked child entries as non-child, then yes, it's broken.

The definition of a regular EC member is that it's always equal to any
other regular member of that EC, in any row that's had all available WHERE
filter constraints applied to it. This cannot be true for child members
because those are only valid in a subset of rows. Consider

SELECT * FROM t1, (SELECT y FROM t2 UNION ALL SELECT 0 AS y FROM t3) ss
WHERE t1.x = ss.y

We will put t1.x and ss.y into an EC, where ss.y is a variable of the
appendrel representing the union. Then we'll put t2.y and constant 0
into the EC as child members. It would be incorrect to deduce "t1.x = 0"
from this --- while that *is* a valid constraint for join rows arising
from rows out of t3, it's incorrect for rows arising from rows out of t2,
so it's not universally valid.

Basically the point here is that deductions involving child EC members
are one-way. You can use them to generate constraints to apply to a
scan of the associated appendrel member, but not to generate constraints
that would apply to other relations in the query.

In a situation where you're considering "grandchild" elements, both those
and the original children have to be marked as children, because all of
them represent only subsets of rows of the appendrel.

regards, tom lane

This is cont'd from previous CF3.

You'll see the overview and the discussion since in the thread
begins from there. The issue ramains as of current 9.4dev head.

http://www.postgresql.org/message-id/20131024.193953.233464126.horiguchi.kyotaro@lab.ntt.co.jp

The issue in brief is that UNION ALL on inheritance tables does
not make use of indices in contrast to that on bare tables. This
is because of appendrels with the depth more than 2 levels
brought by inheritance tables.

Some of UNION ALL operation - especially using ORDERBY and LIMIT
- will be accelerated by this patch. Details in the message
above.

I proposed 3 types of solution but the one of them - tweaking
Equivalence Class (Type 1)- was dismissed because of
inappropriate manipulation on Equivalence Class. The rest do
essentially the same thing - flattening appendrels - at different
timings.

In type 2, the process is implemented as a generic appendrel
flattening function and applied after expand_inherited_tables()
in subquery_planner.

In type 3, the equivelant process is combined in
expand_inherited_rtentry().

Type 2 loops once for whole appendrel list (in most cases) so it
might be more effective than type 3 which searches the parent
appendrel for each appended ones. Type 3 is more approprieate
design assuming that appendrel tree deeper than 2 levels will be
generated only by expand_inherited_tables().

The attached two patches are rebased to current 9.4dev HEAD and
make check at the topmost directory and src/test/isolation are
passed without error. One bug was found and fixed on the way. It
was an assertion failure caused by probably unexpected type
conversion introduced by collapse_appendrels() which leads
implicit whole-row cast from some valid reltype to invalid
reltype (0) into adjust_appendrel_attrs_mutator().

Attached files are the two versions of patches mentioned above.

- unionall_inh_idx_typ2_v4_20140114.patch
- unionall_inh_idx_typ3_v4_20140114.patch

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

On Tue, Jan 14, 2014 at 06:04:47PM +0900, Kyotaro HORIGUCHI wrote:
> I proposed 3 types of solution but the one of them - tweaking
> Equivalence Class (Type 1)- was dismissed because of
> inappropriate manipulation on Equivalence Class. The rest do
> essentially the same thing - flattening appendrels - at different
> timings.
>
> In type 2, the process is implemented as a generic appendrel
> flattening function and applied after expand_inherited_tables()
> in subquery_planner.
>
> In type 3, the equivelant process is combined in
> expand_inherited_rtentry().
>
> Type 2 loops once for whole appendrel list (in most cases) so it
> might be more effective than type 3 which searches the parent
> appendrel for each appended ones. Type 3 is more approprieate
> design assuming that appendrel tree deeper than 2 levels will be
> generated only by expand_inherited_tables().

Let's focus on type 3; Tom and I both found it most promising.

> The attached two patches are rebased to current 9.4dev HEAD and
> make check at the topmost directory and src/test/isolation are
> passed without error. One bug was found and fixed on the way. It
> was an assertion failure caused by probably unexpected type
> conversion introduced by collapse_appendrels() which leads
> implicit whole-row cast from some valid reltype to invalid
> reltype (0) into adjust_appendrel_attrs_mutator().

What query demonstrated this bug in the previous type 2/3 patches?

> - unionall_inh_idx_typ3_v4_20140114.patch

You have not addressed my review comments from November:
http://www.postgresql.org/message-id/20131123073913.GA1008138@tornado.leadboat.com

Specifically, these:

[transvar_merge_mutator()] has roughly the same purpose as
adjust_appendrel_attrs_mutator(), but it propagates the change to far fewer
node types. Why this case so much simpler? The parent translated_vars of
parent_appinfo may bear mostly-arbitrary expressions.

...

I get this warning:

prepunion.c: In function `expand_inherited_rtentry':
prepunion.c:1450: warning: passing argument 1 of `expression_tree_mutator' from incompatible pointer type

...

Approaches (2) and (3) leave the inheritance parent with rte->inh == true
despite no AppendRelInfo pointing to it as their parent. Until now,
expand_inherited_rtentry() has been careful to clear rte->inh in such cases.

--
Noah Misch
EnterpriseDB http://www.enterprisedb.com

Hello, Thank you, and I' sorry to have kept you waiting.

> Let's focus on type 3; Tom and I both found it most promising.

Agreed.

> > The attached two patches are rebased to current 9.4dev HEAD and
> > make check at the topmost directory and src/test/isolation are
> > passed without error. One bug was found and fixed on the way. It
> > was an assertion failure caused by probably unexpected type
> > conversion introduced by collapse_appendrels() which leads
> > implicit whole-row cast from some valid reltype to invalid
> > reltype (0) into adjust_appendrel_attrs_mutator().
>
> What query demonstrated this bug in the previous type 2/3 patches?
>
> > - unionall_inh_idx_typ3_v4_20140114.patch
>
> You have not addressed my review comments from November:
> http://www.postgresql.org/message-id/20131123073913.GA1008138@tornado.leadboat.com

mmm. Sorry, I've overlooked most of it..

em_is_child is no more a issue, and the rest seem to cited below, thanks.

> Specifically, these:
>
> [transvar_merge_mutator()] has roughly the same purpose as
> adjust_appendrel_attrs_mutator(), but it propagates the change to far fewer
> node types. Why this case so much simpler? The parent translated_vars of
> parent_appinfo may bear mostly-arbitrary expressions.

There are only two places where AppendRelInfo node is generated,
expand_inherited_rtentry and
pull_up_union_leaf_queries.(_copyAppendrelInfo is irrelevant to
this discussion.) The core part generating translated_vars for
them are make_inh_translation_list and
make_setop_translation_list respectively. That's all. And they
are essentially works on the same way, making a Var for every
referred target entry of children like following.

| makeVar(varno,
| tle->resno,
| exprType((Node *) tle->expr),
| exprTypmod((Node *) tle->expr),
| exprCollation((Node *) tle->expr),
| 0);

So all we should do to collapse nested appendrels is simplly
connecting each RTEs directly to the root (most ancient?) RTE in
the relationship, resolving Vars like above, as seen in patched
expand_inherited_rtentry.

# If translated_vars are generated always in the way shown above,
# using tree walker might be no use..

This can be done apart from all other stuffs compensating
translation skew done in adjust_appendrel_attrs. I believe they
are in orthogonal relationship.

> Approaches (2) and (3) leave the inheritance parent with rte->inh == true
> despite no AppendRelInfo pointing to it as their parent. Until now,
> expand_inherited_rtentry() has been careful to clear rte->inh in such cases.

Thank you. I missed that point. rte->inh at first works as a
trigger to try expand inheritance and create append_rel_list
entries, and later works to say "dig me through appinfos". From
that point of view, inh of the RTEs whose children took away
should be 0. The two meanings of inh are now become different
from each other so I suppose it'd better rename it, but I don't
come up with good alternatives..

Anyway this is corrected in the patch attached and works as
follows,

BEFORE:
rte[1] Subquery "SELECT*1", inh = 1
+- appinfo[0] - rte[4] Relation "p1", inh = 1
| +- appinfo[2] - rte[6] Relation "p1", inh = 0
| +- appinfo[3] - rte[7] Relation "c11", inh = 0
| +- appinfo[4] - rte[8] Relation "c12", inh = 0
+- appinfo[1] - rte[5] Relation "p2", inh = 1
+- appinfo[5] - rte[9] Relation "p1", inh = 0
+- appinfo[6] - rte[10] Relation "c11", inh = 0
+- appinfo[7] - rte[11] Relation "c12", inh = 0

COLLAPSED:
rte[1] Subquery "SELECT*1", inh = 1
+- appinfo[0] - rte[4] Relation "p1", inh = 1 => 0
+- appinfo[2] - rte[6] Relation "p1", inh = 0
+- appinfo[3] - rte[7] Relation "c11", inh = 0
+- appinfo[4] - rte[8] Relation "c12", inh = 0
+- appinfo[1] - rte[5] Relation "p2", inh = 1 => 0
+- appinfo[5] - rte[9] Relation "p1", inh = 0
+- appinfo[6] - rte[10] Relation "c11", inh = 0
+- appinfo[7] - rte[11] Relation "c12", inh = 0

> I get this warning:
>
> prepunion.c: In function `expand_inherited_rtentry':
> prepunion.c:1450: warning: passing argument 1 of `expression_tree_mutator' from incompatible pointer type

Sorry, I forgot to put a casting to generic type. It is fixed in
the attached version.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

On Tue, Jan 28, 2014 at 06:53:32PM +0900, Kyotaro HORIGUCHI wrote:
> Hello, Thank you, and I' sorry to have kept you waiting.

No hurry.

> > > The attached two patches are rebased to current 9.4dev HEAD and
> > > make check at the topmost directory and src/test/isolation are
> > > passed without error. One bug was found and fixed on the way. It
> > > was an assertion failure caused by probably unexpected type
> > > conversion introduced by collapse_appendrels() which leads
> > > implicit whole-row cast from some valid reltype to invalid
> > > reltype (0) into adjust_appendrel_attrs_mutator().
> >
> > What query demonstrated this bug in the previous type 2/3 patches?

I would still like to know the answer to the above question.

> > [transvar_merge_mutator()] has roughly the same purpose as
> > adjust_appendrel_attrs_mutator(), but it propagates the change to far fewer
> > node types. Why this case so much simpler? The parent translated_vars of
> > parent_appinfo may bear mostly-arbitrary expressions.
>
> There are only two places where AppendRelInfo node is generated,
> expand_inherited_rtentry and
> pull_up_union_leaf_queries.(_copyAppendrelInfo is irrelevant to
> this discussion.) The core part generating translated_vars for
> them are make_inh_translation_list and
> make_setop_translation_list respectively. That's all. And they
> are essentially works on the same way, making a Var for every
> referred target entry of children like following.
>
> | makeVar(varno,
> | tle->resno,
> | exprType((Node *) tle->expr),
> | exprTypmod((Node *) tle->expr),
> | exprCollation((Node *) tle->expr),
> | 0);

It's true that each AppendRelInfo is initially created that way, but they need
not remain so simple. You can assume ctx->child_appinfo->translated_vars
contains only these Var nodes, but parent_appinfo->translated_vars may contain
arbitrary expressions. (I think the pullup_replace_vars() call at
prepjointree.c:954 is where an AppendRelInfo can get non-Var expressions.)

> So all we should do to collapse nested appendrels is simplly
> connecting each RTEs directly to the root (most ancient?) RTE in
> the relationship, resolving Vars like above, as seen in patched
> expand_inherited_rtentry.
>
> # If translated_vars are generated always in the way shown above,
> # using tree walker might be no use..
>
> This can be done apart from all other stuffs compensating
> translation skew done in adjust_appendrel_attrs. I believe they
> are in orthogonal relationship.

Here is a test case that provokes an assertion failure under the patch; I
believe the cause is oversimplification in transvars_merge_mutator():

create table parent (a int, b int);
create table child () inherits (parent);
select parent from parent union all select parent from parent;

While poking at that test case, I noticed that the following test emits three
rows on HEAD and wrongly emits four rows with the patch:

create table parent (a int, b int);
create table child () inherits (parent);
insert into parent values (1,10);
insert into child values (2,20);
select a, b from parent union all select a, b from child;

--
Noah Misch
EnterpriseDB http://www.enterprisedb.com

Hello,

> No hurry.

Thanks.

> > > > The attached two patches are rebased to current 9.4dev HEAD and
> > > > make check at the topmost directory and src/test/isolation are
> > > > passed without error. One bug was found and fixed on the way. It
> > > > was an assertion failure caused by probably unexpected type
> > > > conversion introduced by collapse_appendrels() which leads
> > > > implicit whole-row cast from some valid reltype to invalid
> > > > reltype (0) into adjust_appendrel_attrs_mutator().
> > >
> > > What query demonstrated this bug in the previous type 2/3 patches?
>
> I would still like to know the answer to the above question.

Ouch! Sorry but I couldn't replay the bug just now, please wait
for a while.

> It's true that each AppendRelInfo is initially created that way, but they need
> not remain so simple. You can assume ctx->child_appinfo->translated_vars
> contains only these Var nodes, but parent_appinfo->translated_vars may contain
> arbitrary expressions. (I think the pullup_replace_vars() call at
> prepjointree.c:954 is where an AppendRelInfo can get non-Var expressions.)

Itself is not a problem.

My patch doesn't replace parent's sole Var at top-level with the
corresponding node in child, it repaces any Var node in parent's
expressions in translated_vars with the corresponding node in
child. So expressions in FROM clauses of union's-operand queries
can adequately modifies expressions made in prepjointree. The
query like follows returns correct result with this patch. As I
mentioned before, I think the other stuffs than Var pullup would
be done in adjust_appendrel_attrs separately.

| SELECT (a + 1) as x, (b * 3) as y FROM p1
| UNION ALL
| SELECT (a * 2), (b / 5) FROM p2 ORDER BY x LIMIT 10;

> > So all we should do to collapse nested appendrels is simplly
> > connecting each RTEs directly to the root (most ancient?) RTE in
> > the relationship, resolving Vars like above, as seen in patched
> > expand_inherited_rtentry.
> >
> > # If translated_vars are generated always in the way shown above,
> > # using tree walker might be no use..
> >
> > This can be done apart from all other stuffs compensating
> > translation skew done in adjust_appendrel_attrs. I believe they
> > are in orthogonal relationship.
>
> Here is a test case that provokes an assertion failure under the patch; I
> believe the cause is oversimplification in transvars_merge_mutator():
>
> create table parent (a int, b int);
> create table child () inherits (parent);
> select parent from parent union all select parent from parent;

Wow. Ok, I'm pretty convinced that you're right. I'll dig it on.

> While poking at that test case, I noticed that the following test emits three
> rows on HEAD and wrongly emits four rows with the patch:
>
> create table parent (a int, b int);
> create table child () inherits (parent);
> insert into parent values (1,10);
> insert into child values (2,20);
> select a, b from parent union all select a, b from child;

Mmm. I had the same result. Please let me have a bit more time.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Hello, The attached file
"unionall_inh_idx_typ3_v6_20140203.patch" is the new version of
this patch fixed the 'whole-row-var' bug.

First of all, on second thought about this,

> > create table parent (a int, b int);
> > create table child () inherits (parent);
> > insert into parent values (1,10);
> > insert into child values (2,20);
> > select a, b from parent union all select a, b from child;
>
> Mmm. I had the same result. Please let me have a bit more time.

This turned out to be a correct result. The two tables have
following records after the two INSERTs.

| =# select * from only parent;
| 1 | 10
| (1 row)
|
| =# select * from child;
| 2 | 20
| (1 row)

Then it is natural that the parent-side in the UNION ALL returns
following results.

| =# select * from parent;
| a | b
| ---+----
| 1 | 10
| 2 | 20
| (2 rows)

Finally, the result we got has proved not to be a problem.

====
Second, about the crash in this sql,

> select parent from parent union all select parent from parent;

It is ignored whole-row reference (=0) which makes the index of
child translated-vars list invalid (-1). I completely ignored it
in spite that myself referred to before.

Unfortunately ConvertRowtypeExpr prevents appendrels from being
removed currently, and such a case don't seem to take place so
often, so I decided to exclude the case. In addition, I found
that only setting "rte->inh = false" causes duplicate scanning on
the same relations through abandoned appendrels so I set
parent/child_relid to InvalidOid so as no more to referred to
from the ex-parent (and ex-children).

The following queries seems to work correctly (but with no
optimization) after these fixes.

create table parent (a int, b int);
create table child () inherits (parent);
insert into parent values (1,10);
insert into child values (2,20);
select parent from parent union all select parent from parent;
parent
--------
(1,10)
(2,20)
(1,10)
(2,20)
(4 rows)
select a, parent from parent union all select a,parent from parent;
a | parent
---+--------
1 | (1,10)
2 | (2,20)
1 | (1,10)
2 | (2,20)
(4 rows)
select a, b from parent union all select a, b from parent;
a | b
---+----
1 | 10
2 | 20
1 | 10
2 | 20
(4 rows)
select a, b from parent union all select a, b from child;
a | b
---+----
2 | 20
1 | 10
2 | 20
(3 rows)

> > > > > The attached two patches are rebased to current 9.4dev HEAD and
> > > > > make check at the topmost directory and src/test/isolation are
> > > > > passed without error. One bug was found and fixed on the way. It
> > > > > was an assertion failure caused by probably unexpected type
> > > > > conversion introduced by collapse_appendrels() which leads
> > > > > implicit whole-row cast from some valid reltype to invalid
> > > > > reltype (0) into adjust_appendrel_attrs_mutator().
> > > >
> > > > What query demonstrated this bug in the previous type 2/3 patches?
> >
> > I would still like to know the answer to the above question.

I rememberd after some struggles. It failed during 'make check',
on the following query in inherit.sql.

| update bar set f2 = f2 + 100
| from
| ( select f1 from foo union all select f1+3 from foo ) ss
| where bar.f1 = ss.f1;

The following SQLs causes the same type of crash.

create temp table foo(f1 int, f2 int);
create temp table foo2(f3 int) inherits (foo);
create temp table bar(f1 int, f2 int);
update bar set f2 = 1
from
( select f1 from foo union all select f1+3 from foo ) ss
where bar.f1 = ss.f1;

The tipped stone was "wholerow1" for the subquery created in
preprocess_targetlist.

| /* Not a table, so we need the whole row as a junk var */
| var = makeWholeRowVar(rt_fetch(rc->rti, range_table),
..
| snprintf(resname, sizeof(resname), "wholerow%u", rc->rowmarkId);

Then the finishing blow was a appendRelInfo corresponding to the
var above, whose parent_reltype = 0 and child_reltype != 0, and
of course introduced by my patch. Since such a situation takes
place even for this patch, the modification is left alone.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

On Mon, Feb 03, 2014 at 07:36:22PM +0900, Kyotaro HORIGUCHI wrote:
> > > create table parent (a int, b int);
> > > create table child () inherits (parent);
> > > insert into parent values (1,10);
> > > insert into child values (2,20);
> > > select a, b from parent union all select a, b from child;
> >
> > Mmm. I had the same result. Please let me have a bit more time.
>
> This turned out to be a correct result. The two tables have
> following records after the two INSERTs.
>
> | =# select * from only parent;
> | 1 | 10
> | (1 row)
> |
> | =# select * from child;
> | 2 | 20
> | (1 row)
>
> Then it is natural that the parent-side in the UNION ALL returns
> following results.
>
> | =# select * from parent;
> | a | b
> | ---+----
> | 1 | 10
> | 2 | 20
> | (2 rows)
>
> Finally, the result we got has proved not to be a problem.

The first union branch should return two rows, and the second union branch
should return one row, for a total of three. In any case, I see later in your
mail that you fixed this. The larger point is that this patch has no business
changing the output rows of *any* query. Its goal is to pick a more-efficient
plan for arriving at the same answer. If there's a bug in our current output
for some query, that's a separate discussion from the topic of this thread.

> Second, about the crash in this sql,
>
> > select parent from parent union all select parent from parent;
>
> It is ignored whole-row reference (=0) which makes the index of
> child translated-vars list invalid (-1). I completely ignored it
> in spite that myself referred to before.
>
> Unfortunately ConvertRowtypeExpr prevents appendrels from being
> removed currently, and such a case don't seem to take place so
> often, so I decided to exclude the case.

> + /*
> + * Appendrels which does whole-row-var conversion cannot be
> + * removed. ConvertRowtypeExpr can convert only RELs which can
> + * be referred to using relid.

We have parent and child relids, so it is not clear to me how imposing that
restriction helps us. I replaced transvars_merge_mutator() with a call to
adjust_appendrel_attrs(). This reduces code duplication, and it handles
whole-row references. (I don't think the other nodes adjust_appendrel_attrs()
can handle matter to this caller. translated_vars will never contain join
tree nodes, and I doubt it could contain a PlaceHolderVar with phrels
requiring translation.)

The central design question for this patch seems to be how to represent, in
the range table, the fact that we expanded an inheritance parent despite its
children ending up as appendrel children of a freestanding UNION ALL. The v6
patch detaches the original RTE from the join tree and clears its "inh" flag.
This breaks sepgsql_dml_privileges(), which looks for RTE_RELATION with inh =
true and consults selinux concerning every child table. We could certainly
change the way sepgsql discovers inheritance hierarchies, but nothing clearly
better comes to mind. I selected the approach of preserving the RTE's "inh"
flag, removing the AppendRelInfo connecting that RTE to its enclosing UNION
ALL, and creating no AppendRelInfo children for that RTE. An alternative was
to introduce a new RTE flag, say "append". An inheritance parent under a
UNION ALL would have append = false, inh = true; other inheritance parent RTEs
would have append = true, inh = true; an RTE for UNION ALL itself would have
append = true, inh = false.

> > > > > > The attached two patches are rebased to current 9.4dev HEAD and
> > > > > > make check at the topmost directory and src/test/isolation are
> > > > > > passed without error. One bug was found and fixed on the way. It
> > > > > > was an assertion failure caused by probably unexpected type
> > > > > > conversion introduced by collapse_appendrels() which leads
> > > > > > implicit whole-row cast from some valid reltype to invalid
> > > > > > reltype (0) into adjust_appendrel_attrs_mutator().
> > > > >
> > > > > What query demonstrated this bug in the previous type 2/3 patches?
> > >
> > > I would still like to know the answer to the above question.
>
> I rememberd after some struggles. It failed during 'make check',
> on the following query in inherit.sql.

> [details]

Interesting. Today, the parent_reltype and child_reltype fields of
AppendRelInfo are either both valid or both invalid. Your v6 patch allowed us
to have a valid child_reltype with an invalid parent_reltype. At the moment,
we can't benefit from just one valid reltype. I restored the old invariant.

If the attached patch version looks reasonable, I will commit it.

Incidentally, I tried adding an assertion that append_rel_list does not show
one appendrel as a direct child of another. The following query, off-topic
for the patch at hand, triggered that assertion:

SELECT 0 FROM (SELECT 0 UNION ALL SELECT 0) t0
UNION ALL
SELECT 0 FROM (SELECT 0 UNION ALL SELECT 0) t0;

--
Noah Misch
EnterpriseDB http://www.enterprisedb.com

Thank you for the labor for polishing this patch.

I have no obvious objection at a glance on this new patch.

I agree to commit this if you this is pertinent to commit except
for the issue newly revealed by this patch. Though could you let
me have some more time to examine this by myself and fully
understand the changes what you made?

At Wed, 26 Feb 2014 23:29:35 -0500, Noah Misch wrote
> > Finally, the result we got has proved not to be a problem.
>
> The first union branch should return two rows, and the second union branch
> should return one row, for a total of three. In any case, I see later in your
> mail that you fixed this.

I got it. I confirmed that *after* fixing duplicate rows, then
misunderstood your point.

> The larger point is that this patch has no business
> changing the output rows of *any* query. Its goal is to pick a more-efficient
> plan for arriving at the same answer. If there's a bug in our current output
> for some query, that's a separate discussion from the topic of this thread.

Totally agreed.

> > Second, about the crash in this sql,
> >
> > > select parent from parent union all select parent from parent;
> >
> > It is ignored whole-row reference (=0) which makes the index of
> > child translated-vars list invalid (-1). I completely ignored it
> > in spite that myself referred to before.
> >
> > Unfortunately ConvertRowtypeExpr prevents appendrels from being
> > removed currently, and such a case don't seem to take place so
> > often, so I decided to exclude the case.
>
> > + /*
> > + * Appendrels which does whole-row-var conversion cannot be
> > + * removed. ConvertRowtypeExpr can convert only RELs which can
> > + * be referred to using relid.
>
> We have parent and child relids, so it is not clear to me how imposing that
> restriction helps us. I replaced transvars_merge_mutator() with a call to
> adjust_appendrel_attrs(). This reduces code duplication, and it handles
> whole-row references.

Thank you, I didn't grasp them as a whole..

> (I don't think the other nodes adjust_appendrel_attrs()
> can handle matter to this caller. translated_vars will never contain join
> tree nodes, and I doubt it could contain a PlaceHolderVar with phrels
> requiring translation.)
>
> The central design question for this patch seems to be how to represent, in
> the range table, the fact that we expanded an inheritance parent despite its
> children ending up as appendrel children of a freestanding UNION ALL. The v6
> patch detaches the original RTE from the join tree and clears its "inh" flag.
> This breaks sepgsql_dml_privileges(), which looks for RTE_RELATION with inh =
> true and consults selinux concerning every child table.

Mmm. It was not in my sight. A bit more time is needed to
understand this.

> We could certainly
> change the way sepgsql discovers inheritance hierarchies, but nothing clearly
> better comes to mind. I selected the approach of preserving the RTE's "inh"
> flag, removing the AppendRelInfo connecting that RTE to its enclosing UNION
> ALL, and creating no AppendRelInfo children for that RTE.

Ok, I did that because I was not certain whether removing
"detached" AppendRelInfos are safe or not. It is far smarter than
mine.

> An alternative was
> to introduce a new RTE flag, say "append". An inheritance parent under a
> UNION ALL would have append = false, inh = true; other inheritance parent RTEs
> would have append = true, inh = true; an RTE for UNION ALL itself would have
> append = true, inh = false.

I think that kind of complexity is not necessary for this issue.

> > > > > > > The attached two patches are rebased to current 9.4dev HEAD and
> > > > > > > make check at the topmost directory and src/test/isolation are
> > > > > > > passed without error. One bug was found and fixed on the way. It
> > > > > > > was an assertion failure caused by probably unexpected type
> > > > > > > conversion introduced by collapse_appendrels() which leads
> > > > > > > implicit whole-row cast from some valid reltype to invalid
> > > > > > > reltype (0) into adjust_appendrel_attrs_mutator().
> > > > > >
> > > > > > What query demonstrated this bug in the previous type 2/3 patches?
> > > >
> > > > I would still like to know the answer to the above question.
> >
> > I rememberd after some struggles. It failed during 'make check',
> > on the following query in inherit.sql.
>
> > [details]
>
> Interesting. Today, the parent_reltype and child_reltype fields of
> AppendRelInfo are either both valid or both invalid. Your v6 patch allowed us
> to have a valid child_reltype with an invalid parent_reltype. At the moment,
> we can't benefit from just one valid reltype. I restored the old invariant.

Ok, I understood it.

> If the attached patch version looks reasonable, I will commit it.
>
>
> Incidentally, I tried adding an assertion that append_rel_list does not show
> one appendrel as a direct child of another. The following query, off-topic
> for the patch at hand, triggered that assertion:
>
> SELECT 0 FROM (SELECT 0 UNION ALL SELECT 0) t0
> UNION ALL
> SELECT 0 FROM (SELECT 0 UNION ALL SELECT 0) t0;

This seems not to crash unless this patch is applied, but itself
doesn't seem to be a bug. I think it should be cured along with
this patch even if it is not the issue of this patch.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

On Thu, Feb 27, 2014 at 07:30:57PM +0900, Kyotaro HORIGUCHI wrote:
> Thank you for the labor for polishing this patch.
>
> I have no obvious objection at a glance on this new patch.
>
> I agree to commit this if you this is pertinent to commit except
> for the issue newly revealed by this patch. Though could you let
> me have some more time to examine this by myself and fully
> understand the changes what you made?

Yes; waiting several days is no problem.

> At Wed, 26 Feb 2014 23:29:35 -0500, Noah Misch wrote
> > An alternative was
> > to introduce a new RTE flag, say "append". An inheritance parent under a
> > UNION ALL would have append = false, inh = true; other inheritance parent RTEs
> > would have append = true, inh = true; an RTE for UNION ALL itself would have
> > append = true, inh = false.
>
> I think that kind of complexity is not necessary for this issue.

Agreed.

> > Incidentally, I tried adding an assertion that append_rel_list does not show
> > one appendrel as a direct child of another. The following query, off-topic
> > for the patch at hand, triggered that assertion:
> >
> > SELECT 0 FROM (SELECT 0 UNION ALL SELECT 0) t0
> > UNION ALL
> > SELECT 0 FROM (SELECT 0 UNION ALL SELECT 0) t0;
>
> This seems not to crash unless this patch is applied, but itself
> doesn't seem to be a bug.

To my knowledge, the query does not crash the server under any patch provided
on this thread.

> I think it should be cured along with
> this patch even if it is not the issue of this patch.

That would require changing rather different code, probably something in the
vicinity of pull_up_subqueries(). I'll leave it for another patch.

--
Noah Misch
EnterpriseDB http://www.enterprisedb.com

Noah Misch <noah(at)leadboat(dot)com> writes:
> If the attached patch version looks reasonable, I will commit it.

The test case is completely bogus, as the query explained is significantly
different from the query executed. I'm not sure whether you can just
remove the extra ORDER BY column without getting machine-dependent
results, though.

More generally, I'm afraid the whole approach is probably wrong, or at
least not solving all problems in this area, because of this:

> Incidentally, I tried adding an assertion that append_rel_list does not show
> one appendrel as a direct child of another. The following query, off-topic
> for the patch at hand, triggered that assertion:
> SELECT 0 FROM (SELECT 0 UNION ALL SELECT 0) t0
> UNION ALL
> SELECT 0 FROM (SELECT 0 UNION ALL SELECT 0) t0;

That's not "off topic" at all; it shows that there's not been any effort
to date to flatten appendrel membership, and therefore this partial
implementation is going to miss some cases. It doesn't help to merge an
inheritance-based appendrel into its parent if the query ORDER BY is still
a level or two above that due to UNION ALLs.

I wonder whether we should consider adding a pass to flatten any nested
appendrels after we're done creating them all. Or alternatively, perhaps
rather than changing the representation invariant, we need to take a
harder look at why ordering info isn't getting pushed down through
appendrels.

regards, tom lane

BTW, isn't the proposed change to the comments for adjust_appendrel_attrs
just wrong? If it's correct, why doesn't the Assert(!IsA(node, SubLink))
therein fire? (AFAICS, the existing comment is correct: we don't use
this function until after expression preprocessing is complete.)

regards, tom lane

On Thu, Feb 27, 2014 at 05:47:16PM -0500, Tom Lane wrote:
> BTW, isn't the proposed change to the comments for adjust_appendrel_attrs
> just wrong? If it's correct, why doesn't the Assert(!IsA(node, SubLink))
> therein fire? (AFAICS, the existing comment is correct: we don't use
> this function until after expression preprocessing is complete.)

The comment change is accurate; expand_inherited_tables(), which precedes
subplan conversion, now calls adjust_appendrel_attrs(). I neglected to remove
the SubLink assert or test a scenario actually entailing a SubLink in
translated_vars. Thanks for spotting the problem.

--
Noah Misch
EnterpriseDB http://www.enterprisedb.com

On Thu, Feb 27, 2014 at 05:33:47PM -0500, Tom Lane wrote:
> Noah Misch <noah(at)leadboat(dot)com> writes:
> > If the attached patch version looks reasonable, I will commit it.
>
> The test case is completely bogus, as the query explained is significantly
> different from the query executed. I'm not sure whether you can just
> remove the extra ORDER BY column without getting machine-dependent
> results, though.

Each query tests something slightly different. The EXPLAIN verifies that we
can MergeAppend given this query structure, and the plain SELECT verifies that
any join tree contortions we made to achieve that do not change the answer.

> More generally, I'm afraid the whole approach is probably wrong, or at
> least not solving all problems in this area, because of this:
>
> > Incidentally, I tried adding an assertion that append_rel_list does not show
> > one appendrel as a direct child of another. The following query, off-topic
> > for the patch at hand, triggered that assertion:
> > SELECT 0 FROM (SELECT 0 UNION ALL SELECT 0) t0
> > UNION ALL
> > SELECT 0 FROM (SELECT 0 UNION ALL SELECT 0) t0;
>
> That's not "off topic" at all; it shows that there's not been any effort
> to date to flatten appendrel membership, and therefore this partial
> implementation is going to miss some cases. It doesn't help to merge an
> inheritance-based appendrel into its parent if the query ORDER BY is still
> a level or two above that due to UNION ALLs.

Nonetheless, I find it reasonable to accept a patch that makes
expand_inherited_tables() avoid introducing nested appendrels. Making
pull_up_subqueries() do the same can be a separate effort. There will still
be a pile of ways to stifle MergeAppend, including everything that makes
is_simple_union_all() return false. Having said that, both you and Kyotaro
sound keen to achieve an appendrel flatness invariant in a single patch. If
that's the consensus, I'm fine with bouncing this back so it can happen.

> I wonder whether we should consider adding a pass to flatten any nested
> appendrels after we're done creating them all.

We did consider that upthread. It's a valid option, but I remain more
inclined to teach pull_up_subqueries() to preserve flatness just like
expand_inherited_tables() will.

> Or alternatively, perhaps
> rather than changing the representation invariant, we need to take a
> harder look at why ordering info isn't getting pushed down through
> appendrels.

That could facilitate MergeAppend in considerably more places, such as UNION
ALL containing non-simple branches. I don't have much of a sense concerning
what such a patch would entail.

--
Noah Misch
EnterpriseDB http://www.enterprisedb.com

Hello,

At Thu, 27 Feb 2014 21:53:52 -0500, Noah Misch wrote
> On Thu, Feb 27, 2014 at 05:33:47PM -0500, Tom Lane wrote:
> > Noah Misch <noah(at)leadboat(dot)com> writes:
> > > If the attached patch version looks reasonable, I will commit it.
> >
> > The test case is completely bogus, as the query explained is significantly
> > different from the query executed. I'm not sure whether you can just
> > remove the extra ORDER BY column without getting machine-dependent
> > results, though.
>
> Each query tests something slightly different. The EXPLAIN verifies that we
> can MergeAppend given this query structure, and the plain SELECT verifies that
> any join tree contortions we made to achieve that do not change the answer.

I think Tom said that the second query can yield the same result
even if the 2nd column in orderby is removed so the pertinence of
it seems doubtful. Actually the altered query gave me the same
result on my workset (CentOS6.5/x86-64).

> > More generally, I'm afraid the whole approach is probably wrong, or at
> > least not solving all problems in this area, because of this:
> >
> > > Incidentally, I tried adding an assertion that append_rel_list does not show
> > > one appendrel as a direct child of another. The following query, off-topic
> > > for the patch at hand, triggered that assertion:
> > > SELECT 0 FROM (SELECT 0 UNION ALL SELECT 0) t0
> > > UNION ALL
> > > SELECT 0 FROM (SELECT 0 UNION ALL SELECT 0) t0;
> >
> > That's not "off topic" at all; it shows that there's not been any effort
> > to date to flatten appendrel membership, and therefore this partial
> > implementation is going to miss some cases. It doesn't help to merge an
> > inheritance-based appendrel into its parent if the query ORDER BY is still
> > a level or two above that due to UNION ALLs.
>
> Nonetheless, I find it reasonable to accept a patch that makes
> expand_inherited_tables() avoid introducing nested appendrels. Making
> pull_up_subqueries() do the same can be a separate effort. There will still
> be a pile of ways to stifle MergeAppend, including everything that makes
> is_simple_union_all() return false. Having said that, both you and Kyotaro
> sound keen to achieve an appendrel flatness invariant in a single patch. If
> that's the consensus, I'm fine with bouncing this back so it can happen.

I understood what that query causes and still don't have definite
opinion on which is better between fixing them individually and
in one go. Nontheless, I'd feel more at ease flattening them
altogether regardless of their origin.

> > I wonder whether we should consider adding a pass to flatten any nested
> > appendrels after we're done creating them all.
>
> We did consider that upthread. It's a valid option, but I remain more
> inclined to teach pull_up_subqueries() to preserve flatness just like
> expand_inherited_tables() will.

Yes, the old dumped version of typ2 patch did so. It flattened
appendrel tree for the query prpoerly. Let me hear the reson you
prefer to do so.

> > Or alternatively, perhaps
> > rather than changing the representation invariant, we need to take a
> > harder look at why ordering info isn't getting pushed down through
> > appendrels.
>
> That could facilitate MergeAppend in considerably more places, such as UNION
> ALL containing non-simple branches. I don't have much of a sense concerning
> what such a patch would entail.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Sorry, I did wrong test.

> > > Noah Misch <noah(at)leadboat(dot)com> writes:
> > > > If the attached patch version looks reasonable, I will commit it.
> > >
> > > The test case is completely bogus, as the query explained is significantly
> > > different from the query executed. I'm not sure whether you can just
> > > remove the extra ORDER BY column without getting machine-dependent
> > > results, though.
> >
> > Each query tests something slightly different. The EXPLAIN verifies that we
> > can MergeAppend given this query structure, and the plain SELECT verifies that
> > any join tree contortions we made to achieve that do not change the answer.
>
> I think Tom said that the second query can yield the same result
> even if the 2nd column in orderby is removed so the pertinence of
> it seems doubtful. Actually the altered query gave me the same
> result on my workset (CentOS6.5/x86-64).

No, no! It was actually returned a *different* result. I
accidentially(?) added 'desc' to the '2'. Please forget it.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

On Fri, Feb 28, 2014 at 02:35:50PM +0900, Kyotaro HORIGUCHI wrote:
> At Thu, 27 Feb 2014 21:53:52 -0500, Noah Misch wrote
> > On Thu, Feb 27, 2014 at 05:33:47PM -0500, Tom Lane wrote:
> > > I wonder whether we should consider adding a pass to flatten any nested
> > > appendrels after we're done creating them all.
> >
> > We did consider that upthread. It's a valid option, but I remain more
> > inclined to teach pull_up_subqueries() to preserve flatness just like
> > expand_inherited_tables() will.
>
> Yes, the old dumped version of typ2 patch did so. It flattened
> appendrel tree for the query prpoerly. Let me hear the reson you
> prefer to do so.

Having reviewed my upthread reasoning for preferring one of those two
approaches over the other, it's a weak preference. They have similar runtime
costs. Putting the logic with the code that creates appendrels reduces the
number of code sites one must examine to reason about possible plan
structures. We might not flatten RTE_RELATION appendrel parents exactly the
same way we flatten RTE_SUBQUERY appendrel parents. I would tend to leave
inh=true for the former, for reasons explained in my notes on v7, but set
inh=false for the latter to save needless work. On the other hand, a
flattening pass is less code overall and brings an attractive
uniformity-by-default to the area.

--
Noah Misch
EnterpriseDB http://www.enterprisedb.com

Hello,

> > Yes, the old dumped version of typ2 patch did so. It flattened
> > appendrel tree for the query prpoerly. Let me hear the reson you
> > prefer to do so.
>
> Having reviewed my upthread reasoning for preferring one of those two
> approaches over the other, it's a weak preference. They have similar runtime
> costs. Putting the logic with the code that creates appendrels reduces the
> number of code sites one must examine to reason about possible plan
> structures. We might not flatten RTE_RELATION appendrel parents exactly the
> same way we flatten RTE_SUBQUERY appendrel parents. I would tend to leave
> inh=true for the former, for reasons explained in my notes on v7, but set
> inh=false for the latter to save needless work.

Unfortunately, RTE_SUBQUERY-es with their inh flag cleard might
cause something inconvenient in preprocess_minmax_aggregates()
and/or add_rtes_to_flat_rtable()..

# I haven't found that related to sepgsql, though :-(

I understood that your concern is to deal parent RTEs defferently
according to their relkinds. But I think the inh flags could not
be modified at all for the reason mentioned above.

Finally the seemingly most safe way to exclude removed
intermediate RTEs in subsequent processing is simplly remove
apprelinfos directly linked to them (as did in v7), for both of
the parents, RTE_RELATION and RTE_SUBQUERY. The difference has
disappeared in this story.

At least as of now, inheritance tables define the bottom bound of
a appendrel tree and on the other hand complex(?) union_alls
define the upper bound, and both multilevel (simple)union_alls
and inheritances are flattened individually so all possible
inheritance tree to be collapsed by this patch is only, I think,

Subquery(inh=1)[Relation-inhparent [Relation-child, child, child]]

> On the other hand, a flattening pass is less code overall and
> brings an attractive uniformity-by-default to the area.

Focusing only on the above structure, what we should do to
collapse this tree is only connect the childs to the Subquery
directly, then remove all appendrelinfos connecting to the
Relation-inhparent. inh flag need not to be modified.

# Umm. I strongly suspect that I overlooked something..

Then even widening to general case, the case doesn't seem to
change. All we need to do is, link a child to its grandparent and
isolate the parent removing apprelinfos.

Thoughts?

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

On Mon, Mar 03, 2014 at 07:01:09PM +0900, Kyotaro HORIGUCHI wrote:
> > > Yes, the old dumped version of typ2 patch did so. It flattened
> > > appendrel tree for the query prpoerly. Let me hear the reson you
> > > prefer to do so.
> >
> > Having reviewed my upthread reasoning for preferring one of those two
> > approaches over the other, it's a weak preference. They have similar runtime
> > costs. Putting the logic with the code that creates appendrels reduces the
> > number of code sites one must examine to reason about possible plan
> > structures. We might not flatten RTE_RELATION appendrel parents exactly the
> > same way we flatten RTE_SUBQUERY appendrel parents. I would tend to leave
> > inh=true for the former, for reasons explained in my notes on v7, but set
> > inh=false for the latter to save needless work.
>
> Unfortunately, RTE_SUBQUERY-es with their inh flag cleard might
> cause something inconvenient in preprocess_minmax_aggregates()
> and/or add_rtes_to_flat_rtable()..

preprocess_minmax_aggregates() only cares about RTEs reachable from the join
tree, and the appendrel parents made obsolete by flattening would not be
reachable from the join tree. add_rtes_to_flat_rtable() might be unhappy.

> # I haven't found that related to sepgsql, though :-(
>
> I understood that your concern is to deal parent RTEs defferently
> according to their relkinds. But I think the inh flags could not
> be modified at all for the reason mentioned above.

That's fine, then. It was a minor point.

If you are convinced that a separate flattening pass is best, that suffices
for me at this stage. Please submit the patch you have in mind, incorporating
any improvements from the v7 patch that are relevant to both approaches.

> At least as of now, inheritance tables define the bottom bound of
> a appendrel tree and on the other hand complex(?) union_alls
> define the upper bound, and both multilevel (simple)union_alls
> and inheritances are flattened individually so all possible
> inheritance tree to be collapsed by this patch is only, I think,
>
> Subquery(inh=1)[Relation-inhparent [Relation-child, child, child]]
>
> > On the other hand, a flattening pass is less code overall and
> > brings an attractive uniformity-by-default to the area.
>
> Focusing only on the above structure, what we should do to
> collapse this tree is only connect the childs to the Subquery
> directly, then remove all appendrelinfos connecting to the
> Relation-inhparent. inh flag need not to be modified.
>
> # Umm. I strongly suspect that I overlooked something..
>
> Then even widening to general case, the case doesn't seem to
> change. All we need to do is, link a child to its grandparent and
> isolate the parent removing apprelinfos.

I barely follow what you're saying here. Do you speak of
union_inh_idx_typ2_v2_20131113.patch, unionall_inh_idx_typ3_v7.patch, or some
future design? If we use a separate flattening pass, there's no small limit
on how many layers of appendrel we may need to flatten. pull_up_subqueries()
can create many nested RTE_SUBQUERY appendrel layers; there may be more than
just child, parent and grandparent. There's never more than one layer of
RTE_RELATION appendrel, though.

Thanks,
nm

--
Noah Misch
EnterpriseDB http://www.enterprisedb.com

Noah Misch <noah(at)leadboat(dot)com> writes:
> If you are convinced that a separate flattening pass is best, that suffices
> for me at this stage. Please submit the patch you have in mind, incorporating
> any improvements from the v7 patch that are relevant to both approaches.

I went back and re-read the original message, and this time it struck me
that really the issue here is that add_child_rel_equivalences() doesn't
think it has to deal with the case of a "parent" rel being itself a child.
That's not inherent though; it's just that it didn't occur to me at the
time that such a situation could arise. It takes only very small changes
to allow that to happen.

If you do that, as in the attached changes to equivclass.c, you get
"could not find pathkey item to sort" errors from createplan.c; but
that's just because create_merge_append_plan() is likewise not expecting
the mergeappend's parent rel to be itself a child. Fix for that is
a one-liner, ie, pass down relids.

That gets you to a point where the code generates a valid plan, but it's
got nested MergeAppends, which are unnecessary expense. Kyotaro-san's
original fix for that was overcomplicated. It's sufficient to teach
accumulate_append_subpath() to flatten nested MergeAppendPaths.

In short, the attached patch seems to fix it, for a lot less added
complication than anything else that's been discussed on this thread.
I've only lightly tested it (it could use a new regression test case),
but unless someone can find a flaw I think we should use this approach.

regards, tom lane

Hello,

> > Unfortunately, RTE_SUBQUERY-es with their inh flag cleard might
> > cause something inconvenient in preprocess_minmax_aggregates()
> > and/or add_rtes_to_flat_rtable()..
>
> preprocess_minmax_aggregates() only cares about RTEs reachable from the join
> tree, and the appendrel parents made obsolete by flattening would not be
> reachable from the join tree. add_rtes_to_flat_rtable() might be unhappy.
>
> > # I haven't found that related to sepgsql, though :-(
> >
> > I understood that your concern is to deal parent RTEs defferently
> > according to their relkinds. But I think the inh flags could not
> > be modified at all for the reason mentioned above.
>
> That's fine, then. It was a minor point.

Ya, anyway, inh's alterability during inheritance tree
transformation is not a minor issue, if we choose flattening
rather than equivalance adjustment (what typ1 patch did).

> If you are convinced that a separate flattening pass is best, that suffices
> for me at this stage. Please submit the patch you have in mind, incorporating
> any improvements from the v7 patch that are relevant to both approaches.

All right.

> > At least as of now, inheritance tables define the bottom bound of
> > a appendrel tree and on the other hand complex(?) union_alls
> > define the upper bound, and both multilevel (simple)union_alls
> > and inheritances are flattened individually so all possible
> > inheritance tree to be collapsed by this patch is only, I think,
> >
> > Subquery(inh=1)[Relation-inhparent [Relation-child, child, child]]
> >
> > > On the other hand, a flattening pass is less code overall and
> > > brings an attractive uniformity-by-default to the area.
> >
> > Focusing only on the above structure, what we should do to
> > collapse this tree is only connect the childs to the Subquery
> > directly, then remove all appendrelinfos connecting to the
> > Relation-inhparent. inh flag need not to be modified.
> >
> > # Umm. I strongly suspect that I overlooked something..
> >
> > Then even widening to general case, the case doesn't seem to
> > change. All we need to do is, link a child to its grandparent and
> > isolate the parent removing apprelinfos.
>
> I barely follow what you're saying here. Do you speak of
> union_inh_idx_typ2_v2_20131113.patch, unionall_inh_idx_typ3_v7.patch, or some
> future design?

Sorry, it's about some future design, but the point is inevitable
if we select the 'flattening pass' way.

> If we use a separate flattening pass, there's no small limit
> on how many layers of appendrel we may need to flatten. pull_up_subqueries()
> can create many nested RTE_SUBQUERY appendrel layers; there may be more than
> just child, parent and grandparent. There's never more than one layer of
> RTE_RELATION appendrel, though.

Yes, that is near to my 'general case' I had in my mind something
similar in the structure but different in the source to
inheritance tables, but talking about such possibilities seems
senseless. Now the 'general case' is exactly the same to what you
mentioned above.

On the other hand, Tom gave us a proposal to deal this in
add_child_rel_equivalences(), it is similar at the entry to my
old failed typ1 patch but more profound. I'll consider on this
for now.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Hello, I examined the your patch and it seemed reasonable, but I
have one question about this patch.

You made ec_relids differ to the union of all ec members'
em_relids. Is it right?

====
At Mon, 03 Mar 2014 14:05:10 -0500, Tom Lane wrote
> Noah Misch <noah(at)leadboat(dot)com> writes:
> > If you are convinced that a separate flattening pass is best, that suffices
> > for me at this stage. Please submit the patch you have in mind, incorporating
> > any improvements from the v7 patch that are relevant to both approaches.
>
> I went back and re-read the original message, and this time it struck me
> that really the issue here is that add_child_rel_equivalences() doesn't
> think it has to deal with the case of a "parent" rel being itself a child.

Yes, that is what I tried to solve in one of the first patch but
the brute way led to failure:(

> That's not inherent though; it's just that it didn't occur to me at the
> time that such a situation could arise. It takes only very small changes
> to allow that to happen.

I saw what you did. I marked not-full-fledged eq members as 'not
child'(its real meaning there was full-fledged in contradiction)
to reach the child rels. In contrast, you loosened the ec_relids
shortcut filter and it seems to work but.. Is it right to make
ec_relids different to union of all members' em_relids? This
seems to affect joins afterwards.

> If you do that, as in the attached changes to equivclass.c, you get
> "could not find pathkey item to sort" errors from createplan.c; but
> that's just because create_merge_append_plan() is likewise not expecting
> the mergeappend's parent rel to be itself a child. Fix for that is
> a one-liner, ie, pass down relids.

This seems to just correcting the over simplification by the
assumption that the best_path there cannot have a parent.

> That gets you to a point where the code generates a valid plan, but it's
> got nested MergeAppends, which are unnecessary expense. Kyotaro-san's
> original fix for that was overcomplicated. It's sufficient to teach
> accumulate_append_subpath() to flatten nested MergeAppendPaths.

Ah, it was in typ1-collapse patch. As you might noticed seeing
there, I couldn't put the assumption that directly nested
MergeAppendPaths share the same pathkeys (really?). It's no
problem if the assumption goes on.

> In short, the attached patch seems to fix it, for a lot less added
> complication than anything else that's been discussed on this thread.
> I've only lightly tested it (it could use a new regression test case),
> but unless someone can find a flaw I think we should use this approach.

Mmm. That's motifying but you seems to be right :) Equipping this
with some regression tests become my work from now.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Kyotaro HORIGUCHI <horiguchi(dot)kyotaro(at)lab(dot)ntt(dot)co(dot)jp> writes:
> Hello, I examined the your patch and it seemed reasonable, but I
> have one question about this patch.

> You made ec_relids differ to the union of all ec members'
> em_relids. Is it right?

ec_relids has never included child relids.

regards, tom lane

Hello, I haven't look closer on their relationship.

> > Hello, I examined the your patch and it seemed reasonable, but I
> > have one question about this patch.
>
> > You made ec_relids differ to the union of all ec members'
> > em_relids. Is it right?
>
> ec_relids has never included child relids.

relation.h says that,

| Relids ec_relids; /* all relids appearing in ec_members */
...
| Relids em_relids; /* all relids appearing in em_expr */

But add_eq_member already did this, so the point was whether it's
ok to omit intermediate relations...

| else if (!is_child) /* child members don't add to ec_relids */
| {
| ec->ec_relids = bms_add_members(ec->ec_relids, relids);
| }
| ec->ec_members = lappend(ec->ec_members, em);

I understood that it is ok because an inheritance tree must have
one parent and it can be the representative for whole its
descendents so it's no problem. Thank you, I'll go on.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Kyotaro HORIGUCHI <horiguchi(dot)kyotaro(at)lab(dot)ntt(dot)co(dot)jp> writes:
>> ec_relids has never included child relids.

> relation.h says that,

> | Relids ec_relids; /* all relids appearing in ec_members */
> ...
> | Relids em_relids; /* all relids appearing in em_expr */

Ah. Those comments could use improvement, I guess.

regards, tom lane

Hello. Attached is the 2nd version of 'pushdown in UNION ALL on
partitioned tables' patch type 1 - fix in equiv-member version.

As far as I can see, I have found no problem on the original
Tom's patch. I have no annoyance of modifying inh flag and so
with this.

At Tue, 04 Mar 2014 18:57:56 +0900, Kyotaro HORIGUCHI wrote
me> Mmm. That's motifying but you seems to be right :) Equipping this
me> with some regression tests become my work from now.

And I took an advantage of using Noah's regression test after
some modifications. After all, this patch consists of work of you
all. Thanks for all you did to me.

I simplified the query for regression tests so as to clarify the
objective and getting rid of confisions of readers. Using only
the first column seems to be enough to also make sure of pushing
down and ordering.

Any comments?

At Wed, 05 Mar 2014 13:59:45 -0500, Tom Lane wrote
tgl> >> ec_relids has never included child relids.
> > | Relids ec_relids; /* all relids appearing in ec_members */
> > ...
> > | Relids em_relids; /* all relids appearing in em_expr */
>
> Ah. Those comments could use improvement, I guess.

The revised comment makes it clear. Thank you.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Kyotaro HORIGUCHI <horiguchi(dot)kyotaro(at)lab(dot)ntt(dot)co(dot)jp> writes:
> Hello. Attached is the 2nd version of 'pushdown in UNION ALL on
> partitioned tables' patch type 1 - fix in equiv-member version.

Committed, thanks.

regards, tom lane

Thank you for committing.

At Fri, 28 Mar 2014 11:50:56 -0400, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote in <21426(dot)1396021856(at)sss(dot)pgh(dot)pa(dot)us>
tgl> Kyotaro HORIGUCHI <horiguchi(dot)kyotaro(at)lab(dot)ntt(dot)co(dot)jp> writes:
tgl> > Hello. Attached is the 2nd version of 'pushdown in UNION ALL on
tgl> > partitioned tables' patch type 1 - fix in equiv-member version.
tgl>
tgl> Committed, thanks.
tgl>
tgl> regards, tom lane

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center