[MDEV-36169] If strategies in hint SEMIJOIN are named but inapplicable for the statement, DUPSWEEDOUT shoud be used, but is does not work for engines Aria and InnoDB - Jira

Details

Type: Bug
Status: Closed (View Workflow)
Priority: Critical
Resolution: Fixed
Affects Version/s: 12.0
Fix Version/s: 12.0.1
Component/s: Optimizer
Labels:
None

Description

colored textFrom MDEV-34888: For SEMIJOIN hints, if no strategies are named, semijoin is used if possible based on the strategies enabled according to the optimizer_switch system variable. If strategies are named but inapplicable for the statement, DUPSWEEDOUT is used.

Testcase:

CREATE TABLE t1 (a INTEGER NOT NULL, b INT, PRIMARY KEY (a));

CREATE TABLE t2 (a INTEGER NOT NULL, KEY (a));

CREATE TABLE t3 (a INTEGER NOT NULL, b INT, KEY (a));

INSERT INTO t1 VALUES (1,10), (2,20), (3,30), (4,40);

INSERT INTO t2 VALUES (2), (2), (3), (3), (4), (5);

INSERT INTO t3 VALUES (10,3), (15,3), (20,4), (30,5);

EXPLAIN EXTENDED

SELECT /*+ SEMIJOIN(@subq1 LOOSESCAN) SEMIJOIN(@subq2 LOOSESCAN) */ * FROM t1

WHERE t1.a IN (SELECT /*+ QB_NAME(subq1) */ a FROM t3)

  AND t1.b IN (SELECT /*+ QB_NAME(subq2) */ a FROM t2);

DROP TABLE t1,t2,t3;

This query assumes that LooseScan is not possible for both subqueries at the same time, so in the second case it should be replaced with DuplicateWeedout.

For engine=MyISAM everything looks good:

EXPLAIN EXTENDED

SELECT /*+ SEMIJOIN(@subq1 LOOSESCAN) SEMIJOIN(@subq2 LOOSESCAN) */ * FROM t1

WHERE t1.a IN (SELECT /*+ QB_NAME(subq1) */ a FROM t3)

AND t1.b IN (SELECT /*+ QB_NAME(subq2) */ a FROM t2);

id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra

1	PRIMARY	t3	index	a	a	4	NULL	4	100.00	Using index; LooseScan

1	PRIMARY	t1	eq_ref	PRIMARY	PRIMARY	4	test.t3.a	1	25.00	Using where

1	PRIMARY	t2	ref	a	a	4	test.t1.b	1	66.67	Using index; Start temporary; End temporary

Warnings:

Note	1003	select /*+ SEMIJOIN(@`subq1` LOOSESCAN) SEMIJOIN(@`subq2` LOOSESCAN) */ `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from `test`.`t1` semi join (`test`.`t3`) semi join (`test`.`t2`) where `test`.`t1`.`a` = `test`.`t3`.`a` and `test`.`t2`.`a` = `test`.`t1`.`b`

But for engine=InnoDB (Aria) DuplicateWeedout is not used:

XPLAIN EXTENDED

SELECT /*+ SEMIJOIN(@subq1 LOOSESCAN) SEMIJOIN(@subq2 LOOSESCAN) */ * FROM t1

WHERE t1.a IN (SELECT /*+ QB_NAME(subq1) */ a FROM t3)

AND t1.b IN (SELECT /*+ QB_NAME(subq2) */ a FROM t2);

id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra

1	PRIMARY	t2	index	a	a	4	NULL	6	100.00	Using index

1	PRIMARY	t3	index	a	a	4	NULL	4	100.00	Using index; LooseScan

1	PRIMARY	t1	eq_ref	PRIMARY	PRIMARY	4	test.t3.a	1	25.00	Using where

Warnings:

Note	1003	select /*+ SEMIJOIN(@`subq1` LOOSESCAN) SEMIJOIN(@`subq2` LOOSESCAN) */ `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from `test`.`t1` semi join (`test`.`t3`) semi join (`test`.`t2`) where `test`.`t1`.`a` = `test`.`t3`.`a` and `test`.`t1`.`b` = `test`.`t2`.`a`

But if we use the DuplicateWeedout strategy in both cases, we can see that its use is acceptable:

