半连接物化的两种策略

IN、=ANY 子查询进行半连接(Semi-Join)优化时,其中一种策略就是子查询物化,即生成一张内存或者磁盘的临时表(称为物化表),来存储子查询的执行结果,然后物化表主查询进行连接,以获取最终的结果集

本文翻译自 MariaDB 官方文档,主要介绍使用物化表进行半连接优化的两种策略

以下为翻译内容

半连接物化是子查询半连接优化的一种特殊的子查询物化,包含两种策略:

  • 物化查询(Materialization/lookup)
  • 物化扫描(Materialization/scan)

1. 原理

以一个查找欧洲拥有大城市的国家的 SQL 为例:

1select * from Country 
2where Country.code IN (
3    select City.Country 
4    from City 
5    where City.Population > 7*1000*1000
6) and Country.continent='Europe'

示例 SQL 中,子查询为不相关子查询,因此,可以先单独执行子查询。半连接物化就是先执行子查询,把大城市记录中的 City.country 字段插入到临时表(即物化表)中,然后和 Country 表中欧洲国家对应的记录进行连接操作,过程示意图如下:

连接可以从两个方向进行:

  • 以物化表为驱动表,Country 表为被驱动表进行连接操作 因为该策略会对物化表进行全表扫描,所以被称为物化扫描

  • Country 为驱动表,物化表为被驱动表进行连接操作 使用该策略时,从物化表中查找匹配Country表中记录成本最低的方式,是使用物化表的主键进行查找(正好,物化表有一个用于对表中主键进行去重的主键)。因此,这种策略被称为物化查询

2. 实战

2.1 物化扫描

查找 City 表中人口大于 700 万的城市时,优化器会使用物化扫描,查询执行计划如下:

从上图的查询执行计划,可以得知:

  • 查询中仍然是有 2 个 SELECT 语句(通过 id 列的 id = 1 及 id = 2 可知)
  • id = 2 的查询的 select_type = MATERIALIZED,这说明子查询执行之后,结果集会存储到临时表(即物化表)中,物化表会有一个主键,用于避免表中包含重复的记录
  • 第 1 条记录中,table 列的的值为 <subquery2>,这个表就是存储了子查询结果的 id = 2 的物化表

优化器选择对物化表进行全表扫描,因此,这就是一个使用物化扫描策略的例子

至于查询成本,需要从 City 表读取 15 条记录,往物化表中写入 15 条记录,然后再从物化表中读取这 15 条记录(优化器假定 City 表中没有重复记录),接着使用 eq_ref 方式对 Country 表进行 15 次读取,总计会进行 45 次读和 15 次写

作为比较,在 MySQL 中查看示例 SQL 的执行计划,会得到下图所示的执行计划:

上面 MySQL 的执行计划,会进行 239 + 239 * 15 = 3824 次读表操作

译注:

在 MySQL 5.7.35 中运行,得到的查询计划和 MariaDB 类似,也会使用物化表 参照 2.2 物化查询 中的说明,在 MySQL 中应该是要把 optimizer_switchsemijoinmaterialization 都设置为 off 才会得到上图所示的执行计划

2.2 物化查询

接下来稍微修改下示例 SQL,改为查找人口大于 100 万的城市:

上图中执行计划,除了以下 2 个区别之外,其它的都和物化扫描一样:

  • <subquery2> 表的访问方式由 ALL 变成了 eq_ref
  • 使用了索引 distinct_key

这说明优化器计划对物化表使用索引查找,换句话说就是会使用物化查找策略

MySQL 中(把 optimizer_switchsemijoinmaterialization 都设置为 off),会得到如下图所示的执行计划:

上面两组 MariaDB 的执行计划中,对于 Country 表都会进行全表扫描。对于第二组执行计划(译注:物化查找),MariaDB 会填充物化表(从 City 表读取 238 条记录,然后把它们写入临时表),然后对于 Country 表的的每一条记录,都会对物化表进行一次按主键查找操作,也就是会进行 238 次主键查找。总计会进行 239 + 238 = 477 次读操作,以及对临时表(即物化表)进行 238 次写操作

MySQL 中,第二组执行计划,对于 Country 表的每条记录,都需要使用 CityCountry 列上的索引从 City 表读取 18 条记录,计算出来的成本为 18 * 239 = 4302 如果子查询的调用次数更少,这个执行计划有可能比使用物化表的查询执行计划更优。顺便说一下,MariaDB 也可使用类似这样的执行计划(首次匹配策略),但是没有选择使用

3. 包含 Group By 子句的子查询

子查询包含 Group By 子句时,MariaDB 也可以使用半连接物化策略来优化子查询(其它半连接优化策略不支持这种场景)

这能够高效的执行像查找分组中最大/最小的元素这类的查询

例如,查找每个洲人口最多的城市,执行计划如下:

查询结果如下:

4. 总结

半连接物化:

  • 可以用于不相关的 IN 子查询,子查询中可以使用 Group By 子句、聚合函数(两者可以同时出现,也可以只出现一者)
  • 执行计划输出结果中,type = MATERIALIZED 的行对应子查询,table = <subqueryN> 对应主查询中的子查询部分
  • 系统变量 optimizer_switchmaterializationsemijoin 都设置为 on 时才能使用半连接物化
  • materialzation = on|off 也可以用于设置 `不使用半连接物化



欢迎扫码关注公众号,我们一起学习更多 MySQL 知识: