CTEReadme

使用方法

定义

WITH 子句允许定义在一个相同的 SELECT 语句中有效的表表达式。表表达式被称为“通用表表达式”（CTE）。CTE 的用例与 VIEW 类似，但它比 VIEW 更方便。与 VIEW 不同，您无需事先定义 CTE。

示例

CTE 允许使用递归查询。若要使用递归查询，您需要添加 RECURSIVE 关键字。以下是WITH RECURSIVE子句用法的一个示例。表“部门”以邻接列表的形式表示一个组织的结构。

CREATE TABLE department (
    id INTEGER PRIMARY KEY,  -- department ID
    parent_department INTEGER REFERENCES department, -- upper department ID
    name TEXT -- department name
);

INSERT INTO department (id, parent_department, "name")
VALUES
     (0, NULL, 'ROOT'),
     (1, 0, 'A'),
     (2, 1, 'B'),
     (3, 2, 'C'),
     (4, 2, 'D'),
     (5, 0, 'E'),
     (6, 4, 'F'),
     (7, 5, 'G');

-- department structure represented here is as follows:
--
-- ROOT-+->A-+->B-+->C
--      |         |
--      |         +->D-+->F
--      +->E-+->G

若要提取 A 下的所有部门，您可以使用以下递归查询

WITH RECURSIVE subdepartment AS
(
    -- non-recursive term
    SELECT * FROM department WHERE name = 'A'

    UNION ALL

    -- recursive term
    SELECT d.*
    FROM
        department AS d
    JOIN
        subdepartment AS sd
        ON (d.parent_department = sd.id)
)
SELECT *
FROM subdepartment
ORDER BY name;

递归工作原理

上述查询的含义可以解释如下。

给定三个表，中间表（IntermediateTable）；工作表（WorkTable）；结果表（ResultTable）。

1) 初始化

执行非递归词（SELECT * FROM department WHERE name = 'A'）并将结果分配给 ResultTable 和 WorkTable。

ResultTable = WorkTable = ('A')

使 IntermediateTable 为空。

IntermediateTable = ()

2) 执行递归查询

用 WorkTable 替换子部门，并执行递归词

SELECT d.*
FROM
    department AS d
JOIN
    WT AS sd
    ON d.parent_department = sd.id

接下来，将查询的结果分配给 IntermediateTable。将 IntermediateTable 添加到 ResultTable，并将 IntermediateTable 替换为 WorkTable。使 IntermediateTable 为空。

3) 检查递归是否结束

如果 IntermediateTable 在 2) 中为空，则递归执行结束。返回 ResultTable。

否则，转到 2)。

“subdepartment” 是一款 CTE，其中包含递归表达式，因为它在其定义中引用自身。在上面的查询中，首先，评估非递归项。然后评估递归项并将结果不断添加到前一个结果集中，直到没有更多要处理的数据。最后，执行最后一个 SELECT，并且从结果集中提取数据。

实施

分析递归查询

要表示 CTE，将新结构成员“withClause”添加到 SelectStmt 结构，用于存储 SELECT 语句的已分析信息。 withClause 的定义如下：

/*
 * WithClause -
 *     reprensentation of WITH clause
 */
typedef struct WithClause
{
    NodeTag      type;            /* T_WithClause */
    List        *subquery;        /* subquery list (list of RangeSubselect) */
    bool         recursive;       /* true = WITH RECURSIVE */
} WithClause;

如果未给出 RECURSIVE 关键字，则 CTE 将转换为 WithClause.subquery，并将 WithClause.recursive 设置为 false。

如果给出了 RECURSIVE 关键字，则存储在 WithClause.subquery 中的原始分析树表示子查询，该子查询是 UNION ALL 的非递归项和递归项。不允许在非递归项和递归项之间使用 UNION ALL 以外的其他集合操作。 WithClause.subquery.subquery.larg 表示“SELECT * FROM department WHERE name = 'A'”，而 WithClause.subquery.subquery.rarg 在上面的示例中表示“SELECT d.* FROM department AS d JOIN subdepartment AS sd ON d.parent_department = sd.id”。

