Fixed LP bug #899777.

KEYUSE elements for a possible hash join key are not sorted by field
numbers of the second table T of the hash join operation. Besides
some of these KEYUSE elements cannot be used to build any key as their
key expressions depend on the tables that are planned to be accessed
after the table T. 
The code before the patch did not take this into account and, as a result,
execition of a query the employing block-based hash join algorithm could
cause a crash or return a wrong result set. 

4 files changed, 135 insertions, 14 deletions

diff --git a/mysql-test/r/join_cache.result b/mysql-test/r/join_cache.result
index be579c9240f..8372f68fde0 100644
--- a/mysql-test/r/join_cache.result
+++ b/mysql-test/r/join_cache.result
@@ -5179,4 +5179,51 @@ a	b
 SET SESSION join_cache_level = DEFAULT;
 SET optimizer_switch=@tmp887479_optimizer_switch;
 DROP TABLE t1,t2;
+#
+# Bug #899777: join_cache_level=4 + semijoin=on 
+#
+CREATE TABLE t1 (a int, b int, c int, UNIQUE INDEX idx (a));
+INSERT INTO t1 VALUES (1,8,6), (2,2,8);
+CREATE TABLE t2 (a int, b int, c int, UNIQUE INDEX idx (a));
+INSERT INTO t2 VALUES (1,8,6), (2,2,8);
+CREATE TABLE t3 (a int, b int, c int, UNIQUE INDEX idx (a));
+INSERT INTO t3 VALUES (1,8,6), (2,2,8);
+CREATE TABLE t4 (a int, b int, c int, UNIQUE INDEX idx (a));
+INSERT INTO t4 VALUES (1,8,6), (2,2,8);
+SET @tmp_optimizer_switch=@@optimizer_switch;
+SET SESSION optimizer_switch='semijoin=on';
+SET SESSION optimizer_switch='semijoin_with_cache=on';
+SET SESSION join_cache_level=1;
+EXPLAIN 
+SELECT t1.* FROM t1,t2
+WHERE (t1.b,t2.b) IN (SELECT t3.b,t4.b FROM t3,t4 WHERE t4.c=t3.b)
+AND t1.a = 1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	const	idx	idx	5	const	1	
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	2	
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	2	Using where; Start temporary; Using join buffer (flat, BNL join)
+1	PRIMARY	t4	ALL	NULL	NULL	NULL	NULL	2	Using where; End temporary; Using join buffer (flat, BNL join)
+SELECT t1.* FROM t1,t2
+WHERE (t1.b,t2.b) IN (SELECT t3.b,t4.b FROM t3,t4 WHERE t4.c=t3.b)
+AND t1.a = 1;
+a	b	c
+1	8	6
+SET SESSION join_cache_level=4;
+EXPLAIN 
+SELECT t1.* FROM t1,t2
+WHERE (t1.b,t2.b) IN (SELECT t3.b,t4.b FROM t3,t4 WHERE t4.c=t3.b)
+AND t1.a = 1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	const	idx	idx	5	const	1	
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
+1	PRIMARY	t3	hash_ALL	NULL	#hash#$hj	5	const	2	Using where; Start temporary; Using join buffer (flat, BNLH join)
+1	PRIMARY	t4	hash_ALL	NULL	#hash#$hj	10	const,test.t2.b	2	Using where; End temporary; Using join buffer (incremental, BNLH join)
+SELECT t1.* FROM t1,t2
+WHERE (t1.b,t2.b) IN (SELECT t3.b,t4.b FROM t3,t4 WHERE t4.c=t3.b)
+AND t1.a = 1;
+a	b	c
+1	8	6
+SET SESSION join_cache_level = DEFAULT;
+SET optimizer_switch=@tmp_optimizer_switch;
+DROP TABLE t1,t2,t3,t4;
 set @@optimizer_switch=@save_optimizer_switch;
diff --git a/mysql-test/t/join_cache.test b/mysql-test/t/join_cache.test
index 530528ead2c..66381150ede 100644
--- a/mysql-test/t/join_cache.test
+++ b/mysql-test/t/join_cache.test
@@ -3254,5 +3254,45 @@ SET optimizer_switch=@tmp887479_optimizer_switch;
 
 DROP TABLE t1,t2;
 
