Kylin查询源码分析

11-15 129 views

什么是Kylin

Apache Kylin是一个开源的、分布式的分析型数据仓库,提供Hadoop/Spark 之上的 SQL 查询接口及多维分析(OLAP)能力以支持超大规模数据,最初由 eBay 开发并贡献至开源社区。它能在亚秒内查询巨大的表。

Kylin的查询高性能主要依赖于Cube理论,如图所示:

Kylin查询源码分析

它将表字段划分为维度和量度,通过预先计算,在维度上进行量度聚合并保存聚合结果,而根据维度进行聚合查询时,则可以命中已保存的聚合结果,大大减少数据扫描量和实时计算量。

Kylin的系统架构如图所示:

Kylin查询源码分析

它依赖大数据基础设施HBase、Spark、Hadoop等实现分布式的存储和计算,并基于这些基础设施,设计了构建引擎和查询引擎来分别实现数据的构建和查询。在查询引擎部分,Kylin使用了Calcite来实现SQL的解析、优化和执行。

什么是Calcite

Calcite是一个用于优化异构数据源的查询处理的基础框架,提供了标准的 SQL 语言、多种查询优化和连接各种数据源的能力。从功能上看,它支持SQL 解析、SQL 校验、SQL 查询优化、SQL 生成、数据连接查询等,但不包括数据处理和存储。Calcite的架构如图所示:

Kylin查询源码分析

数据处理和存储系统提供元数据和规则至Calcite,Calcite提供JDBC Server面向客户端查询,并对SQL查询请求进行处理,在Calcite中,一个SQL的解析和执行大概经过以下5个步骤:

  1. 将SQL解析成抽象语法树;
  2. 对抽象语法树进行校验;
  3. 将抽象语法树解析成关系代数表达式;
  4. 对关系代数表达式进行优化,在保持语义不变的前提下,转化为较优的表达式;
  5. 将优化后关系代数表达式转化为物理执行计划并计划,返回最终的结果。

目前Calcite在大数据和数据存储领域有着广泛的使用,如表所示:

Kylin查询源码分析

Kylin、Phoenix、Hive、Flink等均使用Calcite实现JDBC驱动、SQL解析、SQL校验、SQL 查询优化等。

Kylin查询源码分析

数据模型

在源码分析时,我们使用Kylin的官方数据模型示例,如图所示:

Kylin查询源码分析

该雪花模型包含以下5张表:

  1. KYLIN_SALES,销售事实表;
  2. KYLIN_ACCOUNT,用户维度表;
  3. KYLIN_CAL_DT,日期维度表;
  4. KYLIN_CATEGORY_GROUPING,类别维度表
  5. KYLIN_COUNTR,国家维度表。

示例SQL如下所示:

用于查询各站点来自美国消费者的销售额。

入口

Kylin支持多种查询入口,包括WEB控制台、REST API、JDBC驱动、ODBC驱动等。这里介绍了一下JDBC驱动的实现。

当客户端使用JDBC接口访问时,加载的JDBC驱动是org.apache.kylin.jdbc.Driver,这里,Kylin使用了JDBC驱动框架Avatica,Driver即继承自org.apache.calcite.avatica.UnregisteredDriver,覆盖了getFactoryClassName方法,如下所示:

该段代码说明仅支持JDBC 4.0即以上版本协议,并返回了相应的工厂类。工厂类KylinJdbcFactory实现了AvaticaFactory接口,用于创建JDBC相关接口实例,部分代码如下:

该段代码说明JDBC相关接口的实现是在Avatica框架实现基础的进一步继承和扩展,例如,ResultSet接口实现是KylinResultSet,其是AvaticaResultSet的子类,KylinResultSet主要覆盖了AvaticaResultSet的execute方法,该方法的核心代码如下所示:

该段代码说明获取IRemoteClient实例,执行executeQuery方法返回查询结果,而从IRemoteClient的实现KylinClient中的代码可以看到,其实质上是调用kylin-server模块的REST API “kylin/api/query”来实现查询。

那具体看一下该API的服务端,略过Controller层、缓存命中、注释删除等环节,查询代码在org.apache.kylin.rest.service.QueryService的executeRequest方法中,如下所示:

