当我谈查询优化器时，我谈些什么 (1)—

作者：雷宇

Databend 优化器担任人

github.com/leiysky

这几天和迟先生 (github@skyzh) 聊地利偶尔聊到他最近在 CMU 做的 optd 项目（一个依据 Cascades 结构规划的查询优化器库），一同吐槽了各种数据库优化器的规划与完成。这时我突然意识到有些技术上的东西聊起来仍是挺有意思的，值得记录下来。

因而我决定开个坑，聊聊查询优化器相关的一切——从算法基础到工程实践，从技术演进到项目落地，乃至是一些行业八卦。

今日先将“IR 规划”相关的内容作为开篇，聊一聊优化器中常见的规划方法，而且评论其间的规划考量。

什么是查询优化器

在正式开端聊之前，我想先明确一下查询优化器的界说。

在一般语境中，查询优化器特指对查询的履行方案进行优化的一个数据库组件。可是由于各个数据库完成上的不同，查询的优化方法也变得形形色色，比方在 AST 上直接进行 Rewriting，在 AST Lowering 的时分做些转化，在查询履行的时分进行动态的 Rewriting 等等。

为了统一概念，我将从 SQL 解析器 (Parser) 到履行器 (Executor) 之间的一切部分统称为查询优化器 (Query Optimizer)。

什么是 IR

了解编译技术的朋友的应该很了解 IR 这个词。IR 全称为中心言语 (Intermediate Representation) ，常见于各种编程言语的编译器中，比方 Rust 的 HIR & MIR，LLVM 中的 LLVM IR。IR 被用于结构化表明编程言语，便利编译器进行各种剖析与优化。

假设将 SQL 也看成一种编程言语的话，联系型数据库便是运转 SQL 程序的虚拟机，正如 JVM 之于 Java。而查询优化器在其间担任的便是绝大多数的编译工作，将 SQL 句子 (Java code) 翻译成履行方案 (Java bytecode) 交给履行器 (Java runtime) 履行。因而在规划查询优化器时也离不开规划 SQL 的各种 IR。

SQL IR 都长啥样

一般的数据库项目会分为几个模块：解析器 (Parser) ，剖析器 (Analyzer/Binder) ，优化器 (Optimizer) ，履行器 (Executor)。SQL 句子会依次经由各组件的处理，最终转化成查询成果。在咱们的语境里，优化器包括了上面提到的剖析器和优化器两个模块。

SQL 自身是一种模仿天然言语语法规划的声明式言语，依据联系代数，能够描绘调集上的各种运算，并将其映射为对表格数据 (Table) 的查询。

AST

为了便利处理，咱们会像绝大多数编译器那样，首先将 SQL 言语解析为 AST（笼统语法树，即 Abstract Syntax Tree）。一个 SQL AST 一般如下图所示：

在 SQL AST 中，咱们一般将 node 分为两种：Statement(Stmt) 和 Expression(Expr)。每个 SQL AST 的 root node 总是一个 Statement，其间可能包括一些子句 (Clause) 以及 Expression。Expression 是一种递归的结构，其间包括了各种运算符和函数调用，乃至还有嵌套的 Statement (Subqueries)。

在 SQL 中比较有意思的一点是，关于 SELECT Statement 来说 Statement 与 Expression 的边界会比较含糊。由于 SELECT Statement 自身也是递归的，乃至还需求处理运算符优先级的问题 (UNION/EXCEPT/INTERSECT)。与此一起，在 Statement 中也仅有 SELECT Statement 能够与 Expression 相互递归，因而在规划 SQL AST 时需求注意这点。

联系代数

SQL 言语的理论基础是联系代数，每一条查询句子都有对应的联系代数表明，比方：

由于联系代数的表达式也是一个递归的树状结构，因而许多体系也很天然地将 SQL AST 转化成了相似下图的履行方案，咱们将每个 node 称作算子 (Operator)，将整个算子树成为查询方案 (Query plan)。

当然许多体系中也有异类，比方身为祖师爷的 IBM 在 Starburst 体系中引进了 Query Graph Model 这种表明方法。这种表明方法适当的笼统，将许多 property 给 hardcode 在了 QGM 中，导致了解起来异常困难，其宣称的可扩展性也令人置疑。篇幅原因就不在这儿打开解说，有兴趣的话能够去阅览相关论文《Extensible Query Processing in Starburst》以及《Extensible/Rule Based Query Rewrite Optimization in Starburst》。

目前干流的数据库底子都采用了联系代数的表明方法（比方 IBM 的 System R 和 DB2，Oracle 的各种数据库产品，微软的 SQL Server 系列，开源的 PostgreSQL 和 MySQL 8.0），也在此基础上衍生出了丰厚的优化结构和履行结构，因而在规划 SQL IR 时运用联系代数的笼统是一种不会错的选择。

