
This is sort of interesting. It seems the time required for the optimizer to
handle a query doubles with every layer of subquery it has to dig through.

There's a reason I stopped at 2.7s though. When I tried to go one step further
expecting it to take 5s my machine simply froze. It still pinged, but nothing,
not even X niced to -10 responded at all. And it lasted a lot longer than 5s.
After 10 minutes I gave up and rebooted.

I'm a bit at a loss how postgres could even do this with a single process if
it wanted to.

This is with 7.3.3. I'm retrying with 7.4 now.


slo=> explain select * from foo;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 0.93 ms
slo=> explain select * from (select * from foo) as x;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 0.70 ms
slo=> explain select * from (select * from (select * from foo) as x) as x;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 1.08 ms
slo=> explain select * from (select * from (select * from (select * from foo) as x) as x) as x;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 1.16 ms
slo=> explain select * from (select * from (select * from (select * from (select * from foo) as x) as x) as x) as x;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 1.78 ms
slo=> explain select * from (select * from (select * from (select * from (select * from (select * from foo) as x) as x) as x) as x) as x;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 2.09 ms
slo=> explain select * from (select * from (select * from (select * from (select * from (select * from (select * from foo) as x) as x) as x) as x) as x) as x;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 3.48 ms
slo=> explain select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from foo) as x) as x) as x) as x) as x) as x) as x;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 6.01 ms
slo=> explain select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from foo) as x) as x) as x) as x) as x) as x) as x) as x;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 11.22 ms
slo=> explain select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from foo) as x) as x) as x) as x) as x) as x) as x) as x) as x;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 23.32 ms
slo=> explain select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from foo) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 61.56 ms
slo=> explain select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from foo) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 86.47 ms
slo=> explain select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from foo) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 176.93 ms
slo=> explain select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from foo) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 344.69 ms
slo=> explain select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from foo) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 696.42 ms
slo=> explain select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from foo) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 1392.15 ms
slo=> explain select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from (select * from foo) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x) as x;
                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 2776.14 ms


-- 
greg


13 Oct 2003 13:18:24 -0400
Greg Stark <gsstark@mit.edu>
exponential time growth of handling subqueries
Greg Stark <gsstark@mit.edu> writes:
> This is sort of interesting. It seems the time required for the optimizer to
> handle a query doubles with every layer of subquery it has to dig through.

Seems to be due to some brain fade in pull_up_subqueries --- the thing
was constructing truly monstrous rangetables due to poorly thought out
recursive modification of the parse tree :-(.  Patch applied in CVS tip.

			regards, tom lane

Mon, 13 Oct 2003 19:50:58 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: exponential time growth of handling subqueries 