MySQL Bugs: #46548: IN-subqueries return 0 rows with materialization=on

Bug #46548	IN-subqueries return 0 rows with materialization=on
Submitted:	4 Aug 2009 16:42	Modified:	23 Nov 2010 2:53
Reporter:	Patrick Crews	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S3 (Non-critical)
Version:	6.0	OS:	Any
Assigned to:	Øystein Grøvlen	CPU Architecture:	Any
Tags:	materialization, optimizer_switch, subquery, where

Description:
Certain subqueries with WHERE clauses are not being processed properly by azalea when optimizer_switch's materialization is set to on.

From the attached test case:
SELECT `varchar_nokey`  
FROM D  
WHERE `varchar_nokey`  IN (  
SELECT `varchar_key`  
FROM BB  
WHERE `pk`  >  9  )   ;

Returns 4 rows (correctly) in 5.1 and azalea when materialization=off and no rows in azalea with materialization=on.

Seems related to -  Bug#37115	Subquery result differs between materialization and in->exists strategies, but things seem reversed (37115 seemed incorrect without materialization and here things are incorrect *with* materialization)

How to repeat:
Run the attached test case:
Uncomment the appropriate Server0/Server1 values depending on which version is being tested.

Toggle the materialization switch on and off (Server1 version) for azalea and observe the differing results

# Server0: version = 5.1.38-debug-log
# Server1: version = 5.4.4-alpha-debug-log

# The value of optimizer_switch is distinct between the two servers:
# Server 0 : SET SESSION optimizer_switch = 'index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on';
# Server 1 : SET SESSION optimizer_switch = 'firstmatch=on,index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,loosescan=on,materialization=on,semijoin=on';

# The value of optimizer_use_mrr is distinct between the two servers:
# Server 0 : SET SESSION optimizer_use_mrr = '';
# Server 1 : SET SESSION optimizer_use_mrr = 'force';

# The value of engine_condition_pushdown is common between the two servers:
SET SESSION engine_condition_pushdown = ON ;

# The value of join_cache_level is distinct between the two servers:
# Server 0 : SET SESSION join_cache_level = '';
# Server 1 : SET SESSION join_cache_level = 1;

# Begin test case for query 0

--disable_warnings
DROP TABLE IF EXISTS D, BB;
--enable_warnings

CREATE TABLE `D` (
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `varchar_key` varchar(1) DEFAULT NULL,
  `varchar_nokey` varchar(1) DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `varchar_key` (`varchar_key`)
) ENGINE=MyISAM AUTO_INCREMENT=101 DEFAULT CHARSET=latin1;
INSERT INTO `D` VALUES (1,'o','o'),(2,'o','o'),(3,'o','o'),(4,'d','d'),(5,'v','v'),(6,'e','e'),(7,'h','h'),(8,'l','l'),(9,'m','m'),(10,'f','f'),(11,NULL,NULL),(12,'a','a'),(13,'u','u'),(14,'r','r'),(15,NULL,NULL),(16,'l','l'),(17,'q','q'),(18,'r','r'),(19,NULL,NULL),(20,NULL,NULL),(21,'j','j'),(22,'o','o'),(23,'f','f'),(24,'s','s'),(25,'a','a'),(26,'w','w'),(27,'c','c'),(28,'b','b'),(29,'c','c'),(30,'d','d'),(31,'r','r'),(32,'w','w'),(33,'r','r'),(34,'q','q'),(35,'g','g'),(36,NULL,NULL),(37,'c','c'),(38,'h','h'),(39,'n','n'),(40,'i','i'),(41,'r','r'),(42,'e','e'),(43,'b','b'),(44,'s','s'),(45,'a','a'),(46,'k','k'),(47,'k','k'),(48,'v','v'),(49,'d','d'),(50,'g','g'),(51,'l','l'),(52,'p','p'),(53,'j','j'),(54,'k','k'),(55,'n','n'),(56,'v','v'),(57,'p','p'),(58,'t','t'),(59,'r','r'),(60,'t','t'),(61,NULL,NULL),(62,'y','y'),(63,'w','w'),(64,'t','t'),(65,NULL,NULL),(66,'r','r'),(67,'e','e'),(68,'q','q'),(69,'m','m'),(70,'z','z'),(71,'x','x'),(72,'c','c'),(73,'g','g'),(74,'c','c'),(75,'k','k'),(76,'q','q'),(77,'h','h'),(78,'u','u'),(79,'x','x'),(80,'r','r'),(81,'e','e'),(82,'g','g'),(83,'a','a'),(84,'z','z'),(85,'z','z'),(86,'m','m'),(87,'x','x'),(88,'g','g'),(89,'p','p'),(90,'c','c'),(91,'x','x'),(92,'g','g'),(93,'g','g'),(94,'c','c'),(95,'q','q'),(96,'j','j'),(97,'s','s'),(98,'n','n'),(99,'f','f'),(100,'o','o');
CREATE TABLE `BB` (
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `varchar_key` varchar(1) DEFAULT NULL,
  `varchar_nokey` varchar(1) DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `varchar_key` (`varchar_key`)
) ENGINE=MyISAM AUTO_INCREMENT=12 DEFAULT CHARSET=latin1;
INSERT INTO `BB` VALUES (10,'i','i'),(11,'f','f');

 
SELECT `varchar_nokey`  
FROM D  
WHERE `varchar_nokey`  IN (  
SELECT `varchar_key`  
FROM BB  
WHERE `pk`  >  9  )   ;

