Thread: exponential time growth of handling subqueries

exponential time growth of handling subqueries

From
Greg Stark
Date:
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;
QUERYPLAN                       
 
-------------------------------------------------------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)
asx) 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)
asx;                     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)
asx) 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)
asx) as x;                     QUERY PLAN                       
 
-------------------------------------------------------Seq Scan on foo  (cost=0.00..18.84 rows=184 width=788)
(1 row)

Time: 2776.14 ms


-- 
greg



Re: exponential time growth of handling subqueries

From
Tom Lane
Date:
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