MySQL Bugs: #58463: Error Can't find record on SELECT with JOIN and ORDER BY

Bug #58463	Error Can't find record on SELECT with JOIN and ORDER BY
Submitted:	24 Nov 2010 15:34	Modified:	20 Jan 2011 19:16
Reporter:	John Embretsen	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	bzr_mysql-next-mr-opt-backporting	OS:	Any
Assigned to:	Olav Sandstå	CPU Architecture:	Any
Tags:	index_condition_pushdown, mrr, optimizer_switch

Description:
Expecting to get "Empty set" upon executing the following query, one gets an error instead:

mysql> SELECT R.col_int_key AS field1
    -> FROM E LEFT JOIN R ON E.pk = R.col_int 
    -> WHERE R.col_int_key > 5
    -> AND R.pk IS  NULL
    -> ORDER BY field1;
ERROR 1032 (HY000): Can't find record in 'R'

This seems to happen only in mysql-next-mr-opt-backporting branch, so Category is set to Optimizer for this reason, and because the error goes away if "ORDER BY field1" is omitted.

Using non-default character set utf8 for some varchar column in an InnoDB table seems to be required to stumble across this.

How to repeat:
CREATE TABLE E (
  pk INT NOT NULL AUTO_INCREMENT,
  PRIMARY KEY (pk)
);

INSERT INTO E VALUES (2);