运用联系型代数的各种公理和定理咱们能够对 SQL IR 进行各种转化，在确保正确性的一起达到优化的效果。关于详细的优化规则和算法会在后续的文章中进行评论。

最佳工程实践（待定）

有一种认知偏差叫做“常识的咒骂”，意指在与别人沟通时预设了对方具有与自己同等的常识背景。

在软件开发领域这种现象十分常见。写过某类代码的人和没写过某类代码的人在沟通时总会变成鸡同鸭讲，即使双方现已具有了相同的理论基础（算法，编程言语，乃至是领域常识）仍然无法防止。原因在于软件工程具有适当的灵活性，相同的功用能够有许多种完成方法，而不同的完成方法又会有各自的问题。

为了扫除这种沟通上的妨碍，各种技术领域都会发展出自己的一系列 idiom 或许 design pattern，新的项目依据这些实践构建能够省去许多不必要的费事。数据库领域也是如此，可是由于比较小众，且商业化程度较高，导致坊间撒播的常识十分稀少，工程实践也散落在各种开源项目中。

在这篇文章里我会依据我自己的最佳实践从零构建一套 SQL IR，便利渐进式地共享一些规划考量。

由于个人习惯，我会用 Rust 言语来编写代码。不了解 Rust 言语的朋友也不必担心，只需求有一定的 C/C 基础就能够看懂 Rust 的代码逻辑。

Hello, world!

当咱们学习一门新的编程言语时，第一个触摸的程序一般都是 hello world。

fn main() {
    println!("Hello, world!");
}

因而咱们也先从 SQL 的 hello world 开端构建咱们的 IR。

create table t(a int);
select * from t;

这条 SQL 句子翻译成联系代数十分简略，咱们将其记为 Get(t)，意为回来调集 t 中的一切数据。要表明这样的查询咱们能够界说一个简略的 struct 类型。

pub struct Get {
    pub table: String,
}
fn plan() -> Get {
    // select * from t;
    Get {
        table: "t".to_string(),
    }
}

这样简略的一个 SQL IR 就完成了，有了 Get 之后咱们就能表明一切相似 select * from xxx 的查询了，是不是很简略？

Select & Project

接下来咱们能够为这个 IR 增加更多的功用，支撑更多的 SQL 子句。比方：

create table t(a int, b int);
select a from t where a = 1;

这条 SQL 查询翻译成联系代数能够记为 Project(Select(Get(t), a = 1), a)，Select 算子能够依据供给的谓词对数据进行过滤，Project 算子能够对调集进行裁剪以获得需求的 attribute。为了表明这样的查询咱们需求增加更多的 struct 界说。

pub struct Get {
    pub table: String,
}
pub struct Select {
    pub get: Get,
    pub predicate: String,
}
pub struct Project {
    pub select: Select,
    pub project: String,
}
fn plan() -> Project {
    // select a from t where a = 1;
    Project {
        select: Select {
            get: Get {
                table: "t".to_string(),
            },
            predicate: "a = 1".to_string(),
        },
        project: "a".to_string(),
    }
}

来到这儿咱们就面临了几个问题：依照联系代数的定理，Project 是不是能够作为 Select 的 child？Select 关于一条 SQL 查询来说是可选的，代码上该怎么体现这点？

为了处理这些问题，咱们能够引进一些动态分发的特性。在 C /Java 中一般会运用继承来表明 Opeartor，比方：

class Operator {};
class Get : public Operator {};
class Select : public Operator {
    Operator* _child;
};
class Project : public Operator {
    Operator* _child;
};

在 Rust 中，咱们有一个更便利的选择，能够一起享受静态类型和动态分发的优点，那便是 enum。Rust 的 enum 是一种 ADT(Algebraic Data Type)，也被称作 tagged union，能够十分便利地表明咱们的 operators：

pub enum Operator {
    Get {
        table: String,
    },
    Select {
        child: Box<Self>,
        predicate: String,
    },
    Project {
        child: Box<Self>,
        projects: String,
    },
}
fn plan() -> Operator {
    // select a from t where a = 1;
    Operator::Project {
        child: Box::new(Operator::Select {
            child: Box::new(Operator::Get {
                table: "t".to_string(),
            }),
            predicate: "a = 1".to_string(),
        }),
        project: "a".to_string(),
    }
}

由此一来咱们就能够自在表明各种形状的算子树了，IR 的规划开端步入正轨。

Scalar expression

尽管咱们现已引进了 Select 和 Project 的算子，可是关于 Select predicate 和 Project expression 仍是以字符串的方法存在的，不能满意剖析和优化的需求。因而咱们需求为这些 expression 也规划一种 IR。

回想一下，SQL 字符串在经过 Parser 处理后就被转化成了 AST，而其间的表达式会变成 Expr node，大概长这样：

