pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
optimizer picks smaller table to drive nested loops?
6+ messages / 3 participants
[nested] [flat]

* optimizer picks smaller table to drive nested loops?
@ 2003-07-07 18:22 Greg Stark <gsstark@mit.edu>
  2003-07-07 20:58 ` Re: optimizer picks smaller table to drive nested loops? Randy Neumann <Randy_Neumann@centralref.com>
  2003-07-14 18:04 ` Re: optimizer picks smaller table to drive nested loops? Tom Lane <tgl@sss.pgh.pa.us>
  0 siblings, 2 replies; 6+ messages in thread

From: Greg Stark @ 2003-07-07 18:22 UTC (permalink / raw)
  To: pgsql-performance


Someone asked a hypothetical question about how to retrieve all records of a
table twice in SQL. It got me thinking about whether there was a way to do
this efficiently.

"Obviously" if you do it using the UNION ALL approach postgres isn't going to
do two separate scans, doing it otherwise would be quite hard.

However using the join approach it seems postgres ought to be able to do a
single sequential scan and return every tuple it finds twice. It doesn't do
this:

slo=> explain analyze select * from region, (select 1 union all select 2) as x;
                                                       QUERY PLAN                                                       
------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..11162.00 rows=5534 width=108) (actual time=0.13..541.19 rows=5534 loops=1)
   ->  Subquery Scan x  (cost=0.00..2.00 rows=2 width=0) (actual time=0.03..0.08 rows=2 loops=1)
         ->  Append  (cost=0.00..2.00 rows=2 width=0) (actual time=0.02..0.05 rows=2 loops=1)
               ->  Subquery Scan "*SELECT* 1"  (cost=0.00..1.00 rows=1 width=0) (actual time=0.01..0.02 rows=1 loops=1)
                     ->  Result  (cost=0.00..1.00 rows=1 width=0) (actual time=0.01..0.01 rows=1 loops=1)
               ->  Subquery Scan "*SELECT* 2"  (cost=0.00..1.00 rows=1 width=0) (actual time=0.01..0.02 rows=1 loops=1)
                     ->  Result  (cost=0.00..1.00 rows=1 width=0) (actual time=0.01..0.01 rows=1 loops=1)
   ->  Seq Scan on region  (cost=0.00..2813.00 rows=2767 width=104) (actual time=0.03..123.44 rows=2767 loops=2)
 Total runtime: 566.24 msec
(9 rows)

Wouldn't it be faster to drive the nested loop the other way around?

