Bug #74198 Get full table scan after FORCE INDEX for HEAP
Submitted: 3 Oct 2014 0:07 Modified: 12 Oct 2014 17:45
Reporter: Mark Callaghan Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: Memory storage engine Severity:S3 (Non-critical)
Version:5.7.5 OS:Any
Assigned to: CPU Architecture:Any

[3 Oct 2014 0:07] Mark Callaghan
Description:
I can reproduce this in 5.0.85, 5.1.63, 5.5.40, 5.6.21 and 5.7.5.
But only for Heap engine. InnoDB does the right thing.

This claims that it can use indexes xj or xjk.

      Table: foo
Create Table: CREATE TABLE `foo` (
  `i` int(11) NOT NULL AUTO_INCREMENT,
  `j` int(11) DEFAULT NULL,
  `k` int(11) DEFAULT NULL,
  `l` int(11) DEFAULT NULL,
  PRIMARY KEY (`i`),
  KEY `xj` (`j`),
  KEY `xjk` (`j`,`k`)
) ENGINE=MEMORY AUTO_INCREMENT=64001 DEFAULT CHARSET=latin1

bin/mysql -A test -e 'explain select k from foo where j = 100\G'

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: foo
   partitions: NULL
         type: ref
possible_keys: xj,xjk
          key: xj
      key_len: 5
          ref: const
         rows: 2
     filtered: 100.00
        Extra: NULL

But when I FORCE INDEX (xjk) then I get a full table scan

# bin/mysql -A test -e 'explain select k from foo FORCE INDEX(`xjk`) where j = 100\G'
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: foo
   partitions: NULL
         type: ALL
possible_keys: xjk
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 64000
     filtered: 0.00
        Extra: Using where

How to repeat:
create table foo (i int primary key auto_increment, j int, k int, l int) engine=heap;
insert into foo values (null,0,0,0),(null,0,0,0),(null,0,0,0),(null,0,0,0),(null,0,0,0),(null,0,0,0),(null,0,0,0),(null,0,0,0),(null,0,0,0),(null,0,0,0);
<repeat insert 99 times>
insert into foo select null,0,0,0 from foo;
insert into foo select null,0,0,0 from foo;
insert into foo select null,0,0,0 from foo;
insert into foo select null,0,0,0 from foo;
insert into foo select null,0,0,0 from foo;
insert into foo select null,0,0,0 from foo;
update foo set j=i, k=i;
create index xj on foo(j);
create index xjk on foo(j,k);

# OK query
select k from foo where j = 100;

# Bad plan, does full table scan
select k from foo FORCE INDEX(`xjk`) where j = 100;

Suggested fix:
Use the forced index
[3 Oct 2014 8:51] Shane Bester
Verified on 5.7.6.   optimizer trace shows:

