[#MDEV-21633] Assertion `tmp >= 0' failed in best_access_path with rowid

[MDEV-21633] Assertion `tmp >= 0' failed in best_access_path with rowid_filter=ON Created: 2020-02-02 Updated: 2023-11-28
Status:	Stalled
Project:	MariaDB Server
Component/s:	Optimizer
Affects Version/s:	10.4, 10.5, 10.6, 10.7, 10.8, 10.9
Fix Version/s:	10.4, 10.5, 10.6, 10.11

Type:

Bug

Priority:

Major

Reporter:

Elena Stepanova

Assignee:

Igor Babaev

Resolution:

Unresolved

Votes:

Labels:

not-11.0+

Issue Links:

Blocks
is blocked by	MDEV-20743	Revise patches that fixed calculation...	Stalled
Duplicate
duplicates	~~MDEV-22183~~	Assertion `tmp >= 0' failed in best_...	Closed
PartOf
is part of	~~MDEV-22537~~	optimizer_use_cond_selectivity > 1 ca...	Closed
Relates
relates to	MDEV-23707	Fix condition selectivity computation...	Stalled
relates to	MDEV-20595	Assertion `0 < sel && sel <= 2.0' fai...	Stalled
relates to	~~MDEV-22183~~	Assertion `tmp >= 0' failed in best_...	Closed

Description

SET optimizer_switch='rowid_filter=on';

CREATE TABLE t1 (

    pk INT AUTO_INCREMENT,

    a INT,

    b VARCHAR(8),

    KEY(a),

    PRIMARY KEY(pk),

    KEY (a,pk)

) ENGINE=MyISAM;

INSERT INTO t1 (a,b) VALUES

    (NULL,'d'),(9,'b'),(2,'x'),(5,'k'),(NULL,'d'),(3,'s'),(5,'k'),(1,'r'),

    (8,'l'),(3,'z'),(1,'c'),(1,'q'),(NULL,'x'),(NULL,'p'),(NULL,'z'),(7,'a'),

    (0,'i'),(3,'s'),(NULL,'h'),(4,'p'),(1,'i'),(4,'f'),(1,'c'),(NULL,'a'),

    (NULL,'x'),(1,'b'),(NULL,'n'),(NULL,'h'),(5,'i'),(6,'e'),(NULL,'i'),

    (7,'e'),(1,'r'),(NULL,'z'),(1,'i'),(14,'c'),(6,'u'),(3,'b'),(4,'z'),

    (2,'c'),(70,'d'),(NULL,'p'),(21,'j'),(6,'e'),(5,'c'),(13,'i'),(42,'d'),

    (80,'s'),(14,'t'),(9,'a'),(0,'2'),(0,NULL),(0,NULL),(0,NULL),(0,''),

    (0,''),(0,'1'),(0,''),(0,''),(0,''),(0,''),(0,NULL),(0,''),(0,''),(0,''),

    (0,NULL),(0,''),(0,''),(0,''),(0,''),(0,''),(0,''),(0,NULL),(0,NULL),

    (0,NULL),(0,''),(0,''),(0,''),(0,''),(0,NULL),(0,''),(0,NULL),(0,NULL),

    (0,''),(0,''),(0,''),(0,NULL),(0,''),(0,NULL),(0,''),(0,''),(0,''),(0,''),

    (0,''),(0,''),(0,''),(0,NULL),(0,''),(0,NULL),(0,'');

CREATE TABLE t2 (c INT) ENGINE=MyISAM;

INSERT INTO t2 VALUES (1),(2),(3),(4),(5),(6);

SELECT * FROM t1 JOIN t2 WHERE a = c AND pk BETWEEN 4 AND 7 AND a BETWEEN 2 AND 12 AND b != 'foo';

# Cleanup

DROP TABLE t1, t2;

10.4 d87b725e
mysqld: /data/src/10.4/sql/sql_select.cc:7903: void best_access_path(JOIN, JOIN_TAB, table_map, const POSITION, uint, bool, double, POSITION, POSITION*): Assertion `tmp >= 0' failed.
200202 20:01:32 [ERROR] mysqld got signal 6 ;

#7 0x00007f505de2af12 in __GI___assert_fail (assertion=0x564f2cf10b07 "tmp >= 0", file=0x564f2cf0f988 "/data/src/10.4/sql/sql_select.cc", line=7903, function=0x564f2cf13fc0 <best_access_path(JOIN, st_join_table, unsigned long long, st_position const, unsigned int, bool, double, st_position, st_position)::__PRETTY_FUNCTION__> "void best_access_path(JOIN, JOIN_TAB, table_map, const POSITION, uint, bool, double, POSITION, POSITION)") at assert.c:101
#8 0x0000564f2c25eb79 in best_access_path (join=0x7f503c016800, s=0x7f503c0178e0, remaining_tables=1, join_positions=0x7f503c018250, idx=1, disable_jbuf=false, record_count=6, pos=0x7f503c018380, loose_scan_pos=0x7f504bfb1580) at /data/src/10.4/sql/sql_select.cc:7903
#9 0x0000564f2c262b33 in best_extension_by_limited_search (join=0x7f503c016800, remaining_tables=1, idx=1, record_count=6, read_time=3.2102539062500002, search_depth=61, prune_level=1, use_cond_selectivity=4) at /data/src/10.4/sql/sql_select.cc:9464
#10 0x0000564f2c263283 in best_extension_by_limited_search (join=0x7f503c016800, remaining_tables=3, idx=0, record_count=1, read_time=0, search_depth=62, prune_level=1, use_cond_selectivity=4) at /data/src/10.4/sql/sql_select.cc:9550
#11 0x0000564f2c260abf in greedy_search (join=0x7f503c016800, remaining_tables=3, search_depth=62, prune_level=1, use_cond_selectivity=4) at /data/src/10.4/sql/sql_select.cc:8668
#12 0x0000564f2c25fd0c in choose_plan (join=0x7f503c016800, join_tables=3) at /data/src/10.4/sql/sql_select.cc:8233
#13 0x0000564f2c25782c in make_join_statistics (join=0x7f503c016800, tables_list=..., keyuse_array=0x7f503c016af0) at /data/src/10.4/sql/sql_select.cc:5542
#14 0x0000564f2c24b6c2 in JOIN::optimize_inner (this=0x7f503c016800) at /data/src/10.4/sql/sql_select.cc:2251
#15 0x0000564f2c249002 in JOIN::optimize (this=0x7f503c016800) at /data/src/10.4/sql/sql_select.cc:1598
#16 0x0000564f2c25445c in mysql_select (thd=0x7f503c000af0, tables=0x7f503c013880, wild_num=1, fields=..., conds=0x7f503c0155e0, og_num=0, order=0x0, group=0x0, having=0x0, proc_param=0x0, select_options=2147748608, result=0x7f503c0167d8, unit=0x7f503c004a18, select_lex=0x7f503c0132c0) at /data/src/10.4/sql/sql_select.cc:4652
#17 0x0000564f2c2440a6 in handle_select (thd=0x7f503c000af0, lex=0x7f503c004958, result=0x7f503c0167d8, setup_tables_done_option=0) at /data/src/10.4/sql/sql_select.cc:420
#18 0x0000564f2c20a7f7 in execute_sqlcom_select (thd=0x7f503c000af0, all_tables=0x7f503c013880) at /data/src/10.4/sql/sql_parse.cc:6360
#19 0x0000564f2c1ffecd in mysql_execute_command (thd=0x7f503c000af0) at /data/src/10.4/sql/sql_parse.cc:3899
#20 0x0000564f2c20e903 in mysql_parse (thd=0x7f503c000af0, rawbuf=0x7f503c013198 "SELECT * FROM t1 JOIN t2 WHERE a = c AND pk BETWEEN 4 AND 7 AND a BETWEEN 2 AND 12 AND b != 'foo'", length=97, parser_state=0x7f504bfb3160, is_com_multi=false, is_next_command=false) at /data/src/10.4/sql/sql_parse.cc:7901
#21 0x0000564f2c1f9ad0 in dispatch_command (command=COM_QUERY, thd=0x7f503c000af0, packet=0x7f503c0083a1 "SELECT * FROM t1 JOIN t2 WHERE a = c AND pk BETWEEN 4 AND 7 AND a BETWEEN 2 AND 12 AND b != 'foo'", packet_length=97, is_com_multi=false, is_next_command=false) at /data/src/10.4/sql/sql_parse.cc:1842
#22 0x0000564f2c1f815d in do_command (thd=0x7f503c000af0) at /data/src/10.4/sql/sql_parse.cc:1360
#23 0x0000564f2c381377 in do_handle_one_connection (connect=0x564f307ac630) at /data/src/10.4/sql/sql_connect.cc:1412
#24 0x0000564f2c3810c6 in handle_one_connection (arg=0x564f307ac630) at /data/src/10.4/sql/sql_connect.cc:1316
#25 0x0000564f2cd898c9 in pfs_spawn_thread (arg=0x564f306d04f0) at /data/src/10.4/storage/perfschema/pfs.cc:1869
#26 0x00007f505fdb34a4 in start_thread (arg=0x7f504bfb4700) at pthread_create.c:456
#27 0x00007f505dee7d0f in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:97

EXPLAIN also crashes.
Not reproducible with rowid_filter=off.
No obvious problem on a non-debug build.

Comments

Comment by Igor Babaev [ 2020-02-04 ]

Analysis:
When the optimizer considers joining table t1 to table t2 using the best range scan by index pk and a join cache to estimate the cost of such join extension it has to figure out how many rows will be filtered out when performing the index scan. For this purpose the optimizer calls matching_candidates_in_table(). When use_cond_selectivity > 1
the function just multiplies number of records in t2 by t1->cond_selectivity previously calculated in calculate_cond_selectivity_for_table(). The current code of calculate_cond_selectivity_for_table() that appeared after the changes of the commit 26a3d567c9435cd593d7afac8a0f1d00def50740 calculates the selectivity of the conditions for t1 as 0.34 which is absurd as the selectivity of only one condition pk BETWEEN 4 AND 7 is much less than this. Apparently the code of the commit follows some wrong logic. This was noticed for many other cases and MDEV-20743 has to fix it. In the reported test case this bug makes the difference s->found_records - rnd_records negarive and as result after the cost of filtering out is added of the current cost of the join operation the current cost becomes less than it used to be. It does not make sense to investigate further changes of this cost.

Most probably the bug can be reproduced with 10.1 with some other tests cases

I would recommend to add the assertion

DBUG_ASSERT(s->found_records >= rnd_records)

before the code

double cmp_time= (s->found_records - rnd_records)/(double) TIME_FOR_COMPARE;

Comment by Igor Babaev [ 2020-02-06 ]

Let's turn rowid filter optimization off to avoid crashes

set optimizer_switch='rowid_filter=off';

and slightly change the query to make (s->quick->read_time + cmp_time) negative

SELECT * FROM t1 JOIN t2 WHERE a = c AND pk BETWEEN 4 AND 6 AND a BETWEEN 2 AND 12 AND b != 'foo';

Now let's enable optimizer trace, run the query and read optimizer trace. We see that the cost to join table t2 is
equal to COST_MAX:

                          "access_type": "range",

                          "resulting_rows": 34,

                          "cost": 2e308,

                          "chosen": false

This is really no good.
Let's run the query

SELECT * FROM t1 WHERE pk BETWEEN 4 AND 6 AND a BETWEEN 2 AND 12 AND b != 'foo';

Again optimizer trace reports the cost as "cost": 2e308
Let's create a new table and populate it with some data:

CREATE TABLE t3 (d varchar(8), e int, INDEX (d)) ENGINE=MyISAM;

INSERT INTO t3  VALUES ('d',10), ('ddd',12), ('dd',17), ('f',20), ('ff',23), ('fff',27);

Now let's get the best execution plan for the query:

SELECT * FROM t1,t3

WHERE pk BETWEEN 4 AND 6 AND a BETWEEN 2 AND 12 AND b != 'foo' AND d=b AND d BETWEEN 'fff' AND 'ggg';

We see that the optimizer chooses the join order (t3,t1) and employs a join cache

MariaDB [test]> EXPLAIN EXTENDED SELECT * FROM t1,t3 WHERE pk BETWEEN 4 AND 6 AND a BETWEEN 2 AND 12 AND b != 'foo' AND d=b AND d BETWEEN 'fff' AND 'ggg';

+------+-------------+-------+-------+---------------+---------+---------+------+------+----------+------------------------------------------------------------------------+

| id   | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | filtered | Extra                                                                  |

+------+-------------+-------+-------+---------------+---------+---------+------+------+----------+------------------------------------------------------------------------+

|    1 | SIMPLE      | t3    | range | d             | d       | 11      | NULL | 2    |   100.00 | Using index condition                                                  |

|    1 | SIMPLE      | t1    | range | PRIMARY,a,a_2 | PRIMARY | 4       | NULL | 3    |   100.00 | Using index condition; Using where; Using join buffer (flat, BNL join) |

+------+-------------+-------+-------+---------------+---------+---------+------+------+----------+------------------------------------------------------------------------+

though the plan that uses the join order (t1,t3) and a ref access to t3 is apparently cheaper.

Comment by Sergei Petrunia [ 2020-02-28 ]

Studying why does the optimizer get a cost of 2e308 for the query:

SELECT * FROM t1 WHERE pk BETWEEN 4 AND 6 AND a BETWEEN 2 AND 12 AND b != 'foo';

WHERE

  pk BETWEEN 4 AND 6 AND

  a BETWEEN 2 AND 12

  AND b != 'foo';

Indexes:

  PRIMARY KEY (pk),

  KEY a (a),

  KEY a_2 (a,pk)

Range analysis:

table_rows=100.

  PRIMARY KEY (pk), -- quick_rows=3 , quick_key_parts=1

  KEY a (a),        -- quick_rows=11, quick_key_parts=1

  KEY a_2 (a,pk)    -- quick_rows=34, quick_key_parts=2

calculate_cond_selectivity_for_table() starts to compute the selectivity by first taking into account indexes with more key parts.

index a_2: selectivity=0.34

Indexes PK and a are then not taken into account as their first component is already "handled" by quick select on a_2.

As a result, table->cond_selectivity=0.34.
(Note that this "contradicts" to the table's best quick select on pk which has quick->records=3.

Then we reach best_access_path:

       double cmp_time= (s->found_records - rnd_records)/(double) TIME_FOR_COMPARE;

(gdb) p s->found_records

  $33 = 3

(gdb) p rnd_records

  $34 = 34

(gdb) print cmp_time

  $35 = -6.2000000000000002

cmp_time is negative.

      tmp= COST_MULT(record_count,

                     COST_ADD(s->quick->read_time, cmp_time));

(gdb) print cmp_time

  $35 = -6.2000000000000002

(gdb) print record_count

  $36 = 1

(gdb) p s->quick->read_time

  $37 = 5.0058536585365854

Here

COST_ADD(s->quick->read_time, cmp_time)= COST_ADD(5.0058, -6.200)= -1.19415

Then we compute

COST_MULT(1, -1.19)

#define COST_MULT(c,f) (COST_MAX / (f) > (c) ? (c) * (f) : COST_MAX)

(COST_MAX/-1.19 > 1) computes to false

and the result of computation is COST_MAX.

Comment by Alice Sherepa [ 2020-08-07 ]

Somehow test from the description passes on 10.5 bbd70fcc43cc889e4593594ee5, but test from ~~MDEV-22183~~ fails on both 10.4,10.5

SET optimizer_switch='rowid_filter=on';

create table t1 (pk int not null primary key, i1 varchar(10), i2 int, i3 int , key i2 (i2), key (i2,i3,pk)) engine=myisam;

insert into t1 values (45,null,null,null),(46,null,null,null),(44,null,null,null),(43,null,null,null),(49,null,null,null),(50,null,null,null),(51,null,null,null),(52,null,null,null),(53,null,null,null),(54,null,null,null),(55,null,null,null),(56,null,null,null),(57,null,null,null),(58,null,null,null),(59,null,null,null),(60,null,null,null),(61,null,null,null),(62,null,null,null),(63,null,null,null),(64,null,null,null),(65,null,null,null);

select straight_join  1

from t1 join t1 as a2 on t1.i1 = a2.i1

where a2.pk > 4 and a2.pk < 6

  and a2.i3 >= 2 and a2.i2 in (4, 6, 7);

Comment by Igor Babaev [ 2021-11-05 ]

The problem can be demonstrated with the following example:

create table t1 (

  pk1 int primary key,

  a int,

  b int,

  f char(255) default " ",

  index a_b(a,b),

  index b(b)

) engine=myisam;

insert into t1(pk1, a, b)

  select seq, (rand(101)*1000) mod 20, (rand(113)*1000) mod 20  from seq_1_to_1000;

create table t2 (

  pk2 int primary key,

  fk1 int,

  c int,

  f char(255) default " ",

  index fk1(fk1),

  index c(c)

) engine myisam;

insert into t2(pk2, fk1, c)

  select seq, (rand(11)*5000) mod 1000, (rand(13)*5000) mod 500  from seq_1_to_5000;

analyze table t1,t2,t3 persistent for all;

set optimizer_switch='rowid_filter=off';

select * from t1 join t2 on fk1=pk1

   where a between 5 and 7 and b in (3,1) and c between 100 and 129;

Let's see what we have in EXPLAIN EXTENDED for this query:

explain extended select * from t1 join t2 on fk1=pk1 where a between 5 and 7 and b in (3,1) and c between 100 and 129;

+------+-------------+-------+--------+---------------+---------+---------+-------------+------+----------+------------------------------------+

| id   | select_type | table | type   | possible_keys | key     | key_len | ref         | rows | filtered | Extra                              |

+------+-------------+-------+--------+---------------+---------+---------+-------------+------+----------+------------------------------------+

|    1 | SIMPLE      | t2    | range  | fk1,c         | c       | 5       | NULL        | 280  |   100.00 | Using index condition; Using where |

|    1 | SIMPLE      | t1    | eq_ref | PRIMARY,a_b,b | PRIMARY | 4       | test.t2.fk1 | 1    |     9.50 | Using where                        |

+------+-------------+-------+--------+---------------+---------+---------+-------------+------+----------+------------------------------------+

So it is expected about 27 rows (280*9.50) in the result set. I fact we have:

MariaDB [test]> select * from t1 join t2 on fk1=pk1 where a between 5 and 7 and b in (3,1) and c between 100 and 129;

+-----+------+------+------+------+------+------+------+

| pk1 | a    | b    | f    | pk2  | fk1  | c    | f    |

+-----+------+------+------+------+------+------+------+

| 379 |    7 |    3 |      | 1423 |  379 |  100 |      |

| 228 |    5 |    3 |      | 1016 |  228 |  119 |      |

| 353 |    7 |    3 |      | 1158 |  353 |  127 |      |

+-----+------+------+------+------+------+------+------+

3 rows in set (0.009 sec)

Let's see at the selectivities of the range conditions.
For the condition (a between 5 and 7) we have:

MariaDB [test]> explain extended select * from t1 where a between 5 and 7;

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                 |

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

|    1 | SIMPLE      | t1    | range | a_b           | a_b  | 5       | NULL | 146  |   100.00 | Using index condition |

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

1 row in set, 1 warning (0.001 sec)

MariaDB [test]> select count(*) from t1 where a between 5 and 7;

+----------+

| count(*) |

+----------+

|      147 |

+----------+

1 row in set (0.002 sec)

For the condition (b in (3,1)) we have:

MariaDB [test]> explain extended select * from t1 where b in (3,1);+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                 |

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

|    1 | SIMPLE      | t1    | range | b             | b    | 5       | NULL | 89   |   100.00 | Using index condition |

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

1 row in set, 1 warning (0.002 sec)

MariaDB [test]> select count(*) from t1 where b in (3,1);

+----------+

| count(*) |

+----------+

|       90 |

+----------+

1 row in set (0.002 sec)

For the condition ( c between 100 and 129) we have:

MariaDB [test]> explain extended select * from t2 where c between 100 and 129;+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                 |

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

|    1 | SIMPLE      | t2    | range | c             | c    | 5       | NULL | 280  |   100.00 | Using index condition |

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

1 row in set, 1 warning (0.001 sec)

MariaDB [test]> select count(*) from t2 where c between 100 and 129;

+----------+

| count(*) |

+----------+

|      283 |

+----------+

1 row in set (0.003 sec)

So far so good.
Let's see at the selectivity of the condition (a between 5 and 7 and b in (3,1))

MariaDB [test]> explain extended select * from t1 where a between 5 and 7 and b in (3,1);+------+-------------+-------+-------+---------------+------+---------+------+------+----------+------------------------------------+

| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                              |

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+------------------------------------+

|    1 | SIMPLE      | t1    | range | a_b,b         | b    | 5       | NULL | 89   |   100.00 | Using index condition; Using where |

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+------------------------------------+

1 row in set, 1 warning (0.001 sec)

MariaDB [test]> select count(*) from t1 where a between 5 and 7 and b in (3,1);

+----------+

| count(*) |

+----------+

|       14 |

+----------+

1 row in set (0.002 sec)

This is not good at all: the optimizer decides that the selectivity of the condition
(a between 5 and 7 and b in (3,1)) is the same as the selectivity of the condition (b in (3,1)) though there is no correlation between values in columns a and b.
We would expect selectivity equal to (146/1000) * (89/1000)=12.99 and with this selectivity we would expect 13 rows in the result set and this is pretty close to actual 14 rows.
Lets change the condition (b in (3,1)) with the condition ((3,1,13)):

MariaDB [test]> explain extended select * from t1 where b in (3,1,13);

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                 |

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

|    1 | SIMPLE      | t1    | range | b             | b    | 5       | NULL | 138  |   100.00 | Using index condition |

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

1 row in set, 1 warning (0.002 sec)

MariaDB [test]> select count(*) from t1 where b in (3,1,13);

+----------+

| count(*) |

+----------+

|      140 |

+----------+

1 row in set (0.002 sec)

Now we have:

MariaDB [test]> explain extended select * from t1 where a between 5 and 7 and b in (3,1,13);

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                 |

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

|    1 | SIMPLE      | t1    | range | a_b,b         | a_b  | 10      | NULL | 122  |   100.00 | Using index condition |

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

1 row in set, 1 warning (0.002 sec)

MariaDB [test]> select count(*) from t1 where a between 5 and 7 and b in (3,1,13);

+----------+

| count(*) |

+----------+

|       23 |

+----------+

1 row in set (0.002 sec)

Now we see that selectivity of the condition (b in (3,1,13)) is partly ignored. Actually selectivity only of these sub-ranges are taken into account: (a=5 and b < 1) and (a=7 and b > 13):

MariaDB [test]> explain extended select * from t1 where a=7 and b > 13;

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                 |

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

|    1 | SIMPLE      | t1    | range | a_b,b         | a_b  | 10      | NULL | 24   |   100.00 | Using index condition |

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

1 row in set, 1 warning (0.001 sec)

MariaDB [test]> explain extended select * from t1 where a=5 and b < 1;

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

| id   | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                 |

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

|    1 | SIMPLE      | t1    | range | a_b,b         | a_b  | 10      | NULL | 1    |   100.00 | Using index condition |

+------+-------------+-------+-------+---------------+------+---------+------+------+----------+-----------------------+

1 row in set, 1 warning (0.002 sec)

Comment by Igor Babaev [ 2021-11-05 ]

Now let's see how the ignored selectivity of the condition (a between 5 and 7) affects the optimizer choice of the best execution plan for the query:

select * from t1 join t2 on fk1=pk1

   where a between 5 and 7 and b in (3,1) and c between 100 and 129;

We saw that the optimizer chose a plan with the join order (t2,t1):

MariaDB [test]> explain extended select * from t1 join t2 on fk1=pk1    where a between 5 and 7 and b in (3,1) and c between 100 and 129;

+------+-------------+-------+--------+---------------+---------+---------+-------------+------+----------+------------------------------------+

| id   | select_type | table | type   | possible_keys | key     | key_len | ref         | rows | filtered | Extra                              |

+------+-------------+-------+--------+---------------+---------+---------+-------------+------+----------+------------------------------------+

|    1 | SIMPLE      | t2    | range  | fk1,c         | c       | 5       | NULL        | 280  |   100.00 | Using index condition; Using where |

|    1 | SIMPLE      | t1    | eq_ref | PRIMARY,a_b,b | PRIMARY | 4       | test.t2.fk1 | 1    |     9.50 | Using where                        |

+------+-------------+-------+--------+---------------+---------+---------+-------------+------+----------+------------------------------------+

Lets see how good it is:

MariaDB [test]> flush status;

Query OK, 0 rows affected (0.000 sec)

MariaDB [test]> select * from t1 join t2 on fk1=pk1    where a between 5 and 7 and b in (3,1) and c between 100 and 129;

+-----+------+------+------+------+------+------+------+

| pk1 | a    | b    | f    | pk2  | fk1  | c    | f    |

+-----+------+------+------+------+------+------+------+

| 379 |    7 |    3 |      | 1423 |  379 |  100 |      |

| 228 |    5 |    3 |      | 1016 |  228 |  119 |      |

| 353 |    7 |    3 |      | 1158 |  353 |  127 |      |

+-----+------+------+------+------+------+------+------+

3 rows in set (0.007 sec)

MariaDB [test]> show status like "Handler_read%";                                                               +--------------------------+-------+

| Variable_name            | Value |

+--------------------------+-------+

| Handler_read_first       | 0     |

| Handler_read_key         | 284   |

| Handler_read_last        | 0     |

| Handler_read_next        | 283   |

| Handler_read_prev        | 0     |

| Handler_read_retry       | 0     |

| Handler_read_rnd         | 0     |

| Handler_read_rnd_deleted | 0     |

| Handler_read_rnd_next    | 0     |

+--------------------------+-------+

9 rows in set (0.007 sec)

Let's force the join order (t1,t2):

MariaDB [test]> explain extended select * from t1 straight_join t2 on fk1=pk1    where a between 5 and 7 and b in (3,1) and c between 100 and 129;

+------+-------------+-------+-------+---------------+------+---------+-------------+------+----------+------------------------------------+

| id   | select_type | table | type  | possible_keys | key  | key_len | ref         | rows | filtered | Extra                              |

+------+-------------+-------+-------+---------------+------+---------+-------------+------+----------+------------------------------------+

|    1 | SIMPLE      | t1    | range | PRIMARY,a_b,b | b    | 5       | NULL        | 89   |   100.00 | Using index condition; Using where |

|    1 | SIMPLE      | t2    | ref   | fk1,c         | fk1  | 5       | test.t1.pk1 | 5    |     5.60 | Using where                        |

+------+-------------+-------+-------+---------------+------+---------+-------------+------+----------+------------------------------------+

MariaDB [test]> flush status;

Query OK, 0 rows affected (0.000 sec)

MariaDB [test]> select * from t1 straight_join t2 on fk1=pk1    where a between 5 and 7 and b in (3,1) and c between 100 and 129;

+-----+------+------+------+------+------+------+------+

| pk1 | a    | b    | f    | pk2  | fk1  | c    | f    |

+-----+------+------+------+------+------+------+------+

| 228 |    5 |    3 |      | 1016 |  228 |  119 |      |

| 353 |    7 |    3 |      | 1158 |  353 |  127 |      |

| 379 |    7 |    3 |      | 1423 |  379 |  100 |      |

+-----+------+------+------+------+------+------+------+

3 rows in set (0.007 sec)

MariaDB [test]> show status like "Handler_read%";

+--------------------------+-------+

| Variable_name            | Value |

+--------------------------+-------+

| Handler_read_first       | 0     |

| Handler_read_key         | 16    |

| Handler_read_last        | 0     |

| Handler_read_next        | 162   |

| Handler_read_prev        | 0     |

| Handler_read_retry       | 0     |

| Handler_read_rnd         | 0     |

| Handler_read_rnd_deleted | 0     |

| Handler_read_rnd_next    | 0     |

+--------------------------+-------+

9 rows in set (0.005 sec)

We see that the chosen plan is actually essentially worse than the last one.

Comment by Igor Babaev [ 2021-11-06 ]

Here are some other observations we can get when looking through the optimizer trace for the query:

                  "chosen_range_access_summary": {

                    "range_access_plan": {

                      "type": "range_scan",

                      "index": "b",

                      "rows": 89,

                      "ranges": ["(1) <= (b) <= (1)", "(3) <= (b) <= (3)"]

},

                    "rows_for_plan": 89,

                    "cost_for_plan": 113.71,

                    "chosen": true

The above means that the best single-index range scan is by index b that is expected to fetch 89 records and its cost is 113.71.
At the same time we see further that the selectivity of the conditions pushed to the table t1 is "cond_selectivity": 0.095.
It means that the selectivity of the condition (a between 5 and 7 and b in (3,1)) is bigger than the selectivity of the condition b in (3,1). This is not good. In particular it leads to the following:

                "best_access_path": {

                  "considered_access_paths": [

                      "access_type": "range",

                      "resulting_rows": 95,

                      "cost": 112.51,

                      "chosen": true

],

                  "chosen_access_method": {

                    "type": "range",

                    "records": 95,

                    "cost": 112.51,

                    "uses_join_buffering": false

The debugger shows that the best access is still the range scan by index b. Yet all of a sudden its cost has become smaller while the expected number of records to scan has become bigger.

Comment by Michael Widenius [ 2022-04-13 ]

I checked the original query that caused a crash with 10.7-selectivty tree and this didn't crash.
I am now adding the test case to the 10.7-selectivty tree.

Comment by Michael Widenius [ 2022-04-13 ]

I checked also this query in the 10.7-selectivty tree:

explain select * from t1 join t2 on fk1=pk1 where a between 5 and 7 and b in (3,1) and c between 100 and 129;

select_type

table

type

possible_keys

key

key_len

ref

rows

Extra

----------------------------------------------------------------------------------------------------+

1	SIMPLE	t1	range	PRIMARY,a_b,b	b	5	NULL	89	Using index condition; Using where
1	SIMPLE	t2	ref	fk1,c	fk1	5	test.t1.pk1	5	Using where

----------------------------------------------------------------------------------------------------+

Which is the better plan, as Igor showed above

Comment by Alice Sherepa [ 2022-07-19 ]

the test below crashes in a similar way on current 10.5-10.11, but not on 11.0-11.3:

--source include/have_innodb.inc

CREATE TABLE t1 (i1 int, i2 int, pk int, i3 bigint(20), PRIMARY KEY (pk), KEY i1 (i1), KEY (i2), KEY (pk,i3)) engine=innodb;

INSERT INTO `t1` VALUES (1,0,10000,NULL),(15148,0,9999,8),(32767,0,9998,0),(0,0,9997,0),(-18277,0,9996,61385),(32,0,9995,466966986362978304),(NULL,0,9994,0),(6,0,9993,0),(0,0,9992,9),(0,0,9991,20834),(NULL,0,9990,7657808216390107136),(32767,0,9989,3),(6,0,9988,55823),(-18240,0,9987,0),(32767,0,9986,-5713379077272895488),(3,0,9985,58),(0,0,9984,0),(32767,0,9983,0),(6,0,9982,245),(204,0,9981,NULL),(0,0,9980,19376),(9,0,9979,4),(0,0,9978,244),(NULL,0,9977,47664),(17714,0,9976,NULL),(11754,0,9975,108),(32767,0,9974,-2686397177726500864),(NULL,0,9973,5644980657932206080),(NULL,0,9972,48719),(61,0,9971,10274),(32767,0,9970,3),(-23461,0,9969,30997),(2145,0,9968,NULL),(NULL,0,9967,0),(17192,0,9966,NULL),(1,0,9965,0),(3477,0,9964,7),(0,0,9963,NULL),(4,0,9962,50401),(NULL,0,9961,0),(4,0,9960,0),(0,0,9959,NULL),(15801,0,9958,0),(21765,0,9957,0),(4014,0,9956,0),(0,0,9955,NULL),(131,0,9954,0),(0,0,9953,59939),(1395,0,9952,5941373808408526848),(NULL,0,9951,30),(13990,0,9950,NULL),(NULL,0,9949,2),(176,0,9948,45515),(0,0,9947,-8914875462379896832),(238,0,9946,240),(42,0,9945,-6838153084208676864),(3,0,9944,5),(0,0,9943,55),(79,0,9942,5),(0,0,9941,137),(3312,0,9940,61748),(32767,0,9939,0),(24517,0,9938,0),(NULL,0,9937,221),(84,0,9936,1749085505280016384),(4,0,9935,54148),(0,0,9934,20960),(32767,0,9933,1),(212,0,9932,0),(2,0,9931,0),(23611,0,9930,-5848205591117299712),(32767,0,9929,3995),(32767,0,9928,0),(32767,0,9927,12776),(3,0,9926,1),(9,0,9925,624),(0,0,9924,-8148419100796780544),(-19664,0,9923,31767),(NULL,0,9922,71),(-17343,0,9921,NULL),(0,0,9920,0),(17366,0,9919,4354417889713848320),(158,0,9918,36),(656,0,9917,NULL),(12324,0,9916,37961),(0,0,9915,1),(1,0,9914,NULL),(15800,0,9913,NULL),(8,0,9912,0),(32767,0,9911,5),(19059,0,9910,3),(NULL,0,9909,8021),(NULL,0,9908,NULL),(-17259,0,9907,1611444241668505600),(32767,0,9906,2),(NULL,0,9905,NULL),(0,0,9904,-5634847558770622464),(-32271,0,9903,194),(0,0,9902,168),(32767,0,9901,0),(0,0,9900,6),(2168,0,9899,9),(152,0,9898,9),(15416,0,9897,0),(NULL,0,9896,0),(14830,0,9895,15760),(0,0,9894,4),(NULL,0,9893,0),(0,0,9892,11604),(1,0,9891,237),(0,0,9890,63),(9,0,9889,24134),(21694,0,9888,4),(NULL,0,9887,0),(NULL,0,9886,5),(18578,0,9885,3),(0,0,9884,5026017184145473536),(70,0,9883,0),(0,0,9882,0),(NULL,0,9881,NULL),(NULL,0,9880,18026),(205,0,9879,6),(NULL,0,9878,0),(7,0,9877,49757),(30211,0,9876,124),(32191,0,9875,9141181343655264256),(185,0,9874,4941293216155566080),(23118,0,9873,0),(122,0,9872,8056376783412396032),(0,0,9871,28757),(NULL,0,9870,6),(27851,0,9869,6),(0,0,9868,1),(0,0,9867,0),(0,0,9866,9),(32767,0,9865,160),(-13425,0,9864,8),(NULL,0,9863,60017),(218,0,9862,-2239696389686689792),(0,0,9861,NULL),(0,0,9860,53921),(NULL,0,9859,57148),(10148,0,9858,6),(NULL,0,9857,2);

optimize table t1;

SET optimizer_switch='rowid_filter=on';

SELECT  * FROM t1

WHERE (i1 IN (2,5,1,7,9) AND i2 IN (1,7)) AND  (pk IN (98,0) OR pk = 255)  AND i1 IN (3,1)  ;

10.5 8494758e8e06aea5c8d4cddc

mariadbd: /10.5/src/sql/sql_select.cc:8124: void best_access_path(JOIN, JOIN_TAB, table_map, const POSITION, uint, bool, double, POSITION, POSITION*): Assertion `tmp >= 0' failed.
220719 18:04:40 [ERROR] mysqld got signal 6 ;

Server version: 10.5.17-MariaDB-debug-log

??:0(__assert_fail)[0x7f3b21e35fd6]
sql/sql_select.cc:8126(best_access_path(JOIN, st_join_table, unsigned long long, POSITION const, unsigned int, bool, double, POSITION, POSITION*))[0x564bd7edd8c5]
sql/sql_select.cc:9724(best_extension_by_limited_search(JOIN*, unsigned long long, unsigned int, double, double, unsigned int, unsigned int, unsigned int))[0x564bd7ee603e]
sql/sql_select.cc:8893(greedy_search(JOIN*, unsigned long long, unsigned int, unsigned int, unsigned int))[0x564bd7ee1d3f]
sql/sql_select.cc:8458(choose_plan(JOIN*, unsigned long long))[0x564bd7edfa78]
sql/sql_select.cc:5691(make_join_statistics(JOIN, List<TABLE_LIST>&, st_dynamic_array))[0x564bd7ecaf5e]
sql/sql_select.cc:2313(JOIN::optimize_inner())[0x564bd7ea7ee0]
sql/sql_select.cc:1671(JOIN::optimize())[0x564bd7ea12c6]
sql/sql_select.cc:4783(mysql_select(THD, TABLE_LIST, List<Item>&, Item, unsigned int, st_order, st_order, Item, st_order, unsigned long long, select_result, st_select_lex_unit, st_select_lex))[0x564bd7ec1d14]
sql/sql_select.cc:444(handle_select(THD, LEX, select_result*, unsigned long))[0x564bd7e931fb]
sql/sql_parse.cc:6314(execute_sqlcom_select(THD, TABLE_LIST))[0x564bd7dfac4d]
sql/sql_parse.cc:4005(mysql_execute_command(THD*))[0x564bd7de9c42]
sql/sql_parse.cc:8100(mysql_parse(THD, char, unsigned int, Parser_state*, bool, bool))[0x564bd7e05f8a]
sql/sql_parse.cc:1894(dispatch_command(enum_server_command, THD, char, unsigned int, bool, bool))[0x564bd7ddbeb2]
sql/sql_parse.cc:1375(do_command(THD*))[0x564bd7dd8842]
sql/sql_connect.cc:1418(do_handle_one_connection(CONNECT*, bool))[0x564bd82269c0]
sql/sql_connect.cc:1314(handle_one_connection)[0x564bd82261d9]
perfschema/pfs.cc:2203(pfs_spawn_thread)[0x564bd8e9bbc0]
nptl/pthread_create.c:478(start_thread)[0x7f3b22350609]


Query (0x62b0000852a8): SELECT * FROM t1
WHERE (i1 IN (2,5,1,7,9) AND i2 IN (1,7)) AND (pk IN (98,0) OR pk = 255) AND i1 IN (3,1)

Generated at Thu Feb 08 09:08:38 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.

[MDEV-21633] Assertion `tmp >= 0' failed in best_access_path with rowid_filter=ON Created: 2020-02-02 Updated: 2023-11-28