Received: from localhost (unknown [200.46.204.183]) by mail.postgresql.org (Postfix) with ESMTP id 17AF66352E0 for ; Fri, 3 Apr 2009 11:24:49 -0300 (ADT) Received: from mail.postgresql.org ([200.46.204.86]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 31431-05 for ; Fri, 3 Apr 2009 11:24:45 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130]) by mail.postgresql.org (Postfix) with ESMTP id 46BB3634CF2 for ; Fri, 3 Apr 2009 11:24:46 -0300 (ADT) Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.14.2/8.14.2) with ESMTP id n33EOfZK029731; Fri, 3 Apr 2009 10:24:41 -0400 (EDT) To: Matthew Wakeling cc: pgsql-performance@postgresql.org Subject: Re: plpgsql arrays In-reply-to: References: <603c8f070904030647u1c92e13ew53612ac0011ed7c1@mail.gmail.com> <28595.1238767442@sss.pgh.pa.us> Comments: In-reply-to Matthew Wakeling message dated "Fri, 03 Apr 2009 15:14:54 +0100" Date: Fri, 03 Apr 2009 10:24:41 -0400 Message-ID: <29730.1238768681@sss.pgh.pa.us> From: Tom Lane X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0 tagged_above=0 required=5 tests=none X-Spam-Level: X-Archive-Number: 200904/66 X-Sequence-Number: 33433 Matthew Wakeling writes: > On Fri, 3 Apr 2009, Tom Lane wrote: >> I don't actually believe that a standard merge join algorithm will work >> with an intransitive join condition ... > A standard merge join should work absolutely fine, depending on how it's > implemented. If the implementation keeps a list of "current" right-hand > elements, and adds right-hand rows to the list when they compare "equal" > to the current left-hand element, and removes them from the list when they > compare "not equal" to the current left-hand element, then it would work > fine. No, it would not. Not unless you have sorted the inputs in some way that has more knowledge than the "equal" operator represents. Otherwise you can have elements drop out that might still be needed to match to a later left-hand element. Remember the point of the intransitivity assumption: there can be a right-hand element X that is "equal" to two left-hand elements Y and Z, but Y and Z are not "equal" to each other and thus might not be kept adjacent in the left-hand sorting. regards, tom lane