半联接子查询有一种格式
SELECT ... FROM outer_tables WHERE expr IN (SELECT ... FROM inner_tables ...) AND ...
即,子查询是一个IN-subquery,并且它位于WHERE子句中。这最重要的部分
是半联接子查询,我们只对外表的记录在子查询配置的感兴趣
可以很“自然”执行它,通过从欧洲国家开始和检查是否有这么多人口城市:
这个半联接属性还允许“倒退”执行:我们可以开始从大城市,并检查哪些国家:
对比,让我们改变子查询被非半联接:
非半联接
select * from Country where Country.COntinent='Europe' and
半联接操作是类似于普通关系连接。有一个区别在于:对半连接,你对外表的行不在乎匹配内部表多少行。在上面的国家与大城市的例子,德国将会返回一次,即使它有三个城市人口超过一百万的。
semi-join subquery优化策略
1:Table
pullout optimization
有以下两个要求
表撤出,只可能在半连接子查询。
表撤销是基于唯一/主键定义。
eg:
select * from City where City.Country in (select Country.Code from Country where Country.Population < 100*1000);
1是半联接子查询，2是code 是唯一索引/主键
优化后：
select `* from `world`.`City` join `world`.`Country` where ((`world`.`City`.`Country` = `world`.`Country`.`Code`) and (`world`.`Country`.
`Population` < (100 * 1000)))
2:DuplicateWeedout 策略
这个想法是像运行常规内连接一样运行半联接 ,然后使用临时表消除重复记录的组合。
eg: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);
首先,我们运行一个城市和国家表常规内连接:
MariaDB [world]> 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
*************************** 1. row ***************************
possible_keys: Population,Country
*************************** 2. row ***************************
possible_keys: PRIMARY
2 rows in set (0.00 sec)
这个查询将从city表读取238行,对于它们中的每一行将在country表做一个主键查找,扫描另一个238行。这总共476行,您需要添加238次在临时表查找(这通常是快很多自临时表在内存)。
如果我们在MySQL运行相同的EXPLAIN,我们会得到:
mysql> 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)
*************************** 1. row ***************************
possible_keys: NULL
*************************** 2. row ***************************
possible_keys: Population,Country
2 rows in set (0.00 sec)
这个计划将读取(239 + 239 * 18)= 4541行,这是要慢得多。
实况报道
在EXPLAIN DuplicateWeedout显示为"Start temporary/End
temporary"。
这个策略可以处理相关子查询。
但它不能应用，如果子查询有有意义的GROUP BY和/聚合函数。
DuplicateWeedout允许优化器自由混合子查询的表和外部选择的表。
对DuplicateWeedout没有单独的@@optimizer_switch标志 DuplicateWeedout。该策略可以被禁用,通过关掉所有半连接的优化set
@@optimizer_switch = ' optimizer_semijoin = off”命令
让我们用通常的例子,一个寻找有大城市的国家:
select * from Country
where Country.code IN (select City.Country from City
where City.Population > 1*1000*1000) and Country.cOntinent='Europe'
假设,我们的执行计划是找到在欧洲的国家,然后,对于每一个国家, 检查它发现有任何大的城市。常规内连接执行将如下所示:
既然德国有两个大的城市(在这个图中),它将被放入查询输出两次。这是不正确的, SELECT ... FROM CountrySELECT ... FROM Country不应该产生相同的国家记录两次。这个FirstMatch策略通过一旦找到第一个真正的匹配切断执行避免产生重复的行:
注意,短切必须发生在"Using where"被应用后。
FirstMatch in action
在上面的查询的EXPLAIN将如下所示:
MariaDB [world]> explain select * from
Country
+----+------+------+------+-----+---------+-------+---------+-+--------+
| id | select_type|table| type| possible_keys |
key|
key_len|ref|rows|Extra
+----+-----+------+------+--------+-------+---------+----------+------+-------+
|
|
+----+-----+----+------+-------+------+--------+-----------+------+-----------+
2 rows in set (0.00 sec)
FirstMatch(Country)在额外的列意味着一旦我们产生出了一条匹配记录组合,捷径执行和跳回到这个Country表。 FirstMatch的查询计划非常类似于一个你会在MySQL:
MySQL [world]> explain select * from
Country
+----+----+------+------+--------+-------+-----+-------+------+--------------+
| id |select_type|table| type|possible_keys | key|
key_len | ref| rows |
Extra
+----+---+-------+-----+-----+-----------+-------+------+-----+---------------+
|
|
+----+----------+---------+----------+--------+------+-----+------+------+----+
2 rows in set (0.01 sec)
和这两个特定的查询计划将执行在同一时间。
FirstMatch和IN->EXISTS之间的差异
FirstMatch策略背后的主要思想和IN->EXISTS转换的背后主要思想是,然而,FirstMatch有几个优势:
等效传值跨越半连接界限,但不是子查询界限。因此,将子查询转换到半连接和使用FirstMatch仍然可以给一个更好的执行计划。(TODO例子)
只有一种方法可以应用IN->EXISTS策略和MySQL会无条件地这样做。对于FirstMatch,优化器可以做一个选择是否应该运行FirstMatch策略，一旦子查询所有使用表是在连接之前,或者在以后某个时间点。(TODO:示例)
FirstMatch的策略是通过执行子查询和一旦第一个找到匹配切断其执行。
这意味着,子查询的表必须在所有的外部选择的表之后子查询谓词引用的。
EXPLAIN显示FirstMatch为“FirstMatch(tableN)”。
这个策略可以处理相关子查询。
但它不能应用如果子查询有有意义的GROUP BY或聚合函数。
使用FirstMatch策略由@@optimizer_switch中的firstmatch=on|off标志
LooseScan是对半连接子查询的一个执行策略。
思想
我们将通过示例演示LooseScan策略。假设,我们正在寻找有卫星的国家。我们可以让他们使用以下查询(为了简单起见,我们忽略多个国家组成拥有的卫星):
select * from Country
where Country.code in (select country_code from Satellite)
假设,在Satellite.country_code有一个索引。如果我们使用该索引,我们会得到结果会按照拥有卫星的国家顺序:
LooseScan的策略并不真的需要排序,它所需要的只是分组。在上面的图,卫星是按国家分组。例如,所有属于澳大利亚的卫星在一起,没有和其他国家混合的卫星。这使得它容易从每组只选择一个卫星,您可以把它的国家和没有重复的国家名单进行连接:
LooseScan 的行动
对上面的查询EXPLAIN输出如下:
MariaDB [world]> explain select * from Country where Country.code in (select country_code from Satellite);
+----+-------+-------+------+---------+--------+-------+----------+------+---+
| id | select_type|table| type| possible_keys |
key| key_len | ref| rows |
Extra
+----+-----+------+------+----+-------+------+------------+------+---------+
| 1 | PRIMARY| Satellite|
index|country_code|country_code | 9| NULL|
|
+----+-----+-----+-----+--------+------+----+------------------
实况报道
LooseScan避免重复记录的组合产生通过将子查询表放在第一位和使用其索引从重复的行选择一行记录
因此,为了适用LooseScan,子查询应该像:
expr IN (SELECT tbl.keypart1 FROM tbl ...)
或
expr IN (SELECT tbl.keypart2 FROM tbl WHERE
tbl.keypart1=const AND ...)
LooseScan 能处理相关子查询
LooseScan 可以通过在@@optimizer_switch把loosescan=off标志关闭
5:Semi-join materialization strategy
半联接物化是一种特殊的子查询物化用于半连接子查询。它实际上包含两个策略:
Materialization/lookup
Materialization/scan
思想
考虑一个查询,查找在欧洲国家,有大的城市:
select * from Country
where Country.code IN (select City.Country
from City where City.Population > 7*1000*1000) and Country.cOntinent='Europe'
子查询是不相关的,也就是说,我们可以运行它独立于外部的查询。这就是半连接物化的想法,并用大城市的City.country填写临时表。然后用欧洲国家做一个连接:
join可以在两个方向进行:
从物化表到欧洲国家
从欧洲国家到物化表
第一种方式涉及到做一个全扫描物化表,所以我们称之为“Materialization-scan”。
如果你从国家到物化表运行一个连接,最有效的方法是在物化表使用一个查找其主键找到匹配(它有一个:我们用它来消除重复的数据)。正因为如此,我们称之策略为” Materialization-lookup”。
Semi-join materialization 行动
Materialization-Scan
如果我们选择寻找城市人口超过700万,优化器将使用Materialization-Scan和EXPLAIN将展示这个:
MariaDB [world]> explain select * from Country
where Country.code IN (select City.Country from City
where
+----+-------+-------+-----+-------+-------+-------+-----------+------+-------+
| id | select_type| table
+----+--------+-------+------+---------+--------+-------+---------+------+----+
|
|
|
+----+-------+------+--------+--------+-------+-------+---------+------+------+
3 rows in set (0.01 sec)
在这里,你可以看到:
还有两个SELECTs (寻找列id = 1和id = 2)
第二个选择(id =
2)有select_type=MATERIALIZED。这意味着它将被执行,其结果将存储在一个临时表和在所有列有一个唯一键。唯一索引是防止表包含任何重复的记录。
第一个选择收到了表名& lt;subquery2>。这表是我们选择id = 2的物化得到的结果。
优化器选择做一个全扫描物化表,所以这是一个使用Materialization-Scan策略示例。
至于执行成本,我们要从city表读15行,写15行到物化表,读他们回来(优化器假定不会有任何重复的),然后做15 eq ref访问Country表。总的来说,我们将做45次读和15次写。
相比之下,如果你在MySQL运行EXPLAIN,您将得到这个:
MySQL [world]> explain select * from Country
where Country.code IN (select City.Country from City
where
+----+--------------------+---------+-------+--------------------+------------+---------+------+------+------------------------------------+
| id |
select_type
+----+--------------------+---------+-------+--------------------+------------+---------+------+------+------------------------------------+
|
|
+----+--------------------+---------+-------+--------------------+------------+---------+------+------+------------------------------------+
..计划做 (239 + 239*15) = 3824次读表
Materialization-Lookup
让我们稍微修改查询,寻找国家城市人口超过一亿(而不是七):
MariaDB [world]> explain select * from Country
where Country.code IN (select City.Country from City
where
+----+--------------+-------------+--------+--------------------+--------------+---------+------+------+-----------------------+
| id | select_type
+----+--------------+-------------+--------+--------------------+--------------+---------+------+------+-----------------------+
|
|
|
+----+--------------+-------------+--------+--------------------+--------------+---------+------+------+-----------------------+
3 rows in set (0.00 sec)
EXPLAIN输出类似于使用Materialization-scan,除了:
the
访问使用的索引为distinct_key
这意味着优化器计划在物化表做索引查找。换句话说,我们要使用Materialization-lookup策略。
在MySQL(或用optimizer_switch='semijoin=off,materialization=off'),你将得到这个EXPLAIN:
MySQL [world]> explain select * from Country
where Country.code IN (select City.Country from City
where
+----+--------------------+---------+----------------+--------------------+---------+---------+------+------+-------------+
| id |
select_type
+----+--------------------+---------+----------------+--------------------+---------+---------+------+------+-------------+
|
|
你可以看到这两个计划将做一个全扫描Country。第二步,MariaDB将填冲物化表(从表City读取238行和写入临时表),然后在Country做一个唯一索引查找,这做238唯一键查找。总的来说,第二步将成本(239 + 238)= 477 和238次写临时表。
MySQL的计划,第二步是对于来自Country每条记录使用City.Country索引读18行。这是一个成本(18 * 239)= 4302次读操作。要是有更少的子查询调用,这个计划会比一个物化好点。顺便说一下,MariaDB也有一个选项来使用这样查询计划, (见FirstMatch策略),但是它并没有选择它。
有分组的子查询
MariaDB是能够使用半连接物化策略当子查询已分组(其他半连接策略并不适用于这种情况下)。
这为了查询能高效执行,寻找最好的/最后一个元素在一个特定的组。
例如,在他们的大洲找到人口最多的城市:
explain
select * from City
where City.Population in (select max(City.Population) from City, Country
where City.Country=Country.Code
+------+--------------+-------------+------+---------------+------------+---------+----------------------------------+------+-----------------+
| id
+------+--------------+-------------+------+---------------+------------+---------+----------------------------------+------+-----------------+
|
|
|
|
+------+--------------+-------------+------+---------------+------------+---------+----------------------------------+------+-----------------+
4 rows in set (0.00 sec)
这个城市有:
+------+-------------------+---------+------------+
| ID
+------+-------------------+---------+------------+
| 1024 | Mumbai (Bombay)
| 3580 |
Moscow
| 2454 |
Macao
|
| 2515 | Ciudad de México |
MEX
|
|
+------+-------------------+---------+------------+
实况报道
半连接物化
可用于不相关的IN子查询。子查询可以使用分组的和/或聚合函数。
为子查询在EXPLAIN显示为type=MATERIALIZED和table=
当在@@optimizer_switch启用materialization=on 和semijoin=on。
materialization=on|off是与Non-semijoin
materialization共享
Non-semi-join subquery optimizations（非半联接子查询优化）
哪些语句是非半联接查询？
IN子查询某些种类的子查询不能被简化成半连接。这些子查询可以同时相关或不相关的。为了在所有情况下提供一致的性能,MariaDB对于这些类型的子查询提供了几种可选策略。当有几个策略是有可能的,优化器基于成本的估计选择最佳的一个。非半联接的两个主要策略是物化 (也称由外向内的实体化),和in-to-exists的转换。物化仅适用于非相关的子查询,而in-to-exist可用于相关和不相关子查询。
1:子查询有or
SELECT ... FROM ... WHERE (expr1, ..., exprN) [NOT] IN (SELECT ... ) OR expr;
2:否定子查询谓词（not in）
SELECT ... FROM ... WHERE ... (expr1, ..., exprN) NOT IN (SELECT ... ) ...;
3：SELECT或HAVING子句中子查询
SELECT field1, ..., (SELECT ...)
SELECT ...
4：有UNION的子查询
1：Materialization（仅对非相关子查询）
1.1什么是物化？
执行子查询和存储它的结果在一个内部临时表和所有选择的列加上索引。如果临时表的大小是小于系统变量tmp_table_size,这个表是一个hash索引内存堆表。子查询的结果超过这个限制,临时表存储在磁盘上的B -树索引表ARIA或MyISAM(ARIA是默认的)。
1.2：NULL-aware高效执行
（IN谓词会产生null结果，如果IN的任何一个参数为NULL ，（null in (select col )）,col in（select null_column））.
在所有这些情况下,IN的评估是和前段所述一样，通过索引查找到物化子查询。在所有剩余的情况下不能用FALSE替换NULL,不可能使用索引查找。这不是在服务的上一个限制,但由于NULL语义适合ANSI SQL标准。
假设一个IN谓词被判断为NULL IN(SELECT not_null_col from t1),即IN左操作数的是一个NULL值,并且在子查询没有NULL值。在这种情况下IN值既不FALSE,也不是TRUE。相反,它是NULL。如果我们在用NULL作为键执行索引查找,这样的值不会被发现在非NUL列,在谓词将错误地产生一个FALSE。
一般来说,一个NULL值在IN任何一方充当“通配符”,它可以匹配任何价值,如果一个匹配的存在,IN的结果是NULL的。考虑下面的例子:
如果左边的参数是行:(7,NULL,9),IN右边子查询结果是表:
(7, 8, 10)
(6, NULL, NULL)
(7, 11, 9)
IN谓词匹配的行(7，11，9),但结果是空的。在IN两边参数匹配不同的值是通过NULL配匹IN另一个参数,被称为部分匹配。
为了有效地计算IN谓词出现在NULL的结I, 对部分匹配MariaDB实现了两个特殊算法,详细描述
Rowid-merge partial matching
这种技术时使用子查询结果的行数超过一定限度。这项技术在临时表一些列创建特殊的索引,并通过选择每个索引扫描将其合并因此执行操作类似于交集。
Table scan partial matching
该算法用于非常小的表时，rowid-merge算法开销过大不适合。然后服务简单地扫描物化的子查询表和检查部分匹配。因为这个策略不需要任何内存缓冲区,它也用于当没有足够的内存来保存rowid合并策略的索引。
局限性
原则上,子查询物化策略是通用的,然而,由于在MariaDB服务一些技术局限,服务器在下面情况不能应用这种优化。
BLOB字段
要么IN谓词的左操作数是指一个BLOB字段,要么子查询选择一个或更多BLOB字段。
在上述情况下,服务器返回到IN-TO-EXISTS转换。
IN到EXISTS的转换
这种优化是存在于MariaDB和MySQL到MariaDB 5.3之前的老版本唯一的子查询的执行策略。我们做了各种变化,并修复了在这段代码中许多bug,但在本质上仍然是相同的。
这个优化眼下我们参考读物是MySQL文档的。
性能的讨论
速度超过MySQL 5.x和MariaDB 5.1/5.2事例
根据查询和数据,这里描述两种策略任一种可能导致数量级更好/更糟糕的计划比其他策略。
老版本的MariaDB和任何当前MySQL版本(包括MySQL 5.5和MySQL 5.6 DMR截至2011年7月)实现只有IN-TO-EXISTS转换。如下图所示,这个策略在许多常见情况下不如子查询物化。
考虑以下查询是在DBT3基准规模10的数据。查找在他们国家的顶级收益的顾客:
SELECT * FROM part WHERE p_partkey IN
ORDER BY p_retailprice DESC LIMIT 10;
运行这个查询的时间如下:
在 MariaDB 5.2/MySQL 5.x (any MySQL)执行时间: > 1 h
查询花费超过一小时(我们不等待更长的时间),这使得在这种情况下使用子查询是不切实际。下面的EXPLAIN
表明,子查询被转换成一个相关子查询,表明IN-TO-EXISTS转换。
+--+------------+-------+-------+---------+----+------+----------------+
|id|select_type |table
|type
+--+---------+------+-----+--------+---+-----+----------------------------+
| 1|PRIMARY
| 2|DEPENDENT SUBQUERY|lineitem|index_subquery|i_l_suppkey_partkey|func|14|Using where |
+--+-----+----+---------+------------+----+------+------------------------+
在MariaDB5.3执行时间: 43 sec
在MariaDB 5.3运行相同的查询只花了不到一分钟。Expalin
表明,子查询仍然是不相关的,这是一个迹象表明它是通过子查询物化执行饿。
+--+---------+--------+----+--------------+----+-----+---------------------+
|id|select_type|table |type|key
+--+---------+------+------+-------------+----+------+---------------------+
| 1|PRIMARY
| 1|PRIMARY |
| 2|MATERIALIZED|lineitem|range|l_shipdate_partkey|NULL|160060|Using where; Using index|
+--+-------+----------+------+---------+----+------+-------------------------+
这里的速度几乎是无限的,因为MySQL和老MariaDB版本不能在任何合理的时间完成查询。
为了显示部分匹配的好处我们从DBT3基准用两个额外的列扩展客户表:
c_pref_nationkey -首选购买的国家,
c_pref_brand -首选品牌.
这两列被加上前缀百分比的NULL值,即,c_pref_nationkey_05包含NULL值有5%。
考虑查询“找到在一些日期范围没有从一个首选的国家,从一个首选品牌购物所有客户”:
SELECT count(*)
FROM customer
WHERE (c_custkey, c_pref_nationkey_05, c_pref_brand_05) NOT IN
在 MariaDB 5.2/MySQL 5.x (any MySQL)执行时间: 40 sec
在MariaDB执行时间: 2 sec
优化器控制开关
在某些情况下,可能需要覆盖选择的优化器。通常这是基准测试所需或测试目的,或者模仿行为的一个旧版本的服务器,或者如果优化器做了一个糟糕的选择。 所有上述策略可以通过以下开关控制优化器开关系统变量。
materialization=on/off
在一些非常特殊的情况下,即使物化被强制使用,优化器可能仍回归IN-TO-EXISTS策略如果物化没有使用。在这个情况下当物化要求部分匹配
(因为出现NULL值),有两个下属开关控制两部分匹配策略:
partial_match_rowid_merge=on/off
这个开关控制着Rowid-merge策略。除了这个开关,系统变量rowid_merge_buff_size控制Rowid-merge
strategy最大可用的内存
partial_match_table_scan=on/off
控制可选部分匹配策略,通过一个表扫描执行匹配。
in_to_exists=on/off
这个开关控制着IN-TO-EXISTS转换.
系统变量tmp_table_size 和 max_heap_table_size
tmp_table_size 系统变量设置内存临时表最大的限制，如果一个内部临时表超过这个规模,它自动转换成一个磁盘上B-tree
索引的ARIA或MyISAM表。然而注意, 注意然而,内存表不能大于max_heap_table_size。
优化器两个主要的开关- materialization和in_to_exists不能同时掉。如果双方都将关闭,服务器将发出一个错误。
子查询缓存的目标是优化相关子查询的估价，通过把结果和相关参数一起存储在一个缓存,避免重新执行的子查询，如果结果已经在缓存中。
管理
自从MariaDB 5 3 2 beta开始缓存是默认启用的。在早期MariaDB版本,缓存是默认关闭的。能把它打开或关闭使用优化器开关存:set optimizer_switch='subquery_cache=on';
在两个统计变量子查询缓存的效率是可见的:
subquery_cache_hit -全局计数器对于所有子查询缓存命中率统计
subquery_cache_miss -全局计数器对于所有子查询缓存未命中统计
会话变量tmp_table_size和max_heap_table_size都可以影响内存临时表的大小用于缓存。它不能超过上述变量中的最小值(了解详情见实现部分)。
可见性
你使用的缓存时在EXPLAIN EXTENDED输出是可见的(警告)是这样:
"
MariaDB [test]> explain extended select * from t1 where a in (select b from t2);
+----+----------+-------+------+------+------+---------+------+------+----+---+
| id | select_type | table | type | possible_keys |
key
+----+--------+----+-----+------+------+------+------+--+-----+---------------+
|
|
+----+--------+-------+------+---------+------+------+------+------+-------+--+
2 rows in set, 1 warning (0.00 sec)
+-------+------+--------------------------------------------------------------+
| Level | Code |
Message
+-------+------+--------------------------------------------------------------+
| Note
+-------+------+--------------------------------------------------------------+
1 row in set (0.00 sec)
在上面的示例中"
实现
每个子查询缓存创建一个临时表,结果和所有参数都存储。在所有参数，它有一个唯一索引。首先缓存是在堆表中创建的
(如果不能这样做，缓存就不会缓存这个表达式)。当cache表的大小到达到tmp_table_size和max_heap_table_size,命中率将检查:
如果命中率是很小(<0.2)缓存将被禁用
如果命中率是温和的(<0.7)cache表将被清洗(删除所有记录)保持表在内存中
如果命中率高,表将会被转化为一个磁盘表(对于5 .3. 0它只能被转换为一个磁盘表)。
hit rate = hit / (hit + miss)
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 