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
