Matthew Wakeling <matthew@flymine.org> 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