分析递归查询

要分析 CTE，我们将以下新成员“p_ctenamespace”、“p_recursive_namespace”和“p_in_with_clause”添加到 ParseState 结构中。

p_ctenamespace 是非递归 CTE 的命名空间和 RangeSubselects 的列表。以下是 ParseState 的注释摘录：

* [1] Note that p_ctenamespace is a namespace for "relations" but distinct
*     from p_relnamespace. p_ctenamespace is a list of relations that can be
*     referred to in a FROM or JOIN clause (in addition to normal tables and
*     views). p_relnamespace is the list of relations which already have been
*     listed in such clauses and therefore can be referred to in qualified
*     variable references. Also, note that p_ctenamespace is a list of
*     RangeSubselects, not a list of range table entries.

p_recursive_namespace 是递归 CTE 的命名空间，并且是 RangeRecursive 的列表。 RangeRecursive 是新引入的结构

/*
 * RangeRecursive - recursive call appearing in a FROM clause
 */
typedef struct RangeRecursive
{
    NodeTag        type;
    Node       *subquery;        /* the untransformed sub-select clause */
    Alias       *alias;            /* table alias & optional column aliases */
    List       *coldeflist;        /* list of ColumnDef nodes to describe result */
    Node        *non_recursive_term;    /* analyze result of non recusive term */
    bool        recursive;        /* true if recursive query */
} RangeRecursive;

ParseState.p_rtable 是 RangeTblEntry 的列表。为了处理 CTE，将新成员“self_reference”和“non_recursive_query”添加到 RangeTblEntry 中。

/*
 * Fields valid for a RECURSIVE CTE (else NIL)
 */
bool        self_reference; /* delay analyzing SelectStmt */
Query        *non_recursive_query; /* non-recursive term */

如果使用“RECURSIVE”关键字的 CTE 实际上不是递归的，则将“recursive”设置为 false，并将 CTE 视为子查询并将其添加到 ParseState.p_rtable 中。

如果 CTE 引用自身，分析将被延迟，将 self_reference 设置为 true，并将 non_recursive_term 填入。

可能有多个 CTE 元素（查询名称）。

WITH RECURSIVE x AS (SELECT * from y),
               y AS (SELECT * FROM pg_class)
SELECT * FROM x;

在这种情况下，我们应该先分析 y，因为 x 依赖于 y。要查找此类依赖项信息，请执行拓扑排序。有关更多详细信息，请参阅 makeDependencyGraph()。

接下来，我们检查递归查询是否遵循 SQL 标准。标准不允许以下示例查询。

- 非递归项和递归项必须与 UNION ALL 一起使用

WITH RECURSIVE x(n) AS (SELECT 1 UNION SELECT n+1 FROM x)
    SELECT * FROM x;

WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT SELECT n+1 FROM x)
    SELECT * FROM x;

- 非递归项不存在

WITH RECURSIVE x(n) AS (SELECT n FROM x)
    SELECT * FROM x;

- 递归项必须位于左侧

WITH RECURSIVE x(n) AS (SELECT n FROM x UNION ALL SELECT 1)
    SELECT * FROM x;

- 不允许 LEFT JOIN 位于递归项的右侧

 WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1
    UNION ALL
    SELECT x.n+1 FROM y LEFT JOIN x ON x.n = y.a WHERE n < 10)
SELECT * FROM x;

- 不允许 RIGHT JOIN 位于递归项的左侧

WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1    
    UNION ALL
    SELECT x.n+1 FROM x RIGHT JOIN y ON x.n = y.a WHERE n < 10)
SELECT * FROM x;

‐ 在递归术语中不允许 FULL JOIN

WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1
    UNION ALL
    SELECT x.n+1 FROM x FULL JOIN y ON x.n = y.a WHERE n < 10)
SELECT * FROM x;

