Вам не нужно DINSTINCT
для этого. Это добавляет ненужные накладные расходы к оператору удаления.
Во-вторых, почему вы используете временную таблицу? Вы пытались объединить эти два утверждения в одно?
DELETE
FROM Nodes
WHERE id NOT IN
(SELECT node_id FROM Relations)
или удалите строки небольшими порциями, как предложил @Serguei:
SELECT 1
WHILE @@ROWCOUNT > 0
BEGIN
DELETE TOP (1000)
FROM Nodes
WHERE id NOT IN
(SELECT node_id FROM Relations)
END