Thread: Re: Planning time grows exponentially with levels of nested views

[ redirecting to -hackers so the cfbot can see it ]

"Joel Jacobson" <joel@compiler.org> writes:
> I assumed the cost for each nested VIEW layer would grow linear,
> but my testing shows it appears to grow exponentially:

I think it's impossible to avoid less-than-O(N^2) growth on this sort
of case.  For example, the v2 subquery initially has RTEs for v2 itself
plus v1.  When we flatten v1 into v2, v2 acquires the RTEs from v1,
namely v1 itself plus foo.  Similarly, once vK-1 is pulled up into vK,
there are going to be order-of-K entries in vK's rtable, and that stacking
makes for O(N^2) work overall just in manipulating the rtable.

We can't get rid of these rtable entries altogether, since all of them
represent table privilege checks that the executor will need to do.
It occurs to me though that we don't need the rte->subquery trees anymore
once those are flattened, so maybe we could do something like the
attached.  For me, this reduces the slowdown in your example from
O(N^3) to O(N^2).

I'm slightly worried though by this comment earlier in
pull_up_simple_subquery:

    /*
     * Need a modifiable copy of the subquery to hack on.  Even if we didn't
     * sometimes choose not to pull up below, we must do this to avoid
     * problems if the same subquery is referenced from multiple jointree
     * items (which can't happen normally, but might after rule rewriting).
     */

If multiple references are actually possible then this'd break it.  There
seem to be no such cases in the regression tests though, and I'm having a
hard time wrapping my brain around what would cause it.  "git blame"
traces this text to my own commit f44639e1b, which has the log entry

    Don't crash if subquery appears multiple times in jointree.  This should
    not happen anyway, but let's try not to get completely confused if it does
    (due to rewriter bugs or whatever).

so I'm thinking that this was only hypothetical.

It's possible that we could do something similar in the sibling functions
pull_up_simple_union_all etc, but I'm not sure it's worth troubling over.
TBH, for the size of effect you're showing here, I wouldn't be worried
at all; it's only because it seems to be a one-liner to improve it that
I'm interested in doing something.

            regards, tom lane

diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 62a1668796..f93c037778 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -1174,6 +1174,14 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
     Assert(root->placeholder_list == NIL);
     Assert(subroot->placeholder_list == NIL);

+    /*
+     * We no longer need the RTE's copy of the subquery's query tree.  Getting
+     * rid of it saves nothing in particular so far as this level of query is
+     * concerned; but if this query level is in turn pulled up into a parent,
+     * we'd waste cycles copying the now-unused query tree.
+     */
+    rte->subquery = NULL;
+
     /*
      * Miscellaneous housekeeping.
      *

I wrote:
> If multiple references are actually possible then this'd break it.  There
> seem to be no such cases in the regression tests though, and I'm having a
> hard time wrapping my brain around what would cause it.  "git blame"
> traces this text to my own commit f44639e1b, which has the log entry
>     Don't crash if subquery appears multiple times in jointree.  This should
>     not happen anyway, but let's try not to get completely confused if it does
>     (due to rewriter bugs or whatever).
> so I'm thinking that this was only hypothetical.

Ah, found it.  That was evidently a reaction to the immediately preceding
commit (352871ac9), which fixed a rewriter bug that could lead to exactly
the case of multiple jointree references to one RTE.

I think this patch doesn't make things any worse for such a case though.
If we re-introduced such a bug, the result would be an immediate null
pointer crash while trying to process the second reference to a
flattenable subquery.  That's probably better for debuggability than
what happens now, where we just silently process the duplicate reference.

Anyway, I've stuck this into the next CF for future consideration.

            regards, tom lane

PS: to save time for anyone else who wants to investigate this,
it looks like the report mentioned in 352871ac9 was

https://www.postgresql.org/message-id/007401c0860d%24bed809a0%241001a8c0%40archonet.com

"Joel Jacobson" <joel@compiler.org> writes:

> I assumed the cost for each nested VIEW layer would grow linear,

> but my testing shows it appears to grow exponentially:

I think it's impossible to avoid less-than-O(N^2) growth on this sort

of case.  For example, the v2 subquery initially has RTEs for v2 itself

plus v1.  When we flatten v1 into v2, v2 acquires the RTEs from v1,

namely v1 itself plus foo.  Similarly, once vK-1 is pulled up into vK,

there are going to be order-of-K entries in vK's rtable, and that stacking

makes for O(N^2) work overall just in manipulating the rtable.

We can't get rid of these rtable entries altogether, since all of them

represent table privilege checks that the executor will need to do.

It occurs to me though that we don't need the rte->subquery trees anymore

once those are flattened, so maybe we could do something like the

attached.  For me, this reduces the slowdown in your example from

O(N^3) to O(N^2).

On Sun, 18 Apr 2021 at 21:42, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> > If multiple references are actually possible then this'd break it.
>
> I think this patch doesn't make things any worse for such a case though.
> If we re-introduced such a bug, the result would be an immediate null
> pointer crash while trying to process the second reference to a
> flattenable subquery.  That's probably better for debuggability than
> what happens now, where we just silently process the duplicate reference.
>

I took a look at this and wasn't able to find any way to break it, and
your argument that it can't really make such rewriter bugs any worse
makes sense.

Would it make sense to update the comment prior to copying the subquery?

Out of curiosity, I also tested DML against these deeply nested views
to see how the pull-up code in the rewriter compares in terms of
performance, since it does a very similar job. As expected, it's
O(N^2) as well, but it's about an order of magnitude faster:

(times to run a plain EXPLAIN in ms, with patch)

     | SELECT | INSERT | UPDATE | DELETE
-----+--------+--------+--------+--------
v64  |  1.259 |  0.189 |  0.250 |  0.187
v128 |  5.035 |  0.506 |  0.547 |  0.509
v256 | 20.393 |  1.633 |  1.607 |  1.638
v512 | 81.101 |  6.649 |  6.517 |  6.699

Maybe that's not surprising, since there's less to do at that stage.
Anyway, it's reassuring to know that it copes OK with this (I've seen
some quite deeply nested views in practice, but never that deep).

For comparison, this is what SELECT performance looked like for me
without the patch:

     | SELECT
-----+----------
v64  |    9.589
v128 |   73.292
v256 |  826.964
v512 | 7844.419

so, for a one-line change, that's pretty impressive.

Regards,
Dean

Dean Rasheed <dean.a.rasheed@gmail.com> writes:
> I took a look at this and wasn't able to find any way to break it, and
> your argument that it can't really make such rewriter bugs any worse
> makes sense.

Thanks for looking!

> Would it make sense to update the comment prior to copying the subquery?

Yeah, I hadn't touched that yet because the question was exactly about
whether it's correct or not.  I think we can shorten it to

     * Need a modifiable copy of the subquery to hack on, so that the
     * RTE can be left unchanged in case we decide below that we can't
     * pull it up after all.

> Out of curiosity, I also tested DML against these deeply nested views
> to see how the pull-up code in the rewriter compares in terms of
> performance, since it does a very similar job. As expected, it's
> O(N^2) as well, but it's about an order of magnitude faster:

Oh good.  I hadn't thought to look at that angle of things.

> ... for a one-line change, that's pretty impressive.

Yeah.  The problem might get less bad if we get anywhere with the
idea I suggested at [1].  If we can reduce the number of RTEs
in a view's query, then copying it would get cheaper.  Still,
not copying it at all is always going to be better.  I'll go
ahead and push the patch.

            regards, tom lane

[1] https://www.postgresql.org/message-id/697679.1625154303%40sss.pgh.pa.us