Run-time pruning for ModifyTable

Hi David,

On Thu, Jun 27, 2019 at 2:28 PM David Rowley
<david.rowley@2ndquadrant.com> wrote:

Deja vu from this time last year when despite everyone's best efforts
(mostly Alvaro) we missed getting run-time pruning in for MergeAppend
into the PG11 release. This year it was ModifyTable, which is now
possible thanks to Amit and Tom's modifications to the inheritance
planner.

I've attached what I have so far for this.

Thanks for working on this. IIUC, the feature is to skip modifying a
given result relation if run-time pruning dictates that none of its
existing rows will match some dynamically computable quals.

I think it's mostly okay,
but my brain was overheating a bit at the inheritance_planner changes.

I think we need to consider the fact that there is a proposal [1]/messages/by-id/357.1550612935@sss.pgh.pa.us to
get rid of inheritance_planner() as the way of planning UPDATE/DELETEs
on inheritance trees. If we go that route, then a given partitioned
target table will be expanded at the bottom and so, there's no need
for ModifyTable to have its own run-time pruning info, because
Append/MergeAppend will have it. Maybe, we will need some code in
ExecInitModifyTable() and ExecModifyTable() to handle the case where
run-time pruning, during plan tree initialization and plan tree
execution respectively, may have rendered modifying a given result
relation unnecessary.

A cursory look at the patch suggests that most of its changes will be
for nothing if [1]/messages/by-id/357.1550612935@sss.pgh.pa.us materializes. What do you think about that?

Thanks,
Amit

[1]: /messages/by-id/357.1550612935@sss.pgh.pa.us

On Wed, 3 Jul 2019 at 17:27, Amit Langote <amitlangote09@gmail.com> wrote:

A cursory look at the patch suggests that most of its changes will be
for nothing if [1] materializes. What do you think about that?

Yeah, I had this in mind when writing the patch, but kept going
anyway. I think it's only really a small patch of this patch that
would get wiped out with that change. Just the planner.c stuff.
Everything else is still required, as far as I understand.

[1] /messages/by-id/357.1550612935@sss.pgh.pa.us

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Wed, Jul 3, 2019 at 4:34 PM David Rowley
<david.rowley@2ndquadrant.com> wrote:

On Wed, 3 Jul 2019 at 17:27, Amit Langote <amitlangote09@gmail.com> wrote:

A cursory look at the patch suggests that most of its changes will be
for nothing if [1] materializes. What do you think about that?

Yeah, I had this in mind when writing the patch, but kept going
anyway. I think it's only really a small patch of this patch that
would get wiped out with that change. Just the planner.c stuff.
Everything else is still required, as far as I understand.

If I understand the details of [1] correctly, ModifyTable will no
longer have N subplans for N result relations as there are today. So,
it doesn't make sense for ModifyTable to contain
PartitionedRelPruneInfos and for ExecInitModifyTable/ExecModifyTable
to have to perform initial and execution-time pruning, respectively.
As I said, bottom expansion of target inheritance will mean pruning
(both plan-time and run-time) will occur at the bottom too, so the
run-time pruning capabilities of nodes that already have it will be
used for UPDATE and DELETE too.

Thanks,
Amit

Hi, Amit

If I understand the details of [1] correctly, ModifyTable will no longer
have N subplans for N result relations as there are today. So, it doesn't
make sense for ModifyTable to contain PartitionedRelPruneInfos and for
ExecInitModifyTable/ExecModifyTable
to have to perform initial and execution-time pruning, respectively.

Does this mean that the generic plan will not have N subplans for N result relations?
I thought [1] would make creating generic plans faster, but is this correct?

regards,

kato sho

Kato-san,

On Thu, Jul 4, 2019 at 1:40 PM Kato, Sho <kato-sho@jp.fujitsu.com> wrote:

If I understand the details of [1] correctly, ModifyTable will no longer
have N subplans for N result relations as there are today. So, it doesn't
make sense for ModifyTable to contain PartitionedRelPruneInfos and for
ExecInitModifyTable/ExecModifyTable
to have to perform initial and execution-time pruning, respectively.