| select k from foo FORCE INDEX(`xjk`) where j = 100 | {
  "steps": [
    {
      "join_preparation": {
        "select#": 1,
        "steps": [
          {
            "expanded_query": "/* select#1 */ select `foo`.`k` AS `k` from `foo` FORCE INDEX (`xjk`) where (`foo`.`j` = 100)"
          }
        ]
      }
    },
    {
      "join_optimization": {
        "select#": 1,
        "steps": [
          {
            "condition_processing": {
              "condition": "WHERE",
              "original_condition": "(`foo`.`j` = 100)",
              "steps": [
                {
                  "transformation": "equality_propagation",
                  "resulting_condition": "multiple equal(100, `foo`.`j`)"
                },
                {
                  "transformation": "constant_propagation",
                  "resulting_condition": "multiple equal(100, `foo`.`j`)"
                },
                {
                  "transformation": "trivial_condition_removal",
                  "resulting_condition": "multiple equal(100, `foo`.`j`)"
                }
              ]
            }
          },
          {
            "table_dependencies": [
              {
                "table": "`foo` FORCE INDEX (`xjk`)",
                "row_may_be_null": false,
                "map_bit": 0,
                "depends_on_map_bits": [
                ]
              }
            ]
          },
          {
            "ref_optimizer_key_uses": [
              {
                "table": "`foo` FORCE INDEX (`xjk`)",
                "field": "j",
                "equals": "100",
                "null_rejecting": false
              }
            ]
          },
          {
            "rows_estimation": [
              {
                "table": "`foo` FORCE INDEX (`xjk`)",
                "range_analysis": {
                  "table_scan": {
                    "rows": 320,
                    "cost": 2e308
                  },
                  "potential_range_indexes": [
                    {
                      "index": "PRIMARY",
                      "usable": false,
                      "cause": "not_applicable"
                    },
                    {
                      "index": "xj",
                      "usable": false,
                      "cause": "not_applicable"
                    },
                    {
                      "index": "xjk",
                      "usable": true,
                      "key_parts": [
                        "j",
                        "k"
                      ]
                    }
                  ],
                  "setup_range_conditions": [
                  ],
                  "group_index_range": {
                    "chosen": false,
                    "cause": "not_group_by_or_distinct"
                  },
                  "analyzing_range_alternatives": {
                    "range_scan_alternatives": [
                      {
                        "index": "xjk",
                        "chosen": false,
                        "cause": "unknown"
                      }
                    ],
                    "analyzing_roworder_intersect": {
                      "usable": false,
                      "cause": "too_few_roworder_scans"
                    }
                  }
                }
              }
            ]
          },
          {
            "considered_execution_plans": [
              {
                "plan_prefix": [
                ],
                "table": "`foo` FORCE INDEX (`xjk`)",
                "best_access_path": {
                  "considered_access_paths": [
                    {
                      "access_type": "ref",
                      "index": "xjk",
                      "usable": false,
                      "chosen": false
                    },
                    {
                      "rows_to_scan": 320,
                      "access_type": "scan",
                      "resulting_rows": 320,
                      "cost": 81,
                      "chosen": true
                    }
                  ]
                },
                "condition_filtering_pct": 100,
                "rows_for_plan": 320,
                "cost_for_plan": 81,
                "chosen": true
              }
            ]
          },
          {
            "attaching_conditions_to_tables": {
              "original_condition": "(`foo`.`j` = 100)",
              "attached_conditions_computation": [
              ],
              "attached_conditions_summary": [
                {
                  "table": "`foo` FORCE INDEX (`xjk`)",
                  "attached": "(`foo`.`j` = 100)"
                }
              ]
            }
          },
          {
            "refine_plan": [
              {
                "table": "`foo` FORCE INDEX (`xjk`)"
              }
            ]
          }
        ]
      }
    },
    {
      "join_execution": {
        "select#": 1,
        "steps": [
        ]
      }
    }
  ]
} |                                 0 |                       0 |
[12 Oct 2014 7:44] Daniël van Eeden
When I test this on 5.7.5-m15 the indexes are generated as HASH. So the "InnoDB does the right thing" means InnoDB/BTREE is okay and HEAP/HASH is not?

When I remove index xjk and replace it with a BTREE index is seems to do the right thing.

mysql> explain select k from foo FORCE INDEX(`xjk`) where j = 100;
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | foo   | NULL       | ALL  | xjk           | NULL | NULL    | NULL |  640 |     0.31 | Using where |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

mysql> alter table foo drop index `xjk`;
Query OK, 640 rows affected (0.01 sec)
Records: 640  Duplicates: 0  Warnings: 0

mysql> alter table foo add index `xjk` (`j`,`k`) using btree;
Query OK, 640 rows affected (0.00 sec)
Records: 640  Duplicates: 0  Warnings: 0

mysql> explain select k from foo FORCE INDEX(`xjk`) where j = 100;
+----+-------------+-------+------------+------+---------------+------+---------+-------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref   | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+------+---------+-------+------+----------+-------+
|  1 | SIMPLE      | foo   | NULL       | ref  | xjk           | xjk  | 5       | const |    1 |   100.00 | NULL  |
+----+-------------+-------+------------+------+---------------+------+---------+-------+------+----------+-------+
1 row in set, 1 warning (0.00 sec)
[12 Oct 2014 14:42] Mark Callaghan
yes, the right thing (no full table scan) was done for innodb/btree in my tests
[12 Oct 2014 15:30] Daniël van Eeden
I don't think it is possible to use the index if it is a hash over 2 columns and you only specify one column.

http://dev.mysql.com/doc/refman/5.7/en/index-btree-hash.html
"Only whole keys can be used to search for a row." (section 'Hash Index Characteristics')

If this is true it then the index should not be listed under 'possible_keys'.
[12 Oct 2014 17:45] Mark Callaghan
I agree with you.