Thanks. We had tried ORDER BY NEWID() and as Ron suggested it was definitely slower.

TABLESAMPLE didn't work because we need a sample of joined rows and you can only...