# 大数据体系和 SQL

# 火山引擎

例子来源：大规模机器学习平台架构设计

# 计算

计算方面体现在高性能计算，需要考虑的因素

• 新硬件：CPU，GPU，多种类型网卡
• 虚拟化产生损耗：网络和容器会进行一定的虚拟化，存储的分层池化也会带来负载均衡的问题
• 繁多的分布式训练框架：由于机器学习平台的用户很多，并且不同任务依赖的分布式训练框架也不同（数据并行的框架，模型并行的框架，HPC 框架，其他框架），不同训练框架有各自的调度和资源要求，给底层基础设施带来很多挑战

# 存储

对于任何一个系统，存储都是必不可少的，而对于机器学习来说，面临的挑战也有很多

• 高性能和扩展性：随着硬件的计算性能越来越好，为满足读数据的高吞吐量，对于存储的要求非常高，比如需要面对达上百 Gb/s 的单租户带宽吞吐以及很小的延迟，存储的容量也是高达 PB 级别。为了提升模型训练的效率，需要数千个计算实例能同时访问的高性能共享存储。
• 易用性和安全性：对于用户而言，最重要的就是简单方便，能够传输通畅，数据上下云，部分数据对安全性也有要求，所以需要隔离存储；在使用框架的时候为了能够读写存储能够像读本地文件一样方便，就需要存储接口友好，代码零修改，兼容 POSIX
• 成本：尽可能低的成本

# 调度

基于高性能的硬件，调度首先需要对资源（计算 + 存储）进行池化，火山引擎机器学习平台有一个大的计算池，里面有大量的 GPU 和 CPU，在保证不同用户计算容器间的隔离前提下，不同客户共享整个资源池，从而提高集群的利用率。

机器学习的调度需求比较复杂。比如一次分布式训练，有 Worker、Server 和 Scheduler 角色的实例。在调度时，它需要 Gang 调度的能力，所有实例（或其中某一种角色的实例）要么都起来，要么都不起来。同时在训练过程中还需要网络的亲和性。例如同一个分布式训练的容器，申请到的资源能在一台机器肯定是最好。申请多台机器时，这些机器之间的网络连接肯定是越近越好。所以在调度上我们有一些相应的调度策略，包括 多队列调度（排队、抢占）、Gang 调度、堆叠调度等。

# 应用

分布式训练，加速方式主要从计算，通信，显存三个角度考虑

• 计算：因为训练一般都用 GPU，火山引擎有一个高性能算子库，自主研发了很多中细粒度高性能算子，它们的性能往往较于好的开源实现有非常明显的提升
• 通信：火山开通了 BytePS 通信框架，同时利用了 CPU 和 GPU 两种异构资源来加速通信，在对拓扑的探测上做了细致的智能优化，并且支持异步和同步两种训练模式
• 显存：主要针对超大模型场景，开源了 veGiantModel，支持混合并行的策略，包括数据并行，Tensor 并行和流水线并行；可根据参数量、计算量自动切分流水线。veGiantModel 的底层是基于 BytePS 做加速的。

# 批式计算和流式计算

这个就好比分组加密和流密码，分组加密就是批式计算，等着块生成了统一处理，而流密码则实时处理。

# 交互式分析引擎

# 背景

在开源大数据领域，交互式引擎是后来才出现的，最初，大数据领域数据处理引擎以 MapReduce 为主，但是 MapReduce 引擎采用了批处理设计理念，数据处理性能不行

• IO 密集型：Map 阶段中间结果写磁盘，Reduce 阶段写 HDFS，多个 MapReduce 作业之间通过一个共享存储系统 HDFS 交换数据
• 任务调度和启动开销大：大量任务需要分布式调度到各个节点上，且每个任务需要启动一个 Java 虚拟机运行
• 无法充分利用内存：MapReduce 是十多年前提出的分布式技术，当时内存的价格很高，所以设计理念是充分利用磁盘，而如今不再如此，新型计算引擎可以尝试通过内存加速
• Map 端和 Reduce 端均需要排序：这是其本身设计理念决定的，使得其无法很好地应对交互式处理场景

