Hai provato a eseguire la query originale con TOP 1? molto probabilmente sarà altrettanto lento.
A volte, quando l'ottimizzatore pensa che qualcosa sia molto probabile e restituirà un vasto insieme di dati con poco sforzo (cioè quasi tutti i record verranno restituiti), sceglie principalmente i join di ciclo perché deve solo ottenere il primo e un loop join va bene solo per ottenere un paio di record. Quando si scopre che non è vero, ci vuole un'eternità e un giorno per ottenere risultati.
Nel tuo caso, sembra molto raro, quindi questa scelta fa molto male. Prova invece a fare qualcosa come SELECT @count = COUNT(*) FROM ... e quindi controllando se quel conteggio è diverso da zero.