# Diff:

# --- /var/folders/Pt/PtJd7NDTGgyOk3+iDGXrQk+++TI/-Tmp-///randgen69966-1249399454-server0.dump	2009-08-04 11:24:14.000000000 -0400
# +++ /var/folders/Pt/PtJd7NDTGgyOk3+iDGXrQk+++TI/-Tmp-///randgen69966-1249399454-server1.dump	2009-08-04 11:24:14.000000000 -0400
# @@ -1,4 +0,0 @@
# -f
# -f
# -f
# -i

DROP TABLE D, BB;

# End of test case for query 0

# Begin test case for query 1

--disable_warnings
DROP TABLE IF EXISTS C, D, BB;
--enable_warnings

CREATE TABLE `C` (
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `varchar_key` varchar(1) DEFAULT NULL,
  `varchar_nokey` varchar(1) DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `varchar_key` (`varchar_key`)
) ENGINE=MyISAM AUTO_INCREMENT=21 DEFAULT CHARSET=latin1;
INSERT INTO `C` VALUES (1,'g','g'),(2,'v','v'),(3,'t','t'),(4,'u','u'),(5,'n','n'),(6,'p','p'),(7,NULL,NULL),(8,'u','u'),(9,'n','n'),(10,NULL,NULL),(11,'k','k'),(12,'e','e'),(13,'d','d'),(14,'t','t'),(15,'o','o'),(16,'e','e'),(17,'s','s'),(18,NULL,NULL),(19,'d','d'),(20,'z','z');
CREATE TABLE `D` (
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `varchar_key` varchar(1) DEFAULT NULL,
  `varchar_nokey` varchar(1) DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `varchar_key` (`varchar_key`)
) ENGINE=MyISAM AUTO_INCREMENT=101 DEFAULT CHARSET=latin1;
INSERT INTO `D` VALUES (1,'o','o'),(2,'o','o'),(3,'o','o'),(4,'d','d'),(5,'v','v'),(6,'e','e'),(7,'h','h'),(8,'l','l'),(9,'m','m'),(10,'f','f'),(11,NULL,NULL),(12,'a','a'),(13,'u','u'),(14,'r','r'),(15,NULL,NULL),(16,'l','l'),(17,'q','q'),(18,'r','r'),(19,NULL,NULL),(20,NULL,NULL),(21,'j','j'),(22,'o','o'),(23,'f','f'),(24,'s','s'),(25,'a','a'),(26,'w','w'),(27,'c','c'),(28,'b','b'),(29,'c','c'),(30,'d','d'),(31,'r','r'),(32,'w','w'),(33,'r','r'),(34,'q','q'),(35,'g','g'),(36,NULL,NULL),(37,'c','c'),(38,'h','h'),(39,'n','n'),(40,'i','i'),(41,'r','r'),(42,'e','e'),(43,'b','b'),(44,'s','s'),(45,'a','a'),(46,'k','k'),(47,'k','k'),(48,'v','v'),(49,'d','d'),(50,'g','g'),(51,'l','l'),(52,'p','p'),(53,'j','j'),(54,'k','k'),(55,'n','n'),(56,'v','v'),(57,'p','p'),(58,'t','t'),(59,'r','r'),(60,'t','t'),(61,NULL,NULL),(62,'y','y'),(63,'w','w'),(64,'t','t'),(65,NULL,NULL),(66,'r','r'),(67,'e','e'),(68,'q','q'),(69,'m','m'),(70,'z','z'),(71,'x','x'),(72,'c','c'),(73,'g','g'),(74,'c','c'),(75,'k','k'),(76,'q','q'),(77,'h','h'),(78,'u','u'),(79,'x','x'),(80,'r','r'),(81,'e','e'),(82,'g','g'),(83,'a','a'),(84,'z','z'),(85,'z','z'),(86,'m','m'),(87,'x','x'),(88,'g','g'),(89,'p','p'),(90,'c','c'),(91,'x','x'),(92,'g','g'),(93,'g','g'),(94,'c','c'),(95,'q','q'),(96,'j','j'),(97,'s','s'),(98,'n','n'),(99,'f','f'),(100,'o','o');
CREATE TABLE `BB` (
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `varchar_key` varchar(1) DEFAULT NULL,
  `varchar_nokey` varchar(1) DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `varchar_key` (`varchar_key`)
) ENGINE=MyISAM AUTO_INCREMENT=12 DEFAULT CHARSET=latin1;
INSERT INTO `BB` VALUES (10,'i','i'),(11,'f','f');

 
SELECT  `varchar_nokey` AS field1 
FROM D AS table1 
WHERE (table1 . `varchar_nokey`  IN ( 
SELECT subquery_t1 . `varchar_key` 
FROM BB AS subquery_t1 LEFT  JOIN C AS subquery_t2 ON ( subquery_t2 . `varchar_key` = subquery_t1 . `varchar_nokey` ) 
WHERE subquery_t1 . `pk` > 9 ) )  
GROUP BY field1;

