[MDEV-6434] Wrong result (extra rows) with ORDER BY, multiple-column index, InnoDB - JIRA

Details

Type: Bug
Status: Closed
Priority: Major
Resolution: Fixed
Affects Version/s: 5.3.12, 5.5.38, 10.0.12
Fix Version/s: 5.5.39, 10.0.13
Component/s: None
Labels:
None

Description

Initially reported by VAROQUI Stephane on IRC.

CREATE TABLE t1 (a INT, b INT, c INT, d TEXT, KEY idx(a,b,c)) ENGINE=InnoDB;

INSERT INTO t1 (a,c) VALUES
(8, 9),(8, 10),(13, 15),(16, 17),(16, 18),(16, 19),(20, 21),
(20, 22),(20, 24),(20, 25),(20, 26),(20, 27),(20, 28);

SELECT  * FROM t1 WHERE a = 8 AND (b = 1 OR b IS NULL) ORDER BY c;

Actual result (all rows except for a=8 shouldn't be there):

+------+------+------+------+
| a    | b    | c    | d    |
+------+------+------+------+
|    8 | NULL |    9 | NULL |
|    8 | NULL |   10 | NULL |
|   13 | NULL |   15 | NULL |
|   16 | NULL |   17 | NULL |
|   16 | NULL |   18 | NULL |
|   16 | NULL |   19 | NULL |
|   20 | NULL |   21 | NULL |
|   20 | NULL |   22 | NULL |
|   20 | NULL |   24 | NULL |
|   20 | NULL |   25 | NULL |
|   20 | NULL |   26 | NULL |
|   20 | NULL |   27 | NULL |
|   20 | NULL |   28 | NULL |
+------+------+------+------+
13 rows in set (0.01 sec)

+------+-------------+-------+-------------+---------------+------+---------+-------------+------+----------+----------------------------------------------------+
| id   | select_type | table | type        | possible_keys | key  | key_len | ref         | rows | filtered | Extra                                              |
+------+-------------+-------+-------------+---------------+------+---------+-------------+------+----------+----------------------------------------------------+
|    1 | SIMPLE      | t1    | ref_or_null | idx           | idx  | 10      | const,const |    3 |   100.00 | Using index condition; Using where; Using filesort |
+------+-------------+-------+-------------+---------------+------+---------+-------------+------+----------+----------------------------------------------------+
1 row in set, 1 warning (0.00 sec)

MariaDB [test]> show warnings;
+-------+------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Level | Code | Message                                                                                                                                                                                                                           |
+-------+------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Note  | 1003 | select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t1`.`c` AS `c`,`test`.`t1`.`d` AS `d` from `test`.`t1` where ((`test`.`t1`.`a` = 8) and ((`test`.`t1`.`b` = 1) or isnull(`test`.`t1`.`b`))) order by `test`.`t1`.`c` |
+-------+------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

Gliffy Diagrams

Attachments

Activity

Ascending order - Click to sort in descending order

Hide

Permalink

Elena Stepanova added a comment - 2014-07-10 00:02

The original query / on the user's schema and data produced a slightly different plan:

SELECT  * FROM `navigation`  WHERE  `parent_id`=8 and (`project_id` = '1' OR `project_id` is null) ORDER BY `index` ASC;

+------+-------------+------------+-------------+-----------------------------+-----------+---------+-------------+------+-----------------------------+
| id   | select_type | table      | type        | possible_keys               | key       | key_len | ref         | rows | Extra                       |
+------+-------------+------------+-------------+-----------------------------+-----------+---------+-------------+------+-----------------------------+
|    1 | SIMPLE      | navigation | ref_or_null | navigation_ibfk_1,parent_id | parent_id | 10      | const,const |    3 | Using where; Using filesort |
+------+-------------+------------+-------------+-----------------------------+-----------+---------+-------------+------+-----------------------------+
1 row in set (0.00 sec)

Create Table: CREATE TABLE `navigation` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `parent_id` int(10) unsigned DEFAULT NULL,
  `group_id` int(10) unsigned DEFAULT NULL,
  `project_id` int(10) unsigned DEFAULT NULL,
  `nav_id` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  `index` int(10) NOT NULL,
  `label` varchar(255) COLLATE utf8_unicode_ci NOT NULL,
  `module` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  `controller` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  `action` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  `uri` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  `resource` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  `params` text COLLATE utf8_unicode_ci,
  `class` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `group_id` (`group_id`),
  KEY `navigation_ibfk_1` (`project_id`),
  KEY `parent_id` (`parent_id`,`project_id`,`index`),
  CONSTRAINT `navigation_ibfk_1` FOREIGN KEY (`project_id`) REFERENCES `project` (`id`) ON DELETE CASCADE ON UPDATE CASCADE,
  CONSTRAINT `navigation_ibfk_2` FOREIGN KEY (`parent_id`) REFERENCES `navigation` (`id`) ON DELETE CASCADE ON UPDATE CASCADE,
  CONSTRAINT `navigation_ibfk_3` FOREIGN KEY (`group_id`) REFERENCES `navigation_group` (`id`) ON DELETE CASCADE ON UPDATE CASCADE
) ENGINE=InnoDB AUTO_INCREMENT=51 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci ROW_FORMAT=COMPACT

Show

Elena Stepanova added a comment - 2014-07-10 00:02 The original query / on the user's schema and data produced a slightly different plan: SELECT * FROM `navigation` WHERE `parent_id`=8 and (`project_id` = '1' OR `project_id` is null) ORDER BY `index` ASC; +------+-------------+------------+-------------+-----------------------------+-----------+---------+-------------+------+-----------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +------+-------------+------------+-------------+-----------------------------+-----------+---------+-------------+------+-----------------------------+ | 1 | SIMPLE | navigation | ref_or_null | navigation_ibfk_1,parent_id | parent_id | 10 | const,const | 3 | Using where ; Using filesort | +------+-------------+------------+-------------+-----------------------------+-----------+---------+-------------+------+-----------------------------+ 1 row in set (0.00 sec) Create Table: CREATE TABLE `navigation` ( `id` int(10) unsigned NOT NULL AUTO_INCREMENT, `parent_id` int(10) unsigned DEFAULT NULL, `group_id` int(10) unsigned DEFAULT NULL, `project_id` int(10) unsigned DEFAULT NULL, `nav_id` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL, `index` int(10) NOT NULL, `label` varchar(255) COLLATE utf8_unicode_ci NOT NULL, `module` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL, `controller` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL, `action` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL, `uri` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL, `resource` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL, `params` text COLLATE utf8_unicode_ci, `class` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL, PRIMARY KEY (`id`), KEY `group_id` (`group_id`), KEY `navigation_ibfk_1` (`project_id`), KEY `parent_id` (`parent_id`,`project_id`,`index`), CONSTRAINT `navigation_ibfk_1` FOREIGN KEY (`project_id`) REFERENCES `project` (`id`) ON DELETE CASCADE ON UPDATE CASCADE, CONSTRAINT `navigation_ibfk_2` FOREIGN KEY (`parent_id`) REFERENCES `navigation` (`id`) ON DELETE CASCADE ON UPDATE CASCADE, CONSTRAINT `navigation_ibfk_3` FOREIGN KEY (`group_id`) REFERENCES `navigation_group` (`id`) ON DELETE CASCADE ON UPDATE CASCADE ) ENGINE=InnoDB AUTO_INCREMENT=51 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci ROW_FORMAT=COMPACT

5 older comments

Hide

Permalink

Sergei Petrunia added a comment - 2014-07-21 18:35 - edited

Possible directions for fix:
1. Make get_quick_select_for_ref() produce equality ranges.
2. Put the equalities that were removed by EQ_REF back into the WHERE clause.
3. Let find_all_keys() require reading of all columns that are used by the
quick select.

Show

Sergei Petrunia added a comment - 2014-07-21 18:35 - edited Possible directions for fix: 1. Make get_quick_select_for_ref() produce equality ranges. 2. Put the equalities that were removed by EQ_REF back into the WHERE clause. 3. Let find_all_keys() require reading of all columns that are used by the quick select.

Hide

Permalink

Sergei Petrunia added a comment - 2014-07-21 18:52 - edited

re solution #1:
get_quick_select_for_ref() is not consistent about use of EQ_RANGE flag:

For the primary equality it has:

  range->flag= (ref->key_length == key_info->key_length ? EQ_RANGE : 0);

for the "OR NULL" part of ref_or_null, EQ_RANGE flag is set unconditionally.

On the other hand, QUICK_SELECT_DESC::QUICK_SELECT_DESC has this code:

  /* Remove EQ_RANGE flag for keys that are not using the full key */

however, other code, like QUICK_RANGE_SELECT::unique_key_range, looks as if
EQ_RANGE can be set for equalities that don't cover the whole key.

Also, when range optimizer constructs quick select for the WHERE clause in this table, it does set EQ_RANGE flag.

Show

Sergei Petrunia added a comment - 2014-07-21 18:52 - edited re solution #1: get_quick_select_for_ref() is not consistent about use of EQ_RANGE flag: For the primary equality it has: range->flag= (ref->key_length == key_info->key_length ? EQ_RANGE : 0); for the "OR NULL" part of ref_or_null, EQ_RANGE flag is set unconditionally. On the other hand, QUICK_SELECT_DESC::QUICK_SELECT_DESC has this code: /* Remove EQ_RANGE flag for keys that are not using the full key */ however, other code, like QUICK_RANGE_SELECT::unique_key_range, looks as if EQ_RANGE can be set for equalities that don't cover the whole key. Also, when range optimizer constructs quick select for the WHERE clause in this table, it does set EQ_RANGE flag.

Hide

Permalink

Sergei Petrunia added a comment - 2014-07-21 19:30

Approach #2 is not a good idea. We've had an intent of doing the reverse: implementing a feature where parts of WHERE clause that are guaranteed to be true by use of range access should be removed from the WHERE.

Show

Sergei Petrunia added a comment - 2014-07-21 19:30 Approach #2 is not a good idea. We've had an intent of doing the reverse: implementing a feature where parts of WHERE clause that are guaranteed to be true by use of range access should be removed from the WHERE.

Hide

Permalink

Sergei Petrunia added a comment - 2014-07-22 14:36

Implementing solution #1 alone is not sufficient. when scanning equality ranges, there will still be compare_key (or compare_key2) calls done inside either ICP or handler::range_read_record. Ergo, all index columns must be present in the read set.

Show

Sergei Petrunia added a comment - 2014-07-22 14:36 Implementing solution #1 alone is not sufficient. when scanning equality ranges, there will still be compare_key (or compare_key2) calls done inside either ICP or handler::range_read_record. Ergo, all index columns must be present in the read set.

Hide

Permalink

Sergei Petrunia added a comment - 2014-07-22 14:55

Fix pushed into 5.5

Show

Sergei Petrunia added a comment - 2014-07-22 14:55 Fix pushed into 5.5

People

Assignee:

Sergei Petrunia

Reporter:

Elena Stepanova

Votes:

0 Vote for this issue

Watchers:

4 Start watching this issue

Dates

Created:

2014-07-09 23:58

Updated:

2014-07-22 14:55

Resolved:

2014-07-22 14:55

Agile

View on Board