为了克服 MapReduce 地性能缺陷，Google 提出了新型交互式计算引擎 Dremel，它构建于 Googel 地 GFS（Google File System）等系统之上，支撑了 Google 的数据分析服务 BigQuery 等诸多服务。Dremel 的技术亮点主要有两个：一个是采用了 MPP 架构，使用了多层查询树，使得任务可以在数千个节点上并行窒息感和聚合结果；二是实现了嵌套数据的列式存储 ，避免读取不必要的数据，大大减少网络和磁盘 IO。

# 分类

交互式计算引擎是具备交互式分析能力的分布式大数据计算引擎，它常用于 OLAP 场景。OLAP 有很多实现方法，根据存储数据的方式不同可以分为 ROLAP，MOLAP，HOLAP 等。

• ROLAP：基于关系型数据库的 OLAP 实现（Relational OLAP）。它以关系型数据库为核心，以关系型结构进行多维度的表示和存储。它将多维结构划分为两类表：一类是事实表，用来存储数据和纬度关键字；另一类是纬度表，即对每个纬度至少使用一个表来存放纬度层次，成员类别等纬度描述信息。ROLAP 的最大好处是可以实时的从源数据中获取最新数据更新，以保持数据实施性，缺点在于运算效率比较低，用户等待响应时间比较长。
• MOLAD：基于多维度的 OLAP 实现（Multidimensional OLAP）。它以多位数据组织方式为核心，使用多纬数据存储数据。多维数组在存储系统中形成 数据立方体（Cube） 的结构，此结构是经过高度优化的，可以最大程度地提高查询能力。MOLAP 的优势在于借助数据多纬预处理显著提高运算效率，主要额缺陷在于占用存储空间和数据更新有一定延滞。
• HOLAP：基于混合组织的 OLAP 实现（Hybrid OLAP），用户可以根据自己的业务需求，选择哪些模型采用 ROLAP，哪些采用 MOLAP。一般来说，将不常用或需要灵活定位的分析使用 ROLAP 方式，而常用，常规模型采用 MOLAP 实现。

Impala 和 Presto 可用于 ROLAP 场景，而 Druid 和 Kylin 常用于 MOLAP 场景。也有人将 Druid 规划到 “HOLAP” 范畴，因为它不会进行预计算，因此是一种 “ROLAP”，但同时它此用了列式存储，且为非关系型模型，因此也是一种 “MOLAP”。

# 常见开源实现

在大数据生态圈中，主流的应用于 ROLAP 场景的交互式计算引擎包括 Impala 和 Prosto，它们的特点如下：

• Hadoop native（跟 Hadoop 生态系统有完好的结合）
  • 可直接在 Hive Metastore 对接，处理 Hive 中的表
  • 可直接处理存储在 HDFS 和 HBase 中的数据
• 计算与存储分析：它们仅仅是查询引擎，不提供数据存储服务，所有要处理的数据都存储在第三方系统中，比如 Hive，HDFS 和 HBase 等
• MPP 架构：采用经典的 MPP 架构，具有较好的扩展性，能够对应 TB 甚至 PB 级别数据的交互式查询需求
• 嵌套式数据存储：支持常见的列式存储格式，比如 ORC（仅 Presto 支持）和 Parquet（Impala 和 Presto 均支持）

主流的应用于 MOLAP 场景的交互式计算引擎包括 Druid 和 Kylin，它们的特点如下：

• 数据建模：将数据分为纬度和度量两类，且所有查询必须针对以上两类列进行
• 数据预计算：为了提高数据查询效率，MOLAP 引擎一般会根据纬度和度量列，预先生成计算结果

# YARN

# 背景

既然说最初是为了改善 MapReduce 的实现，那么有何需要改善的？MapReduce1 中，有如下局限性：

• 扩展性差：jobtracker 兼顾资源管理和作业控制跟踪功能跟踪任务，启动失败或迟缓的任务，记录任务的执行状态，维护计数器），压力大，成为系统的瓶颈
• 可靠性差：采用了 master/slave 结构，master 容易单点故障
• 资源利用率低：基于槽位的资源分配模型，槽位是一种粗粒度的资源划分单位，通常一个任务不会用完一个槽位的资源，hadoop1 分为 map slot 和 reduce slot，而它们之间资源不共享，造成一些资源空闲。
• 不支持多：不支持多种计算框架并行。