Does this mean that the generic plan will not have N subplans for N result relations?
I thought [1] would make creating generic plans faster, but is this correct?

Yeah, making a generic plan for UPDATE of inheritance tables will
certainly become faster, because we will no longer plan the same query
N times for N child tables. There will still be N result relations
but only one sub-plan to fetch the rows from. Also, planning will
still cost O(N), but with a much smaller constant factor.

By the way, let's keep any further discussion on this particular topic
in the other thread.

Thanks,
Amit

On Monday, July 8, 2019 11:34 AM, Amit Langote wrote:

By the way, let's keep any further discussion on this particular topic
in the other thread.

Thanks for the details. I got it.

Regards,
Kato sho

Here's a rebased version of this patch (it had a trivial conflict).
No further changes.

--
�lvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On Thu, Sep 12, 2019 at 10:10 AM Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:

Here's a rebased version of this patch (it had a trivial conflict).

Hi, FYI partition_prune.sql currently fails (maybe something to do
with commit d52eaa09?):

 where s.a = $1 and s.b = $2 and s.c = (select 1);
 explain (costs off) execute q (1, 1);
                           QUERY PLAN
----------------------------------------------------------------
+----------------------------------------------------
  Append
    InitPlan 1 (returns $0)
      ->  Result
-   Subplans Removed: 1
    ->  Seq Scan on p1
-         Filter: ((a = $1) AND (b = $2) AND (c = $0))
+         Filter: ((a = 1) AND (b = 1) AND (c = $0))
    ->  Seq Scan on q111
-         Filter: ((a = $1) AND (b = $2) AND (c = $0))
+         Filter: ((a = 1) AND (b = 1) AND (c = $0))
    ->  Result
-         One-Time Filter: ((1 = $1) AND (1 = $2) AND (1 = $0))
-(10 rows)
+         One-Time Filter: (1 = $0)
+(9 rows)

execute q (1, 1);
a | b | c

On Tue, Nov 05, 2019 at 04:04:25PM +1300, Thomas Munro wrote:

On Thu, Sep 12, 2019 at 10:10 AM Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:

Here's a rebased version of this patch (it had a trivial conflict).

Hi, FYI partition_prune.sql currently fails (maybe something to do
with commit d52eaa09?):

David, perhaps you did not notice that? For now I have moved this
patch to next CF waiting on author to look after the failure.

Amit, Kato-san, both of you are marked as reviewers of this patch.
Are you planning to look at it?
--
Michael

On Wed, Nov 27, 2019 at 05:17:06PM +0900, Michael Paquier wrote:

On Tue, Nov 05, 2019 at 04:04:25PM +1300, Thomas Munro wrote:

On Thu, Sep 12, 2019 at 10:10 AM Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:

Here's a rebased version of this patch (it had a trivial conflict).

Hi, FYI partition_prune.sql currently fails (maybe something to do
with commit d52eaa09?):

David, perhaps you did not notice that? For now I have moved this
patch to next CF waiting on author to look after the failure.

Amit, Kato-san, both of you are marked as reviewers of this patch.
Are you planning to look at it?

David, this patch is marked as "waiting on author" since 11/27, and
there have been no updates or responses since then. Do you plan to
submit a new patch version in this CF? We're already half-way through,
so there's not much time ...

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On Thu, Jan 16, 2020 at 10:45:25PM +0100, Tomas Vondra wrote:

David, this patch is marked as "waiting on author" since 11/27, and
there have been no updates or responses since then. Do you plan to
submit a new patch version in this CF? We're already half-way through,
so there's not much time ...

The reason why I moved it to 2020-01 is that there was not enough time
for David to reply back. At this stage, it seems more appropriate to
me to mark it as returned with feedback and move on.
--
Michael

Sorry, I didn't notice this email until now.

On Wed, Nov 27, 2019 at 5:17 PM Michael Paquier <michael@paquier.xyz> wrote:

