pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
dum query plan
4+ messages / 4 participants
[nested] [flat]

* dum query plan
@ 2003-04-16 06:58 Jonathan Moore <moore@discern.com>
  2003-04-17 01:21 ` Re: dum query plan Stephan Szabo <sszabo@megazone23.bigpanda.com>
  2003-04-17 03:15 ` Re: dum query plan Tom Lane <tgl@sss.pgh.pa.us>
  2003-04-17 14:12 ` Re: dum query plan Jean-Luc Lachance <jllachan@nsd.ca>
  0 siblings, 3 replies; 4+ messages in thread

From: Jonathan Moore @ 2003-04-16 06:58 UTC (permalink / raw)
  To: pgsql-performance

I am wondering why it uses the O(n^2) nested loop when there is a O(N)
methoud using btree indexes for a merg join. I am using  7.2.1 would
upgrading fix my problime or is it somthing else?

Given the schema:

drop   table Entry_Pairs;
create table Entry_Pairs (
    left_entry  int              REFERENCES Entry   ON DELETE RESTRICT,
    right_entry int              REFERENCES Entry   ON DELETE RESTRICT,
    relation    int     NOT NULL                                      ,
    subtract    bool    NOT NULL                                      ,
    comment     int         NULL REFERENCES Comment ON DELETE SET NULL,
    UNIQUE (left_entry, right_entry, relation)
);
CREATE INDEX entry_pairs_left_index ON entry_pairs (left_entry);
CREATE INDEX entry_pairs_right_index ON entry_pairs (right_entry);
--

You get this"

dblex=> explain select A.left_entry from entry_pairs A, entry_pairs B
where A.right_entry != B.left_entry;
NOTICE:  QUERY PLAN:

Nested Loop  (cost=100000000.00..102876671.17 rows=97545252 width=12)
  ->  Seq Scan on entry_pairs a  (cost=0.00..167.77 rows=9877 width=8)
  ->  Seq Scan on entry_pairs b  (cost=0.00..167.77 rows=9877 width=4)

EXPLAIN

That is dum. If you just walk both B-Tree indexes there is a O(n)
search. I tryed to turn off netsed loops but it still did it. (the
reason the cost is 100000000.00 is a artifact from turing off loops)

-Jonathan




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

* Re: dum query plan
  2003-04-16 06:58 dum query plan Jonathan Moore <moore@discern.com>
@ 2003-04-17 01:21 ` Stephan Szabo <sszabo@megazone23.bigpanda.com>
  2 siblings, 0 replies; 4+ messages in thread

From: Stephan Szabo @ 2003-04-17 01:21 UTC (permalink / raw)
  To: Jonathan Moore <moore@discern.com>; +Cc: pgsql-performance


On 15 Apr 2003, Jonathan Moore wrote:

> I am wondering why it uses the O(n^2) nested loop when there is a O(N)
> methoud using btree indexes for a merg join. I am using  7.2.1 would
> upgrading fix my problime or is it somthing else?
>
> Given the schema:
>
> drop   table Entry_Pairs;
> create table Entry_Pairs (
>     left_entry  int              REFERENCES Entry   ON DELETE RESTRICT,
>     right_entry int              REFERENCES Entry   ON DELETE RESTRICT,
>     relation    int     NOT NULL                                      ,
>     subtract    bool    NOT NULL                                      ,
>     comment     int         NULL REFERENCES Comment ON DELETE SET NULL,
>     UNIQUE (left_entry, right_entry, relation)
> );
> CREATE INDEX entry_pairs_left_index ON entry_pairs (left_entry);
> CREATE INDEX entry_pairs_right_index ON entry_pairs (right_entry);
> --
>
> You get this"
>
> dblex=> explain select A.left_entry from entry_pairs A, entry_pairs B
> where A.right_entry != B.left_entry;
> NOTICE:  QUERY PLAN:
>
> Nested Loop  (cost=100000000.00..102876671.17 rows=97545252 width=12)
>   ->  Seq Scan on entry_pairs a  (cost=0.00..167.77 rows=9877 width=8)
>   ->  Seq Scan on entry_pairs b  (cost=0.00..167.77 rows=9877 width=4)
>
> EXPLAIN
>
> That is dum. If you just walk both B-Tree indexes there is a O(n)
> search. I tryed to turn off netsed loops but it still did it. (the
> reason the cost is 100000000.00 is a artifact from turing off loops)

