对应的语法：

语法的特征

  • semi-join子查询必须EXSIT和IN语句组成的布尔表达式，并且在外层查询的WHERE或者ON子句中出现。
  • 外层查询也可以有其他的搜索条件，只不过和IN子查询的搜索条件必须使用AND连接起来。
  • semi-join子查询必须是一个单一的查询，不能是由若干查询由UNION连接起来的形式。
  • semi-join子查询不能包含GROUP BY或者HAVING语句或者聚集函数。

这里以mysql8.0.13为例，讲一下semi-join的几个执行策略：

使用tmp_table, 按照join order, 选择记录qep_tab table的rowid作为唯一key进行去重，为了更好的理解，举一个例子：
SQL：

  1. SELECT Country.Name
  2. FROM Country
  3. WHERE Code IN
  4.     (SELECT CountryCode
  5.      FROM City
  6.      WHERE Population > 1M)

Duplicateweedout示意图：

处理过程：

  1. 找到duplicate weedout的qep_tab range
  1. /*找到sj的一个tab, 即第一个non-constant table*/
  2. QEP_TAB *const first_sj_tab = qep_array + first_table;
  3. /*这里由于last duplicate weedout table是outer join中的一个inner tables,
  4.   这里遍历找到last_sj_tab*/
  5. if (last_sj_tab->first_inner() != NO_PLAN_IDX &&
  6.             first_sj_tab->first_inner() != last_sj_tab->first_inner()) {
  7.    QEP_TAB *tab2 = &qep_array[last_sj_tab->first_inner()]; 
  9.    while (tab2->first_upper() != NO_PLAN_IDX &&
  10.            tab2->first_upper() != first_sj_tab->first_inner())
  11.      tab2 = qep_array + tab2->first_upper();
  12.   if (qep_array[tab2->first_inner()].last_inner() > last_sj_tab->idx())
  13.       last_sj_tab =
  14.                 &qep_array[qep_array[tab2->first_inner()].last_inner()];
  15.  }

  1. 记录需要记录rowid的qep_tab和jt_rowid_offset(duplicate_weedout_tmp_table的column长度)

    1. for (QEP_TAB *tab_in_range = qep_array + first_table;
    2.   tab_in_range <= last_sj_tab; tab_in_range++) {
    3.  if (sj_table_is_included(join, join->best_ref[tab_in_range->idx()])) {
    4.    ...
    5.    jt_rowid_offset += tab_in_range->table()->file->ref_length;
    6.    ...
    7.    tab_in_range->keep_current_rowid = true;
    8.  }
    9. }

  2. 当发现需要记录jt_rowid_offset > 0时：

    • 如果jt_rowid_offset + null_bytes为长度 > 512，就创建名为的Field_longlong做为tmp_table的hash_field来去重
    • 如果jt_rowid_offset + null_bytes为长度 <= 512，就创建名为rowids的Field_varstring作为weedout_key的tmp_table来去重
  3. 执行是在do_sj_dups_weedout函数中会将需要记录rowid的qep_tab->table的h->ref(rowid存在这里)写入tmp_table中的visible_field_ptr()[0]中，在ha_write_row的时候会根据record是否与上一条record重复来决定是否写入，外层调用会对返回值判断来查看是否是需要写入的记录，从而达到去重的目的

执行计划 start temporary 和 end temporary表示duplicateweedout的qep_tab range区间 9.png

只扫描外表同样结果的一条记录用于匹配内表，其好处就是避免单条记录匹配内表多条记录而产生的重复的记录，也是一种去重的方式，其示意图如下：

  1. 找到sj range的跳转的qep_tab和记录比较qep_tab

  2. 执行期间匹配到满足的记录就直接跳到last outer table(ot2)

    1. if(table condition satisfied) {
    2.   do join with next tables;
    3.   jump out to the jump_to;
    4.   discard row combination;
    5.   continue current table scan;
    6. }

    执行计划
    last semijoin table的qep_tab记录firstmatch标记
    4.png

inner table 基于index进行分组, 分组后与outer table join, 进行condition的匹配，如果匹配到了的记录，提取outer table的记录，inner table 选取下一个分组继续进行计算。
Query:

  1. SELECT ...
  2. FROM ot1, ...
  3. WHERE outer_expr IN
  4.     (SELECT it1.key
  5.      FROM it1,
  7.      WHERE cond(it1, it2))

处理过程

  1. 选择loosescan_parts作为内表的index
  2. 计算 loosescan parts的长度 loosescan_key_len
  3. alloc loosescan_buf挂在执行loosescan的qep_tab上
  4. 执行过程中如果发现有匹配的记录，则key_copy copy key_info到loosescan_buf上，后续用key_cmp对loosescan_buf进行比较来做分组的过滤

执行计划
与firstmatch相同在last semijoin table的qep_tab记录looseScan标记
6.png ###

将inner tables物化成temp table，通过扫描物化表或者对物化表查找的方式来避免重复record
!

处理过程

  1. setup_semijoin_materialized_table创建一个tmp table放在qep_tab的sjm_exec->table

  2. 在prepare_scan的join_materialize_semijoin(materialize钩子函数)物化semijoin nested table

    1.   /*semijoin 第一个内层物化table所在的qep_tab*/
    2.   QEP_TAB *const first = tab->join()->qep_tab + sjm->inner_table_index;
    3.   /*semijoin 最后一个内层物化table所在的qep_tab*/
    4.   QEP_TAB *const last = first + (sjm->table_count - 1);
    5.   last->next_select = end_sj_materialize;
    6.   last->set_sj_mat_exec(sjm);  // TODO: This violates comment for sj_mat_exec!
    7.   if (tab->table()->hash_field) tab->table()->file->ha_index_init(0, 0);
    8.   int rc;
    9.   /*物化过程*/
    10.   if ((rc = sub_select(tab->join(), first, false)) < 0) DBUG_RETURN(rc);
    11.   if ((rc = sub_select(tab->join(), first, true)) < 0) DBUG_RETURN(rc);
    12.   if (tab->table()->hash_field) tab->table()->file->ha_index_or_rnd_end();