CREATE TABLE R (
  pk INT NOT NULL AUTO_INCREMENT,
  col_int INT,
  col_int_key INT,
  col_varchar_1024_utf8 VARCHAR(1024) CHARACTER SET utf8,
  PRIMARY KEY (pk),
  KEY col_int_key (col_int_key)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

INSERT INTO R VALUES (3, 1, 9, NULL);

SELECT R.col_int_key AS field1
FROM E LEFT JOIN R ON E.pk = R.col_int 
WHERE R.col_int_key > 5
AND R.pk IS  NULL
ORDER BY field1;

Note that the error goes away if default character set instead of utf8 is used for the column col_varchar_1024_utf8 in table R.

Verified against mysql-next-mr-opt-backporting at revno 3286, revid tor.didriksen@oracle.com-20101116165843-86cs5woahaule77bm, using default optimizer options:

Variable_name: optimizer_join_cache_level
        Value: 1
Variable_name: optimizer_prune_level
        Value: 1
Variable_name: optimizer_search_depth
        Value: 62
Variable_name: optimizer_switch
        Value: index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,engine_condition_pushdown=on,index_condition_pushdown=on,materialization=on,semijoin=on,loosescan=on,firstmatch=on,mrr=on,mrr_cost_based=off

The error goes away if disabling ICP (index_condition_pushdown):

mysql> SET optimizer_switch='index_condition_pushdown=off';
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT R.col_int_key AS field1 FROM E LEFT JOIN R ON E.pk = R.col_int  WHERE R.col_int_key > 5 AND R.pk IS  NULL ORDER BY field1;
Empty set (0.00 sec)

The explain output for the failing query:

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	E	system	PRIMARY	NULL	NULL	NULL	1	Using filesort
1	SIMPLE	R	const	PRIMARY,col_int_key	PRIMARY	4	const	1	Using index condition; Using where

The index condition that gets pushed down to InnoDB on R's primary key is:

   isnull(`test`.`R`.`pk`)

Note that the same test case does not fail when I run with source code from mysql-next-mr-opt-team. This also have ICP enabled. The test case produces the same query plan (explain output) and do push the same index condition down to InnoDB.

It turns out that switching off MRR also makes this error go away. So if either mrr=off or index_condition_pushdown=off in the value of the variable optimizer_switch, then the issue disappears.

This may explain why the issue was not observed in mysql-next-mr-opt-team, where MRR is not yet available.

Here is an overview of what seems to happen:

1. During optimization the optimizer will evaluate which access method
is best for accessing data from table R. The alternatives are using
the primary key (pk) or the secondary index col_int_key. Based on cost
estimates the primary key is select. This is also as specified in the
explain output:

id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE E system PRIMARY NULL NULL NULL 1 Using filesort
1 SIMPLE R const PRIMARY,col_int_key PRIMARY 4 const 1 Using index condition; Using where

2. As one of the last steps of the optimization phase is to check if
any part of the conditions on the tables can be pushed down to the
storage engine. For table R being accessed using the primary key it is
determined that:

isnull(`test`.`R`.`pk`)

can be pushed down to InnoDB. This is done and is now stored in the
handler object that is used for accessing table R.

So far everything looks correct.

3. During the execution phase it seems like MySQL changes its mind and
decides to use the secondary index col_int_key for accessing the table
R (instead of the primary key) (and this leads to the problems...)

4. MySQL determines it needs to use filesort to do the access of table
R. Since MRR is "on" (and cost-based off) it sets up to use MRR for
this. MRR is done in three phases.

5. MRR phase 1: an extra clone of the handler object for table R is
created and set up to read keys using the col_int_key index. This
produces in this case one key. This key is stored in the MRR sort
buffer.

6. MRR phase 2: The MRR sort buffer is "sorted" in primary key order
(it still contains only one key).

7. MRR phase 3: Retrieve the records using the key values from the
sort buffer. For doing this the original handler for table R is
used. The retrieval is done using the primary key. And (unfortunately)
this handler has the index condition that got pushed in stage 2 as
active. So the requested record for the key is filtered out by InnoDB
due to the pushed index condition. As a result InnoDB (correctly)
returns HA_ERR_KEY_NOT_FOUND for this key. This error is not expected
and not handled in the MRR implementation and as a consequence this
error get propagated all the way back to the client.

Step 3 in the above explanation says that "MySQL changes its mind"
about which index to use during execution. Here is how that happens:

1. During JOIN::exec() a call to create_sort_index() is done.

2. In create_sort_index() we run the following check:

    // If table has a range, move it to select
    if (select && !select->quick && tab->ref.key >= 0)
    {

   If this is true we will either give select->quick a value either by
   assigning tab->quick to it or allocate a new QUICK-SELECT object.

   In our case select->quick is not NULL so we will not create a new a
   QUICK_SELECT object. In stead the existing QUICK_SELECT object will
   be used. This is the same object that was used during cost
   evaluation in the optimizer phase. This was used for evaluating the
   cost of using the secondary index col_int_key.

3. When we start the file sort in find_all_keys() we use this
   QUICK_SELECT object. We call reset() on and then use it. Since this
   has been originally initialized to use col_int_key as its index it
   will still use this index for reading data from the table.

So it seems like the "change to use a different index" than the
optimizer concluded should be used (ie. using col_int_key instead of
pk) happens due to we re-use an old QUICK_SELECT object for
col_int_key instead of creating a new QUICK_SELECT object for pk.

Note that after pushing the first part of WL#5692 which changes MRR from always being used to be cost-based the test case no longer hits this bug (due to MRR not being used).

In order to reproduce the bug the following must be added to the test case:

set optimizer_switch='mrr_cost_based=off';

The problem with the server changing to use the wrong index during execution for accessing the table will be fixed by the patch for Bug#58456. This change also solves the problem with MRR reported in this bug.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/126426

3312 Olav Sandstaa	2010-12-09
      Patch for Bug#58463 Error Can't find record on SELECT with JOIN and ORDER BY
      
      This problem was caused by the server pushing down an index condition on
      the primary key as part of the optimization phase. Later, during the 
      execution phase the server (due to a bug) changed to use a secondary index
      instead of the primary index for accessing the table. This made MRR fail
      in phase 3 due to not finding the expected records when retrieving them
      using the primary key due to the pushed index condition filtering them away.
      
      This problem with the server accidentally switching to using a secondary index will
      be fixed by the fix for Bug#58456. 
      
      This patch contains a test case based on the bug report and an added assert to
      the DS-MRR implementation that will trigger if a similar situation should occur
      again (DS-MRR used on a secondary index while an index condition has been pushed
      on the primary index for the same handler object).
      
      Note to reviewers: In order for running the new test without failure the patch
      for Bug#58456 needs to be applied first.
     @ mysql-test/include/mrr_tests.inc
        Test case for Bug#58463 Error Can't find record on SELECT with JOIN and ORDER BY.
     @ mysql-test/r/innodb_mrr.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/innodb_mrr_all.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/innodb_mrr_cost.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/innodb_mrr_cost_all.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/innodb_mrr_cost_icp.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/innodb_mrr_icp.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/innodb_mrr_none.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/myisam_mrr.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/myisam_mrr_all.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/myisam_mrr_cost.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/myisam_mrr_cost_all.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/myisam_mrr_cost_icp.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/myisam_mrr_icp.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/myisam_mrr_none.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ sql/handler.cc
        Added assert that will detect if DS-MRR is attempted run using
        a secondary index when there exists a pushed index condition for
        the primary key on the same handler.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/128137

3321 Olav Sandstaa	2011-01-07
      Patch for Bug#58463 Error Can't find record on SELECT with JOIN and ORDER BY
      
      This problem was caused by the server pushing down an index condition on
      the primary key as part of the optimization phase. Later, during the 
      execution phase the server (due to a bug) changed to use a secondary index
      instead of the primary index for accessing the table. This made MRR fail
      in phase 3 due to not finding the expected records when retrieving them
      using the primary key due to the pushed index condition filtering them away.
      
      This problem with the server accidentally switching to using a secondary index will
      be fixed by the fix for Bug#58456. 
      
      This patch contains a test case based on the bug report and an added assert to
      the DS-MRR implementation that will trigger if a similar situation should occur
      again (DS-MRR used on a secondary index while an index condition has been pushed
      on the primary index for the same handler object).
     @ mysql-test/include/mrr_tests.inc
        Test case for Bug#58463 Error Can't find record on SELECT with JOIN and ORDER BY.
     @ mysql-test/r/innodb_mrr.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/innodb_mrr_all.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/innodb_mrr_cost.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/innodb_mrr_cost_all.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/innodb_mrr_cost_icp.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/innodb_mrr_icp.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/innodb_mrr_none.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/myisam_mrr.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/myisam_mrr_all.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/myisam_mrr_cost.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/myisam_mrr_cost_all.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/myisam_mrr_cost_icp.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/myisam_mrr_icp.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ mysql-test/r/myisam_mrr_none.result
        Result file for test case for Bug#58463 Error Can't find record on SELECT 
        with JOIN and ORDER BY.
     @ sql/handler.cc
        Added assert that will detect if DS-MRR is attempted run using
        a secondary index when there exists a pushed index condition for
        the primary key on the same handler.

Patch pushed to mysql-next-mr-opt-backporting with revision id:
olav.sandstaa@oracle.com-20110107083831-mvpa9nlv4eu063m6 .

Note: This bug was fixed by the patch for Bug#58456: 

  http://lists.mysql.com/commits/127082

which was pushed into mysql-trunk-bugfixing on December 16. 2010.
The patch pushed for this bug contains the test case and an added 
assert.

Pushed into mysql-trunk 5.6.2 (revid:jorgen.loland@oracle.com-20110120090926-xms6k8scdrtl8yai) (version source revid:jorgen.loland@oracle.com-20110120090926-xms6k8scdrtl8yai) (merge vers: 5.6.2) (pib:24)

Changes to test suite. No changelog entry needed.