EXPLAIN EXTENDED

SELECT /*+ SEMIJOIN(@subq1 DUPSWEEDOUT) SEMIJOIN(@subq2 DUPSWEEDOUT) */ * FROM t1

WHERE t1.a IN (SELECT /*+ QB_NAME(subq1) */ a FROM t3)

AND t1.b IN (SELECT /*+ QB_NAME(subq2) */ a FROM t2);

id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra

1	PRIMARY	t3	index	a	a	4	NULL	4	100.00	Using index; Start temporary

1	PRIMARY	t1	eq_ref	PRIMARY	PRIMARY	4	test.t3.a	1	25.00	Using where; End temporary

1	PRIMARY	t2	ref	a	a	4	test.t1.b	1	66.67	Using index; Start temporary; End temporary

Warnings:

Note	1003	select /*+ SEMIJOIN(@`subq1` DUPSWEEDOUT) SEMIJOIN(@`subq2` DUPSWEEDOUT) */ `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from `test`.`t1` semi join (`test`.`t3`) semi join (`test`.`t2`) where `test`.`t1`.`a` = `test`.`t3`.`a` and `test`.`t2`.`a` = `test`.`t1`.`b`

Attachments

Issue Links

blocks

MDEV-34888 Implement subquery optimizer hints

Stalled

MDEV-35504 MySQL 8-style optimizer hints: milestone 1

Stalled

is caused by

MDEV-34888 Implement subquery optimizer hints

Stalled

split to

MDEV-36707 Semi-joins can introduce incorrect cardinality

Open

Activity

Ascending order - Click to sort in descending order

Oleg Smirnov added a comment - 2025-04-03 05:53 - edited

A bit simplified notation (no change to the logic):

EXPLAIN EXTENDED

SELECT  * FROM t1

  WHERE t1.a IN (SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t3)

  AND t1.b IN (SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t2);

The behaviour appears to be dependent on the uniqueness of KEY(a) of `t1`. If the key is not unique:

CREATE TABLE t1 (a INTEGER NOT NULL, b INT, KEY (a)) engine=InnoDB;

then we get

EXPLAIN EXTENDED

SELECT  * FROM t1

WHERE t1.a IN (SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t3)

AND t1.b IN (SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t2);

id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra

1	PRIMARY	t3	index	a	a	4	NULL	4	100.00	Using index; LooseScan

1	PRIMARY	t1	ref	a	a	4	test.t3.a	1	25.00	Using where

1	PRIMARY	t2	ref	a	a	4	test.t1.b	1	100.00	Using index; Start temporary; End temporary

LooseScan/DupsWeedout, which is expected.

However, if the key is unique

CREATE TABLE t1 (a INTEGER NOT NULL, b INT, UNIQUE KEY (a)) engine=InnoDB;

then the EXPLAIN output

EXPLAIN EXTENDED

SELECT  * FROM t1

WHERE t1.a IN (SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t3)

AND t1.b IN (SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t2);

id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra

1	PRIMARY	t2	index	a	a	4	NULL	6	100.00	Using index

1	PRIMARY	t3	index	a	a	4	NULL	4	100.00	Using index; LooseScan

1	PRIMARY	t1	eq_ref	a	a	4	test.t3.a	1	25.00	Using where

Warnings:

Note	1003	select /*+ SEMIJOIN(@`select#2` LOOSESCAN) SEMIJOIN(@`select#3` LOOSESCAN) */ `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from `test`.`t1` semi join (`test`.`t3`) semi join (`test`.`t2`) where `test`.`t1`.`a` = `test`.`t3`.`a` and `test`.`t1`.`b` = `test`.`t2`.`a`

looks like a case of table pullout of the table `t2`. However, table pullout does not seem applicable here since values of `t2.a` are not unique.