YARN 很好解决了 MapReduce1 中的局限性：yarn 基本思想：一个全局的资源管理器 ResourceManager 和与每个应用对应的 ApplicationMaster，Resourcemanager 和 NodeManager 组成全新的通用系统，以分布式的方式管理应用程序。

# 组件

ResourceManager

• 处理客户端请求
• 启动 / 监控 ApplicationMaster
• 监控 NodeManager
• 资源分配与调度

APPlicationMaster

• 程序切分
• 为应用程序申请资源，并分配任务
• 任务监控与容错

NodeManager

• 单个节点上资源管理
• 处理来自 ResourceManager 的命令
• 处理来自 ApplicationMaster 的命令

Container
对任务运行环境的抽象，封装了 CPU、内存等多维资源以及环境变量、启动命令等任务运行相关信息

# Kubernetes

kubernetes，简称 K8s。是一个开源的，用于管理云平台中多个主机上的容器化的应用，Kubernetes 的目标是让部署容器化的应用简单并且高效（powerful）,Kubernetes 提供了应用部署，规划，更新，维护的一种机制。当部署完 kubernetes，便拥有了一个完整的集群。

特点

• 可移植：支持公有云，私有云，混合云，多重云（multi-cloud）
• 可扩展：模块化，插件化，可挂载，可组合
• 自动化：自动部署，自动重启，自动复制，自动伸缩 / 扩展

组件

一个 kubernetes 集群是由一组 node 机器组成，这些 node 上会运行由 kubernetes 所管理的容器化应用，每个集群至少有一个工作节点。

工作节点会托管所谓的 Pods，而 Pod 就是作为应用负载的组件。 控制平面管理集群中的工作节点和 Pods。 为集群提供故障转移和高可用性， 这些控制平面一般跨多主机运行，而集群也会跨多个节点运行。

# 关系代数

就说一下 join 吧

例如，现在有一个任务让你查询某同学借阅的图书书名及作者，假设在数据库中有 book 表和 borrow 表，要查询图书的书名和作者在 book 表中，但是查找的人是这名同学，所以条件是借阅人为该同学，有关信息在 borrow 表中，因此待查询的对象为 book 表和 borrow 表，查询结果是部分属性列，我们想用选择和投影运算可以解决这个问题，可是这两个关系运算作用的对象应当为一个关系，为了解决这个问题，就可以用笛卡尔积使多个关系合并成一个关系；而连接运算就是在笛卡尔积运算的基础上进行某些选择的结果，根据定义，从两个关系的笛卡尔积中选取属性间满足一定条件的元组；大致分为

• 一般连接
• 等值连接
• 自然连接

# 一般连接

假设两个关系 R 和 S ， A 是 R 中的属性组， B 是 S 中的属性组，这两个属性列数相同，而且取值是可以比较的。

如果有需要计算 R 和 S 的一般连接，连接条件是 C<D ，首先计算两个关系的笛卡尔积， R 关系的每一个元组和 S 关系的每一个元组串接得到新关系 5 列 20 行，在此基础上进行筛选，提取 2、3、4、8 行即为最终结果。

分析有以下要点：

• 两个关系参与
• 计算笛卡尔积
• 比较两个关系中的属性组
• 找出属性间值的比较符合条件的元组

# 等值连接

等值连接运算从 R 和 S 的广义笛卡尔积中选择 R 关系在 A 属性组上的值等于 S 关系在 B 属性上值的元组，需要比较的通常是两个属性列是否相等，即 θ 为 = 。

对于前面的例子，如果将条件改为 C=D ，也就是查询关系 R 的 C 上和关系 S 的 D 上元素相等的元组进行连接，发现

其要点与一般连接不同的是需要选择属性组间值相等的元组。

在等值连接中有一种特殊情况，也可以比较两关系间某列相同元素的元组，比如

# 自然连接

在上一个例子中，可以发现属性列值重复存储，这样没有意义，可以去掉重复的一列，保留一列 B

可以不用注明属性属于哪一个关系，连接运算符下面不用注明选择的条件，这种特殊情况的等值连接被称为自然连接，故给出定义，从 R 和 S 的广义笛卡尔积上选择 R 关系和 S 关系同名属性 B 上值相等的元组

