Thanks! This is *exactly* what I'm doing currently. The only trouble is to get the le, ge, cmp etc operators to agree with MySQL's idea of whether a row is lt/gt/eq the other row.
Imagine the left-hand table has "éclair" and "ecstatic", and the right-hand table has only "ecstatic". MySQL sorts é before other 'e' values, so the merge algorithm sees "éclair" on the left and "ecstatic" on the right after fetching the first row from each table. Perl thinks "ecstatic" should come first though -- at least that's how it works with just the default collations. So the merge algorithm concludes "ecstatic" doesn't exist in the left-hand table. After this, it runs out of rows in the right-hand table and decides "éclair" doesn't exist there, then fetches the next row from the left-hand table -- and decides "ecstatic" doesn't exist in the right-hand table.
It's quite a train wreck unless I get Perl's sorting to exactly match MySQL's!