pub enum Expr {
    ColumnRef(ColumnRef),
    Literal(Literal),
    Function(Function),
    BinaryOp(BinaryOp),
    UnaryOp(UnaryOp),
    Subquery(SelectStmt),
}

expression 自身是一种递归的结构，AST 的 Expr node 也是一种递归结构，咱们是否能够偷懒直接运用 Expr node 作为咱们的 SQL IR 的一部分呢？咱们能够先试试。

运用 Expr 替换 String 后，咱们能够得到：

pub enum Operator {
    Get {
        table: String,
    },
    Select {
        child: Box<Self>,
        predicate: Expr,
    },
    Project {
        child: Box<Self>,
        projects: Vec<Expr>,
    },
}

接下来给定一条 SQL，让咱们来试试常用的一些剖析，看看好不好使：

select a from t
where exists (select * from t1 where t.a = t1.a)

Q: Project 中的 Expr 依靠了哪些 table 的哪些 columns？A: 运用了一个叫做 a 的 column，但我不知道它是哪个 table 的，或许底子就不存在这个 column
Q: Project 中的 Expr 的回来类型是什么？A: 不知道，Expr 中没有包括任何类型信息
Q: Select 中的 subquery 是 correlated subquery 吗？A: 不知道，Expr 中的 subquery 仅仅一个未处理过的 AST

Ok，看起来 Expr 并没有咱们想象中的那么好用。为了进行上面的这些剖析，咱们需求规划一套信息愈加丰厚的 IR。为了与 Expr 进行区别，咱们将其命名为 ScalarExpr。

将以上的剖析归纳一下，咱们对 ScalarExpr 的要求是：

一切的 identifier 都要 resolve 成 fully qualified name
类型信息需求被注入，而且需求经过 type check
一切的 subquery 都要被转化成 SQL IR 的方法

结合以上需求，再加上一些 desugar，ScalarExpr 大概长这样：

pub enum ScalarExpr {
    ColumnRef(Vec<Identifier>, Type),
    Literal(Value, Type),
    Function(Signature, Vec<Self>),
    Subquery(Quantifier, Box<Operator>),
}

如此一来，表达式的 IR 规划也成型了，让咱们把整套 SQL IR 整合起来吧。

The IR

经过以上的规划，咱们具有了：

能够灵活表达各种 SQL 查询的算子树结构 Operator
能够供给丰厚语义信息的 ScalarExpr

尽管还缺少一些要害的算子，比方 Join, Union, Aggregate 等。可是由于全体结构现已十分明晰，咱们能够照葫芦画瓢地把它们也加上。

整合之后咱们就有了一套适当完美的 SQL IR：

pub enum ScalarExpr {
    ColumnRef(Vec<Identifier>, Type),
    Literal(Value, Type),
    Function(Signature, Vec<Self>),
    Subquery(Quantifier, Box<Operator>),
}
pub enum Operator {
    Get {
        table: String,
    },
    Select {
        child: Box<Self>,
        predicate: ScalarExpr,
    },
    Project {
        child: Box<Self>,
        projects: Vec<ScalarExpr>,
    },
    Join {
        kind: JoinKind,
        condition: ScalarExpr,
        left: Box<Self>,
        right: Box<Self>,
    },
    UnionAll {
        left: Box<Self>,
        right: Box<Self>,
    },
    Aggregate {
        group_by: Vec<ScalarExpr>,
        aggr_exprs: Vec<ScalarExpr>,
        child: Box<Self>,
    },
}

由于过于完美，我决定给这个 IR 起个霸气的名字——The IR。

Property derivation

当咱们想要对 IR 进行剖析和优化时，咱们总是需求获取一些 IR 的 property。咱们能够经过编写 analyzer 遍历整个 IR 来核算出这些 property，可是这样需求消耗大量精力保护 IR 所处上下文的状况。

幸运的是 SQL 作为一个声明式的查询言语数据流适当简略，咱们能够运用其特性核算 property。

The IR 中的数据流向和 operator 之间的父子联系紧密相关，全体呈现为一个有向无环图 (DAG)，一切的数据都从子节点流向父节点。

在这种特性下，核算某个 The IR 节点的 property 要做的工作很简略，只需递归核算其每个子节点的 property，再依据这些 property 核算出其自身的 property，咱们称这个进程为 property derivation。

pub struct Property;
fn derive_property(op: &Operator) -> Property {
    // Calculate the properties of the children operators.
    let children_property: Vec<Property> = op
        .children()
        .map(derive_property)
        .collect();
    // Calculate property with the children properties.
    op.calculate_property(&children_property)
}

在 SQL 优化中，常用的 property 能够分为两类，分别是描绘数据集特征的 relational/logical property 和描绘数据物理特征的 physical property。

常见的 relational property 有：

