MDEV-28749: restore_prev_nj_state() doesn't update cur_sj_inner_tables correctly

(Try 2)

The code that updates semi-join optimization state for a join order prefix
had several bugs. The visible effect was bad optimization for FirstMatch or
LooseScan strategies: they either weren't considered when they should have
been, or considered when they shouldn't have been.

In order to hit the bug, the optimizer needs to consider several different
join prefixes in a certain order. Queries with "obvious" query plans which
prune all join orders except one are not affected.

Internally, the bugs in updates of semi-join state were:
1. restore_prev_sj_state() assumed that
  "we assume remaining_tables doesnt contain @tab"
  which wasn't true.
2. Another bug in this function: it did remove bits from
   join->cur_sj_inner_tables but never added them.
3. greedy_search() adds tables into the join prefix but neglects to update
   the semi-join optimization state. (It does update nested outer join
   state, see this call:
     check_interleaving_with_nj(best_table)
   but there's no matching call to update the semi-join state.
   (This wasn't visible because most of the state is in the POSITION
    structure which is updated. But there is also state in JOIN, too)

The patch:
- Fixes all of the above
- Adds JOIN::dbug_verify_sj_inner_tables() which is used to verify the
  state is correct at every step.
- Renames advance_sj_state() to optimize_semi_joins().
  = Introduces update_sj_state() which ideally should have been called
    "advance_sj_state" but I didn't reuse the name to not create confusion.

2 files changed, 7 insertions, 7 deletions

diff --git a/mysql-test/main/subselect_sj.result b/mysql-test/main/subselect_sj.result
index 9fd8186b66c..e9a484bbcbf 100644
--- a/mysql-test/main/subselect_sj.result
+++ b/mysql-test/main/subselect_sj.result
@@ -2178,10 +2178,10 @@ INSERT INTO t5 VALUES (7,0),(9,0);
 explain
 SELECT * FROM t3 WHERE t3.a IN (SELECT t5.a FROM t2, t4, t5 WHERE t2.c = t5.a AND t2.b = t5.b);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t5	index	a	a	10	NULL	2	Using index; Start temporary
+1	PRIMARY	t5	index	a	a	10	NULL	2	Using where; Using index; LooseScan
 1	PRIMARY	t4	ALL	NULL	NULL	NULL	NULL	3	
-1	PRIMARY	t2	ALL	b	NULL	NULL	NULL	10	Using where
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	15	Using where; End temporary; Using join buffer (flat, BNL join)
+1	PRIMARY	t2	ref	b	b	5	test.t5.b	2	Using where; FirstMatch(t5)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	15	Using where; Using join buffer (flat, BNL join)
 SELECT * FROM t3 WHERE t3.a IN (SELECT t5.a FROM t2, t4, t5 WHERE t2.c = t5.a AND t2.b = t5.b);
 a
 0
diff --git a/mysql-test/main/subselect_sj_jcl6.result b/mysql-test/main/subselect_sj_jcl6.result
index e97c1d5e915..c485b5e5f39 100644
--- a/mysql-test/main/subselect_sj_jcl6.result
+++ b/mysql-test/main/subselect_sj_jcl6.result
@@ -2189,10 +2189,10 @@ INSERT INTO t5 VALUES (7,0),(9,0);
 explain
 SELECT * FROM t3 WHERE t3.a IN (SELECT t5.a FROM t2, t4, t5 WHERE t2.c = t5.a AND t2.b = t5.b);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t5	index	a	a	10	NULL	2	Using index; Start temporary
-1	PRIMARY	t4	ALL	NULL	NULL	NULL	NULL	3	Using join buffer (flat, BNL join)
-1	PRIMARY	t2	ALL	b	NULL	NULL	NULL	10	Using where; Using join buffer (incremental, BNL join)
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	15	Using where; End temporary; Using join buffer (incremental, BNL join)
+1	PRIMARY	t5	index	a	a	10	NULL	2	Using where; Using index; LooseScan
+1	PRIMARY	t4	ALL	NULL	NULL	NULL	NULL	3	
+1	PRIMARY	t2	ref	b	b	5	test.t5.b	2	Using where; FirstMatch(t5)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	15	Using where; Using join buffer (flat, BNL join)
 SELECT * FROM t3 WHERE t3.a IN (SELECT t5.a FROM t2, t4, t5 WHERE t2.c = t5.a AND t2.b = t5.b);
 a
 0