[MDEV-27262] Unexpected index intersection with full index scan for an index - Jira

Details

Type: Task
Status: Closed (View Workflow)
Priority: Major
Resolution: Fixed
Fix Version/s: 10.2.42, 10.3.33, 10.4.23, 10.5.14, 10.6.6, 10.7.2
Component/s: Optimizer
Labels:
None

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.

Attachments

Issue Links

causes

MDEV-26446 Crash on st_join_table::save_explain_data

Closed

Activity

Ascending order - Click to sort in descending order

Igor Babaev (Inactive) created issue - 2021-12-15 07:39

Igor Babaev (Inactive) added a comment - 2021-12-15 23:56

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

Igor Babaev (Inactive) added a comment - 2021-12-15 23:56 This bug manifests itself more clearly in 10.4 where the optimization employing range rowid filters has been introduced.

Igor Babaev (Inactive) made changes - 2021-12-15 23:56

Field	Original Value	New Value
Link		This issue causes ~~MDEV-26446~~ [ ~~MDEV-26446~~ ]

Igor Babaev (Inactive) added a comment - 2021-12-16 00:44

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 |

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

Igor Babaev (Inactive) added a comment - 2021-12-16 00:44 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 | +------+-------------+-------+-------------+----------------+-------+---------+------+------+----------+--------------------------------------+

Igor Babaev (Inactive) made changes - 2021-12-20 06:21

Status

Open [ 1 ]

In Progress [ 3 ]

Igor Babaev (Inactive) made changes - 2021-12-20 06:22

Assignee	Igor Babaev [ igor ]	Oleksandr Byelkin [ sanja ]
Status	In Progress [ 3 ]	In Review [ 10002 ]

Igor Babaev (Inactive) added a comment - 2021-12-20 17:49

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;

Igor Babaev (Inactive) added a comment - 2021-12-20 17:49 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;

Sergei Petrunia added a comment - 2021-12-20 19:43

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

Sergei Petrunia added a comment - 2021-12-20 19:43 A question: http://lists.askmonty.org/pipermail/commits/2021-December/014823.html

Igor Babaev (Inactive) added a comment - 2021-12-21 02:23

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~~).

Igor Babaev (Inactive) added a comment - 2021-12-21 02:23 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 ).

Igor Babaev (Inactive) made changes - 2021-12-21 06:04

Assignee

Oleksandr Byelkin [ sanja ]

Sergei Petrunia [ psergey ]

Igor Babaev (Inactive) added a comment - 2021-12-21 19:17

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 |

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

Igor Babaev (Inactive) added a comment - 2021-12-21 19:17 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 | +------+-------------+-------+-------------+----------------+-------+---------+------+------+--------------------------------------+

Sergei Petrunia added a comment - 2021-12-23 07:58

The second patch is ok to push.

Sergei Petrunia added a comment - 2021-12-23 07:58 The second patch is ok to push.

Sergei Petrunia made changes - 2021-12-23 07:58

Assignee	Sergei Petrunia [ psergey ]	Igor Babaev [ igor ]
Status	In Review [ 10002 ]	Stalled [ 10000 ]

Igor Babaev (Inactive) added a comment - 2021-12-25 18:54

Attention: See my comment how to merge into 10.4.

Igor Babaev (Inactive) added a comment - 2021-12-25 18:54 Attention: See my comment how to merge into 10.4.

Igor Babaev (Inactive) made changes - 2021-12-25 18:54

Fix Version/s		10.2.42 [ 26803 ]
Fix Version/s		10.3.33 [ 26805 ]
Fix Version/s		10.4.23 [ 26807 ]
Fix Version/s		10.5.14 [ 26809 ]
Fix Version/s		10.6.6 [ 26811 ]
Fix Version/s		10.7.2 [ 26813 ]
Fix Version/s	10.2 [ 14601 ]
Resolution		Fixed [ 1 ]
Status	Stalled [ 10000 ]	Closed [ 6 ]

People

Assignee:: Igor Babaev (Inactive)

Reporter:: Igor Babaev (Inactive)

Votes:: 0 Vote for this issue

Watchers:: 3 Start watching this issue

Dates

Created:: 2021-12-15 07:39

Updated:: 2021-12-28 12:05

Resolved:: 2021-12-25 18:54

Git Integration

Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.

MariaDB Server