# 外连接

在自然连接中，有时候左右两边部分元组的属性无法匹配，合成后直接被删除了，我们将它们称为悬浮元组，而对于外连接来说，相当于对于自然连接的一种扩充，分为左、右、全外连接。自然连接中丢弃的悬浮元组在外连接中会根据左右情况予以保留。

例如
学生表 (左)

成绩表 (右)

左外连接

右外连接

# 编译原理相关知识

# 词法分析

词法分析器在程序编译过程中所处的位置

Lexical Analyzer ，输入源程序，扫描器 Scanner 从左至右逐个字符地对源程序进行扫描，产生多个单词符号；单词符号的种类有

• 基本字（关键字）： begin 、 repeat 、 for 等程序语言定义好的
• 标识符：用来表示各种名字，如变量名、数组名和过程名
• 常数：各种类型的常数
• 运算符： +、-、*、/
• 界符： ,、;、()、space符

输出的单词符号的表示形式为 (单词种别,单词自身的值) ，单词种别通常用整数编码表示

• 若一个种别只有一个单词符号，则种别编码就代表该单词符号，假定基本字、运算符、界符都是一符一种。
• 若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值
• 标识符单列一种，标识符自身的值表示成按机器字节划分的内部码。
• 常数按类型分种，常数的值则表示成标准的二进制形式

# 如何设计

# 扫描缓冲区

两个指针分别指向起点和搜索位置，考虑到单词长度超过缓冲区的长度，造成存储不连续，可以分为两个半区互补使用。

如果某单词的结尾在一个半区找不到，那么在下一个半区一定能找得到，所以半区的长度就是程序语言允许的单词最大长度，比如某编程语言的标识符长度不超过 128 ，就可以推断出编译器的扫描缓冲区总长度为 256 。

# 状态转换图

状态转换图是一张有限方向图，节点代表状态，用圆圈表示，状态之间用箭弧连接，上面的标记（字符）代表射出的结点状态下可能出现的输入字符或字符类，一张转换图只包含有限个状态，其中有一个为初态，至少有一个终态。
状态转换图可用于识别一定的字符串，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于 α ，则称 α 被该状态转换图所识别。

终态上的 * 代表最后一个输入的字符不属于刚才读入的单词，将其退回去。

几点限制，不必使用超前搜索

• 所有基本字都是保留字，用户不能用它们作自己的标识符
• 基本字作为特殊的标识符来处理，使用保留字表
• 如果基本字、标识符和常数（或括号）之间没有确定的运算符或界符作为间隔，则必须使用一个空白符作间隔

# 语法分析

语法分析正是建立在词法分析的基础上，以词法分析识别出的正确单词符号串为输入，判断是否符合相应的语法规则，同时进行错误处理，为语义分析和后续步骤做准备。在编译的过程中处于核心地位。执行语法分析的程序称为语法分析程序，也称为语法分析器。

那么何为文法？

以前上编译原理课，经常说自上而下的语法分析， 文法是描述语言的语法结构的形式规则（即语法规则），这些规则必须准确且可理解。文法通过对高级语言的语法规则进行形式化的描述，从而能够更加精确的描述高级语言程序的语法结构，适合描述高级语言语法规则的文法是上下文无关文法。

选用哪条文法规则？

比如已知文法

E → T|E+T|E-T
T → F|T*F|T/F
F → (E)|i
让你给出下列表达式的最左最右推导
i*(i+i)
i+i*i

思想
1. 输入待推导的表达式
2. 对表达式字符串进行第一行文法判定

• 判断是否有 + or - 运算符括号内除外，是则输出 E→E+T or E→E-T ， + 之前的所有字符返回进行 2 ， + 之后的字符进行 3 ；否则进行下一步。
• 输出 E→T ，所有字符串进行 3 。

3. 对表达式字符串进行第二行文法判定

• 判断是否有 * or / 运算符括号内除外，是则输出 E→E*T or E→E/T ， + 之前的所有字符返回进行 2 ， + 之后的字符进行 3 ；否则进行下一步。
• 输出 T→F ，所有字符串进行 4 。

