在具有hierarchyid字段的SQL Server表上运行有序查询性能缓慢

Question

我有一个类别树存储在一个表中，该表目前有一个传统的ParentCategoryId字段和一个称为Echelon的hierarchyid字段。

以下查询成功地提取了我所需格式的数据，其中包含深度级别和按深度和类别名称排序的类别：

WITH q AS
(
    SELECT
        c.Id,
        c.Name,
        c.Echelon,
        c.Echelon AS NewEchelon
    FROM
        Category c
    WHERE
        Deleted IS NULL AND ParentCategoryId IS NULL
    UNION ALL
    SELECT
        c2.Id,
        c2.Name,
        c2.Echelon,
        hierarchyid::Parse(q.NewEchelon.ToString() + CAST(ROW_NUMBER() OVER (ORDER BY q.Name) AS NVARCHAR(MAX)) + '/')
    FROM
        q
    JOIN
        Category c2 ON c2.Deleted IS NULL AND c2.Echelon.IsDescendantOf(q.Echelon) = 1 AND c2.Echelon.GetLevel() = q.Echelon.GetLevel() + 1
)
SELECT * FROM q ORDER BY NewEchelon

遗憾的是，这个查询的性能不太好。真正的表只有319个类别，其中89个类别是软删除的，Deleted列中有一个非空值。

该查询的时间如下：

SQL Server parse and compile time: 
   CPU time = 0 ms, elapsed time = 0 ms.
(230 row(s) affected)
 SQL Server Execution Times:
   CPU time = 218 ms,  elapsed time = 321 ms.

现在，对于如此少量的数据，三分之一秒的时间对我来说似乎相当疯狂。除了集群PK之外，表上没有索引。有没有办法重写它，使它更快？我只需要添加适当的索引吗？每当类别或其结构发生变化时，我是否应该考虑存储使用上述查询生成的HierarchySortOrder？我应该考虑在应用程序级别缓存类别树吗？

我的直觉告诉我，这个查询不应该花这么长时间，我可能错过了一个技巧，但我很感谢任何关于这个问题的建议！

---

以下是执行计划：

执行计划http://s27.postimg.org/mo30oy2yp/executionplam.png链接到全尺寸图像

Answer 1

考虑到它是一个联合查询、一些函数和一个联接，处理时间对我来说似乎是公平的同时使用With会带来子查询处理时间，以考虑