Евгений Быков

Я думаю, что соответствующий алгоритм на псевдокоде можно изобразить как-то так:

Создадим массив из N элементов типа Node и проинициализируем его:

class Node {
    int group;
    int key;
    int index;
}

Node[N] nodes;

for (int i = 0; i < N; i++) {
    nodes[i].group = 0;
    nodes[i].index = i;
}

Последовательность элементов с одинаковым значением поля group будем в дальнейшем называть группой. Таким образом, после инициализации мы имеем одну неотсортированную группу из N элементов.

Теперь будем сортировать этот массив в цикле по функциям, в каждой итерации мы будем ужесточать порядок в группах, которые содержат более одного элемента, т.е., еще не отсортированы:

for (int j = 0; j < M; j++) {
    // для каждой группы, содержащей более одного элемента
        // вычисляем значение ключа в каждом элементе этой группы
        // сортируем на месте элементы этой группы по этому ключу
        // разбиваем группу на подгруппы с одинаковым значением ключа, присваиваем подгруппам уникальные номера
    // если все группы содержат ровно по одному элементу, то досрочный выход из цикла
}

Суть алгоритма в том, что после выполнения j-ой итерации массив nodes оказывается побит на группы, содержащие ровно по одному элементу, и группы, содержащие элементы, которые нельзя различить, используя только функции с номерами меньше j. При этом сами группы между собой упорядочены.

По-моему, очевидно, что лишних вызовов функций вычисления ключа в этом алгоритме нет.

После завершения цикла все элементы в массиве nodes отсортированы, для ссылки на элементы исходного массива используется значение поля index.

Сливаем две таблицы

SELECT * FROM tbl1
UNION ALL
SELECT * FROM tbl2

затем группируем по всем полям и выбираем те группы, которые содержат более одной записи

SELECT *
    FROM (SELECT * FROM tbl1
          UNION ALL
          SELECT * FROM tbl2
         )
    GROUP BY field1, field2, ...
    HAVING COUNT(*) > 1

Такой запрос не требует индексов и будет очень эффективен даже на очень больших таблицах
Разумеется, решение основано на предположении об уникальности записей в каждой из таблиц