From: Roy Lyseng
Date: August 3 2010 7:42am
Subject: bzr commit into mysql-next-mr-opt-backporting branch (roy.lyseng:3222)
 Bug#51457
List-Archive: http://lists.mysql.com/commits/114897
X-Bug: 51457
Message-Id: <20100803074228.5310D1E6@tyr67.norway.sun.com>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="===============5686070350365046988=="

--===============5686070350365046988==
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

#At file:///home/rl136806/mysql/repo/mysql-work2/ based on revid:roy.lyseng@stripped

 3222 Roy Lyseng	2010-08-03
      Bug#51457: Firstmatch semijoin strategy gives wrong results for
                 certain query plans
      
      When the optimizer selects a semijoin FirstMatch plan that has
      non-correlated tables interspersed with inner tables, the "jumps"
      are placed so that execution might become incorrect.
      Example: A query with an outer correlated table ot, a non-correlated
      table nt and two inner tables it1 and it2 are used in a query and the
      optimizer chooses the FirstMatch join order ot - it1 - nt - it2.
      The optimizer assigns a "jump" from table it2 to ot. This strategy will
      omit duplicates resulting from table nt.
      
      The fix assures that the jump from the last table in a consecutive
      range of inner table goes to the most immediately preceeding outer
      table (regardless of whether the outer table is correlated or not).
      In this case, there are two consecutive ranges of inner tables:
      {it1} and {it2}. In the first range, the last inner table is it1, the
      jump should be to table ot. In the second range, the jump from it2
      should be to nt.
      
      It is currently possible to generate such query plans, hence the
      bug fix includes some test cases. However, such plans are probably
      generated due to a problem with the join optimizer cost model.
      When this problem is fixed, it may be impossible to generate
      such FirstMatch plans, unless one can assign different costs
      to different tables, or another measure is used to force a specific
      join order.
      
      mysql-test/r/subselect_innodb.result
        Test results for bug#51457.
      
      mysql-test/t/subselect_innodb.test
        Test case for bug#51457. Notice the above comment for test validity.
        The test goes into subselect_innodb because it is required to use
        tables with one row that are not hit by const table optimization.
      
      sql/sql_select.cc
        In setup_semijoin_dups_elimination(), in the case for FIRST_MATCH,
        loop over the set of inner and non-correlated outer tables and assign
        jump target to the last table in each consecutive range of inner
        tables. The jump target should be the most immediately preceeding
        outer table.

    modified:
      mysql-test/r/subselect_innodb.result
      mysql-test/t/subselect_innodb.test
      sql/sql_select.cc
=== modified file 'mysql-test/r/subselect_innodb.result'
--- a/mysql-test/r/subselect_innodb.result	2010-06-19 13:22:14 +0000
+++ b/mysql-test/r/subselect_innodb.result	2010-08-03 07:40:15 +0000
@@ -392,3 +392,87 @@ and t2.a='1' AND t1.a=t3.b) > 0;
 a
 2
 DROP TABLE t1,t2,t3;
