Ahi lo que veo mas problematico son los EXIST y mas que todo el NOT EXIST. Normalmente eso no es muy eficiente de hacer.
Que el SELECT de insercion sea "grande" no es en si el problema (es posible hacer inserciones de 1-4GB -dependiendo de motor y parametros- en unos <200 segundos en hardware medio medio, siempre y cuando todo este alineado
). Asi que pon atencion a lo que te estan diciendo que eso se puede mejorar bastante...