代数

原文链接：https://calcite.apache.org/docs/algebra.html

关系代数是 Calcite 的核心。每个查询都可以表示为一个 关系运算符树。你可以将 SQL 转换为关系代数，也可以直接构建关系运算符树。

优化器规则使用保持 相同语义 的 数学恒等式 来变换表达式树。例如，如果过滤器没有引用其他输入中的列，那么将过滤器推入到内部关联的输入则是有效的。

Calcite 通过反复地将优化器规则应用于关系表达式来优化查询。成本模型指导该过程，优化器引擎生成与原始语义相同，但成本较低的替代表达式。

优化过程是可扩展的。你可以添加自己的 关系运算符、优化器规则、成本模型 和 统计信息。

代数构建器

构建关系表达式的最简单方法是使用代数构建器 RelBuilder。下面是一个例子：

表扫描

1
2
3
4

final FrameworkConfig config;
final RelBuilder builder = RelBuilder.create(config);
final RelNode node = builder.scan("EMP").build();
System.out.println(RelOptUtil.toString(node));

你可以在 RelBuilderExample.java 中找到这个例子和其他例子的完整代码。这段代码打印如下：

1

LogicalTableScan(table=[[scott, EMP]])

它创建了对 EMP 表的扫描，相当于如下 SQL：

1

SELECT * FROM scott.EMP;

添加投影

现在，让我们添加一个投影，相当于如下 SQL：

1

SELECT ename, deptno FROM scott.EMP;

我们只需要在调用 build 方法前，添加一个 project 方法调用：

1
2

final RelNode node = builder.scan("EMP").project(builder.field("DEPTNO"), builder.field("ENAME")).build();
System.out.println(RelOptUtil.toString(node));

输出结果如下：

1
2

LogicalProject(DEPTNO=[$7], ENAME=[$1])
  LogicalTableScan(table=[[scott, EMP]])

对 builder.field 的两次调用创建了简单表达式，这些表达式从输入的关系表达式中返回字段。那也就是说，scan 方法的调用创建了 TableScan。Calcite 将它们转换为按序号的字段引用，例如：$7 和 $1。

添加过滤和聚合

下面是一个包含聚合和过滤的查询语句：

1
2

final RelNode node = builder.scan("EMP").aggregate(builder.groupKey("DEPTNO"), builder.count(false, "C"), builder.sum(false, "S", builder.field("SAL"))).filter(builder.call(SqlStdOperatorTable.GREATER_THAN, builder.field("C"), builder.literal(10))).build();
System.out.println(RelOptUtil.toString(node));

相当于如下 SQL：

1

SELECT deptno, count(*) AS c, sum(sal) AS s FROM emp GROUP BY deptno HAVING count(*) > 10

并生成如下结果：

1
2
3

LogicalFilter(condition=[>($1, 10)])
  LogicalAggregate(group=[{7}], C=[COUNT()], S=[SUM($5)])
    LogicalTableScan(table=[[scott, EMP]])

压栈和出栈

构建器使用 堆栈 来存储第一步生成的关系表达式，并将它作为输入传递给下一步。这允许生成关系表达式的方法生成一个构建器。

在大多数情况下，你只需要使用 build() 这个堆栈方法，用来获取最后一个关系表达式，也就是树的根节点。

有时候堆栈会嵌套得非常深，以至于令人困惑。为了让这些事情清楚明了，你可以从堆栈中去除些表达式。例如，我们正在构建下面这个复杂的连接查询：

1
2
3
4
5

               join
             /      \
        join          join
      /      \      /      \
CUSTOMERS ORDERS LINE_ITEMS PRODUCTS

我们分三个阶段进行构建。先将中间结果存储在 left 和 right 变量中，然后使用 push() 方法，在创建最终的 Join 对象时，将它们放回堆栈中：

1
2
3

final RelNode left = builder.scan("CUSTOMERS").scan("ORDERS").join(JoinRelType.INNER, "ORDER_ID").build();
final RelNode right = builder.scan("LINE_ITEMS").scan("PRODUCTS").join(JoinRelType.INNER, "PRODUCT_ID").build();
final RelNode result = builder.push(left).push(right).join(JoinRelType.INNER, "ORDER_ID").build();

转换约定

默认的 RelBuilder 会创建没有约定的逻辑 RelNode。但你可以通过 adoptConvention() 来进行切换，从而使用不同的约定：

1

final RelNode result = builder.push(input).adoptConvention(EnumerableConvention.INSTANCE).sort(toCollation).build();

在这个案例中，我们在 input RelNode 之上创建了一个 EnumerableSort。

字段名称和序号

你可以通过名称或序号来引用一个字段。

序号是从零开始的。每个运算符保证它输出字段出现的顺序。例如，Project 返回每个标量表达式生成的字段。

运算符的字段名称需要保证是唯一的，但有时这也意味着，名称并不完全符合你的预期。例如，当你对 EMP 和 DEPT 进行关联时，其中一个输出字段会叫做 DEPTNO，而另一个输出字段则会叫做类似 DEPTNO_1 的名称。

一些关系表达式方法让你能够更好地控制字段名称：

• project 允许你使用 alias(expr, fieldName) 来包装表达式。它删除了包装器，但保留了建议的名称（只要它是唯一的）；
• values(String[] fieldNames, Object... values) 接受一个字段名称数组。如果数组中的任何元素为空，构建器将会生成一个唯一的名称；

如果一个表达式投影成输入字段，或投影成输入字段的一个转换，那么它将使用输入字段的名称。

一旦唯一的字段名称完成了分配，这些名称就是不可变的。如果你有一个特定的 RelNode 实例，你可以依赖字段名称的不变性。事实上，整个关系表达式也是不可变的。

