数据分析的语言接口
OLAP计算引擎是一架机器，而操作这架机器的是编程语言。使用者通过特定语言告诉计算引擎，需要读取哪些数据、以及需要进行什么样的计算。编程语言有很多种，任何人都可以设计出一门编程语言，然后设计对应的编译器做解析。编程语言从分类上来说，可以分为命令式，声明式。
命令式编程语言是我们最常见的编程语言，C/C++/Java等都是命令式编程语言，这类语言明确的告诉机器应该执行什么样的指令，留给编译器优化的空间很小了。
声明式编程描述程序应该获得什么结果，至于如何做到，并不关注细节。SQL就是一种声明式编程语言。例如SQL语句select count(1) from department where kpi =3.25，指明计算kpi=3.25的人数，但不会具体指定如何完成计算。这给后续的优化器留下了很大的操作空间，优化器可以根据SQL的需求和实际的数据做各种各样的探索，寻找到最佳的执行方式。
一个优秀的分析语言应该具有以下几个特征：
- 语言简单，门槛低
- 语意明确，无歧义
- 资料丰富，方便学习
- 生态丰富，工具多
- 方便扩展，可编排复杂的逻辑
SQL是一种历史悠久的，使用比较广泛的分析语言。在关系型数据库时代就广泛使用的一种语言。在21世纪初，出现了MapReduce算法，数据分析师需要编写MapReduce程序来分析数据。MapReduce程序是一种命令式语言，编写过程非常麻烦，堪比写程序，这就需要数据分析师不仅具备算法能力，还要具备工程能力，使用体验非常糟糕。这就需要两个团队来合作，BI团队把分析需求传递给开发团队，由开发团队去开发分析程序。为了改善分析体验，出现了SQL on Hadoop的解决方案，典型的如Hive，提供SQL接口，并把用户输入的SQL转写成MapReduce执行计划，因而极大的提升了数据分析的体验，实现了BI团队的自主分析，降低了数据分析的门槛，大大增加了受众范围。因此，SQL的影响力是非常大的。从Hive开始，大数据的主要使用接口就转移到了SQL上。而工程师们可以在SQL这张皮之下，专心的优化性能，无缝的升级计算引擎，保持使用接口的一致性。
SQL的语法简单，逻辑清晰，了解了最简单的查询语句之后，就可以嵌套多层表达很复杂的逻辑。SQL基于关系代数，有理论基础，保证语意明确没有歧义。SQL的发展历史非常久远，因而学习资料也比较多，方便新入门者学习。同时围绕SQL的生态也比较丰富，有很多工具使用SQL做分析。
除了SQL之外，也有一些软件推出自定义的语言，例如Elasticsearch使用Lucene语法，Prometheus推出了自定义的PromQL，而Splunk推出了SPL。每一种新的语法，对于新用户而言，都存在一定的学习门槛。因而都不如SQL使用广泛。可以说SQL是数据分析的事实标准。
数据模型
数据模型（DataModel） 用于描述数据在数据库中的组织形式。常见的模型有关系模型（Relational），键值模型（Key/Value），图模型（Graph），文档模型（Document），列簇模型（Column-family）等。 关系型数据库采用关系模型。Redis采用键值模型。图数据库采用图模型。MongolDB采用文档模型。
关系模型中的关系有点绕口，在英文中是Relational，硬翻译成了关系，我的理解，关系指的是一些相互之间有关系的属性组成的一个实体，因为各个列属性之间存在关联关系，而被称为一个关系，其实指的是属性之间的相关性，这种相关性体现在：属于同一行；满足列之间的约束条件；满足行之间的约束条件；满足不同关系之间的约束条件。通过不同的约束条件，是全部的数据形成一种有组织的存在。
数据库通过关系模型，定义出一个个关系实体，确保内容之间满足一定的约束标间，并且提供编程接口去读写数据库内容。一个数据库包含一堆关系，每个关系是一个多行多列的表格。每一行的各个列之间是相关的，也可能会定义一些约束条件。行与行之间，也可能通过定义唯一键（Primary Key），定义排序方式来约束行之间的关系。关系与关系之间，可以通过外部键来实现。
这种列之间和行之间的约束关系，在OLTP场景中比较实用，因为OLTP关注的数据本身，因此在存储数据时，更多关注数据的存储形式。而OLAP关注的数据的分析，所以在数仓中，这些约束条件是弱化的，因此，在数仓中，我们只需关注一张多行多列的表格即可，像PK、排序这类约束属性，更多只是用来做数据加速的手段。关系模型用来作为一种严密的理论，给执行器的优化提供理论基础。但是这个名字毕竟太绕口，在后续文章中，除非涉及到关系模型相关的理论，会使用关系这个词，一般情况下，会用表来指代一个关系。
关系代数(Relational Algebra)
关系模型和关系代数是SQL的理论基础。代数不仅是我们所熟知的简单的加减乘除等数学计算。在计算机行业，我们见到过多种algebra，在神经网络中常用的线性代数（linear algebra），在电路中用到的布尔代数（boolean algebra），香农把布尔代数带入到了逻辑电路设计中，为计算机二进制计算提供了理论依据。此外还有N多种algebra，这里不一一列举。
关系代数，源自于集合代数，讲述集合之间的变换关系。关系代数中的一系列操作，接受一个或两个关系作为输入，产生一个新的关系作为结果。由于输入和输出都是一个关系，我们可以串联多个算子，形成更加复杂的算子。关系代数中包含的算子有：σ (select，从一个关系中筛选出部分行，形成一个新的关系),Π(projection，从一个关系中筛选出部分列，形成一个新的关系),∪(Union，合并两个关系), ∩(Intersection，取两个关系的交集部分), –(difference，取两个关系的差集部分), ×(Product，两个关系的笛卡尔积),⋈(Join，两个关系在满足某些条件下的连接),ρ（Rename，重命名关系中的列）, ←(Assignments，把一个临时的查询命名成一个新的关系), δ(Duplicate Eliminating，去重), γ(Aggregation，对部分列做聚合计算，结果形成一个新关系), τ(Sorting，排序结果形成一个新关系)。这里定义了常用的关系操作，名字已经表示出了其操作的含义，在这里不再介绍每个操作的明细了。在语法解析和优化器阶段我们会再次接触到关系代数，并且借助于关系代数的理论依据，来做一些语法树上的转换。在这里我们只需要知道在关系代数上有这些操作，并且在之后的SQL语法上看到如何用SQL语法来表达这些操作。
SQL
SQL语言的发展历史
SQL的发展历史，可以追溯到机械化数据分析的历史。在20世纪初，IBM主要的业务是打孔卡业务，也就是使用卡上的孔来记录信息，然后利用电路的通断判断是否有孔，并通过电路驱动机械装置，累计计算结果。打孔卡类似我们现代使用的答题卡，答题卡的每一个题目，都提供了四个选项，然后用铅笔涂黑对应的选项；打孔卡不同的地方在于，选中的部分穿透成孔，当放置到电路板上时，有孔的部分会有电流通过，进而触发之后的动作。这是在当时是一项非常先进的数据分析方法，相较于古老的依赖人去计数，也让大数据的自动化分析成为可能。在20世纪初，要统计数千万人口的信息，需要投入大量的人力资源，而打孔卡这种创世纪的发明，带来了数据分析行业的快速发展。因此可以说IBM的业务主要是提供数据分析的机器，主要的客户场景是联邦政府的人口普查，以及业机构做商业分析。这个时候，数据存储以来打孔卡，而数据计算是机械装置，计算结果输出到打印机。
到20世纪50年代，随着电气化的发展，磁带取代打孔卡成为新的存储设备，电气装置取代机械装置做计数。计算结果可以继续存储到磁带上。磁带的存储空间很大，不过磁带的缺点是只能顺序读写，这导致数据处理的程序不得不适应这种特性按照顺序处理。
到了60、70年代，磁盘被发明出来，磁盘可以被随机读写，这极大的改变了数据处理方式。数据结构无需考虑数据之间的顺序，一些更加复杂的数据模型被发明出来，例如网状模型或者层次化模型。1970年，Edgar Codd定义了关系模型，给出了非过程式的查询数据的方法，关系型数据库诞生了。关系模型非常简洁，并且提供了理论基础。非过程式的查询方法，屏蔽了实现的细节，使用者只需要声明所需要的结果即可，实现的过程则交给优化器给出最优的执行计划，这极大的降低了使用门槛。关系模型的发明者也因此获得了图灵奖。尽管关系模型在学术上非常吸引人，但是在现实中，在性能上还比不上已经存在的数据库。
到了70年代后期、80年代，IBM推出了一个突破性的项目System R，在项目中研发了至关重要的能够使关系型数据库非常高效的技术。在System R中，IBM推出了SQL的最早期版本，称为Sequal，后来演化成了SQL（Structed Query Language结构化查询语言）。这个项目虽然是个原型，但是它促进了之后IBM推出了第一个商用的关系模型的数据库产品System/38(1979),SQL/DS(1981),DB2(1983)。其中DB2目前还是活跃的商用数据库，在大学中也有DB2的使用课程。至此，SQL语言出现了，并且被其他的商用数据库系统所采用，比如Oracle的数据库。在数十年内，SQL语言凭借着其易用性，击败了其他需要关心底层实现的数据库产品，成为了事实上的标准。
1986年ANSI标准推出了SQL标准，称为SQL86，就是我们常说的ANSI SQL。之后标准经过陆续补充，以添加新的特性，陆续出现了SQL89，SQL92，SQL1999（正则式，触发器，OO）， SQL2003（XML,窗口函数，Sequence，自增ID），SQL2006， SQL2008（清空表语法，Fancy Sorting）， SQL2011（临时表，管道式DML）， 最近的是SQL2016（Json，多态表）。
一般来说，一个数据分析系统，不一定完全遵循SQL的标准，这主要是由分析系统的特有特性所决定的，有些特性，在SQL标准里边是没有的，所以一般会在SQL标准上做一些拓展，号称是兼容ANSI SQL。一个系统需要支持的最小功能集合是SQL92标准。
SQL的功能
SQL语法包含了几个类别的功能，分别是
Data Manipulation Language（DML）：数据操作语言，用于增删改查数据。
Data Definition Language（DDL）：数据定义语言，用于定义表的格式。
Data Control Language（DCL）:数据控制语言，用于控制权限等。
虽然DML和DCL是SQL系统的基础功能，本文的关注重点更多是数据处理的技术，以及如何加快数据处理的技术，因此更多关注DDL。 在DDL中，也有增删改查，在这几项中，本文更多关注查的部分内容，即如何加快数据的读取和计算。而数据的写入、存储部分的优化手段，也是为了满足加速数据计算的目的。
SQL的处理过程
SQL全称Structed Query Language(结构化查询语言)。SQL语法简单，易学易用，是数据分析领域最通用的语言。SQL是数据分析的操作工具，对于用户而言SQL代表浙用户的操作语义，但是对于程序而言，只是接收到一串字符串。程序需要理解SQL的意义，要经过词法分析、语法分析、语义分析、构造成抽象语法树。词法分析、语法分析是非常基础的操作。大学的计算机的编译原理课程应该包含了本部分内容，词法分析和语法分析的模式是固定的，玩不出花样，无助于提升计算速度。不过作为OLAP引擎中必不可少的第一环，还是有必要对词法分析和语法分析做出简单的介绍，有助于了解后续章节中的查询计划和优化器，但是本章不会占用太多篇幅，本文的重点是关于计算速度的内容。
开发者也可以研发自定义的分析语言，只要语言符合一定的规则，没有歧义，在语义上完整，也能过称为一种语言。不过开发一个新的语言非常困难，大多数的新语言采用程序式编程，每一个短语表示一个简单的操作；或者采用管道式声明语法，每一部分代表输入，计算和输出，但是要定义一种能够无限扩展而没有歧义的语法是很难的。在语义完整程度上是不能和SQL相比较的。无论是开发一门新的语言，还是采用SQL，流程都和下图类似。OLAP引擎解析SQL，生成抽象语法树，再转化成逻辑执行计划，经过优化后，生成高性能的算子组合。这就是编译和优化的过程。
图2-1 程序编译和SQL编译
在了解编译之前，我们首先了解一下SQL的结构定义。SQL是围绕着关系进行的。可以在关系上定义各种操作，也可以定义多个关系的操作。
关系
SQL操作的对象是结构化数据。SQL语法的基础语法以及嵌套扩展，都是围绕着“关系”进行的。“关系”可以想象成数据库中的表，由多行多列组成。一个SQL，接受一个或多个“关系”的输入，并输出一个“关系”。在嵌套查询时，内部查询输出一个中间“关系”，并作为外层查询的输入“关系”，类似于Linux命令行中的管道语法。在下文中，用“表”来表示“关系”。
SQL 语法
单表上的操作
在一个表上，可以进行过滤(WHERE)、转换(scalar函数)、聚合(聚合或分组聚合)、聚合后过滤（HAVING）、排序（ORDER BY）、投影（SELECT）、截断行数（LIIMIT）等操作。各个操作之间的执行时间存在先后顺序。一个典型的SQL语法如：
[WITH with_query [,...]]
SELECT expr
FROM TABLE
WHERE bool_expr
GROUP BY columns
HAVING Condition
ORDER BY expr
LIMIT count在执行顺序上，首先从表中select出需要的列；然后执行WHERE语句；过滤完后，执行GROUP BY聚合计算；聚合后的结果执行HAVING执行二次过滤；然后执行ORDER BY排序结果；最后根据LIMIT限定输出的行数。
图2-2 SQL执行顺序
经过以上步骤，完成对一个表的操作，并且输出一个新的表。当需要嵌套查询时，把内部的结果表用括号包含起来，即可视同内部查询为一个普通表，然后执行上述相同的操作。因而，SQL的语法可以无限的嵌套。对于嵌套查询，除了用括号把子查询包含起来作为子表，另一种做法是用with语句定义子查询。下文予以详细介绍。
SELECT子句
最简单的SELECT操作是SELECT select_expr from TABLE。表示从表中获取数据，也允许在数据之上增加一些列的计算。在select可跟的表达式有：
- SELECT 列名.表示从表中读取列的原始数据。
- SELECT scalar_function(列名)，表示读取列的原始数据，并且经过scalar_function逐行转换每一行原始数据，输出转换后结果。Scalar Function是转换函数，表示1行到1行的转换。经过转换后的数据行数不会发生改变。一个典型的转换函数是round函数，表示把原始数据截断后保留几个小数位。
- SELECT aggregate_function(列名)，表示读取原始数据，并且对所有的原始数据做聚合计算，输出聚合后的结果，结果只包含一行一列数据。
SELECT后的表达式有可以有1个或者多个，可用逗号来连接多个表达式，如果是第1或第2种情况，两种表达式可以混合使用，例如SELECT column1, scalar_function(column2)，可以并列出现无限多个列名或者转换函数。对于第3种情况，在没有group by语句的情况下，聚合函数只能和其他聚合函数混合使用，例如SELECT aggretate_function1(column1), aggregate_function2(column2)，在同级别不能出现1或者2的情况，当然聚合函数内是可以嵌套转换函数的，例如SELECT aggregate_function(scalar_function(column))。对于有group by的情况，group by的列名以及列名之上的转换函数可以出现在select中。原理也很简单，因为case 1和2不改变结果行数，case 3聚合计算只输出一行结果，所以是不能在同级别混用的。
转换函数（scalar function）
如上文所说，转换函数对每一行输入，经过计算后，输出对应一行的结果，即，转换函数不会改变输入数据的行数。scalar function的scalar就代表是对原有数据的线性伸缩，不改变原数据的维度空间。转换函数的输入参数可以是0个或者多个；输出只有1个，即无论输入多少列参数，输出只有一列。如果希望输出多列，则需要把输出结果整合到一个复杂类型里，例如数组array或者字典map，再通过嵌套查询展开结果。
由于转换函数不改变结果的行数，因此可以无限嵌套调用转换函数，例如fun1(fun2(fun3(fun4(fun5(key)))))，尽管大多数情况下无限层次的嵌套并不是必要的，一到两层的嵌套是常见的场景。
转换函数定义好了输入输出模式，函数实现并不属于执行框架的内容，执行框架无需关注函数的内部实现，只需要调用该函数，并且把对应的参数传入函数，然后获得输出结果并传递给后续的算子即可。
基于这套机制，用户可以开发更多自定义的UDF，并且注册到执行引擎中。开发者在开发UDF的过程中，只需要关心UDF的格式定义，而无需关注执行引擎内部复杂的实现逻辑。
转换函数的一个样例，key列取一位小数输出：
SELECT round(key,1) FROM table
图2-3
聚合函数
聚合函数和转换函数的不同点在于：聚合函数无论接受多少行输入数据，输出数据都只有一个值，即一行一列；如果是按照窗口聚合（group by某些列），那么每个窗口内的输入数据只会产生一个输出数据。例如求均值的函数avg，无论输入的数据有多少行，最终都只输出一个均值。另一个不同点在于，转换函数没有内部状态，输入数据后可以立马得到输出结果；而聚合函数，要在内存中保存一个状态，直到全部数据都输入结束后，才能拿到最终的结果。例如avg函数，在内存中保存一个sum和一个count这两个值作为状态，分别表示输入数据的求和值以及输入行数，每输入一个新的数据，都更新状态，最终输出时才把两者相除，获得均值。
聚合函数也是一种UDAF(用户自定义聚合函数)。用户可以开发自己的UDAF，并且注册到执行引擎中供调用。
聚合函数的一个样例，求访问日志的平均延时：
SELECT status，avg(dValue) FROM accesslog group by status
按照status划分窗口，分别有200和500两个窗口，每个窗口内的数据分别计算avg这个集合函数，产生一个聚合结果。
图2-4 聚合函数
选择性聚合
如果在SQL里边只有一个聚合函数，我们只期望对部分数据做聚合计算，那么只需要把过滤条件放在where中，先过滤出自己想要的数据即可。但是，如果有多个聚合函数呢，每个聚合函数需要的过滤条件不一样呢？对于count算子，有对应的count_if函数可以附加过滤条件。对于其他的聚合函数，也可以使用case when先过滤出来需要的数据，然后再执行聚合计算，例如avg(case when status=200 then latency end)。不过case when并不是专门用来做过滤的，语法使用起来也不叫复杂，也不是所有聚合函数都满足这种过滤的语意。除了case when，还有一种专门的选择性聚合算子，可以对每个聚合函数附加一个过滤条件。具体语法如：
SELECT
key,
AGG1(x) FILTER (WHERE condition1),
AGG2(y) FILTER (WHERE condition2),
AGG3(z) FILTER (WHERE condition3),
...
FROM每个聚合算子后都跟着一个filter( where bool表达式)，满足bool表达式的内容才会参与对应的聚合。在同一层的的各个聚合函数，可以指定各自的过滤条件，也可以不指定过滤条件，每个聚合函数对应的过滤条件之间没有任何关系，可以相同，也可以不同。这就是选择性聚合，在语法层面给多样化的聚合提供了方便。
Distinct 聚合
在聚合函数中，所有的输入都会参与到聚合中。但是有一种场景，先把数据做去重，再做聚合。最常见的使用场景是count(distinct key)，先对key做去重，在计算count值。除了count，其他的聚合函数也可以使用该语法，例如avg(distinct key)，先去重再聚合。
聚合函数内的完整语法是:
aggregate_function(all key)
aggregate_function(distinct key)第一种语法不做去重，全部数据参与计算。第二种语法先做去重，再做聚合计算。默认是第一种语法，因此all关键字不是必须的。
聚合中的Null值
在聚合函数的输入参数中，如果参数值是null，那么不参与计算。例如sum(key)，只统计非null值的和。count(key)只统计非null的个数。此处有个例外，就是count(*)，因为*并不是具体的列，不存在null或非null的差别，因此所有的行都会统计在内。
如果聚合函数的所有输入，排除掉null值后，只有0行有效数据，那么聚合函数的返回结果是null，因为没有任何有效数据参与计算。以sum为例，如果全都是null，或者只有0行输入，返回0或者其他特殊值是不合适的，因为没有特殊值可以唯一代表这种场景，只有返回null才合适。在所有的聚合函数中，除了count之外，都符合这一定义，count 0行输入的结果是0。
GROUP BY分组聚合
只有聚合函数的场景，所有的输入都聚合成一个结果。如果要把输入分到多个分组中，每个分组分别生成聚合结果，则需要用group by指定分组。 Group by后跟一列或者多列、或者有某些列经过转换函数计算后的结果。Group by子句是配合聚合算子使用的。没有group by的情况下，聚合算子接受所有的输入数据，产生一个计算结果；有group by的情况，称为分组聚合，各行数据先按照group by中指定的列或列的转换结果，计算所属分组，每个分组内无论有多少行数据，都会计算产生一行聚合结果。图2-4是一个group by分组聚合的样例，按照status分组，总共有2个分组，每个分组产生一行聚合结果，即共两行聚合结果。
Group by的一个样例，求访问日志中每个站点的平均延时：
SELECT avg(latency), host from accesslog GROUP BY host
在一个分组内，可以执行多个聚合函数，每个聚合函数产生一列聚合结果。即分组的数量决定结果行数，聚合函数的数量决定结果的列数。
在有group by的场景下，select中指定的表达式，除了聚合函数外，还可以select某些列，或者某些列经过转换函数计算后的结果，这些列是有限制条件的，只能是group by中出现的列。如果是非group by的列，就会出现一个难以抉择的问题，因为分组是按照group by的列分组的，每个分组只输出一行结果，如果select 非group by的列，那么在分组中，会有多行数据进入同一分组，在输出时到底选择哪一行作为解决呢？这没有明确的答案。有几种可能性，第一种是随机的选择一行；第二种是选择第一行；第三种是选择最后一行；第四种是全部输出。可能性太多，如果用户不明确的告诉SQL选择哪一种选项，就会造成误判，输出结果不一定满足用户预期。每一种选项都会有对应的聚合函数实现。当然在mysql系统中，是按照第一种选项输出的。
对于需要在分组内产生多行聚合结果的使用场景，可以参考窗口函数。
如果要分组的列是null值，则null值会作为一个单独的分组。
一般的场景下，一个原始数据只会在一个分组内参与聚合计算，不会同时出现在多个分组中。但也有一些高级用法就是grouping set操作，在下文详细介绍。
Grouping sets操作
上文介绍的group by子句，是比较简单的一种分组聚合操作。全量的数据，会按照分组条件分到不同的组里边，每一行数据，都只会在一个分组中参与聚合。还有一种更加复杂的分组聚合操作是grouping sets操作。相关关键字是grouping sets, cube, rollup。该算子可以允许在一次查询中，按照不同的分组条件，多次分组。每一条数据，都会按照不同的分组条件多次参与聚合。
例如，如果你希望按照多个分组聚合(grade, class), (grade),(class),如果使用group by，那么要分别执行三次group by操作。使用grouping sets则可以在一次查询中完成，语法是select grade,class,count(1) from log group by grouping sets((grade, class), (grade),(class))。在输出的结果中，grade class两列都会输出，但是在后两个集合中，只group by了一列，另一列以null出现在结果中。
Rollup语法是一种特殊的grouping sets语法，roll up后跟的集合，会按照层级聚合的方式，枚举出所有的前缀集合。例如group by rollup(grade, class),相当于group by grouping sets ((grade, class),(grade),())。最后一个分组条件是空分组，也就是不分组，相当于没有group by的场景。
Cube语法也是一种特殊的grouping sets语法，cube和roll up不同之处在于，cube会枚举所有可能的集合。例如group by cube(grade,class)，相当于group by grouping sets((grade,class),(grade),(class),())。
窗口函数
转换函数输入一行数据，输出一行数据。聚合函数把多行数据聚合成一行。有没有一种聚合函数，实现聚合，但是不改变输入行数呢？答案是窗口函数。
窗口函数在表达结果上类似于转换函数，针对每一行输入，都会产生一行输出，不会改变结果的行数。但在使用上，在窗口函数内部，可以使用聚合计算函数。窗口函数根据某些列分成多个桶，把每一行数据分发到对应的桶中去，然后在每一个桶上执行聚合函数，并且把结果写回到每一行。因此，相当于窗口函数把聚合函数当成了转换函数来使用。转换函数是把一行输入转换成一行输出；窗口函数是把窗口内的若干行聚合后生成一个结果，但是每一行都会有一个结果。
窗口函数的逻辑如图2-4所示，有窗口列，排序列，参与聚合的列。在每个窗口内对指定的若干行进行聚合计算，并且写入到当前行的结果中。输出的结果行数和输入的行数相同。
图2-5 窗口函数示意图
窗口函数最简单的场景，例如：avg(key2) over()，表示把所有数据当成一个分组做avg聚合，并且写回每条数据中，虽然结果中的每行数字都相同，但是没有改变结果行数。如下图中的out3的结果所示，所有行的均值为3，3就是每一行对应的结果。
再复杂一点的窗口函数场景，例如：avg(key2) over(partition by key1)，表示按照key1作为分组，每个分组内分别执行avg聚合计算，并且更新到每个分组的每条数据中。如下图的out1所示，a这个窗口的均值是1.5，窗口内所有的结果都填充为1.5。b这个窗口内均值是4，窗口内所有的结果都填充成4。
更加复杂一点的窗口函数样例如：avg(key2) over(partition by key1 order by key2)，表示按照key1作为分组，在每个分组内再按照key2排序，计算窗口内从第一行到当前行为止的数据的avg聚合结果，也就是分组内每一行的结果可能是不一样的。参考下图中的out2这个结果，a这个窗口，第一行数据是1，均值就是1；第二行数据是2，第二行对应的窗口均值就是第一行和第二行的均值，也就是1.5。因此结果中，第一行的结果是1，第二行的结果是1.5。这个和out1的对比比较明显，out1的结果中，每个窗口内的结果都是一样的。
上边的样例还不是最复杂的，前2个样例，都是在分组内的所有数据上执行聚合；加上order by之后，是聚合从第一行到当前行的数据。那有没有一种方法，只聚合当前行附近的几行呢？能否更加灵活的指定窗口内哪些行参与聚合计算呢？答案是可以的。窗口函数可以指定当前行的前后若干行参与聚合计算，例如avg(key2) over(partition by key1 order by key2 range between unbounded preceding and current row)，表示从第一行到当前行。range between 1 precedingand 2 following，表示包含前一行、当前行、后两行总共4行组成的数据进行聚合，更新到当前行的结果。参与聚合的行称为一个frame，一个frame内的数据聚合生成一个结果。
图2-6窗口函数的输出
在窗口函数中，除了普通的聚合函数，还有一些特殊的、专门用于窗口运算的聚合函数。例如：rank()用于窗口内的排序，输出排序后的序号，相同的值序号相同，但是相同的值会占用计数值，例如100、102、102、103，输出序号是1、2、2、4，注意最后一个序号是4。如果期望输出的需要是去重排序后的序号，则应该用dense_rank函数，针对上述例子，输出序号为1、2、2、3。此外还有row_number输出行号。cume_dist排序后从窗口第一行开始的累积百分比，和rank类似，相同的值输出相同的结果，输出结果为rank()/total。percent_rank输出(rank()-1)/total-1)。cume_dist和percent_rank的差别在于，后者从0开始累积。
运算符和函数
在内部实现和表达效果上中，运算符和函数是相同的。两者的区别在于语法形式不同，函数有明确的函数名，包含0个或者多个参数的参数列表；运算符则是通过常见的符号来表达意义，例如+-*/等符号。运算符包含1个或者2个参数。双目运算符包含两个参数，例如+运算符，需要左右参数。单目运算符包含一个参数，例如-运算符，代表符号的取反操作。运算符需要在语法文件中显式定义语法形式。而函数名是不需要定义在语法文件中的，在语法文件中只是一个普通的字符串而已，直到语意检查阶段才需要检查函数是否存在。
表达式
表达式是一种有一个或多个函数、运算符、连接符组成的一个完整表达式（Expression）。表达式的作用等同于转换函数，输入0个或多个字段，输出一行一列结果。常见的表达式有bool表达式，逻辑表达式，比较表达式，函数调用，lambda表达式等。
比较表达式
比较表达式通过比较运算符>,>=,<,<=,=,<>等连接两个表达式，用于判定两个表达式的大小关系。左右的表达式不一定是基础类型，也可能是复杂的表达式，例如函数调用表达式。基础类型的数据包括integer、bigint等数值类型，也可能是varchar，char等字符串类型。除了上述比较算法，还有between关键字，key between x to y，等价于key >=x and key <=y，是一个闭区间。
Bool表达式
bool表达式指的是返回结果为bool类型的一类表达式。Bool表达式广泛的应用于各种过滤条件中，例如WHERE，HAVING，ON等。一些转换函数可以返回bool类型结果，还有一些比较运算符可以返回bool结果。例如>,< 等比较运算符。
逻辑表达式
函数可以代表一个简单的表达式，如果要表达复杂的逻辑，除了函数嵌套函数，还可以用逻辑链接符号组合多个表达式，形成一个复杂的bool表达式。逻辑表达式由逻辑运算符AND、OR、NOT连接1个或者2个bool表达式，并且返回bool结果。其中AND和OR是双目运算符，NOT是单目运算符。
Lambda表达式
Lambda表达式又称为是匿名函数，没有函数名称，只有参数列表和计算表达式。Lambda表达式可以用于让用户自定义处理逻辑，相当于一种UDF。通常在使用中，lambda表达也可以作为函数的参数传入函数，然后在函数内调用该lambda表达式迭代处理数据。
一个简单的lambda表达式如：x -> x + 1，表示接受一个参数x，返回x+1。
WHERE子句
Where子句后跟一个bool表达式，表示从表中读取数据后，会对每一行数据评估该bool表达式的结果。如果表达式评估结果为true，则该行数据就会传递后给后续的算子做进一步计算；如果评估结果为false或者位置状态，则丢弃改行数据，不再参与后续计算。
Bool表达式可以是一个简单的表达式，例如a=1；也可以是嵌套多层转换函数组成的bool表达式，例如a%10=1；或者由逻辑运算符连接起来的逻辑表达式，例如 a AND b。Bool表达式中的函数都是转换函数，不能是聚合函数。
Where子句的操作发生在聚合计算之前。Where 子句非常重要，可以帮助减少读取和计算的数据量，常常用于加速计算。在优化器中，有一些规则帮助把过滤条件尽可能的下推到叶子结点。filter下推是一种非常常用且有效的加速手段。
Where子句的一个样例，获取学生中所有的男生信息：
SELECT * FROM student where gender = ‘male’
HAVING子句
Having子句常常跟随group by子句出现。Having子句类似于where，是一个bool表达式。但Having应用于group by聚合计算之后，每个分组的计算结果会用来继续评估Having表达式的结果，只有满足having子句为true的分组，才能输出到后续的算子。
Having和where的区别在于：1， where在group by之前完成，having 在group by之后执行；2，where应用于每条原始数据上，having应用于group by分组聚合结果上。
理论上而言，即便没有group by计算，只有一个全局聚合操作，能够使用having，但是全局聚合的结果只有一样，那么这个时候having的作用就是判断这一行结果是否满足条件。例如select avg(latency) as avg_latency from log having avg_latency > 100
即便没有group by没有任何聚合函数，select中只有原始列或者转换函数的结果时，也可以用having，但这时候having就没有意义了，因为having中的条件是可以合并到where中的。例如select * from log where latency > 10000000 having status>200，完全可以写成select * from log where latency > 10000000 and status>200。
总而言之，having子句一般和group by语句联合使用，用于过滤分组聚合后的结果，筛选出分组聚合结果满足特定条件的某些分组。
Having子句的一个样例，求访问日志中平均延时大于10秒的站点及其延时：
SELECT avg(latency), host from accesslog GROUP BY host HAVING avg(latency) > 10
having子句的执行发生在group by之后，order by之前。顺序参考图2-2。
Order By子句
Order by子句包含一个或多个表达式，用于排序输出的结果。在order by中可以指定多个表达式，每个表达式指定排序方式，可以升序，也可以降序，默认是升序排列。排序时多个表达式从左到右依次评估。当左侧表达式评估出来的多个行结果一样时，会评估右侧表达式的值用于排序。例如order by key1 asc, key2 desc 表示按照key1升序排列，当key1相同时，按照key2降序排列。
Order by子句的一个样例，学生按照分数排序：Select * from student order by score asc
Limit 子句
Limit子句用于限制返回结果的行数。当之前的算子输出行数超出了limit指定的行数时，会丢弃超出的部分。由于Limit算子可以减少传递给下游的数据量。因而在优化中非常有用。例如order by和limit算子合并，在排序阶段就大大减少用于排序的数据量；把limit算子尽可能向叶子结点的方向下推。通常而言，limit算子会和order by联合使用。如果单独使用limit算子，输出结果不保证顺序，也就是说每次执行会获得不同的结果。和order by联合使用时，才能保证每次查询结果的一致性。
一个查询样例：SELECT * FROM student limit 100，表示获取100个学生信息。
通常而言，limit限定最多的返回行数。在MySQL中，还可以通过limit offset,line这个翻页语法，从第offset行开始，读取line行结果。而对于OLAP引擎而言，支持翻页并不现实，因为每次提交翻页请求，都是要计算一遍SQL，获得结果后再翻页返回，因而代价非常大。除非OLAP引擎把计算结果缓存在内存中，等待下次翻页获取。MySQL之所以能够支持翻页，一方面是因为MySQL的查询一般是事务性查询，另一方面数据量比较小，翻页的代价不大。
多个表间操作
在一层SQL查询中，数据源可以是一个表，也可以是多个表。对多个表进行操作并产出一个新的表。表之前的操作包括连接操作（join），集合操作（set）。
Join
Join可以把多个表（左右）连接成一个表，根据一定的条件让多个表对应的行输出到同一行，左表的一行数据和右表的一行数据连接成一行，左表和右表的列都会出现在结果中。Join的操作类型包括Inner Join、Left Join、Right Join、Full Join、Cross Join。各种Join的策略参考下图所示，Inner Join输出左右两表的交集，即满足连接条件的行，输出结果中，左表和右表的列都不为null。Left Join不管左表是否满足条件都输出，而右表只输出满足条件的行，其他行以null输出。Right Join和Left Join相反。Full Join同时输出左右表，对于满足条件的行，输出对应的左右表连接后的结果，对于不满足的行，输出左表(右表)的行，同时右表(左表)以null输出，相当于集合了Left Join和Right Join的特性。Cross Join没有链接条件，输出两个表的笛卡尔积。
Join操作是SQL所有算子中，计算复杂度最高的算子之一。针对Join的优化是SQL中一个非常重要的课题，Join的执行方式、执行顺序，左右表的大小等因素都会影响Join的性能。在后续章节中，会介绍基于规则的优化器和基于代价的优化器来优化Join算子。
图2-7 不同的Join类型
Set
Set操作是一种集合操作，集合的元素是行，用于把多个表前后拼接成一个表。拼接后不改变列的个数，原表中的一行，原样输出到结果中，参与set操作的左右表的列个数和类型必须保持一致。set操作和join操作的差别在于，join是左右表列与列按照连接条件拼接成一行，set操作是行与行拼接成更多行，不改变原始一行的内容。Set操作包括Union、Intersect、Except。分别代表并集、交集、差集。
集合的理论基础是集合代数，默认场景下，集合是不包含重复元素的。集合运算符后可以添加distinct或者all关键字，分别表示结果去重和不去重。默认是去重的结果。例如table1 union table2，输出两个表去重后的结果。
嵌套查询
在一个最简单的查询中，from语句指定了要从什么表中读取数据。在from中，最简单的情况是指定一个表，从这一个表中读取数据出来；稍微复杂的情况是from多张表的join结果；再复杂一点，from的来源，根本不是一张表，而是另一个查询的输出结果。我们都知道，一个SQL查询的结果也能成为一个新的表，这个新的表可以作为另一个查询的输入。这就是关系模型的优秀之处，任何关系经过计算后，形成第二个关系，再经过第二次计算，则形成了第三个关系。理论上，表活着关系可以经过无数轮计算，组成一个单向流动的链表。这就是嵌套查询。嵌套查询的结果，可以像一张普通的表一样，参与下游的计算、join、union等。
在SQL中，写嵌套查询有两种形式，第一种，最直观的就是from 后写一个子查询，并且把子查询用()包含起来，形成一个完整的整体，例如:
select abc from ( select abc from table）
()内部的即为一个完整的子查询。
第二种是with语法：
with temp_table1 as (select abc from table),
temp_table2 as (select abc from temp_table1)
select * from temp_table2通过with语法，可以定义多个视图，视图用括号左右包含起来。多个临时表之间，用逗号分隔。with语句的最后不需要加逗号，直接跟select语句。
with语句比较简洁，可以做到每一行只定义一个视图，视图的定义和使用可以分开到不同的地方，在使用时只需要引用视图的表名即可。定义一次视图甚至可以多次引用。而嵌套式查询，临时表的定义和使用放在一起，每使用一次就需要定义一次。外层的查询语句内部是一个子查询，from关键字在整个SQL语句的中间位置，导致外层查询的前半部分在子查询前边，后半部分在子查询后边，同一层查询语意被一个复杂的字查询分隔开，不利于对SQL语意理解。因此在使用前套查询时，推荐使用with语法。
with查询中定义一个视图，在后续可以引用多次该视图。视图并不是物化视图，如果引用多次视图，会展开执行多次。
子查询表达式
子查询除了作为一种关系在from语句中被引用。还有一种用途是作为表达式被引用，例如where语句中的引用子查询结果作为一个集合，判断某个值和这个集合的关系。子查询表达式和嵌套查询的区别在于，子查询表达式在plan中扮演一个表达式，而嵌套查询扮演一个视图。在子查询中，可以引用外层查询的属性，而外层查询中，不能引用子查询的属性。
除了from后，嵌套子查询可以出现在SQL的几乎每个位置。
- 出现在select输出结果中，
select (select 1) as one from student。 - 出现在where中，select name from student where id in (select id from applied)。
对于判断外层查询属性和内层子查询结果之间关系的判定方式，有几种方式：
- ALL 表示外层表达式要满足子查询的所有结果。
- ANY表示外层表达式需要满足子查询的至少一个结果。
- IN 等同于ANY。
- EXISTS表示至少有一行结果返回。
按照输出结果，子查询包括三种类型：
- 标量子查询（scalar subquery）：只返回一行一列结果。
- 多行输出子查询：输出多行一列，或多行多列。
- exists子查询：输出结果是bool类型。
按是否引用外层查询的属性，分为：
- 关联子查询：子查询中引用到了外层查询的属性。
- 无关联子查询：子查询没有引用外层查询的属性。
标量子查询表达式
标量子查询的结果只有一行一列一个值。针对这个特性，可以有很多优化手段。在后续的优化器章节会给出介绍。理论上来说，对于外层查询的每一行数据，都需要去执行一次子查询表达式。但是这里还有些不同点，对于相关子查询和不相关子查询的处理是不同的。对于不相关子查询，子查询没有引用外部的任何列，因此对于外部的每一行数据，子查询的执行结果都是相同的，因此执行一次即可。这种场景下，子查询只会执行一次。
标量子查询可以用于case表达式、select子句、where子句、order by子句、函数的参数等。由于标量子查询只返回一行一列，因此可以当成单个值使用。
scalar 子查询在被使用之处，只能要求出现一个结果，但并未在语法上约束子查询返回一个结果。用户可以写一个聚合子查询只返回一个结果，或者用limit 1限定返回一个结果；也可以写一个可能返回多行数据的SQL，只有在执行时，如果实际返回多行结果则会报错。
例如select count(1) from log where latency >= (select avg(latency) from log)，子查询中时聚合函数，一定会返回一行结果，因而可以正常执行。但加入用户写这样一个子查询select count(1) from log where latency >= (select (latency) from log)，则存在三种可能，返回0行结果，返回1行结果，返回大于1行结果。如果返回0行结果，则以null作为子查询的输出，如果返回大于1行结果，则运行报错。因为标量子查询的外层需要一行一列输入。或者说，标量子查询之所以称为是标量子查询，是因为外层查询要求子查询输出一行一列，而不是子查询本身通过语法或者实际运行只能得到一行一列结果。
除了where中，还可以在select中，例如select *, (select max(latency) from log )from log，在每一行都输出最大的latency值。如果写成select *, (select latency from log )from log则会报错。
也可以作为函数参数:select *, abs((select max(latency) from log) )from log。基本上，在需要单个值的地方就可以使用标量子查询。
子查询用于判断集合从属关系
in和not in用于判定外层查询的属性是否属于内层子查询结果的集合内。例如：
select * from course where student_id in (select student_id from student where apply_year='2018')
in和not in除了用于子查询，还可以指定一个list常量，例如：
select * from course where student_id in（1，2，3）
Exists子查询用于判定是否是空集合
Exists子查询检查子查询是否有输出结果，如果有至少一行结果，则判定为true，否则判定为false。通常Exists子查询被用于关联子查询，也就是说针对外层查询的每一行数据，判定Exists子查询的结果。 如果是非关联子查询，则对于外层查询的每一行数据，Exists的结果都是一行的结果，这样做没有意义。
例如，SELECT name FROM websites WHERE EXISTS ( select count from access_log WHERE websites.id = access_log.site_id and count > 100) 表示输出访问日志中count > 100的网站的名字。
not exists是相反的语意，表示子查询的结果为空集合。
Exists查询也可以用in语法来表达，in语法表示判断某一列的每一行是否在子查询的输出结果中。例如上述的逻辑，可以用in语法来表达：SELECT name FROM websites WHERE id in ( SELECT site_id from access_log where count > 100)。显然，在in查询中，子查询是不相关查询，因此，子查询只需要执行一次即可，因而查询效率较高。
子查询用于比较级和数值大小关系
外层查询可以和子查询的结果进行对比，对比的运算符包括<,>, <=, >=, =, <>。子查询的结果可以包含修饰符SOME，ANY，ALL。外层表的每一行会逐个和子查询结果的每一行进行对比，返回true或者false。如果是SOME或者ANY修饰符，那么只需要至少1行对比为true即可。如果是ALL修饰符，那么就需要所有的行对比结果都为true才行。=ANY的语义和IN相同。<>ALL的意义和NOT IN相同。
一个样例：SELECT Num FROM Test2 WHERE Num > ANY (SELECT Num FROM Test1)表示Test2这张表中的Num，如果在Test1表中存在比之小的值，则该行数据满足条件，会输出到下游算子中。
量化子查询会在优化器章节进行深入的介绍其优化方法。
子查询用于判定集合是否包含重复值
和exists类似，还有一个unique关键字，用于判断子查询的所有行是否包含重复值，如果包含重复值，那么返回false；如果不包含重复值，则返回true。
例如：
select * from log where unique (select projectName from log)
子查询的实际运行方式
一般来说，上述几种子查询，如果是非关联子查询，每一行判定结果都一样，意义不是很大。所以，通常上边的这些子查询都会是关联子查询，这样才会每一行结果不一样。而关联子查询一般会在plan优化阶段，转化为join计算。
子查询是一种语法表示形式，在物化plan中，是没有子查询这种执行方式的，一般需要需要转化为等价的关系代数表达形式。
除了常规的几种join（left，right，full，cross），还有两种特殊的join形式，semijon和antijoin。semijoin用于in或exists查询，表示只要满足条件，就输出左表的数据，每行数据只输出一次。antijoin用于not in或not exists，表示只要不满足条件，就输出左表的数据，每行数据只输出一次。虽然semejoin和antijoin有等价的表示形式，但是这两种特化的表达形式可以获得更好的执行性能。
Null 处理
对于常规的数据处理是很简单的，但是往往有一些非法的case需要处理。null就是一个典型的场景。一个非法值，或者不知道具体值的值就用null表示。
在聚合函数中，输入null值的处理在上文已经描述过了。在这个章节中，主要考虑转换函数输入null的情况。
对于一个转换函数或者转换表达式，如果返回值是非boolean的情况，例如代数运算，如果输入是null，那么输出也是null。
如果转换函数或者转换表达式返回值是boolean的情况，例如一个比较表达式，正常情况输出只有true、false两种场景，如果输入的一个参数是null，无法明确判定是true还是false的情况下，则需要第三种状态，即unkonwn状态用于判断。为什么简单粗暴的输出null呢？这是因为，unknown代表的信息量要大于null。在后续的计算中，即便存在unkonwn状态，也能过推断出结果。
针对and、or、not逻辑表达式，当出现unkonwn时，甚至可以借助短路求值的思想，获得最终结果，无需关心unknown到底是true还是false。
AND： 如果是true and unknown，结果取决于unkonwn，那么结果就是unkonwn；如果是false and unkonwn，无论unkonwn是true还是false，结果都是false。
OR：如果是true or unkonwn，无论unknown是true还是false，结果都是true；如果是false or unknown，结果取决于unknown，结果仍为unknown。
NOT： not unknown，结果仍是unknown。
Is null语法和is not null语法：is null可以判断一个表达式是否是null，is not null正好相反。同时在SQL标准中，还有is unknown语法和is not unknown语法，不过这两个关于unknown的语法并不是所有的SQL引擎都支持。
在用于分组操作时，例如group by，distinct，union等， 如果指定的列中包含null，那么所有对应null的行都会作为一个分组。这一点和计算表达式中的表现是不同的，例如判断null=null，那么输出将是unknown，而不是true。
Unnest语法
在SQL中，生成新的数据依赖于表达式或者函数，在上文中提到，函数分成两种类型，分别是标量转换函数，另一种是聚合计算函数。标量计算函数把一行输入数据转换成一行一列输出结果；聚合计算函数把多行输入数据转换成一行一列输出结果。如果我们要输出一列转换成多列，那么可以通过多个表达式实现。如果我们需要把一行转化成多行，该怎么处理呢？在这种需求场景下，就用到了Unnest语法。
Unnest语法可以把一行数据转换成多行数据。例如输入数据是一个数组类型，那么可以把数组中的每一个元素作为一行结果输出。语法如：
SELECT element FROM (VALUES ( ARRAY[1,2,3]) ) as t(element)。输出结果为3行，分别是1、2、3.。
其他SQL语法
除了SELECT语法，还有其他的语法例如INSERT/CREATE 等DDL语句。
小结
本文介绍了SQL和查询相关的一些核心语法规则，有助于读者了解SQL能够完成哪些方面的计算。在后续的章节中，我们继续了解SQL语言如何转化成抽象语法树的。