+#
+# Bug#51457 Firstmatch semijoin strategy gives wrong results for
+#           certain query plans
+#
+DROP TABLE IF EXISTS t0, t1, t2, t6, t8;
+SET @@default_storage_engine='innodb';
+SET @@optimizer_switch='semijoin=on,materialization=off,firstmatch=on,loosescan=off';
+SET @@optimizer_join_cache_level=0;
+CREATE TABLE t0(a INTEGER);
+CREATE TABLE t1(a INTEGER);
+INSERT INTO t1 VALUES(1);
+CREATE TABLE t2(a INTEGER);
+INSERT INTO t2 VALUES(5), (8);
+CREATE TABLE t6(a INTEGER);
+INSERT INTO t6 VALUES(7), (1), (0), (5), (1), (4);
+CREATE TABLE t8(a INTEGER);
+INSERT INTO t8 VALUES(1), (3), (5), (7), (9), (7), (3), (1);
+EXPLAIN
+SELECT *
+FROM t2 AS nt2
+WHERE 1 IN (SELECT it1.a
+FROM t1 AS it1 JOIN t6 AS it3 ON it1.a=it3.a);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	it1	ALL	NULL	NULL	NULL	NULL	1	Using where; FirstMatch
+1	PRIMARY	nt2	ALL	NULL	NULL	NULL	NULL	2	
+1	PRIMARY	it3	ALL	NULL	NULL	NULL	NULL	6	Using where; FirstMatch(nt2)
+SELECT *
+FROM t2 AS nt2
+WHERE 1 IN (SELECT it1.a
+FROM t1 AS it1 JOIN t6 AS it3 ON it1.a=it3.a);
+a
+5
+8
+EXPLAIN
+SELECT *
+FROM t2 AS nt2, t8 AS nt4
+WHERE 1 IN (SELECT it1.a
+FROM t1 AS it1 JOIN t6 AS it3 ON it1.a=it3.a);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	it1	ALL	NULL	NULL	NULL	NULL	1	Using where; FirstMatch
+1	PRIMARY	nt2	ALL	NULL	NULL	NULL	NULL	2	
+1	PRIMARY	it3	ALL	NULL	NULL	NULL	NULL	6	Using where; FirstMatch(nt2)
+1	PRIMARY	nt4	ALL	NULL	NULL	NULL	NULL	8	
+SELECT *
+FROM t2 AS nt2, t8 AS nt4
+WHERE 1 IN (SELECT it1.a
+FROM t1 AS it1 JOIN t6 AS it3 ON it1.a=it3.a);
+a	a
+5	1
+5	3
+5	5
+5	7
+5	9
+5	7
+5	3
+5	1
+8	1
+8	3
+8	5
+8	7
+8	9
+8	7
+8	3
+8	1
+EXPLAIN
+SELECT *
+FROM t0 AS ot1, t2 AS nt3
+WHERE ot1.a IN (SELECT it2.a
+FROM t1 AS it2 JOIN t8 AS it4 ON it2.a=it4.a);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	ot1	ALL	NULL	NULL	NULL	NULL	1	
+1	PRIMARY	it2	ALL	NULL	NULL	NULL	NULL	1	Using where; FirstMatch(ot1)
+1	PRIMARY	nt3	ALL	NULL	NULL	NULL	NULL	2	
+1	PRIMARY	it4	ALL	NULL	NULL	NULL	NULL	8	Using where; FirstMatch(nt3)
+SELECT *
+FROM t0 as ot1, t2 AS nt3
+WHERE ot1.a IN (SELECT it2.a
+FROM t1 AS it2 JOIN t8 AS it4 ON it2.a=it4.a);
+a	a
+DROP TABLE t0, t1, t2, t6, t8;
+SET @@default_storage_engine=default;
+SET @@optimizer_switch=default;
+SET @@optimizer_join_cache_level=default;
+# End of bug#51457