‐ WHERE 子句具有在递归术语中使用递归名称的子查询

 term not allowed
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x
                          WHERE n IN (SELECT * FROM x))
  SELECT * FROM x;

‐ 在递归术语中不允许 GROUP BY、HAVING

WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x GROUP BY n)
  SELECT * FROM x;

‐ 在递归术语中不允许聚合函数

WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT count(*) FROM x)
  SELECT * FROM x;

除上述限制外，我们还增加了更多限制

‐ 在递归查询中不允许 ORDER BY

WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x ORDER BY 1)
  SELECT * FROM x;

‐ 在递归查询中不允许 LIMIT OFFSET

WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x LIMIT 10 OFFSET 1)
  SELECT * FROM x;

‐ 在递归查询中不允许 FOR UPDATE

WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x FOR UPDATE)
  SELECT * FROM x;

‐ 在递归术语中不允许带有使用递归名称的子查询的目标列表

WITH RECURSIVE x(id) AS (values (1)
    UNION ALL
    SELECT (SELECT * FROM x) FROM x WHERE id < 5
) SELECT * FROM x;

‐ 不支持相互递归调用

WITH RECURSIVE
  x (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM y WHERE id < 5),
  y (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 5)
SELECT * FROM x;

请注意，SQL Server 和 Firebird 也不允许相互递归查询。Oracle 不支持 WITH RECURSIVE，但有自己的 CONNECT BY 语法。

在 WITH RECURSIVE 子句中定义的表被识别为解析树节点中 RangeTblEntry 中 RTEKind 之外的 RTE_RECURSIVE。将结构类型为 RangeRecursive 的名称空间 “p_recursive_namespace” 添加到 ParseState 结构中。

typedef struct RangeRecursive
{
    NodeTag        type;
    Node       *subquery; /* whole subquery */
    Alias      *alias;            /* table alias & optional column aliases */
    List       *coldeflist;        /* list of ColumnDef nodes */
    Node       *non_recursive_term; /* analyze result of non recursive term */
    bool       recursive; /* true if recursive */
} RangeRecursive;

non_recursive_term 保留对非递归术语进行分析的结果。使用这个推断出递归查询的类型。

改写器

应用于改写器的更改很小。fireRIRrules() 递归展开子查询。如果是递归查询，我们只需做同样的事情。

生成计划

添加了新计划节点“递归”和“递归扫描”。递归计划是用于执行 WITH RECURSIVE 查询的顶级计划。在下面的示例中，Recursion 计划表示“SELECT * FROM subdepartment”部分的执行计划。递归计划始终具有“追加”子计划，该子计划表示非递归部分和递归部分的“UNION ALL”的执行计划。非递归部分的计划没有什么特别之处，并且是根据非递归查询部分生成的普通计划。递归扫描表示递归部分的计划。

以下是 EXPLAIN 输出的示例。

EXPLAIN WITH RECURSIVE subdepartment AS
(
    -- non recursive term
    SELECT * FROM department WHERE name = 'A'

    UNION ALL

    -- recursive term
    SELECT d.* FROM department AS d, subdepartment AS sd
        WHERE d.parent_department = sd.id
)
SELECT * FROM subdepartment;

                                    QUERY PLAN                                     
-----------------------------------------------------------------------------------
 Recursion on subdepartment  (cost=0.00..50.76 rows=12 width=40)
   ->  Append  (cost=0.00..50.64 rows=12 width=40)
         ->  Seq Scan on department  (cost=0.00..24.50 rows=6 width=40)
               Filter: (name = 'A'::text)
         ->  Hash Join  (cost=0.01..26.02 rows=6 width=40)
               Hash Cond: (d.parent_department = sd.id)
               ->  Seq Scan on department d  (cost=0.00..21.60 rows=1160 width=40)
               ->  Hash  (cost=0.00..0.00 rows=1 width=4)
                     ->  Recursive Scan on sd  (cost=0.00..0.00 rows=1 width=4)

表示递归计划的结构如下

