Trotzdem würde mich diese "Berechnung" interessieren.

Anstelle von

select ...
, Key1 concat key2 as sortkey
...
order by sortkey

müsste doch auch ein "order by key1, key2" genügen.
Oder fügst du noch bedingte Konstanten ein?

Wenn in der Stückliste die Schlüssel Mandant und/oder Firma fehlen, benötigst du diese ja eigentlich gar nicht für den Sort, da du diese ja über ggf. einen Subselect/CTE hinzufügst.

Somit beschränkt sich das Problem auf die Abteilung.
Auch hier ist die Frage, ob diese dann nicht auch mehr oder weniger konstant ist.

Auch ist die Art des Cursors wichtig.
Ich hoffe es ist kein scrollable (sensitive) Cursor, das verhindert eine Kopie der Daten und erzwingt ggf. einen temporären Index über den gesamten Datenbestand, was die Antwortzeit erklärt.

Kannst du den SQL mal posten?