Еще повертев запрос немного пришел к выводу что запрос сам по себе плохой
(две таблицы джойнятся не по уник идентификатоу)

Вот так у меня работает быстро (1 сек)

select top 1000000
*
from tx1 t1
inner join tx1 t2 on (t1.x1=t2.x1 or t1.x2=t2.x2)
where
t1.id!=t2.id

и учти что если много повторов (для это множитель в рандоме сделай 100 а не 10000000)
получается много совпадений и при 3000 объеме таблицы и множителе 100 получается 172000 результатов