typedef struct Recursion
{
    Scan    scan;
    Plan    *subplan;
    List    *subrtable;        /* temporary workspace for planner */
} Recursion;

表示 RecursiveScan 计划的结构如下

typedef struct RecursiveScan
{
    Scan        scan;
} RecursiveScan;

执行器

为了执行有关 CTE 的计划，我们添加了新成员“es_tuplestorestate”、“es_rscan_tupledesc”和“es_disallow_tuplestore”。es_tuplestorestate 用于记忆工作表 (WT) 的 TupleStoreState。es_rscan_tupledesc 用于记忆 CTE 返回的数据类型的类型信息。实际上未使用 es_disallow_tuplestore。

为了管理递归查询执行状态，添加了以下结构。

typedef struct RecursionState
{
    ScanState    ss;
    PlanState  *subplan;        /* plan for non recursive query */
    bool recursive_empty; /* if recursive term does exist, true */
    Tuplestorestate *intermediate_tuplestorestate; /* intermediate table (IT) */
    Tuplestorestate *working_table;        /* working table (WT) */
    bool init_done; /* initialization flag */
} RecursionState;

typedef struct RecursiveScanState
{
    ScanState    ss;
    TupleDesc    tupdesc;
    Tuplestorestate **working_table;    /* working table */
} RecursiveScanState;

初始化递归计划

这是由 ExecInitRecursion() 完成的。将创建工作表 (WT) 并将其指针存储在 RecursionState.working_table 中。将创建中间表 (IT) 并将其指针存储在 RecursionState.intermediate_tuplestorestate 中。

在初始化中，必须使用上面创建的 WT，并将指向 WT 的指针存储在主执行器状态 (Estate) 中的 es_tuplestorestate 中。

扫描类型信息取自非递归查询（保存于 RecursionState.subquery）并存储在 RecursionState.ss 和 Estate/es_rscan_tupledesc 中。

执行递归计划

递归计划由 ExecRecursion() 执行。主力是 RecursionNext()。首先执行非递归术语的计划，并将结果存储在 WT 中。然后执行递归术语的计划，该术语是递归计划的子计划。如果计划返回一行或多行，则将它们存储在 IT 中。交换 IT 和 WT 然后重新创建 IT。如果没有返回行，则结束递归且 ExecRecursion() 返回 NULL。

初始化 RecursiveScan 计划

这与 RecursiveScan 的初始化非常相似，但扫描类型信息取自 ExecInitRecursion() 初始化的 Estate.es_rscan_tupledesc。

执行 RecursiveScan 计划

Recursive 扫描由 ExecRecursiveScan() 执行。主力是 RecursivescanNext()。它只返回存储在 WT 中的元组。工作表存储在 Estate 结构中。

执行器中的其他更改

哈希连接计划并不总是在哈希连接结束前重新创建哈希。如果哈希连接的子计划是 RecursiveScan，则需要重新创建哈希。为了解决此问题，PlanState 结构添加了“has_recursivescan”，当上层计划的子计划是 RecursiveScan 时置为 true，并且重新创建哈希。
处理递归时执行 exec_append_initialize_next()。该函数现为全局函数。

限制

SEARCH 和 CYCLE 子句尚未实现。
不允许相互递归。
只有 UNION ALL 的最后一个 SELECT 可以包含递归名称。
递归和 RecursiveScan 计划的开销始终为 0。

CTE 的更多乐趣

人们越来越多地将 CTE 用于 SQL 表达式。已启动 CTE 奖金页面来鼓励人们使用它。还有一些依赖它们的代码片段

CTEReadme

内容

使用方法

定义

示例

递归工作原理

实施

分析递归查询

分析递归查询

改写器

生成计划

执行器

初始化递归计划

执行递归计划

初始化 RecursiveScan 计划

执行 RecursiveScan 计划

执行器中的其他更改

限制

CTE 的更多乐趣

导航菜单

页面操作

页面操作

个人工具

导航

工具

搜索