This is an automated email from the ASF dual-hosted git repository.
jiafengzheng pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris-website.git
The following commit(s) were added to refs/heads/master by this push:
new 4f56c2f9cae fix
4f56c2f9cae is described below
commit 4f56c2f9caec87de7f01cc494cad833033702c1e
Author: jiafeng.zhang <zhang...@gmail.com>
AuthorDate: Sat Aug 27 12:00:17 2022 +0800
fix
---
blog/principle-of-Doris-SQL-parsing.md | 84 ++++++----------------
.../principle-of-Doris-SQL-parsing.md | 74 +++++--------------
2 files changed, 40 insertions(+), 118 deletions(-)
diff --git a/blog/principle-of-Doris-SQL-parsing.md
b/blog/principle-of-Doris-SQL-parsing.md
index cacadfe20bc..bc76cda6b7f 100644
--- a/blog/principle-of-Doris-SQL-parsing.md
+++ b/blog/principle-of-Doris-SQL-parsing.md
@@ -36,7 +36,7 @@ First, AST will be processed preliminary by Analyze and then
optimized by Single
Since there are many types of SQL, this article focuses on the analysis of
query SQL. Doris's SQL analysis will be explained deeply in the algorithm
principle and code implementation.
-# 1 Introduction to Doris
+# 1. Introduction to Doris
Doris is an interactive SQL database based on MPP architecture, mainly used to
solve near real-time reports and multi-dimensional analysis. The Doris
architecture is straightforward, with only two types of processes.
- Frontend（FE）: It is mainly responsible for user request access, query
parsing and planning, storage and management of metadata, and node
management-related work.
@@ -45,15 +45,12 @@ Doris is an interactive SQL database based on MPP
architecture, mainly used to s
In Doris' storage engine, data will be horizontally divided into several data
shards (Tablet, also called data bucket). Each tablet contains several rows of
data. Multiple Tablets belong to different partitions logically. A Tablet only
belongs to one Partition. And a Partition contains several Tablets. Tablet is
the smallest physical storage unit for operations such as data movement,
copying, etc.
-# 2 SQL parsing In Apache Doris
+# 2. SQL parsing In Apache Doris
SQL parsing in this article refers to **the process of generating a complete
physical execution plan after a series of parsing of an SQL statement**.
This process includes the following four steps: lexical analysis, syntax
analysis, generating a logical plan, and generating a physical plan.
-<div align=center>
-<img alt="Figure1 The process of SQL parsing"
src="../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_1_en.png"/>
-</div>
- <p align="center">Figure1 The process of SQL parsing</p>
+
## 2.1 Lexical analysis
The lexical analysis will identify the SQL in the form of a string into
tokens, in preparation for the grammatical analysis.
@@ -72,24 +69,19 @@ SQL Tokens could be divided into the following categories:
## 2.2 Syntax analysis
The syntax analysis will convert the token generated by the lexical analysis
into an abstract syntax tree based on the syntax rules, as shown in Figure 2.
-<div align=center>
-<img alt=">Figure2 An example of an abstract syntax tree" width="60%"
src="../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_2_en.png"/>
-</div>
-<p align="center">Figure2 An example of an abstract syntax tree</p>
+
## 2.3 Logical plan
The logical plan converts the abstract syntax tree into an algebraic relation,
which is an operator tree, and each node represents a calculation method for
data. The entire tree represents the calculation method and flows direction of
data, as shown in Figure 3.
-<div align=center>
-<img alt="Figure3 Relational algebra example" width="20%"
src="../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_3_en.png"/>
-</div>
- <p align="center">Figure3 Relational algebra example</p>
+
+ 
## 2.4 Physical plan
The physical plan is the plan that determines which computing operations are
performed on which machines. It will be generated based on the logical plan,
the distribution of machines, and the distribution of data.
The SQL parsing of the Doris system also adopts these steps, but it is refined
and optimized according to the characteristics of the Doris system structure
and the storage method of data to maximize the computing power of the machine.
-# 3 Design goals
+# 3. Design goals
The design goals of the Doris SQL parsing architecture are:
1. Maximize Computational Parallelism
@@ -98,15 +90,12 @@ The design goals of the Doris SQL parsing architecture are:
3. Minimize the amount of data that needs to be scanned
-# 4 Architecture
+# 4. Architecture
Doris SQL parsing includes five steps: lexical analysis, syntax analysis,
generation of a stand-alone logical plan, generation of a distributed logical
plan, and generation of a physical execution plan.
In terms of code implementation, it corresponds to the following five steps:
Parse, Analyze, SinglePlan, DistributedPlan, and Schedule, which as shown in
Figure 4.
-<div align=center>
-<img alt="Figure 4 System Architecture Diagram" width="40%"
src="../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_4_en.png"/>
-</div>
- <p align="center">Figure 4 System Architecture Diagram</p>
+
The Parse phase will not be discussed in this article. Analyze will do some
pre-processing of the AST. A stand-alone query plan will be optimized by
SinglePlan based on the AST. DistributedPlan will split the stand-alone query
plan into distributed query plans. Schedule phase will determine which machines
the query plan will be sent to for execution.
@@ -114,13 +103,9 @@ The Parse phase will not be discussed in this article.
Analyze will do some pre-
Figure 5 shows a simple query SQL parsing implementation in Doris.
+
-<div align=center>
-<img alt="Figure5 The parsing process of query sql in Doris" width="50%"
src="../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_5_en.png"/>
-</div>
- <p align="center">Figure5 The parsing process of query sql in Doris</p>
-
-# 5 Parse Phase
+# 5. Parse Phase
In the Parse stage, JFlex technology is used for lexical analysis, java cup
parser technology is used for syntax analysis, and an AST（Abstract Syntax
Tree）will finally generate. These are existing and mature technologies and will
not be introduced in detail here.
AST has a tree-like structure, which represents a piece of SQL. Therefore,
different types of queries -- select, insert, show, set, alter table, create
table, etc. will generate additional data structures after Parse (SelectStmt,
InsertStmt, ShowStmt, SetStmt, AlterStmt, AlterTableStmt, CreateTableStmt,
etc.). However, they all inherit from Statements and will perform some specific
processing according to their own grammar rules. For example: for select type
SQL, the SelectStmt structure [...]
@@ -129,12 +114,8 @@ SelectStmt structure contains SelectList, FromClause,
WhereClause, GroupByClause
All structures in AST are composed of basic structure expressions--Expr by
using various combinations, as shown in Figure 6.
-<div align=center>
-<img alt="Figure6 Implementation of Abstract Syntax Tree AST in Doris"
width="60%"
src="../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_6_en.png"/>
-</div>
- <p align="center">Figure6 Implementation of Abstract Syntax Tree AST in
Doris</p>
-
-# 6 Analyze Phase
+
+# 6. Analyze Phase
Analyze will perform pre-processing and semantic analysis on the abstract
syntax tree AST generated in the Parse phase, preparing for the generation of
stand-alone logic plans.
The abstract class StatementBase represents the abstract syntax tree. This
abstract class contains a most crucial member function--analyze(), which is
used to perform what's needed to do in Analyze phase.
@@ -161,20 +142,17 @@ After analyzing the AST, a rewrite operation will be
performed again to simplify
For example: simplification of constant expressions: 1 + 1 + 1 is rewritten as
3, 1 > 2 is rewritten as Flase, etc. Convert some statements into a unified
processing method, such as rewriting where in, where exists as semi join, where
not in, where not exists as anti join.
-# 7 Generate stand-alone logical Plan phase
+# 7. Generate stand-alone logical Plan phase
At this stage, algebraic relations will be generated according to the AST
abstract syntax tree, also known as the operator number. Each node on the tree
is an operator, representing an operation.
As shown in Figure 7, ScanNode represents scan and read operations on a table.
HashJoinNode represents the join operation. A hash table of a small table will
be constructed in memory, and the large table will be traversed to find the
exact value of the join key. Project means the projection operation, which
represents the column that needs to be output at the end. Figure 7 shows that
only citycode column will output.
-<div align=center>
-<img alt="Figure7 Example of a stand-alone logical plan" width="50%"
src="../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_7_en.png"/>
-</div>
- <p align="center">Figure7 Example of a stand-alone logical plan</p>
+
Without optimization, the generated relational algebra is very expensive to
send to storage and execute.
For query:
-```undefined
+```sql
select a.siteid, a.pv from table1 a join table2 b on a.siteid = b.siteid where
a.citycode=122216 and b.username="test" order by a.pv limit 10
```
As shown in Figure 8, for unoptimized relational algebra, all columns need to
be read out for a series of calculations. In the end, siteid and pv column are
selected and output. A large amount of useless column data wastes computing
resources.
@@ -204,10 +182,7 @@ When Doris generates algebraic relations, a lot of
optimizations are made: the p
Figure 9 shows an example of optimization. The optimization of Doris is
carried out in generating relational algebra. Generating one will optimize
one.· Projection pushdown: BE only scans the columns that must be read when
Scanning.
-<div align=center>
-<img alt="Figure9 The process of single-machine query plan optimization"
width="100%"
src="../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_9_en.png"/>
-</div>
- <p align="center">Figure9 The process of single-machine query plan
optimization</p>
+
# 8 Generate Distributed Plan Phase
@@ -229,10 +204,7 @@ For query operations, the join operation is the most
common.
**bucket shuffle join**：When the join key is a bucketing key, and only one
partition is involved, the bucket shuffle join algorithm is preferred. Since
bucketing itself represents a way of dividing data, it only needs to take the
hash modulo of the number of buckets from the right table to the left table, so
that only one copy of the data in the right table needs to be transmitted over
the network, which greatly reduces the network of data transmission, as shown
in Figure 10.
-<div align=center>
-<img alt="Figure10 Example of bucket shuffle join" width="40%"
src="../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_10_en.png"/>
-</div>
- <p align="center">Figure10 Example of bucket shuffle join</p>
+
Figure 11 shows the core process of creating a distributed logical plan with a
single-machine logical plan with HashJoinNode.
@@ -252,17 +224,11 @@ Figure 11 shows the core process of creating a
distributed logical plan with a s
- If hash partition join is used, the data in the left table and the right
table must be split, and both left and right nodes need to be split out to
create left ExchangeNode and right ExchangeNode respectively. HashJoinNode
specifies the left and right nodes as left ExchangeNode and right ExchangeNode.
Create a PlanFragment separately and specify RootPlanNode as this HashJoinNode.
Finally, specify the data sending destination of leftFragment and rightFragment
as left ExchangeNode and ri [...]
-<div align=center>
-<img alt="Figure11 The core process of HashJoinNode creating a distributed
logic plan" width="50%"
src="../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_11_en.png"/>
-</div>
- <p align="center">Figure11 The core process of HashJoinNode creating a
distributed logic plan</p>
+
Figure 12 is an example after the join operation of two tables is converted
into a PlanFragment tree, there are 3 PlanFragments generated. The final output
data passes through the ResultSinkNode node.
-<div align=center>
-<img alt="Figure12 From stand-alone plan to distributed plan" width="50%"
src="../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_12_cn.png"/>
-</div>
- <p align="center">Figure12 From stand-alone plan to distributed plan</p>
+
# 9. Schedule phase
@@ -292,10 +258,7 @@ This step is to create a distributed physical plan based
on the distributed logi
**e. to thrift stage**：Create RPC requests based on FInstanceExecParam of all
PlanFragments, then send them to the BE side for execution. A complete SQL
parsing process is completed.
-<div align=center>
-<img alt="Figure13 The core process of creating a distributed physical plan"
width="60%"
src="../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_13_en.png"/>
-</div>
- <p align="center">Figure13 The core process of creating a distributed
physical plan</p>
+
Figure 14 is a simple example. The PlanFrament in the figure contains a
ScanNode. The ScanNode scans three tablets. Each tablet has two copies, and the
cluster assumes that there are two hosts.
@@ -303,10 +266,7 @@ The computeScanRangeAssignment stage determines that
replicas 1, 3, 5, 8, 10, an
If the global concurrency is set to 1, 2 instances of FInstanceExecParam are
created and sent to host1 and host2 for execution. If the global concurrency is
set to 3, 3 instances of FInstanceExecParam are created on this host1, and
three instances of FInstanceExecParam are created on host2. Each instance scans
one replica, equivalent to initiating 6 RPC requests.
-<div align=center>
-<img alt="Figure14 Process of generating a physical plan" width="60%"
src="../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_14_en.png"/>
-</div>
- <p align="center">Figure14 Process of generating a physical plan</p>
+
# 10 Summary
This article first briefly introduces Doris and then introduces the general
process of SQL parsing: lexical analysis, syntax analysis, generating logical
plans, and generating physical plans. Then, it presents the overall
architecture of DorisSQL parsing. In the end, the five processes: Parse,
Analyze, SinglePlan, DistributedPlan, and Schedule are explained in detail, and
an in-depth explanation is given of the algorithm principle and code
implementation.
diff --git
a/i18n/zh-CN/docusaurus-plugin-content-blog/principle-of-Doris-SQL-parsing.md
b/i18n/zh-CN/docusaurus-plugin-content-blog/principle-of-Doris-SQL-parsing.md
index 51efa17509b..4a405895ba2 100644
---
a/i18n/zh-CN/docusaurus-plugin-content-blog/principle-of-Doris-SQL-parsing.md
+++
b/i18n/zh-CN/docusaurus-plugin-content-blog/principle-of-Doris-SQL-parsing.md
@@ -48,12 +48,10 @@ SQL解析在这篇文章中指的是**将一条sql语句经过一系列的解析
这个过程包括以下四个步骤：词法分析，语法分析，生成逻辑计划，生成物理计划。 如图1所示：
-<div align=center>
-<img alt="图 1 SQL解析的流程"
src="../../../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_1_cn.png"/>
-</div>
- <p align="center">图 1 SQL解析的流程</p>
+
## 2.1 词法分析
+
词法分析主要负责将字符串形式的sql识别成一个个token，为语法分析做准备。
```undefined
select ...... from ...... where ....... group by ..... order by ......
@@ -70,17 +68,13 @@ SQL 的 Token 可以分为如下几类：
## 2.2 语法分析
语法分析主要负责根据语法规则，将词法分析生成的token转成抽象语法树（Abstract Syntax Tree），如图2所示。
-<div align=center>
-<img alt=">图 2 抽象语法树示例" width="60%"
src="../../../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_2_cn.png"/>
-</div>
-<p align="center">图 2 抽象语法树示例</p>
+
+
## 2.3 逻辑计划
逻辑计划负责将抽象语法树转成代数关系。代数关系是一棵算子树，每个节点代表一种对数据的计算方式，整棵树代表了数据的计算方式以及流动方向，如图3所示。
-<div align=center>
-<img alt="图3 关系代数示例" width="20%"
src="../../../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_3_cn.png"/>
-</div>
- <p align="center">图3 关系代数示例</p>
+
+
## 2.4 物理计划
物理计划是在逻辑计划的基础上，根据机器的分布，数据的分布，决定去哪些机器上执行哪些计算操作。
@@ -101,10 +95,7 @@ Doris SQL解析具体包括了五个步骤：词法分析，语法分析，生
具体代码实现上包含以下五个步骤：Parse, Analyze, SinglePlan, DistributedPlan, Schedule。
-<div align=center>
-<img alt="图4 系统总体架构图" width="40%"
src="../../../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_4_cn.png"/>
-</div>
- <p align="center">图4 系统总体架构图</p>
+
如图4所示，Parse阶段本文不详细讲，Analyze负责对AST进行前期的一些处理，SinglePlan根据AST进行优化生成单机查询计划，DistributedPlan将单机的查询计划拆成分布式的查询计划，Schedule阶段负责决定查询计划下发到哪些机器上执行。
@@ -112,10 +103,7 @@ Doris SQL解析具体包括了五个步骤：词法分析，语法分析，生
图5展示了一个简单的查询SQL在Doris的解析实现
-<div align=center>
-<img alt="图5 查询sql在Doris中的解析过程" width="50%"
src="../../../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_5_cn.png"/>
-</div>
- <p align="center">图5 查询sql在Doris中的解析过程</p>
+
# 5 Parse阶段
词法分析采用jflex技术，语法分析采用java cup parser技术，最后生成抽象语法树（Abstract Syntax
Tree）AST，这些都是现有的、成熟的技术，在这里不进行详细介绍。
@@ -126,10 +114,7 @@
SelectStmt结构包含了SelectList，FromClause，WhereClause，GroupByClause
AST中所有结构都是由基本结构表达式Expr通过多种组合而成，如图6所示。
-<div align=center>
-<img alt="图6 Doris中抽象语法树AST的实现" width="60%"
src="../../../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_6_cn.png"/>
-</div>
- <p align="center">图6 Doris中抽象语法树AST的实现</p>
+
# 6 Analyze阶段
Analyze主要是对Parse阶段生成的抽象语法树AST进行一些前期的处理和语义分析，为生成单机逻辑计划做准备。
@@ -163,10 +148,7 @@ Analyze主要是对Parse阶段生成的抽象语法树AST进行一些前期的
如图7所示，ScanNode代表着对一个表的扫描操作，将一个表的数据读出来。HashJoinNode代表着join操作，小表在内存中构建哈希表，遍历大表找到连接键相同的值。Project表示投影操作，代表着最后需要输出的列，图7表示只用输出citycode这一列。
-<div align=center>
-<img alt="图7 单机逻辑计划示例" width="50%"
src="../../../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_7_cn.png"/>
-</div>
- <p align="center">图7 单机逻辑计划示例</p>
+
如果不进行优化，生成的关系代数下发到存储中执行的代价非常高。
@@ -178,10 +160,7 @@ select a.siteid, a.pv from table1 a join table2 b on
a.siteid = b.siteid where a
Doris在生成代数关系时，进行了大量的优化，将投影列和查询条件尽可能放到扫描操作时执行。
-<div align=center>
-<img alt="图8 未优化的关系代数" width="20%"
src="../../../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_8_cn.png"/>
-</div>
- <p align="center">图8 未优化的关系代数</p>
+
**具体来说这个阶段主要做了如下几项工作：**
@@ -201,10 +180,7 @@ Doris在生成代数关系时，进行了大量的优化，将投影列和查询
图9展示了优化的示例，Doris是在生成关系代数的过程中优化，边生成边优化。
-<div align=center>
-<img alt="图9 单机查询计划优化的过程" width="100%"
src="../../../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_9_cn.png"/>
-</div>
- <p align="center">图9 单机查询计划优化的过程</p>
+
# 8 生成分布式Plan阶段
@@ -226,10 +202,7 @@ Doris在生成代数关系时，进行了大量的优化，将投影列和查询
**bucket shuffle join**：当join key是分桶key，并且只涉及到一个分区时，就会优先采用bucket shuffle
join算法。由于分桶本身就代表了数据的一种切分方式，所以可以利用这一特点，只需将右表对左表的分桶数hash取模，这样只需网络传输一份右表数据，极大减少了数据的网络传输，如图10所示。
-<div align=center>
-<img alt="图10 bucket shuffle join示例" width="40%"
src="../../../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_10_cn.png"/>
-</div>
- <p align="center">图10 bucket shuffle join示例</p>
+
如图11展示了带有HashJoinNode的单机逻辑计划创建分布式逻辑计划的核心流程。
@@ -249,17 +222,11 @@ Doris在生成代数关系时，进行了大量的优化，将投影列和查询
- 如果使用hash partition join，左表和右边的数据都要切分，需要将左右节点都拆分出去，分别创建left ExchangeNode,
right ExchangeNode，HashJoinNode指定左右节点为left ExchangeNode和 right
ExchangeNode。单独创建一个PlanFragment，指定RootPlanNode为这个HashJoinNode。最后指定leftFragment,
rightFragment的数据发送目的地为left ExchangeNode, right ExchangeNode。
-<div align=center>
-<img alt="图 11 HashJoinNode创建分布式逻辑计划核心流程" width="50%"
src="../../../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_11_cn.png"/>
-</div>
- <p align="center">图 11 HashJoinNode创建分布式逻辑计划核心流程</p>
+
图12是两个表的join操作转换成PlanFragment树之后的示例，一共生成了3个PlanFragment。最终数据的输出通过ResultSinkNode节点。
-<div align=center>
-<img alt="图12 从单机计划到分布式计划" width="50%"
src="../../../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_12_cn.png"/>
-</div>
- <p align="center">图12 从单机计划到分布式计划</p>
+
# 9 Schedule阶段
@@ -289,10 +256,8 @@ Doris在生成代数关系时，进行了大量的优化，将投影列和查询
**e. to
thrift阶段**：根据所有PlanFragment的FInstanceExecParam创建rpc请求，然后下发到BE端执行。这样一个完整的SQL解析过程完成了。
-<div align=center>
-<img alt="图13 创建分布式物理计划核心流程" width="60%"
src="../../../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_13_cn.png"/>
-</div>
- <p align="center">图13 创建分布式物理计划核心流程</p>
+
+
如图14所示是一个简单示例，图中的PlanFrament包含了一个ScanNode，ScanNode扫描3个tablet，每个tablet有2副本，集群假设有2台host。
@@ -300,10 +265,7 @@ computeScanRangeAssignment阶段确定了需要扫描replica 1,3,5,8,10,12，其
如果全局并发度设置为1时，则创建2个实例FInstanceExecParam，下发到host1和host2上去执行，如果如果全局并发度设置为3，这个host1上创建3个实例FInstanceExecParam，host2上创建3个实例FInstanceExecParam，每个实例扫描一个replica，相当于发起6个rpc请求。
-<div align=center>
-<img alt="图14 生成物理计划的过程" width="60%"
src="../../../static/images/blogs/principle-of-Doris-SQL-parsing/Figure_14_cn.png"/>
-</div>
- <p align="center">图14 生成物理计划的过程</p>
+
# 10 总结
本文首先简单介绍了Doris，然后介绍SQL解析的通用流程：词法分析，语法分析，生成逻辑计划，生成物理计划，接着从总体上介绍了Doris在SQL解析这块的总体架构，最后详细讲解了Parse，Analyze，SinglePlan，DistributedPlan，Schedule等5个过程，从算法原理和代码实现上进行了深入的讲解。
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@doris.apache.org
For additional commands, e-mail: commits-h...@doris.apache.org