该段代码仍是基于JDBC接口,而connection通过org.apache.kylin.query.QueryConnection的getConnection方法创建,代码如下所示:

其加载的JDBC驱动是org.apache.calcite.jdbc.Driver,说明后续基于Calcite进行SQL解析、校验、优化和执行。这里,通过Calcite标准的model字段传入元数据描述文件

元数据

元数据描述文件示例如下所示:

OLAPSchemaFactory类实现了Calcite的SchemaFactory接口,创建OLAPSchema类实例,而OLAPSchema类则通过读取HBase上存储的元数据信息生成OLAPTable类的Map集合,代码如下所示:

OLAPTable类实现了Calcite的QueryableTable和TranslatableTable接口(这两个接口均继承自Table接口),用于描述表,其中比较重要的几个方法如下所示:

该方法在Table接口中定义,用于获取表字段信息,Kylin除了按Calcite定义返回RelDataType类型的字段信息,也会按自身定义保存ColumnDesc类型的字段集合,其中包含维度信息,用于后续执行物理查询时判断从哪些Cuboid扫描数据。

该方法在Table接口中定义,用于获取表的行数等统计信息,在CBO方式的优化中计算成本,但是Kylin存储引擎统计的是各Cuboid的统计信息,所以这里统一返回固定值。

该方法在TranslatableTable接口中定义,说明在优化过程中,扫描表数据的关系表达式节点会转化为OLAPTableScan类实例,关于OLAPTableScan类会在后续优化、执行过程中再介绍。

同时,OLAPTable还有一些方法用于返回Enumerable接口实例(也就是Kylin实现的OLAPQuery类),如下所示:

这些方法在执行物理查询时,Calcite会通过反射进行调用,获取OLAPQuery类,实际的数据扫描委托给OLAPQuery完成,关于OLAPQuery类会在后续优化、执行过程中再介绍。

解析

查询请求传递到服务端,并在服务端执行stat.executeQuery(correctedSql)后,会进入具体的查询流程,首先进行SQL的解析。Calcite的语法解析是基于JavaCC实现的。JavaCC是一个语法解析器生成框架, 其根据预先定义的规则生成相应的解析器代码。Calcite的语法解析规则是calcite-core中的codegen/templates/Parser.jj,根据其生成的解析器类是org.apache.calcite.sql.parser.impl. SqlParserImpl。调用该类实例解析SQL生成抽象语法树(即SqlNode)的代码在CalcitePrepareImpl中,如下所示:

示例SQL经过解析得到的抽象语法树如图所示:

Kylin查询源码分析

树中的每个节点是SqlNode子类实例。

校验

抽象语法树通过SqlValidatorImpl类的validate方法进行校验,校验的细节此处暂不展开,仅列出校验的主要步骤包括:

  1. 对抽象语法树根节点进行标准化重写,在保持语义的前提下,将SqlOrderBy、SqlDelete、SqlUpdate、SqlMerge等类型节点重写为SqlSelect类型节点;
  2. 调用各节点的validate方法进行校验。

代码如下:

所以,上一步的抽象语法树经过校验会转化为下图:

Kylin查询源码分析

关系代数表达式

校验后的抽象语法树通过SqlToRelConverter 类的convertQueryRecursive方法进一步解析成关系代数表达式。这个方法代码如下所示:

从这个方法的命名就可以看出,方法内部是在递归调用,从抽象语法树根节点开始,根据其类型,分别调用对应的convertSelect、convertInsert、convertDelete、convertUpdate、convertMerge等方法,转化为RelNode类型实例(RelNode是关系代数表达式节点接口),而在这些方法内部,会对传入节点的子节点,根据其类型,再递归调用这些方法,从而将抽象语法树所有节点均转化为RelNode类型实例,并建立相互之间的关系。通过convertSelect方法具体转化SqlSelect类型节点的代码部分如下所示:

其依次对from、where、groupBy、orderBy等子节点进行转化。最终,上一步的抽象语法树进行转化后得到下列关系代数表达式:

其根节点排序(LogicalSort),叶子节点是两张表的数据扫描(OLAPTableScan)

优化

