On Sun, Apr 18, 2021, at 22:14, Tom Lane wrote: > "Joel Jacobson" <j...@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