On Tue, Nov 05, 2019 at 04:04:25PM +1300, Thomas Munro wrote:

On Thu, Sep 12, 2019 at 10:10 AM Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:

Here's a rebased version of this patch (it had a trivial conflict).

Hi, FYI partition_prune.sql currently fails (maybe something to do
with commit d52eaa09?):

David, perhaps you did not notice that? For now I have moved this
patch to next CF waiting on author to look after the failure.

Amit, Kato-san, both of you are marked as reviewers of this patch.
Are you planning to look at it?

Sorry, I never managed to look at the patch closely. As I commented
up-thread, the functionality added by this patch would be unnecessary
if we were to move forward with the other project related to UPDATE
and DELETE over inheritance trees:

/messages/by-id/357.1550612935@sss.pgh.pa.us

I had volunteered to submit a patch in that thread and even managed to
write one but didn't get time to get it in good enough shape to post
it to the list, like I couldn't make it handle foreign child tables.
The gist of the new approach is that ModifyTable will always have
*one* subplan under ModifyTable, not N for N target partitions as
currently. That one subplan being the same plan as one would get if
the query were SELECT instead of UPDATE/DELETE, it would automatically
take care of run-time pruning if needed, freeing ModifyTable itself
from having to do it.

Now, the chances of such a big overhaul of how UPDATEs of inheritance
trees are handled getting into PG 13 seem pretty thin even if I post
the patch in few days, so perhaps it would make sense to get this
patch in so that we can give users run-time pruning for UPDATE/DELETE
in PG 13, provided the code is not very invasive. If and when the
aforesaid overhaul takes place, that code would go away along with a
lot of other code.

Thanks,
Amit

On Thu, Jan 23, 2020 at 4:31 PM Amit Langote <amitlangote09@gmail.com> wrote:

Now, the chances of such a big overhaul of how UPDATEs of inheritance
trees are handled getting into PG 13 seem pretty thin even if I post
the patch in few days, so perhaps it would make sense to get this
patch in so that we can give users run-time pruning for UPDATE/DELETE
in PG 13, provided the code is not very invasive. If and when the
aforesaid overhaul takes place, that code would go away along with a
lot of other code.

Fwiw, I updated the patch, mainly expected/partition_prune.out. Some
tests in it were failing as a fallout of commits d52eaa09 (pointed out
by Thomas upthread) and 6ef77cf46e8, which are not really related to
the code being changed by the patch.

On the patch itself, it seems straightforward enough. It simply takes
the feature we have for Append and MergeAppend nodes and adopts it for
ModifyTable which for the purposes of run-time pruning looks very much
like the aforementioned nodes.

Part of the optimizer patch that looks a bit complex is the changes to
inheritance_planner() which is to be expected, because that function
is a complex beast itself. I have suggestions to modify some comments
around the code added/modified by the patch for clarity; attaching a
delta patch for that.

The executor patch looks pretty benign too. Diffs that looked a bit
suspicious at first are due to replacing
ModifyTableState.resultRelInfo that is a pointer into
EState.es_result_relations array by an array of ResultRelInfo
pointers, but doing that seems to make the relevant code easier to
follow, especially if you consider the changes that the patch makes to
that code.

I'll set the CF entry to Needs Review, because AFAICS there are no
unaddressed comments.

Thanks,
Amit

Thanks for having a look at this, Amit.

On Fri, 24 Jan 2020 at 21:57, Amit Langote <amitlangote09@gmail.com> wrote:

On Thu, Jan 23, 2020 at 4:31 PM Amit Langote <amitlangote09@gmail.com> wrote:
Part of the optimizer patch that looks a bit complex is the changes to
inheritance_planner() which is to be expected, because that function
is a complex beast itself. I have suggestions to modify some comments
around the code added/modified by the patch for clarity; attaching a
delta patch for that.