# Diff:

# --- /var/folders/Pt/PtJd7NDTGgyOk3+iDGXrQk+++TI/-Tmp-///randgen69966-1249399457-server0.dump	2009-08-04 11:24:17.000000000 -0400
# +++ /var/folders/Pt/PtJd7NDTGgyOk3+iDGXrQk+++TI/-Tmp-///randgen69966-1249399457-server1.dump	2009-08-04 11:24:17.000000000 -0400
# @@ -1,2 +0,0 @@
# -f
# -i

DROP TABLE C, D, BB;

# End of test case for query 1

Suggested fix:
Ensure correct processing of queries regardless of optimizer settings.

Query plans:

With materialization:
EXPLAIN SELECT `varchar_nokey` FROM D WHERE `varchar_nokey`  IN (SELECT `varchar_key` FROM BB WHERE `pk` >  9  ) ;
*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: D
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 100
        Extra: 
*************************** 2. row ***************************
           id: 1
  select_type: PRIMARY
        table: BB
         type: range
possible_keys: PRIMARY,varchar_key
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 2
        Extra: Using index condition; Using MRR; Materialize

Without materialization:
EXPLAIN SELECT `varchar_nokey` FROM D WHERE `varchar_nokey`  IN (SELECT `varchar_key` FROM BB WHERE `pk` >  9  ) ;
*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: BB
         type: range
possible_keys: PRIMARY,varchar_key
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 2
        Extra: Using index condition; Using MRR; Start temporary
*************************** 2. row ***************************
           id: 1
  select_type: PRIMARY
        table: D
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 100
        Extra: Using where; End temporary; Using join buffer

Below is a simplified test case that produces the issue. Query plan is the same.
The following is siginificant wrt observing the issue:
   - B.c needs to be varchar, not char 
   - The first row of D must have a match in B

In addition, if there is not a where-condition on the primary key of B, another plan will be chosen and the issue is not observed.

CREATE TABLE D (
  pk int,
  c varchar(1),
  PRIMARY KEY (pk)
);
INSERT INTO D VALUES (1,'o'),(2,'f');

CREATE TABLE B (
  pk int,
  c varchar(1),
  PRIMARY KEY (pk)
);
INSERT INTO B VALUES (1,'i'),(2,'f');

SELECT pk FROM D WHERE c IN (SELECT c FROM B WHERE pk > 0);