数据会集包括的 attributes/columns 信息
数据集的基数 (cardinality)，表明数据会集的 record 数量
核算信息 (statistics)，表明 attributes 的数据散布
数据束缚 (constraints)，表明 attributes 的束缚，比方 NOT NULL
函数依靠 (functional dependency)，表明 attributes 之间的函数依靠联系

常见的 physical property 有：

有序性 (order)
并行度 (DOP)
数据散布 (distribution)
数据分区 (partition)

结合联系代数的性质，咱们能够描绘 property 种类之间的区别。

假设有联系 $R$ 和 $S$ ： $R$ 的 relational property 为 $RP_R$ ，physical property 为 $PP_R$ ； $S$ 的 relational property 为 $RP_S$ ，physical property 为 $PP_S$ 。

咱们能够得到：

$RP_R = RP_S$

不难看出两个 relation 的等价联系能够决定 relational property 的等价联系，可是 physical property 的等价联系却不受 relation 的等价联系影响。

关于 property 与详细的查询优化算法结合的内容将在后续的文章里打开评论。

有了 property derivation 之后，咱们就能运用联系代数的定理在确保正确性的情况下对 The IR 进行优化了。

那么接下来的问题便是，property 该长啥样？

Relational properties

在 relational property 中最重要的部分莫过于 attributes 的表明方法。朴素的联系代数中，每一个 relation 都是由 tuples 组成的 set ，tuple 中的每个 attribute 都有自己的 unique name，咱们很天然地能够想到直接将 tuple schema 作为 attributes 的表明方法。

咱们先回想一下一个 table 是怎么创立的。

create table t(a int);

在 SQL 中咱们运用 DDL(Data Definition Language) 来创立和管理各种 table。在创立 table 时咱们需求为其指定 table schema，里边包括了 table 中每个 column 的详细界说，对应了联系代数中的 attributes。table schema 的结构大概会长这样：

pub struct TableSchema {
    pub name: String,
    pub columns: Vec<ColumnDefinition>
}
pub struct ColumnDefinition {
    pub name: String,
    pub column_type: Type,
    pub not_null: bool,
}

已然 ColumnDefinition 与 attribute 是一一对应的联系，咱们可不能够直接用 ColumnDefinition 来表明 attribute 的 property？

咱们能够先来试试，在 The IR 中加上关于 attributes 的支撑。

fn derive_attributes(op: &Operator) -> Vec<ColumnDefinition> {
    // Calculate the attributes of the children operators.
    let children_attributes: Vec<Vec<ColumnDefinition>> =
        op.children().iter().map(derive_attributes).collect();
    // Calculate attributes with the children attributes.
    op.calculate_attributes(&children_attributes)
}

咱们首先需求对 The IR 做一些修正，为 Get 算子加上 table schema 信息。

pub enum Operator {
    Get {
        table: String,
        schema: Vec<ColumnDefinition>,
    },
    // Nothing changed for other variants
}

然后咱们为 Operator 完成 attributes derivation。

impl Operator {
    fn calculate_attributes(&self, children: &[Vec<ColumnDefinition>]) -> Vec<ColumnDefinition> {
        match self {
            Operator::Get { schema, .. } => {
                let attributes = schema.clone();
                attributes
            }
            Operator::Select { .. } => children[0].clone(),
            Operator::Join { .. } => {
                let mut attributes = children[0].clone();
                attributes.extend(children[1].clone());
                attributes
            }
            Operator::UnionAll { .. } => children[0].clone(),
            Operator::Project { .. } => todo!(),
            Operator::Aggregate { .. } => todo!(),
        }
    }
}

大部分的算子完成仍是很顺畅的，可是能够看到 Project 和 Aggregate 被标成了 todo。咱们这时会发现，Project 和 Aggregate 没法直接运用 children attributes 生成他们自己的 attributes。再回到联系代数上，Project 的效果是裁剪 tuple 的形状，抑或是修正 attribute 的 name， SELECT a 1 AS b FROM t 这种 SQL 底子无法表达为朴素的 Project；至于 Aggregate，朴素的联系代数中底子没有这个运算，这是对联系代数的扩展内容。

联系代数理论不存在了！

可是尽管如此，工程仍是得继续进行，咱们需求引进一些“村规”来扩展联系代数的界说。咱们在此给出 The IR 中的 Project 和 Aggregate 的方法化界说：

$Project(R, (f_1, …, f_n)) → {(x_1, …, x_n)}$ 表明将联系 $R$ 中的 attributes 作为输入，输出 $f_1$ 到 $f_n$ 的 n 个函数映射组成的 tuple
$Aggregate(R, (k_1, …, k_m), (f_1, …, f_n)) → {(x_1, …, x_m, x_m 1, …, x_m n)}$ 表明将联系 R 中的 tuples 依照 $k_1$ 到 $k_m$ 的 m 个 attributes 进行分组，而且对每个分组履行 $f_1$ 到 $f_n$ 的 n 个函数映射，最终输出分组后的 tuples

