1. 引言
1.1 传统关系型数据库查询实现
在传统关系型数据库中，可以将用户输入的SQL语句划分为DDL、DML、DQL、DCL等类型，对于不同类型的SQL语句，数据库引擎的执行方式、复杂度存在较大差异。其中，DQL类型查询语句的复杂度最高，其执行过程一般分为5个阶段：
- SQL输入。接受客户端用户输入的SQL语句。
- 语法分析Parser。将SQL查询语句经词法分析和语法分析后变换为一棵语法树传递给下一个阶段。
- 语义检查Analyzer。根据语法树和数据库的元信息进行语义检查，对语法分析树进行逻辑判断，树的结构不发生变化；对语法分析树上的各个节点进行语义分析，比如判断表是否存在，列的类型是否正确等，对不合法的语义报告错误。
- 查询优化Optimizer。通常包含两项工作：一是逻辑优化，二是物理优化。其中优化器的逻辑优化运用查询优化技术，如视图重写，子查询提升，子链接提升，条件化简、等价谓词重写，外连接消除等，对语法树进行等价转换，得到逻辑查询执行计划。优化器的物理优化根据数据库的统计信息，使用基于代价的查询优化方式，对多种查询执行计划进行定量分析，对每一个可能的执行方式进行评估，选择出代价最小的作为最优的物理查询执行计划。
- 查询执行Executor。根据物理查询执行计划执行查询，逐步调用相关算法进行执行，比如单表的顺序扫描，索引扫描，多表的嵌套循环连接，基于排序的两趟算法，基于散列的两趟算法等，不同的数据库，通常会有所不同但又相似的实现。
1.2 ClickHouse查询实现
ClickHouse的查询实现过程与传统关系型数据库相似。从ClickHouse的主函数Server::main可以看出，其查询实现过程如下：
- 创建全局上下文SharedContext。
- 初始化线程池，ClickHouse是多线程模式，一个客户端对应一个后台线程进行服务。
- ZooKeeper初始化。
- 初始化全局上下文SharedContext，读取config一些参数初始化，元数据信息初始化，所有Query共享。
- 遍历监听地址，端口号创建不同类型的服务，包括HTTP，HTTPS，TCP，TCP with SSL，MySQL，Postgresql等，不同类型的服务对应不同的处理函数，HTTP对应HTTPHandler.cpp的HTTPHandler::handleRequest()，TCP对应TCPHandler.cpp的TCPHandler::runImpl()，MySQL对应MySQLHandler.cpp的MySQLHandler::run()等。
- 启动各种服务线程，监听并接受SQL语句，执行查询任务。
- 等待各种服务线程结束。
int Server::main(const std::vector<std::string> & /*args*/)
{
//创建全局共享上下文,所有Query共享,包括一些settings,available functions, data types, aggregate functions, databases,...
auto shared_context = Context::createShared();
auto global_context = std::make_unique<Context>(Context::createGlobal(shared_context.get()));
//初始化线程池
GlobalThreadPool::initialize(config().getUInt("max_thread_pool_size", 10000));
//初始化ZooKeeper
zkutil::ZooKeeperNodeCache main_config_zk_node_cache([&] { return global_context->getZooKeepe
//初始化元数据信息
loadMetadataSystem(*global_context);
global_context->initializeSystemLogs();
loadMetadata(*global_context, default_database);
database_catalog.loadDatabases();
//遍历监听地址,端口号创建不同类型服务
auto servers = std::make_shared<std::vector<ProtocolServerAdapter>>();
{
for (const auto & listen_host : listen_hosts)
{
//HTTP
const char * port_name = "http_port";
createServer(listen_host, port_name, listen_try, [&](UInt16 port)
{
Poco::Net::ServerSocket socket;
auto address = socketBindListen(socket, listen_host, port);
servers->emplace_back(
port_name,std::make_unique<HTTPServer>(
context(), createHandlerFactory(*this, async_metrics, "HTTPHandler-factory"), server_pool, socket, http_params));
});
// TCP
port_name = "tcp_port";
createServer(listen_host, port_name, listen_try, [&](UInt16 port)
{
Poco::Net::ServerSocket socket;
auto address = socketBindListen(socket, listen_host, port);
servers->emplace_back(port_name, std::make_unique<Poco::Net::TCPServer>(
new TCPHandlerFactory(*this, /* secure */ false, /* proxy protocol */ false),
server_pool,
socket,
new Poco::Net::TCPServerParams));
});
//MySQL
port_name = "mysql_port";
createServer(listen_host, port_name, listen_try, [&](UInt16 port)
{...}
//PostgreSQL
port_name = "postgresql_port";
createServer(listen_host, port_name, listen_try, [&](UInt16 port)
{...}
}
}
//启动服务
for (auto & server : *servers)
server.start();
//等待各种服务线程结束
waitForTerminationRequest();
//正常退出
return Application::EXIT_OK;
}2. SQL输入
下面以TCPHandler为例，解析服务端是如何处理客户端发来的请求的，入口函数为TCPHandler::runImpl()。
2.1 实现流程
2.2 流程描述
- 初始化套接字对应的输入和输出流缓冲区。
- 循环从网络接收SQL语句。
- 执行查询executeQuery，将SQL语句经过词法语法解析Parser，查询优化Optimizer(重写Rewriter，语义analyzer，execute）生成物理执行计划QueryPlan。主要包括三个函数：parseQurey()词法语法分析，生成各类抽象语法树AST，InterpreterFactory::get()基于规则重写、语义分析语法树，生成初步的执行计划操作链，AST经过Rewriter处理器生成TreeRewriterResult改写后的语法树，然后经过表达式处理器SelectQueryExpresionAnalyzer将语法树上的表达式转化为一系列可执行的动作，并将一系列可执行的动作保存在表达式分析结果中ExpressionAnalysisResult。
- 处理查询processOrdinaryQueryWithProcessors，生成查询结果，写入到Socket输出缓冲区，等待发送给客户端。根据Query种类调用不同的处理函数，处理insert Query调用processInsertQuery()，并发处理普通查询调用processOrdinaryQueryWithProcessors()，单线程处理普通查询调用processOrdinaryQuery()。
3. 语法分析Parser
3.1 实现流程
ClickHouse采用手写的一个递归下降的语法解释器Parser来对SQL进行解析，入口函数为parseQuery()，其核心逻辑在tryParseQuery函数中，该函数利用lexer扫描Query字符流，并将其分割成一个个的Token，然后Parser再对Token流进行解析生成AST抽象语法树。
输入：查询SQL语句。
输出：不同种类的抽象语法树AST，基类IAST，查询类ASTSelectQuery，插入类ASTInsertQuery，DDL类（ASTAlterCommand，ASTCreateQuery）等。
3.2 流程描述
- 调用tokens()扫描Query字符流，将其分割成一个个的Token。
- 调用parseImpl对Token流进行解析生成各类AST抽象语法树，这个方法粗略地将Query分为了几种。但本质上可以归纳为两种：第一种为有结果输出，对应show,select等语句；第二种为无结果输出，对应insert，use，set和与系统相关的语句exit，每一种Query都自定义了其专属的parseImpl函数。
- 以select语句对应的ParserSelectQuery::parseImpl进行分析，首先给出select语句中可能出现的关键词，在词法分析生成的Tocken流中抓取这些关键字，如果成功抓取，则调用setExpression保存到ASTSelectQuery节点上相应位置。
bool ParserSelectQuery::parseImpl(Pos & pos, ASTPtr & node, Expected &
expected)
{
//创建ASTSelectQuery节点
auto select_query = std::make_shared<ASTSelectQuery>();
node = select_query;
//select语句中可能出现的关键词
ParserKeyword s_select("SELECT");
ParserKeyword s_distinct("DISTINCT");
ParserKeyword s_from("FROM");
ParserKeyword s_prewhere("PREWHERE");
ParserKeyword s_where("WHERE");
ParserKeyword s_group_by("GROUP BY");
ParserKeyword s_with("WITH");
ParserKeyword s_totals("TOTALS");
ParserKeyword s_having("HAVING");
ParserKeyword s_order_by("ORDER BY");
ParserKeyword s_limit("LIMIT");
ParserKeyword s_settings("SETTINGS");
ParserKeyword s_by("BY");
ParserKeyword s_rollup("ROLLUP");
ParserKeyword s_cube("CUBE");
ParserKeyword s_top("TOP");
ParserKeyword s_with_ties("WITH TIES");
ParserKeyword s_offset("OFFSET");
ParserKeyword s_fetch("FETCH");
ParserKeyword s_only("ONLY");
ParserKeyword s_row("ROW");
ParserKeyword s_rows("ROWS");
ParserKeyword s_first("FIRST");
ParserKeyword s_next("NEXT");
ASTPtr with_expression_list;
ASTPtr select_expression_list;
ASTPtr tables;
ASTPtr prewhere_expression;
ASTPtr where_expression;
ASTPtr group_expression_list;
ASTPtr having_expression;
ASTPtr order_expression_list;
ASTPtr limit_by_length;
ASTPtr limit_by_offset;
ASTPtr limit_by_expression_list;
ASTPtr limit_offset;
ASTPtr limit_length;
ASTPtr top_length;
ASTPtr settings;
//从Tocken流中抓取这些关键字对应的子句,并解析成对应的AST
//WITH expr list 解析成ASTWithElement
//FROM database.table or FROM table or FROM (subquery) or FROM tableFunction(...) 解析成ASTTablesTnSelectQuery
// WHERE expr
// GROUP BY expr list
.........
///关键字对应的每个部分存入ASTSelectQuery相应位置
select_query->setExpression(ASTSelectQuery::Expression::WITH, std::move(with_expression_list));
select_query->setExpression(ASTSelectQuery::Expression::SELECT, std::move(select_expression_list));
select_query->setExpression(ASTSelectQuery::Expression::TABLES, std::move(tables));
select_query->setExpression(ASTSelectQuery::Expression::PREWHERE, std::move(prewhere_expression));
select_query->setExpression(ASTSelectQuery::Expression::WHERE, std::move(where_expression));
select_query->setExpression(ASTSelectQuery::Expression::GROUP_BY, std::move(group_expression_list));
select_query->setExpression(ASTSelectQuery::Expression::HAVING, std::move(having_expression));
select_query->setExpression(ASTSelectQuery::Expression::ORDER_BY, std::move(order_expression_list));
select_query->setExpression(ASTSelectQuery::Expression::LIMIT_BY_OFFSET, std::move(limit_by_offset));
select_query->setExpression(ASTSelectQuery::Expression::LIMIT_BY_LENGTH, std::move(limit_by_length));
select_query->setExpression(ASTSelectQuery::Expression::LIMIT_BY, std::move(limit_by_expression_list));
select_query->setExpression(ASTSelectQuery::Expression::LIMIT_OFFSET, std::move(limit_offset));
select_query->setExpression(ASTSelectQuery::Expression::LIMIT_LENGTH, std::move(limit_length));
select_query->setExpression(ASTSelectQuery::Expression::SETTINGS, std::move(settings));
return true;
}3.3 相关函数
3.4 如何查看AST
explain ast select * from t2 where tc2=2 and tc3=3；
其中，每一个节点都是一个具体的AST实例，比如表达式a,b+c,f(d)对应ASTExpressionList，函数对应ASTFunction。
4. 查询优化Optimizer
4.1 实现流程
ClickHouse中定义了Interpreter类，不同的查询种类对应不同的Interpreter子类，作用就是重写、分析语法树、生成物理执行计划，包括两个部分，InterpreterFactory::get()函数实现了Optimizer的逻辑优化(Rewriter & Analyzer)功能，interpreter->execute()函数实现了Optimizer的物理优化功能。入口函数为executeQuery()，其核心逻辑函数为executeQueryImpl()。
输入：不同种类的抽象语法树AST，基类IAST，查询类ASTSelectQuery，插入类ASTInsertQuery，DDL类(ASTAlterCommand，ASTCreateQuery)等。
输出：QueryPipeline物理查询计划。
4.2 流程描述
- 调用InterpreterFactory::get()实现重写语义优化，根据AST的不同类型，调用不同函数，查询类InterpreterSelectQuery::InterpreterSelectQuery，插入类InterpreterInsertQuery::InterpreterInsertQuery，ddl类InterpreterDropQuery::InterpreterDropQuery。以InterpreterSelectQuery::InterpreterSelectQuery为例，结构从AST转化为TreeRewriter，再经过表达式分析器SelectQueryExpressionAnalyzer将语法树中的表达式转化为一系列执行动作Actions，存放在ExpressionAnalysisResult上，作为物理优化的输入。
- 调用interpreter->execute()，根据不同的AST类型，执行不同的函数，查询类InterpreterSelectQuery::execute，插入类InterpreterInsertQuery::execute，以InterpreterSelectQuery::execute为例进行分析，包括生成物理查询计划和为物理查询计划创建processor两个部分。核心逻辑函数buildQueryPlan生成物理查询计划，将一系列的Actions转化成Step，比如简单查询select * from t2 where tc2=2 and tc3=3;则分成四个Step，ReadFormStorageStep扫描，SettingQuotaAndLimitsStep限额，FilterStep过滤，projectStep投影。buildPipeline为每个Step创建processor，并将上下层连接起来，输出QueryPipeline结构交给执行器Executor去执行。
4.3 如何查看计划
三个选项header=1,打印输出端口的头部信息，actions =1打印一系列执行动作，description =1打印查询Step描述。
通过explain header=1, actions=1,description=1 select * from t2 where tc2=2 and tc3=3;查询逻辑查询计划
其中，每个节点称为一个Step，Header代表该步对应的输出端口的头部信息，Actions代表该步需要执行的动作。
4.4 如何查看转化成pipeline的计划
三个选项header=1,打印输出端口的头部信息，graph=1以无向无环图的方式打印，compact=1以简化的方式打印有向无环图，默认1。
通过explain pipeline select * from t2 where tc2=2 and tc3=3;(max_threads=2)查询物理执行计划：
其中，打印每一个步对应的processor名称，2代表对应的processor个数，意味着同时两个线程执行该步，0-->1代表处理者MergeTreeThread 0个输入端口，1个输出端口。
explain pipeline graph =1 select * from t2 where tc2=2 and tc3=3;将物理查询计划以有向无环图的形式展示：
可以利用工具查看：dot -Tpng example1.dot -o example1.png
5. 查询执行Executor
5.1 实现流程
执行物理查询计划，生成查询结果，写入到Socket输出缓冲区，等待发送给客户端。根据查询种类的不同，调用不同的处理函数，处理insert Query调用processInsertQuery，并发处理普通查询调用processOrdinaryQueryWithProcessors，单线程处理普通查询调用processOrdinaryQuery。
输入：QueryPipeline结构体。
输出：与client交互，发送数据Block。
5.2 流程描述
- 调用函数sendData(header)发送头部信息，一般包括列名。
- 循环调用Executor.pull(block，interactive_delay/1000)拉取一个Block，如果一定时间内拉取不到，认为超时，报错结束查询。拉取第一个Block时，根据QueryPipeline.processors创建有向无环图，创建调度线程去创建子线程生产Chunk，放到全局队列ConcurrentBoundedQueue queue。主线程每次从queue里获取一个Chunk，并转化为Block，就是将Chunk里的列数据，列名，列类型重新指向一下。当执行结束时等待调度线程结束。
- 如果client取消查询，则停止发送取消查询，等待调度线程结束。
- 如果Block不为null格式，调用sendData(block)把输出结果写入到套接字输出缓冲区中,client从这个输出缓冲区读取就能够得到结果。
