深入了解递归 CTE

• 下载 CTE - 0.6 KB

引言

SQL Server 2005 中引入的公共表表达式 (CTE) 一直让我颇为困扰。我能够照搬语法来实现我想要的结果，但我无法诚实地说我理解其工作原理。我总是需要一个心智模型来理解事物，而这个模型在那时是缺失的。

最近，我认为我找到了一个模型，它能帮助我处理 CTE 并解释它们虽然不同，但实际上与普通编程中的递归是类似的。

背景

递归

让我们从递归这个通用编程概念开始。考虑这段代码：

public string Rec(int Level) {
    if (Level == 0)
        return "0";
    else
        return Level.ToString() + "_" + Rec(Level - 1);
}

这段代码会反复调用自身，直到 Level 达到 0。所以这次调用

Rec(3);

会产生如下结果：

3_2_1_0

大致上，执行过程是这样的：

RecursionExample(3) =
        "3_" + RecursionExample(2) = 
            "3_2_" + RecursionExample(1) = 
                "3_2_1_" + RecursionExample(0) = 
                    "3_2_1_0"

每次函数被调用时，它会接收前一次调用的 Level，将其转换为一个将要返回的字符串，并在减去 1 后将 Level 传递给下一次调用。

SQL 中的递归

现在来看 SQL。这里有一个递归 CTE 的例子：

with cte as (
    select    1 id, null ParentId
    union all
    select    C.Id, C.ParentId
    from    SomeTable as C
        inner join cte as P -- here it joins against itself
                on C.ParentId = P.Id    
)

在其定义中，它会与自身连接，使其成为一个递归 CTE。这与 C# 示例中函数调用自身是相同的原理，但有一些细微差别。

首先，它实际上并不是与自身连接，而是与自身的前一次迭代连接。就像 C# 示例调用自身几次，每次得到不同结果（"3_"、"3_2_" 等）一样，CTE 的执行也有阶段。每次调用自身，都会创建一个新的阶段。

其次，SQL 是一种基于集合的语言。所以，而不是将一个整数传递给下一次调用并接收一个字符串，CTE 的每次迭代都会接收一个集合，并返回一个集合（具有相同的列）。在这里，我们与前一次迭代进行连接，并将当前迭代的结果与前一次迭代的结果进行 union。CTE 中的每次迭代都会产生一个行集合，而 CTE 的下一次调用将该集合作为其输入。

但是，在下一次迭代中只使用当前迭代中的行，就像 C# 代码中递减并传递给下一次调用的整数一样。与所有先前迭代的 union 操作是在该集合返回之后才进行的，就像在 C# 中添加到字符串中的一样。理解这两者之间的分离很重要。

最后，它的工作方式与 C# 的方式有些相反。在 C# 示例中，每次函数调用自身时，它都会将工作所需的值 (Level - 1) 传递给它。在 SQL 中，我们实际上并没有传递变量，而是针对 CTE 的前一次迭代进行操作。它有点像向后看。

让我们用一个简单的例子来澄清这一点，就像我们在 C# 中做的那样。考虑这个表示小型父子关系的表：

ID	父节点 ID
1	null
2	1
3	1
4	2

当我们将上述 CTE 应用于它时，执行步骤将是这样的，这与我们在 C# 中的操作是类似的：

1, null
    2, 1
    3, 1
        4, 2

第一次迭代是我们选择 CTE 中的第一行 (1, null)。

然后是 union 操作，它会触发对 CTE 的新调用。在第一次迭代中，我们只有一行，所以第二次迭代“看到”的就是这一行来进行连接。这是理解递归 CTE 的关键：CTE 中的每次迭代只“看到”前一次迭代的结果。

因此，第二次迭代与那一行进行连接，并返回 (2, 1) 和 (3, 1)，因为它们的 Parent ID = 1。

现在，另一个 CTE 再次调用自身，将 SomeTable 中的行与这两行进行连接，结果是 (4, 2)。

再次进行一次连接，但没有返回更多行，因此递归停止，CTE 返回所有五条记录。

使用老式 SQL 模拟 CTE

这种行为可以在不使用 CTE 的情况下进行模拟，如下所示：

-- create table to hold results
declare @cte table (
    id int,
    ParentId int,
    Pass int
)
-- declare variable to hold pass
declare @Pass int
set    @Pass = 0

-- insert initial set
insert    @cte(id, ParentId, Pass)
values    (1, 0, @Pass)

-- add descendants
while     @@ROWCOUNT > 0 -- keep going until there are no more rows added
begin
    -- increment pass
    set @Pass = @Pass + 1
    
    -- insert next pass
    insert    @cte (id, ParentId, Pass)
    select    C.Id, C.ParentId, @Pass
    from    @t C
        inner join @cte P 
            on C.ParentId = P.id
            and P.Pass = @Pass - 1 -- only join against rows from 
                        --the previous pass, just like the CTE
end    
select * from @cte -- including the Pass column here to clear things up.
                   -- The 'real' CTE does not include it (probably becuase it doesn't have
                   -- to use it under the covers)

WHILE @@ROWCOUNT < 0 会一直重复该部分，直到没有更多行受影响为止。每次将新集合添加到结果集中时，通过添加迭代深度来保持它们的独立性。该迭代深度可以在连接中使用，以仅识别在前一次迭代中添加的行。

使用 CTE 模拟老式 SQL

上一个示例中的 Pass 列可以轻松添加到 CTE 中，以帮助用户跟踪结果集创建的各个步骤。以下列表正是这样做的。

with cte as (
    select    1 id, 0 ParentId, 0 Pass -- start with Pass = 0
    union all
    select    C.Id, 
        C.ParentId, 
        P.Pass + 1    -- Increment Pass column with each pass by adding 1
                    -- to the previous value (note that *P*.Pass was used to add to)
    from    @t as C
        inner join cte P on C.ParentId = P.Id    
)
select * from cte

我们从一个起始行开始，并为其指定 Pass = 0。然后我们与其进行连接以查找子项，并添加它们，指定 Pass = 1，以此类推，直到没有更多行被添加。

使用代码

包含了一个示例代码供用户自行查看。只需打开并执行它。

关注点

当我理解了每次迭代只查看前一次迭代时，CTE 就变得不再神秘，我使用它们生产环境时也更加得心应手了。在那之前，我只是在重复我并未完全理解的代码。迭代为我提供了一个心智模型，帮助我处理 CTE。我希望它也能帮助你做到这一点。CTE 能使代码更清晰，更容易写对，并且对于未来阅读你代码的开发者来说也更容易理解（当然，在他阅读了这篇文章之后 ;-))。

我相信它们是 SQL 的一个非常受欢迎的补充，因为它们允许你指定你想要什么，而不是必须告诉 SQL如何获取该结果。SQL 长期以来是最成功的声明式语言之一，而 CTE 让你能够比以往更清晰地表达你的意图。比较这两个示例应该能证明这一点。

历史

• 2010 年 5 月 25 日：版本 1.0。