这个村规最大的改动是引进了 derived column。关于 SQL 中直接来自于 table 的 column，咱们称之为 base table column；关于经过 Project/Aggregate 核算出的 column，咱们称之为 derived column。在引进 derived column 概念之前咱们能够确保一切的数据来源最终都会指向 Get 算子，可是引进之后这个约好就被打破了，出现了相似编程言语中效果域 (scope) 的概念，咱们在进行优化时需求愈加的注意。

有了村规后咱们就能够给 Project 和 Aggregate 也完成 attributes derivation，但与此一起咱们也需求对 The IR 的结构做一些修正：

pub enum Operator {
    Project {
        child: Box<Self>,
        projects: Vec<(ScalarExpr, String)>,
    },
    // Others
}
impl Operator {
    fn calculate_attributes(&self, children: &[Vec<ColumnDefinition>]) -> Vec<ColumnDefinition> {
        match self {
            Operator::Project { projects, .. } => {
                let attributes: Vec<ColumnDefinition> = projects
                    .iter()
                    .map(|(expr, alias)| ColumnDefinition {
                        name: alias.clone(),
                        column_type: expr.column_type(),
                        not_null: expr.nullable(),
                    })
                    .collect();
                attributes
            }
            Operator::Aggregate {
                group_by,
                aggr_exprs,
                ..
            } => {
                let mut attributes: Vec<ColumnDefinition> = group_by
                    .iter()
                    .map(|expr| ColumnDefinition {
                        name: expr.name(),
                        column_type: expr.column_type(),
                        not_null: expr.nullable(),
                    })
                    .collect();
                attributes.extend(aggr_exprs.iter().map(|expr| ColumnDefinition {
                    name: expr.name(),
                    column_type: expr.column_type(),
                    not_null: expr.nullable(),
                }));
                attributes
            }
            // Others
        }
    }
}

这样一来关于一切的算子咱们都能够核算 attributes property 了，赶紧来试用一下吧。

先来看看 SQL 中最常见也最有用的优化——谓词下推。这个优化能够经过将 Select 算子下推到其他算子内以削减其他算子的核算量，一起还能够确保整个查询的成果不会改动，十分的简练优雅。

咱们来测验在 The IR 上完成这个优化。思路上十分简略，依据联系代数定理直接互换 Select 与 Project 的方位即可。可是由于咱们引进了 derived column，咱们有必要查看 Select 中的 predicate 是否依靠了 Project 生成的 column。

fn push_down_select_project(op: &Operator) -> Option<Operator> {
    match op {
        Operator::Select {
            child: project @ box Operator::Project { child, projects },
            predicate,
        } => {
            let project_attributes: Vec<ColumnDefinition> = derive_attributes(&project);
            let predicate_used_columns: Vec<String> = predicate.used_columns();
            // Check if the predicate uses any column from the project.
            let used_derived_columns = predicate_used_columns.iter().any(|used_column| {
                project_attributes
                    .iter()
                    .any(|attr| attr.name == *used_column)
            });
            if used_derived_columns {
                None
            } else {
                Some(Operator::Project {
                    child: Box::new(Operator::Select {
                        child: child.clone(),
                        predicate: predicate.clone(),
                    }),
                    projects: projects.clone(),
                })
            }
        }
        _ => None,
    }
}

看起来现已底子可用了，可喜可贺。咱们再来试试更杂乱的比如，比方试试有 Join 的 SQL：

由于 Join 不像 Project 那样会产生额定的 derived column，因而查看的逻辑会相对简略一些。咱们先完成一个测验将 Select 下推到 Join 的 left child 的优化：

fn push_down_select_join_left(op: &Operator) -> Option<Operator> {
    match op {
        Operator::Select {
            child: join @ box Operator::Join { left, right, .. },
            predicate,
        } => {
            let left_attributes: Vec<ColumnDefinition> = derive_attributes(&left);
            let predicate_used_columns: Vec<String> = predicate.used_columns();
            // Check if the predicate only uses column from left.
            let only_left = predicate_used_columns
                .iter()
                .all(|used_column| left_attributes.iter().any(|attr| attr.name == *used_column));
            if only_left {
                Some(Operator::Join {
                    left: Box::new(Operator::Select {
                        child: left.clone(),
                        predicate: predicate.clone(),
                    }),
                    right: right.clone(),
                    ..join.clone()
                })
            } else {
                None
            }
        }
        _ => None,
    }
}

一切看起来都很夸姣，可是魔鬼往往藏在细节里。咱们来看这个比如在 PostgreSQL 中的输出：

leiysky=# create table t(a int);
CREATE TABLE
leiysky=# create table t1(a int);
CREATE TABLE
leiysky=# insert into t values(1);
INSERT 0 1
leiysky=# insert into t1 values(1);
INSERT 0 1
leiysky=# select * from t, t1 where t.a = 1;
 a | a
