全部产品
云市场

查询优化器介绍

更新时间:2019-11-20 17:19:50

DRDS接收到一条SQL后的执行过程大致如下:

  1. 语法解析器(Parser)将 SQL 文本解析成抽象语法树(AST)
  2. 语法树被转化成基于关系代数的逻辑计划
  3. 优化器(Optimizer)对逻辑计划进行优化得到物理计划
  4. 执行器(Executor)执行该计划,得到查询结果并返回给用户

x

本章将会介绍查询优化器的基本原理,包含:

  • 关系代数算子
  • 查询改写(RBO阶段)
  • 查询计划枚举(CBO阶段)

关系代数算子

一条 SQL 查询在数据库系统中通常被表示为一棵关系代数算子组成的,场景的算子有以下这些:

  1. Project 用于描述SQL中的Select列,包括函数计算
  2. FIlter 用于描述SQL中的Where条件
  3. Join 用于描述SQL中的Join,其对应的物理算子有HashJoin、 BKAJoin、 Nested-Loop Join、 SortMergeJoin
  4. Agg 用于描述SQL中的Group By及聚合函数,其对应的物理算子有HashAgg、SortAgg
  5. Sort 用于描述SQL中的Order By及Limit,其对应的物理算子有TopN、MemSort
  6. LogicalView 用于描述DRDS下发至MySQL(RDS或PolarDB)的SQL,其内部可能包含一个或多个逻辑算子
  7. Gather 代表从多个数据流汇集数据的操作,通常出现在LogicalView之上(若开启并行执行,则并行优化步骤会将其上拉)

例如,对于以下查询 SQL:(修改自 TPC-H Query 3)

  1. SELECT l_orderkey, sum(l_extendedprice *(1 - l_discount)) AS revenue
  2. FROM CUSTOMER, ORDERS, LINEITEM
  3. WHERE c_mktsegment = 'AUTOMOBILE'
  4. and c_custkey = o_custkey
  5. and l_orderkey = o_orderkey
  6. and o_orderdate < '1995-03-13'
  7. and l_shipdate > '1995-03-13'
  8. GROUP BY l_orderkey;

通过 EXPLAIN 命令看到 DRDS 的执行计划:

  1. HashAgg(group="l_orderkey", revenue="SUM(*)")
  2. HashJoin(condition="o_custkey = c_custkey", type="inner")
  3. Gather(concurrent=true)
  4. LogicalView(tables="ORDERS_[0-7],LINEITEM_[0-7]", shardCount=8, sql="SELECT `ORDERS`.`o_custkey`, `LINEITEM`.`l_orderkey`, (`LINEITEM`.`l_extendedprice` * (? - `LINEITEM`.`l_discount`)) AS `x` FROM `ORDERS` AS `ORDERS` INNER JOIN `LINEITEM` AS `LINEITEM` ON (((`ORDERS`.`o_orderkey` = `LINEITEM`.`l_orderkey`) AND (`ORDERS`.`o_orderdate` < ?)) AND (`LINEITEM`.`l_shipdate` > ?))")
  5. Gather(concurrent=true)
  6. LogicalView(tables="CUSTOMER_[0-7]", shardCount=8, sql="SELECT `c_custkey` FROM `CUSTOMER` AS `CUSTOMER` WHERE (`c_mktsegment` = ?)")

用树状图表示如下:

x

注意,左边的 LogicalView 实际包含了 ORDERS 和 LINEITEM 两张表的 Join。EXPLAIN 结果中 LogicalView 的 SQL 属性也体现了这一点。

本章将会介绍DRDS查询优化器的基本原理,DRDS优化过程主要分为以下两个步骤:

  1. 查询改写(RBO阶段)
  2. 查询计划枚举 (CBO阶段)

x

查询改写(RBO)

查询改写(SQL Rewrite)阶段输入为逻辑执行计划,输出为逻辑执行计划。这一步主要应用一些启发式规则,是基于规则的优化器(Rule-Based Optimizer,简称 RBO),所以也常被称为 RBO 阶段。

查询改写这一步的主要功能有:

子查询去关联化

子查询去关联化 (Subquery Unnesting)是将含有关联项的子查询(关联子查询)表示为 SemiJoin 或类似的算子,便于后续的各种优化处理,例如下推到 MySQL 或在 DRDS 层选择某种算法执行。

下面是一个例子:IN 子查询转化为SemiJoin 算子,并最终转化成 SemiHashJoin 物理算子由 DRDS 进行执行:

  1. > explain select id from t1 where id in (select id from t2 where t2.name = 'hello');
  2. SemiHashJoin(condition="id = id", type="semi")
  3. Gather(concurrent=true)
  4. LogicalView(tables="t1", shardCount=2, sql="SELECT `id` FROM `t1` AS `t1`")
  5. Gather(concurrent=true)
  6. LogicalView(tables="t2_[0-3]", shardCount=4, sql="SELECT `id` FROM `t2` AS `t2` WHERE (`name` = ?)")

算子下推

算子下推是非常关键的一步,DRDS 内置了各种算子的下推优化规则,包括:

  1. 谓词下推/列裁剪:将Filter及Project算子下推至MySQL执行,过滤掉不需要的行和列
  2. Join Clustering:将Join按照拆分方式及拆分键相等进行重排和聚簇,方便下一步的Join下推
  3. Join下推:对于符合条件的Join,将其下推至MySQL执行
  4. Agg下推:将聚合(Agg)拆分为FinalAgg+LocalAgg两个阶段,并将LocalAgg下推至MySQL
  5. Sort下推:将排序(Sort)拆分为MergeSort+LocalSort两个阶段,并将LocalSort下推至MySQL

受篇幅限制,我们将查询下推单独放在“查询改写与下推”这篇文档中。

查询计划枚举(CBO)

经过查询改写阶段的逻辑执行计划会被输入到查询计划枚举(Plan Enumerator),输出一个最终的物理执行计划。

查询计划枚举在多个可行的查询计划中,根据预先定义的代价模型,选择出代价最低的一个。与查询改写阶段不同,在查询计划枚举中,规则可能产生更好的执行计划,也可能产生更差的执行计划,我们会根据前后的代价相比较来选择出较优的那个,因此这也被称为基于代价的优化(Cost-based Optimizer,简称 CBO)。

其核心组件有以下几个部分:

  • 统计信息(Statistics)
  • 基数估计(Cardinality Estimation)
  • 转化规则(Transform Rules)
  • 代价模型(Cost Model)
  • 计划空间搜索引擎(Plan Space Search Engine)

逻辑上,CBO 的过程可以看作以下这样:

  1. 搜索引擎利用转化规则,对输入的逻辑执行计划进行变换,构造出物理执行计划的搜索空间
  2. 之后,利用代价模型对搜索空间中的每一个执行计划进行代价估计,选出代价最低的物理执行计划。
  3. 而代价估计的过程离不开基数估计:它利用各个表、列的统计信息,估算出各算子的输入行数、选择率等信息,提供给算子的代价模型,从而估算出查询计划的代价。

查询计划枚举(CBO)的实现比较复杂,有兴趣的读者可以参考论文《The Volcano Optimizer Generator》。