revision-id: 59a3c46b7b2dfecc04679b0aaaa5a7ee7fc1de1e (mariadb-10.5.2-432-g59a3c46b7b2) parent(s): 687b7cc7f7ef1f842a080a2d5d57eb5e24e26f42 author: Sergei Petrunia committer: Sergei Petrunia timestamp: 2021-03-15 14:22:21 +0300 message: MDEV-17399: JSON_TABLE: Fix the problem with cross-nested-join dependency Fix for for the problem with - Cross-outer-join dependency - dead-end join prefix - join order pruning See the comments in the patch for detailed description --- mysql-test/suite/json/r/json_table.result | 31 +++++++- mysql-test/suite/json/t/json_table.test | 33 ++++++++- sql/json_table.cc | 114 ++++++++++++++++++++++++++++++ sql/json_table.h | 3 + sql/sql_select.cc | 3 + 5 files changed, 182 insertions(+), 2 deletions(-) diff --git a/mysql-test/suite/json/r/json_table.result b/mysql-test/suite/json/r/json_table.result index 6a8a9fb08ec..ffe88a7721f 100644 --- a/mysql-test/suite/json/r/json_table.result +++ b/mysql-test/suite/json/r/json_table.result @@ -457,5 +457,34 @@ seq0 name seq1 color seq2 size seq3 price 2 Y NULL NULL 2 11 NULL NULL 2 Y 1 red NULL NULL NULL NULL # -# End of 10.5 tests +# Test for the problem with +# - Cross-outer-join dependency +# - dead-end join prefix +# - join order pruning +# +create table t20 (a int not null); +create table t21 (a int not null primary key, js varchar(100)); +insert into t20 select seq from seq_1_to_100; +insert into t21 select a, '{"a":100}' from t20; +create table t31(a int); +create table t32(b int); +insert into t31 values (1); +insert into t32 values (1); +explain +select +t20.a, jt1.ab +from +t20 +left join t21 on t20.a=t21.a +join +(t31 left join (t32 join JSON_TABLE(t21.js,'$' COLUMNS (ab INT PATH '$.a')) AS jt1) on t31.a<3); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t31 system NULL NULL NULL NULL 1 +1 SIMPLE t20 ALL NULL NULL NULL NULL 100 +1 SIMPLE t21 eq_ref PRIMARY PRIMARY 4 test.t20.a 1 +1 SIMPLE t32 ALL NULL NULL NULL NULL 1 Using where +1 SIMPLE jt1 ALL NULL NULL NULL NULL 40 Table function: json_table +drop table t20,t21,t31,t32; +# +# End of 10.6 tests # diff --git a/mysql-test/suite/json/t/json_table.test b/mysql-test/suite/json/t/json_table.test index 071642fc737..03cc19ad72c 100644 --- a/mysql-test/suite/json/t/json_table.test +++ b/mysql-test/suite/json/t/json_table.test @@ -1,3 +1,5 @@ +--source include/have_sequence.inc + select * from json_table('[{"a": 1, "b": [11,111]}, {"a": 2, "b": [22,222]}]', '$[*]' COLUMNS( a INT PATH '$.a')) as tt; select * from JSON_TABLE( '[ {"a": 1, "b": [11,111]}, {"a": 2, "b": [22,222]}, {"a":3}]', '$[*]' COLUMNS( a INT PATH '$.a', NESTED PATH '$.b[*]' COLUMNS (b INT PATH '$'))) as jt; @@ -342,5 +344,34 @@ json_table( ) as T order by seq0, name; --echo # ---echo # End of 10.5 tests +--echo # Test for the problem with +--echo # - Cross-outer-join dependency +--echo # - dead-end join prefix +--echo # - join order pruning +--echo # + +create table t20 (a int not null); +create table t21 (a int not null primary key, js varchar(100)); + +insert into t20 select seq from seq_1_to_100; +insert into t21 select a, '{"a":100}' from t20; + +create table t31(a int); +create table t32(b int); +insert into t31 values (1); +insert into t32 values (1); + +explain +select + t20.a, jt1.ab +from + t20 + left join t21 on t20.a=t21.a + join + (t31 left join (t32 join JSON_TABLE(t21.js,'$' COLUMNS (ab INT PATH '$.a')) AS jt1) on t31.a<3); + +drop table t20,t21,t31,t32; + +--echo # +--echo # End of 10.6 tests --echo # diff --git a/sql/json_table.cc b/sql/json_table.cc index 1c44e370195..701aeff5020 100644 --- a/sql/json_table.cc +++ b/sql/json_table.cc @@ -1284,3 +1284,117 @@ void Table_function_json_table::fix_after_pullout(TABLE_LIST *sql_table, } +/* + @brief + Recursively make all tables in the join_list also depend on deps. +*/ + +static void add_extra_deps(List<TABLE_LIST> *join_list, table_map deps) +{ + TABLE_LIST *table; + List_iterator<TABLE_LIST> li(*join_list); + while ((table= li++)) + { + table->dep_tables |= deps; + NESTED_JOIN *nested_join; + if ((nested_join= table->nested_join)) + { + // set the deps inside, too + add_extra_deps(&nested_join->join_list, deps); + } + } +} + + +/* + @brief + Add extra dependencies implied by table functions so that the join + optimizer does not construct "dead-end" join prefixes. + + @detail + There are two kinds of limitations on join order: + 1A. Outer joins require that inner tables follow outer. + 1B. Tables within a join nest must be present in the join order + "without interleaving". See check_interleaving_with_nj for details. + + 2. Table function argument may refer to *any* table that precedes the + current table in the query text. The table maybe outside of the current + nested join and/or inside another nested join. + + @example + + select ... + from + t20 left join t21 on t20.a=t21.a + join + (t31 left join (t32 join + JSON_TABLE(t21.js, + '$' COLUMNS (ab INT PATH '$.a')) AS jt + ) on t31.a<3 + ) + + Here, jt's argument refers to t21. + + Table dependencies are: + t21 -> t20 + t32 -> t31 + jt -> t21 t31 (also indirectly depends on t20 through t21) + + This allows to construct a "dead-end" join prefix, like: + + t31, t32 + + Here, "no interleaving" rule requires the next table to be jt, but we + can't add it, because it depends on t21 which is not in the join prefix. + + @end example + + Dead-end join prefixes do not work with join prefix pruning done for + @@optimizer_prune_level: it is possible that all non-dead-end prefixes are + pruned away. + + The solution is as follows: if there is an outer join that contains + (directly on indirectly) a table function JT which has a reference JREF + outside of the outer join: + + left join ( T_I ... json_table(JREF, ...) as JT ...) + + then make *all* tables T_I also dependent on outside references in JREF. + This way, the optimizer will put table T_I into the join prefix only when + JT can be put there as well, and "dead-end" prefixes will not be built. + + @param join_list List of tables to process. Initial invocation should + supply the JOIN's top-level table list. + @param nest_tables Bitmap of all tables in the join list. + + @return Bitmap of all outside references that tables in join_list have +*/ + +table_map add_table_function_dependencies(List<TABLE_LIST> *join_list, + table_map nest_tables) +{ + TABLE_LIST *table; + table_map res= 0; + List_iterator<TABLE_LIST> li(*join_list); + + // Recursively compute extra dependencies + while ((table= li++)) + { + NESTED_JOIN *nested_join; + if ((nested_join= table->nested_join)) + { + res |= add_table_function_dependencies(&nested_join->join_list, + nested_join->used_tables); + } + else if (table->table_function) + res |= table->dep_tables; + } + res= res & ~nest_tables & ~PSEUDO_TABLE_BITS; + // Then, make all "peers" have them: + if (res) + add_extra_deps(join_list, res); + + return res; +} + + diff --git a/sql/json_table.h b/sql/json_table.h index bab4ef9c185..8988c05354a 100644 --- a/sql/json_table.h +++ b/sql/json_table.h @@ -252,5 +252,8 @@ class Table_function_json_table : public Sql_alloc TABLE *create_table_for_function(THD *thd, TABLE_LIST *sql_table); +table_map add_table_function_dependencies(List<TABLE_LIST> *join_list, + table_map nest_tables); + #endif /* JSON_TABLE_INCLUDED */ diff --git a/sql/sql_select.cc b/sql/sql_select.cc index 2acb6f9443a..e9ae46e1a5e 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -1921,6 +1921,9 @@ JOIN::optimize_inner() /* Convert all outer joins to inner joins if possible */ conds= simplify_joins(this, join_list, conds, TRUE, FALSE); + + add_table_function_dependencies(join_list, table_map(-1)); + if (thd->is_error() || select_lex->save_leaf_tables(thd)) { if (arena)