X-Original-To: pgsql-performance@postgresql.org Received: from spampd.localdomain (postgresql.org [64.49.215.8]) by postgresql.org (Postfix) with ESMTP id BCB06475956 for ; Wed, 16 Apr 2003 23:15:42 -0400 (EDT) Received: from sss.pgh.pa.us (unknown [192.204.191.242]) by postgresql.org (Postfix) with ESMTP id BAAAA475458 for ; Wed, 16 Apr 2003 23:15:38 -0400 (EDT) Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.12.9/8.12.9) with ESMTP id h3H3FVU6002844; Wed, 16 Apr 2003 23:15:31 -0400 (EDT) To: Jonathan Moore Cc: pgsql-performance@postgresql.org Subject: Re: dum query plan In-reply-to: <1050476308.20872.19.camel@spunge-bob> References: <1050476308.20872.19.camel@spunge-bob> Comments: In-reply-to Jonathan Moore message dated "15 Apr 2003 23:58:28 -0700" Date: Wed, 16 Apr 2003 23:15:31 -0400 Message-ID: <2843.1050549331@sss.pgh.pa.us> From: Tom Lane X-Spam-Status: No, hits=-32.3 required=5.0 tests=BAYES_00,EMAIL_ATTRIBUTION,IN_REP_TO,QUOTED_EMAIL_TEXT, REFERENCES,REPLY_WITH_QUOTES 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/150 X-Sequence-Number: 1656 Jonathan Moore 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