4. 对表达式字符串进行第三行文法判定
第一个字符是否为 ( ，是则输出 F→(E) ，然后将该字符串的 ( 、 ) 删除，返回 2 ；否则输出 F →i ，操作结束。

针对 LL1 文法

比如对于自上而下的语法分析来说，无论是递归下降子程序法还是非递归预测分析法，他们都只能处理 LL1 文法。

根据 LL1 文法的三个条件

• 需要消除左递归包括间接左递归
• 需要消除回溯
• first 集合和 follow 集合不相交

所以首先需要重写文法，消除左递归，避免陷入死循环，提取左因子，避免回溯。

我们知道，直接消除左递归的一般形式为

p->pα|β

p->βp'
p'->αp'|ε

消除间接左递归
对于给定文法 G(S)

S->Qc|c
Q->Rb|b
R->Sa|a

对于此文法，不存在直接左递归，但是 S、Q、R 都是间接左递归的。给出一个文法消除左递归的条件

• 不含以 ε 为右部的产生式
• 不含回路

满足这两个条件比较容易，接下来的思路就是将间接转化为直接，层层带入，转化为只关于 S 的闭包。
比如，把文法 G 中的所有非终结符按任一种顺序排列 P1、 P2、...Pn ，按此顺序执行：
从上而下考察每一个产生式 Pi(i∈[i,n]) ，将之前的非终结符号 Pj(j∈[1,i-1]) 带入 Pi (如果可以带入)；然后可以得到 Pi 的一个产生式，如果存在直接左递归，则消除，否则，开始新的一轮循环，考察 Pi+1 。

for(从1到n的每个i){
	for(从1到i-1的每个j){
		把形如Pi->Pγ的产生式改成Pi->δ1γ|δkγ|δ2γ|...|δkγ，其中Pj->δ1|δk|δ2|...|δk是关于Aj的所有产生式
	}
	消除关于Pi产生式的直接左递归
}

S->Sabc|abc|bc|c
Q->Sab|ab|b
R->Sa|a

消除回溯

为了消除回溯必须保证，对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应该是确信无疑的。

FIRST 集合：假设 G 是一个不含左递归的文法，对 G 的所有非终结符的每个候选 α 定义它的终结首符集 FIRST(α) 为： FIRST(α)={a|α=*=>a...,a∈Vt} ，特别的，若 α=*=>ε ，则规定 ε∈FIRST(α)

如果非终结符 A 的所有候选首符集两两不相交，即 A 的任何两个不同候选 αi 和 αj ， FIRST(αi)∩FIRST(αj)=Ø ；当要求 A 匹配输入串时， A 能根据它面临的第一个输入符号 a ，准确地指派一个候选去执行任务，这个候选就是那个终结首符集含有 a 的候选式 α ，它是唯一的，因为任何候选首符集两两不相交。

这样就可以根据当前的终结符找一个唯一可能的候选，可是一个文法可能最开始的时候并不具备一个非终结符的多个候选首符集两两不相交这个条件，可以提取公共左因子来进行改造，来使它具备这个条件。

经过反复提取左因子，就能把每个非终结符 (包括新引进者) 的所有候选首符集变得两两不相交。

FOLLOW 集合：假定 S 是文法 G 的开始符号，对于 G 的任何非终结符 A ，我们定义 FOLLOW 集合
FOLLOW(A)={a|S=*=>...Aa...,a∈Vt} ，也就是 FOLLOW(A) 集合是所有紧跟 A 之后的终结符或 # 所组成的集合（ # 是句尾的标志），称 FOLLOW(A) 是 A 的随符集。

计算所有非终结符号 A 的 FOLLOW(A) 集合时，不断应用下面的规则，直到再没有新的终结符号可以被加入到任意的 FOLLOW 集合中为止。
注意：当 A 是最右部的时候，将 # 加入到 FOLLOW(A) 中

• 将 # 放到 FOLLOW(A) 中， A 是文法的开始符号。
• 如果存在一个产生式 A→αBβ ，那么 FIRST(B) 中除 ε 之外的所有符号都在 FOLLOW(B) 中。 FOLLOW(B) 是求跟在 B 后的终结符或 # 组成的集合，因此对于跟在 B 后的 β ，它的 FIRST 集合就是 FOLLOW(B) 的子集。
• 如果存在一个产生式 A→αB ，或存在产生式 A→αBβ 且 FIRST(B) 包含 ε ，那么 FOLLOW(A) 中的所有符号都在 FOLLOW(B) 中。对于 A→αBβ ，且 β 多步推导出 ε ，那么可以用 αB 替换 A ， B 后面紧跟的字符就是 A 后面紧跟的字符。

详情请见：消除回溯

# 抽象语法树

当在开发语言时，可能在开始的时候，选择 LL1 文法来描述语言的语法规则，编译器前端生成 LL1 语法树，编译器后端对 LL1 语法树进行处理，生成字节码或者是汇编代码。但是随着工程的开发，在语言中加入了更多的特性，用 LL1 文法描述时，感觉限制很大，并且编写文法时很吃力，所以这个时候决定采用 LR1 文法来描述语言的语法规则，把编译器前端改生成 LR1 语法树，但在这个时候，你会发现很糟糕，因为以前编译器后端是对 LL1 语树进行处理，不得不同时也修改后端的代码。

抽象语法树的第一个特点为：不依赖于具体的文法。无论是 LL1 文法，还是 LR1，或者还是其它的方法，都要求在语法分析时候，构造出相同的语法树，这样可以给编译器后端提供了清晰，统一的接口。即使是前端采用了不同的文法，都只需要改变前端代码，而不用连累到后端。即减少了工作量，也提高的编译器的可维护性。

抽象语法树的第二个特点为：不依赖于语言的细节。在编译器家族中，大名鼎鼎的 gcc 算得上是一个老大哥了，它可以编译多种语言，例如 c，c＋＋，java，ADA，Object C， FORTRAN， PASCAL， COBOL 等等。在前端 gcc 对不同的语言进行词法，语法分析和语义分析后，产生抽象语法树形成中间代码作为输出，供后端处理。要做到这一点，就必须在构造语法树时，不依赖于语言的细节，例如在不同的语言中，类似于 if－condition－then 这样的语句有不同的表示方法。

其流程即是词法分析和语法分析，这两步是从代码生成抽象语法树的关键所在

• 词法分析，也叫扫描 scanner
  它读取我们的代码，然后把它们按照预定的规则合并成一个个的标识 tokens。同时，它会移除空白符、注释等。最后，整个代码将被分割进一个 tokens 列表（或者说一维数组）。当词法分析源代码的时候，它会一个一个字母地读取代码，所以很形象地称之为扫描 - scans。当它遇到空格、操作符，或者特殊符号的时候，它会认为一个话已经完成了。
• 语法分析，也称解析器
  它会将词法分析出来的数组转换成树形的形式，同时，验证语法。语法如果有错的话，抛出语法错误。当生成树的时候，解析器会删除一些没必要的标识 tokens（比如：不完整的括号），因此 AST 不是 100% 与源码匹配的。

# 分布式系统中 shuffle 的实现方式

MapReduce 的流程，执行过程分为三个环节

• map 阶段负责读取和解析数据，
• shuffle 阶段负责把对应的数据分发给相应的 reducer
• reduce 阶段则做汇总属于自己的数据并做最终业务逻辑处理。

大量 IO 导致 MR 性能不佳，如何优化 IO，我们需要关注 shuffle 阶段，整个 shuffle 阶段可以拆成两部分 shuffle write ， shuffle read 。

• shuffle write：mapper 把处理好的数据写到本地磁盘上，一般会以 reduce 好处理的形式组织
• shuffle read：reducer 把分散在各个 mapper 的数据读取到本地并合并

由于 shuffle read 在 shuffle write 之后，相对被动，上游写了多少文件，怎么写的，下游就只能相应去处理，所以重点关注 shuffle write，shuffle 的关键在于为每个下游独立输出数据，也就是把每个 reducer 的数据写在一起，能想到每个 mapper 都为每个 reducer 生成一个文件，再把对应数据都写进去，这就是 hash shuffle，分为两种机制，普通运行机制和合并运行机制，合并机制主要是通过复用 buffer 来优化 shuffle 过程中产生的小文件的数量，hash shuffle 不具有排序能力。

详见：shuffle 机制和原理分析

# group-by 与 join 的执行方式

MySQL 中，group by 用来分组，根据一个或多个列对结果集进行分组，使得对数据的分类更加精确；join 则用于获取两个表中匹配的关系

hive 是用来分析 hdfs 上的结构化数据的非交互式的数据仓库，解决数据冗余，hive 最终被编译成 MapReduce，通过 SQL 执行 MapReduce。

SELECT 

	name

   ,rank

   ,count(1) 	AS cnt 

FROM TEST 

GROUP BY name, rank;

Map 阶段的 key 即是 group by 字段的组合

t_student

t_rank

SELECT

	t.student

   ,tt.rank

FROM t_student t

JOIN t_rank tt

on t.rank_id = tt.rank_id;

# 常见的查询优化器

单机环境要求不高，对于大数据的应用，查询优化很重要

# Top-down Optimizer

论文中给出的实现是一个自顶向下（top-down）的递归算法，在每个递归节点上，可以通过某些规则决定 apply 规则的先后顺序。这样做的好处是，如果不希望遍历整个搜索空间，该策略能够在给定的有限步数内给出较优解。但代价则是代码逻辑变得十分难懂，也无法进行进行剪枝优化。从使用者的角度看，原本 top-down 优化中 apply rule 一定是先父节点、后子节点，而 Calcite 中的优化则是 “随机” 发生在 plan tree 的各个节点上，这也给编写 rule 带来了一些麻烦。

参考：Calcite 中新增的 Top-down 优化器，核心逻辑看不懂

<!-- ## Bottom-up Optimizer

# Rule-based Optimizer，RBO

• Rule
• Pattern

# Cost-based Optimizer，CBO

• 动态规划

# 交换律、结合律、传递性

# RBO 优化规则

• 列裁剪
• 谓词下推
• 传递闭包
• Runtime Filter（min-max filter，in-list filter，bloom filter）
• Join 消除
• 谓词合并

# CBO 相关概念

• 统计信息
  • Number of Distinct Value，NDV
  • Selectivity
  • Cardinality
• 代价模型

# 查询优化器的社区开源实践

# Apache Calcite

# Orca

# Volcano/Cascade 框架

• Memo
• AND/OR Graph
• Expression group
• Group expression
• Pattern
• Rule
• Branch-and-Bound Pruning
• Winner -->

# SQL 相关的前沿趋势

# 存储计算分离

我们知道 CPU 是由控制器、运算器和寄存器组成的，我们在运行一段程序的时候我们的指令是存储在我们的存储器的，我们所执行的每一个步骤都和存储分离不开。

计算和存储分离并不是现在才出现的一个新名词，在 20 年前就有 NAS - 网络附加存储这个东西，本质上也就是使用 TCP/IP 协议的以太网文件服务器。当时如果想要大规模的存储，就会让服务器将数据保存到 NAS 这个上面，但是 NAS 价格及其昂贵，并且扩展比较困难，NAS 也就不适用于高速发展的互联网应用。

这个时候谷歌摒弃了之前的观念 “移动存储到计算”，采取了 “移动计算到存储的观念”，将计算和存储耦合了，因为当时的网络速度对比现在来说慢了几百倍，网络速度跟不上我们的需要。在典型的 MapReduce 部署中计算和存储都在同一个集群中进行，比如后续的 hadoop。这里其实也就是用本地 IO 速度来替换网络传输速度。

随着技术的进步，我们的网络速度也越来越快，我们的瓶颈不再是网络速度，但是我们的磁盘 I/O 速度却没有明显的速度增长，计算和存储融合的架构缺点也再逐渐暴露，由于计算和存储耦合的缺点越来越多，并且网络速度越来越快，现在架构又在重新向计算和存储分离这一方向重新开始发展。

应用于数据库和消息队列。

参考：MySQL 存算分离解析（杂谈） & 聊聊计算和存储分离

# HSAP, HTAP, HTSAP

HSAP 与 HTAP 都会成为企业数据架构中不可或缺的重要组成部分，而在应对有规模企业，特别是当互联网 / 物联网应用不断扩大时，企业分析查询对大数据有着越来越高的需求，那么这时，HSAP 就有了其更加不可或缺的作用。而对 HTAP 数据库来讲，虽然在技术实现上并不会太简单，但从本质上讲，HTAP 在对其分布式事务能力进行妥协后，应该也有同时具备 HSAP 能力的潜能。

参考：关于 HTAP 与 HSAP

# Cloud Native, Serverless

关于云原生和无服务器之间的联系

云原生比云计算多了一个 native，阿里某位大佬说过：“因云而生的软件，硬件，架构，就是真正的云原生，因云而生的技术，就是云原生技术。”

云原生是一个更加泛的概念，他表示的是在云计算领域中的一部分，是在云且原生的部分。那么 Serverless 架构呢，它本身也是因云而生，成长在云，Serverless 架构是一种技术架构，而云原生是一种泛概念，他的外面还有云计算。

参考：Cloud Native （云原生）和 Severless （无服务器）之间具体有怎样的联系？

# 数据仓库，数据湖，湖仓一体，联邦查询

参考：一文读懂数据仓库、数据湖、湖仓一体

# 数据仓库

Data Warehouse（DW/DWH），早期系统采用关系型数据库来存放管理数据，但是随着大数据技术的兴起，人们对于多方面数据进行分析的需求愈加强烈，这就要求建立一个能够面向分析、集成保存大量历史数据的新型管理机制，这一机制就是数据仓库。

数据仓库通常存储来自不同源的数据，集成源数据以提供统一的视图。这些资源可以包括事务系统、应用程序日志文件、关系数据库等等。

特征

• 数据仓库的数据是面向主题的
• 数据仓库的数据是集成的
• 数据仓库的数据是随时间不断变化的
• 数据仓库的数据是非易失的

# 数据湖

Data Lake 是一个以原始格式存储数据的存储库或系统，它按原样存储数据，而无需事先对数据进行结构化处理。无论是否结构化或半结构化亦或是二进制数据如图形，音频，视频都可以存。

特征

• 容量大
• 格式多
• 处理速度快
• 体系结构，数据湖是由多个组件构成的生态系统

Hadoop 相比于数据湖，虽然 Hadoop 基于分布式，可横向扩展文件系统架构，可以管理和处理海量数据，但是它无法提供数据湖所需要的复杂元数据管理功能。根据数据湖的体系结构，数据湖是由多个组件构成的生态系统，而 Hadoop 仅仅提供了其中的部分组件功能。

# 湖仓一体

数据湖虽然适合数据的存储，但是缺少一些关键功能，不支持事务，缺乏一致性，隔离性，不能保证执行数据质量，这样的短板决定了，让数据湖来承载读写访问、批处理、流作业是不现实的。而且，数据湖缺乏结构性，一旦没有被治理好，就会变成数据沼泽。

既然都是拿数据为业务服务，数据湖和数仓作为两大 “数据集散地”，能不能彼此整合一下，让数据流动起来，少点重复建设呢？，于是，Databricks 率先提出了湖仓一体（Data Lakehouse）的概念。

湖仓一体是一种结合了数据湖灵活性和数据仓库规范性优势的新范式，在基于数据湖的低成本存储上，实现与数据仓库中类似的数据结构和数据管理功能。

Data Lakehouse 的出现试图去融合数仓和数据湖这两者之间的差异，通过将数仓构建在数据湖上，使得存储变得更为廉价和弹性，同时 lakehouse 能够有效地提升数据质量，减小数据冗余。

在 lakehouse 的构建中，ETL（Extract-Transform-Load）起了非常重要的作用，它能够将未经规整的数据湖层数据转换成数仓层结构化的数据。

特征

• 支持事务，可以处理多条不同的数据管道，意味着它可以在不破坏数据完整性的前提下支持并发的读写事务
• 根据应用需求为绝大多数数据施加 schemas，标准化
• 报表以及分析应用的支持
• 数据类型扩展，这一点结合数据湖的优势
• 端到端的流式支持，支持流式分析，从而能够满足实时报表的需求
• 计算存储分离，数据存储在一个集群中，而在另一个集群中进行处理
• 开放性（跨构件，引擎，语言操作）

<!-- ### 联邦查询 -->

<!-- ## 智能化：AI4DB，DB4AI -->