Oleg Smirnov added a comment - 2025-04-03 05:53 - edited A bit simplified notation (no change to the logic): EXPLAIN EXTENDED SELECT * FROM t1 WHERE t1.a IN ( SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t3) AND t1.b IN ( SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t2); The behaviour appears to be dependent on the uniqueness of KEY(a) of `t1`. If the key is not unique: CREATE TABLE t1 (a INTEGER NOT NULL , b INT , KEY (a)) engine=InnoDB; then we get EXPLAIN EXTENDED SELECT * FROM t1 WHERE t1.a IN ( SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t3) AND t1.b IN ( SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t2); id select_type table type possible_keys key key_len ref rows filtered Extra 1 PRIMARY t3 index a a 4 NULL 4 100.00 Using index ; LooseScan 1 PRIMARY t1 ref a a 4 test.t3.a 1 25.00 Using where 1 PRIMARY t2 ref a a 4 test.t1.b 1 100.00 Using index ; Start temporary ; End temporary LooseScan/DupsWeedout, which is expected. However, if the key is unique CREATE TABLE t1 (a INTEGER NOT NULL , b INT , UNIQUE KEY (a)) engine=InnoDB; then the EXPLAIN output EXPLAIN EXTENDED SELECT * FROM t1 WHERE t1.a IN ( SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t3) AND t1.b IN ( SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t2); id select_type table type possible_keys key key_len ref rows filtered Extra 1 PRIMARY t2 index a a 4 NULL 6 100.00 Using index 1 PRIMARY t3 index a a 4 NULL 4 100.00 Using index ; LooseScan 1 PRIMARY t1 eq_ref a a 4 test.t3.a 1 25.00 Using where Warnings: Note 1003 select /*+ SEMIJOIN(@`select#2` LOOSESCAN) SEMIJOIN(@`select#3` LOOSESCAN) */ `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from `test`.`t1` semi join (`test`.`t3`) semi join (`test`.`t2`) where `test`.`t1`.`a` = `test`.`t3`.`a` and `test`.`t1`.`b` = `test`.`t2`.`a` looks like a case of table pullout of the table `t2`. However, table pullout does not seem applicable here since values of `t2.a` are not unique.

Oleg Smirnov added a comment - 2025-04-07 07:03

Another observation: adding one more record to `t3` changes the join order and makes both hints work as expected:

...

INSERT INTO t3 VALUES (10,3), (11,4), (15,3), (20,4), (30,5);

...

EXPLAIN EXTENDED

SELECT  * FROM t1

WHERE t1.a IN (SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t2)

AND t1.b IN (SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t3);

id      select_type     table   type    possible_keys   key     key_len ref     rows    filtered        Extra

1       PRIMARY t2      index   a       a       4       NULL    6       100.00  Using index; LooseScan

1       PRIMARY t1      eq_ref  a       a       4       test.t2.a       1       16.67   Using where

1       PRIMARY t3      ref     a       a       4       test.t1.b       1       100.00  Using index; Start temporary; End temporary

Warnings:

Note    1003    select /*+ SEMIJOIN(@`select#2` LOOSESCAN) SEMIJOIN(@`select#3` LOOSESCAN) */ `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from `test`.`t1` semi join (`test`.`t2`) semi join (`test`.`t3`) where `test`.`t1`.`a` = `test`.`t2`.`a` and `test`.`t3`.`a` = `test`.`t1`.`b`

Full test case:

--source include/have_innodb.inc

CREATE TABLE t1 (a INTEGER NOT NULL, b INT, UNIQUE KEY (a)) engine=InnoDB;

CREATE TABLE t2 (a INTEGER NOT NULL, KEY (a));

CREATE TABLE t3 (a INTEGER NOT NULL, b INT, KEY (a));

INSERT INTO t1 VALUES (1,10), (2,20), (3,30), (4,40);

INSERT INTO t2 VALUES (2), (2), (3), (3), (4), (5);

INSERT INTO t3 VALUES (10,3), (11,4), (15,3), (20,4), (30,5);

EXPLAIN EXTENDED

SELECT  * FROM t1

  WHERE t1.a IN (SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t2)

  AND t1.b IN (SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t3);

DROP TABLE t1,t2,t3;

