X-Original-To: pgsql-performance@postgresql.org Received: from spampd.localdomain (postgresql.org [64.49.215.8]) by postgresql.org (Postfix) with ESMTP id 6DE004758F1 for ; Thu, 17 Apr 2003 11:29:40 -0400 (EDT) Received: from spunge-bob.discern.com (dsl092-251-241.sfo2.dsl.speakeasy.net [66.92.251.241]) by postgresql.org (Postfix) with ESMTP id B6545475458 for ; Thu, 17 Apr 2003 11:29:39 -0400 (EDT) Received: by spunge-bob.discern.com (Postfix, from userid 1000) id E89FD27C88; Wed, 16 Apr 2003 15:02:49 -0700 (PDT) Subject: dum query plan: more info. From: Jonathan Moore To: pgsql-performance@postgresql.org Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: Ximian Evolution 1.0.5 Date: 16 Apr 2003 15:02:49 -0700 Message-Id: <1050530569.20873.120.camel@spunge-bob> Mime-Version: 1.0 X-Spam-Status: No, hits=-12.0 required=5.0 tests=BAYES_10,DATE_IN_PAST_12_24,USER_AGENT_XIMIAN 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/153 X-Sequence-Number: 1659 I now under stand that my join was rong but none of the seguestions are the optimal solution to the problime. You can make this order n if you try. The trick is to use a mearg join using sorted list of the unique keys in each colum join. The question you are asking is what left hand entrys do not exist on the right. select A.left form pairs A, pairs B where A.left != B.right; (note: my code in the first example select left form the rong table but it dosn't change the search.) take the DB: (1,2) (2,1) (1,5) (4,5) (5,2) Sort the colums: left right ==== ===== 1 1 2 2 4 5 5 Start at the top you see that you have 1 in both columes there for you know that 1 is not a answer. pop both colums. same for 2. Whe you get to the top of the lists as 4, 5; you know that 4 apperas on the only in the left colum as you don't see it on the right. pop the left colum. now you see that 5 is on both sides so 5 is not a canadate. You are out of options so you are done 4 is the only value that is on the left and only on the left. This methoud is order O(n) if both colums have b-tree indexes so you don't have to pre sort them othere wise it is O(n*log(n)) as the sort is the greatest complexity. In eathere case it is way better then O(n^2) for almost any n. I have this implmented in my code by selecting each colum and then doing the mearg my self more expensive then a in db join as there is pointless data copys. sudo perl for the hole thing is: #!/usr/bin/not-realy-perl my @left = select distinct left_entry from entry_pairs order by left_entry; my @right = select distinct right_entry from entry_pairs order by right_entry; my @only_left; while (1) { if (not @left) { last; #done } elsif (not @right) { push @only_left, $left[0]; pop @left; } elsif ($left[0] == $right[0]) { pop @left; pop @right; } elsif ($left[0] < $right[0]) { push @only_left, $left[0]; pop @left; } elsif ($left[0] > $right[0]) { pop @right; } } -Jonathan