[MDEV-27262] Unexpected index intersection with full index scan for an index Created: 2021-12-15  Updated: 2021-12-28  Resolved: 2021-12-25

Status: Closed
Project: MariaDB Server
Component/s: Optimizer
Fix Version/s: 10.2.42, 10.3.33, 10.4.23, 10.5.14, 10.6.6, 10.7.2

Type: Task Priority: Major
Reporter: Igor Babaev Assignee: Igor Babaev
Resolution: Fixed Votes: 0
Labels: None

Issue Links:
Problem/Incident
causes MDEV-26446 Crash on st_join_table::save_explain_... Closed

 Description   

For the table 

CREATE TABLE t1 (
 
  id int(10) unsigned NOT NULL AUTO_INCREMENT,
 
  p char(32) DEFAULT NULL,
 
  es tinyint(3) unsigned NOT NULL DEFAULT 0,
 
  er tinyint(3) unsigned NOT NULL DEFAULT 0,
 
  x mediumint(8) unsigned NOT NULL DEFAULT 0,
 
  PRIMARY KEY (id),
 
  INDEX es (es),
 
  INDEX x (x),
 
  INDEX er (er,x),
 
  INDEX p (p)
 
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

populated with the statements:

insert into t1(es,er) select 0, 1 from seq_1_to_45;
 
insert into t1(es,er) select 0, 2 from seq_1_to_49;
 
insert into t1(es,er) select 0, 3 from seq_1_to_951;
 
insert into t1(es,er) select 0, 3 from seq_1_to_1054;
 
insert into t1(es,er) select 0, 6 from seq_1_to_25;
 
insert into t1(es,er) select 0, 11 from seq_1_to_1;
 
insert into t1(es,er) select 1, 1 from seq_1_to_45;
 
insert into t1(es,er) select 1, 2 from seq_1_to_16;
 
insert into t1(es,er) select 1, 3 from seq_1_to_511;
 
insert into t1(es,er) select 1, 4 from seq_1_to_687;
 
insert into t1(es,er) select 1, 6 from seq_1_to_50;
 
insert into t1(es,er) select 1, 7 from seq_1_to_4;
 
insert into t1(es,er) select 1, 11 from seq_1_to_1;
 
insert into t1(es,er) select 2, 1 from seq_1_to_82;
 
insert into t1(es,er) select 2, 2 from seq_1_to_82;
 
insert into t1(es,er) select 2, 3 from seq_1_to_1626;
 
insert into t1(es,er) select 2, 4 from seq_1_to_977;
 
insert into t1(es,er) select 2, 6 from seq_1_to_33;
 
insert into t1(es,er) select 2, 11 from seq_1_to_1;
 
insert into t1(es,er) select 3, 1 from seq_1_to_245;
 
insert into t1(es,er) select 3, 2 from seq_1_to_81;
 
insert into t1(es,er) select 3, 3 from seq_1_to_852;
 
insert into t1(es,er) select 3, 4 from seq_1_to_2243;
 
insert into t1(es,er) select 3, 6 from seq_1_to_44;
 
insert into t1(es,er) select 3, 11 from seq_1_to_1;
 
insert into t1(es,er) select 4, 1 from seq_1_to_91;
 
insert into t1(es,er) select 4, 2 from seq_1_to_83;
 
insert into t1(es,er) select 4, 3 from seq_1_to_297;
 
insert into t1(es,er) select 4, 4 from seq_1_to_2456;
 
insert into t1(es,er) select 4, 6 from seq_1_to_19;
 
insert into t1(es,er) select 4, 11 from seq_1_to_1;
 
update t1 set p='foobar';
 
update t1 set x=0;

the following execution plan is chosen for the query

SELECT * FROM t1
 
  WHERE ((p = 'foo' AND er != 4) OR er = 4 ) AND (es >= 4) LIMIT 2;

if the optimizer switch index_merge_sort_intersection is set to 'on'

EXPLAIN EXTENDED SELECT * FROM t1 WHERE ((p = 'foo' AND er != 4) OR er = 4 ) AND (es >= 4) limit 2;
 
+------+-------------+-------+-------------+---------------+-------+---------+------+------+----------+------------------------------------------+
 
| id   | select_type | table | type        | possible_keys | key   | key_len | ref  | rows | filtered | Extra                                    |
 
+------+-------------+-------+-------------+---------------+-------+---------+------+------+----------+------------------------------------------+
 
|    1 | SIMPLE      | t1    | index_merge | es,er,p       | er,es | 0,1     | NULL | 1852 |   100.00 | Using sort_intersect(er,es); Using where |
 
+------+-------------+-------+-------------+---------------+-------+---------+------+------+----------+------------------------------------------+

As the range condition for the index 'er' (er!=4 OR er=4) is always true this index is of no use for index intersection.



 Comments   
Comment by Igor Babaev [ 2021-12-15 ]

This bug manifests itself more clearly in 10.4 where the optimization employing range rowid filters has been introduced.

Comment by Igor Babaev [ 2021-12-16 ]

The problem appears for queries whose WHERE conditions contain OR formulas where the Range Optimizer builds OR ranges fully covering an index. Such ranges should be ignored, but the function key_or() from the Range Optimizer code not always does it.
A similar problem can be seen for the query from index_merge1.inc

select * from t0 force index(i1, i2, i3, i4, i5, i6 ) where
 
    ((key3 < 5 or key5 < 4) and (key1 < 4 or key2 < 4))
 
  or
 
    ((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));

For this query the Range Optimizer builds the following plan

MariaDB [test]> explain extended
 
    -> select * from t0 force index(i1, i2, i3, i4, i5, i6 ) where
 
    ->     ((key3 < 5 or key5 < 4) and (key1 < 4 or key2 < 4))
 
    ->   or
 
    ->     ((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
 
+------+-------------+-------+-------------+----------------+-------+---------+------+------+----------+--------------------------------------+
 
| id   | select_type | table | type        | possible_keys  | key   | key_len | ref  | rows | filtered | Extra                                |
 
+------+-------------+-------+-------------+----------------+-------+---------+------+------+----------+--------------------------------------+
 
|    1 | SIMPLE      | t0    | index_merge | i1,i2,i3,i5,i6 | i3,i5 | 0,4     | NULL | 1024 |   100.00 | Using sort_union(i3,i5); Using where |
 
+------+-------------+-------+-------------+----------------+-------+---------+------+------+----------+--------------------------------------+

It does not make sense to use here an index merge scan as the range for the index i3 is (-inf,+inf).

It should be noted that the index intersect plan is chosen for the reported query only due to a defect in the InnoDB code the makes the returns wrong estimates of the cardinality of the big ranges. The engine always thinks that the number of records in a range cannot exceed 50% of the number of records in the whole index.
At the same time the above query from index_merge1.inc reproduces the problem for both InnoDB and MyISAM:

MariaDB [test]> alter table t0 engine=innodb;
 
Query OK, 1024 rows affected (...)               
Records: 1024  Duplicates: 0  Warnings: 0
 
 
 
MariaDB [test]> analyze table t0;
 
+---------+---------+----------+----------+
 
| Table   | Op      | Msg_type | Msg_text |
 
+---------+---------+----------+----------+
 
| test.t0 | analyze | status   | OK       |
 
+---------+---------+----------+----------+
 
1 row in set (...)
 
 
 
MariaDB [test]> explain extended select * from t0 force index(i1, i2, i3, i4, i5, i6 ) where     ((key3 < 5 or key5 < 4) and (key1 < 4 or key2 < 4))   or     ((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
 
+------+-------------+-------+-------------+----------------+-------+---------+------+------+----------+--------------------------------------+
 
| id   | select_type | table | type        | possible_keys  | key   | key_len | ref  | rows | filtered | Extra                                |
 
+------+-------------+-------+-------------+----------------+-------+---------+------+------+----------+--------------------------------------+
 
|    1 | SIMPLE      | t0    | index_merge | i1,i2,i3,i5,i6 | i3,i5 | 0,4     | NULL | 1024 |   100.00 | Using sort_union(i3,i5); Using where |
 
+------+-------------+-------+-------------+----------------+-------+---------+------+------+----------+--------------------------------------+

Comment by Igor Babaev [ 2021-12-20 ]

The following change should be applied when merging the patch into 10.4:

diff --git a/mysql-test/t/range_innodb.test b/mysql-test/t/range_innodb.test
 
index 7420e72..5a19b39 100644
 
--- a/mysql-test/t/range_innodb.test
 
+++ b/mysql-test/t/range_innodb.test
 
@@ -173,6 +173,7 @@ set @save_isp=@@innodb_stats_persistent;
 
 set global innodb_stats_persistent= 1;
 
 analyze table t1;
 
 
+set optimizer_switch='rowid_filter=off';
 
 let $q=
 
 SELECT * FROM t1
 
   WHERE ((p = 'foo' AND er != 4) OR er = 4 ) AND (es >= 4) LIMIT 2;
 
@@ -190,6 +191,7 @@ eval $q;
 
 eval EXPLAIN EXTENDED $q;
 
 set optimizer_switch='index_merge_sort_intersection=default';
 
 
+set optimizer_switch='rowid_filter=default';
 
 set global innodb_stats_persistent= @save_isp;
 
 DROP TABLE t1;

Comment by Sergei Petrunia [ 2021-12-20 ]

A question: http://lists.askmonty.org/pipermail/commits/2021-December/014823.html

Comment by Igor Babaev [ 2021-12-21 ]

Here's another query where the overlapped ranges that are ORed and cover the whole index er:

SELECT * FROM t1
 
  WHERE ((p = 'foo' AND er < 6) OR er >=2 ) AND (es >= 4) LIMIT 2;

When the optimizer switch 'index_merge_sort_intersection' is set to 'on' we see the same problem

MariaDB [test]> EXPLAIN EXTENDED SELECT * FROM t1   WHERE ((p = 'foo' AND er < 6) OR er >=2 ) AND (es >= 4) LIMIT 2;
 
+------+-------------+-------+-------------+---------------+-------+---------+------+------+----------+------------------------------------------+
 
| id   | select_type | table | type        | possible_keys | key   | key_len | ref  | rows | filtered | Extra                                    |
 
+------+-------------+-------+-------------+---------------+-------+---------+------+------+----------+------------------------------------------+
 
|    1 | SIMPLE      | t1    | index_merge | es,er,p       | es,er | 1,0     | NULL | 1852 |   100.00 | Using sort_intersect(es,er); Using where |
 
+------+-------------+-------+-------------+---------------+-------+---------+------+------+----------+------------------------------------------+

However this query does not cause any problem in 10.4 with default settings for optimizer switches 'rowid_filter' and 'index_merge_sort_intersection' ('on' and 'off' correspondingly. This is because for this query when only the index er is enabled key_or() returns the range (-inf,+inf) for the index er rather then just NULL (see comments in MDEV-26446).

Comment by Igor Babaev [ 2021-12-21 ]

A similar problem can be observed for overlapping ranges that are Ored and cover the whole index when the optimizer decides to use a table retrieval with index_merge_sort_union scan:

MariaDB [test]> explain select * from t0 force index(i1, i2, i3, i4, i5, i6 ) where
 
    ->     ((key3 < 10 or key5 < 4) and (key1 < 4 or key2 < 4))
 
    ->   or
 
    ->     ((key3 >=5 or key5 < 2) and (key5 < 5 or key6 < 6));
 
+------+-------------+-------+-------------+----------------+-------+---------+------+------+--------------------------------------+
 
| id   | select_type | table | type        | possible_keys  | key   | key_len | ref  | rows | Extra                                |
 
+------+-------------+-------+-------------+----------------+-------+---------+------+------+--------------------------------------+
 
|    1 | SIMPLE      | t0    | index_merge | i1,i2,i3,i5,i6 | i3,i5 | 0,4     | NULL | 1024 | Using sort_union(i3,i5); Using where |
 
+------+-------------+-------+-------------+----------------+-------+---------+------+------+--------------------------------------+

Comment by Sergei Petrunia [ 2021-12-23 ]

The second patch is ok to push.

Comment by Igor Babaev [ 2021-12-25 ]

Attention: See my comment how to merge into 10.4.

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