Oleg Smirnov added a comment - 2025-04-07 07:03 Another observation: adding one more record to `t3` changes the join order and makes both hints work as expected: ... INSERT INTO t3 VALUES (10,3), (11,4), (15,3), (20,4), (30,5); ... EXPLAIN EXTENDED SELECT * FROM t1 WHERE t1.a IN ( SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t2) AND t1.b IN ( SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t3); id select_type table type possible_keys key key_len ref rows filtered Extra 1 PRIMARY t2 index a a 4 NULL 6 100.00 Using index ; LooseScan 1 PRIMARY t1 eq_ref a a 4 test.t2.a 1 16.67 Using where 1 PRIMARY t3 ref a a 4 test.t1.b 1 100.00 Using index ; Start temporary ; End temporary Warnings: Note 1003 select /*+ SEMIJOIN(@`select#2` LOOSESCAN) SEMIJOIN(@`select#3` LOOSESCAN) */ `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b` from `test`.`t1` semi join (`test`.`t2`) semi join (`test`.`t3`) where `test`.`t1`.`a` = `test`.`t2`.`a` and `test`.`t3`.`a` = `test`.`t1`.`b` Full test case: --source include/have_innodb.inc CREATE TABLE t1 (a INTEGER NOT NULL , b INT , UNIQUE KEY (a)) engine=InnoDB; CREATE TABLE t2 (a INTEGER NOT NULL , KEY (a)); CREATE TABLE t3 (a INTEGER NOT NULL , b INT , KEY (a)); INSERT INTO t1 VALUES (1,10), (2,20), (3,30), (4,40); INSERT INTO t2 VALUES (2), (2), (3), (3), (4), (5); INSERT INTO t3 VALUES (10,3), (11,4), (15,3), (20,4), (30,5); EXPLAIN EXTENDED SELECT * FROM t1 WHERE t1.a IN ( SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t2) AND t1.b IN ( SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t3); DROP TABLE t1,t2,t3;

Sergei Petrunia added a comment - 2025-04-07 17:08

Ok I'm debugging this testcase:

CREATE TABLE t1 (a INTEGER NOT NULL, b INT, UNIQUE KEY (a)) engine=InnoDB;

CREATE TABLE t2 (a INTEGER NOT NULL, KEY (a));

CREATE TABLE t3 (a INTEGER NOT NULL, b INT, KEY (a));

INSERT INTO t1 VALUES (1,10), (2,20), (3,30), (4,40);

INSERT INTO t2 VALUES (2), (2), (3), (3), (4), (5);

INSERT INTO t3 VALUES (10,3), (15,3), (20,4), (30,5);

set optimizer_trace=1;

 EXPLAIN EXTENDED  SELECT  * FROM t1 WHERE t1.a IN (SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t2) AND t1.b IN (SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t3);

The EXPLAIN output is

+------+-------------+-------+--------+---------------+------+---------+-----------+------+----------+------------------------+

| id   | select_type | table | type   | possible_keys | key  | key_len | ref       | rows | filtered | Extra                  |

+------+-------------+-------+--------+---------------+------+---------+-----------+------+----------+------------------------+

|    1 | PRIMARY     | t3    | index  | a             | a    | 4       | NULL      | 4    |   100.00 | Using index            |

|    1 | PRIMARY     | t2    | index  | a             | a    | 4       | NULL      | 7    |   100.00 | Using index; LooseScan |

|    1 | PRIMARY     | t1    | eq_ref | a             | a    | 4       | test.t2.a | 1    |    14.29 | Using where            |

+------+-------------+-------+--------+---------------+------+---------+-----------+------+----------+------------------------+

This query plan is invalid, because it has no provisions to remove duplicates generated by table t3.

Looking at optimize_semi_joins() call that is made after we've built the prefix of:
t3, t2

We have
dups_producing_tables=6

Then:

  LooseScan_picker::set_from_prev():

    first_loose_scan_table = 0  // t3

    loosescan_need_tables= 5  // {t3,t1}

ok so far.
Then at start of LooseScan_picker::check_qep() there is this piece

/*

      LooseScan strategy can't handle interleaving between tables from the

      semi-join that LooseScan is handling and any other tables.

      If we were considering LooseScan for the join prefix (1)

         and the table we're adding creates an interleaving (2)

      then

         stop considering loose scan

*/

    if ((first_loosescan_table != MAX_TABLES) &&   // (1)

        (first->table->emb_sj_nest->sj_inner_tables & remaining_tables) && //(2)

        new_join_tab->emb_sj_nest != first->table->emb_sj_nest) //(2)

      first_loosescan_table= MAX_TABLES;