(I'm also a bit puzzled why the optimizer is calculating that 2,813 * 2 = 5,534)

This is tested on 7.3. I haven't tried CVS yet.

-- 
greg




^ permalink  raw  reply  [nested|flat] 6+ messages in thread

* Re: optimizer picks smaller table to drive nested loops?
  2003-07-07 18:22 optimizer picks smaller table to drive nested loops? Greg Stark <gsstark@mit.edu>
@ 2003-07-07 20:58 ` Randy Neumann <Randy_Neumann@centralref.com>
  1 sibling, 0 replies; 6+ messages in thread

From: Randy Neumann @ 2003-07-07 20:58 UTC (permalink / raw)
  To: Greg Stark <gsstark@mit.edu>; +Cc: pgsql-performance

On Monday 07 July 2003 12:22 pm, you wrote:

> loops=1) ->  Seq Scan on region  (cost=0.00..2813.00 rows=2767 width=104)
> (actual time=0.03..123.44 rows=2767 loops=2) Total runtime: 566.24 msec
> (9 rows)
>
> (I'm also a bit puzzled why the optimizer is calculating that 2,813 * 2 =
> 5,534)

You should read it 2767 (rows) * 2 = 5534 (rows)
2813.00 is part of the cost.



^ permalink  raw  reply  [nested|flat] 6+ messages in thread

* Re: optimizer picks smaller table to drive nested loops?
  2003-07-07 18:22 optimizer picks smaller table to drive nested loops? Greg Stark <gsstark@mit.edu>
@ 2003-07-14 18:04 ` Tom Lane <tgl@sss.pgh.pa.us>
  2003-07-14 18:40   ` Re: optimizer picks smaller table to drive nested loops? Greg Stark <gsstark@mit.edu>
  1 sibling, 1 reply; 6+ messages in thread

From: Tom Lane @ 2003-07-14 18:04 UTC (permalink / raw)
  To: Greg Stark <gsstark@mit.edu>; +Cc: pgsql-performance

Greg Stark <gsstark@mit.edu> writes:
> slo=> explain analyze select * from region, (select 1 union all select 2) as x;
>                                                        QUERY PLAN                                                       
> ------------------------------------------------------------------------------------------------------------------------
>  Nested Loop  (cost=0.00..11162.00 rows=5534 width=108) (actual time=0.13..541.19 rows=5534 loops=1)
>    ->  Subquery Scan x  (cost=0.00..2.00 rows=2 width=0) (actual time=0.03..0.08 rows=2 loops=1)
>          ->  Append  (cost=0.00..2.00 rows=2 width=0) (actual time=0.02..0.05 rows=2 loops=1)
>                ->  Subquery Scan "*SELECT* 1"  (cost=0.00..1.00 rows=1 width=0) (actual time=0.01..0.02 rows=1 loops=1)
>                      ->  Result  (cost=0.00..1.00 rows=1 width=0) (actual time=0.01..0.01 rows=1 loops=1)
>                ->  Subquery Scan "*SELECT* 2"  (cost=0.00..1.00 rows=1 width=0) (actual time=0.01..0.02 rows=1 loops=1)
>                      ->  Result  (cost=0.00..1.00 rows=1 width=0) (actual time=0.01..0.01 rows=1 loops=1)
>    ->  Seq Scan on region  (cost=0.00..2813.00 rows=2767 width=104) (actual time=0.03..123.44 rows=2767 loops=2)
>  Total runtime: 566.24 msec
> (9 rows)

> Wouldn't it be faster to drive the nested loop the other way around?

You seem to be using a rather wacko value of cpu_tuple_cost; those
Result nodes ought to be costed at 0.01 not 1.00.  With the default
cost settings I get an other-way-around plan for a similar test.
(I used tenk1 from the regression database as the outer table.)

However, it looks to me like the subquery-scan-outside plan probably
is the faster one, on both my machine and yours.  I get

regression=# explain analyze select * from tenk1, (select 1 union all select 2) as x;
                                                         QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..858.00 rows=20000 width=248) (actual time=0.42..3648.61 rows=20000 loops=1)
   ->  Seq Scan on tenk1  (cost=0.00..458.00 rows=10000 width=244) (actual time=0.23..199.97 rows=10000 loops=1)
   ->  Subquery Scan x  (cost=0.00..0.02 rows=2 width=0) (actual time=0.07..0.24 rows=2 loops=10000)
         ->  Append  (cost=0.00..0.02 rows=2 width=0) (actual time=0.05..0.17 rows=2 loops=10000)
               ->  Subquery Scan "*SELECT* 1"  (cost=0.00..0.01 rows=1 width=0) (actual time=0.03..0.06 rows=1 loops=10000)
                     ->  Result  (cost=0.00..0.01 rows=1 width=0) (actual time=0.01..0.02 rows=1 loops=10000)
               ->  Subquery Scan "*SELECT* 2"  (cost=0.00..0.01 rows=1 width=0) (actual time=0.03..0.06 rows=1 loops=10000)
                     ->  Result  (cost=0.00..0.01 rows=1 width=0) (actual time=0.01..0.02 rows=1 loops=10000)
 Total runtime: 3807.39 msec
(9 rows)

regression=# set cpu_tuple_cost = 1;
SET
regression=# explain analyze select * from tenk1, (select 1 union all select 2) as x;
                                                       QUERY PLAN
------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..40718.00 rows=20000 width=248) (actual time=0.39..1214.42 rows=20000 loops=1)
   ->  Subquery Scan x  (cost=0.00..2.00 rows=2 width=0) (actual time=0.10..0.31 rows=2 loops=1)
         ->  Append  (cost=0.00..2.00 rows=2 width=0) (actual time=0.06..0.22 rows=2 loops=1)
               ->  Subquery Scan "*SELECT* 1"  (cost=0.00..1.00 rows=1 width=0) (actual time=0.05..0.08 rows=1 loops=1)
                     ->  Result  (cost=0.00..1.00 rows=1 width=0) (actual time=0.03..0.04 rows=1 loops=1)
               ->  Subquery Scan "*SELECT* 2"  (cost=0.00..1.00 rows=1 width=0) (actual time=0.05..0.08 rows=1 loops=1)
                     ->  Result  (cost=0.00..1.00 rows=1 width=0) (actual time=0.02..0.03 rows=1 loops=1)
   ->  Seq Scan on tenk1  (cost=0.00..10358.00 rows=10000 width=244) (actual time=0.17..188.37 rows=10000 loops=2)
 Total runtime: 1371.17 msec
(9 rows)

The flipover point between the two plans is cpu_tuple_cost = 0.04 in
my tests.

It looks to me like we've neglected to charge any cost associated with
Subquery Scan or Append nodes.  Certainly Subquery Scan ought to charge
at least a cpu_tuple_cost per row.  Perhaps Append ought to as well ---
although since it doesn't do selection or projection, I'm not quite sure
where the time is going in that case.  (Hmmm... time to get out the
profiler...)

			regards, tom lane



^ permalink  raw  reply  [nested|flat] 6+ messages in thread

* Re: optimizer picks smaller table to drive nested loops?
  2003-07-07 18:22 optimizer picks smaller table to drive nested loops? Greg Stark <gsstark@mit.edu>
  2003-07-14 18:04 ` Re: optimizer picks smaller table to drive nested loops? Tom Lane <tgl@sss.pgh.pa.us>
@ 2003-07-14 18:40   ` Greg Stark <gsstark@mit.edu>
  2003-07-14 20:58     ` Re: optimizer picks smaller table to drive nested loops? Tom Lane <tgl@sss.pgh.pa.us>
  0 siblings, 1 reply; 6+ messages in thread

From: Greg Stark @ 2003-07-14 18:40 UTC (permalink / raw)
  To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Greg Stark <gsstark@mit.edu>; pgsql-performance


Tom Lane <tgl@sss.pgh.pa.us> writes:

> You seem to be using a rather wacko value of cpu_tuple_cost; those
> Result nodes ought to be costed at 0.01 not 1.00.  With the default

oops yes, thanks. that was left over from other experimentation.

> However, it looks to me like the subquery-scan-outside plan probably
> is the faster one, on both my machine and yours.  I get
> 
> regression=# explain analyze select * from tenk1, (select 1 union all select 2) as x;
>                                                          QUERY PLAN
> ----------------------------------------------------------------------------------------------------------------------------
>  Nested Loop  (cost=0.00..858.00 rows=20000 width=248) (actual time=0.42..3648.61 rows=20000 loops=1)
>    ->  Seq Scan on tenk1  (cost=0.00..458.00 rows=10000 width=244) (actual time=0.23..199.97 rows=10000 loops=1)
>    ->  Subquery Scan x  (cost=0.00..0.02 rows=2 width=0) (actual time=0.07..0.24 rows=2 loops=10000)
...
>  Total runtime: 3807.39 msec

>  Nested Loop  (cost=0.00..40718.00 rows=20000 width=248) (actual time=0.39..1214.42 rows=20000 loops=1)
>    ->  Subquery Scan x  (cost=0.00..2.00 rows=2 width=0) (actual time=0.10..0.31 rows=2 loops=1)
>    ->  Seq Scan on tenk1  (cost=0.00..10358.00 rows=10000 width=244) (actual time=0.17..188.37 rows=10000 loops=2)
>  Total runtime: 1371.17 msec

Woah, that's pretty whacky. It seems like it ought to be way faster to do a
single sequential scan and return two records for each tuple read rather than
do an entire unnecessary sequential scan, even if most or even all of the
second one is cached.

-- 
greg




^ permalink  raw  reply  [nested|flat] 6+ messages in thread

* Re: optimizer picks smaller table to drive nested loops?
  2003-07-07 18:22 optimizer picks smaller table to drive nested loops? Greg Stark <gsstark@mit.edu>
  2003-07-14 18:04 ` Re: optimizer picks smaller table to drive nested loops? Tom Lane <tgl@sss.pgh.pa.us>
  2003-07-14 18:40   ` Re: optimizer picks smaller table to drive nested loops? Greg Stark <gsstark@mit.edu>
@ 2003-07-14 20:58     ` Tom Lane <tgl@sss.pgh.pa.us>
  2003-07-14 22:41       ` Re: optimizer picks smaller table to drive nested loops? Tom Lane <tgl@sss.pgh.pa.us>
  0 siblings, 1 reply; 6+ messages in thread

From: Tom Lane @ 2003-07-14 20:58 UTC (permalink / raw)
  To: Greg Stark <gsstark@mit.edu>; +Cc: pgsql-performance

Greg Stark <gsstark@mit.edu> writes:
> Tom Lane <tgl@sss.pgh.pa.us> writes:
>> However, it looks to me like the subquery-scan-outside plan probably
>> is the faster one, on both my machine and yours.  I get

> Woah, that's pretty whacky. It seems like it ought to be way faster to do a
> single sequential scan and return two records for each tuple read rather than
> do an entire unnecessary sequential scan, even if most or even all of the
> second one is cached.

The problem is the CPU expense of executing "SELECT 1 UNION SELECT 2"
over and over.  Doing that for every row of the outer table adds up.

We were both testing on relatively small tables --- I suspect the
results would be different if the outer table were too large to fit
in disk cache.

I am not sure why the planner did not choose to stick a Materialize
node atop the Subquery Scan, though.  It looks to me like it should
have considered that option --- possibly the undercharging for Subquery
Scan is the reason it wasn't chosen.

			regards, tom lane



^ permalink  raw  reply  [nested|flat] 6+ messages in thread

* Re: optimizer picks smaller table to drive nested loops?
  2003-07-07 18:22 optimizer picks smaller table to drive nested loops? Greg Stark <gsstark@mit.edu>
  2003-07-14 18:04 ` Re: optimizer picks smaller table to drive nested loops? Tom Lane <tgl@sss.pgh.pa.us>
  2003-07-14 18:40   ` Re: optimizer picks smaller table to drive nested loops? Greg Stark <gsstark@mit.edu>
  2003-07-14 20:58     ` Re: optimizer picks smaller table to drive nested loops? Tom Lane <tgl@sss.pgh.pa.us>
@ 2003-07-14 22:41       ` Tom Lane <tgl@sss.pgh.pa.us>
  0 siblings, 0 replies; 6+ messages in thread

From: Tom Lane @ 2003-07-14 22:41 UTC (permalink / raw)
  To: Greg Stark <gsstark@mit.edu>; +Cc: pgsql-performance

I said:
> I am not sure why the planner did not choose to stick a Materialize
> node atop the Subquery Scan, though.  It looks to me like it should
> have considered that option --- possibly the undercharging for Subquery
> Scan is the reason it wasn't chosen.

Indeed, after fixing the unrealistic estimate for SubqueryScan, I get
this:

regression=# explain analyze select * from tenk1, (select 1 union all select 2) as x;
                                                          QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.06..858.06 rows=20000 width=248) (actual time=0.25..1448.19 rows=20000 loops=1)
   ->  Seq Scan on tenk1  (cost=0.00..458.00 rows=10000 width=244) (actual time=0.06..162.48 rows=10000 loops=1)
   ->  Materialize  (cost=0.06..0.08 rows=2 width=4) (actual time=0.01..0.03 rows=2 loops=10000)
         ->  Subquery Scan x  (cost=0.00..0.06 rows=2 width=4) (actual time=0.10..0.27 rows=2 loops=1)
               ->  Append  (cost=0.00..0.04 rows=2 width=0) (actual time=0.07..0.20 rows=2 loops=1)
                     ->  Subquery Scan "*SELECT* 1"  (cost=0.00..0.02 rows=1 width=0) (actual time=0.05..0.08 rows=1 loops=1)
                           ->  Result  (cost=0.00..0.01 rows=1 width=0) (actual time=0.03..0.03 rows=1 loops=1)
                     ->  Subquery Scan "*SELECT* 2"  (cost=0.00..0.02 rows=1 width=0) (actual time=0.03..0.06 rows=1 loops=1)
                           ->  Result  (cost=0.00..0.01 rows=1 width=0) (actual time=0.01..0.02 rows=1 loops=1)
 Total runtime: 1627.26 msec
(10 rows)

which is probably the best way to do it, all things considered.

			regards, tom lane



^ permalink  raw  reply  [nested|flat] 6+ messages in thread


end of thread, other threads:[~2003-07-14 22:41 UTC | newest]

Thread overview: 6+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2003-07-07 18:22 optimizer picks smaller table to drive nested loops? Greg Stark <gsstark@mit.edu>
2003-07-07 20:58 ` Randy Neumann <Randy_Neumann@centralref.com>
2003-07-14 18:04 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-07-14 18:40   ` Greg Stark <gsstark@mit.edu>
2003-07-14 20:58     ` Tom Lane <tgl@sss.pgh.pa.us>
2003-07-14 22:41       ` Tom Lane <tgl@sss.pgh.pa.us>

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox