From: Roy Lyseng
Date: August 4 2010 7:07am
Subject: bzr push into mysql-next-mr-opt-backporting branch (roy.lyseng:3221 to 3222)
 Bug#51457
List-Archive: http://lists.mysql.com/commits/114977
X-Bug: 51457
Message-Id: <20100804070755.BE3E41E6@tyr67.norway.sun.com>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="===============1721740234323108037=="

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

 3222 Roy Lyseng	2010-08-04
      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
 3221 Roy Lyseng	2010-07-30
      Delete redundant and erroneous call to print_plan().
      This function is only called in debug mode, so implication is minor.

    modified:
      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-04 07:05:47 +0000
@@ -392,3 +392,86 @@ 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
+#
+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-04 07:05:47 +0000
@@ -401,3 +401,67 @@ 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 #
+
+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-04 07:05:47 +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;
       }


--===============1721740234323108037==
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: 46b0a9cfabb50fc0f5e037036363f04db4e7e60c
# timestamp: 2010-08-04 09:07:55 +0200
# base_revision_id: roy.lyseng@stripped\
#   4ftoia6pm7120ehc
# 
# Begin bundle
IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWTVy3eMABq5fgAX0eP///3/3
3+C////+YA5ffbvvbRGVqrYW1VAJhUmzp12mCRTQSJKWzUiq4aimanojQaBoaNAAAAADQAAAASkC
MgJgaTImJM1PKmJ5I9QGQ0bRNGhoDEOYTRkaGhkMI0Mhpo0AGIyZAMIBgEiIRCp/qYAp+qR+o9SN
piT0mmRoGJphNMg0aaaaCNRRpo0ADQGgAAAaDIA0AAABIkTQEYmpk0DRppGVPKb1R7UTT0Q0GTTQ
9CBo9SsSNu5dfmHUQQoIG4IIIIiamuldR+CrBIQBBQkT5CxkGg9A4LSOIYDAZEHFKgRgRTjBQx27
t0jV/FJz7QNhVUnKhKU1uPrxBUKHBgsBTFAMJHMN3gJu6nBylIhr0sZya1dJyD2moYQjkvy8Wuc5
i1uc1TQwmN0HMrUpTbbeV3OXy7eoFhMCoE1y+UjK4hw9DjS7kDr1cBjbzCc6l57piU8tlfjpJ0qq
vuXhnU+zCxdH4yLdTpW58X9zgE5KQAJRDAUIJ8dJuSEvAQSjMEtpb1AvDyleC3LoTbGM7XsC1LeQ
CDGY7VpJJ69Gxqme7mqoEzkBNwHINwIoIGwI8DG7mwJ+o40gdAiVgcGjQKw4s4gZBrPYKAeOUq8g
QMDrtOnwLZgYLfjZ0eRi3S0Znhnl+E0rk7JuJKLcKnUxmZXqmusXR8Vc1JeRHGxLJbgt7cnu5r4q
UVrntajMxudMaFW7PE4FZ90Qy/yewCx2AOkC+gYX3WCwVBcp5rYNbXxpHI97pM1ihuXU5KUtyRre
AA7Ds9Kwgveyki6ZbXa3xDfXTG3fdkqtW9NtqMMy5VfZUXZxWalK4Jl91qldTC66upRlnZ8AzBgv
vIJkgGEiSDeBJJJIMJJINyzZ+RMxInNQh7aQoegNRGwX/rM86ar3KUzSeD1WUdL26oJ2tdzsunJ0
slN2AmzIe6hSLLO9nUdl/TbbUeXtV4+OKMvnzRG6haCK7lKG23uS3GJUE9bDvGNtpDBoRgfmLjQ9
g49O0F+rAe+W9bDtLhosYFAw7hwONJIe5c3zcxignE5xICYv2mIL7B5frPv/cIWHKPCOW01i3C6C
KuCK3G0K04IdI4OsAj56Q0ENp0Yl+wqDyoSEWPeceeNguRY2HyX6i+uGN++32WyTGucQvGDGG3aN
ptOAJBQNV96SjUkvWB9R2nWrKUrVqt2UJViUBezkMmE8SAqFiDEQIMiF1mCCAeGcioKb+kR4XXiJ
9tZaVsRAFBiJQOhBNFq8TqMLCeoRqDnOH1aLikQs6QuYHrucq2Y0JApAYltF8zCEhd3OIPDlCDqm
vpxwDx0/C2IQxsCijTZnUqNVQ2HyINRiJ2VxRuS081OOrfQ3mXpUlRcbPLNd50wLmN8urgmrRoEw
aQNc2QYg64AKK0GEgOk2A5UdDFbQyIE2D0UQff8hCiKxFk5tWvjwz2ZxoFfMEBbOALX2hjAFgRQK
EMJBTajWCq7NJXYGULtjCMaENwwXeKHlws2SGPbVgX35yDuMIDnIgMaygiaWzA7SUgzhKCrE5s0j
fJWpoPIEgzVMQPeL994SHwPEIcQNwqZ9kStkRL7WK9CJeMui6KohpjQPKhCGhvY/OI0SVVw3WdWh
iTXU/hMUdZbYWbRCXYLOJ2k/xNxDPgIRsWFnRcbVGIxjUjJdLIaYCTk5IaiplTcwVrlJTbaD4NNw
lggsU8rELTMMsqSs+qUBZTcqjjxp1mhWOYXpvfNkgzLJxabBbBQ4br8AClbASfMwBIsfcb8S+I95
ZAaV3uSYukvrIEaZ5z5bjaXGocULuXDc0OtpbkXlu5VJRE4KfVLQEi1zxwmWtz1g6WVqCmakFyBa
K217qvRIl2+2qqpCq/uTGMkLEWnV19gO/jh+n4X6XjHwV6UIsOgvZBI7QVAkM5fOvV62WgvvCTA7
iSup50L1i5kj3gedIqIQ/KIx9GohMGQCmp05aiKAJn4gSIYZgTEXwApEfkAv7EfkCgD3gMFeLMPO
ogPIDD+hiJBYCPb/oKc6RpFAL1ArgIEEf5CkYL7dSSF8Be8FgAswSLkgssuAX5JHx8UECCQJiQaw
SHXeB8ELSApBMsf8K5IwEjYIySNAF8TCoDJI62IRAGYLaC/wBALXeCqBQBALTIFYkViDpkWNs5wJ
gkZCkCgllFlSNluKPF3jiHep1VKaD9AhB+yYfUUv7ndD9aCzDDIDka0HrFRa5ci1sMREJQCTAec7
in194eY856T0GE4J6pLUREvr78X+sIxREs9VX1mE6hGC+3Rdiltwx1wWSExOQvq+iXY1mgtDqkWg
wsRn+yoH9CGmDWBU2hhiSLHjzrpEfaY1xNkpQQRwZgP9qoigwONpywRJCZHAnMSIRCLnOQALDarI
BcfuEfxO21GoztmBHfug6CPuJngevsjeegaqDDDq5tN3iHWHf32eB630W3kviuIeJSkENtK1pZKB
ejO4lpKuCApXhEIpwhjbOkogLnLRYnT1KFAMbBsbY9FsOG3ecC9l3C5FliIGom9ENhgfmJ3g3Qoy
8JXadQYCyltJCw/51DzfMJvW46y6etFHi8J3zaVBcR2Gudl1IqqsVJOZORimEqPYTQXMQxgLIHKc
ociBZtdDCXluObs1DtDcN0kKaxPEl6YhU9RipdAPEUJiHPRcKSNJ1IaM1tnQHlIMTbEENRU53GJZ
fu8LjJvjevh7BExEszEJBujspZr63PlBxC8XMgO/43nOdFpRKSkN0OpTAICzfygV6aKnne+BDu2R
ObY0TrKiqpgVKpLgW1FvZG9RMWJ4PKmGu2lNaZMoQVO8Q4PCDKr5WNmQwlYlgfPbBnrJXB/usXK5
Lggv6FsyFIlgbxKXbDkcTWMFHY8eSiHX0kpCQRwhODygTZrLxBnI9qcUxDh/gtK+YqZgfFQHaoNB
wMoKHg0hpdcJLReohG7gxF5lOYWwE16pLe5Hs92vt1B7juWjbbSbRcZkAeAF9QVgwPJptDYOoLvV
9pXRcEmVyvEWCuVDPy6DzEc6V68tCx5t6gzTkVIar53aUpnwRJF8ZfH7KBI0F1QKRLBiB377jU0L
oDRg1xTUboSukcBdQbcrXiKgps2/iMCD3+PGlpY2DHs0+sE153A23uFGcj6RpC+EQARBAH3ARAQG
IFdd5gGxZlXEzqAhgXaN5/l8/6Kv+Wnn5zLIR0g+EybD/L746BHeeOfSK9YehAvbj+cyN2gbGMKh
S6pATC0DYiQpncvmRamks0lCrakqIBmpdkCLPbMKV+VjUt9+HylJAtZjCMe7tyis9Elxj2A2AehW
ZhKfWWC1kYzKjYpda8uY/VOtKVdIQsGSPdRaAXM/feEq8Krt5bxd85FbZkRliHhClr0tQ4sx2qkO
kaWrDJKtEZ1E0ga85WFSgnJAPgglcDcVJZVMUJKgmGq+YIsSLlkyvXshQ1cHeOovQzwGHtGEMIiA
kr22m0cTkSXp0+KNPkYNhRrsZZmtEicbDUB5hWHASqDwEF26DIrC8IQTkOi9SjtaGTudjKzrgeM2
ClpuUloERJshZkuzVZVCNhQu0DXUxgCbvN0alVHQ9R7GvQ0lzay5pdKDvgsqaaIR7BVFMMCsCln8
A0lPYqpSRfEi1Cz3m2RyDDWC7tUzlqE8j6bSTGxtsabb5WkQyXzP2tIwVUCxyHFqqqFVknVCIFqN
/LnXZIVRQIaLrPMIR0aoCugNZag3/NisuId6rnvv2LWG09Aaj360tMjcAMJNtDNS7lsWmyHaLgkJ
UP5CpJI2mw02gbEHZHN3HoyU3EieGugUrCgGGmQbUDJJEPsG3ADo4zqJRgeSVGdj2IPwFvFUjlvD
5HoWHBcG23HNq2BrpSZM51mjYfcyQSIbtlCvgUkDVIFiGgtQWO4wwgiMChlS6b8NmYNpGOGizfNu
sUimYmk2hT37WdCGNhOkpWNVl1F3SGE83iBO5QCYDGyEMhBAMRYTkEwYxkDGECGxgwGwG2DAgS8D
Esgs1yCyyII5xVCJVlwWuAG0luVUBahXgwtaRNnBHTBg/FWJ9BrJCfgXhIBZ80L22zMeg5IV2NAY
U15CvL9jRNhznIKCJrdtUgk5YBjNGd9xG5XqDXcI7mro7f1sXWXpGPtzsWvIbRDRzpGojTwwl2g2
1lmREkX3lpkfJXssa2hRSiS093IZMVpT5UyoRalcPODDScYVl0GBhX8/B8ue3KfT1SiVk1kzcceE
YphVRBnRJR7xHYItXObS4sFNfZekvcK/eGvRIMRBqlEiCANLInRfpUURiX/i7kinChIGrlu8YA==


--===============1721740234323108037==--