--- ---
 1 | 1
(1 row)

最终回来的成果有两个叫做 a 的 attributes。在 The IR 目前的完成中，咱们无法知道这个 Select 该下推到哪边。由于当咱们查看依靠了 a 的 predicate 能被下推到哪一侧时，咱们会发现 Join 的两边都能够满意。尽管同一个 table 中不允许存在多个具有相同 name 的 columns，可是不同 table 之间并没有这样的约束。

PostreSQL 作为对 ANSI SQL 支撑度最高的开源数据库产品，天然也能很好地处理这种问题。经过 EXPLAIN 句子咱们能够看到它将 Select 下推到了正确的当地：

leiysky=# explain(verbose) select * from t, t1 where t.a = 1;
                              QUERY PLAN
----------------------------------------------------------------------
 Nested Loop  (cost=0.00..491.78 rows=33150 width=8)
   Output: t.a, t1.a
   ->  Seq Scan on public.t1  (cost=0.00..35.50 rows=2550 width=4)
         Output: t1.a
   ->  Materialize  (cost=0.00..41.94 rows=13 width=4)
         Output: t.a
         ->  Seq Scan on public.t  (cost=0.00..41.88 rows=13 width=4)
               Output: t.a
               Filter: (t.a = 1)
(9 rows)

The IR 作为完美的 SQL IR，也有必要有自己的处理方案。咱们仔细观察这条查询的话，会发现 Select 的谓词是用 qualified name 表明的，假设运用 unqualified name 的话 PostgreSQL 会抛出这样的报错：

leiysky=# select * from t, t1 where a = 1;
ERROR:  column reference "a" is ambiguous
LINE 1: select * from t, t1 where a = 1;

由于在当前的上下文中，a 是存在歧义的，可是 t.a 就不存在歧义。咱们来试试用 qualified name 表明 attribute property 来处理这个问题，为此咱们需求改动一些代码：

pub struct QualifiedName(pub Vec<String>);
impl QualifiedName {
    /// If the current name can be used to refer another name
    pub fn can_refer(&self, other: &Self) -> bool {
        self.0.len() <= other.0.len() 
          && self.0.iter().zip(other.0.iter()).all(|(a, b)| a == b)
    }
}
pub struct ColumnDefinition {
    /// Use qualified name
    pub name: QualifiedName,
    pub column_type: Type,
    pub not_null: bool,
}
fn resolve_attribute(
    attributes: &[ColumnDefinition],
    name: &QualifiedName,
) -> Option<ColumnDefinition> {
    let candidates: Vec<ColumnDefinition> = attributes
        .iter()
        .filter(|attr| attr.name.can_refer(name))
        .collect();
    if candidates.len() == 1 {
        Some(candidates[0].clone())
    } else if candidates.len() > 1 {
        panic!("Watch out, ambiguous reference found!")
    }else {
        None
    }
}
fn push_down_select_join_left(op: &Operator) -> Option<Operator> {
    match op {
        Operator::Select {
            child: join @ box Operator::Join { left, right, .. },
            predicate,
        } => {
            let left_attributes: Vec<ColumnDefinition> = derive_attributes(&left);
            let predicate_used_columns: Vec<QualifiedName> = predicate.used_columns();
            // Check if the predicate only uses column from left.
            let only_left = predicate_used_columns
                .iter()
                .all(|used_column| resolve_attribute(&left_attributes, used_column).is_some());
            if only_left {
                Some(Operator::Join {
                    left: Box::new(Operator::Select {
                        child: left.clone(),
                        predicate: predicate.clone(),
                    }),
                    right: right.clone(),
                    ..join.clone()
                })
            } else {
                None
            }
        }
        _ => None,
    }
}

这样一来上面的问题就处理了，咱们有了处理杂乱 attribute 引证的才能，可是间隔一劳永逸仍有很大的间隔。咱们再来看一个比如：

leiysky=# select * from (select * from t1) as t, t1 where t.a = 1;
 a | a
--- ---
 1 | 1
(1 row)

尽管 SQL 中不允许在同一个 FROM clause 中运用多个相同的 table name，可是咱们能够运用 inlined view 或许 CTE 绕过这点。依照咱们现在的完成，在处理 t.a = 1 时咱们拿到的 attributes 里边有两个 t1.a 而没有 t.a，这是由于咱们没有处理 inlined view 的 alias。为此，咱们需求增加一个 Project 专门用于给 attributes 做 renaming。

那么问题又来了，由于咱们仅仅是为一些 columns 做了 renaming 就将它们当成了 derived columns 来处理，为咱们的 Select 下推徒增了许多担负。为此咱们有必要修正 The IR 的界说和各种相关代码，服务于 name 的 mapping：

