[Commits] 9f6066441c1: MDEV-26301: LATERAL DERIVED refills the temp. table too many times
by psergey 08 Aug '21
by psergey 08 Aug '21
08 Aug '21
revision-id: 9f6066441c1f014c48770e52164cf2fab93ca078 (mariadb-10.5.4-837-g9f6066441c1)
parent(s): 4ba4c06038165726dad6a18d85c2b54446ea5ef8
author: Sergei Petrunia
committer: Sergei Petrunia
timestamp: 2021-08-08 19:15:45 +0300
message:
MDEV-26301: LATERAL DERIVED refills the temp. table too many times
---
mysql-test/main/derived_split_innodb.result | 220 ++++++++++++++++++++++++++++
mysql-test/main/derived_split_innodb.test | 153 +++++++++++++++++++
mysql-test/main/mysqld--help.result | 3 +-
mysql-test/main/opt_trace.result | 2 +-
sql/opt_split.cc | 192 +++++++++++++++++++++++-
sql/sql_derived.cc | 9 ++
sql/sql_lex.cc | 1 +
sql/sql_lex.h | 3 +
sql/sql_priv.h | 1 +
sql/sql_select.cc | 5 +-
sql/sql_select.h | 28 +++-
sql/sql_union.cc | 1 +
sql/sys_vars.cc | 1 +
13 files changed, 609 insertions(+), 10 deletions(-)
diff --git a/mysql-test/main/derived_split_innodb.result b/mysql-test/main/derived_split_innodb.result
index 9edf9a1f2ae..d37339b8393 100644
--- a/mysql-test/main/derived_split_innodb.result
+++ b/mysql-test/main/derived_split_innodb.result
@@ -241,3 +241,223 @@ set optimizer_switch='split_materialized=default';
set use_stat_tables=default;
set optimizer_use_condition_selectivity=default;
# End of 10.3 tests
+#
+# MDEV-26301: LATERAL DERIVED refills the temp. table too many times
+#
+create table t1(a int, b int);
+insert into t1 select seq,seq from seq_1_to_5;
+create table t2(a int, b int, key(a));
+insert into t2
+select A.seq,B.seq from seq_1_to_25 A, seq_1_to_2 B;
+create table t3(a int, b int, key(a));
+insert into t3
+select A.seq,B.seq from seq_1_to_5 A, seq_1_to_3 B;
+analyze table t1,t2,t3 persistent for all;
+Table Op Msg_type Msg_text
+test.t1 analyze status Engine-independent statistics collected
+test.t1 analyze status OK
+test.t2 analyze status Engine-independent statistics collected
+test.t2 analyze status Table is already up to date
+test.t3 analyze status Engine-independent statistics collected
+test.t3 analyze status Table is already up to date
+explain
+select * from
+(t1 left join t2 on t2.a=t1.b) left join t3 on t3.a=t1.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 5
+1 SIMPLE t2 ref a a 5 test.t1.b 2 Using where
+1 SIMPLE t3 ref a a 5 test.t1.b 3 Using where
+create table t10 (
+grp_id int,
+col1 int,
+key(grp_id)
+);
+insert into t10
+select
+A.seq,
+B.seq
+from
+seq_1_to_100 A,
+seq_1_to_100 B;
+create table t11 (
+col1 int,
+col2 int
+);
+insert into t11
+select A.seq, A.seq from seq_1_to_10 A;
+analyze table t10,t11 persistent for all;
+Table Op Msg_type Msg_text
+test.t10 analyze status Engine-independent statistics collected
+test.t10 analyze status Table is already up to date
+test.t11 analyze status Engine-independent statistics collected
+test.t11 analyze status OK
+set optimizer_trace=1;
+explain
+select * from
+(
+(t1 left join t2 on t2.a=t1.b)
+left join t3 on t3.a=t1.b
+) left join (select grp_id, count(*)
+from t10 left join t11 on t11.col1=t10.col1
+group by grp_id) T on T.grp_id=t1.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 5
+1 PRIMARY t2 ref a a 5 test.t1.b 2 Using where
+1 PRIMARY t3 ref a a 5 test.t1.b 3 Using where
+1 PRIMARY <derived2> ref key0 key0 5 test.t1.b 10 Using where
+2 LATERAL DERIVED t10 ref grp_id grp_id 5 test.t1.b 100
+2 LATERAL DERIVED t11 ALL NULL NULL NULL NULL 10 Using where; Using join buffer (flat, BNL join)
+select
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+information_schema.optimizer_trace;
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+[
+
+ {
+ "unsplit_cost": 253440.0075,
+ "split_cost": 2535.968504,
+ "record_count_for_split": 30,
+ "split_chosen": true
+ }
+]
+set @tmp_26301=@@optimizer_switch;
+set optimizer_switch='split_materialized_is_lazy=on';
+explain
+select * from
+(
+(t1 left join t2 on t2.a=t1.b)
+left join t3 on t3.a=t1.b
+) left join (select grp_id, count(*)
+from t10 left join t11 on t11.col1=t10.col1
+group by grp_id) T on T.grp_id=t1.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 5
+1 PRIMARY t2 ref a a 5 test.t1.b 2 Using where
+1 PRIMARY t3 ref a a 5 test.t1.b 3 Using where
+1 PRIMARY <derived2> ref key0 key0 5 test.t1.b 10 Using where
+2 LATERAL DERIVED t10 ref grp_id grp_id 5 test.t1.b 100
+2 LATERAL DERIVED t11 ALL NULL NULL NULL NULL 10 Using where; Using join buffer (flat, BNL join)
+select
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+information_schema.optimizer_trace;
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+[
+
+ {
+ "unsplit_cost": 253440.0075,
+ "split_cost": 2535.968504,
+ "record_count_for_split": 30,
+ "join_prefix_fanout_for_split": 5,
+ "split_chosen": true
+ }
+]
+create table t21 (pk int primary key);
+insert into t21 values (1),(2),(3);
+create table t22 (pk int primary key);
+insert into t22 values (1),(2),(3);
+explain
+select * from
+t21, t22,
+(
+(t1 left join t2 on t2.a=t1.b)
+left join t3 on t3.a=t1.b
+) left join (select grp_id, count(*)
+from t10 left join t11 on t11.col1=t10.col1
+group by grp_id) T on T.grp_id=t1.b
+where
+t21.pk=1 and t22.pk=2;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t21 const PRIMARY PRIMARY 4 const 1 Using index
+1 PRIMARY t22 const PRIMARY PRIMARY 4 const 1 Using index
+1 PRIMARY t1 ALL NULL NULL NULL NULL 5
+1 PRIMARY t2 ref a a 5 test.t1.b 2 Using where
+1 PRIMARY t3 ref a a 5 test.t1.b 3 Using where
+1 PRIMARY <derived2> ref key0 key0 5 test.t1.b 10 Using where
+2 LATERAL DERIVED t10 ref grp_id grp_id 5 test.t1.b 100
+2 LATERAL DERIVED t11 ALL NULL NULL NULL NULL 10 Using where; Using join buffer (flat, BNL join)
+select
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+information_schema.optimizer_trace;
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+[
+
+ {
+ "unsplit_cost": 253440.0075,
+ "split_cost": 2535.968504,
+ "record_count_for_split": 30,
+ "join_prefix_fanout_for_split": 5,
+ "split_chosen": true
+ }
+]
+explain
+select * from
+t21,
+(
+(t1 left join t2 on t2.a=t1.b)
+left join t3 on t3.a=t1.b
+) left join (select grp_id, count(*)
+from
+t22 join t10 left join t11 on t11.col1=t10.col1
+where
+t22.pk=1
+group by grp_id) T on T.grp_id=t1.b
+where
+t21.pk=1;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t21 const PRIMARY PRIMARY 4 const 1 Using index
+1 PRIMARY t1 ALL NULL NULL NULL NULL 5
+1 PRIMARY t2 ref a a 5 test.t1.b 2 Using where
+1 PRIMARY t3 ref a a 5 test.t1.b 3 Using where
+1 PRIMARY <derived2> ref key0 key0 5 test.t1.b 10 Using where
+2 LATERAL DERIVED t22 const PRIMARY PRIMARY 4 const 1 Using index
+2 LATERAL DERIVED t10 ref grp_id grp_id 5 test.t1.b 100
+2 LATERAL DERIVED t11 ALL NULL NULL NULL NULL 10 Using where; Using join buffer (flat, BNL join)
+select
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+information_schema.optimizer_trace;
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+[
+
+ {
+ "unsplit_cost": 253440.0075,
+ "split_cost": 2535.968504,
+ "record_count_for_split": 30,
+ "join_prefix_fanout_for_split": 5,
+ "split_chosen": true
+ }
+]
+create table t5 (
+pk int primary key
+);
+insert into t5 select seq from seq_1_to_1000;
+explain
+select * from
+t21,
+(
+(((t1 join t5 on t5.pk=t1.b)) left join t2 on t2.a=t1.b)
+left join t3 on t3.a=t1.b
+) left join (select grp_id, count(*)
+from
+t22 join t10 left join t11 on t11.col1=t10.col1
+where
+t22.pk=1
+group by grp_id) T on T.grp_id=t1.b
+where
+t21.pk=1;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t21 const PRIMARY PRIMARY 4 const 1 Using index
+1 PRIMARY t1 ALL NULL NULL NULL NULL 5 Using where
+1 PRIMARY t5 eq_ref PRIMARY PRIMARY 4 test.t1.b 1 Using index
+1 PRIMARY t2 ref a a 5 test.t1.b 2
+1 PRIMARY t3 ref a a 5 test.t1.b 3
+1 PRIMARY <derived2> ref key0 key0 5 test.t1.b 10 Using where
+2 LATERAL DERIVED t22 const PRIMARY PRIMARY 4 const 1 Using index
+2 LATERAL DERIVED t10 ref grp_id grp_id 5 test.t5.pk 100
+2 LATERAL DERIVED t11 ALL NULL NULL NULL NULL 10 Using where; Using join buffer (flat, BNL join)
+set optimizer_trace=0;
+set optimizer_switch=@tmp_26301;
+drop table t1,t2,t3,t5, t10, t11, t21, t22;
diff --git a/mysql-test/main/derived_split_innodb.test b/mysql-test/main/derived_split_innodb.test
index bee9ef497b6..1369018f532 100644
--- a/mysql-test/main/derived_split_innodb.test
+++ b/mysql-test/main/derived_split_innodb.test
@@ -193,3 +193,156 @@ set use_stat_tables=default;
set optimizer_use_condition_selectivity=default;
--echo # End of 10.3 tests
+
+--echo #
+--echo # MDEV-26301: LATERAL DERIVED refills the temp. table too many times
+--echo #
+
+# 5 values
+create table t1(a int, b int);
+insert into t1 select seq,seq from seq_1_to_5;
+
+# 5 value groups of size 2 each
+create table t2(a int, b int, key(a));
+insert into t2
+select A.seq,B.seq from seq_1_to_25 A, seq_1_to_2 B;
+
+# 5 value groups of size 3 each
+create table t3(a int, b int, key(a));
+insert into t3
+select A.seq,B.seq from seq_1_to_5 A, seq_1_to_3 B;
+
+analyze table t1,t2,t3 persistent for all;
+
+explain
+select * from
+ (t1 left join t2 on t2.a=t1.b) left join t3 on t3.a=t1.b;
+
+# Now, create tables for Groups.
+
+create table t10 (
+ grp_id int,
+ col1 int,
+ key(grp_id)
+);
+
+# 100 groups of 100 values each
+insert into t10
+select
+ A.seq,
+ B.seq
+from
+ seq_1_to_100 A,
+ seq_1_to_100 B;
+
+# and X10 multiplier
+
+create table t11 (
+ col1 int,
+ col2 int
+);
+insert into t11
+select A.seq, A.seq from seq_1_to_10 A;
+
+
+analyze table t10,t11 persistent for all;
+set optimizer_trace=1;
+
+explain
+select * from
+ (
+ (t1 left join t2 on t2.a=t1.b)
+ left join t3 on t3.a=t1.b
+ ) left join (select grp_id, count(*)
+ from t10 left join t11 on t11.col1=t10.col1
+ group by grp_id) T on T.grp_id=t1.b;
+select
+ json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+ information_schema.optimizer_trace;
+
+set @tmp_26301=@@optimizer_switch;
+set optimizer_switch='split_materialized_is_lazy=on';
+
+explain
+select * from
+ (
+ (t1 left join t2 on t2.a=t1.b)
+ left join t3 on t3.a=t1.b
+ ) left join (select grp_id, count(*)
+ from t10 left join t11 on t11.col1=t10.col1
+ group by grp_id) T on T.grp_id=t1.b;
+select
+ json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+ information_schema.optimizer_trace;
+
+create table t21 (pk int primary key);
+insert into t21 values (1),(2),(3);
+
+create table t22 (pk int primary key);
+insert into t22 values (1),(2),(3);
+
+# Same as above but throw in a couple of const tables.
+explain
+select * from
+ t21, t22,
+ (
+ (t1 left join t2 on t2.a=t1.b)
+ left join t3 on t3.a=t1.b
+ ) left join (select grp_id, count(*)
+ from t10 left join t11 on t11.col1=t10.col1
+ group by grp_id) T on T.grp_id=t1.b
+where
+ t21.pk=1 and t22.pk=2;
+
+select
+ json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+ information_schema.optimizer_trace;
+
+explain
+select * from
+ t21,
+ (
+ (t1 left join t2 on t2.a=t1.b)
+ left join t3 on t3.a=t1.b
+ ) left join (select grp_id, count(*)
+ from
+ t22 join t10 left join t11 on t11.col1=t10.col1
+ where
+ t22.pk=1
+ group by grp_id) T on T.grp_id=t1.b
+where
+ t21.pk=1;
+
+select
+ json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+ information_schema.optimizer_trace;
+
+# And also add a non-const table
+
+create table t5 (
+ pk int primary key
+ );
+insert into t5 select seq from seq_1_to_1000;
+
+explain
+select * from
+ t21,
+ (
+ (((t1 join t5 on t5.pk=t1.b)) left join t2 on t2.a=t1.b)
+ left join t3 on t3.a=t1.b
+ ) left join (select grp_id, count(*)
+ from
+ t22 join t10 left join t11 on t11.col1=t10.col1
+ where
+ t22.pk=1
+ group by grp_id) T on T.grp_id=t1.b
+where
+ t21.pk=1;
+
+set optimizer_trace=0;
+set optimizer_switch=@tmp_26301;
+drop table t1,t2,t3,t5, t10, t11, t21, t22;
diff --git a/mysql-test/main/mysqld--help.result b/mysql-test/main/mysqld--help.result
index 78616ae7c9d..6a38d720493 100644
--- a/mysql-test/main/mysqld--help.result
+++ b/mysql-test/main/mysqld--help.result
@@ -718,7 +718,8 @@ The following specify which files/extra groups are read (specified before remain
extended_keys, exists_to_in, orderby_uses_equalities,
condition_pushdown_for_derived, split_materialized,
condition_pushdown_for_subquery, rowid_filter,
- condition_pushdown_from_having, not_null_range_scan
+ condition_pushdown_from_having, not_null_range_scan,
+ split_materialized_is_lazy
--optimizer-trace=name
Controls tracing of the Optimizer:
optimizer_trace=option=val[,option=val...], where option
diff --git a/mysql-test/main/opt_trace.result b/mysql-test/main/opt_trace.result
index d4ba8eccb91..97d3b48ee85 100644
--- a/mysql-test/main/opt_trace.result
+++ b/mysql-test/main/opt_trace.result
@@ -8954,9 +8954,9 @@ json_detailed(json_extract(trace, '$**.lateral_derived_choice'))
],
"split_plan_choice":
{
+ "unsplit_cost": 25.72361682,
"split_cost": 2.488945919,
"record_count_for_split": 4,
- "unsplit_cost": 25.72361682,
"split_chosen": true
},
"chosen_lateral_derived":
diff --git a/sql/opt_split.cc b/sql/opt_split.cc
index d482c2de2a4..2d124a7fe2e 100644
--- a/sql/opt_split.cc
+++ b/sql/opt_split.cc
@@ -876,11 +876,92 @@ void reset_validity_vars_for_keyuses(KEYUSE_EXT *key_keyuse_ext_start,
}
+
+/*
+ @brief
+ Find shortest join order sub-prefix that covers the specified table_map.
+
+ @detail
+ Given a join prefix and a bitmap of table(s) in table_map, find the
+ shortest prefix of the prefix that covers the tables in the table_map.
+*/
+
+uint get_prefix_size(const POSITION *positions, uint max_pos, table_map map)
+{
+ map= map & ~PSEUDO_TABLE_BITS; // remove OUTER_REF_TABLE_BIT
+ table_map covered= 0;
+ uint i;
+
+ for (i=0; i < max_pos; i++)
+ {
+ covered |= positions[i].table->table->map;
+ if (!(map & ~covered))
+ break;
+ }
+ return i;
+}
+
+
+/*
+ @brief
+ Find the shortest join prefix that has a KEYUSE_EXT for a given key_part.
+
+ @detail
+ Given an array of KEYUSE objects for access to {table, key, key_part},
+ and a join order prefix (specified by array of POSITION structs),
+ find the shortest prefix for which there is a KEYUSE_EXT object describin
+ the access to they table.key.key_part
+
+ @note
+ KEYUSE_EXT objects are from inside the derived table, while the join
+ prefix is from the parent JOIN, so we need to use
+ KEYUSE_EXT::needed_in_prefix
+*/
+
+uint get_min_prefix_for_key_part(const POSITION *positions, uint max_prefix_size,
+ KEYUSE_EXT *keyuse)
+{
+ TABLE *table= keyuse->table;
+ uint key= keyuse->key;
+ uint keypart= keyuse->keypart;
+ uint prefix_size= max_prefix_size;
+
+ while (keyuse->table == table && keyuse->key == key &&
+ keyuse->keypart == keypart)
+ {
+ uint cur_size= get_prefix_size(positions, max_prefix_size,
+ keyuse->needed_in_prefix);
+ if (cur_size < prefix_size)
+ prefix_size= cur_size;
+ keyuse++;
+ }
+ return prefix_size;
+}
+
+
+/*
+ Get fanout of of a join prefix
+*/
+double get_join_prefix_fanout(const POSITION *positions, uint prefix_size)
+{
+ double fanout = 1.0;
+ for (uint i=0; i <= prefix_size; i++)
+ {
+ if (positions[i].records_read > 1e-30)
+ fanout *= positions[i].records_read;
+ if (positions[i].cond_selectivity > 1e-30)
+ fanout *= positions[i].cond_selectivity;
+ }
+ return fanout;
+}
+
/**
@brief
Choose the best splitting to extend the evaluated partial join
@param
+ join_prefix Join order prefix built so far
+ prefix_size Length of the join prefix
record_count estimated cardinality of the extended partial join
remaining_tables tables not joined yet
@@ -906,7 +987,9 @@ void reset_validity_vars_for_keyuses(KEYUSE_EXT *key_keyuse_ext_start,
if the plan has been chosen, NULL - otherwise.
*/
-SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
+SplM_plan_info * JOIN_TAB::choose_best_splitting(const POSITION *join_prefix,
+ uint prefix_size,
+ double record_count,
table_map remaining_tables)
{
SplM_opt_info *spl_opt_info= table->spl_opt_info;
@@ -922,6 +1005,7 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
SplM_plan_info *spl_plan= 0;
uint best_key= 0;
uint best_key_parts= 0;
+ uint best_min_prefix_size;
Json_writer_object spl_trace(thd, "lateral_derived_choice");
Json_writer_array trace_indexes(thd, "indexes_for_splitting");
@@ -942,6 +1026,7 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
uint key= keyuse_ext->key;
KEYUSE_EXT *key_keyuse_ext_start= keyuse_ext;
key_part_map found_parts= 0;
+ uint prefix_len= 0;
do
{
if (keyuse_ext->needed_in_prefix & remaining_tables)
@@ -951,11 +1036,40 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
}
if (!(keyuse_ext->keypart_map & found_parts))
{
+ /*
+ Check for
+ 1. found_parts is empty and this is the first key part we've found
+ 2. or, we are looking at the first keyuse object for this keypart,
+ and found_parts has a bit set for the previous key part.
+ */
if ((!found_parts && !keyuse_ext->keypart) ||
(found_parts && ((keyuse_ext->keypart_map >> 1) & found_parts)))
+ {
+ if (optimizer_flag(thd, OPTIMIZER_SWITCH_SPLIT_MATERIALIZED_IS_LAZY))
+ {
+ /*
+ Find the shortest join prefix we'll need to get a lookup value
+ for this keypart read this key part
+ */
+ uint min_for_kp= get_min_prefix_for_key_part(join_prefix,
+ prefix_size,
+ keyuse_ext);
+ /*
+ The join prefix needed to read all keyparts is the longest
+ prefix of all key parts.
+ */
+ if (min_for_kp > prefix_len)
+ prefix_len= min_for_kp;
+ }
+
found_parts|= keyuse_ext->keypart_map;
+ }
else
{
+ /*
+ This is a new key part but it doesn't form a continuous index
+ prefix. Skip all KEYUSEs for this index.
+ */
do
{
keyuse_ext++;
@@ -981,6 +1095,11 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
best_key_parts= keyuse_ext->keypart + 1;
best_rec_per_key= rec_per_key;
best_key_keyuse_ext_start= key_keyuse_ext_start;
+ if (optimizer_flag(thd, OPTIMIZER_SWITCH_SPLIT_MATERIALIZED_IS_LAZY))
+ {
+ best_min_prefix_size= prefix_len;
+ trace.add("min_prefix_len", (longlong)prefix_len);
+ }
}
keyuse_ext++;
}
@@ -1069,10 +1188,29 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
if (spl_plan)
{
Json_writer_object choice(thd, "split_plan_choice");
+ choice.add("unsplit_cost", spl_opt_info->unsplit_cost);
+
choice.add("split_cost", spl_plan->cost);
choice.add("record_count_for_split", record_count);
- choice.add("unsplit_cost", spl_opt_info->unsplit_cost);
- if(record_count * spl_plan->cost < spl_opt_info->unsplit_cost - 0.01)
+
+ double fanout= record_count;
+ if (optimizer_flag(thd, OPTIMIZER_SWITCH_SPLIT_MATERIALIZED_IS_LAZY))
+ {
+ /*
+ The LATERAL DERIVED table will only be refilled if the values it
+ refers to change.
+ The values refer only to the prefix of the join prefix so far.
+ Adjust the number of LATERAL DERIVED refills accordingly.
+ */
+ double prefix_fanout= get_join_prefix_fanout(join_prefix,
+ best_min_prefix_size);
+ if (prefix_fanout < record_count)
+ prefix_fanout= record_count;
+
+ choice.add("join_prefix_fanout_for_split", fanout);
+ }
+
+ if (fanout * spl_plan->cost < spl_opt_info->unsplit_cost - 0.01)
{
/*
The best plan that employs splitting is cheaper than
@@ -1112,6 +1250,10 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
@param
remaining_tables used to filter out the equalities that cannot
be pushed.
+ lparams if non-NULL, call lparams->add() to collect a list
+ of the "parameter" items for the lateral subquery.
+ The list will be used to reduce the number of times
+ the lateral derived table is refilled.
@details
This function is called by JOIN_TAB::fix_splitting that is used
@@ -1128,18 +1270,23 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
true on failure
*/
-bool JOIN::inject_best_splitting_cond(table_map remaining_tables)
+bool JOIN::inject_best_splitting_cond(table_map remaining_tables,
+ Lateral_derived_parameters *lparams)
{
Item *inj_cond= 0;
List<Item> *inj_cond_list= &spl_opt_info->inj_cond_list;
List_iterator<KEY_FIELD> li(spl_opt_info->added_key_fields);
KEY_FIELD *added_key_field;
+ table_map needed_tables= 0;
while ((added_key_field= li++))
{
if (remaining_tables & added_key_field->val->used_tables())
continue;
+ if (lparams && lparams->add_param(added_key_field->val))
+ return true;
if (inj_cond_list->push_back(added_key_field->cond, thd->mem_root))
return true;
+ needed_tables |= added_key_field->val->used_tables();
}
DBUG_ASSERT(inj_cond_list->elements);
switch (inj_cond_list->elements) {
@@ -1230,8 +1377,15 @@ bool JOIN_TAB::fix_splitting(SplM_plan_info *spl_plan,
memcpy((char *) md_join->best_positions,
(char *) spl_plan->best_positions,
sizeof(POSITION) * md_join->table_count);
- if (md_join->inject_best_splitting_cond(remaining_tables))
+
+ Lateral_derived_parameters *lparams= NULL;
+ if (optimizer_flag(join->thd, OPTIMIZER_SWITCH_SPLIT_MATERIALIZED_IS_LAZY))
+ lparams= new Lateral_derived_parameters;
+
+ if (md_join->inject_best_splitting_cond(remaining_tables, lparams))
return true;
+
+ table->pos_in_table_list->get_unit()->lateral_derived_params= lparams;
/*
This is called for a proper work of JOIN::get_best_combination()
called for the join that materializes T
@@ -1283,3 +1437,31 @@ bool JOIN::fix_all_splittings_in_plan()
}
return false;
}
+
+
+bool Lateral_derived_parameters::add_param(Item *item)
+{
+ Cached_item *tmp;
+ if (!(tmp= new_Cached_item(current_thd, item, FALSE)) ||
+ list.push_back(tmp))
+ return true;
+
+ return false;
+}
+
+
+/*
+ @brief
+ Test if LATERAL DERIVED table's parameters changed since last invocation
+
+ @return
+ false Parameter values have not changed since last invocation
+ true Parameter values have changed since last invocation. Current values
+ of the parameters are now saved.
+*/
+bool Lateral_derived_parameters::need_refill()
+{
+ if (test_if_group_changed(list) == -1)
+ return false; // not changed
+ return true;
+}
diff --git a/sql/sql_derived.cc b/sql/sql_derived.cc
index f8ee3475af8..25524c90da5 100644
--- a/sql/sql_derived.cc
+++ b/sql/sql_derived.cc
@@ -1233,6 +1233,15 @@ bool mysql_derived_fill(THD *thd, LEX *lex, TABLE_LIST *derived)
DBUG_RETURN(res);
}
+ /*
+ For LATERAL DERIVED tables, check if we actually need to refill it. If its
+ "parameters" (i.e. items it refers to) have the same values, we don't need
+ to refill.
+ */
+ if (unit->lateral_derived_params &&
+ !unit->lateral_derived_params->need_refill())
+ DBUG_RETURN(false);
+
if (unit->executed && !derived_is_recursive &&
(unit->uncacheable & UNCACHEABLE_DEPENDENT))
{
diff --git a/sql/sql_lex.cc b/sql/sql_lex.cc
index b9ca67182cf..5b3897b28fa 100644
--- a/sql/sql_lex.cc
+++ b/sql/sql_lex.cc
@@ -2915,6 +2915,7 @@ void st_select_lex_unit::init_query()
columns_are_renamed= false;
with_wrapped_tvc= false;
have_except_all_or_intersect_all= false;
+ lateral_derived_params= NULL;
}
void st_select_lex::init_query()
diff --git a/sql/sql_lex.h b/sql/sql_lex.h
index 45a3bf72fa4..278ee7d5276 100644
--- a/sql/sql_lex.h
+++ b/sql/sql_lex.h
@@ -845,6 +845,7 @@ class JOIN;
class select_unit;
class Procedure;
class Explain_query;
+class Lateral_derived_parameters;
void delete_explain_query(LEX *lex);
void create_explain_query(LEX *lex, MEM_ROOT *mem_root);
@@ -964,6 +965,8 @@ class st_select_lex_unit: public st_select_lex_node {
bool columns_are_renamed;
+ Lateral_derived_parameters *lateral_derived_params;
+
void init_query();
st_select_lex* outer_select();
const st_select_lex* first_select() const
diff --git a/sql/sql_priv.h b/sql/sql_priv.h
index 07f07a7150f..7cdb6a62d08 100644
--- a/sql/sql_priv.h
+++ b/sql/sql_priv.h
@@ -234,6 +234,7 @@
#define OPTIMIZER_SWITCH_USE_ROWID_FILTER (1ULL << 33)
#define OPTIMIZER_SWITCH_COND_PUSHDOWN_FROM_HAVING (1ULL << 34)
#define OPTIMIZER_SWITCH_NOT_NULL_RANGE_SCAN (1ULL << 35)
+#define OPTIMIZER_SWITCH_SPLIT_MATERIALIZED_IS_LAZY (1ULL << 36)
#define OPTIMIZER_SWITCH_DEFAULT (OPTIMIZER_SWITCH_INDEX_MERGE | \
OPTIMIZER_SWITCH_INDEX_MERGE_UNION | \
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 39e224ab024..85c3355cf08 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -7460,7 +7460,10 @@ best_access_path(JOIN *join,
loose_scan_opt.init(join, s, remaining_tables);
if (s->table->is_splittable())
- spl_plan= s->choose_best_splitting(record_count, remaining_tables);
+ {
+ spl_plan= s->choose_best_splitting(join_positions, idx, record_count,
+ remaining_tables);
+ }
Json_writer_array trace_paths(thd, "considered_access_paths");
if (s->keyuse)
diff --git a/sql/sql_select.h b/sql/sql_select.h
index 29e42ff8ef8..2a9cb5464e6 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -249,6 +249,7 @@ class AGGR_OP;
class Filesort;
struct SplM_plan_info;
class SplM_opt_info;
+class Lateral_derived_parameters;
typedef struct st_join_table {
TABLE *table;
@@ -682,7 +683,9 @@ typedef struct st_join_table {
void partial_cleanup();
void add_keyuses_for_splitting();
- SplM_plan_info *choose_best_splitting(double record_count,
+ SplM_plan_info *choose_best_splitting(const POSITION *join_prefix,
+ uint top_prefix_size,
+ double record_count,
table_map remaining_tables);
bool fix_splitting(SplM_plan_info *spl_plan, table_map remaining_tables,
bool is_const_table);
@@ -1795,7 +1798,8 @@ class JOIN :public Sql_alloc
bool inject_cond_into_where(Item *injected_cond);
bool check_for_splittable_materialized();
void add_keyuses_for_splitting();
- bool inject_best_splitting_cond(table_map remaining_tables);
+ bool inject_best_splitting_cond(table_map remaining_tables,
+ Lateral_derived_parameters *params);
bool fix_all_splittings_in_plan();
void make_notnull_conds_for_range_scans();
@@ -2532,4 +2536,24 @@ void propagate_new_equalities(THD *thd, Item *cond,
COND_EQUAL *inherited,
bool *is_simplifiable_cond);
+/*
+ A list of parameters for a derived table that uses LATERAL DERIVED
+ optimization.
+
+ The last values of the parameters are saved, which one can use to check
+ whether
+ - they've changed and one needs to refill the LATERAL DERIVED table
+ - they are not changed and refill is not needed.
+*/
+class Lateral_derived_parameters : public Sql_alloc
+{
+ List<Cached_item> list;
+public:
+ // Construction interface
+ bool add_param(Item *item);
+
+ // Execution interface
+ bool need_refill();
+};
+
#endif /* SQL_SELECT_INCLUDED */
diff --git a/sql/sql_union.cc b/sql/sql_union.cc
index b88d78c0db3..a0a89b1e401 100644
--- a/sql/sql_union.cc
+++ b/sql/sql_union.cc
@@ -2588,6 +2588,7 @@ bool st_select_lex_unit::cleanup()
}
columns_are_renamed= false;
cleaned= 1;
+ lateral_derived_params= NULL;
for (SELECT_LEX *sl= first_select(); sl; sl= sl->next_select())
error|= sl->cleanup();
diff --git a/sql/sys_vars.cc b/sql/sys_vars.cc
index 2f7cf290dcd..725f407fc3b 100644
--- a/sql/sys_vars.cc
+++ b/sql/sys_vars.cc
@@ -2717,6 +2717,7 @@ export const char *optimizer_switch_names[]=
"rowid_filter",
"condition_pushdown_from_having",
"not_null_range_scan",
+ "split_materialized_is_lazy",
"default",
NullS
};
1
0
[Commits] 4d3c4340286: MDEV-21130: Histograms: use JSON as on-disk format
by Sergei Petrunia 06 Aug '21
by Sergei Petrunia 06 Aug '21
06 Aug '21
revision-id: 4d3c434028649a0f14471ed4a1a4c10b97b78eb8 (mariadb-10.6.3-32-g4d3c4340286)
parent(s): 44f88fc96104365877b9ad8cc7106d48fc1d5448
author: Sergei Petrunia
committer: Sergei Petrunia
timestamp: 2021-08-06 20:08:16 +0300
message:
MDEV-21130: Histograms: use JSON as on-disk format
A demo of how to use in-memory data structure for histogram.
The patch shows how to
* convert string form of data to binary form
* compare two values in binary form
* compute a fraction for val in [X, Y] range.
grep for GSOC-TODO for notes.
---
sql/field.h | 3 +
sql/sql_statistics.cc | 256 +++++++++++++++++++++++++++++++++++++++++++++++++-
sql/sql_statistics.h | 40 +++++++-
3 files changed, 289 insertions(+), 10 deletions(-)
diff --git a/sql/field.h b/sql/field.h
index 4b64742b7b3..a24c6e8a300 100644
--- a/sql/field.h
+++ b/sql/field.h
@@ -1852,6 +1852,7 @@ class Field: public Value_source
{
return (double) 0.5;
}
+ virtual bool pos_through_val_str() { return false;}
/*
Check if comparison between the field and an item unambiguously
@@ -2137,6 +2138,8 @@ class Field_str :public Field {
{
return pos_in_interval_val_str(min, max, length_size());
}
+ bool pos_through_val_str() override {return true;}
+
bool test_if_equality_guarantees_uniqueness(const Item *const_item) const
override;
SEL_ARG *get_mm_leaf(RANGE_OPT_PARAM *param, KEY_PART *key_part,
diff --git a/sql/sql_statistics.cc b/sql/sql_statistics.cc
index 818d2b8d492..eed22d7ed77 100644
--- a/sql/sql_statistics.cc
+++ b/sql/sql_statistics.cc
@@ -1240,7 +1240,8 @@ class Column_stat: public Stat_table
default:
return NULL;
}
- if (!hist->parse(mem_root, table_field->read_stats->histogram_type_on_disk,
+ if (!hist->parse(mem_root, table_field,
+ table_field->read_stats->histogram_type_on_disk,
(const uchar*)val.ptr(), val.length()))
{
table_field->read_stats->histogram_= hist;
@@ -1253,7 +1254,7 @@ class Column_stat: public Stat_table
}
};
-bool Histogram_binary::parse(MEM_ROOT *mem_root, Histogram_type type_arg, const uchar *ptr_arg, uint size_arg)
+bool Histogram_binary::parse(MEM_ROOT *mem_root, Field *, Histogram_type type_arg, const uchar *ptr_arg, uint size_arg)
{
// Just copy the data
size = (uint8) size_arg;
@@ -1288,21 +1289,260 @@ void Histogram_json::init_for_collection(MEM_ROOT *mem_root, Histogram_type htyp
size = (uint8) size_arg;
}
-bool Histogram_json::parse(MEM_ROOT *mem_root, Histogram_type type_arg, const uchar *ptr, uint size_arg)
+bool Histogram_json::parse(MEM_ROOT *mem_root, Field *field, Histogram_type type_arg, const uchar *ptr, uint size_arg)
{
DBUG_ENTER("Histogram_json::parse");
type = type_arg;
const char *json = (char *)ptr;
int vt;
- bool result = json_get_array_items(json, json + strlen(json), &vt, hist_buckets);
+ bool result = json_get_array_items(json, json + strlen(json), &vt, hist_buckets_text);
if (!result)
{
my_error(ER_JSON_HISTOGRAM_PARSE_FAILED, MYF(0), vt);
DBUG_RETURN(true);
}
+ size= hist_buckets_text.size();
+
+ /*
+ Convert the text based array into a data structure that allows lookups and
+ estimates
+ */
+ for (auto &s : hist_buckets_text)
+ {
+ field->store_text(s.data(), s.size(), &my_charset_bin);
+
+ // Get the value in "truncated key tuple format" here:
+ uchar buf[MAX_KEY_LENGTH];
+ uint len_to_copy= field->key_length();
+ uint bytes= field->get_key_image(buf, len_to_copy, Field::itRAW);
+ histogram_bounds.push_back(std::string((char*)buf, bytes));
+ }
+
DBUG_RETURN(false);
}
+
+static
+void store_key_image_to_rec_no_null(Field *field, uchar *ptr) {
+ MY_BITMAP *old_map= dbug_tmp_use_all_columns(field->table,
+ &field->table->write_set);
+ field->set_key_image(ptr, field->key_length());
+ dbug_tmp_restore_column_map(&field->table->write_set, old_map);
+}
+
+/*
+ GSOC-TODO:
+ This is our replacement for Field::pos_in_interval_val_real
+
+ We take midpoint_val and an interval [min_val, max_val], and return
+ a number between 0.0 and 1.0 which specifies how close midpoint_val is
+ to one of the bounds.
+
+ @param field Field object. We don't care about the field's current value
+ (actually, we overwrite it). We need it for its virtual
+ functions.
+
+*/
+double pos_in_interval_through_val_real(Field *field,
+ uchar* min_val,
+ uchar *max_val,
+ uchar *midpoint_val)
+{
+
+ // For each passed value: unpack it into Field's current value. Then, we can
+ // get the value as double.
+
+ store_key_image_to_rec_no_null(field, min_val);
+ double min_val_real= field->val_real();
+
+ store_key_image_to_rec_no_null(field, max_val);
+ double max_val_real= field->val_real();
+
+ store_key_image_to_rec_no_null(field, midpoint_val);
+ double midpoint_val_real= field->val_real();
+
+ // The code below is a copy of logic from Field::pos_in_interval_val_real:
+ double n, d;
+ n= midpoint_val_real - min_val_real;
+ if (n < 0)
+ return 0.0;
+ d= max_val_real - min_val_real;
+ if (d <= 0)
+ return 1.0;
+ return MY_MIN(n/d, 1.0);
+}
+
+// Copy-paste:
+static
+inline ulonglong char_prefix_to_ulonglong(uchar *src)
+{
+ uint sz= sizeof(ulonglong);
+ for (uint i= 0; i < sz/2; i++)
+ {
+ uchar tmp= src[i];
+ src[i]= src[sz-1-i];
+ src[sz-1-i]= tmp;
+ }
+ return uint8korr(src);
+}
+
+// copy-paste:
+static inline double safe_substract(ulonglong a, ulonglong b)
+{
+ return (a > b)? double(a - b) : -double(b - a);
+}
+
+/*
+ GSOC-TODO:
+ This is our replacement for Field::pos_in_interval_val_str
+
+ We take midpoint_val and an interval [min_val, max_val], and return
+ a number between 0.0 and 1.0 which specifies how close midpoint_val is
+ to one of the bounds.
+
+ @param field Field object. We don't care about the field's current value
+ (actually, we overwrite it). We need it for its virtual
+ functions.
+
+ @TODO
+ Instead of copying the pos_in_interval_val_str(), we should do better:
+ if all three passed values have a common prefix, skip it.
+ This will make the returned value more precise.
+
+*/
+
+double pos_in_interval_through_strxfrm(Field *field,
+ uchar *min_val,
+ uchar *max_val,
+ uchar *midpoint_val)
+{
+ // The code below is a copy of logic from Field::pos_in_interval_val_str
+ uchar mp_prefix[sizeof(ulonglong)];
+ uchar minp_prefix[sizeof(ulonglong)];
+ uchar maxp_prefix[sizeof(ulonglong)];
+ ulonglong mp, minp, maxp;
+
+ uint min_len= uint2korr(min_val);
+ uint max_len= uint2korr(max_val);
+ uint midpoint_len= uint2korr(midpoint_val);
+
+ auto cset= field->charset();
+
+ cset->strnxfrm(mp_prefix, sizeof(mp),
+ midpoint_val + HA_KEY_BLOB_LENGTH,
+ midpoint_len);
+ cset->strnxfrm(minp_prefix, sizeof(minp),
+ min_val + HA_KEY_BLOB_LENGTH,
+ min_len);
+ cset->strnxfrm(maxp_prefix, sizeof(maxp),
+ max_val + HA_KEY_BLOB_LENGTH,
+ max_len);
+ mp= char_prefix_to_ulonglong(mp_prefix);
+ minp= char_prefix_to_ulonglong(minp_prefix);
+ maxp= char_prefix_to_ulonglong(maxp_prefix);
+ double n, d;
+ n= safe_substract(mp, minp);
+ if (n < 0)
+ return 0.0;
+ d= safe_substract(maxp, minp);
+ if (d <= 0)
+ return 1.0;
+ return MY_MIN(n/d, 1.0);
+}
+
+
+/*
+ GSOC-TODO:
+ This is how range selectivity function should look like.
+
+ @param field The table field histogram is for. We don't care about the
+ field's current value, we only need its virtual functions to
+ perform various operations
+
+ @param min_endp, max_endp - this specifies the range.
+*/
+double Histogram_json::range_selectivity_new(Field *field, key_range *min_endp,
+ key_range *max_endp)
+{
+ fprintf(stderr, "Histogram_json::range_selectivity_new\n");
+
+
+ /*
+ GSOC-TODO:
+ The code below is NOT what this function have.
+
+ == WHAT THIS CODE DOES ==
+ At the moment it does a linear walk through histogram_bounds and compares
+ min_endp to each of histogram bucket's min and max.
+ ATTENTION: This is a demo of how key_cmp() is used to compare the values.
+
+ When it finds the bucket such that BUCKET_START < min_endp < BUCKET_END,
+ it computes a position of min_endp within the bucket.
+ ATTENTION: calls to pos_in_interval_.... are a demo of how to compute
+ position of a value within a [min,max] range.
+
+ == WHAT THIS CODE SHOULD DO ==
+ * Use binary search to locate the range [MIN_BUCKET; MAX_BUCKET] - the
+ set of buckets that overlaps with the search interval {min_endp, max_endp}.
+
+ * If the search interval covers MIN_BUCKET only partially, compute a
+ position of min_endp within the bucket.
+
+ * The same for max_endp.
+
+ * Compute the final selectivity and return it.
+ */
+ std::string prev_s;
+ bool have_prev_s=false;
+ for (auto &s : histogram_bounds)
+ {
+ if (!have_prev_s)
+ {
+ prev_s = s;
+ have_prev_s= true;
+ continue;
+ }
+
+ // It's a test code, so we only process min_endp.
+ if (min_endp)
+ {
+ const uchar *min_key= min_endp->key;
+ // TODO: also, properly handle SQL NULLs.
+ // in this test patch, we just assume the values are not SQL NULLs.
+ if (field->real_maybe_null())
+ min_key++;
+
+ int res1= field->key_cmp((uchar*)prev_s.data(), min_key);
+ const char *str1="<";
+ if (res1>0) str1=">";
+ if (res1==0) str1="=";
+
+ int res2= field->key_cmp(min_key, (uchar*)s.data());
+ const char *str2="<";
+ if (res2>0) str2=">";
+ if (res2==0) str2="=";
+ fprintf(stderr, "prev_bound %s min_key %s bound\n", str1, str2);
+
+ if (res1<0 && res2 < 0)
+ {
+ double sel;
+ if (field->pos_through_val_str())
+ sel= pos_in_interval_through_strxfrm(field, (uchar*)prev_s.data(),
+ (uchar*)s.data(), (uchar*)min_key);
+ else
+ sel= pos_in_interval_through_val_real(field, (uchar*)prev_s.data(),
+ (uchar*)s.data(), (uchar*)min_key);
+
+ fprintf(stderr, " pos_in_interval=%g\n", sel);
+ }
+
+ prev_s= s;
+ }
+ }
+ fprintf(stderr, "Histogram_json::range_selectivity_new ends\n");
+ return 0.5;
+}
+
void Histogram_json::serialize(Field *field)
{
field->store((char*)values, strlen((char*)values),
@@ -4107,8 +4347,14 @@ double get_column_range_cardinality(Field *field,
max_mp_pos= 1.0;
Histogram_base *hist = col_stats->histogram_;
- if (hist && hist->is_usable(thd))
+ if (hist && hist->is_usable(thd)) {
+ /*
+ GSOC-TODO: for now, we just call range_selectivity_new here.
+ */
+ sel= hist->range_selectivity_new(field, min_endp, max_endp);
+
sel= hist->range_selectivity(min_mp_pos, max_mp_pos);
+ }
else
sel= (max_mp_pos - min_mp_pos);
res= col_non_nulls * sel;
diff --git a/sql/sql_statistics.h b/sql/sql_statistics.h
index 2673b36d050..6c498e17ac6 100644
--- a/sql/sql_statistics.h
+++ b/sql/sql_statistics.h
@@ -149,7 +149,7 @@ bool is_eits_usable(Field* field);
class Histogram_base : public Sql_alloc
{
public:
- virtual bool parse(MEM_ROOT *mem_root, Histogram_type type_arg,
+ virtual bool parse(MEM_ROOT *mem_root, Field *field, Histogram_type type_arg,
const uchar *ptr, uint size)= 0;
virtual void serialize(Field *to_field)= 0;
@@ -173,13 +173,19 @@ class Histogram_base : public Sql_alloc
virtual double point_selectivity(double pos, double avg_selection)=0;
+ virtual double range_selectivity_new(Field *field, key_range *min_endp,
+ key_range *max_endp)
+ {
+ return 1.0;
+ };
+
virtual ~Histogram_base(){}
};
class Histogram_binary : public Histogram_base
{
public:
- bool parse(MEM_ROOT *mem_root, Histogram_type type_arg,
+ bool parse(MEM_ROOT *mem_root, Field *, Histogram_type type_arg,
const uchar *ptr_arg, uint size_arg) override;
void serialize(Field *to_field) override;
@@ -341,11 +347,28 @@ class Histogram_json : public Histogram_base
private:
Histogram_type type;
uint8 size; /* Number of elements in the histogram*/
+
+ /*
+ GSOC-TODO: This is used for storing collected JSON text. Rename it
+ accordingly.
+ */
uchar *values;
- std::vector<std::string> hist_buckets;
+
+ // List of values in string form.
+ /*
+ GSOC-TODO: We don't need to save this. It can be a local variable in
+ parse().
+ Eventually we should get rid of this at all, as we can convert the
+ endpoints and add them to histogram_bounds as soon as we've read them.
+ */
+ std::vector<std::string> hist_buckets_text;
+
+ // Array of histogram bucket endpoints in KeyTupleFormat.
+ std::vector<std::string> histogram_bounds;
public:
- bool parse(MEM_ROOT *mem_root, Histogram_type type_arg, const uchar *ptr, uint size) override;
+ bool parse(MEM_ROOT *mem_root, Field *field, Histogram_type type_arg,
+ const uchar *ptr, uint size) override;
void serialize(Field *field) override;
@@ -364,7 +387,7 @@ class Histogram_json : public Histogram_base
void init_for_collection(MEM_ROOT *mem_root, Histogram_type htype_arg, ulonglong size) override;
- bool is_available() override {return get_width() > 0 && get_values(); }
+ bool is_available() override {return get_width() > 0 /*&& get_values()*/; }
bool is_usable(THD *thd) override
{
@@ -379,6 +402,13 @@ class Histogram_json : public Histogram_base
double range_selectivity(double min_pos, double max_pos) override {return 0.1;}
double point_selectivity(double pos, double avg_selection) override {return 0.5;}
+
+ /*
+ GSOC-TODO: This function should eventually replace both range_selectivity()
+ and point_selectivity(). See its code for more details.
+ */
+ double range_selectivity_new(Field *field, key_range *min_endp,
+ key_range *max_endp) override;
};
class Columns_statistics;
1
0
revision-id: 58d6489885b9459f6c0d71c94ec9f60cac893f2e (mariadb-10.5.11-59-g58d6489885b)
parent(s): c03949f15325c331a943a15465adf74487cad91b
author: Sergei Petrunia
committer: Sergei Petrunia
timestamp: 2021-08-03 19:09:49 +0300
message:
Update test results 2
---
mysql-test/suite/sys_vars/r/sysvars_server_notembedded.result | 10 ++++++++++
1 file changed, 10 insertions(+)
diff --git a/mysql-test/suite/sys_vars/r/sysvars_server_notembedded.result b/mysql-test/suite/sys_vars/r/sysvars_server_notembedded.result
index 3498d5de743..d0012bda4b3 100644
--- a/mysql-test/suite/sys_vars/r/sysvars_server_notembedded.result
+++ b/mysql-test/suite/sys_vars/r/sysvars_server_notembedded.result
@@ -2392,6 +2392,16 @@ NUMERIC_BLOCK_SIZE 1
ENUM_VALUE_LIST NULL
READ_ONLY YES
COMMAND_LINE_ARGUMENT REQUIRED
+VARIABLE_NAME OPTIMIZER_LATERAL_LAZY_REFILL
+VARIABLE_SCOPE SESSION
+VARIABLE_TYPE BIGINT UNSIGNED
+VARIABLE_COMMENT Controls Lazy Lateral Table Refill fix. 0 means disabled, 1 means enabled in the optimizer. Higher values are reserved for future use.
+NUMERIC_MIN_VALUE 0
+NUMERIC_MAX_VALUE 2
+NUMERIC_BLOCK_SIZE 1
+ENUM_VALUE_LIST NULL
+READ_ONLY NO
+COMMAND_LINE_ARGUMENT REQUIRED
VARIABLE_NAME OPTIMIZER_MAX_SEL_ARG_WEIGHT
VARIABLE_SCOPE SESSION
VARIABLE_TYPE BIGINT UNSIGNED
1
0
revision-id: c03949f15325c331a943a15465adf74487cad91b (mariadb-10.5.11-58-gc03949f1532)
parent(s): 3216601d4a56cd6db30cc1a1db629dd73086df4b
author: Sergei Petrunia
committer: Sergei Petrunia
timestamp: 2021-08-03 17:27:16 +0300
message:
Update test results
---
mysql-test/main/mysqld--help.result | 5 +++++
1 file changed, 5 insertions(+)
diff --git a/mysql-test/main/mysqld--help.result b/mysql-test/main/mysqld--help.result
index 7b0ce27ead3..6872adbcfba 100644
--- a/mysql-test/main/mysqld--help.result
+++ b/mysql-test/main/mysqld--help.result
@@ -681,6 +681,10 @@ The following specify which files/extra groups are read (specified before remain
max_connections*5 or max_connections + table_cache*2
(whichever is larger) number of file descriptors
(Automatically configured unless set explicitly)
+ --optimizer-lateral-lazy-refill=#
+ Controls Lazy Lateral Table Refill fix. 0 means disabled,
+ 1 means enabled in the optimizer. Higher values are
+ reserved for future use.
--optimizer-max-sel-arg-weight=#
The maximum weight of the SEL_ARG graph. Set to 0 for no
limit
@@ -1640,6 +1644,7 @@ old-alter-table DEFAULT
old-mode
old-passwords FALSE
old-style-user-limits FALSE
+optimizer-lateral-lazy-refill 0
optimizer-max-sel-arg-weight 32000
optimizer-prune-level 1
optimizer-search-depth 62
1
0
revision-id: 3216601d4a56cd6db30cc1a1db629dd73086df4b (mariadb-10.5.11-57-g3216601d4a5)
parent(s): 767ccf27c70b7fbc746dacfcba3ebe14c0539a86
author: Sergei Petrunia
committer: Sergei Petrunia
timestamp: 2021-08-03 17:10:19 +0300
message:
MDEV-26301: more test coverage
---
mysql-test/main/derived_split_innodb.result | 79 ++++++++++++++++++++++++++++-
mysql-test/main/derived_split_innodb.test | 46 ++++++++++++++++-
2 files changed, 123 insertions(+), 2 deletions(-)
diff --git a/mysql-test/main/derived_split_innodb.result b/mysql-test/main/derived_split_innodb.result
index 063a29d2366..0392b806c7b 100644
--- a/mysql-test/main/derived_split_innodb.result
+++ b/mysql-test/main/derived_split_innodb.result
@@ -355,6 +355,83 @@ json_detailed(json_extract(trace, '$**.split_plan_choice'))
"split_chosen": true
}
]
+create table t21 (pk int primary key);
+insert into t21 values (1),(2),(3);
+create table t22 (pk int primary key);
+insert into t22 values (1),(2),(3);
+explain
+select * from
+t21, t22,
+(
+(t1 left join t2 on t2.a=t1.b)
+left join t3 on t3.a=t1.b
+) left join (select grp_id, count(*)
+from t10 left join t11 on t11.col1=t10.col1
+group by grp_id) T on T.grp_id=t1.b
+where
+t21.pk=1 and t22.pk=2;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t21 const PRIMARY PRIMARY 4 const 1 Using index
+1 PRIMARY t22 const PRIMARY PRIMARY 4 const 1 Using index
+1 PRIMARY t1 ALL NULL NULL NULL NULL 5
+1 PRIMARY t2 ref a a 5 test.t1.b 2 Using where
+1 PRIMARY t3 ref a a 5 test.t1.b 3 Using where
+1 PRIMARY <derived2> ref key0 key0 5 test.t1.b 10 Using where
+2 LATERAL DERIVED t10 ref grp_id grp_id 5 test.t1.b 100
+2 LATERAL DERIVED t11 ALL NULL NULL NULL NULL 10 Using where; Using join buffer (flat, BNL join)
+select
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+information_schema.optimizer_trace;
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+[
+
+ {
+ "unsplit_cost": 253440.0075,
+ "split_cost": 2535.968504,
+ "record_count_for_split": 30,
+ "join_prefix_fanout_for_split": 5,
+ "split_chosen": true
+ }
+]
+explain
+select * from
+t21,
+(
+(t1 left join t2 on t2.a=t1.b)
+left join t3 on t3.a=t1.b
+) left join (select grp_id, count(*)
+from
+t22 join t10 left join t11 on t11.col1=t10.col1
+where
+t22.pk=1
+group by grp_id) T on T.grp_id=t1.b
+where
+t21.pk=1;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t21 const PRIMARY PRIMARY 4 const 1 Using index
+1 PRIMARY t1 ALL NULL NULL NULL NULL 5
+1 PRIMARY t2 ref a a 5 test.t1.b 2 Using where
+1 PRIMARY t3 ref a a 5 test.t1.b 3 Using where
+1 PRIMARY <derived2> ref key0 key0 5 test.t1.b 10 Using where
+2 LATERAL DERIVED t22 const PRIMARY PRIMARY 4 const 1 Using index
+2 LATERAL DERIVED t10 ref grp_id grp_id 5 test.t1.b 100
+2 LATERAL DERIVED t11 ALL NULL NULL NULL NULL 10 Using where; Using join buffer (flat, BNL join)
+select
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+information_schema.optimizer_trace;
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+[
+
+ {
+ "unsplit_cost": 253440.0075,
+ "split_cost": 2535.968504,
+ "record_count_for_split": 30,
+ "join_prefix_fanout_for_split": 5,
+ "split_chosen": true
+ }
+]
set optimizer_trace=0;
set @@optimizer_lateral_lazy_refill=default;
-drop table t1,t2,t3, t10, t11;
+drop table t1,t2,t3, t10, t11, t21, t22;
diff --git a/mysql-test/main/derived_split_innodb.test b/mysql-test/main/derived_split_innodb.test
index 71a734b09df..98a5ca354ae 100644
--- a/mysql-test/main/derived_split_innodb.test
+++ b/mysql-test/main/derived_split_innodb.test
@@ -277,6 +277,50 @@ select
from
information_schema.optimizer_trace;
+create table t21 (pk int primary key);
+insert into t21 values (1),(2),(3);
+
+create table t22 (pk int primary key);
+insert into t22 values (1),(2),(3);
+
+# Same as above but throw in a couple of const tables.
+explain
+select * from
+ t21, t22,
+ (
+ (t1 left join t2 on t2.a=t1.b)
+ left join t3 on t3.a=t1.b
+ ) left join (select grp_id, count(*)
+ from t10 left join t11 on t11.col1=t10.col1
+ group by grp_id) T on T.grp_id=t1.b
+where
+ t21.pk=1 and t22.pk=2;
+
+select
+ json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+ information_schema.optimizer_trace;
+
+explain
+select * from
+ t21,
+ (
+ (t1 left join t2 on t2.a=t1.b)
+ left join t3 on t3.a=t1.b
+ ) left join (select grp_id, count(*)
+ from
+ t22 join t10 left join t11 on t11.col1=t10.col1
+ where
+ t22.pk=1
+ group by grp_id) T on T.grp_id=t1.b
+where
+ t21.pk=1;
+
+select
+ json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+ information_schema.optimizer_trace;
+
set optimizer_trace=0;
set @@optimizer_lateral_lazy_refill=default;
-drop table t1,t2,t3, t10, t11;
+drop table t1,t2,t3, t10, t11, t21, t22;
1
0
[Commits] 767ccf27c70: MDEV-26301: LATERAL DERIVED refills the temp. table too many times
by psergey 03 Aug '21
by psergey 03 Aug '21
03 Aug '21
revision-id: 767ccf27c70b7fbc746dacfcba3ebe14c0539a86 (mariadb-10.5.11-56-g767ccf27c70)
parent(s): 398387f0e638ee027406e72e3460fb1bf755b31d
author: Sergei Petrunia
committer: Sergei Petrunia
timestamp: 2021-08-03 16:54:05 +0300
message:
MDEV-26301: LATERAL DERIVED refills the temp. table too many times
Add support of the fix in the optimizer part.
Also added @@optimizer_lateral_lazy_refill to control this.
---
mysql-test/main/derived_split_innodb.result | 117 ++++++++++++++++++++++++++++
mysql-test/main/derived_split_innodb.test | 87 +++++++++++++++++++++
mysql-test/main/opt_trace.result | 2 +-
sql/opt_split.cc | 116 ++++++++++++++++++++++++++-
sql/sql_class.h | 1 +
sql/sql_select.cc | 2 +-
sql/sql_select.h | 4 +-
sql/sys_vars.cc | 8 ++
8 files changed, 331 insertions(+), 6 deletions(-)
diff --git a/mysql-test/main/derived_split_innodb.result b/mysql-test/main/derived_split_innodb.result
index 9edf9a1f2ae..063a29d2366 100644
--- a/mysql-test/main/derived_split_innodb.result
+++ b/mysql-test/main/derived_split_innodb.result
@@ -241,3 +241,120 @@ set optimizer_switch='split_materialized=default';
set use_stat_tables=default;
set optimizer_use_condition_selectivity=default;
# End of 10.3 tests
+#
+# MDEV-26301: LATERAL DERIVED refills the temp. table too many times
+#
+create table t1(a int, b int);
+insert into t1 select seq,seq from seq_1_to_5;
+create table t2(a int, b int, key(a));
+insert into t2
+select A.seq,B.seq from seq_1_to_25 A, seq_1_to_2 B;
+create table t3(a int, b int, key(a));
+insert into t3
+select A.seq,B.seq from seq_1_to_5 A, seq_1_to_3 B;
+analyze table t1,t2,t3 persistent for all;
+Table Op Msg_type Msg_text
+test.t1 analyze status Engine-independent statistics collected
+test.t1 analyze status OK
+test.t2 analyze status Engine-independent statistics collected
+test.t2 analyze status Table is already up to date
+test.t3 analyze status Engine-independent statistics collected
+test.t3 analyze status Table is already up to date
+explain
+select * from
+(t1 left join t2 on t2.a=t1.b) left join t3 on t3.a=t1.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 5
+1 SIMPLE t2 ref a a 5 test.t1.b 2 Using where
+1 SIMPLE t3 ref a a 5 test.t1.b 3 Using where
+create table t10 (
+grp_id int,
+col1 int,
+key(grp_id)
+);
+insert into t10
+select
+A.seq,
+B.seq
+from
+seq_1_to_100 A,
+seq_1_to_100 B;
+create table t11 (
+col1 int,
+col2 int
+);
+insert into t11
+select A.seq, A.seq from seq_1_to_10 A;
+analyze table t10,t11 persistent for all;
+Table Op Msg_type Msg_text
+test.t10 analyze status Engine-independent statistics collected
+test.t10 analyze status Table is already up to date
+test.t11 analyze status Engine-independent statistics collected
+test.t11 analyze status OK
+set optimizer_trace=1;
+explain
+select * from
+(
+(t1 left join t2 on t2.a=t1.b)
+left join t3 on t3.a=t1.b
+) left join (select grp_id, count(*)
+from t10 left join t11 on t11.col1=t10.col1
+group by grp_id) T on T.grp_id=t1.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 5
+1 PRIMARY t2 ref a a 5 test.t1.b 2 Using where
+1 PRIMARY t3 ref a a 5 test.t1.b 3 Using where
+1 PRIMARY <derived2> ref key0 key0 5 test.t1.b 10 Using where
+2 LATERAL DERIVED t10 ref grp_id grp_id 5 test.t1.b 100
+2 LATERAL DERIVED t11 ALL NULL NULL NULL NULL 10 Using where; Using join buffer (flat, BNL join)
+select
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+information_schema.optimizer_trace;
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+[
+
+ {
+ "unsplit_cost": 253440.0075,
+ "split_cost": 2535.968504,
+ "record_count_for_split": 30,
+ "split_chosen": true
+ }
+]
+select @@optimizer_lateral_lazy_refill;
+@@optimizer_lateral_lazy_refill
+0
+set @@optimizer_lateral_lazy_refill=1;
+explain
+select * from
+(
+(t1 left join t2 on t2.a=t1.b)
+left join t3 on t3.a=t1.b
+) left join (select grp_id, count(*)
+from t10 left join t11 on t11.col1=t10.col1
+group by grp_id) T on T.grp_id=t1.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 5
+1 PRIMARY t2 ref a a 5 test.t1.b 2 Using where
+1 PRIMARY t3 ref a a 5 test.t1.b 3 Using where
+1 PRIMARY <derived2> ref key0 key0 5 test.t1.b 10 Using where
+2 LATERAL DERIVED t10 ref grp_id grp_id 5 test.t1.b 100
+2 LATERAL DERIVED t11 ALL NULL NULL NULL NULL 10 Using where; Using join buffer (flat, BNL join)
+select
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+information_schema.optimizer_trace;
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+[
+
+ {
+ "unsplit_cost": 253440.0075,
+ "split_cost": 2535.968504,
+ "record_count_for_split": 30,
+ "join_prefix_fanout_for_split": 5,
+ "split_chosen": true
+ }
+]
+set optimizer_trace=0;
+set @@optimizer_lateral_lazy_refill=default;
+drop table t1,t2,t3, t10, t11;
diff --git a/mysql-test/main/derived_split_innodb.test b/mysql-test/main/derived_split_innodb.test
index bee9ef497b6..71a734b09df 100644
--- a/mysql-test/main/derived_split_innodb.test
+++ b/mysql-test/main/derived_split_innodb.test
@@ -193,3 +193,90 @@ set use_stat_tables=default;
set optimizer_use_condition_selectivity=default;
--echo # End of 10.3 tests
+
+--echo #
+--echo # MDEV-26301: LATERAL DERIVED refills the temp. table too many times
+--echo #
+
+# 5 values
+create table t1(a int, b int);
+insert into t1 select seq,seq from seq_1_to_5;
+
+# 5 value groups of size 2 each
+create table t2(a int, b int, key(a));
+insert into t2
+select A.seq,B.seq from seq_1_to_25 A, seq_1_to_2 B;
+
+# 5 value groups of size 3 each
+create table t3(a int, b int, key(a));
+insert into t3
+select A.seq,B.seq from seq_1_to_5 A, seq_1_to_3 B;
+
+analyze table t1,t2,t3 persistent for all;
+
+explain
+select * from
+ (t1 left join t2 on t2.a=t1.b) left join t3 on t3.a=t1.b;
+
+# Now, create tables for Groups.
+
+create table t10 (
+ grp_id int,
+ col1 int,
+ key(grp_id)
+);
+
+# 100 groups of 100 values each
+insert into t10
+select
+ A.seq,
+ B.seq
+from
+ seq_1_to_100 A,
+ seq_1_to_100 B;
+
+# and X10 multiplier
+
+create table t11 (
+ col1 int,
+ col2 int
+);
+insert into t11
+select A.seq, A.seq from seq_1_to_10 A;
+
+
+analyze table t10,t11 persistent for all;
+set optimizer_trace=1;
+
+explain
+select * from
+ (
+ (t1 left join t2 on t2.a=t1.b)
+ left join t3 on t3.a=t1.b
+ ) left join (select grp_id, count(*)
+ from t10 left join t11 on t11.col1=t10.col1
+ group by grp_id) T on T.grp_id=t1.b;
+select
+ json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+ information_schema.optimizer_trace;
+
+select @@optimizer_lateral_lazy_refill;
+set @@optimizer_lateral_lazy_refill=1;
+
+explain
+select * from
+ (
+ (t1 left join t2 on t2.a=t1.b)
+ left join t3 on t3.a=t1.b
+ ) left join (select grp_id, count(*)
+ from t10 left join t11 on t11.col1=t10.col1
+ group by grp_id) T on T.grp_id=t1.b;
+select
+ json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+ information_schema.optimizer_trace;
+
+set optimizer_trace=0;
+set @@optimizer_lateral_lazy_refill=default;
+drop table t1,t2,t3, t10, t11;
diff --git a/mysql-test/main/opt_trace.result b/mysql-test/main/opt_trace.result
index d4ba8eccb91..97d3b48ee85 100644
--- a/mysql-test/main/opt_trace.result
+++ b/mysql-test/main/opt_trace.result
@@ -8954,9 +8954,9 @@ json_detailed(json_extract(trace, '$**.lateral_derived_choice'))
],
"split_plan_choice":
{
+ "unsplit_cost": 25.72361682,
"split_cost": 2.488945919,
"record_count_for_split": 4,
- "unsplit_cost": 25.72361682,
"split_chosen": true
},
"chosen_lateral_derived":
diff --git a/sql/opt_split.cc b/sql/opt_split.cc
index d482c2de2a4..a569c323792 100644
--- a/sql/opt_split.cc
+++ b/sql/opt_split.cc
@@ -876,6 +876,70 @@ void reset_validity_vars_for_keyuses(KEYUSE_EXT *key_keyuse_ext_start,
}
+
+/*
+ given a table bitmap, find the prefix of positions array that covers the
+ tables in the bitmap.
+*/
+
+uint get_prefix_size(const POSITION *positions, uint max_position, table_map map)
+{
+ map= map & ~PSEUDO_TABLE_BITS; // remove OUTER_REF_TABLE_BIT
+ table_map covered= 0;
+ uint i;
+
+ for (i=0; i < max_position; i++)
+ {
+ covered |= positions[i].table->table->map;
+ if (!(map & ~covered))
+ break;
+ }
+ return i;
+}
+
+
+/*
+ Walk through the KEYUSE_EXT objects for given {table,key,key_part} and
+ find the shortest prefix of positions array that we have a keyuse object for.
+*/
+
+uint get_min_prefix_for_key_part(const POSITION *positions, uint max_prefix_size,
+ KEYUSE_EXT *keyuse)
+{
+ TABLE *table= keyuse->table;
+ uint key= keyuse->key;
+ uint keypart= keyuse->keypart;
+ uint prefix_size= max_prefix_size;
+
+ while (keyuse->table == table && keyuse->key == key &&
+ keyuse->keypart == keypart)
+ {
+ uint cur_size= get_prefix_size(positions, max_prefix_size,
+ keyuse->needed_in_prefix);
+ if (cur_size < prefix_size)
+ prefix_size= cur_size;
+ keyuse++;
+ }
+ return prefix_size;
+}
+
+
+/*
+ Get fanout of of a join prefix
+*/
+double get_join_prefix_fanout(const POSITION *positions, uint prefix_size)
+{
+ double fanout = 1.0;
+ for (uint i=0; i <= prefix_size; i++)
+ {
+ if (positions[i].records_read > 1e-30)
+ fanout *= positions[i].records_read;
+ if (positions[i].cond_selectivity > 1e-30)
+ fanout *= positions[i].cond_selectivity;
+ }
+ return fanout;
+}
+
/**
@brief
Choose the best splitting to extend the evaluated partial join
@@ -906,7 +970,9 @@ void reset_validity_vars_for_keyuses(KEYUSE_EXT *key_keyuse_ext_start,
if the plan has been chosen, NULL - otherwise.
*/
-SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
+SplM_plan_info * JOIN_TAB::choose_best_splitting(const POSITION *join_prefix,
+ uint top_prefix_size,
+ double record_count,
table_map remaining_tables)
{
SplM_opt_info *spl_opt_info= table->spl_opt_info;
@@ -922,6 +988,7 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
SplM_plan_info *spl_plan= 0;
uint best_key= 0;
uint best_key_parts= 0;
+ uint best_min_prefix_size;
Json_writer_object spl_trace(thd, "lateral_derived_choice");
Json_writer_array trace_indexes(thd, "indexes_for_splitting");
@@ -942,6 +1009,7 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
uint key= keyuse_ext->key;
KEYUSE_EXT *key_keyuse_ext_start= keyuse_ext;
key_part_map found_parts= 0;
+ uint prefix_len= 0;
do
{
if (keyuse_ext->needed_in_prefix & remaining_tables)
@@ -951,11 +1019,31 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
}
if (!(keyuse_ext->keypart_map & found_parts))
{
+ /*
+ 1. found_parts is empty and this is the first key part we've found
+ 2. or, we are looking at the first keyuse object for this keypart,
+ and found_parts has a bit set for the previous key part.
+ */
if ((!found_parts && !keyuse_ext->keypart) ||
(found_parts && ((keyuse_ext->keypart_map >> 1) & found_parts)))
+ {
+ if (thd->variables.optimizer_lateral_lazy_refill > 0)
+ {
+ uint min_for_kp= get_min_prefix_for_key_part(join_prefix,
+ top_prefix_size,
+ keyuse_ext);
+ // The prefix length needed for {kp1, kp2, ...} is max of the
+ // needed prefix length for each key part.
+ if (min_for_kp > prefix_len)
+ prefix_len= min_for_kp;
+ }
+
found_parts|= keyuse_ext->keypart_map;
+ }
else
{
+ // This is a new key part but it doesn't form a continuous
+ // index prefix. Skip all KEYUSEs for this index.
do
{
keyuse_ext++;
@@ -981,6 +1069,11 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
best_key_parts= keyuse_ext->keypart + 1;
best_rec_per_key= rec_per_key;
best_key_keyuse_ext_start= key_keyuse_ext_start;
+ if (thd->variables.optimizer_lateral_lazy_refill > 0)
+ {
+ best_min_prefix_size= prefix_len;
+ trace.add("min_prefix_len", (longlong)prefix_len);
+ }
}
keyuse_ext++;
}
@@ -1069,10 +1162,21 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
if (spl_plan)
{
Json_writer_object choice(thd, "split_plan_choice");
+ choice.add("unsplit_cost", spl_opt_info->unsplit_cost);
+
choice.add("split_cost", spl_plan->cost);
choice.add("record_count_for_split", record_count);
- choice.add("unsplit_cost", spl_opt_info->unsplit_cost);
- if(record_count * spl_plan->cost < spl_opt_info->unsplit_cost - 0.01)
+
+ // psergey-todo: best_min_prefix_size allows us to compute a more tight
+ // bound than record_count.
+ double fanout= record_count;
+ if (thd->variables.optimizer_lateral_lazy_refill > 0)
+ {
+ fanout= get_join_prefix_fanout(join_prefix, best_min_prefix_size);
+ choice.add("join_prefix_fanout_for_split", fanout);
+ }
+
+ if(fanout * spl_plan->cost < spl_opt_info->unsplit_cost - 0.01)
{
/*
The best plan that employs splitting is cheaper than
@@ -1134,12 +1238,14 @@ bool JOIN::inject_best_splitting_cond(table_map remaining_tables)
List<Item> *inj_cond_list= &spl_opt_info->inj_cond_list;
List_iterator<KEY_FIELD> li(spl_opt_info->added_key_fields);
KEY_FIELD *added_key_field;
+ table_map needed_tables= 0;
while ((added_key_field= li++))
{
if (remaining_tables & added_key_field->val->used_tables())
continue;
if (inj_cond_list->push_back(added_key_field->cond, thd->mem_root))
return true;
+ needed_tables |= added_key_field->val->used_tables();
}
DBUG_ASSERT(inj_cond_list->elements);
switch (inj_cond_list->elements) {
@@ -1156,6 +1262,10 @@ bool JOIN::inject_best_splitting_cond(table_map remaining_tables)
if (inject_cond_into_where(inj_cond))
return true;
+ // psergey-todo: walk the join tabs until we are satisfying needed_tables...
+ // and inject the check at that point.
+ // Other solution is to just add a cache...
+
select_lex->uncacheable|= UNCACHEABLE_DEPENDENT_INJECTED;
st_select_lex_unit *unit= select_lex->master_unit();
unit->uncacheable|= UNCACHEABLE_DEPENDENT_INJECTED;
diff --git a/sql/sql_class.h b/sql/sql_class.h
index 62ce5c8a2d2..8964a8aa4f7 100644
--- a/sql/sql_class.h
+++ b/sql/sql_class.h
@@ -689,6 +689,7 @@ typedef struct system_variables
ulong optimizer_search_depth;
ulong optimizer_selectivity_sampling_limit;
ulong optimizer_use_condition_selectivity;
+ ulong optimizer_lateral_lazy_refill;
ulong use_stat_tables;
double sample_percentage;
ulong histogram_size;
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 7057ed1b5e1..5b901df2e54 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -7455,7 +7455,7 @@ best_access_path(JOIN *join,
loose_scan_opt.init(join, s, remaining_tables);
if (s->table->is_splittable())
- spl_plan= s->choose_best_splitting(record_count, remaining_tables);
+ spl_plan= s->choose_best_splitting(join_positions, idx, record_count, remaining_tables);
Json_writer_array trace_paths(thd, "considered_access_paths");
if (s->keyuse)
diff --git a/sql/sql_select.h b/sql/sql_select.h
index 29e42ff8ef8..7ffab774248 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -682,7 +682,9 @@ typedef struct st_join_table {
void partial_cleanup();
void add_keyuses_for_splitting();
- SplM_plan_info *choose_best_splitting(double record_count,
+ SplM_plan_info *choose_best_splitting(const POSITION *join_prefix,
+ uint top_prefix_size,
+ double record_count,
table_map remaining_tables);
bool fix_splitting(SplM_plan_info *spl_plan, table_map remaining_tables,
bool is_const_table);
diff --git a/sql/sys_vars.cc b/sql/sys_vars.cc
index a8e4ff2dded..e87d371453d 100644
--- a/sql/sys_vars.cc
+++ b/sql/sys_vars.cc
@@ -2672,6 +2672,14 @@ static Sys_var_ulong Sys_optimizer_use_condition_selectivity(
SESSION_VAR(optimizer_use_condition_selectivity), CMD_LINE(REQUIRED_ARG),
VALID_RANGE(1, 5), DEFAULT(4), BLOCK_SIZE(1));
+static Sys_var_ulong Sys_optimizer_lateral_lazy_refill(
+ "optimizer_lateral_lazy_refill",
+ "Controls Lazy Lateral Table Refill fix. 0 means disabled, "
+ "1 means enabled in the optimizer. Higher values are reserved "
+ "for future use.",
+ SESSION_VAR(optimizer_lateral_lazy_refill), CMD_LINE(REQUIRED_ARG),
+ VALID_RANGE(0, 2), DEFAULT(0), BLOCK_SIZE(1));
+
static Sys_var_ulong Sys_optimizer_search_depth(
"optimizer_search_depth",
"Maximum depth of search performed by the query optimizer. Values "
1
0
[Commits] 34c7b851360: MDEV-26301: LATERAL DERIVED refills the temp. table too many times
by psergey 03 Aug '21
by psergey 03 Aug '21
03 Aug '21
revision-id: 34c7b851360fe7f12ebadfd743d99738aad5c8f3 (mariadb-10.5.11-56-g34c7b851360)
parent(s): 398387f0e638ee027406e72e3460fb1bf755b31d
author: Sergei Petrunia
committer: Sergei Petrunia
timestamp: 2021-08-03 16:51:59 +0300
message:
MDEV-26301: LATERAL DERIVED refills the temp. table too many times
Add support of the fix in the optimizer part.
Also added @@optimizer_lateral_lazy_refill to control this.
---
mysql-test/main/derived_split_innodb.result | 116 ++++++++++++++++++++++++++++
mysql-test/main/derived_split_innodb.test | 86 +++++++++++++++++++++
mysql-test/main/opt_trace.result | 2 +-
sql/opt_split.cc | 116 +++++++++++++++++++++++++++-
sql/sql_class.h | 1 +
sql/sql_select.cc | 2 +-
sql/sql_select.h | 4 +-
sql/sys_vars.cc | 8 ++
8 files changed, 329 insertions(+), 6 deletions(-)
diff --git a/mysql-test/main/derived_split_innodb.result b/mysql-test/main/derived_split_innodb.result
index 9edf9a1f2ae..9847c159d3c 100644
--- a/mysql-test/main/derived_split_innodb.result
+++ b/mysql-test/main/derived_split_innodb.result
@@ -241,3 +241,119 @@ set optimizer_switch='split_materialized=default';
set use_stat_tables=default;
set optimizer_use_condition_selectivity=default;
# End of 10.3 tests
+#
+# MDEV-26301: LATERAL DERIVED refills the temp. table too many times
+#
+create table t1(a int, b int);
+insert into t1 select seq,seq from seq_1_to_5;
+create table t2(a int, b int, key(a));
+insert into t2
+select A.seq,B.seq from seq_1_to_25 A, seq_1_to_2 B;
+create table t3(a int, b int, key(a));
+insert into t3
+select A.seq,B.seq from seq_1_to_5 A, seq_1_to_3 B;
+analyze table t1,t2,t3 persistent for all;
+Table Op Msg_type Msg_text
+test.t1 analyze status Engine-independent statistics collected
+test.t1 analyze status OK
+test.t2 analyze status Engine-independent statistics collected
+test.t2 analyze status Table is already up to date
+test.t3 analyze status Engine-independent statistics collected
+test.t3 analyze status Table is already up to date
+explain
+select * from
+(t1 left join t2 on t2.a=t1.b) left join t3 on t3.a=t1.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 5
+1 SIMPLE t2 ref a a 5 test.t1.b 2 Using where
+1 SIMPLE t3 ref a a 5 test.t1.b 3 Using where
+create table t10 (
+grp_id int,
+col1 int,
+key(grp_id)
+);
+insert into t10
+select
+A.seq,
+B.seq
+from
+seq_1_to_100 A,
+seq_1_to_100 B;
+create table t11 (
+col1 int,
+col2 int
+);
+insert into t11
+select A.seq, A.seq from seq_1_to_10 A;
+analyze table t10,t11 persistent for all;
+Table Op Msg_type Msg_text
+test.t10 analyze status Engine-independent statistics collected
+test.t10 analyze status Table is already up to date
+test.t11 analyze status Engine-independent statistics collected
+test.t11 analyze status OK
+set optimizer_trace=1;
+explain
+select * from
+(
+(t1 left join t2 on t2.a=t1.b)
+left join t3 on t3.a=t1.b
+) left join (select grp_id, count(*)
+from t10 left join t11 on t11.col1=t10.col1
+group by grp_id) T on T.grp_id=t1.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 5
+1 PRIMARY t2 ref a a 5 test.t1.b 2 Using where
+1 PRIMARY t3 ref a a 5 test.t1.b 3 Using where
+1 PRIMARY <derived2> ref key0 key0 5 test.t1.b 10 Using where
+2 LATERAL DERIVED t10 ref grp_id grp_id 5 test.t1.b 100
+2 LATERAL DERIVED t11 ALL NULL NULL NULL NULL 10 Using where; Using join buffer (flat, BNL join)
+select
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+information_schema.optimizer_trace;
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+[
+
+ {
+ "unsplit_cost": 253440.0075,
+ "split_cost": 2535.968504,
+ "record_count_for_split": 30,
+ "split_chosen": true
+ }
+]
+select @@optimizer_lateral_lazy_refill;
+@@optimizer_lateral_lazy_refill
+0
+set @@optimizer_lateral_lazy_refill=1;
+explain
+select * from
+(
+(t1 left join t2 on t2.a=t1.b)
+left join t3 on t3.a=t1.b
+) left join (select grp_id, count(*)
+from t10 left join t11 on t11.col1=t10.col1
+group by grp_id) T on T.grp_id=t1.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 5
+1 PRIMARY t2 ref a a 5 test.t1.b 2 Using where
+1 PRIMARY t3 ref a a 5 test.t1.b 3 Using where
+1 PRIMARY <derived2> ref key0 key0 5 test.t1.b 10 Using where
+2 LATERAL DERIVED t10 ref grp_id grp_id 5 test.t1.b 100
+2 LATERAL DERIVED t11 ALL NULL NULL NULL NULL 10 Using where; Using join buffer (flat, BNL join)
+select
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+information_schema.optimizer_trace;
+json_detailed(json_extract(trace, '$**.split_plan_choice'))
+[
+
+ {
+ "unsplit_cost": 253440.0075,
+ "split_cost": 2535.968504,
+ "record_count_for_split": 30,
+ "join_prefix_fanout_for_split": 5,
+ "split_chosen": true
+ }
+]
+set @@optimizer_lateral_lazy_refill=default;
+drop table t1,t2,t3, t10, t11;
diff --git a/mysql-test/main/derived_split_innodb.test b/mysql-test/main/derived_split_innodb.test
index bee9ef497b6..9c425cc1885 100644
--- a/mysql-test/main/derived_split_innodb.test
+++ b/mysql-test/main/derived_split_innodb.test
@@ -193,3 +193,89 @@ set use_stat_tables=default;
set optimizer_use_condition_selectivity=default;
--echo # End of 10.3 tests
+
+--echo #
+--echo # MDEV-26301: LATERAL DERIVED refills the temp. table too many times
+--echo #
+
+# 5 values
+create table t1(a int, b int);
+insert into t1 select seq,seq from seq_1_to_5;
+
+# 5 value groups of size 2 each
+create table t2(a int, b int, key(a));
+insert into t2
+select A.seq,B.seq from seq_1_to_25 A, seq_1_to_2 B;
+
+# 5 value groups of size 3 each
+create table t3(a int, b int, key(a));
+insert into t3
+select A.seq,B.seq from seq_1_to_5 A, seq_1_to_3 B;
+
+analyze table t1,t2,t3 persistent for all;
+
+explain
+select * from
+ (t1 left join t2 on t2.a=t1.b) left join t3 on t3.a=t1.b;
+
+# Now, create tables for Groups.
+
+create table t10 (
+ grp_id int,
+ col1 int,
+ key(grp_id)
+);
+
+# 100 groups of 100 values each
+insert into t10
+select
+ A.seq,
+ B.seq
+from
+ seq_1_to_100 A,
+ seq_1_to_100 B;
+
+# and X10 multiplier
+
+create table t11 (
+ col1 int,
+ col2 int
+);
+insert into t11
+select A.seq, A.seq from seq_1_to_10 A;
+
+
+analyze table t10,t11 persistent for all;
+set optimizer_trace=1;
+
+explain
+select * from
+ (
+ (t1 left join t2 on t2.a=t1.b)
+ left join t3 on t3.a=t1.b
+ ) left join (select grp_id, count(*)
+ from t10 left join t11 on t11.col1=t10.col1
+ group by grp_id) T on T.grp_id=t1.b;
+select
+ json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+ information_schema.optimizer_trace;
+
+select @@optimizer_lateral_lazy_refill;
+set @@optimizer_lateral_lazy_refill=1;
+
+explain
+select * from
+ (
+ (t1 left join t2 on t2.a=t1.b)
+ left join t3 on t3.a=t1.b
+ ) left join (select grp_id, count(*)
+ from t10 left join t11 on t11.col1=t10.col1
+ group by grp_id) T on T.grp_id=t1.b;
+select
+ json_detailed(json_extract(trace, '$**.split_plan_choice'))
+from
+ information_schema.optimizer_trace;
+
+set @@optimizer_lateral_lazy_refill=default;
+drop table t1,t2,t3, t10, t11;
diff --git a/mysql-test/main/opt_trace.result b/mysql-test/main/opt_trace.result
index d4ba8eccb91..97d3b48ee85 100644
--- a/mysql-test/main/opt_trace.result
+++ b/mysql-test/main/opt_trace.result
@@ -8954,9 +8954,9 @@ json_detailed(json_extract(trace, '$**.lateral_derived_choice'))
],
"split_plan_choice":
{
+ "unsplit_cost": 25.72361682,
"split_cost": 2.488945919,
"record_count_for_split": 4,
- "unsplit_cost": 25.72361682,
"split_chosen": true
},
"chosen_lateral_derived":
diff --git a/sql/opt_split.cc b/sql/opt_split.cc
index d482c2de2a4..a569c323792 100644
--- a/sql/opt_split.cc
+++ b/sql/opt_split.cc
@@ -876,6 +876,70 @@ void reset_validity_vars_for_keyuses(KEYUSE_EXT *key_keyuse_ext_start,
}
+
+/*
+ given a table bitmap, find the prefix of positions array that covers the
+ tables in the bitmap.
+*/
+
+uint get_prefix_size(const POSITION *positions, uint max_position, table_map map)
+{
+ map= map & ~PSEUDO_TABLE_BITS; // remove OUTER_REF_TABLE_BIT
+ table_map covered= 0;
+ uint i;
+
+ for (i=0; i < max_position; i++)
+ {
+ covered |= positions[i].table->table->map;
+ if (!(map & ~covered))
+ break;
+ }
+ return i;
+}
+
+
+/*
+ Walk through the KEYUSE_EXT objects for given {table,key,key_part} and
+ find the shortest prefix of positions array that we have a keyuse object for.
+*/
+
+uint get_min_prefix_for_key_part(const POSITION *positions, uint max_prefix_size,
+ KEYUSE_EXT *keyuse)
+{
+ TABLE *table= keyuse->table;
+ uint key= keyuse->key;
+ uint keypart= keyuse->keypart;
+ uint prefix_size= max_prefix_size;
+
+ while (keyuse->table == table && keyuse->key == key &&
+ keyuse->keypart == keypart)
+ {
+ uint cur_size= get_prefix_size(positions, max_prefix_size,
+ keyuse->needed_in_prefix);
+ if (cur_size < prefix_size)
+ prefix_size= cur_size;
+ keyuse++;
+ }
+ return prefix_size;
+}
+
+
+/*
+ Get fanout of of a join prefix
+*/
+double get_join_prefix_fanout(const POSITION *positions, uint prefix_size)
+{
+ double fanout = 1.0;
+ for (uint i=0; i <= prefix_size; i++)
+ {
+ if (positions[i].records_read > 1e-30)
+ fanout *= positions[i].records_read;
+ if (positions[i].cond_selectivity > 1e-30)
+ fanout *= positions[i].cond_selectivity;
+ }
+ return fanout;
+}
+
/**
@brief
Choose the best splitting to extend the evaluated partial join
@@ -906,7 +970,9 @@ void reset_validity_vars_for_keyuses(KEYUSE_EXT *key_keyuse_ext_start,
if the plan has been chosen, NULL - otherwise.
*/
-SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
+SplM_plan_info * JOIN_TAB::choose_best_splitting(const POSITION *join_prefix,
+ uint top_prefix_size,
+ double record_count,
table_map remaining_tables)
{
SplM_opt_info *spl_opt_info= table->spl_opt_info;
@@ -922,6 +988,7 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
SplM_plan_info *spl_plan= 0;
uint best_key= 0;
uint best_key_parts= 0;
+ uint best_min_prefix_size;
Json_writer_object spl_trace(thd, "lateral_derived_choice");
Json_writer_array trace_indexes(thd, "indexes_for_splitting");
@@ -942,6 +1009,7 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
uint key= keyuse_ext->key;
KEYUSE_EXT *key_keyuse_ext_start= keyuse_ext;
key_part_map found_parts= 0;
+ uint prefix_len= 0;
do
{
if (keyuse_ext->needed_in_prefix & remaining_tables)
@@ -951,11 +1019,31 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
}
if (!(keyuse_ext->keypart_map & found_parts))
{
+ /*
+ 1. found_parts is empty and this is the first key part we've found
+ 2. or, we are looking at the first keyuse object for this keypart,
+ and found_parts has a bit set for the previous key part.
+ */
if ((!found_parts && !keyuse_ext->keypart) ||
(found_parts && ((keyuse_ext->keypart_map >> 1) & found_parts)))
+ {
+ if (thd->variables.optimizer_lateral_lazy_refill > 0)
+ {
+ uint min_for_kp= get_min_prefix_for_key_part(join_prefix,
+ top_prefix_size,
+ keyuse_ext);
+ // The prefix length needed for {kp1, kp2, ...} is max of the
+ // needed prefix length for each key part.
+ if (min_for_kp > prefix_len)
+ prefix_len= min_for_kp;
+ }
+
found_parts|= keyuse_ext->keypart_map;
+ }
else
{
+ // This is a new key part but it doesn't form a continuous
+ // index prefix. Skip all KEYUSEs for this index.
do
{
keyuse_ext++;
@@ -981,6 +1069,11 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
best_key_parts= keyuse_ext->keypart + 1;
best_rec_per_key= rec_per_key;
best_key_keyuse_ext_start= key_keyuse_ext_start;
+ if (thd->variables.optimizer_lateral_lazy_refill > 0)
+ {
+ best_min_prefix_size= prefix_len;
+ trace.add("min_prefix_len", (longlong)prefix_len);
+ }
}
keyuse_ext++;
}
@@ -1069,10 +1162,21 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
if (spl_plan)
{
Json_writer_object choice(thd, "split_plan_choice");
+ choice.add("unsplit_cost", spl_opt_info->unsplit_cost);
+
choice.add("split_cost", spl_plan->cost);
choice.add("record_count_for_split", record_count);
- choice.add("unsplit_cost", spl_opt_info->unsplit_cost);
- if(record_count * spl_plan->cost < spl_opt_info->unsplit_cost - 0.01)
+
+ // psergey-todo: best_min_prefix_size allows us to compute a more tight
+ // bound than record_count.
+ double fanout= record_count;
+ if (thd->variables.optimizer_lateral_lazy_refill > 0)
+ {
+ fanout= get_join_prefix_fanout(join_prefix, best_min_prefix_size);
+ choice.add("join_prefix_fanout_for_split", fanout);
+ }
+
+ if(fanout * spl_plan->cost < spl_opt_info->unsplit_cost - 0.01)
{
/*
The best plan that employs splitting is cheaper than
@@ -1134,12 +1238,14 @@ bool JOIN::inject_best_splitting_cond(table_map remaining_tables)
List<Item> *inj_cond_list= &spl_opt_info->inj_cond_list;
List_iterator<KEY_FIELD> li(spl_opt_info->added_key_fields);
KEY_FIELD *added_key_field;
+ table_map needed_tables= 0;
while ((added_key_field= li++))
{
if (remaining_tables & added_key_field->val->used_tables())
continue;
if (inj_cond_list->push_back(added_key_field->cond, thd->mem_root))
return true;
+ needed_tables |= added_key_field->val->used_tables();
}
DBUG_ASSERT(inj_cond_list->elements);
switch (inj_cond_list->elements) {
@@ -1156,6 +1262,10 @@ bool JOIN::inject_best_splitting_cond(table_map remaining_tables)
if (inject_cond_into_where(inj_cond))
return true;
+ // psergey-todo: walk the join tabs until we are satisfying needed_tables...
+ // and inject the check at that point.
+ // Other solution is to just add a cache...
+
select_lex->uncacheable|= UNCACHEABLE_DEPENDENT_INJECTED;
st_select_lex_unit *unit= select_lex->master_unit();
unit->uncacheable|= UNCACHEABLE_DEPENDENT_INJECTED;
diff --git a/sql/sql_class.h b/sql/sql_class.h
index 62ce5c8a2d2..8964a8aa4f7 100644
--- a/sql/sql_class.h
+++ b/sql/sql_class.h
@@ -689,6 +689,7 @@ typedef struct system_variables
ulong optimizer_search_depth;
ulong optimizer_selectivity_sampling_limit;
ulong optimizer_use_condition_selectivity;
+ ulong optimizer_lateral_lazy_refill;
ulong use_stat_tables;
double sample_percentage;
ulong histogram_size;
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 7057ed1b5e1..5b901df2e54 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -7455,7 +7455,7 @@ best_access_path(JOIN *join,
loose_scan_opt.init(join, s, remaining_tables);
if (s->table->is_splittable())
- spl_plan= s->choose_best_splitting(record_count, remaining_tables);
+ spl_plan= s->choose_best_splitting(join_positions, idx, record_count, remaining_tables);
Json_writer_array trace_paths(thd, "considered_access_paths");
if (s->keyuse)
diff --git a/sql/sql_select.h b/sql/sql_select.h
index 29e42ff8ef8..7ffab774248 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -682,7 +682,9 @@ typedef struct st_join_table {
void partial_cleanup();
void add_keyuses_for_splitting();
- SplM_plan_info *choose_best_splitting(double record_count,
+ SplM_plan_info *choose_best_splitting(const POSITION *join_prefix,
+ uint top_prefix_size,
+ double record_count,
table_map remaining_tables);
bool fix_splitting(SplM_plan_info *spl_plan, table_map remaining_tables,
bool is_const_table);
diff --git a/sql/sys_vars.cc b/sql/sys_vars.cc
index a8e4ff2dded..e87d371453d 100644
--- a/sql/sys_vars.cc
+++ b/sql/sys_vars.cc
@@ -2672,6 +2672,14 @@ static Sys_var_ulong Sys_optimizer_use_condition_selectivity(
SESSION_VAR(optimizer_use_condition_selectivity), CMD_LINE(REQUIRED_ARG),
VALID_RANGE(1, 5), DEFAULT(4), BLOCK_SIZE(1));
+static Sys_var_ulong Sys_optimizer_lateral_lazy_refill(
+ "optimizer_lateral_lazy_refill",
+ "Controls Lazy Lateral Table Refill fix. 0 means disabled, "
+ "1 means enabled in the optimizer. Higher values are reserved "
+ "for future use.",
+ SESSION_VAR(optimizer_lateral_lazy_refill), CMD_LINE(REQUIRED_ARG),
+ VALID_RANGE(0, 2), DEFAULT(0), BLOCK_SIZE(1));
+
static Sys_var_ulong Sys_optimizer_search_depth(
"optimizer_search_depth",
"Maximum depth of search performed by the query optimizer. Values "
1
0
[Commits] 398387f0e63: MDEV-26300: Better Optimize Trace support for LATERAL DERIVED optimization
by psergey 03 Aug '21
by psergey 03 Aug '21
03 Aug '21
revision-id: 398387f0e638ee027406e72e3460fb1bf755b31d (mariadb-10.5.11-55-g398387f0e63)
parent(s): 91e925e199ce61623f8413bfa789d0e7098c3d72
author: Sergei Petrunia
committer: Sergei Petrunia
timestamp: 2021-08-03 13:36:08 +0300
message:
MDEV-26300: Better Optimize Trace support for LATERAL DERIVED optimization
---
mysql-test/main/opt_trace.result | 186 ++++++++++++++++++++++++++-------------
mysql-test/main/opt_trace.test | 17 ++--
sql/opt_split.cc | 86 ++++++++++++++----
3 files changed, 202 insertions(+), 87 deletions(-)
diff --git a/mysql-test/main/opt_trace.result b/mysql-test/main/opt_trace.result
index 9bf1cda18a3..d4ba8eccb91 100644
--- a/mysql-test/main/opt_trace.result
+++ b/mysql-test/main/opt_trace.result
@@ -449,6 +449,11 @@ select * from v2 {
}
]
},
+ {
+ "check_lateral_derived": {
+ "not_applicable": "no candidate field can be accessed through ref"
+ }
+ },
{
"best_join_order": ["t1"]
},
@@ -774,6 +779,11 @@ explain select * from v1 {
}
]
},
+ {
+ "check_lateral_derived": {
+ "not_applicable": "group list has no candidates"
+ }
+ },
{
"best_join_order": ["t1"]
},
@@ -8829,84 +8839,138 @@ id select_type table type possible_keys key key_len ref rows Extra
1 PRIMARY t1 range idx_b idx_b 5 NULL 4 Using index condition; Using where
1 PRIMARY <derived2> ref key0 key0 5 test.t1.a 2
2 LATERAL DERIVED t2 ref idx_a idx_a 5 test.t1.a 1
+select json_valid(trace) from information_schema.optimizer_trace;
+json_valid(trace)
+1
select
-json_detailed(json_extract(trace, '$**.choose_best_splitting'))
+json_detailed(json_extract(trace, '$**.check_lateral_derived'))
from
information_schema.optimizer_trace;
-json_detailed(json_extract(trace, '$**.choose_best_splitting'))
+json_detailed(json_extract(trace, '$**.check_lateral_derived'))
[
- [
-
+ {
+ "split_variants":
+ [
+ "t2.a"
+ ]
+ }
+]
+select
+json_detailed(json_extract(trace, '$**.lateral_derived_info'))
+from
+information_schema.optimizer_trace;
+json_detailed(json_extract(trace, '$**.lateral_derived_info'))
+[
+
+ {
+ "cost_breakdown":
{
- "considered_execution_plans":
- [
-
- {
- "plan_prefix":
- [
- ],
- "table": "t2",
- "best_access_path":
+ "oper_cost": 20.73533557,
+ "read_time": 4.98828125,
+ "join_read_time": 112.9872812
+ },
+ "unsplit_cost": 25.72361682,
+ "unsplit_card": 90,
+ "rec_len": 152
+ }
+]
+select
+json_detailed(json_extract(trace, '$**.lateral_derived_choice'))
+from
+information_schema.optimizer_trace;
+json_detailed(json_extract(trace, '$**.lateral_derived_choice'))
+[
+
+ {
+ "indexes_for_splitting":
+ [
+
+ {
+ "table": "t2",
+ "index": "idx_a",
+ "parts": 1,
+ "rec_per_key": 1.8367
+ }
+ ],
+ "build_split_plan":
+ [
+
+ {
+ "considered_execution_plans":
+ [
+
{
- "considered_access_paths":
+ "plan_prefix":
[
-
+ ],
+ "table": "t2",
+ "best_access_path":
+ {
+ "considered_access_paths":
+ [
+
+ {
+ "access_type": "ref",
+ "index": "idx_a",
+ "used_range_estimates": false,
+ "cause": "not available",
+ "rows": 1.8367,
+ "cost": 2.000585794,
+ "chosen": true
+ },
+
+ {
+ "type": "scan",
+ "chosen": false,
+ "cause": "cost"
+ }
+ ],
+ "chosen_access_method":
{
- "access_type": "ref",
- "index": "idx_a",
- "used_range_estimates": false,
- "cause": "not available",
- "rows": 1.8367,
+ "type": "ref",
+ "records": 1.8367,
"cost": 2.000585794,
- "chosen": true
- },
-
- {
- "type": "scan",
- "chosen": false,
- "cause": "cost"
+ "uses_join_buffering": false
}
- ],
- "chosen_access_method":
- {
- "type": "ref",
- "records": 1.8367,
- "cost": 2.000585794,
- "uses_join_buffering": false
- }
- },
- "rows_for_plan": 1.8367,
- "cost_for_plan": 2.367925794,
- "cost_for_sorting": 1.8367,
- "estimated_join_cardinality": 1.8367
+ },
+ "rows_for_plan": 1.8367,
+ "cost_for_plan": 2.367925794,
+ "cost_for_sorting": 1.8367,
+ "estimated_join_cardinality": 1.8367
+ }
+ ]
+ },
+
+ {
+ "found_split_plan":
+ {
+ "oper_cost": 0.488360125,
+ "join_best_read": 4.203625794,
+ "cost": 2.488945919,
+ "output_cardinality": 1.8367
}
- ]
+ }
+ ],
+ "split_plan_choice":
+ {
+ "split_cost": 2.488945919,
+ "record_count_for_split": 4,
+ "unsplit_cost": 25.72361682,
+ "split_chosen": true
},
-
+ "chosen_lateral_derived":
{
- "best_splitting":
- {
- "table": "t2",
- "key": "idx_a",
- "record_count": 4,
- "cost": 2.488945919,
- "unsplit_cost": 25.72361682
- }
+ "startup_cost": 9.955783677,
+ "lateral_cost": 2.488945919,
+ "records": 1
}
- ]
-]
-select
-json_detailed(json_extract(trace, '$**.lateral_derived'))
-from
-information_schema.optimizer_trace;
-json_detailed(json_extract(trace, '$**.lateral_derived'))
-[
+ },
{
- "startup_cost": 9.955783677,
- "splitting_cost": 2.488945919,
- "records": 1
+ "indexes_for_splitting":
+ [
+ ]
}
]
drop table t1,t2;
diff --git a/mysql-test/main/opt_trace.test b/mysql-test/main/opt_trace.test
index 66a333d7dc5..16788695e6a 100644
--- a/mysql-test/main/opt_trace.test
+++ b/mysql-test/main/opt_trace.test
@@ -729,19 +729,20 @@ from t1 join
on t1.a=t.a
where t1.b < 3;
-#
-# Just show that choose_best_splitting function has coverage in the
-# optimizer trace and re-optmization of child select inside it is distinct
-# from the rest of join optimization.
+select json_valid(trace) from information_schema.optimizer_trace;
+
+select
+ json_detailed(json_extract(trace, '$**.check_lateral_derived'))
+from
+ information_schema.optimizer_trace;
+
select
- json_detailed(json_extract(trace, '$**.choose_best_splitting'))
+ json_detailed(json_extract(trace, '$**.lateral_derived_info'))
from
information_schema.optimizer_trace;
-# Same as above. just to show that splitting plan has some coverage in the
-# trace.
select
- json_detailed(json_extract(trace, '$**.lateral_derived'))
+ json_detailed(json_extract(trace, '$**.lateral_derived_choice'))
from
information_schema.optimizer_trace;
diff --git a/sql/opt_split.cc b/sql/opt_split.cc
index 41b8acf5dcb..d482c2de2a4 100644
--- a/sql/opt_split.cc
+++ b/sql/opt_split.cc
@@ -343,6 +343,9 @@ bool JOIN::check_for_splittable_materialized()
if (!partition_list)
return false;
+ Json_writer_object trace_wrapper(thd);
+ Json_writer_object trace_split(thd, "check_lateral_derived");
+
ORDER *ord;
Dynamic_array<SplM_field_ext_info> candidates(PSI_INSTRUMENT_MEM);
@@ -388,8 +391,10 @@ bool JOIN::check_for_splittable_materialized()
}
}
if (candidates.elements() == 0) // no candidates satisfying (8.1) && (8.2)
+ {
+ trace_split.add("not_applicable", "group list has no candidates");
return false;
-
+ }
/*
For each table from this join find the keys that can be used for ref access
of the fields mentioned in the 'array candidates'
@@ -447,7 +452,11 @@ bool JOIN::check_for_splittable_materialized()
}
if (!spl_field_cnt) // No candidate field can be accessed by ref => !(9)
+ {
+ trace_split.add("not_applicable",
+ "no candidate field can be accessed through ref");
return false;
+ }
/*
Create a structure of the type SplM_opt_info and fill it with
@@ -465,16 +474,20 @@ bool JOIN::check_for_splittable_materialized()
spl_opt_info->tables_usable_for_splitting= 0;
spl_opt_info->spl_field_cnt= spl_field_cnt;
spl_opt_info->spl_fields= spl_field;
- for (cand= cand_start; cand < cand_end; cand++)
{
- if (!cand->is_usable_for_ref_access)
- continue;
- spl_field->producing_item= cand->producing_item;
- spl_field->underlying_field= cand->underlying_field;
- spl_field->mat_field= cand->mat_field;
- spl_opt_info->tables_usable_for_splitting|=
- cand->underlying_field->table->map;
- spl_field++;
+ Json_writer_array trace_range(thd, "split_variants");
+ for (cand= cand_start; cand < cand_end; cand++)
+ {
+ if (!cand->is_usable_for_ref_access)
+ continue;
+ spl_field->producing_item= cand->producing_item;
+ trace_range.add(cand->producing_item);
+ spl_field->underlying_field= cand->underlying_field;
+ spl_field->mat_field= cand->mat_field;
+ spl_opt_info->tables_usable_for_splitting|=
+ cand->underlying_field->table->map;
+ spl_field++;
+ }
}
/* Attach this info to the table T */
@@ -738,7 +751,19 @@ void JOIN::add_keyuses_for_splitting()
spl_opt_info->unsplit_cost= best_positions[table_count-1].read_time +
oper_cost;
+ {
+ Json_writer_object trace(thd, "lateral_derived_info");
+ {
+ Json_writer_object cost_detail(thd, "cost_breakdown");
+ cost_detail.add("oper_cost", oper_cost);
+ cost_detail.add("read_time", best_positions[table_count-1].read_time);
+ cost_detail.add("join_read_time", best_read);
+ }
+ trace.add("unsplit_cost", spl_opt_info->unsplit_cost);
+ trace.add("unsplit_card", spl_opt_info->unsplit_card);
+ trace.add("rec_len", (ulonglong) rec_len);
+ }
if (!(save_qep= new Join_plan_state(table_count + 1)))
goto err;
@@ -793,6 +818,9 @@ void JOIN::add_keyuses_for_splitting()
void JOIN_TAB::add_keyuses_for_splitting()
{
+ Json_writer_object trace(join->thd);
+ trace.add_table_name(this);
+
DBUG_ASSERT(table->spl_opt_info != NULL);
SplM_opt_info *spl_opt_info= table->spl_opt_info;
spl_opt_info->join->add_keyuses_for_splitting();
@@ -895,6 +923,8 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
uint best_key= 0;
uint best_key_parts= 0;
+ Json_writer_object spl_trace(thd, "lateral_derived_choice");
+ Json_writer_array trace_indexes(thd, "indexes_for_splitting");
/*
Check whether there are keys that can be used to join T employing splitting
and if so, select the best out of such keys
@@ -939,6 +969,13 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
key_info->actual_rec_per_key(keyuse_ext->keypart);
if (rec_per_key < best_rec_per_key)
{
+ Json_writer_object trace(thd);
+ trace.add_table_name(keyuse_ext->table);
+ trace.add("index",
+ keyuse_ext->table->key_info[keyuse_ext->key].name.str);
+ trace.add("parts", (longlong)keyuse_ext->keypart + 1);
+ trace.add("rec_per_key", rec_per_key);
+
best_table= keyuse_ext->table;
best_key= keyuse_ext->key;
best_key_parts= keyuse_ext->keypart + 1;
@@ -951,17 +988,19 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
}
while (keyuse_ext->table == table);
}
+ trace_indexes.end();
spl_opt_info->last_plan= 0;
+
if (best_table)
{
/*
The key for splitting was chosen, look for the plan for this key
in the cache
*/
- Json_writer_array spl_trace(thd, "choose_best_splitting");
spl_plan= spl_opt_info->find_plan(best_table, best_key, best_key_parts);
if (!spl_plan)
{
+ Json_writer_array spl_trace(thd, "build_split_plan");
/*
The plan for the chosen key has not been found in the cache.
Build a new plan and save info on it in the cache
@@ -1010,12 +1049,11 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
if (unlikely(thd->trace_started()))
{
Json_writer_object wrapper(thd);
- Json_writer_object find_trace(thd, "best_splitting");
- find_trace.add("table", best_table->alias.c_ptr());
- find_trace.add("key", best_table->key_info[best_key].name);
- find_trace.add("record_count", record_count);
+ Json_writer_object find_trace(thd, "found_split_plan");
+ find_trace.add("oper_cost", oper_cost);
+ find_trace.add("join_best_read", join->best_read);
find_trace.add("cost", spl_plan->cost);
- find_trace.add("unsplit_cost", spl_opt_info->unsplit_cost);
+ find_trace.add("output_cardinality", split_card);
}
memcpy((char *) spl_plan->best_positions,
(char *) join->best_positions,
@@ -1023,8 +1061,17 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
reset_validity_vars_for_keyuses(best_key_keyuse_ext_start, best_table,
best_key, remaining_tables, false);
}
+ else
+ {
+ Json_writer_object find_trace(thd, "cached_split_plan_found");
+ find_trace.add("cost", spl_plan->cost);
+ }
if (spl_plan)
{
+ Json_writer_object choice(thd, "split_plan_choice");
+ choice.add("split_cost", spl_plan->cost);
+ choice.add("record_count_for_split", record_count);
+ choice.add("unsplit_cost", spl_opt_info->unsplit_cost);
if(record_count * spl_plan->cost < spl_opt_info->unsplit_cost - 0.01)
{
/*
@@ -1032,7 +1079,10 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
the plan without splitting
*/
spl_opt_info->last_plan= spl_plan;
+ choice.add("split_chosen", true);
}
+ else
+ choice.add("split_chosen", false);
}
}
@@ -1044,9 +1094,9 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
startup_cost= record_count * spl_plan->cost;
records= (ha_rows) (records * spl_plan->split_sel);
- Json_writer_object trace(thd, "lateral_derived");
+ Json_writer_object trace(thd, "chosen_lateral_derived");
trace.add("startup_cost", startup_cost);
- trace.add("splitting_cost", spl_plan->cost);
+ trace.add("lateral_cost", spl_plan->cost);
trace.add("records", records);
}
else
1
0
[Commits] 4dac8c1cb79: Better Optimize Trace support for LATERAL DERIVED optimization
by Sergei Petrunia 01 Aug '21
by Sergei Petrunia 01 Aug '21
01 Aug '21
revision-id: 4dac8c1cb79f9204a8eb566915f65cb01d66424f (mariadb-10.5.11-55-g4dac8c1cb79)
parent(s): 91e925e199ce61623f8413bfa789d0e7098c3d72
author: Sergei Petrunia
committer: Sergei Petrunia
timestamp: 2021-08-01 23:24:41 +0300
message:
Better Optimize Trace support for LATERAL DERIVED optimization
---
sql/opt_split.cc | 81 +++++++++++++++++++++++++++++++++++++++++++-------------
1 file changed, 62 insertions(+), 19 deletions(-)
diff --git a/sql/opt_split.cc b/sql/opt_split.cc
index 41b8acf5dcb..c7a2726edc3 100644
--- a/sql/opt_split.cc
+++ b/sql/opt_split.cc
@@ -343,6 +343,9 @@ bool JOIN::check_for_splittable_materialized()
if (!partition_list)
return false;
+ Json_writer_object trace_wrapper(thd);
+ Json_writer_object trace_split(thd, "check_lateral_derived");
+
ORDER *ord;
Dynamic_array<SplM_field_ext_info> candidates(PSI_INSTRUMENT_MEM);
@@ -388,8 +391,10 @@ bool JOIN::check_for_splittable_materialized()
}
}
if (candidates.elements() == 0) // no candidates satisfying (8.1) && (8.2)
+ {
+ trace_split.add("not_applicable", "group list has no candidates");
return false;
-
+ }
/*
For each table from this join find the keys that can be used for ref access
of the fields mentioned in the 'array candidates'
@@ -447,7 +452,11 @@ bool JOIN::check_for_splittable_materialized()
}
if (!spl_field_cnt) // No candidate field can be accessed by ref => !(9)
+ {
+ trace_split.add("not_applicable",
+ "no candidate field can be accessed through ref");
return false;
+ }
/*
Create a structure of the type SplM_opt_info and fill it with
@@ -465,16 +474,20 @@ bool JOIN::check_for_splittable_materialized()
spl_opt_info->tables_usable_for_splitting= 0;
spl_opt_info->spl_field_cnt= spl_field_cnt;
spl_opt_info->spl_fields= spl_field;
- for (cand= cand_start; cand < cand_end; cand++)
{
- if (!cand->is_usable_for_ref_access)
- continue;
- spl_field->producing_item= cand->producing_item;
- spl_field->underlying_field= cand->underlying_field;
- spl_field->mat_field= cand->mat_field;
- spl_opt_info->tables_usable_for_splitting|=
- cand->underlying_field->table->map;
- spl_field++;
+ Json_writer_array trace_range(thd, "split_variants");
+ for (cand= cand_start; cand < cand_end; cand++)
+ {
+ if (!cand->is_usable_for_ref_access)
+ continue;
+ spl_field->producing_item= cand->producing_item;
+ trace_range.add(cand->producing_item);
+ spl_field->underlying_field= cand->underlying_field;
+ spl_field->mat_field= cand->mat_field;
+ spl_opt_info->tables_usable_for_splitting|=
+ cand->underlying_field->table->map;
+ spl_field++;
+ }
}
/* Attach this info to the table T */
@@ -738,7 +751,12 @@ void JOIN::add_keyuses_for_splitting()
spl_opt_info->unsplit_cost= best_positions[table_count-1].read_time +
oper_cost;
-
+ {
+ Json_writer_object trace(thd, "lateral_derived");
+ trace.add("unsplit_cost", spl_opt_info->unsplit_cost);
+ trace.add("unsplit_card", spl_opt_info->unsplit_card);
+ trace.add("rec_len", (ulonglong) rec_len);
+ }
if (!(save_qep= new Join_plan_state(table_count + 1)))
goto err;
@@ -793,6 +811,9 @@ void JOIN::add_keyuses_for_splitting()
void JOIN_TAB::add_keyuses_for_splitting()
{
+ Json_writer_object trace(join->thd);
+ trace.add_table_name(this);
+
DBUG_ASSERT(table->spl_opt_info != NULL);
SplM_opt_info *spl_opt_info= table->spl_opt_info;
spl_opt_info->join->add_keyuses_for_splitting();
@@ -895,6 +916,8 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
uint best_key= 0;
uint best_key_parts= 0;
+ Json_writer_object spl_trace(thd, "lateral_plan_choice");
+ Json_writer_array trace_indexes(thd, "indexes_for_splitting");
/*
Check whether there are keys that can be used to join T employing splitting
and if so, select the best out of such keys
@@ -939,6 +962,13 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
key_info->actual_rec_per_key(keyuse_ext->keypart);
if (rec_per_key < best_rec_per_key)
{
+ Json_writer_object trace(thd);
+ trace.add_table_name(keyuse_ext->table);
+ trace.add("index",
+ keyuse_ext->table->key_info[keyuse_ext->key].name.str);
+ trace.add("parts", (longlong)keyuse_ext->keypart + 1);
+ trace.add("rec_per_key", rec_per_key);
+
best_table= keyuse_ext->table;
best_key= keyuse_ext->key;
best_key_parts= keyuse_ext->keypart + 1;
@@ -951,17 +981,19 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
}
while (keyuse_ext->table == table);
}
+ trace_indexes.end();
spl_opt_info->last_plan= 0;
+
if (best_table)
{
/*
The key for splitting was chosen, look for the plan for this key
in the cache
*/
- Json_writer_array spl_trace(thd, "choose_best_splitting");
spl_plan= spl_opt_info->find_plan(best_table, best_key, best_key_parts);
if (!spl_plan)
{
+ Json_writer_array spl_trace(thd, "build_split_plan");
/*
The plan for the chosen key has not been found in the cache.
Build a new plan and save info on it in the cache
@@ -1010,12 +1042,11 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
if (unlikely(thd->trace_started()))
{
Json_writer_object wrapper(thd);
- Json_writer_object find_trace(thd, "best_splitting");
- find_trace.add("table", best_table->alias.c_ptr());
- find_trace.add("key", best_table->key_info[best_key].name);
- find_trace.add("record_count", record_count);
+ Json_writer_object find_trace(thd, "found_split_plan");
+ find_trace.add("oper_cost", oper_cost);
+ find_trace.add("join_best_read", join->best_read);
find_trace.add("cost", spl_plan->cost);
- find_trace.add("unsplit_cost", spl_opt_info->unsplit_cost);
+ find_trace.add("output_cardinality", split_card);
}
memcpy((char *) spl_plan->best_positions,
(char *) join->best_positions,
@@ -1023,8 +1054,17 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
reset_validity_vars_for_keyuses(best_key_keyuse_ext_start, best_table,
best_key, remaining_tables, false);
}
+ else
+ {
+ Json_writer_object find_trace(thd, "cached_split_plan_found");
+ find_trace.add("cost", spl_plan->cost);
+ }
if (spl_plan)
{
+ Json_writer_object choice(thd, "split_plan_choice");
+ choice.add("split_cost", spl_plan->cost);
+ choice.add("record_count_for_split", record_count);
+ choice.add("unsplit_cost", spl_opt_info->unsplit_cost);
if(record_count * spl_plan->cost < spl_opt_info->unsplit_cost - 0.01)
{
/*
@@ -1032,7 +1072,10 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
the plan without splitting
*/
spl_opt_info->last_plan= spl_plan;
+ choice.add("split_chosen", true);
}
+ else
+ choice.add("split_chosen", false);
}
}
@@ -1044,9 +1087,9 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
startup_cost= record_count * spl_plan->cost;
records= (ha_rows) (records * spl_plan->split_sel);
- Json_writer_object trace(thd, "lateral_derived");
+ Json_writer_object trace(thd, "chosen_lateral_derived");
trace.add("startup_cost", startup_cost);
- trace.add("splitting_cost", spl_plan->cost);
+ trace.add("lateral_cost", spl_plan->cost);
trace.add("records", records);
}
else
1
0
[Commits] 93e964a8f55: Better Optimize Trace support for LATERAL DERIVED optimization
by Sergei Petrunia 30 Jul '21
by Sergei Petrunia 30 Jul '21
30 Jul '21
revision-id: 93e964a8f5545c1688fcf1101ea298403cc6dbe1 (mariadb-10.5.11-55-g93e964a8f55)
parent(s): 91e925e199ce61623f8413bfa789d0e7098c3d72
author: Sergei Petrunia
committer: Sergei Petrunia
timestamp: 2021-07-30 22:53:00 +0300
message:
Better Optimize Trace support for LATERAL DERIVED optimization
---
sql/opt_split.cc | 86 ++++++++++++++++++++++++++++++++++++++++++-------------
sql/sql_array.h | 2 ++
sql/sql_select.cc | 5 ++++
3 files changed, 73 insertions(+), 20 deletions(-)
diff --git a/sql/opt_split.cc b/sql/opt_split.cc
index 41b8acf5dcb..61e4eed1b6f 100644
--- a/sql/opt_split.cc
+++ b/sql/opt_split.cc
@@ -188,6 +188,7 @@
#include "mariadb.h"
#include "sql_select.h"
#include "opt_trace.h"
+#include "sql_test.h" /* for print_keyuse_array_for_trace */
/* Info on a splitting field */
struct SplM_field_info
@@ -343,6 +344,9 @@ bool JOIN::check_for_splittable_materialized()
if (!partition_list)
return false;
+ Json_writer_object trace_wrapper(thd);
+ Json_writer_object trace_split(thd, "check_lateral_derived");
+
ORDER *ord;
Dynamic_array<SplM_field_ext_info> candidates(PSI_INSTRUMENT_MEM);
@@ -388,8 +392,10 @@ bool JOIN::check_for_splittable_materialized()
}
}
if (candidates.elements() == 0) // no candidates satisfying (8.1) && (8.2)
+ {
+ trace_split.add("not_applicable", "group list has no candidates");
return false;
-
+ }
/*
For each table from this join find the keys that can be used for ref access
of the fields mentioned in the 'array candidates'
@@ -447,7 +453,11 @@ bool JOIN::check_for_splittable_materialized()
}
if (!spl_field_cnt) // No candidate field can be accessed by ref => !(9)
+ {
+ trace_split.add("not_applicable",
+ "no candidate field can be accessed through ref");
return false;
+ }
/*
Create a structure of the type SplM_opt_info and fill it with
@@ -465,16 +475,20 @@ bool JOIN::check_for_splittable_materialized()
spl_opt_info->tables_usable_for_splitting= 0;
spl_opt_info->spl_field_cnt= spl_field_cnt;
spl_opt_info->spl_fields= spl_field;
- for (cand= cand_start; cand < cand_end; cand++)
{
- if (!cand->is_usable_for_ref_access)
- continue;
- spl_field->producing_item= cand->producing_item;
- spl_field->underlying_field= cand->underlying_field;
- spl_field->mat_field= cand->mat_field;
- spl_opt_info->tables_usable_for_splitting|=
- cand->underlying_field->table->map;
- spl_field++;
+ Json_writer_array trace_range(thd, "split_variants");
+ for (cand= cand_start; cand < cand_end; cand++)
+ {
+ if (!cand->is_usable_for_ref_access)
+ continue;
+ spl_field->producing_item= cand->producing_item;
+ trace_range.add(cand->producing_item);
+ spl_field->underlying_field= cand->underlying_field;
+ spl_field->mat_field= cand->mat_field;
+ spl_opt_info->tables_usable_for_splitting|=
+ cand->underlying_field->table->map;
+ spl_field++;
+ }
}
/* Attach this info to the table T */
@@ -738,7 +752,16 @@ void JOIN::add_keyuses_for_splitting()
spl_opt_info->unsplit_cost= best_positions[table_count-1].read_time +
oper_cost;
-
+ {
+ Json_writer_object obj(thd);
+ {
+ //Json_writer_object(thd, "added_keyuses");
+ //print_keyuse_array_for_trace(thd, &ext_keyuses_for_splitting);
+ }
+ obj.add("unsplit_cost", spl_opt_info->unsplit_cost);
+ obj.add("unsplit_card", spl_opt_info->unsplit_card);
+ obj.add("rec_len", (ulonglong) rec_len);
+ }
if (!(save_qep= new Join_plan_state(table_count + 1)))
goto err;
@@ -894,7 +917,10 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
SplM_plan_info *spl_plan= 0;
uint best_key= 0;
uint best_key_parts= 0;
-
+
+ Json_writer_array spl_trace(thd, "lateral_plan_choice");
+ Json_writer_array wrapper(thd);
+ Json_writer_array trace_indexes(thd, "indexes_for_splitting");
/*
Check whether there are keys that can be used to join T employing splitting
and if so, select the best out of such keys
@@ -939,6 +965,13 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
key_info->actual_rec_per_key(keyuse_ext->keypart);
if (rec_per_key < best_rec_per_key)
{
+ Json_writer_object trace(thd);
+ trace.add_table_name(keyuse_ext->table);
+ trace.add("index",
+ keyuse_ext->table->key_info[keyuse_ext->key].name.str);
+ trace.add("parts", (longlong)keyuse_ext->keypart + 1);
+ trace.add("rec_per_key", rec_per_key);
+
best_table= keyuse_ext->table;
best_key= keyuse_ext->key;
best_key_parts= keyuse_ext->keypart + 1;
@@ -951,17 +984,19 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
}
while (keyuse_ext->table == table);
}
+ trace_indexes.end();
spl_opt_info->last_plan= 0;
+
if (best_table)
{
/*
The key for splitting was chosen, look for the plan for this key
in the cache
*/
- Json_writer_array spl_trace(thd, "choose_best_splitting");
spl_plan= spl_opt_info->find_plan(best_table, best_key, best_key_parts);
if (!spl_plan)
{
+ Json_writer_array spl_trace(thd, "build_split_plan");
/*
The plan for the chosen key has not been found in the cache.
Build a new plan and save info on it in the cache
@@ -1010,12 +1045,9 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
if (unlikely(thd->trace_started()))
{
Json_writer_object wrapper(thd);
- Json_writer_object find_trace(thd, "best_splitting");
- find_trace.add("table", best_table->alias.c_ptr());
- find_trace.add("key", best_table->key_info[best_key].name);
- find_trace.add("record_count", record_count);
+ Json_writer_object find_trace(thd, "found_split_plan");
find_trace.add("cost", spl_plan->cost);
- find_trace.add("unsplit_cost", spl_opt_info->unsplit_cost);
+ find_trace.add("output_cardinality", split_card);
}
memcpy((char *) spl_plan->best_positions,
(char *) join->best_positions,
@@ -1023,8 +1055,19 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
reset_validity_vars_for_keyuses(best_key_keyuse_ext_start, best_table,
best_key, remaining_tables, false);
}
+ else
+ {
+ Json_writer_object wrapper(thd);
+ Json_writer_object find_trace(thd, "cached_split_plan_found");
+ find_trace.add("cost", spl_plan->cost);
+ }
if (spl_plan)
{
+ Json_writer_object wrapper(thd);
+ Json_writer_object choice(thd, "split_plan_choice");
+ choice.add("split_cost", spl_plan->cost);
+ choice.add("record_count_for_split", record_count);
+ choice.add("unsplit_cost", spl_opt_info->unsplit_cost);
if(record_count * spl_plan->cost < spl_opt_info->unsplit_cost - 0.01)
{
/*
@@ -1032,7 +1075,10 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
the plan without splitting
*/
spl_opt_info->last_plan= spl_plan;
+ choice.add("split_chosen", true);
}
+ else
+ choice.add("split_chosen", false);
}
}
@@ -1044,9 +1090,9 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count,
startup_cost= record_count * spl_plan->cost;
records= (ha_rows) (records * spl_plan->split_sel);
- Json_writer_object trace(thd, "lateral_derived");
+ Json_writer_object trace(thd, "chosen_lateral_derived");
trace.add("startup_cost", startup_cost);
- trace.add("splitting_cost", spl_plan->cost);
+ trace.add("lateral_cost", spl_plan->cost);
trace.add("records", records);
}
else
diff --git a/sql/sql_array.h b/sql/sql_array.h
index b6de1b18d78..244d4a5be06 100644
--- a/sql/sql_array.h
+++ b/sql/sql_array.h
@@ -289,6 +289,8 @@ template <class Elem> class Dynamic_array
{
my_qsort2(array.buffer, array.elements, sizeof(Elem), (qsort2_cmp)cmp_func, data);
}
+
+ DYNAMIC_ARRAY *impl() { return &array; }
};
typedef Bounds_checked_array<Item*> Ref_ptr_array;
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 7057ed1b5e1..538696b2c7a 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -5484,7 +5484,12 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list,
s->scan_time();
if (s->table->is_splittable())
+ {
+ Json_writer_object trace(thd);
+ trace.add_table_name(s);
+ Json_writer_object trace_lateral(thd, "lateral_derived");
s->add_keyuses_for_splitting();
+ }
/*
Set a max range of how many seeks we can expect when using keys
1
0