Org chart CTE with exact index but plan shows expensive sort node

Question

I've got a moderately large table (148 million rows) that's got pretty common org chart attributes to it. Names are changed, but it's the same idea. I was thinking of adding a hierarchyid column to the mix; then I could index that and hopefully make some of the queries faster.

This query is modeled on the msdocs sample on hierarchy id. Before I ran it, I put indexes on (employeeid), (managerid, include employeeid), and (officeid, managerid, employeeid) hoping to make it as fast as possible. But the query took over 5 hours to run.

I looked at the plan, and the (officeid, managerid, employeeid) index is used for both parts of the cte.

What I don't understand is that the ROW_NUMBER() windowing function also appears to have added a SORT node, which ss says is taking 94% of the query time. It's already using an index that is pre-ordered in the same way, so why is there a SORT node taking up 94% of the time?

Thanks

WITH paths(path, duns, extended_gu, extended_parent)   
AS (  -- This section provides the value for the root of the hierarchy  
    SELECT hierarchyid::GetRoot() AS path, employeeid, officeid, managerid
    FROM OrgChart where officeid = 0

    -- This section provides values for all nodes except the root  
    UNION ALL   
    SELECT CAST(p.path.ToString() + CAST(ROW_NUMBER() OVER (PARTITION BY RD.officeid, RD.managerid 
    ORDER BY RD.officeid, RD.managerid) AS varchar(30)) + '/' AS hierarchyid),   
    RD.employeeid, RD.managerid, Rd.officeid
    FROM OrgChart rd   
    JOIN paths AS p ON rd.managerid = P.employeeid
) 
UPDATE rd set tree=P.Path
FROM Paths P
INNER JOIN  OrgChart rd on rd.duns = P.Duns

EDIT: Schema, added in response to comment below. I don't see a "Paste The Plan" as a feature in the editor; where is that? Rather than null on the roots, those ids are 0

CREATE TABLE [dbo].[OrgChart](
    [employeeid] [int] NOT NULL,
    [managerid] [int] NOT NULL,
    [officeid] [int] NOT NULL,
    ...
    [tree] [hierarchyid] NULL
) ON [PRIMARY]
GO

CREATE UNIQUE NONCLUSTERED INDEX [uixOrgChart_employeeids] ON [dbo].[OrgChart]
(
    [employeeid] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]

CREATE UNIQUE NONCLUSTERED INDEX [uixOrgChart_officemgremployee] ON [dbo].[OrgChart]
(
    [officeid] ASC,
    [managerid] ASC,
    [employeeid] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]

CREATE NONCLUSTERED INDEX [uixOrgChart_mgremp] ON [dbo].[OrgChart]
(
    [managerid] ASC
)
INCLUDE([employeeid]) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]

Answer 1

Actually Erik's comment above was the most probative.

Creating a better index cut the time from 5 hours to a little over 3.

The other thing that made an even bigger difference was not updating columns on the main table; rather, I directed the hierarchy ids off into a normalized table instead. That cut the time from a little over 3 to a little over 1