(Copied from duplicate report Bug#46551:)
The change to setup_sj_materialization shown below, fixes the problem.
That is, disabling caching of key values.  
Next step is to look into why the caching does not work ...

=== modified file 'sql/sql_select.cc'
--- sql/sql_select.cc	2009-09-29 10:45:07 +0000
+++ sql/sql_select.cc	2009-09-30 10:14:45 +0000
@@ -9791,7 +9791,7 @@ bool setup_sj_materialization(JOIN_TAB *
     tab_ref->key_buff2=tab_ref->key_buff+ALIGN_SIZE(tmp_key->key_length);
     tab_ref->key_err=1;
     tab_ref->null_rejecting= 1;
-    tab_ref->disable_cache= FALSE;
+    tab_ref->disable_cache= TRUE;
 
     KEY_PART_INFO *cur_key_part= tmp_key->key_part;
     store_key **ref_key= tab_ref->key_copy;

Observations from debugging:
When caching is not disabled, cmp_buffer_with_ref() will copy previous key from
key_buff to key_buff2, and then read the new key into key_buff.  Then, if key_buff and key_buff2 is equal, it will conclude that it is the same key as before and that the correct record already exists in the record_buffer.

However, it is observed that when a new key is read into key_buff, the actual character value is put in a position that is one byte beyond key_length.  Hence, the key_length parts of key_buff and key_buff is still equal, and it is concluded that the current row can be used.  In other words, the value of the first row of D will be used for all rows of D.  This also explains why is it significant that the first row of D does not give a match.

The working theory is that the store_key_item created in setup_sj_materialization() is not initialized correctly, either wrt buffer position or key length.

If D.c is defines as not null, the error does not occur.

The problem is that it is assumed that key_length is the same as for key_info of the temporary table.  However, when creating store_key_item, Field_varstring::new_key_field is used to create the Field object to be used for copying the key.  It contains the following:

    /* Keys length prefixes are always packed with 2 bytes */
    res->length_bytes= 2;

That way, 2 length bytes are used when copying the key, not 1 as in the original table.

Seems like I have been looking at this problem from the wrong end. Discovered a difference between table.cc:open_binary_frm() and sql_select.cc:create_tmp_table() with respect to keys:

When open_binary_frm() adds to store_length of a key_part to account for null bytes or length bytes, it also updates key_length of the parent key_info.  If the same is done in create_tmp_table(), its key_length can be used to allocate the key buffers the way it is done today.

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/86314

3649 oystein.grovlen@sun.com	2009-10-09
      Bug#46548 IN-subqueries return 0 rows with materialization=on
      
      This bug is related to key lookups in a materialized table.  A caching 
      mechanism is used to check whether you are doing lookup on the same key 
      as the last time.  In that case, the right record is assumed to already 
      be present in the record buffer (see cmp_buffer_with_ref()).
      
      The problem is that it derives the key_length from the 
      key_info of the materialized table.  However, when creating the table,
      this key_length did not take into account extra bytes used to store null
      information and length of variable length fields. When the key_length was
      not correct, cmp_buffer_with_ref() would not compare the entire key, 
      and there was a risk that it would wrongly assume that it already had 
      the right record in the buffer.
      
      The problem is fixed by also adjusting key_length of key_info when any of 
      its key_parts are adjusted (create_tmp_table()).  This is the way it is 
      already done for keys in ordinary tables (see open_binary_frm()).
     @ mysql-test/r/subselect_mat.result
        Updated result file to reflect test case for Bug#46548
     @ mysql-test/t/subselect_mat.test
        Test case for Bug#46548
     @ sql/sql_select.cc
        create_tmp_table(): When adjusting store_length of key parts, make sure
        to also update total key length as stored in associated key_info.

Patch pushed to mysql-6.0-codebase-bugfixing. 
revid:oystein.grovlen@sun.com-20091009093541-7bkrgk2tsnpi6iyf

Updated wrong report.

approved with minor comments sent by mail

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/88128

3672 oystein.grovlen@sun.com	2009-10-26
      Bug#46548 IN-subqueries return 0 rows with materialization=on
      
      This bug is related to key lookups in a materialized table.  A caching 
      mechanism is used to check whether you are doing lookup on the same key 
      as the last time.  In that case, the right record is assumed to already 
      be present in the record buffer (see cmp_buffer_with_ref()).
      
      The problem is that it derives the key_length from the 
      key_info of the materialized table.  However, when creating the table,
      this key_length did not take into account extra bytes used to store null
      information and length of variable length fields. When the key_length was
      not correct, cmp_buffer_with_ref() would not compare the entire key, 
      and there was a risk that it would wrongly assume that it already had 
      the right record in the buffer.
      
      The problem is fixed by also adjusting key_length of key_info when any of 
      its key_parts are adjusted (create_tmp_table()).  This is the way it is 
      already done for keys in ordinary tables (see open_binary_frm()).
     @ mysql-test/r/subselect_mat.result
        Updated result file to reflect test case for Bug#46548
     @ mysql-test/t/subselect_mat.test
        Test case for Bug#46548
     @ sql/sql_select.cc
        create_tmp_table(): When adjusting store_length of key parts, make sure
        to also update total key length as stored in associated key_info.
     @ sql/table.cc
        Add comment to indicate that much of the logic from open_binary_frm() has been
        duplicated in create_tmp_table()

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/91259

3722 oystein.grovlen@sun.com	2009-11-23
      Bug#46548 IN-subqueries return 0 rows with materialization=on
      
      This bug is related to key lookups in a materialized table.  A caching 
      mechanism is used to check whether you are doing lookup on the same key 
      as the last time.  In that case, the right record is assumed to already 
      be present in the record buffer (see cmp_buffer_with_ref()).
      
      The problem is that it derives the key_length from the 
      key_info of the materialized table.  However, when creating the table,
      this key_length did not take into account extra bytes used to store null
      information and length of variable length fields. When the key_length was
      not correct, cmp_buffer_with_ref() would not compare the entire key, 
      and there was a risk that it would wrongly assume that it already had 
      the right record in the buffer.
       
      The problem is fixed by making key_length of key_info always be the sum of
      the store_length of its key_parts (in create_tmp_table()).  As it is for
      ordinary tables (see open_binary_frm()).
     @ mysql-test/r/subselect_mat.result
        Updated result file to reflect test case for Bug#46548
     @ mysql-test/t/subselect_mat.test
        Test case for Bug#46548
     @ sql/sql_select.cc
        create_tmp_table(): Change the way the total key_length is computed to
        sum up the store_length for every key part.
     @ sql/table.cc
        Add comment to indicate that much of the logic from open_binary_frm() has been
        duplicated in create_tmp_table()

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/91302

3723 oystein.grovlen@sun.com	2009-11-23
      Bug#46548 (addendum)
      Remove KEY::extra_length.  It is not in use.
     @ sql/structs.h
        Remove KEY::extra_length.  It is not in use.
     @ sql/table.cc
        Remove KEY::extra_length.  It is not in use.

Patches pushed as revision ID 
oystein.grovlen@sun.com-20091123130801-cyv1ikcvpb3p5qas

Pushed into 6.0.14-alpha (revid:alik@sun.com-20091211055901-yp18b3c7xuhl87rf) (version source revid:alik@sun.com-20091211055401-43rjwq7gjed6ds83) (merge vers: 6.0.14-alpha) (pib:13)

Noted in 6.0.14 changelog.

With materialization enabled, certain subqueries with a WHERE clause
that should return rows returned no rows.

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/105087

3063 oystein.grovlen@sun.com	2010-04-06
      Bug#46548 IN-subqueries return 0 rows with materialization=on
      
      (Backporting of revid:oystein.grovlen@sun.com-20091123095520-ponntgejv3mju88o)
      
      This bug is related to key lookups in a materialized table.  A caching 
      mechanism is used to check whether you are doing lookup on the same key 
      as the last time.  In that case, the right record is assumed to already 
      be present in the record buffer (see cmp_buffer_with_ref()).
      
      The problem is that it derives the key_length from the 
      key_info of the materialized table.  However, when creating the table,
      this key_length did not take into account extra bytes used to store null
      information and length of variable length fields. When the key_length was
      not correct, cmp_buffer_with_ref() would not compare the entire key, 
      and there was a risk that it would wrongly assume that it already had 
      the right record in the buffer.
       
      The problem is fixed by making key_length of key_info always be the sum of
      the store_length of its key_parts (in create_tmp_table()).  As it is for
     @ mysql-test/r/subselect_mat.result
        Updated result file to reflect test case for Bug#46548
     @ mysql-test/t/subselect_mat.test
        Test case for Bug#46548
     @ sql/sql_select.cc
        create_tmp_table(): Change the way the total key_length is computed to
        sum up the store_length for every key part.
     @ sql/table.cc
        Add comment to indicate that much of the logic from open_binary_frm() has been
        duplicated in create_tmp_table()

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/105122

3064 oystein.grovlen@sun.com	2010-04-07
      Bug#46548 (addendum)
      
      (Backporting of revid:oystein.grovlen@sun.com-20091123130522-0zbbzdjh928zn9q0)
      
      Remove KEY::extra_length.  It is not in use.
     @ sql/structs.h
        Remove KEY::extra_length.  It is not in use.
     @ sql/table.cc
        Remove KEY::extra_length.  It is not in use.

Pushed into mysql-next-mr (revid:alik@sun.com-20100816062819-bluwgdq8q4xysmlg) (version source revid:alik@sun.com-20100816062612-enatdwnv809iw3s9) (pib:20)

Pushed into mysql-trunk 5.6.99-m5 (revid:alexander.nozdrin@oracle.com-20101113155825-czmva9kg4n31anmu) (version source revid:vasil.dimov@oracle.com-20100629074804-359l9m9gniauxr94) (merge vers: 5.6.99-m4) (pib:21)

Bug does not appear in any released 5.6.x version. No 5.6.1 changelog entry needed.