which seems like it could prevent construction of join orders like

{t3,t2,t1}

, but it doesn't

Looking at the condition:

(1):  first_loosescan_table=0 , so (1)->TRUE.

(2): first->table->emb_sj_nest->sj_inner_tables = 4 // this is t3.  'first' also points to t3.

    remaining_tables=1 // t1.

   so (2)-> FALSE.

(3):  (new_join_tab->emb_sj_nest != first->table->emb_sj_nest)  evaluates to TRUE.

It seems there's a problem with line (2).

Sergei Petrunia added a comment - 2025-04-07 17:08 Ok I'm debugging this testcase: CREATE TABLE t1 (a INTEGER NOT NULL , b INT , UNIQUE KEY (a)) engine=InnoDB; CREATE TABLE t2 (a INTEGER NOT NULL , KEY (a)); CREATE TABLE t3 (a INTEGER NOT NULL , b INT , KEY (a)); INSERT INTO t1 VALUES (1,10), (2,20), (3,30), (4,40); INSERT INTO t2 VALUES (2), (2), (3), (3), (4), (5); INSERT INTO t3 VALUES (10,3), (15,3), (20,4), (30,5); set optimizer_trace=1; EXPLAIN EXTENDED SELECT * FROM t1 WHERE t1.a IN ( SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t2) AND t1.b IN ( SELECT /*+ SEMIJOIN(LOOSESCAN) */ a FROM t3); The EXPLAIN output is +------+-------------+-------+--------+---------------+------+---------+-----------+------+----------+------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +------+-------------+-------+--------+---------------+------+---------+-----------+------+----------+------------------------+ | 1 | PRIMARY | t3 | index | a | a | 4 | NULL | 4 | 100.00 | Using index | | 1 | PRIMARY | t2 | index | a | a | 4 | NULL | 7 | 100.00 | Using index; LooseScan | | 1 | PRIMARY | t1 | eq_ref | a | a | 4 | test.t2.a | 1 | 14.29 | Using where | +------+-------------+-------+--------+---------------+------+---------+-----------+------+----------+------------------------+ This query plan is invalid, because it has no provisions to remove duplicates generated by table t3. Looking at optimize_semi_joins() call that is made after we've built the prefix of: t3, t2 We have dups_producing_tables=6 Then: LooseScan_picker::set_from_prev(): first_loose_scan_table = 0 // t3 loosescan_need_tables= 5 // {t3,t1} ok so far. Then at start of LooseScan_picker::check_qep() there is this piece /* LooseScan strategy can't handle interleaving between tables from the semi-join that LooseScan is handling and any other tables. If we were considering LooseScan for the join prefix (1) and the table we're adding creates an interleaving (2) then stop considering loose scan */ if ((first_loosescan_table != MAX_TABLES) && // (1) (first->table->emb_sj_nest->sj_inner_tables & remaining_tables) && //(2) new_join_tab->emb_sj_nest != first->table->emb_sj_nest) //(2) { first_loosescan_table= MAX_TABLES; } which seems like it could prevent construction of join orders like {t3,t2,t1} , but it doesn't Looking at the condition: (1): first_loosescan_table=0 , so (1)->TRUE. (2): first->table->emb_sj_nest->sj_inner_tables = 4 // this is t3. 'first' also points to t3. remaining_tables=1 // t1. so (2)-> FALSE. (3): (new_join_tab->emb_sj_nest != first->table->emb_sj_nest) evaluates to TRUE. It seems there's a problem with line (2).

Sergei Petrunia added a comment - 2025-04-07 18:06

bb-11.8-MDEV-34870-join-order-fix-semijoin .

Sergei Petrunia added a comment - 2025-04-07 18:06 bb-11.8- MDEV-34870 -join-order-fix-semijoin .

Oleg Smirnov added a comment - 2025-04-12 15:31

This fix has changed the result of one of `opt_hints_join_order.test` cases:

CREATE TABLE t1(f1 INT(11) NOT NULL);

INSERT INTO t1 VALUES (10);

CREATE TABLE t2

  f1 INT(11) NOT NULL AUTO_INCREMENT,

  f2 INT(11) DEFAULT NULL,

  PRIMARY KEY (f1),

  KEY (f2)

);

