ToB企服应用市场:ToB评测及商务社交产业平台

标题: Semi-Join Subquery优化策略 [打印本页]
作者: 金歌    时间: 2023-5-6 22:09
标题: Semi-Join Subquery优化策略
Semi-Join Subquery优化策略

Semi-Join Subquery(半连接子查询)：对应IN或EXISTS子查询，仅需要检查"外表记录"在"子查询结果集"中是否存在匹配记录，不需要计算"子查询结果集"中记录匹配次数，也不需要返回"子查询结果集"中匹配记录内容
在MariaDB(MySQL)中，常用优化Semi-Join(半连接)的策略有：
First Match策略

当循环"外部查询结果集"的每条记录去"子查询中"确认"是否匹配"时，只需要找到第一条匹配记录(First Match)既可跳出子查询。
如下面查询：
  1. SELECT * FROM Country
  2. WHERE Country.code IN (
  3.     SELECT City.Country
  4.     FROM City
  5.     WHERE City.Population > 1*1000*1000
  6. )
  7. AND Country.continent='Europe'
复制代码
如果不使用First Match策略，当处理到Country表上满足" Country.continent='Europe' "条件的德国(Deu)记录时，会扫描City表上满足" City.Population > 110001000 AND City.Country='DEU' "的所有记录，再根据匹配记录总数返回"是否匹配"结果：

如果使用First Match策略，当处理到Country表上满足" Country.continent='Europe' "条件的德国(Deu)记录时，会扫描City表上满足" City.Population > 110001000 AND City.Country='DEU' "的第一条记录"Berlin"后，立即返回"是否匹配"结果：

在MariaDB上使用First Match策略的查询的执行计划为：
  1. MariaDB [world]> explain select * from Country where Country.code IN (select City.Country from City where City.Population > 1*1000*1000) and Country.continent='Europe';
  2. +----+-------------+---------+------+--------------------+-----------+---------+--------------------+------+----------------------------------+
  3. | id | select_type | table   | type | possible_keys      | key       | key_len | ref                | rows | Extra                            |
  4. +----+-------------+---------+------+--------------------+-----------+---------+--------------------+------+----------------------------------+
  5. |  1 | PRIMARY     | Country | ref  | PRIMARY,continent  | continent | 17      | const              |   60 | Using index condition            |
  6. |  1 | PRIMARY     | City    | ref  | Population,Country | Country   | 3       | world.Country.Code |   18 | Using where; FirstMatch(Country) |
  7. +----+-------------+---------+------+--------------------+-----------+---------+--------------------+------+----------------------------------+
  8. 2 rows in set (0.00 sec)
复制代码
MariaDB的执行计划中会有明显的FirstMatch标识。
在MySQL上使用First Match策略的查询的执行计划为：
  1. MySQL [world]> explain select * from Country  where Country.code IN (select City.Country from City where City.Population > 1*1000*1000) and Country.continent='Europe';
  2. +----+--------------------+---------+----------------+--------------------+-----------+---------+-------+------+------------------------------------+
  3. | id | select_type        | table   | type           | possible_keys      | key       | key_len | ref   | rows | Extra                              |
  4. +----+--------------------+---------+----------------+--------------------+-----------+---------+-------+------+------------------------------------+
  5. |  1 | PRIMARY            | Country | ref            | continent          | continent | 17      | const |   60 | Using index condition; Using where |
  6. |  2 | DEPENDENT SUBQUERY | City    | index_subquery | Population,Country | Country   | 3       | func  |   18 | Using where                        |
  7. +----+--------------------+---------+----------------+--------------------+-----------+---------+-------+------+------------------------------------+
  8. 2 rows in set (0.01 sec)
复制代码
MariaDB的执行计划中仅显示为依赖子查询(DEPENDENT SUBQUERY)
First Match策略和将IN子查询转换为EXISTS依赖子查询很相似，但两者还是存在明显差异，并非所有EXISTS操作都能使用First Match策略，如子查询中使用GROUP BY相关的聚合函数时，需要先完成GROUP BY操作才能确认"是否匹配"。
Table Pullout策略

当子查询的查询列表项只有主键或唯一索引键时，能推算出"子查询结果集"不存在重复记录，因此可以将子查询改为关联查询，即将子查询中的表上提到关联查询。
对于查询：
  1. SELECT *
  2. FROM City
  3. WHERE City.Country IN (
  4.         SELECT Country.Code
  5.         FROM Country
  6.         WHERE Country.Population < 100*1000
  7. );