I've made another pass over the patch and made various changes. The
biggest of which was the required modifications to nodeModifyTable.c
so that it can now prune all partitions. Append and MergeAppend were
modified to allow this in 5935917ce59 (Thanks for pushing that Tom).
I've also slightly simplified the code in ExecModifyTable() and added
slightly more code to ExecInitModifyTable(). We now only set
mt_whichplan to WHICHPLAN_CHOOSE_SUBPLAN when run-time pruning is
enabled and do_exec_prune is true. I also made it so when all
partitions are pruned that we set mt_whichplan to
WHICHPLAN_CHOOSE_SUBPLAN as this saves an additional run-time check
during execution.

Over in inheritance_planner(), I noticed that the RT index of the
SELECT query and the UPDATE/DELETE query can differ. There was some
code that performed translations. I changed that code slightly so that
it's a bit more optimal. It was building two lists, one for the old
RT index and one for the new. It added elements to this list
regardless of if the RT indexes were the same or not. I've now changed
that to only add to the list if they differ, which I feel should never
be slower and most likely always faster. I'm also now building a
translation map between the old and new RT indexes, however, I only
found one test in the regression tests which require any sort of
translation of these RT indexes. This was with an inheritance table,
so I need to do a bit more work to find a case where this happens with
a partitioned table to ensure all this works.

The executor patch looks pretty benign too. Diffs that looked a bit
suspicious at first are due to replacing
ModifyTableState.resultRelInfo that is a pointer into
EState.es_result_relations array by an array of ResultRelInfo
pointers, but doing that seems to make the relevant code easier to
follow, especially if you consider the changes that the patch makes to
that code.

Yeah, that's because the ModifyTableState's resultRelInfo field was
just a pointer to the estate->es_result_relations array offset by the
ModifyTable's resultRelIndex. This was fine previously because we
always initialised the plans for each ResultRelInfo. However, now
that we might be pruning some of those that array can't be used as
it'll still contain ResultRelInfos for relations we're not going to
touch. Changing this to an array of pointers allows us to point to the
elements in estate->es_result_relations that we're going to use. I
also renamed the field just to ensure nothing can compile (thinking of
extensions here) that's not got updated code.

Tom, I'm wondering if you wouldn't mind looking over my changes to
inheritance_planner()?

David

On Tue, 10 Mar 2020 at 00:13, David Rowley <dgrowleyml@gmail.com> wrote:

Over in inheritance_planner(), I noticed that the RT index of the
SELECT query and the UPDATE/DELETE query can differ. There was some
code that performed translations. I changed that code slightly so that
it's a bit more optimal. It was building two lists, one for the old
RT index and one for the new. It added elements to this list
regardless of if the RT indexes were the same or not. I've now changed
that to only add to the list if they differ, which I feel should never
be slower and most likely always faster. I'm also now building a
translation map between the old and new RT indexes, however, I only
found one test in the regression tests which require any sort of
translation of these RT indexes. This was with an inheritance table,
so I need to do a bit more work to find a case where this happens with
a partitioned table to ensure all this works.

I had a closer look at this today and the code I have in
inheritance_planner() is certainly not right.

It's pretty easy to made the SELECT and UPDATE/DELETE's RT indexes
differ with something like:

drop table part_t cascade;
create table part_t (a int, b int, c int) partition by list (a);
create table part_t12 partition of part_t for values in(1,2) partition
by list (a);
create table part_t12_1 partition of part_t12 for values in(1);
create table part_t12_2 partition of part_t12 for values in(2);
create table part_t3 partition of part_t for values in(3);
create view vw_part_t as select * from part_t;

explain analyze update vw_part_t set a = t2.a +0 from part_t t2 where
t2.a = vw_part_t.a and vw_part_t.a = (select 1);

In this case, the sub-partitioned table changes RT index. I can't
just take the RelOptInfo's from the partition_root's simple_rel_array
and put them in the correct element in the root's simple_rel_array as
they RT indexes stored within also need to be translated.

I'll be having another look at this to see what the best fix is going to be.

David

David Rowley <dgrowleyml@gmail.com> writes:

I had a closer look at this today and the code I have in
inheritance_planner() is certainly not right.

