pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Jean-Luc Lachance <jllachan@nsd.ca>
To: Jonathan Moore <moore@discern.com>
Cc: pgsql-performance@postgresql.org
Subject: Re: dum query plan
Date: Thu, 17 Apr 2003 10:12:35 -0400
Message-ID: <3E9EB653.B6E200B4@nsd.ca> (raw)
References: <1050476308.20872.19.camel@spunge-bob>

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




view thread (4+ messages)

Message-ID: <3E9EB653.B6E200B4@nsd.ca>
Permalink:  ../3E9EB653.B6E200B4@nsd.ca/
Also on:    postgresql.org/message-id/3E9EB653.B6E200B4@nsd.ca

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-performance@postgresql.org
  Cc: jllachan@nsd.ca, moore@discern.com
  Subject: Re: dum query plan
  In-Reply-To: <3E9EB653.B6E200B4@nsd.ca>
  References: <1050476308.20872.19.camel@spunge-bob> <3E9EB653.B6E200B4@nsd.ca>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

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