+--echo #
+--echo # Bug #899777: join_cache_level=4 + semijoin=on 
+--echo #
+
+CREATE TABLE t1 (a int, b int, c int, UNIQUE INDEX idx (a));
+INSERT INTO t1 VALUES (1,8,6), (2,2,8);
+CREATE TABLE t2 (a int, b int, c int, UNIQUE INDEX idx (a));
+INSERT INTO t2 VALUES (1,8,6), (2,2,8);
+CREATE TABLE t3 (a int, b int, c int, UNIQUE INDEX idx (a));
+INSERT INTO t3 VALUES (1,8,6), (2,2,8);
+CREATE TABLE t4 (a int, b int, c int, UNIQUE INDEX idx (a));
+INSERT INTO t4 VALUES (1,8,6), (2,2,8);
+
+SET @tmp_optimizer_switch=@@optimizer_switch;
+SET SESSION optimizer_switch='semijoin=on';
+SET SESSION optimizer_switch='semijoin_with_cache=on';
+
+SET SESSION join_cache_level=1;
+EXPLAIN 
+SELECT t1.* FROM t1,t2
+  WHERE (t1.b,t2.b) IN (SELECT t3.b,t4.b FROM t3,t4 WHERE t4.c=t3.b)
+        AND t1.a = 1;
+SELECT t1.* FROM t1,t2
+  WHERE (t1.b,t2.b) IN (SELECT t3.b,t4.b FROM t3,t4 WHERE t4.c=t3.b)
+        AND t1.a = 1;
+
+SET SESSION join_cache_level=4;
+EXPLAIN 
+SELECT t1.* FROM t1,t2
+  WHERE (t1.b,t2.b) IN (SELECT t3.b,t4.b FROM t3,t4 WHERE t4.c=t3.b)
+        AND t1.a = 1;
+SELECT t1.* FROM t1,t2
+  WHERE (t1.b,t2.b) IN (SELECT t3.b,t4.b FROM t3,t4 WHERE t4.c=t3.b)
+        AND t1.a = 1;
+
+SET SESSION join_cache_level = DEFAULT;
+SET optimizer_switch=@tmp_optimizer_switch;
+
+DROP TABLE t1,t2,t3,t4;
+
 # this must be the last command in the file
 set @@optimizer_switch=@save_optimizer_switch;
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 7c36f7c4d8c..8bb490e5045 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -7183,10 +7183,26 @@ static bool create_hj_key_for_table(JOIN *join, JOIN_TAB *join_tab,
 
   do
   {
-    if (!(~used_tables & keyuse->used_tables) &&
-	(first_keyuse || keyuse->keypart != (keyuse-1)->keypart))
-      key_parts++;
-    first_keyuse= FALSE;
+    if (!(~used_tables & keyuse->used_tables))
+    {
+      if (first_keyuse)
+      {
+        key_parts++;
+        first_keyuse= FALSE;
+      }
+      else
+      {
+        KEYUSE *curr= org_keyuse;
+        for( ; curr < keyuse; curr++)
+        {
+          if (curr->keypart == keyuse->keypart &&
+              !(~used_tables & curr->used_tables))
+            break;
+        }
+        if (curr == keyuse)
+           key_parts++;
+      }
+    }
     keyuse++;
   } while (keyuse->table == table && keyuse->is_for_hash_join());
   if (!key_parts)
@@ -7211,15 +7227,31 @@ static bool create_hj_key_for_table(JOIN *join, JOIN_TAB *join_tab,
   keyuse= org_keyuse;
   do
   {
-    if (!(~used_tables & keyuse->used_tables) &&
-        (first_keyuse || keyuse->keypart != (keyuse-1)->keypart))
-    {
-      Field *field= table->field[keyuse->keypart];
-      uint fieldnr= keyuse->keypart+1;
-      table->create_key_part_by_field(keyinfo, key_part_info, field, fieldnr);
-      first_keyuse= FALSE;
-      key_part_info++;
+    if (!(~used_tables & keyuse->used_tables))
+    { 
+      bool add_key_part= TRUE;
+      if (!first_keyuse)
+      {
+        for(KEYUSE *curr= org_keyuse; curr < keyuse; curr++)
+        {
+          if (curr->keypart == keyuse->keypart &&
+              !(~used_tables & curr->used_tables))
+	  {
+            keyuse->keypart= NO_KEYPART;
+            add_key_part= FALSE;
+            break;
+          }
+        }
+      }
+      if (add_key_part)
+      {
+        Field *field= table->field[keyuse->keypart];
+        uint fieldnr= keyuse->keypart+1;
+        table->create_key_part_by_field(keyinfo, key_part_info, field, fieldnr);
+        key_part_info++;
+      }
     }
+    first_keyuse= FALSE;
     keyuse++;
   } while (keyuse->table == table && keyuse->is_for_hash_join());
 
@@ -7302,8 +7334,7 @@ static bool create_ref_for_key(JOIN *join, JOIN_TAB *j,
       {
         if  (are_tables_local(j, keyuse->val->used_tables()))
         {
-          if ((is_hash_join_key_no(key) && 
-              (keyparts == 0 || keyuse->keypart != (keyuse-1)->keypart)) ||
+          if ((is_hash_join_key_no(key) && keyuse->keypart != NO_KEYPART) ||
               (!is_hash_join_key_no(key) && keyparts == keyuse->keypart &&
                !(found_part_ref_or_null & keyuse->optimize)))
           {
@@ -7357,6 +7388,7 @@ static bool create_ref_for_key(JOIN *join, JOIN_TAB *j,
     for (i=0 ; i < keyparts ; keyuse++,i++)
     {
       while (((~used_tables) & keyuse->used_tables) || 
+             keyuse->keypart == NO_KEYPART ||
 	     (keyuse->keypart != 
               (is_hash_join_key_no(key) ?
                  keyinfo->key_part[i].field->field_index : i)) || 
diff --git a/sql/sql_select.h b/sql/sql_select.h
index 4333b825c28..ffe3985c3c3 100644
--- a/sql/sql_select.h
+++ b/sql/sql_select.h
@@ -77,6 +77,8 @@ typedef struct keyuse_t {
   bool is_for_hash_join() { return is_hash_join_key_no(key); }
 } KEYUSE;
 
+#define NO_KEYPART ((uint)(-1))
+
 class store_key;
 
 const int NO_REF_PART= uint(-1);