INSERT INTO t2 VALUES (1, 7), (2, 1), (4, 7);

CREATE TABLE t4(f1 INT DEFAULT NULL);

INSERT INTO t4 VALUES (2);

EXPLAIN EXTENDED

SELECT /*+ JOIN_PREFIX(t2@qb2, t4@qb1, ta3, ta4) */ COUNT(*) FROM t1 JOIN t2 AS ta3 JOIN t2 AS ta4

  WHERE ta4.f1 IN (SELECT /*+ QB_NAME(qb1) */ f1 FROM t4) AND

        ta3.f2 IN (SELECT /*+ QB_NAME(qb2) */ f2 FROM t2);

DROP TABLE t1, t2, t4;

The previous result was

id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra

1	PRIMARY	t2	index	f2	f2	5	NULL	3	100.00	Using where; Using index; Start temporary

1	PRIMARY	t4	ALL	NULL	NULL	NULL	NULL	1	100.00	Using where; Using join buffer (flat, BNL join)

1	PRIMARY	ta3	ref	f2	f2	5	test.t2.f2	1	33.33	Using index

1	PRIMARY	ta4	eq_ref	PRIMARY	PRIMARY	4	test.t4.f1	1	33.33	End temporary

1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	1	100.00	Using join buffer (flat, BNL join)

Warnings:

Note	1003	select /*+ JOIN_PREFIX(@`select#1` `t2`@`qb2`,`t4`@`qb1`,`ta3`,`ta4`) */ count(0) AS `COUNT(*)` from `test`.`t1` semi join (`test`.`t4`) semi join (`test`.`t2`) join `test`.`t2` `ta3` join `test`.`t2` `ta4` where `test`.`ta4`.`f1` = `test`.`t4`.`f1` and `test`.`ta3`.`f2` = `test`.`t2`.`f2`

Notice `filtered`= 33.33 for the table `ta3`. The patched version displays `filtered`=100.00 for the same table:

...

1	PRIMARY	ta3	ref	f2	f2	5	test.t2.f2	1	100.00	Using index

...

The unpatched version has the following section in the optimizer trace:

    "plan_prefix": "t2,t4",

    "table": "ta3",

    "rows_for_plan": 4.5,

    "cost_for_plan": 0.022352386,

    "semijoin_strategy_choice": [

        "strategy": "LooseScan",

        "rows": 1.5,

        "cost": 0.03709339

},

        "chosen_strategy": "LooseScan"

],

    "sj_rows_out": 0.5,

    "sj_rows_for_plan": 1.5,

    "sj_filtered": 33.33333333,

...

So, it applies LooseScan semijoin strategy for joining `ta3`, calculates `sj_filtered`=33.33 and stores 0.5 to `POSITION::records_out` while `POSITION::records_init` == 1.5. However, the next table `ta4` is joined using DuplicateWeedout strategy spanning over four tables from `t2` to `ta4` and covering `ta3`. This isn't a valid combination of semijoins, and this is handled later at `fix_semijoin_strategies_for_picked_join_order()`:

    uint i_end= first + join->best_positions[first].n_sj_tables;

    for (uint i= first; i < i_end; i++)

      if (i != first)

        join->best_positions[i].sj_strategy= SJ_OPT_NONE;

      handled_tabs |= join->best_positions[i].table->table->map;

Here the LooseScan strategy is discarded, however `POSITION::records_out` remains equal to 0.5 as is was set by LooseScan strategy. Then this value is copied to `JOIN_TAB::records_out` and displayed in the EXPLAIN output as the ratio 0.5 / 1.5 (33.33%).

The patched version doesn't apply LooseScan to `ta3`, so `POSITION::records_out` == 1.5 and `filtered` equals 100%, which is correct and corresponds to the output of ANALYZE.

This scenario raises a number of questions.
1. Is such a scenario only possible for a combination of covering DuplicateWeedout/nested LooseScan or for other strategies too?
2. Is it legitimate to apply any nested semijoin strategies during join order enumeration if there is already another semijoin strategy covering the current table?
3. If it is legitimate, should we restore `POSITION::records_out` at `fix_semijoin_strategies_for_picked_join_order()` to the initial value (before semijoin) when the semijoin strategy is discarded? This will at least provide more accurate output of EXPLAIN.
4. Even if the EXPLAIN output will be accurate, `partial_join_cardinality` will not, and this may negatively affect optimizer choices. In our scenario, partial join "t2,t4,ta3" was expected to filter 33.33% of records while in fact `filtered` should be 100.00%.