pub enum Operator {
    Project {
        child: Box<Self>,
        // (Expression, Source name, Alias)
        projects: Vec<(ScalarExpr, QualifiedName, QualifiedName)>,
    },
    // Others
}

这些问题经过略微多写点代码还能处理，可是看看接下来的这个比如，我信任大部分人会像我相同直接抓狂：

leiysky=# select a from t natural join t1;
 a
---
 1
(1 row)
leiysky=# select t.a from t natural join t1;
 a
---
 1
(1 row)
leiysky=# select t1.a from t natural join t1;
 a
---
 1
(1 row)
leiysky=# select * from t natural join t1;
 a
---
 1
(1 row)
leiysky=# select a from t join t1 on t.a = t1.a;
ERROR:  column reference "a" is ambiguous
LINE 1: select a from t join t1 on t.a = t1.a;

咱们当然能够为代码中再加上各种奇奇怪怪的约束，开各种难以保护的洞来保护这种 property，而且在进行优化的一起确保这些 property 的正确性。可是关于懒惰的程序员们来说，寻觅一种更简略的规划才是更好的选择。

欢迎来到深水区。

The IR made simple

最开端的 The IR 是十分简练而优雅的，可是为了完成更多的功用，支撑更杂乱的需求，咱们为其增加了许多咱们不想重视的信息。总的来说，抱负状况的 The IR 应该是：

具有简练的代数结构
Operator 节点之间彻底独立
不必处理 names（仅用于 debug 和展示）

让咱们在回过头来思考一下，The IR 真的离不开 name 吗？咱们最开端运用 name 来表明 attribute 首要是出于直觉，复用了 table schema。可是 name 中融入了许多无用的信息，对咱们的优化毫无协助，就像编程言语中的各种 symbol name 相同，到了程序运转时都会变成内存地址和寄存器编号。

没有 name 便无法区别 attributes，name 岂是如此不方便之物？

归根结底，咱们需求的是为每个 attribute 附上一个 unique id，无论是 integer 仍是 string，总归咱们的仅有目的便是用 id 来区别和引证 attribute。一切的 name resolution 通通丢进 AST lowering，我只想要 attribute id！

在进行了重新规划之后咱们改动了 attribute 的表明方法，一起也更改了一些 The IR 的界说。默认情况下，咱们运用 int64 类型作为 attribute id。

pub type Id = i64;
pub struct Attribute {
    pub id: Id,
    pub column_type: Type,
    pub nullable: Type,
}
pub enum ScalarExpr {
    ColumnRef(Id),
    // Others
}

id 的规划一般离不开对应的上下文 (context)，在 SQL IR 中 attribute id 的常见规划方法首要能够分为两类：

一种是依据咱们之前用到的 tuple attribute 的笼统，将 attribute 在 tuple 中的 index 作为 attribute id，咱们将这种 id 称为 local id。这种规划的特点是逻辑上的同一个 attribute 的 id 会跟着其所处的 operator 的不同而发生改动。这种 id 的优点是能够从 operator tree 中推理出来，不需求靠外部的状况进行保护。可是缺点便是在对 operator 进行转化时需求频繁的对 id 进行 remapping。
另一种是经过保护一个全局的 id generator，给 SQL IR 中的一切 attribute 赋予一个 unique id，咱们将这种 id 称为 global id。这种规划的优点是将 attribute 与 tuple schema 进行了解耦，能够运用 HashMap<Id, Attribute> 这种无序调集结构表明 attributes。一起也能够运用调集运算协助 property derivation，下降保护杂乱度。可是缺点是运用 global id 的 operator tree 需求依靠外部状况，无法独自存在。

运用这两种不同的规划会对优化器的详细完成形成十分大的影响。

比方说关于这个优化：

在有适宜的索引可用时，经过这个优化能够防止 full table scan 然后提高功能。

假设运用 local id 的规划，完成这个优化会十分简略，只需求将整个 operator tree 仿制一份，最终运用 UnionAll 连接起来即可。

可是假设运用 global id 的规划，这便是一个 non-trivial 的操作，乃至能够说是十分苦楚。为了区别不同的 attribute，咱们有必要在仿制 operator tree 的一起为一切的 attribute 生成新的 id，再将一切引证这些 attribute 的当地替换成新的 id，这在查询较为杂乱时会形成许多费事。

再比方说进行 join order 优化时：

依据 Join 算子的交换律，咱们能够合法交换 Join 的左右 child。运用 global id 的规划时，由于 attributes 能够表明为无序调集，因而这个操作关于 property derivation 毫无影响。可是运用 local id 的规划时这个操作就会让人苦楚不堪。

除掉优化相关的部分，在关于 correlated subquery 的表明上他们的差异也十分巨大。correlated subquery 是一种特别的 subquery，它能够拜访自己的 scope 以外的 attribute，关于这类特别的 attribute 拜访咱们称之为 outer reference。

