一、概述
公用表表达式或 CTE 就像临时视图，仅在单个 SQL 语句期间存在。常用表表达式有两种：“普通”和“递归”。普通的公用表表达式有助于通过从主 SQL 语句中分解出子查询来使查询更容易理解。递归公用表表达式提供了对树和图进行分层或递归查询的能力，这种能力在 SQL 语言中是不可用的。
所有公用表表达式（普通的和递归的）都是通过在SELECT、INSERT、DELETE或UPDATE语句前面添加一个 WITH 子句来创建的。单个 WITH 子句可以指定一个或多个公用表表达式，其中一些是普通的，一些是递归的。
2.普通公用表表达式
一个普通的公用表表达式就像一个在单个语句的持续时间内存在的视图一样工作。普通的公用表表达式对于分解子查询和使整个 SQL 语句更易于阅读和理解很有用。
WITH 子句可以包含普通的公用表表达式，即使它包含 RECURSIVE 关键字也是如此。使用 RECURSIVE 不会强制公用表表达式递归。
3.递归公用表表达式
递归公用表表达式可用于编写遍历树或图的查询。递归公用表表达式具有与普通公用表表达式相同的基本语法，但具有以下附加属性：
- “ select-stmt ”必须是复合选择。也就是说，CTE 主体必须是两个或多个单独的 SELECT 语句，由 UNION、UNION ALL、INTERSECT 或 EXCEPT 等复合运算符分隔。
- 组成复合的一个或多个单独的 SELECT 语句必须是“递归的”。如果 SELECT 语句的 FROM 子句恰好包含一个对 CTE 表（在 AS 子句左侧命名的表）的引用，则该 SELECT 语句是递归的。
- 复合中的一个或多个 SELECT 语句必须是非递归的。
- 所有非递归 SELECT 语句必须出现在任何递归 SELECT 语句之前。
- 递归 SELECT 语句必须与非递归 SELECT 语句分开，并通过 UNION 或 UNION ALL 运算符彼此分开。如果有两个或多个递归 SELECT 语句，则必须使用将第一个递归 SELECT 语句与最后一个非递归 SELECT 语句分开的相同运算符将它们彼此分开。
- 递归 SELECT 语句不能使用 聚合函数或窗口函数。
换句话说，递归公用表表达式必须如下所示：
在上图中，initial-select表示一个或多个非递归 SELECT 语句，recursive-select表示一个或多个递归 SELECT 语句。最常见的情况是只有一个初始选择和一个 递归选择，但允许每个选择超过一个。
将递归公用表表达式中以cte-table-name命名的表称为“递归表”。在上面的recursive-cte气泡图中，递归表必须在recursive-select中每个顶级 SELECT 语句的 FROM 子句中恰好出现一次， 并且不得出现在 initial-select或 recursive-select中的任何其他地方，包括子查询。initial-select可以是复合选择，但它可能不包括 ORDER BY、LIMIT 或 OFFSET。递归选择也可以是复合选择限制是该复合的所有元素必须由将 initial-select与recursive-select分开的相同 UNION 或 UNION ALL 运算符分隔。递归选择允许包含 ORDER BY、LIMIT 和/或 OFFSET，但不能使用 聚合函数或窗口函数。
在版本 3.34.0 (2020-12-01)中添加了递归选择成为复合的能力。在早期版本的 SQLite 中，递归选择只能是一个简单的 SELECT 语句。
计算递归表内容的基本算法如下：
- 运行初始选择并将结果添加到队列中。
- 当队列不为空时：
- 从队列中提取一行。
- 将该单行插入递归表
- 假设刚刚提取的单行是递归表中的唯一行并运行递归选择，将所有结果添加到队列中。
上述基本程序可以通过以下附加规则进行修改：
如果 UNION 运算符将initial-select与 recursive-select连接起来，那么只有在之前没有相同的行被添加到队列中时才将行添加到队列中。重复的行在被添加到队列之前被丢弃，即使重复的行已经通过递归步骤从队列中提取出来。如果运算符是 UNION ALL，则初始选择和 递归选择生成的所有行总是添加到队列中，即使它们是重复的。在确定一行是否重复时，NULL 值比较彼此相等而不等于任何其他值。
LIMIT 子句（如果存在）确定将在步骤 2b 中添加到递归表中的最大行数。一旦达到限制，递归就会停止。零限制意味着没有行被添加到递归表中，而负限制意味着可以向递归表中添加无限数量的行。
OFFSET 子句（如果存在且具有正值 N）会阻止将前 N 行添加到递归表中。前 N 行仍然由递归选择处理——它们只是没有添加到递归表中。在跳过所有 OFFSET 行之前，行不计入满足 LIMIT 的内容。
如果存在 ORDER BY 子句，它会确定在步骤 2a 中从队列中提取行的顺序。如果没有 ORDER BY 子句，则提取行的顺序是未定义的。（在当前的实现中，如果省略 ORDER BY 子句，队列将变为 FIFO，但应用程序不应依赖于该事实，因为它可能会更改。）
3.1. 递归查询示例
以下查询返回 1 到 1000000 之间的所有整数：
WITH RECURSIVE cnt(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM cnt WHERE x<1000000) SELECT x FROM cnt;
考虑一下这个查询是如何工作的。initial-select 首先运行并返回单行和单列“1”。这一行被添加到队列中。在步骤 2a 中，该行从队列中提取并添加到“cnt”。然后根据步骤 2c 运行递归选择，生成一个值为“2”的新行以添加到队列中。队列仍然有一行，因此重复第 2 步。“2”行被提取并通过步骤 2a 和 2b 添加到递归表中。然后使用包含 2 的行，就好像它是递归表的完整内容一样，并且再次运行递归选择，导致将值为“3”的行添加到队列中。这将重复 999999 次，直到最后在步骤 2a 中队列中的唯一值是包含 1000000 的行。该行被提取并添加到递归表中。但是这一次，WHERE 子句导致递归选择不返回任何行，因此队列保持为空并且递归停止。
优化说明： 在上面的讨论中，像“将行插入递归表”这样的语句应该从概念上理解，而不是从字面上理解。听起来好像 SQLite 正在积累一个包含一百万行的巨大表，然后返回并从上到下扫描该表以生成结果。真正发生的是查询优化器发现“cnt”递归表中的值只使用了一次。因此，当每一行被添加到递归表时，该行作为主 SELECT 语句的结果立即返回，然后被丢弃。SQLite没有累积一个包含一百万行的临时表。运行上面的例子只需要很少的内存。但是，如果该示例使用 UNION 而不是 UNION ALL，则 SQLite 将不得不保留所有先前生成的内容以检查重复项。出于这个原因，程序员应该在可行的情况下努力使用 UNION ALL 而不是 UNION。
这是前面示例的变体：
WITH RECURSIVE
cnt(x) AS (
SELECT 1
UNION ALL
SELECT x+1 FROM cnt
LIMIT 1000000
)
SELECT x FROM cnt;
这种变化有两个不同之处。初始选择是“SELECT 1”而不是“VALUES(1)”。但这些只是表达完全相同事物的不同语法。另一个变化是递归由 LIMIT 而不是 WHERE 子句停止。LIMIT 的使用意味着当百万分之一的行被添加到“cnt”表时（并由主 SELECT 返回，感谢查询优化器）然后递归立即停止，无论队列中可能剩下多少行. 在更复杂的查询中，有时很难确保 WHERE 子句最终会导致队列耗尽和递归终止。但是 LIMIT 子句将始终停止递归。
3.2. 分层查询示例
考虑一个描述组织成员以及该组织内的指挥链的表格：
CREATE TABLE org( name TEXT PRIMARY KEY, boss TEXT REFERENCES org, height INT, -- other content omitted );
组织中的每个成员都有一个名字，大多数成员只有一个老板。（整个组织的负责人有一个空的“boss”字段。）“org”表的行形成了一棵树。
下面是一个计算 Alice 组织中每个人（包括 Alice）的平均身高的查询：
WITH RECURSIVE
works_for_alice(n) AS (
VALUES('Alice')
UNION
SELECT name FROM org, works_for_alice
WHERE org.boss=works_for_alice.n
)
SELECT avg(height) FROM org
WHERE org.name IN works_for_alice;
下一个示例在单个 WITH 子句中使用两个公用表表达式。下表记录了一个家谱：
CREATE TABLE family( name TEXT PRIMARY KEY, mom TEXT REFERENCES family, dad TEXT REFERENCES family, born DATETIME, died DATETIME, -- NULL if still alive -- other content );
“family”表类似于早期的“org”表，只是现在每个成员都有两个父母。我们想知道爱丽丝所有在世的祖先，从最年长的到最年轻的。首先定义一个普通的公用表表达式“parent_of”。那个普通的 CTE 是一个视图，可以用来找到任何个人的所有父母。然后在“ancestor_of_alice”递归 CTE 中使用该普通 CTE。然后在最终查询中使用递归 CTE：
WITH RECURSIVE
parent_of(name, parent) AS
(SELECT name, mom FROM family UNION SELECT name, dad FROM family),
ancestor_of_alice(name) AS
(SELECT parent FROM parent_of WHERE name='Alice'
UNION ALL
SELECT parent FROM parent_of JOIN ancestor_of_alice USING(name))
SELECT family.name FROM ancestor_of_alice, family
WHERE ancestor_of_alice.name=family.name
AND died IS NULL
ORDER BY born;
3.3. 针对图表的查询
假设您有一个无向图，其中每个节点都由一个整数标识，边由如下表定义：
CREATE TABLE edge(aa INT, bb INT); CREATE INDEX edge_aa ON edge(aa); CREATE INDEX edge_bb ON edge(bb);
索引不是必需的，但它们确实有助于大型图形的性能。要查找图中连接到节点 59 的所有节点，请使用类似于以下内容的查询：
WITH RECURSIVE nodes(x) AS ( SELECT 59 UNION SELECT aa FROM edge JOIN nodes ON bb=x UNION SELECT bb FROM edge JOIN nodes ON aa=x ) SELECT x FROM nodes;
本例中的初始选择是简单查询“SELECT 59”。这建立了基本情况。递归选择由 其他两个 SELECT 语句组成。第一个递归 SELECT 沿着 bb-to-aa 方向的边缘，第二个递归 SELECT 沿着 aa-to-bb 方向的边缘。如果图形包含循环，则使用 UNION 代替 UNION ALL 以防止递归进入无限循环。
下面是一个针对有向图使用图查询的真实示例：版本控制系统 (VCS) 通常会将项目的不断发展的版本存储为有向无环图 (DAG)。将项目的每个版本称为“签入”。一次签入可以有零个或多个父母。大多数签入（第一个除外）只有一个父级，但在合并的情况下，一个签入可能有两个或三个或更多父级。跟踪签入及其发生顺序的模式可能如下所示：
CREATE TABLE checkin( id INTEGER PRIMARY KEY, mtime INTEGER -- timestamp when this checkin occurred ); CREATE TABLE derivedfrom( xfrom INTEGER NOT NULL REFERENCES checkin, -- parent checkin xto INTEGER NOT NULL REFERENCES checkin, -- derived checkin PRIMARY KEY(xfrom,xto) ); CREATE INDEX derivedfrom_back ON derivedfrom(xto,xfrom);
该图是非循环的。并且我们假设每个子checkin的mtime不小于其所有parents的mtime。但与前面的示例不同，此图在任意两次签入之间可能具有多条不同长度的路径。
我们想及时知道二十个最近的祖先（在整个 DAG 的成千上万个祖先中）以签入“@BASELINE”。（Fossil VCS 使用与此类似的查询来显示签入的 N 个最近的祖先。例如： http ://www.sqlite.org/src/timeline?p=trunk&n=30 。）
WITH RECURSIVE
ancestor(id,mtime) AS (
SELECT id, mtime FROM checkin WHERE id=@BASELINE
UNION
SELECT derivedfrom.xfrom, checkin.mtime
FROM ancestor, derivedfrom, checkin
WHERE ancestor.id=derivedfrom.xto
AND checkin.id=derivedfrom.xfrom
ORDER BY checkin.mtime DESC
LIMIT 20
)
SELECT * FROM checkin JOIN ancestor USING(id);
递归选择中的“ORDER BY checkin.mtime DESC”术语通过防止查询跟随很久以前合并签入的分支，使查询运行得更快。ORDER BY 强制递归选择关注最近的签到，也就是我们想要的。如果递归选择上没有 ORDER BY，人们将被迫计算数千个祖先的完整集合，按时间对它们进行排序，然后取前 20 个。ORDER BY 实质上设置了一个优先级队列，强制递归查询首先查看最近的祖先，允许使用 LIMIT 子句将查询范围限制为仅感兴趣的签入。
3.4. 使用 ORDER BY 控制树的深度优先与广度优先搜索
递归选择上的 ORDER BY 子句可用于控制树的搜索是深度优先还是广度优先。为了说明，我们将使用上面示例中“org”表的变体，没有“height”列，并插入一些真实数据：
CREATE TABLE org(
name TEXT PRIMARY KEY,
boss TEXT REFERENCES org
) WITHOUT ROWID;
INSERT INTO org VALUES('Alice',NULL);
INSERT INTO org VALUES('Bob','Alice');
INSERT INTO org VALUES('Cindy','Alice');
INSERT INTO org VALUES('Dave','Bob');
INSERT INTO org VALUES('Emma','Bob');
INSERT INTO org VALUES('Fred','Cindy');
INSERT INTO org VALUES('Gail','Cindy');
这是一个以广度优先模式显示树结构的查询：
WITH RECURSIVE
under_alice(name,level) AS (
VALUES('Alice',0)
UNION ALL
SELECT org.name, under_alice.level+1
FROM org JOIN under_alice ON org.boss=under_alice.name
ORDER BY 2
)
SELECT substr('..........',1,level*3) || name FROM under_alice;
“ORDER BY 2”（与“ORDER BY under_alice.level+1”的含义相同）导致组织结构图中的较高级别（“级别”值较小）首先被处理，从而导致广度优先搜索。输出是：
Alice ...Bob ...Cindy ......Dave ......Emma ......Fred ......Gail
但是，如果我们更改 ORDER BY 子句以添加“DESC”修饰符，这将导致递归选择首先处理组织中的较低级别（具有较大的“级别”值），从而导致深度优先搜索：
WITH RECURSIVE
under_alice(name,level) AS (
VALUES('Alice',0)
UNION ALL
SELECT org.name, under_alice.level+1
FROM org JOIN under_alice ON org.boss=under_alice.name
ORDER BY 2 DESC
)
SELECT substr('..........',1,level*3) || name FROM under_alice;
这个修改后的查询的输出是：
Alice ...Bob ......Dave ......Emma ...Cindy ......Fred ......Gail
当递归选择中省略 ORDER BY 子句时，队列表现为 FIFO，这会导致广度优先搜索。
3.5. 古怪的递归查询示例
以下查询计算 Mandelbrot 集的近似值并将结果输出为 ASCII-art：
WITH RECURSIVE
xaxis(x) AS (VALUES(-2.0) UNION ALL SELECT x+0.05 FROM xaxis WHERE x<1.2),
yaxis(y) AS (VALUES(-1.0) UNION ALL SELECT y+0.1 FROM yaxis WHERE y<1.0),
m(iter, cx, cy, x, y) AS (
SELECT 0, x, y, 0.0, 0.0 FROM xaxis, yaxis
UNION ALL
SELECT iter+1, cx, cy, x*x-y*y + cx, 2.0*x*y + cy FROM m
WHERE (x*x + y*y) < 4.0 AND iter<28
),
m2(iter, cx, cy) AS (
SELECT max(iter), cx, cy FROM m GROUP BY cx, cy
),
a(t) AS (
SELECT group_concat( substr(' .+*#', 1+min(iter/7,4), 1), '')
FROM m2 GROUP BY cy
)
SELECT group_concat(rtrim(t),x'0a') FROM a;
在此查询中，“xaxis”和“yaxis”CTE 定义点的网格，Mandelbrot 集将为其近似。“m(iter,cx,cy,x,y)”CTE 中的每一行表示在“iter”次迭代之后，从 cx,cy 开始的 Mandelbrot 迭代已经到达点 x,y。此示例中的迭代次数限制为 28（这严重限制了计算的分辨率，但对于低分辨率的 ASCII 艺术输出来说已经足够了）。“m2(iter,cx,cy)”CTE 保存从点 cx,cy 开始时达到的最大迭代次数。最后，“a(t)”CTE 中的每一行都包含一个字符串，它是输出 ASCII-art 的一行。最后的 SELECT 语句只是查询“a”CTE 以检索所有 ASCII-art 行，一个接一个。
在 SQLite命令行 shell中运行上面的查询会产生以下输出：
....#
..#*..
..+####+.
.......+####.... +
..##+*##########+.++++
.+.##################+.
.............+###################+.+
..++..#.....*#####################+.
...+#######++#######################.
....+*################################.
#############################################...
....+*################################.
...+#######++#######################.
..++..#.....*#####################+.
.............+###################+.+
.+.##################+.
..##+*##########+.++++
.......+####.... +
..+####+.
..#*..
....#
+.
下一个查询解决了数独难题。拼图的状态由一个 81 个字符的字符串定义，该字符串是通过从左到右然后从上到下逐行读取拼图框中的条目而形成的。拼图中的空白方块用“.”表示。特点。因此输入字符串：
53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28。 ...419..5....8..79
对应这样一个谜题：
5 3 7 6 1 9 5 9 8 6 8 6 3 4 8 3 1 7 2 6 6 2 8 4 1 9 5 8 7 9
这是解决难题的查询：
WITH RECURSIVE
input(sud) AS (
VALUES('53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79')
),
digits(z, lp) AS (
VALUES('1', 1)
UNION ALL SELECT
CAST(lp+1 AS TEXT), lp+1 FROM digits WHERE lp<9
),
x(s, ind) AS (
SELECT sud, instr(sud, '.') FROM input
UNION ALL
SELECT
substr(s, 1, ind-1) || z || substr(s, ind+1),
instr( substr(s, 1, ind-1) || z || substr(s, ind+1), '.' )
FROM x, digits AS z
WHERE ind>0
AND NOT EXISTS (
SELECT 1
FROM digits AS lp
WHERE z.z = substr(s, ((ind-1)/9)*9 + lp, 1)
OR z.z = substr(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)
OR z.z = substr(s, (((ind-1)/3) % 3) * 3
+ ((ind-1)/27) * 27 + lp
+ ((lp-1) / 3) * 6, 1)
)
)
SELECT s FROM x WHERE ind=0;
“输入”CTE 定义输入拼图。“digits”CTE 定义了一个表，其中包含 1 到 9 之间的所有数字。解决难题的工作由“x”CTE 承担。x(s,ind) 中的条目表示 81 个字符的字符串“s”是一个有效的数独谜题（它没有冲突）并且第一个未知字符位于位置“ind”，或者如果所有字符都为 ind==0填充字符位置。然后，目标是计算“ind”为 0 的“x”的条目。
求解器通过向“x”递归表添加新条目来工作。给定先前的条目，递归选择尝试用 1 到 9 之间的所有值填充一个新位置，这些值实际上在该位置有效。复杂的“NOT EXISTS”子查询是判断每个候选“s”字符串是否是有效数独游戏的魔法。
通过查找 ind==0 的字符串找到最终答案。如果原始数独问题没有唯一解，则查询将返回所有可能的解。如果原始问题无法解决，则不会返回任何行。在这种情况下，唯一的答案是：
534678912672195348198342567859761423426853791713924856961537284287419635345286179
该解决方案是在现代工作站上用不到 300 毫秒的时间计算出来的。
4.物化提示
公用表表达式的“AS MATERIALIZED”和“AS NOT MATERIALIZED”形式是从 PostgreSQL 复制的非标准 SQL 语法。在 AS 关键字后使用 MATERIALIZED 或 NOT MATERIALIZED 向查询规划器提供关于 CTE 应如何实现的非绑定提示。
如果使用了 MATERIALIZED 短语，则可能会评估select-stmt以生成保存在内存或临时磁盘文件中的临时表，以便在该表名出现在后续 SQL 中时用于代替 CTE 表名。由于立即评估 select-stmt，因此失去了应用查询扁平化或下推优化等优化的机会。（CTE 然后充当“优化栅栏”。）
如果使用 NOT MATERIALIZED 短语，则select-stmt 将作为子查询替换 CTE 表名的每次出现。然后将扁平化和 下推等优化应用于子查询，就像直接使用子查询一样。不管其名称如何，NOT MATERIALIZED 短语并不禁止使用物化。如果查询规划器认为这是最好的解决方案，它仍然可以自由地使用物化来实现子查询。NOT MATERIALIZED 的真正含义更接近“TREAT LIKE ANY ORDINARY VIEW OR SUBQUERY”。
如果两个提示都不存在，则 SQLite 3.35.0 (2021-03-12) 和更高版本处理 CTE，如果多次使用 CTE，就好像存在 MATERIALIZED 短语，或者如果CTE 仅使用一次。在 SQLite 3.35.0 之前，所有 CTE 都被视为存在 NOT MATERIALIZED 短语。根据使用次数决定将特定 CTE 视为具体化还是未具体化是一种启发式方法，如果我们想出更好的查询计划策略，它可能会在未来的版本中发生变化。区别纯粹是性能问题。应以任何一种方式计算等效答案。
应用程序不应该依赖于此提示的语义效果关于调用用户定义函数的时间或频率。查询规划器的未来版本可能会忽略此提示。
MATERIALIZED 和 NOT MATERIALIZED 提示仅在 SQLite 3.35.0 (2021-03-12) 及更高版本中可用。
5.限制和注意事项
WITH 子句不能在CREATE TRIGGER中使用。
WITH 子句必须出现在顶级SELECT语句的开头或子查询的开头。WITH 子句不能放在复合选择的第二个或后续 SELECT 语句之前。
SQL:1999 规范要求 RECURSIVE 关键字在任何包含递归公用表表达式的 WITH 子句中跟在 WITH 之后。但是，为了与 SqlServer 和 Oracle 兼容，SQLite 不强制执行此规则。