现代SQL语法可以翻译成关系代数树吗？

Question

我有一个抽象语法树形式的 SQL 查询的解析表示。 我想将其转换为中间逻辑树表示，然后优化器可以将其扩展为候选物理操作树。

根据讨论该主题的各种资源（CMU 讲座、数据库管理系统、Dayal 1987 年关于嵌套子查询的论文），我设法将大部分查询转换为中间代数形式（例如

π_a(R⋈S)

），但我陷入翻译通用表表达式和横向连接。

• 我无法找到一种方法将 CTE 包含在代数树中而不内联对它们的所有引用。在沿着代数树运行时，优化器会遇到相同的扩展 CTE，这似乎效率低下。
• 根据定义，横向连接中的子查询可以引用前面的 FROM 项提供的列。当使用关系代数树表示时，子查询之前的 FROM 项是父节点，但连接节点只能引用子节点输出的列。例如：

SELECT *
FROM
  (SELECT 1 id) A,
  (
    (SELECT 2) B
    JOIN LATERAL (SELECT A.id) C ON TRUE
  ) D;

    NAT. JOIN
        ├── A
        └── LATERAL JOIN (D)
            ├── B
            └── C <- should be able to reference A

这些约束可以用“代数运算”来表达吗？或者它们通常需要定制的数据结构吗？例如，CTE 的单独子树而不是整个逻辑计划的单个树 - 但是，优化器如何全局优化查询而不是单独优化每个子树？ 更一般地说，为了查询优化的目的，是否有比代数树更好的中间表示？

Answer 1

例如：

有向无环图：DAG中的每个节点代表一个操作，边代表数据流。这允许操作之间存在更复杂的关系，例如引用前面的 FROM 项中的列的横向联接。

• 带注释的关系运算符树：使用注释或元数据增强关系运算符树可以帮助捕获优化所需的其他信息，例如横向连接、绑定的上下文或 CTE 的存在。
关于内联 CTE 与使用子树：正如您正确指出的那样，将 CTE 内联到代数树中可能会导致冗余和低效率。然而，在某些情况下，内联可能是最简单的优化方法。对于更复杂的查询或跨多个查询的优化，维护 CTE 的单独表示可能会有所帮助。这可能涉及单独存储 CTE 并根据需要在主查询计划中引用它们。

为了进一步阅读该主题，除了您已经提到的来源之外，我还推荐 Chamberlin, D.D. 等人所著的《System R: Relational Approach to Database Management》。其中讨论了 System R 项目及其内部结构，以及 Graefe, G 的“Volcano：可扩展并行查询评估系统”。