Although I didn't get around to it for v13, there's still a plan on the
table for inheritance_planner() to get nuked from orbit [1]/messages/by-id/357.1550612935@sss.pgh.pa.us.

Maybe this improvement should be put on hold till that's done?

regards, tom lane

[1]: /messages/by-id/357.1550612935@sss.pgh.pa.us

On Wed, 25 Mar 2020 at 13:00, Tom Lane <tgl@sss.pgh.pa.us> wrote:

David Rowley <dgrowleyml@gmail.com> writes:

I had a closer look at this today and the code I have in
inheritance_planner() is certainly not right.

Although I didn't get around to it for v13, there's still a plan on the
table for inheritance_planner() to get nuked from orbit [1].

Maybe this improvement should be put on hold till that's done?

Possibly. I'm not really wedded to the idea of getting it in. However,
it would really only be the inheritance planner part that would need
to be changed later. I don't think any of the other code would need to
be adjusted.

Amit shared his thoughts in [1]/messages/by-id/CA+HiwqGhD7ieKsv5+GkmHgs-XhP2DoUhtESVb3MU-4j14=G6LA@mail.gmail.com. If you'd rather I held off, then I will.

David

[1]: /messages/by-id/CA+HiwqGhD7ieKsv5+GkmHgs-XhP2DoUhtESVb3MU-4j14=G6LA@mail.gmail.com

Hi David,

Sorry I couldn't get to this sooner.

On Wed, Mar 25, 2020 at 9:49 AM David Rowley <dgrowleyml@gmail.com> wrote:

On Wed, 25 Mar 2020 at 13:00, Tom Lane <tgl@sss.pgh.pa.us> wrote:

David Rowley <dgrowleyml@gmail.com> writes:

I had a closer look at this today and the code I have in
inheritance_planner() is certainly not right.

Although I didn't get around to it for v13, there's still a plan on the
table for inheritance_planner() to get nuked from orbit [1].

Maybe this improvement should be put on hold till that's done?

Possibly. I'm not really wedded to the idea of getting it in. However,
it would really only be the inheritance planner part that would need
to be changed later. I don't think any of the other code would need to
be adjusted.

Amit shared his thoughts in [1]. If you'd rather I held off, then I will.

David

[1] /messages/by-id/CA+HiwqGhD7ieKsv5+GkmHgs-XhP2DoUhtESVb3MU-4j14=G6LA@mail.gmail.com

Actually, I was saying in that email that the update/delete planning
overhaul being talked about will make the entirety of the
functionality this patch is adding, which is ModifyTable node being
able to prune its subplans based on run-time parameter values,
redundant. That's because, with the overhaul, there won't be multiple
subplans under ModifyTable, only one which would take care of any
pruning that's necessary.

What I did say in favor of this patch though is that it doesn not seem
that invasive, so maybe okay to get in for v13.

--
Thank you,

Amit Langote
EnterpriseDB: http://www.enterprisedb.com

On Wed, 25 Mar 2020 at 15:37, Amit Langote <amitlangote09@gmail.com> wrote:

Actually, I was saying in that email that the update/delete planning
overhaul being talked about will make the entirety of the
functionality this patch is adding, which is ModifyTable node being
able to prune its subplans based on run-time parameter values,
redundant. That's because, with the overhaul, there won't be multiple
subplans under ModifyTable, only one which would take care of any
pruning that's necessary.

Thanks for explaining. I've not read over any patch for that yet, so
wasn't aware of exactly what was planned.

With your explanation, I imagine some sort of Append / MergeAppend
that runs the query as if it were a SELECT, but each
Append/MergeAppend subnode is tagged somehow with an index of which
ModifyTable subnode that it belongs to. Basically, just one complete
plan, rather than a plan per ModifyTable subnode.

What I did say in favor of this patch though is that it doesn not seem
that invasive, so maybe okay to get in for v13.

Since it seems there's much less code that will be useful after the
rewrite than I thought, combined with the fact that I'm not entirely
sure the best way to reuse the partitioned table's RelOptInfo from the
SELECT's PlannerInfo, then I'm going to return this one with feedback.

David