在转化得到关系代数表达式后,会进一步对其进行优化,在保持语义不变的前提下,对表达式进行转化和调整以找到最优的表达式。优化器可以分为2类:

  1. 基于规则的优化器(Rule Based Optimizer,简称RBO):根据优化规则将一个关系表达式转化为另外一个关系表达式,同时原有表达式被放弃,经过一系列转化后生成最终表达式;
  2. 基于成本的优化器(Cost Based Optimizer,简称CBO):根据优化规则对关系表达式进行转换,同时原有表达式也会保留,经过一系列转化后生成多个表达式,之后计算每个表达式的成本,从中挑选成本最小的表达式作为最终表达式。

Calcite有两个优化器实现:

  1. HepPlanner: RBO的实现,按照规则进行匹配,直到达到次数限制或者遍历后无匹配规则;
  2. VolcanoPlanner: CBO 的实现,一直迭代各规则,直到找到成本最小的表达式。

Calcite的优化在Prepare类的optimize方法中,部分代码如下所示:

首先生成一个VolcanoPlanner类型的优化器实例,然后通过getProgram获取Program接口实例,并通过该接口的run方法执行优化。Program接口有多个实现,getProgram方法最终是通过Programs类的standard方法获取的SequenceProgram类实例,代码如下所示:

也就是说,优化可划分为串行执行的5步,包括将子查询转化为Join操作、删除无用字段等,其中第三步是使用已创建的VolcanoPlanner类型优化器实例进行优化。关系代数表达式的叶子节点是OLAPTableScan类型,该类覆盖了RelNode的register方法,其中添加了Kylin扩展的多个规则,如下表所示:

说明
OLAPToEnumerableConverterRule 将RelNode类型节点转化为OLAPToEnumerableConverter类型节点
OLAPFilterRule 将LogicalFilter类型节点转化为OLAPFilterRel类型节点
OLAPProjectRule 将LogicalProject类型节点转化为OLAPProjectRel类型节点
OLAPAggregateRule 将LogicalAggregate类型节点转化为OLAPAggregateRel类型节点
OLAPJoinRule 将LogicalJoin 类型节点转化为 OLAPJoinRel或OLAPFilterRel类型节点
OLAPLimitRule 将Sort类型节点转化为OLAPLimitRel类型节点
OLAPSortRule 将Sort类型节点转化为OLAPSortRel类型节点
OLAPUnionRule 将Union类型节点转化为OLAPUnionRel类型节点
OLAPWindowRule 将Window类型节点转化为OLAPWindowRel类型节点
OLAPValuesRule 将LogicalValues类型节点转化为OLAPValuesRel类型节点

同时,还删除了多个Calcite原生的规则,部分如下所示:

以此来保持表达式中的一些模式,便于后续物理执行计划的相关操作。经过上述优化后,关系表达式转化为如下结果:

执行

最后是将关系代数表达式转化为实际物理执行计划,扫描HBase中的数据并返回结果,这里正在梳理过程中,可先参考官方推荐的文档https://www.jianshu.com/p/21df8303d2ae了解其原理,其中,会执行OLAPTableScan类的implement方法,如下所示:

通过反射调用OLAPQuery类的相关方法,这些方法在之前介绍元数据时曾提及,其均返回Enumerable接口实例。以OLAPEnumerator为例,其在迭代获取结果时,实质上是调用queryStorage方法,代码如下所示:

获取相应的IStorageQuery接口实例,通过协处理器扫描HBase数据。

标签:

Kylin构建源码分析

1 摘要 Kylin作为MOLAP的代表之一,其核心思想是设计cube模型,指定维度和量度,通过在维度上进行量度的预先上卷计算,保存上卷结果,以空间换时间,加速维度...

阅读全文

使用Hive存储数据实践

数据存储需求是:每天会生成大量文章数据,每条文章数据包含标题、内容、URL、发表时间等多个字段,数据后续不会更新,因此考虑使用Hive作为数据仓库存储这些...

阅读全文

storm-kafka KafkaSpout原理分析

Storm Spout 通过实现Storm中的ISpout接口,重写其中的nextTuple、ack和fail方法,可以实现tuple流的发送、成功确认、失败重发。ISpout接口代码如下所示。 ...

阅读全文