许多编程言语中也支撑相似的操作，能够从函数中拜访界说在函数内没有界说的变量，经过与特定环境 (environment) 进行绑定 (bind) 后才能履行。这种特别的函数叫做闭包 (Closure)。

fn main() {
    let a = 1;
    let f = || {
        let b = a; // a is captured from outside
        println!("{}", b);
    }; // f is a closure
    f(); // stdout: 1
}

运用 global id 的规划能够经过 attribute property 核算出 subquery 是否为 correlated。可是运用 local id 的规划时咱们一般会在 scalar expression 的 ColumnRef 中额定保护一个 scope id，完成起来十分费事。

correlated subquery 是一个十分大的论题，咱们或许会在后续的文章中聊到。

由此可见两种规划各有优缺点，在工程实践中咱们要结合自己的需求选择合适自己的规划。就我个人而言，global id 是一种更好的规划，由于它在绝大多数的情况下都能很轻松地处理问题。

运用 global id 进行改造后，The IR 的代码能够得到大幅的简化：

pub type Id = i64;
pub struct Context {
    pub id_gen: Id,
}
pub struct Attribute {
    pub id: Id,
    pub column_type: Type,
    pub nullable: Type,
}
pub type AttributeSet = HashMap<Id, Attribute>;
pub enum ScalarExpr {
    ColumnRef(Id),
    Literal(Value, Type),
    Function(Signature, Vec<Self>),
    Subquery(Quantifier, Box<Operator>),
}
pub enum Operator {
    Get {
        table: String,
        output_columns: AttributeSet,
    },
    Select {
        child: Box<Self>,
        predicate: ScalarExpr,
    },
    Project {
        child: Box<Self>,
        projects: Vec<(ScalarExpr, Id)>,
    },
    Join {
        kind: JoinKind,
        condition: ScalarExpr,
        left: Box<Self>,
        right: Box<Self>,
    },
    UnionAll {
        left: Box<Self>,
        right: Box<Self>,
    },
    Aggregate {
        group_by: Vec<ScalarExpr>,
        aggr_exprs: Vec<(ScalarExpr, Id)>,
        child: Box<Self>,
    },
}

在把杂乱度转嫁给 AST lowerer 之后，咱们能够自傲地说，The IR 现已是个 production ready 的 SQL IR 了。它能够支撑一切的 SQL 运算和常用的优化，具有易用的 API，一起也十分易于了解。更重要的是，没有人比这篇文章的读者更懂 The IR，任何读者都能够依据自己的需求轻松扩展 The IR。

后记

终于到了这篇文章的结尾。

作为系列的开篇，我在这篇文章里仅仅简略地聊了聊 SQL IR 规划中的一些重视点，并没有深化评论各种算法的细节。

可是共享 IR 的规划进程是一件很有意思的工作。许多 IR 就像路旁边的一棵长得歪歪扭扭的树，第一次路过的人都不知道它为什么会长成那样，只有从小住在这儿的人才知道在这棵树很小的时分人们总是喜爱在它的树枝上挂腊肉。这件小事是导致最终成果的重要原因，可是它过于微乎其微，导致知道的人从来不会自动共享——当然现实中往往也没人关怀背后的原因。

数据库开发是一个小众领域，一起又有许多工程化的实践经验。这些经验在坊间罕见撒播，我不期望它像美国的登月技术相同跟着年代的变化而消失，这也是我想到写这个系列文章的初衷。

鄙人一篇文章里我会共享关于优化器架构的相关内容，敬请等待。

关于 Databend

Databend 是一款开源、弹性、低成本，依据目标存储也能够做实时剖析的新式数仓。等待您的重视，一同探索云原生数仓处理方案，打造新一代开源 Data Cloud。

‍‍ Databend Cloud：databend.cn

Databend 文档：docs.databend.cn/

Wechat：Databend

✨ GitHub：github.com/datafuselab…

当我谈查询优化器时，我谈些什么 (1)—— IR 设计

什么是查询优化器

什么是 IR

SQL IR 都长啥样

AST

联系代数

最佳工程实践（待定）

Hello, world!

Select & Project

Scalar expression

The IR

Property derivation

Relational properties

The IR made simple

后记

关于 Databend

作者信息

推广

当我谈查询优化器时，我谈些什么 (1)—— IR 设计

什么是查询优化器

什么是 IR

SQL IR 都长啥样

AST

联系代数

最佳工程实践（待定）

Hello, world!

Select & Project

Scalar expression

The IR

Property derivation

Relational properties

The IR made simple

后记

关于 Databend

相关文章

《成为解决问题的高手》总结篇 —— 解决多人问题的工具

我用ChatGPT做直播技术选型，卷死了同事

为了弄清起点小说如何算字扣钱，我特意注册了作家账号

Android通过GPS获取定位的方式

作者信息

推广