Materialization-scan与Materialization-lookup的区别：

  • Materialization-Scan:

    1. temporary table–> outer tabl

  • Materialization-lookup

执行计划
MATERIALIZED代表使用了物化策略
8.png

  • optimizer_switch

    optimizer_switch 可以对semi-join使用的策略进行，其配置参数有：
    semijoin : on/off 

    1. materialization : on/off

    firstmatch : on/off
    loosescan : on/off
    duplicateweedout : on/off

  • Optimizer Hints

    Optimizer Hints 可以支持在SQL中hint方式指定semi-join使用的策略, 如：
    指定TPCH Q20 使用duplicateweedout策略:

    1. SELECT /*+ JOIN_PREFIX(nation) */ s_name,
    2.                                 s_address
    3. FROM supplier,
    4.    nation
    5. WHERE s_suppkey IN
    6.   (SELECT /*+ SEMIJOIN(DUPSWEEDOUT) */ ps_suppkey
    7.    FROM partsupp
    8.    WHERE ps_partkey IN
    9.        (SELECT p_partkey
    10.         FROM part
    11.         WHERE p_name LIKE 'peru%' )
    12.      AND ps_availqty >
    13.        (SELECT 0.5 * sum(l_quantity)
    14.         FROM lineitem
    15.         WHERE l_partkey = ps_partkey
    16.           AND l_suppkey = ps_suppkey
    17.           AND l_shipdate >= '1993-01-01'
    18.           AND l_shipdate < date_add('1993-01-01' ,interval '1' YEAR) ) )
    19. AND n_name = 'PERU'
    20. ORDER BY s_name;

对于选择semi-join策略的查询，PolarDB产品对semi-join所有策略实现了并行加速，根据代价评估，通过拆分semi-join的任务，多线程模型并行运行任务集，加速去重，使查询性能得到了显著的提升，以Q20为例

  1. select
  2. s_name,
  3. s_address
  4. from
  5. supplier, nation
  6. where
  8. select
  9. ps_suppkey
  10. from
  11. partsupp
  12. where
  13. ps_partkey in (
  14. select
  15. p_partkey
  16. from
  17. part
  18. where
  19. p_name like '[COLOR]%'
  20. )
  21. and ps_availqty > (
  22. select
  23. 0.5 * sum(l_quantity)
  24. from
  25. lineitem
  26. where
  27. l_partkey = ps_partkey
  28. and l_suppkey = ps_suppkey
  29. and l_shipdate >= date('[DATE]’)
  30. and l_shipdate < date('[DATE]’) + interval ‘1’ year
  31. )
  32. )
  33. and s_nationkey = n_nationkey
  34. and n_name = '[NATION]'
  35. order by
  36. s_name;
  1. mysql> SELECT c1,d1 FROM t1 WHERE c1 IN ( SELECT t2.c1 FROM t2 WHERE t2.c1 = 'f'      OR t2.c2 < 'y' ) and t1.c1 and d1 > '1900-1-1' like "R1%" ORDER BY t1.c1 DESC, t1.d1 DESC;
  2. Empty set, 1024 warnings (0.34 sec)
  3. mysql> set max_parallel_degree=0;
  4. Query OK, 0 rows affected (0.00 sec)
  5. mysql>  SELECT c1,d1 FROM t1 WHERE c1 IN ( SELECT t2.c1 FROM t2 WHERE t2.c1 = 'f'      OR t2.c2 < 'y' ) and t1.c1 and d1 > '1900-1-1' like "R1%" ORDER BY t1.c1 DESC, t1.d1 DESC;
  6. Empty set, 65535 warnings (2.69 sec)
  7. mysql> explain SELECT c1,d1 FROM t1 WHERE c1 IN ( SELECT t2.c1 FROM t2 WHERE t2.c1 = 'f'      OR t2.c2 < 'y' ) and t1.c1 and d1 > '1900-1-1' like "R1%" ORDER BY t1.c1 DESC, t1.d1 DESC;
  8. +----+--------------+-------------+------------+--------+---------------+------------+---------+----------+--------+----------+---------------------------------------------------------+
  9. | id | select_type  | table       | partitions | type   | possible_keys | key        | key_len | ref      | rows   | filtered | Extra                                                   |
  10. +----+--------------+-------------+------------+--------+---------------+------------+---------+----------+--------+----------+---------------------------------------------------------+
  11. |  1 | SIMPLE       | <gather1>   | NULL       | ALL    | NULL          | NULL       | NULL    | NULL     |  33464 |   100.00 | Merge sort                                              |
  12. |  1 | SIMPLE       | t1          | NULL       | ALL    | NULL          | NULL       | NULL    | NULL     |  62802 |    30.00 | Parallel scan (32 workers); Using where; Using filesort |
  13. |  1 | SIMPLE       | <subquery2> | NULL       | eq_ref | <auto_key>    | <auto_key> | 103     | sj.t1.c1 |      1 |   100.00 | NULL                                                    |
  15. +----+--------------+-------------+------------+--------+---------------+------------+------