Join optimizer pruning seems to work poorly for semi-joins

[Sergey Petrunia]

Join optimizer pruning seems to be too aggressive in pruning query plans with semi-joins. Quick investigation in debugger hints at that it is not comparing apples-to-apples when comparing record counts.

As a result, one can observe effects like this:

create table ten (a int);
insert into ten values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);

create table one_k (a int);
insert into one_k select A.a + 10*B.a + 100*C.a from ten A, ten B, ten C;

MariaDB [test]> set optimizer_prune_level=0;
Query OK, 0 rows affected (0.00 sec)

MariaDB [test]> explain select * from one_k A where a in (select B.a from ten B, ten C where C.a < A.a);
+----+-------------+-------+------+---------------+------+---------+------+------+----------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------------------+
| 1 | PRIMARY | A | ALL | NULL | NULL | NULL | NULL | 1000 | |
| 1 | PRIMARY | C | ALL | NULL | NULL | NULL | NULL | 10 | Using where |
| 1 | PRIMARY | B | ALL | NULL | NULL | NULL | NULL | 10 | Using where; FirstMatch(A) |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------------------+
3 rows in set (0.01 sec)

MariaDB [test]> set optimizer_prune_level=1;
Query OK, 0 rows affected (0.00 sec)

MariaDB [test]> explain select * from one_k A where a in (select B.a from ten B, ten C where C.a < A.a);
+----+-------------+-------+------+---------------+------+---------+------+------+----------------------------------------------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------------------------------------------------------+
| 1 | PRIMARY | B | ALL | NULL | NULL | NULL | NULL | 10 | Start temporary |
| 1 | PRIMARY | C | ALL | NULL | NULL | NULL | NULL | 10 | Using where |
| 1 | PRIMARY | A | ALL | NULL | NULL | NULL | NULL | 1000 | Using where; End temporary; Using join buffer (flat, BNL join) |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------------------------------------------------------+
3 rows in set (0.00 sec)

[Sergey Petrunia (sergefp)]

Last_query_cost values:

- The plan with A,C,B and FirstMatch: 22391.696266
- The plan with B,C,A and Start/End Temorary: 50707.742164