Oleg Smirnov added a comment - 2025-04-12 15:31 This fix has changed the result of one of `opt_hints_join_order.test` cases: CREATE TABLE t1(f1 INT (11) NOT NULL ); INSERT INTO t1 VALUES (10); CREATE TABLE t2 ( f1 INT (11) NOT NULL AUTO_INCREMENT, f2 INT (11) DEFAULT NULL , PRIMARY KEY (f1), KEY (f2) ); INSERT INTO t2 VALUES (1, 7), (2, 1), (4, 7); CREATE TABLE t4(f1 INT DEFAULT NULL ); INSERT INTO t4 VALUES (2); EXPLAIN EXTENDED SELECT /*+ JOIN_PREFIX(t2@qb2, t4@qb1, ta3, ta4) */ COUNT (*) FROM t1 JOIN t2 AS ta3 JOIN t2 AS ta4 WHERE ta4.f1 IN ( SELECT /*+ QB_NAME(qb1) */ f1 FROM t4) AND ta3.f2 IN ( SELECT /*+ QB_NAME(qb2) */ f2 FROM t2); DROP TABLE t1, t2, t4; The previous result was id select_type table type possible_keys key key_len ref rows filtered Extra 1 PRIMARY t2 index f2 f2 5 NULL 3 100.00 Using where ; Using index ; Start temporary 1 PRIMARY t4 ALL NULL NULL NULL NULL 1 100.00 Using where ; Using join buffer (flat, BNL join ) 1 PRIMARY ta3 ref f2 f2 5 test.t2.f2 1 33.33 Using index 1 PRIMARY ta4 eq_ref PRIMARY PRIMARY 4 test.t4.f1 1 33.33 End temporary 1 PRIMARY t1 ALL NULL NULL NULL NULL 1 100.00 Using join buffer (flat, BNL join ) Warnings: Note 1003 select /*+ JOIN_PREFIX(@`select#1` `t2`@`qb2`,`t4`@`qb1`,`ta3`,`ta4`) */ count (0) AS ` COUNT (*)` from `test`.`t1` semi join (`test`.`t4`) semi join (`test`.`t2`) join `test`.`t2` `ta3` join `test`.`t2` `ta4` where `test`.`ta4`.`f1` = `test`.`t4`.`f1` and `test`.`ta3`.`f2` = `test`.`t2`.`f2` Notice `filtered`= 33.33 for the table `ta3`. The patched version displays `filtered`=100.00 for the same table: ... 1 PRIMARY ta3 ref f2 f2 5 test.t2.f2 1 100.00 Using index ... The unpatched version has the following section in the optimizer trace: { "plan_prefix": "t2,t4", "table": "ta3", "rows_for_plan": 4.5, "cost_for_plan": 0.022352386, "semijoin_strategy_choice": [ { "strategy": "LooseScan", "rows": 1.5, "cost": 0.03709339 }, { "chosen_strategy": "LooseScan" } ], "sj_rows_out": 0.5, "sj_rows_for_plan": 1.5, "sj_filtered": 33.33333333, ... So, it applies LooseScan semijoin strategy for joining `ta3`, calculates `sj_filtered`=33.33 and stores 0.5 to `POSITION::records_out` while `POSITION::records_init` == 1.5. However, the next table `ta4` is joined using DuplicateWeedout strategy spanning over four tables from `t2` to `ta4` and covering `ta3`. This isn't a valid combination of semijoins, and this is handled later at `fix_semijoin_strategies_for_picked_join_order()`: uint i_end= first + join->best_positions[first].n_sj_tables; for (uint i= first; i < i_end; i++) { if (i != first) join->best_positions[i].sj_strategy= SJ_OPT_NONE; handled_tabs |= join->best_positions[i].table->table->map; } Here the LooseScan strategy is discarded, however `POSITION::records_out` remains equal to 0.5 as is was set by LooseScan strategy. Then this value is copied to `JOIN_TAB::records_out` and displayed in the EXPLAIN output as the ratio 0.5 / 1.5 (33.33%). The patched version doesn't apply LooseScan to `ta3`, so `POSITION::records_out` == 1.5 and `filtered` equals 100%, which is correct and corresponds to the output of ANALYZE. This scenario raises a number of questions. 1. Is such a scenario only possible for a combination of covering DuplicateWeedout/nested LooseScan or for other strategies too? 2. Is it legitimate to apply any nested semijoin strategies during join order enumeration if there is already another semijoin strategy covering the current table? 3. If it is legitimate, should we restore `POSITION::records_out` at `fix_semijoin_strategies_for_picked_join_order()` to the initial value (before semijoin) when the semijoin strategy is discarded? This will at least provide more accurate output of EXPLAIN. 4. Even if the EXPLAIN output will be accurate, `partial_join_cardinality` will not, and this may negatively affect optimizer choices. In our scenario, partial join "t2,t4,ta3" was expected to filter 33.33% of records while in fact `filtered` should be 100.00%.

Sergei Petrunia added a comment - 2025-04-21 13:35 - edited

Thanks, good analysis!

1. Is such a scenario only possible for a combination of covering DuplicateWeedout/nested LooseScan or for other strategies too?

Generally speaking, this can apply for other strategies too.
When we're building a join prefix, we can decide to apply strategy X, then add a more tables and decide to apply another strategy Y . This will "cancel out" all strategies that attempted to remove duplicates that Y "handles".

2. Is it legitimate to apply any nested semijoin strategies during join order enumeration if there is already another semijoin strategy covering the current table?

That was the way it was implemented. New strategy overrides the previous choice. (I'm not sure if that's the best design. But this was explicitly intended).

3. If it is legitimate, should we restore `POSITION::records_out` at `fix_semijoin_strategies_for_picked_join_order()` to the initial value (before semijoin) when the semijoin strategy is discarded? This will at least provide more accurate output of EXPLAIN.

This would provide "fixed" EXPLAIN output. But it would not fix the fact that join optimization has used incorrect values of partial join cardinalities...

One can say that the "final" records_out after the semi-join duplicates are removed should be the same regardless of which strategy was used... Although I am not sure if the formulas in our code have this property...

Sergei Petrunia added a comment - 2025-04-21 13:35 - edited Thanks, good analysis! 1. Is such a scenario only possible for a combination of covering DuplicateWeedout/nested LooseScan or for other strategies too? Generally speaking, this can apply for other strategies too. When we're building a join prefix, we can decide to apply strategy X, then add a more tables and decide to apply another strategy Y . This will "cancel out" all strategies that attempted to remove duplicates that Y "handles". 2. Is it legitimate to apply any nested semijoin strategies during join order enumeration if there is already another semijoin strategy covering the current table? That was the way it was implemented. New strategy overrides the previous choice. (I'm not sure if that's the best design. But this was explicitly intended). 3. If it is legitimate, should we restore `POSITION::records_out` at `fix_semijoin_strategies_for_picked_join_order()` to the initial value (before semijoin) when the semijoin strategy is discarded? This will at least provide more accurate output of EXPLAIN. This would provide "fixed" EXPLAIN output. But it would not fix the fact that join optimization has used incorrect values of partial join cardinalities... One can say that the "final" records_out after the semi-join duplicates are removed should be the same regardless of which strategy was used... Although I am not sure if the formulas in our code have this property...

Oleg Smirnov added a comment - 5 days ago

This fix is pushed to feature branch bb-11.8-MDEV-34870-join-order.
Discussions about semi-join cardinalities are moved to MDEV-36707.

Oleg Smirnov added a comment - 5 days ago This fix is pushed to feature branch bb-11.8- MDEV-34870 -join-order. Discussions about semi-join cardinalities are moved to MDEV-36707 .

People

Assignee:: Sergei Petrunia

Reporter:: Lena Startseva

Votes:: 0 Vote for this issue

Watchers:: 3 Start watching this issue

Dates

Created:: 2025-02-25 18:00

Updated:: 6 days ago 09:46

Resolved:: 6 days ago 09:15

Git Integration

Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.

MariaDB Server