复制代码
在MariaDB 5.2 和MySQL 5.6版本及之前版本上，执行计划为：
  1. MySQL [world]> explain select * from City where City.Country in (select Country.Code from Country where Country.Population < 100*1000);
  2. +----+--------------------+---------+-----------------+--------------------+---------+---------+------+------+-------------+
  3. | id | select_type        | table   | type            | possible_keys      | key     | key_len | ref  | rows | Extra       |
  4. +----+--------------------+---------+-----------------+--------------------+---------+---------+------+------+-------------+
  5. |  1 | PRIMARY            | City    | ALL             | NULL               | NULL    | NULL    | NULL | 4079 | Using where |
  6. |  2 | DEPENDENT SUBQUERY | Country | unique_subquery | PRIMARY,Population | PRIMARY | 3       | func |    1 | Using where |
  7. +----+--------------------+---------+-----------------+--------------------+---------+---------+------+------+-------------+
  8. 2 rows in set (0.00 sec)
复制代码
如果Country.Code是主键或唯一索引，则可以将SQL改写为：
  1. SELECT City.*
  2. FROM City
  3. INNER JOIN Country
  4. ON City.Country=Country.Code
  5. WHERE Country.Population < 100*1000;
复制代码
改为关联查询后，可以根据两张关联表的统计数据来选择驱动表和被驱动表，因此在MariaDB 5.3或MySQL 5.7版本，执行计划为：
  1. MariaDB [world]> explain select * from City where City.Country in (select Country.Code from Country where Country.Population < 100*1000);
  2. +----+-------------+---------+-------+--------------------+------------+---------+--------------------+------+-----------------------+
  3. | id | select_type | table   | type  | possible_keys      | key        | key_len | ref                | rows | Extra                 |
  4. +----+-------------+---------+-------+--------------------+------------+---------+--------------------+------+-----------------------+
  5. |  1 | PRIMARY     | Country | range | PRIMARY,Population | Population | 4       | NULL               |   37 | Using index condition |
  6. |  1 | PRIMARY     | City    | ref   | Country            | Country    | 3       | world.Country.Code |   18 |                       |
  7. +----+-------------+---------+-------+--------------------+------------+---------+--------------------+------+-----------------------+
  8. 2 rows in set (0.00 sec)
复制代码
Materialization策略

在使用Table Pullout策略时，需要能明确推算出"子查询结果集"不存在重复记录时才能将"子查询"改为"关联查询"，如果将"子查询结果集"通过临时表去重固化后消除重复记录，则可以将子查询转换为"关联查询"，即Materialization策略。
如对于查询：
  1. SELECT * FROM Country
  2. WHERE Country.code IN (
  3.     SELECT City.Country
  4.     FROM City
  5.     WHERE City.Population > 1*1000*1000
  6. )
  7. AND Country.continent='Europe'
复制代码

在转换为"关联查询"后，按照"关联查询"中临时表是否为"驱动表"可以将Semi-join Materialization策略细分为：
使用Materialization/scan 策略时，MariaDB 查询计划为：
  1. MariaDB [world]> explain select * from Country where Country.code IN (select City.Country from City where  City.Population > 7*1000*1000);
  2. +----+--------------+-------------+--------+--------------------+------------+---------+--------------------+------+-----------------------+
  3. | id | select_type  | table       | type   | possible_keys      | key        | key_len | ref                | rows | Extra                 |
  4. +----+--------------+-------------+--------+--------------------+------------+---------+--------------------+------+-----------------------+
  5. |  1 | PRIMARY      | <subquery2> | ALL    | distinct_key       | NULL       | NULL    | NULL               |   15 |                       |
  6. |  1 | PRIMARY      | Country     | eq_ref | PRIMARY            | PRIMARY    | 3       | world.City.Country |    1 |                       |
  7. |  2 | MATERIALIZED | City        | range  | Population,Country | Population | 4       | NULL               |   15 | Using index condition |
  8. +----+--------------+-------------+--------+--------------------+------------+---------+--------------------+------+-----------------------+
  9. 3 rows in set (0.01 sec)
复制代码
使用Materialization/lookup 策略时，MariaDB 查询计划为：
  1. MariaDB [world]> explain select * from Country where Country.code IN (select City.Country from City where  City.Population > 1*1000*1000) ;
  2. +----+--------------+-------------+--------+--------------------+--------------+---------+------+------+-----------------------+
  3. | id | select_type  | table       | type   | possible_keys      | key          | key_len | ref  | rows | Extra                 |
  4. +----+--------------+-------------+--------+--------------------+--------------+---------+------+------+-----------------------+
  5. |  1 | PRIMARY      | Country     | ALL    | PRIMARY            | NULL         | NULL    | NULL |  239 |                       |
  6. |  1 | PRIMARY      | <subquery2> | eq_ref | distinct_key       | distinct_key | 3       | func |    1 |                       |
  7. |  2 | MATERIALIZED | City        | range  | Population,Country | Population   | 4       | NULL |  238 | Using index condition |
  8. +----+--------------+-------------+--------+--------------------+--------------+---------+------+------+-----------------------+
  9. 3 rows in set (0.00 sec)
