## MDEV-32290 Findings & Analysis The following document is in three sections: Test Case, Analysis, and Fix. All line numbers below are with respect to git SHA 1bbe91facc0517a08e5af179e35d8eeaf532389e which was the tip of 10.11 at the time of writing. ### Test Case I believe this scenario to be as simple as possible to reproduce the crash: ```sql CREATE TABLE t1 (a int); WITH RECURSIVE cte (a) AS ( SELECT 1 UNION SELECT a + 1 FROM ( SELECT 1 a FROM cte UNION SELECT 1 FROM t1 x1, t1 x2 ) d ) SELECT a FROM cte; DROP TABLE t1; ``` Summary and outline of features in the query which are required, details follow in the "Analysis" section. - Recursive CTE - Creates asymmetrical `uncacheable` flags in the `UNION` branch queries. - Gives the second execution where we call `mysql_derived_fill`. The first execution is the one that frees, so the null pointer can only be read on a later execution. - UNION - There must be a branch that owns the join buffer but does not have its `uncacheable` flag marked. - Materialization - `d` is materialized rather than merged into #3. - JOIN - Creates the join buffer which happens to be deallocated prematurely (causing the crash) - `JOIN_TAB::cleanup()` frees this when called by `do_select` Using the following EXPLAIN output, we map the above query to the select IDs. #1 is the outer select, #2 and #3 are the anchor and the recursive branch of `cte`, and #4 and #5 are the two branches of the derived table `d`. ``` +------+-------------------+------------+------+---------------+------+---------+------+------+----------+------------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +------+-------------------+------------+------+---------------+------+---------+------+------+----------+------------------------------------+ | 1 | PRIMARY | | ALL | NULL | NULL | NULL | NULL | 2 | 100.00 | | | 2 | DERIVED | NULL | NULL | NULL | NULL | NULL | NULL | NULL | NULL | No tables used | | 3 | UNCACHEABLE UNION | | ALL | NULL | NULL | NULL | NULL | 3 | 100.00 | | | 4 | LATERAL DERIVED | | ALL | NULL | NULL | NULL | NULL | 2 | 100.00 | | | 5 | UNION | x1 | ALL | NULL | NULL | NULL | NULL | 1 | 100.00 | | | 5 | UNION | x2 | ALL | NULL | NULL | NULL | NULL | 1 | 100.00 | Using join buffer (flat, BNL join) | | NULL | UNION RESULT | | ALL | NULL | NULL | NULL | NULL | NULL | NULL | | | NULL | UNION RESULT | | ALL | NULL | NULL | NULL | NULL | NULL | NULL | | +------+-------------------+------------+------+---------------+------+---------+------+------+----------+------------------------------------+ ``` The `EXPLAIN` itself never crashes, since `full` in `JOIN::join_free` also requires `!thd->lex->describe` (sql_select.cc:15913). ### Analysis The free and the bad read are both consequences of filling the derived table, so we need two fills to see the crash. The first sets up the nullptr and the second dereferences it. Freeing the cache pointer happens at the end of a derived table fill. `do_select` calls `join->join_free()` at sql_select.cc:22666, which computes `full= !(select_lex->uncacheable) && !(thd->lex->describe)` (sql_select.cc:15913), it tests the whole field and not just the `UNCACHEABLE_DEPENDENT` bit. A breakpoint there for the repro query, on the first derived table fill, gives `select_lex->uncacheable=0`. `JOIN::cleanup(true)` then calls `JOIN_TAB::cleanup` on each tab (sql_select.cc:16017), which releases the buffer and nulls the pointer (sql_select.cc:15531). In contrast to our test case, on a single derived table fill, the cache (join buffer) is released after use which is harmless as there will be no subsequent execution in the same query's lifetime to dereference the (now null) cache buffer pointer. The second derived table fill reuses some of the data structures from the first. `st_select_lex_unit::exec` calls `optimize()` (sql_union.cc:2194), which skips its early return because the unit's `uncacheable` is nonzero (sql_union.cc:2070) and takes `sl->join->reinit()` for an already optimized branch (sql_union.cc:2120-2121). Here, `JOIN::reinit` (sql_select.cc:4626-4683) resets join state but allocates no new join buffer. `exec` then calls `sl->join->optimize()` itself (sql_union.cc:2263), which returns immediately because `optimization_state != JOIN::NOT_OPTIMIZED` (sql_select.cc:1964-1965). The query runs again as-is, and a breakpoint at sql_select.cc:22843 shows `sub_select_cache` entered for x2 with `cache=0x0`, the same pointer released on the first fill. Why does a second fill even happen? It's from the CTE's `a + 1`. Iteration 1 sees `cte` = {1}, fills `d` = {1}, and #3 yields 2, which is new. Iteration 2 sees `cte` = {1, 2}, fills `d` = {1} again, and #3 yields 2, which is already present, so the recursion stops. Substituting `a` for `a + 1` gives no crash; the cache is still freed but there is no later fill to dereference the null pointer in that case. `JOIN_TAB::preread_init` refills when `derived->get_unit()->uncacheable` is nonzero (sql_select.cc:15731-15734), so every scan of `` (see above `EXPLAIN`) refills it. `st_select_lex::check_subqueries_with_recursive_references` is what sets that flag, walking outward from the select holding the recursive reference and marking that select and its master unit (sql_cte.cc:1621-1622), with `register_as_derived_with_rec_ref` marking the unit again (sql_derived.cc:1165). The walk stops at the first unit owned by the same WITH clause, so it marks #4 and d's unit and nothing else. Note this is not `st_select_lex::mark_as_dependent`, which does mark siblings, with `UNCACHEABLE_UNITED` (sql_lex.cc:3505-3511). That sibling marking is what would have prevented this crash, but the recursive reference path has no equivalent. We don't need any rows in the simple table. `do_select` runs the query a second time with `end_of_records` set at sql_select.cc:22621, `sub_select` forwards that at sql_select.cc:23037, and for x1 that pointer is `sub_select_cache`. With `t1` empty, x1 returns no rows, but the flush call into the buffer is still made. A join is required, since `sub_select_cache` is reachable only from a query that has a join buffer, and a join buffer needs a preceding table to buffer rows from. ### Fix Propagate the unit's `UNCACHEABLE_DEPENDENT` bits down to every branch of the union during `st_select_lex_unit::optimize`, immediately before (or inside of) the loop over branches at sql_union.cc:2102. `st_select_lex::optimize_unflattened_subqueries` already does this for subqueries (see sql_lex.cc:5103-5115), and its comment names this crash, so the fix gives derived table units an invariant they were missing. We can't rely on that code here because our case is a materialized CTE and it doesn't take the subquery execution path through the uncacheable propagation loop found in `st_select_lex::optimize_unflattened_subqueries`. This is the idea of the fix, but a separate loop isn't explicitly needed as we can leverage the loop starting just after it. But, for clarity: ``` diff --git a/sql/sql_union.cc b/sql/sql_union.cc index 15d4e3552cb..6619dc8082e 100644 --- a/sql/sql_union.cc +++ b/sql/sql_union.cc @@ -2099,6 +2099,11 @@ bool st_select_lex_unit::optimize() table->no_keyread= 0; } } + if (uncacheable) + { + for (SELECT_LEX *sl= select_cursor; sl; sl= sl->next_select()) + sl->uncacheable|= (uncacheable & UNCACHEABLE_DEPENDENT); + } for (SELECT_LEX *sl= select_cursor; sl; sl= sl->next_select()) { if (sl->tvc) ``` With the flag propagated, `JOIN::cleanup` takes the `full == false` path and calls `JOIN_TAB::partial_cleanup` (sql_select.cc:32473), which does not free the join cache. It will do this at the end of each fill of the derived table, instead of the full clean. The buffer is then released once, at statement teardown, through `st_select_lex::cleanup` (sql_union.cc:2838) calling `JOIN::destroy` (sql_select.cc:5041). The outer select's `join_free` is not what releases it, because that walk skips recursive with element units (sql_select.cc:15923-15924) and so does `cleanup_all_joins` (sql_union.cc:2869-2870). So the net effect of the fix is to move the join buffer release for #5 from the end of the first derived fill to statement teardown. Of course, the crash is fixed as well. `EXPLAIN` output after the above fix: ``` +------+-------------------+------------+------+---------------+------+---------+------+------+----------+------------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +------+-------------------+------------+------+---------------+------+---------+------+------+----------+------------------------------------+ | 1 | PRIMARY | | ALL | NULL | NULL | NULL | NULL | 2 | 100.00 | | | 2 | DERIVED | NULL | NULL | NULL | NULL | NULL | NULL | NULL | NULL | No tables used | | 3 | UNCACHEABLE UNION | | ALL | NULL | NULL | NULL | NULL | 3 | 100.00 | | | 4 | LATERAL DERIVED | | ALL | NULL | NULL | NULL | NULL | 2 | 100.00 | | | 5 | DEPENDENT UNION | x1 | ALL | NULL | NULL | NULL | NULL | 1 | 100.00 | | | 5 | DEPENDENT UNION | x2 | ALL | NULL | NULL | NULL | NULL | 1 | 100.00 | Using join buffer (flat, BNL join) | | NULL | UNION RESULT | | ALL | NULL | NULL | NULL | NULL | NULL | NULL | | | NULL | UNION RESULT | | ALL | NULL | NULL | NULL | NULL | NULL | NULL | | +------+-------------------+------------+------+---------------+------+---------+------+------+----------+------------------------------------+ ```