但是，如果一个关系表达式已经通过了多个重写规则（参考 RelOptRule），结果表达式的字段名称可能看起来与原始表达式不太一样。这种情况下，最好按照序号来引用字段。

当你正在构建一个接受多个输入的关系表达式时，你需要考虑到那些点，从而构建字段引用。这在构建关联条件时经常出现。

假设你正在 EMP 和 DEPT 上构建一个关联查询，EMP 有 8 个字段 EMPNO、ENAME、JOB、MGR、HIREDATE、SAL、COMM、DEPTNO，DEPT 有 3 个字段 DEPTNO、DNAME、LOC。在内部，Calcite 使用偏移量来表示这些字段，存储在一个包含 11 个字段的组合输入行中：左侧输入的第一个字段是 #0（请记住，序号从 0 开始），右侧输入的第一个字段是 #8。

通过构建器 API，你可以指定哪个输入的哪个字段。要引用内部字段序号是 #5 的 SAL，可以写成 builder.field(2, 0, "SAL")，builder.field(2, "EMP", "SAL") 或 builder.field(2, 0, 5)。这个写法表示，在两个输入中，#0 输入的 #5 字段。为什么它需要知道有两个输入？因为它们存储在堆栈中，#1 输入位于堆栈顶部，#0 输入在其下方。如果我们不告诉构建器是两个输入，它不知道 #0 输入的深度。

类似地，要引用内部字段是 #9 (8 + 1) 的 DNAME，可以写成 builder.field(2, 1, "DNAME")，builder.field(2, "DEPT", "DNAME") 或 builder.field(2, 1, 1)。

递归查询

警告：当前 API 是实验性的，如有变更不会另行通知。

下面是一个递归查询的 SQL，用于生成 1, 2, 3, ...10 这样的序列：

1

WITH RECURSIVE aux(i) AS (VALUES (1) UNION ALL SELECT i + 1 FROM aux WHERE i < 10) SELECT * FROM aux

可以对 TransientTable 和 RepeatUnion 进行表扫描，来生成这个 SQL：

1
2

final RelNode node = builder.values(new String[] {"i"}, 1).transientScan("aux").filter(builder.call(SqlStdOperatorTable.LESS_THAN, builder.field(0), builder.literal(10))).project(builder.call(SqlStdOperatorTable.PLUS, builder.field(0), builder.literal(1))).repeatUnion("aux", true).build();
System.out.println(RelOptUtil.toString(node));

生成结果如下：

1
2
3
4
5
6
7

LogicalRepeatUnion(all=[true])
  LogicalTableSpool(readType=[LAZY], writeType=[LAZY], tableName=[aux])
    LogicalValues(tuples=[[{ 1 }]])
  LogicalTableSpool(readType=[LAZY], writeType=[LAZY], tableName=[aux])
    LogicalProject($f0=[+($0, 1)])
      LogicalFilter(condition=[<($0, 10)])
        LogicalTableScan(table=[[aux]])

接口摘要

关系运算符

以下方法会创建一个关系表达式 RelNode，并将它压入堆栈中，然后返回 RelBuilder。

参数类型：

• expr，interval：RexNode；
• expr...， requiredField...：RexNode 数组；
• exprList，measureList，partitionKeys，orderKeys， requiredFieldList：可迭代的 RexNode；
• fieldOrdinal：行内字段的序号（从 0 开始）；
• fieldName：字段名称，在行内唯一；
• fieldName...：字符串数组；
• fieldNames：可迭代的字符串；
• rowType：RelDataType；
• groupKey：RelBuilder.GroupKey；
• aggCall...：RelBuilder.AggCall 数组；
• aggCallList：可迭代的 RelBuilder.AggCall；
• value...：对象数组；
• value：对象；
• tupleList：可迭代的 RexLiteral 集合；
• all，distinct，strictStart，strictEnd，allRows：布尔值；
• alias：字符串；
• correlationId：CorrelationId；
• variablesSet：可迭代的 CorrelationId；
• varHolder：RexCorrelVariable Holder；
• patterns：键为字符串，值为 RexNode 的 Map；
• subsets：键为字符串，值为字符串有序集合的 Map；
• distribution：RelDistribution；
• collation：RelCollation；
• operator：SqlOperator；
• joinType：JoinRelType；

builder 方法执行了各种优化，具体包括：

• 如果要求按顺序投影所有列，project 则返回它的输入；

• filter 会打平条件表达式，所以，一个 AND 和 OR 可能有 2 个以上的子节点。filter 也会进行简化，例如将 x = 1 AND TRUE 转化为 x = 1；

• 如果你先使用 sort，然后使用 limit 时，效果就像你调用了 sortLimit 一样；

有一些注解方法，可以向堆栈顶部的关系表达式添加信息：

堆栈方法

标量表达式方法

以下方法返回标量表达式 RexNode。许多方法使用堆栈的内容。例如，field("DEPTNO") 返回被添加到堆栈中的关系表达式的 DEPTNO 字段的引用。

模式方法

以下方法会返回用于 match 中的模式。

分组键方法

以下方法会返回一个 RelBuilder.GroupKey。

聚合调用方法

以下方法会返回一个 RelBuilder.AggCall。

如果想要进一步地修改 AggCall，可以调用如下方法：

窗口聚合调用方法

为了创建一个 RelBuilder.OverCall（它代表对窗口聚合函数的调用）， 需要先创建一个聚合调用，然后调用它的 over() 方法，例如：count().over()。

如果想要进一步地修改 OverCall，可以调用如下方法：

笔者因为工作原因接触到 Calcite，前期学习过程中，深感 Calcite 学习资料之匮乏，因此创建了 Calcite 从入门到精通知识星球，希望能够将学习过程中的资料和经验沉淀下来，为更多想要学习 Calcite 的朋友提供一些帮助。