ShakilljohnnygПо 100млн строк в каждой таблице.
Любому ускорению от 5% по сравнению с посимвольным сравнением буду рад.
у вас два полных скана, некий расход памяти и проверка (100млн * 100млн ) пар.

если маски повторяются в пределах одной таблицы, можно дистинктом уменьшить количество проверяемых пар, но получим затраты на дистинкт; можно отсеять обратные друг другу комбинации; можно сразу выбрать одинаковые маски из A и B как подходящие, можно сразу выбрать случаи когда одна маска покрывает другую и т.д.Можно еще взять с начала строки все что до символа "_" прибавить "%" и проиндексировать. А потом искать, в обе стороны, по этим индексам пары с помощью LIKE. Тогда, если "_" обычно встерчается не в начале строки, то можно отсечь какое то количество пар, НО, даже 1млн * 1млн это все равно очень и очень много. Так что, я бы сказал что задача в таком виде не решаема в реальные сроки.

Еще было бы интересно узнать зачем все это надо?