=== modified file 'mysql-test/t/subselect_innodb.test'
--- a/mysql-test/t/subselect_innodb.test	2010-06-18 08:45:53 +0000
+++ b/mysql-test/t/subselect_innodb.test	2010-08-03 07:40:15 +0000
@@ -401,3 +401,71 @@ SELECT t1.* FROM t1 WHERE (SELECT COUNT(
                            and t2.a='1' AND t1.a=t3.b) > 0;
 
 DROP TABLE t1,t2,t3;
+
+--echo #
+--echo # Bug#51457 Firstmatch semijoin strategy gives wrong results for
+--echo #           certain query plans
+--echo #
+
+--disable_warnings
+DROP TABLE IF EXISTS t0, t1, t2, t6, t8;
+--enable_warnings
+
+SET @@default_storage_engine='innodb';
+SET @@optimizer_switch='semijoin=on,materialization=off,firstmatch=on,loosescan=off';
+SET @@optimizer_join_cache_level=0;
+
+CREATE TABLE t0(a INTEGER);
+
+CREATE TABLE t1(a INTEGER);
+INSERT INTO t1 VALUES(1);
+
+CREATE TABLE t2(a INTEGER);
+INSERT INTO t2 VALUES(5), (8);
+
+CREATE TABLE t6(a INTEGER);
+INSERT INTO t6 VALUES(7), (1), (0), (5), (1), (4);
+
+CREATE TABLE t8(a INTEGER);
+INSERT INTO t8 VALUES(1), (3), (5), (7), (9), (7), (3), (1);
+
+EXPLAIN
+SELECT *
+FROM t2 AS nt2
+WHERE 1 IN (SELECT it1.a
+            FROM t1 AS it1 JOIN t6 AS it3 ON it1.a=it3.a);
+
+SELECT *
+FROM t2 AS nt2
+WHERE 1 IN (SELECT it1.a
+            FROM t1 AS it1 JOIN t6 AS it3 ON it1.a=it3.a);
+
+EXPLAIN
+SELECT *
+FROM t2 AS nt2, t8 AS nt4
+WHERE 1 IN (SELECT it1.a
+            FROM t1 AS it1 JOIN t6 AS it3 ON it1.a=it3.a);
+
+SELECT *
+FROM t2 AS nt2, t8 AS nt4
+WHERE 1 IN (SELECT it1.a
+            FROM t1 AS it1 JOIN t6 AS it3 ON it1.a=it3.a);
+
+EXPLAIN
+SELECT *
+FROM t0 AS ot1, t2 AS nt3
+WHERE ot1.a IN (SELECT it2.a
+                FROM t1 AS it2 JOIN t8 AS it4 ON it2.a=it4.a);
+
+SELECT *
+FROM t0 as ot1, t2 AS nt3
+WHERE ot1.a IN (SELECT it2.a
+                FROM t1 AS it2 JOIN t8 AS it4 ON it2.a=it4.a);
+
+DROP TABLE t0, t1, t2, t6, t8;
+
+SET @@default_storage_engine=default;
+SET @@optimizer_switch=default;
+SET @@optimizer_join_cache_level=default;
+
+--echo # End of bug#51457

=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc	2010-07-30 07:32:20 +0000
+++ b/sql/sql_select.cc	2010-08-03 07:40:15 +0000
@@ -1509,9 +1509,26 @@ int setup_semijoin_dups_elimination(JOIN
       {
         JOIN_TAB *jump_to= tab - 1;
         DBUG_ASSERT(tab->emb_sj_nest != NULL); // First table must be inner
-        if (!tab->emb_sj_nest)
-          jump_to= tab;         /// @todo fix this (BUG#51457)
-        tab_end->do_firstmatch= jump_to;
+        for (JOIN_TAB *j= tab; j <= tab_end; j++)
+        {
+          if (!j->emb_sj_nest)
+          {
+            /*
+              Let last non-correlated table be jump target for
+              subsequent inner tables.
+            */
+            jump_to= j;
+          }
+          else
+          {
+            /*
+              Assign jump target for last table in a consecutive range of 
+              inner tables.
+            */
+            if (j == tab_end || !(j+1)->emb_sj_nest)
+              j->do_firstmatch= jump_to;
+          }
+        }
         i+= pos->n_sj_tables;
         break;
       }


--===============5686070350365046988==
MIME-Version: 1.0
Content-Type: text/bzr-bundle; charset="us-ascii";
	name="bzr/roy.lyseng@stripped"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

# Bazaar merge directive format 2 (Bazaar 0.90)
# revision_id: roy.lyseng@stripped
# target_branch: file:///home/rl136806/mysql/repo/mysql-work2/
# testament_sha1: a6e813aff4ace183062507c150195b098bdedef0
# timestamp: 2010-08-03 09:42:28 +0200
# base_revision_id: roy.lyseng@stripped\
#   4ftoia6pm7120ehc
# 
# Begin bundle
IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWRpC9L0ABsLfgAX0eP///3/3
3+C////+YA6ffbfPWbG2ahRbAUGvaGbXTiaZsbWbaigjsylQUTw1RDCNGRoDQ0AA0ZBoZAAZNDQA
AkqaNT1NkgyYp6NU9TaMamoeoaAGjIG1ANAB6hzCaMjQ0MhhGhkNNGgAxGTIBhAMAkRCBGgRpNoR
6UzBRPFHtU8po/Smg2p6mgaNNACKRFNo1Gh6hB6jIaGExD1AZMTaTageRomEwJIggExGmmgjJqaZ
NEZNE9JtE0yNMmQxAYlAkbc1y9YcRx044zOOOOO8VFcFxPyVAJFKOmWpcJwDlPWyT8ONwuFmN65s
axCHqhriUrtlin4kh3tFaJRjnwiFKxw+xnqIgmAoHAWxZE40wocPAfw7nE82jwflj6ItGLxuPQH9
zAgctN7+3wjKUoO8pRaIZ2F9UoWtttt6s50PB1fXy+YLCYFQJro/cRocQ4e1xZtA7Z9Yxt7QpSq9
m+glTVuu7uSXatcsV6tdX1aL1X9oyXG10ma6/4WgLZEgAcItIhC32v2IdxCFNwBbaW+4F5dhXqW9
eCbYxnb94Wpb9gEHPMdtpJIc4tCLQ/PybUC4TBcwPQHMEwVHI/kMadTdl6YBb5zxzLwOYliB1kRA
xDxh4gcA+8rGGApGxRVEpKVl1Bp1MjqKmX65+HuRsa6a02Qd/nuauV/IOGVHk5ngateN1i6NFcqS
8EddiWS3Bb8MPx774qUVrnytRkxudka1W7VE6Ss/jEMv/b94FjrA9YF9A033WCwVBdh9ttLXK+NI
zfM6TNYob15s6UtnG56QBpjTbFXOWNrnAriVUVM3cGlE76tK8FK7RMzMntxHpu5o+djjAo3hIQfK
o33pnvc1Mxz3/oE6oImAuogqEgMJJIDmAkkkJBhJJAb1o16kznInRQh76QoewMyNwv+37dttOTma
HJTQ9N9nbJuTkamXRqa4wadMIyzFy3lMrWTmP2w9PxGXXXr1Hx+1vh8Oi2zl0IozWNCfvbG23ypX
GZUKaWHWMbbSGBkIsPI4npPUSP6cwf7tpTTRseBoZERyAWkD3EgkcZ1fm9fx6EGCLxi8AIi+kvBf
aNh8x+P8RCt6v5n67Q1AZgbweXgm5nYF67kupwETDzgGn06g7DtzMuRqD2imNug246eh8hXLfMbu
p1lMruFOlvhbCY3b+AYDBjDfvG02nAEhYM9GhJRmkvAD6jodipnOhdVVlMspEnC1jvGCIR2DhIWA
MIdAax1iI49pANUYiIEgnI05UVTKWAcRAYcRMiQKxiSKl4mJLdVK0O7n9WtdUh1VrcD03ubMzsSC
kBiXIL1MIQl7dIg8sQYZTj20YA6JOa9UEuNEIVWwmzSW4es1+ZEijS7uLPgEUaKjfGC+i7dr51R8
jasFtNRaTMFl9AjfM4aTE1xI3y1COPamVDCSNtISChgC3FEC28JxotK0bzTNphoWFuykrgcD1FdW
jCrN3I7u3bfxEbdwV6A4WRcDx0foGjgVg8xFAMOwT3G6YWQI89lG4nwnvsRFo30HEiO+qJLdwNvt
x2FVbhvLnDaO4TEX9NCSWu4gQgG62WvcQmlMjsNhhE7p1tmFRU/6FH6ZhE/U8AOwbbRq0Lro6Cgk
YtBvrS5LfDIJ65TIpLKCMUIo6TTiM5wYs1zx5qHTN7ZaXHKQ3mcp0cYBpbv7C840Dkzd3FxXwnmV
V58bEbyAXJqgt4czUYbAq2RI8xOUF5bxDfvtMj9+QGTCLOBYeVBesZ05owrO3FXnIpzGN5Hd1Aah
+IK/QtKWEZvHGJeNwNW3hGouqMIdjGUduAcxG6cxHr2lxkai4tNZs5yDvkSyOhlsdqzM7s9mlFxQ
9tsVZjB5UuE6KIoc60RYMBYYPmr7kieP1VmtUKD+pQYyRahbufl2A1nW32fjZssTHarEoIpOBYw5
A4AphAY7/lXhrwWwcgTgDcVtUciuIdZTsA5FKREjjE5/ltITBkCU1PHGoigCYfYBkUEQEAoEqkAz
EwAPSJgBkB2AQDWWxgjNesnMMAQHSQJMG6J1f8GbnKWDIH+g2gJCEubtJtBAO7oqjkHeFzAHQBSt
QqqrAc9Tu2EJCEwYFDRBSKfEB3I2AMATBMMRUJFwkZCMEjYAv2C2QGCRyYQjUQAxBbQX+QHBUF9o
KYJwHBbMRLFIvEHBSYNs5gKAkbBSBQSxAxSNNuKcF884X6LzNhD9BJDGwHxKKtz3BioGsgLYORq8
1n6D+QrLko5FyMOgRCVgkE14mkDER5j0GP29HSHSTkwKBLughFkGCKsdfMQ9wWWJKX5Vqb7q2EZL
57lmp5cM84L5ExORY/XPQ1rQYB/g4UMQYYI2eVQf6UNMGtJVtDDWSXvXvXARnKX7quDMI++X1hQd
uZziaKw79qIm1zSaA2DMmJjAvZ+Aj6jlSi4wqiA/NjEx+4if1Id7+0IFkhgr17vAPwPDp0o6rz56
Kwj+yvDwJzcdmZKpkqohejU4lpKuaApXhEIpwhjbPyFEBc5aL07fQoUAxsGxtj9C6d+XSVP577pK
Y6OBkjJDuERNSsHnCkNq+AtwSWk1ms5H++nIawsGGaiqUwaj+V14HpyF0rpOtevrij870z1TaVBc
R7GvBl1IqqsVJPBORjkuV8mOEYmHDAgwMTKiQa9xvMPPd9OJxJE2l2HLlwKbrxfAti2hhcxtZ7gp
EwtoOdThCryuuOaOMN8a0B5QC8zdx2TyaMTqWGBeV6eeg9LNpmXVtLqRElJQF8MrMN6fHoidcw1B
AVaA175jKW4FkpUj1xcdSqAQGHDtgWhNFXu0PiQ8d0Uo2NFLipWrAqqpcTCph6I6FFBazueu2jPC
1s0yhYgqxndBrp72NmsYTclkfXhBs0k4h7rhdmKXRBZwWOAyXmzBhc26F9AQNCHMc6RJCI+kmSie
EBW2DOyfNXKkNH6GKbsEUsYb4gNsQZRoQtJnmZIZLg6SyXeOjdyYRYYRiFThFd/zCIrmdDt8bjV0
Zh4nnXI220m0ZG0gD1AaKhcDA72m0Ng6hj2fxLrLtSZdNwsFU3d/A5ksF3bTE4z6QzLUYEVZIN4M
Cy8SV5m1234zCrmMmEIkpyNB13VlzIWgbGBl3Jk+bpVwOwXANuFTXizKBSZv/uMCD9XdxtiYNgx7
uT5AmvZiDbefMKdtD4jJC/V3AHccD3gO4OHACVNJcG1WKXAvUBDAx3N7P9/D21/1gfER7fZUwhHQ
D40KMPJ+qPUd+zgLFZeJAvLV6zUb9wbGMKinokCgYAbESKh1ryRgmktiShXNSiyAZpXVAi/toFrv
C9qG6y33E4AtRe6L+nPB6D5El3P6gZgD5CgxCEeReLMjVQqbVPSvDkPhS5KbrQhaGSZiPdctwGTP
foCb9NbuYt8fE1K2jBGMQ9MKWvm1DizHaqQ6RsasMkq0RGpTFIGvtKwqUE5IB9SCV1G8qSyqYoSV
hMINO00SCMEjJbGX6ruURKlrIPoHY0IZ6hh9QwhhEQErQ202jrPSQXycfiRl62BmCbLBinFbEiL6
y4D2BQHaJSDvEFebmBQFgOghUeVKgjwwYhm0ytjmB85kKDJmgksBDwMnViXfJVp0ZESjAZab3AhR
/PysaU2YsMkOGFde6XIW8hqyKqYYSSewaTKy8suAtf9gbpptVZlGUSYIWzzHLJ6Q0ZguOmh6dInr
PLAljY22NNt9jSIZL7n+DSNKqgXPgcWUlIJKqGt0OK40825dkBSJg7Irp9YOjfc4UTBlhcGkT3Xr
DuDqqY6Wa1qDafGDJ/felsxMwDaIgKNtDM1xWmqe7bLui8JCVD6SpJI2mYMZuMwHeNCjpPyqlmUL
xwtGbO4IHHQOxBvU0fORyAJabrGKCB8LFCh2NrQfkLaKSPNoHwtsLz0L0NtuOTPaGdrUKHMtiNp9
zJCSG8JhZQKUDKbivDYK4KWrLbXHe4iVpfBTdlYG0ffdhNn3b7FIpkTSbQp91rOhDGwpaZvauMbL
jIwpseoRTFQCYDGyEMIQQDEWE5BMGMZAwYQIbGDAbAbYMCAD3sAwFlcgssEEd4qhErlEXLqXJADa
SlVgMELIGGDSKM86OEGh9yvT5zMkT7DIJAWzJ16qol+88yFXfMGCerAVhZrZEWDceYJiIrPlUhLn
QGqiNmWJG9ZKDPERxaxj6fzsXnXzGPwnkW7A5RDR3pG0jZ1aZdoOWsswRKMsjA1nru23tcoWUxK3
fm9IygsC3inzDxSyHrBhtOMKq8DM9wi+fsEe/5e/GnxJ8iKU0yqt7uPN+KYJJ3Nc0k9CzMikmKK+
ypJe0VW4LcUguITp5cTI+z6zx5fq0Yial/F3JFOFCQGkL0vQ


--===============5686070350365046988==--