Can you describe the algorithm you think it should be taking with perhaps
a small set of data like say (given only left and right):

(1,2)
(3,4)
(5,6)

(I think the query should return 1,1,1,3,3,3,5,5,5 for this case)




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

* Re: dum query plan
  2003-04-16 06:58 dum query plan Jonathan Moore <moore@discern.com>
@ 2003-04-17 03:15 ` Tom Lane <tgl@sss.pgh.pa.us>
  2 siblings, 0 replies; 4+ messages in thread

From: Tom Lane @ 2003-04-17 03:15 UTC (permalink / raw)
  To: Jonathan Moore <moore@discern.com>; +Cc: pgsql-performance

Jonathan Moore <moore@discern.com> writes:
> I am wondering why it uses the O(n^2) nested loop when there is a O(N)
> methoud using btree indexes for a merg join.

With an inequality for the WHERE condition?  I don't think so.  The
expected output is of size O(N^2), so how could the algorithm take
less than O(N^2) steps?

> dblex=> explain select A.left_entry from entry_pairs A, entry_pairs B
> where A.right_entry != B.left_entry;

			regards, tom lane




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

* Re: dum query plan
  2003-04-16 06:58 dum query plan Jonathan Moore <moore@discern.com>
@ 2003-04-17 14:12 ` Jean-Luc Lachance <jllachan@nsd.ca>
  2 siblings, 0 replies; 4+ messages in thread

From: Jean-Luc Lachance @ 2003-04-17 14:12 UTC (permalink / raw)
  To: Jonathan Moore <moore@discern.com>; +Cc: pgsql-performance

Your WHERE clause is the reason you get O(N^2).

How about describing in words what you want.

maybe what you really want is:

select left_entry from entry_pairs A where not exists ( 
  select 1 from entry_pairs B where A.right_entry = B.left_entry)

JLL

Jonathan Moore wrote:
> 
> I am wondering why it uses the O(n^2) nested loop when there is a O(N)
> methoud using btree indexes for a merg join. I am using  7.2.1 would
> upgrading fix my problime or is it somthing else?
> 
> Given the schema:
> 
> drop   table Entry_Pairs;
> create table Entry_Pairs (
>     left_entry  int              REFERENCES Entry   ON DELETE RESTRICT,
>     right_entry int              REFERENCES Entry   ON DELETE RESTRICT,
>     relation    int     NOT NULL                                      ,
>     subtract    bool    NOT NULL                                      ,
>     comment     int         NULL REFERENCES Comment ON DELETE SET NULL,
>     UNIQUE (left_entry, right_entry, relation)
> );
> CREATE INDEX entry_pairs_left_index ON entry_pairs (left_entry);
> CREATE INDEX entry_pairs_right_index ON entry_pairs (right_entry);
> --
> 
> You get this"
> 
> dblex=> explain select A.left_entry from entry_pairs A, entry_pairs B
> where A.right_entry != B.left_entry;
> NOTICE:  QUERY PLAN:
> 
> Nested Loop  (cost=100000000.00..102876671.17 rows=97545252 width=12)
>   ->  Seq Scan on entry_pairs a  (cost=0.00..167.77 rows=9877 width=8)
>   ->  Seq Scan on entry_pairs b  (cost=0.00..167.77 rows=9877 width=4)
> 
> EXPLAIN
> 
> That is dum. If you just walk both B-Tree indexes there is a O(n)
> search. I tryed to turn off netsed loops but it still did it. (the
> reason the cost is 100000000.00 is a artifact from turing off loops)
> 
> -Jonathan
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 6: Have you searched our list archives?
> 
> http://archives.postgresql.org




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


end of thread, other threads:[~2003-04-17 14:12 UTC | newest]

Thread overview: 4+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2003-04-16 06:58 dum query plan Jonathan Moore <moore@discern.com>
2003-04-17 01:21 ` Stephan Szabo <sszabo@megazone23.bigpanda.com>
2003-04-17 03:15 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-04-17 14:12 ` Jean-Luc Lachance <jllachan@nsd.ca>

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