Re: Planning time grows exponentially with levels of nested views

On Sun, Apr 18, 2021, at 22:14, Tom Lane wrote:
> "Joel Jacobson" <joel@compiler.org <mailto:joel%40compiler.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).

Many thanks for explaining and the patch.

I've tested the patch successfully.
Planning time grows much slower now:

EXPLAIN ANALYZE SELECT * FROM v64;
- Planning Time: 14.981 ms
+ Planning Time: 2.802 ms

EXPLAIN ANALYZE SELECT * FROM v128;
- Planning Time: 109.407 ms
+ Planning Time: 11.595 ms

EXPLAIN ANALYZE SELECT * FROM v256;
- Planning Time: 1594.809 ms
+ Planning Time: 46.709 ms

Very nice.

/Joel