复制代码
Loose Scan策略

在Materialization/scan 策略时，需要先将"子查询结果集"移除重复记录并固化到临时表，再作为驱动表进行关联查询。MySQL特性Index Loose Scan能在一次扫描中得跳过重复索引键得到"没有重复记录的临时结果集"，Loose Scan策略基于Index Loose Scan特性保证关联查询不会出现"重复关联问题"。
如对于查询：
  1. SELECT * FROM Country  
  2. WHERE Country.code IN (
  3.     SELECT country_code FROM Satellite
  4. )
复制代码
如果Satellite.country_code 存在索引，基于Index Loose Scan特性则能快速获得"SELECT DISTINCT country_code FROM Satellite"的效果，如图所示：

使用Loose Scan 策略时，MariaDB 查询计划为：
  1. MariaDB [world]> explain select * from Country where Country.code in (select country_code from Satellite);
  2. +----+-------------+-----------+--------+---------------+--------------+---------+------------------------------+------+-------------------------------------+
  3. | id | select_type | table     | type   | possible_keys | key          | key_len | ref                          | rows | Extra                               |
  4. +----+-------------+-----------+--------+---------------+--------------+---------+------------------------------+------+-------------------------------------+
  5. |  1 | PRIMARY     | Satellite | index  | country_code  | country_code | 9       | NULL                         |  932 | Using where; Using index; LooseScan |
  6. |  1 | PRIMARY     | Country   | eq_ref | PRIMARY       | PRIMARY      | 3       | world.Satellite.country_code |    1 | Using index condition               |
  7. +----+-------------+-----------+--------+---------------+--------------+---------+------------------------------+------+-------------------------------------+
复制代码
Loose Scan 策略和Materialization/scan 策略区别：
Duplicate Weedout策略

当无法根据表结构信息推算出"子查询结果集"不存在重复记录时，如果将子查询改写为关联查询，则会导致"外表记录"被关联匹配多次而产生重复记录，可以通过将关联结果集插入到"带有唯一索引的临时表"的方式来移除重复记录，保证最终查询结果的准确性。
对于查询：
  1. SELECT *
  2. FROM Country
  3. WHERE Country.code IN (
  4.     SELECT City.Country
  5.     FROM City
  6.     WHERE City.Population > 0.33 * Country.Population
  7.     AND City.Population > 1*1000*1000
  8. );
复制代码
可以改写为：
  1. CREATE tmp_Country LIKE Country;
  3. INSERT IGNORE INTO tmp_Country
  4. SELECT Country.*
  5. FROM Country
  6. INNER JOIN City
  7. ON Country.code = City.Country
  8. WHERE City.Population > 0.33 * Country.Population
  9. AND City.Population > 1*1000*1000
  11. SELECT * FROM tmp_Country;
复制代码
如图所示：

使用Duplicate Weedout 策略时，MariaDB 查询计划为：
  1. explain select * from Country where Country.code IN (select City.Country from City where City.Population > 0.33 * Country.Population and City.Population > 1*1000*1000)\G
  2. *************************** 1. row ***************************
  3.            id: 1
  4.   select_type: PRIMARY
  5.         table: City
  6.          type: range
  7. possible_keys: Population,Country
  8.           key: Population
  9.       key_len: 4
  10.           ref: NULL
  11.          rows: 238
  12.         Extra: Using index condition; Start temporary
  13. *************************** 2. row ***************************
  14.            id: 1
  15.   select_type: PRIMARY
  16.         table: Country
  17.          type: eq_ref
  18. possible_keys: PRIMARY
  19.           key: PRIMARY
  20.       key_len: 3
  21.           ref: world.City.Country
  22.          rows: 1
  23.         Extra: Using where; End temporary
  24. 2 rows in set (0.00 sec)
复制代码
学习总结

First Match策略通过"找到第一条匹配记录即返回"的方式来跳过无效子查询扫描。
除First Match策略外都是子查询转换为关联查询来优化提升查询效率，按照不同查询场景采用不同策略来"避免重复记录"：
参考资料

Semi-join Subquery Optimizations

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4