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.

1 files changed, 7 insertions, 1 deletions

diff --git a/sql/sql_select.h b/sql/sql_select.h
index 4a2929207a5..e65267558e1 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -1307,9 +1307,15 @@ public:
     Bitmap of inner tables of semi-join nests that have a proper subset of
     their tables in the current join prefix. That is, of those semi-join
     nests that have their tables both in and outside of the join prefix.
+    (Note: tables that are constants but have not been pulled out of semi-join
+    nests are not considered part of semi-join nests)
   */
   table_map cur_sj_inner_tables;
-  
+
+#ifndef DBUG_OFF
+  void dbug_verify_sj_inner_tables(uint n_positions) const;
+#endif
+
   /* We also maintain a stack of join optimization states in * join->positions[] */
 /******* Join optimization state members end *******/