|
I was able to set this up on my system, the place where the issue is the function table_cond_selectivity.
Here is the stack trace at which I am looking
#0 table_cond_selectivity (join=0x62d0000e24b8, idx=0, s=0x62d0000fc4c0, rem_tables=3) at /home/varunraiko/MariaDB/10.4-dev/sql/sql_select.cc:9057
|
#1 0x0000555556905295 in best_extension_by_limited_search (join=0x62d0000e24b8, remaining_tables=7, idx=0, record_count=1, read_time=0, search_depth=62,
|
prune_level=1, use_cond_selectivity=4) at /home/varunraiko/MariaDB/10.4-dev/sql/sql_select.cc:9465
|
#2 0x0000555556900409 in greedy_search (join=0x62d0000e24b8, remaining_tables=7, search_depth=62, prune_level=1, use_cond_selectivity=4)
|
at /home/varunraiko/MariaDB/10.4-dev/sql/sql_select.cc:8596
|
#3 0x00005555568fe0cb in choose_plan (join=0x62d0000e24b8, join_tables=7) at /home/varunraiko/MariaDB/10.4-dev/sql/sql_select.cc:8162
|
#4 0x00005555568e988e in make_join_statistics (join=0x62d0000e24b8, tables_list=..., keyuse_array=0x62d0000e27a8)
|
at /home/varunraiko/MariaDB/10.4-dev/sql/sql_select.cc:5481
|
#5 0x00005555568c6b23 in JOIN::optimize_inner (this=0x62d0000e24b8) at /home/varunraiko/MariaDB/10.4-dev/sql/sql_select.cc:2193
|
#6 0x00005555568c014d in JOIN::optimize (this=0x62d0000e24b8) at /home/varunraiko/MariaDB/10.4-dev/sql/sql_select.cc:1562
|
#7 0x00005555567972e4 in st_select_lex::optimize_unflattened_subqueries (this=0x62b0000860b8, const_only=false)
|
at /home/varunraiko/MariaDB/10.4-dev/sql/sql_lex.cc:4187
|
#8 0x0000555556cf1499 in JOIN::optimize_unflattened_subqueries (this=0x6290000cd290) at /home/varunraiko/MariaDB/10.4-dev/sql/opt_subselect.cc:5481
|
#9 0x00005555568cce70 in JOIN::optimize_stage2 (this=0x6290000cd290) at /home/varunraiko/MariaDB/10.4-dev/sql/sql_select.cc:2755
|
#10 0x00005555568c6e37 in JOIN::optimize_inner (this=0x6290000cd290) at /home/varunraiko/MariaDB/10.4-dev/sql/sql_select.cc:2219
|
#11 0x00005555568c014d in JOIN::optimize (this=0x6290000cd290) at /home/varunraiko/MariaDB/10.4-dev/sql/sql_select.cc:1562
|
#12 0x00005555568e09d9 in mysql_select (thd=0x62b00007e270, tables=0x629000093888, wild_num=0, fields=..., conds=0x0, og_num=0, order=0x0, group=0x0, having=0x0,
|
proc_param=0x0, select_options=2147748612, result=0x629000094940, unit=0x62b0000821a0, select_lex=0x62b0000860b8)
|
at /home/varunraiko/MariaDB/10.4-dev/sql/sql_select.cc:4591
|
#13 0x00005555569876a3 in mysql_explain_union (thd=0x62b00007e270, unit=0x62b0000821a0, result=0x629000094940)
|
at /home/varunraiko/MariaDB/10.4-dev/sql/sql_select.cc:26746
|
#14 0x000055555681ff58 in execute_sqlcom_select (thd=0x62b00007e270, all_tables=0x629000093888) at /home/varunraiko/MariaDB/10.4-dev/sql/sql_parse.cc:6296
|
#15 0x000055555680b885 in mysql_execute_command (thd=0x62b00007e270) at /home/varunraiko/MariaDB/10.4-dev/sql/sql_parse.cc:3899
|
#16 0x000055555682a460 in mysql_parse (thd=0x62b00007e270,
|
rawbuf=0x62b000085290 "EXPLAIN SELECT COUNT(1) FROM (SELECT user.*, edoc_user_rubric_assignment.id assignment_id, edoc_user_rubric_assignment.rubric_id assignment_rubric_id, edoc_user_rubric_assignment.year_id assig"..., length=1752, parser_state=0x7fffe0f844c0, is_com_multi=false, is_next_command=false)
|
at /home/varunraiko/MariaDB/10.4-dev/sql/sql_parse.cc:7909
|
#17 0x00005555567fd3b3 in dispatch_command (command=COM_QUERY, thd=0x62b00007e270, packet=0x62900007d271 "", packet_length=1752, is_com_multi=false,
|
is_next_command=false) at /home/varunraiko/MariaDB/10.4-dev/sql/sql_parse.cc:1842
|
#18 0x00005555567f9863 in do_command (thd=0x62b00007e270) at /home/varunraiko/MariaDB/10.4-dev/sql/sql_parse.cc:1359
|
#19 0x0000555556beecbc in do_handle_one_connection (connect=0x6110000082b0) at /home/varunraiko/MariaDB/10.4-dev/sql/sql_connect.cc:1412
|
#20 0x0000555556bee55a in handle_one_connection (arg=0x6110000082b0) at /home/varunraiko/MariaDB/10.4-dev/sql/sql_connect.cc:1316
|
#21 0x00007ffff5f776db in start_thread (arg=0x7fffe0f87300) at pthread_create.c:463
|
|
For Good Plan
(gdb) p table->alias.Ptr
|
$13 = 0x60c000037130 "tch"
|
(gdb) p table->quick_keys
|
$14 = {map = 0}
|
(gdb) p table->quick_rows[key]
|
$15 = 0
|
(gdb) p pushdown_cond_selectivity
|
$18 = 1
|
For Bad Plan
(gdb) p table->cond_selectivity
|
$28 = 1
|
(gdb) p table->alias.Ptr
|
$29 = 0x60c000037130 "tch"
|
(gdb) p table->quick_rows[key]
|
$30 = 1
|
(gdb) p table->quick_keys
|
$31 = {map = 0}
|
So in table_cond_selectivity we have a line of code like
sel /= (double)table->quick_rows[key] / (double) table->stat_records();
|
(gdb) p s->table->stat_records()
|
$37 = 880208
|
(gdb) p sel
|
$32 = 880208
|
quick_rows[key] shows 1 which is incorrect, it is just some garbage.
So in the bad plan for key for which we don't have any range access (or sargable condition we predict one row, which in my opinion is just garbage). We are only expected to use the estimate of quick_row[key] only when we have quick_keys.is_set(key) set to TRUE
|
|
Patch
http://lists.askmonty.org/pipermail/commits/2019-September/013970.html
|
|
Patch with a test case:
http://lists.askmonty.org/pipermail/commits/2019-September/013973.html
|
|
New Patch
http://lists.askmonty.org/pipermail/commits/2019-September/013974.html
|
|
Varun Gupta has provided the following simple test case that reproduces the same bug in 10.1:
create table t1 (id int, a int, PRIMARY KEY(id), key(a));
|
insert into t1 select seq, seq from seq_1_to_100;
|
create table t2 (id int, a int, b int, PRIMARY KEY(id), key(a), key(b));
|
insert into t2 select seq, seq, seq from seq_1_to_100;
|
set optimizer_switch='exists_to_in=off';
|
set optimizer_use_condition_selectivity=2;
|
explain select * from t1
|
where exists (select * from t1 t , t2 where t.a=t1.a and t2.a = t.id and t2.b < 20);
|
explain select * from t1 , t1 t WHERE t1.a = t.a and t1.id = 65;
|
explain select * from t1
|
where exists (select * from t1 t , t2 where t.a=t1.a and t2.a = t.id and t2.b < 20);
|
While EXPLAIN for the first query returns an expected efficient execution plan
MariaDB [test]> explain select * from t1
|
-> where exists (select * from t1 t , t2 where t.a=t1.a and t2.a = t.id and t2.b < 20);
|
+------+--------------------+-------+-------+---------------+------+---------+-----------+------+--------------------------+
|
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
|
+------+--------------------+-------+-------+---------------+------+---------+-----------+------+--------------------------+
|
| 1 | PRIMARY | t1 | index | NULL | a | 5 | NULL | 100 | Using where; Using index |
|
| 2 | DEPENDENT SUBQUERY | t | ref | PRIMARY,a | a | 5 | test.t1.a | 1 | Using index |
|
| 2 | DEPENDENT SUBQUERY | t2 | ref | a,b | a | 5 | test.t.id | 1 | Using where |
|
+------+--------------------+-------+-------+---------------+------+---------+-----------+------+--------------------------
|
EXPLAIN for the third query returns an inefficient execution plan:
MariaDB [test]> explain select * from t1
|
-> where exists (select * from t1 t , t2 where t.a=t1.a and t2.a = t.id and t2.b < 20);
|
+------+--------------------+-------+--------+---------------+---------+---------+-----------+------+------------------------------------+
|
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
|
+------+--------------------+-------+--------+---------------+---------+---------+-----------+------+------------------------------------+
|
| 1 | PRIMARY | t1 | index | NULL | a | 5 | NULL | 100 | Using where; Using index |
|
| 2 | DEPENDENT SUBQUERY | t2 | range | a,b | b | 5 | NULL | 18 | Using index condition; Using where |
|
| 2 | DEPENDENT SUBQUERY | t | eq_ref | PRIMARY,a | PRIMARY | 4 | test.t2.a | 1 | Using where |
|
+------+--------------------+-------+--------+---------------+---------+---------+-----------+------+------------------------------------+
|
However the first and the third query are the same.
An analysis of the processing of the third query shows that direct cause of the bad choice is a wrong
estimate of the cardinality of the partial join [t] . The cardinality is too high because the function table_cond_selectivity() returns an absurd number 100 while a selectivity cannot be greater than 1.
Further analysis shows that the following code added by the patch fixing the bug MDEV-6003 (commit 2acd81af73ac337658eb646ba2434f46a6dc8dc5) leads to this number. When accessing table t by outer reference t1.a via index on a (the second index defined to t) we do not perform any range analysis for t and this can be checked in debugger. Yet we see t->quick_key_parts[1] contains 1 andtable->quick_rows[key] contains 1 though the should have been remained untouched and equal to 0.. These confusing numbers force the code to consider t.a as equal to a constant whose selectivity should be discounted. The numbers has been left by running EXPLAIN for the second query that really uses ref access with a constant.
Thus real cause of the problem is that TABLE::init does not clean the arrays TABLE::quick_key_parts[] and TABLE::>quick_rows[]. It should have done it because the TABLE structure created for any instance of t1 can be reused for many queries.
|
|
igor also requested to add an assert that would say that the selectivity is in the range (0,1]
|
|
After adding the ASSERT to table_cond_selectivity, I see some tests failing in the main suite.
TEST CASE #1
CREATE TABLE t1 (a varchar(16), b int, PRIMARY KEY(a), KEY(b));
|
INSERT INTO t1 VALUES
|
('USAChinese',10), ('USAEnglish',20), ('USAFrench',30);
|
|
CREATE TABLE t2 (i int);
|
INSERT INTO t2 VALUES
|
(1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(1),(2),(3),(4);
|
ANALYZE TABLE t1, t2;
|
|
set use_stat_tables='preferably';
|
set optimizer_use_condition_selectivity=3;
|
|
EXPLAIN EXTENDED
|
SELECT * FROM t1, t2
|
WHERE a <> 'USARussian' AND b IS NULL;
|
Analysis
Debugging inside the function calculate_cond_selectivity_for_table
For Primary Key on column a (the condition is a <> 'USARussian')
(gdb) p keynr
|
$6 = 0
|
(gdb) p table->quick_rows[keynr]
|
$3 = 4
|
(gdb) p table_records
|
$4 = 3
|
(gdb) p quick_cond_selectivity
|
$5 = 1.3333333333333333
|
Inside this function we have:
table->cond_selectivity*= quick_cond_selectivity;
|
(gdb) p table->cond_selectivity
|
$22 = 1.3333333333333333
|
The estimate for range access for index(a) > total records in the table.
The estimates should always be capped to the total number of records in the table.
So to fix this it would be correct to just make the range optimizer not return
estimates that are greater than the records in a table.
For Index on column b
(gdb) p quick_cond_selectivity
|
$24 = 0.33333333333333331
|
(gdb) p table->quick_rows[keynr]
|
$26 = 1
|
(gdb) p keynr
|
$27 = 1
|
table->cond_selectivity*= quick_cond_selectivity;
|
(gdb) p table->cond_selectivity
|
$28 = 0.44444444444444442
|
So this is the total selectivity for the table t1
Now adding a breakpoint to table_cond_selectivity.
(gdb) where
|
#0 table_cond_selectivity (join=0x7fffe0008658, idx=0, s=0x7fffe00091f8, rem_tables=2) at /home/varunraiko/MariaDB/10.1/sql/sql_select.cc:7647
|
#1 0x0000555555a812dd in best_extension_by_limited_search (join=0x7fffe0008658, remaining_tables=3, idx=0, record_count=1, read_time=0,
|
search_depth=62, prune_level=1, use_cond_selectivity=3) at /home/varunraiko/MariaDB/10.1/sql/sql_select.cc:8008
|
Inside the function table_cond_selectivity we have
ref access on table t1 is with index b
(gdb) p pos->key
|
$30 = 1
|
(gdb) p table->quick_rows[key]
|
$34 = 1
|
(gdb) p table->stat_records()
|
$35 = 3
|
Then we discount the selectivty of b IS NULL from the total selectivity of the
table t1
sel /= (double)table->quick_rows[key] / (double) table->stat_records();
|
(gdb) p sel
|
$36 = 1.3333333333333333
|
So after discount the selectivity for (b IS NULL), we end up with sel=1.333
which is incorrect and this is why we hit the assert
|
TEST CASE #2
CREATE TABLE t1 (
|
a INT,
|
b INT NOT NULL,
|
c char(100),
|
KEY (b, c),
|
KEY (b, a, c)
|
)DEFAULT CHARSET = utf8;
|
|
INSERT INTO t1 VALUES
|
(1, 1, 1),
|
(2, 2, 2),
|
(3, 3, 3),
|
(4, 4, 4),
|
(5, 5, 5),
|
(6, 6, 6),
|
(7, 7, 7),
|
(8, 8, 8),
|
(9, 9, 9);
|
|
INSERT INTO t1 SELECT a + 10, b, c FROM t1;
|
INSERT INTO t1 SELECT a + 20, b, c FROM t1;
|
INSERT INTO t1 SELECT a + 40, b, c FROM t1;
|
INSERT INTO t1 SELECT a + 80, b, c FROM t1;
|
INSERT INTO t1 SELECT a + 160, b, c FROM t1;
|
INSERT INTO t1 SELECT a + 320, b, c FROM t1;
|
INSERT INTO t1 SELECT a + 640, b, c FROM t1;
|
INSERT INTO t1 SELECT a + 1280, b, c FROM t1 LIMIT 80;
|
|
set optimizer_use_condition_selectivity=2;
|
EXPLAIN SELECT a FROM t1 WHERE b = 1 ORDER BY c DESC LIMIT 9;
|
This is also crashes when I added the ASSERT for sel in (0,1]
Analysis
Here I will use the optimizer trace to demonstrate the problem. Now I will run
the query without the ASSERT so that I could see the estimates in the optimizer
trace
{
|
"range_scan_alternatives": [
|
{
|
"index": "b",
|
"ranges": ["(1) <= (b) <= (1)"],
|
"rowid_ordered": false,
|
"using_mrr": false,
|
"index_only": false,
|
"rows": 226,
|
"cost": 409.38,
|
"chosen": false,
|
"cause": "cost"
|
},
|
{
|
"index": "b_2",
|
"ranges": ["(1) <= (b) <= (1)"],
|
"rowid_ordered": false,
|
"using_mrr": false,
|
"index_only": true,
|
"rows": 222,
|
"cost": 135.96,
|
"chosen": true
|
}
|
],
|
"chosen_range_access_summary": {
|
"range_access_plan": {
|
"type": "range_scan",
|
"index": "b_2",
|
"rows": 222,
|
"ranges": ["(1) <= (b) <= (1)"]
|
},
|
"rows_for_plan": 222,
|
"cost_for_plan": 135.96,
|
"chosen": true
|
}
|
}
|
So here we see we have range access on index * b* and b_2
The estimate of records to be read for index b is 226
The estimate of records to be read for index b_2 is 222
So selectivity for table t1 (b=1) is :
"selectivity_for_indexes": [
|
{
|
"index_name": "b",
|
"selectivity_from_index": 0.1834
|
}
|
],
|
(gdb) p table_records
|
$1 = 1232
|
So we used index b to calculate the selectivity for the table t1.
Now we go the best_access_path to pick the best access on table t1, here we pick to do ref access with index b_2
"considered_access_paths": [
|
{
|
"access_type": "ref",
|
"index": "b",
|
"used_range_estimates": true,
|
"rows": 226,
|
"cost": 124,
|
"chosen": true
|
},
|
{
|
"access_type": "ref",
|
"index": "b_2",
|
"used_range_estimates": true,
|
"rows": 222,
|
"cost": 124.73,
|
"chosen": true
|
},
|
Then in table_cond_selectivity we would discount the ref access selectvity for
index b_2 from the total_selectivity
selectivity from index b_2= 0.18019480
(gdb) p key
|
$7 = 1
|
(gdb) p table->quick_rows[key]
|
$8 = 222
|
(gdb) p table->stat_records()
|
$9 = 1232
|
(gdb) p (double)table->quick_rows[key] / (double) table->stat_records()
|
$6 = 0.18019480519480519
|
So here we do the discount of selectivity for index b_2
sel /= (double)table->quick_rows[key] / (double) table->stat_records();
|
Before discount total selectivity
(gdb) p sel
|
$10 = 0.18344155844155843
|
After discount total selectivity
(gdb) p sel
|
$11 = 1.0180180180180181
|
This is why we hit the assert.
|
|
Probably duplicates https://jira.mariadb.org/browse/MDEV-20424
|
|
Pushed to 10.1 and removed the assert that was added in MDEV-20576. That will be added again with MDEV-20595
|
|
It appears that "Fix Version/s" is incorrect due to the effects of the re-release that occurred due to MDEV-20987. The "Fix Version/s" field needs to be incremented by 1 for every release series, so it should be 10.1.44, 10.2.30, 10.3.21, 10.4.11.
|