Когда сможешь отобразить план, то сможешь на нем правой кнопкой мыши щелкнуть и там будет. Show execution plan xml (или както так). Вот этот xml надо скопировать, вставить вот сюда https://www.brentozar.com/pastetheplan/ и прислать нам ссылку. Мы сможем посмотреть и может что-то посоветуем.
У тебя запрос не полный. Должно быть еще что-то про выборку из твоей CTE. Ты ее щас просто объявил, но не выбираешь из нее. Следубщей строкой должно идити что-то типа select a, b, c from a where a=12345
в чем суть рандома в вашей задаче? если вы думаете что 900к из 1ккк это достаточная выборка для получения инсайтов - не думайте так. хотите быстро - уберите ORDER BY. ну и * замените на конкретные поля, которые нужны, а не все подряд тащите.
ну и да, вам во 2-й канал (см закрепленное сообщение)