X-Original-To: pgsql-performance@postgresql.org Received: from spampd.localdomain (postgresql.org [64.49.215.8]) by postgresql.org (Postfix) with ESMTP id ECAF7475D91 for ; Thu, 17 Apr 2003 10:11:19 -0400 (EDT) Received: from beamish.nsd.ca (beamish.nsd.ca [205.150.156.194]) by postgresql.org (Postfix) with ESMTP id DF6D3475F1B for ; Thu, 17 Apr 2003 10:11:15 -0400 (EDT) Received: (from smap@localhost) by beamish.nsd.ca (8.9.3/8.9.3) id KAA30572; Thu, 17 Apr 2003 10:11:07 -0400 X-Authentication-Warning: beamish.nsd.ca: smap set sender to using -f Received: from reddog.nsd.ca(192.168.101.30) by beamish.nsd.ca via smap (V2.1/2.1+anti-relay+anti-spam) id xma030568; Thu, 17 Apr 03 10:11:02 -0400 Received: from nsd.ca (jllachan-linux.nsd.ca [192.168.101.148]) by reddog.nsd.ca (8.8.7/8.8.7) with ESMTP id KAA27904; Thu, 17 Apr 2003 10:05:29 -0400 Message-ID: <3E9EB653.B6E200B4@nsd.ca> Date: Thu, 17 Apr 2003 10:12:35 -0400 From: Jean-Luc Lachance X-Mailer: Mozilla 4.77 [en] (X11; U; Linux 2.4.18-24.7.x i686) X-Accept-Language: en MIME-Version: 1.0 To: Jonathan Moore Cc: pgsql-performance@postgresql.org Subject: Re: dum query plan References: <1050476308.20872.19.camel@spunge-bob> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Spam-Status: No, hits=-30.7 required=5.0 tests=BAYES_01,EMAIL_ATTRIBUTION,QUOTED_EMAIL_TEXT,REFERENCES, REPLY_WITH_QUOTES,X_AUTH_WARNING autolearn=ham version=2.50 X-Spam-Level: X-Spam-Checker-Version: SpamAssassin 2.50 (1.173-2003-02-20-exp) X-Archive-Number: 200304/152 X-Sequence-Number: 1658 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