From: Roy Lyseng Date: July 30 2010 11:54am Subject: bzr commit into mysql-next-mr-opt-backporting branch (roy.lyseng:3222) Bug#51457 List-Archive: http://lists.mysql.com/commits/114722 X-Bug: 51457 Message-Id: <20100730115443.72E311E6@tyr67.norway.sun.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============8830480084686470675==" --===============8830480084686470675== 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-07-30 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. 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-07-30 11:54:24 +0000 @@ -392,3 +392,93 @@ 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 empty, ones, ot1, nt1, nt4, it1, it3, it4; +SET @@default_storage_engine='innodb'; +SET @@optimizer_switch='semijoin=on,materialization=off,firstmatch=on,loosescan=off'; +SET @@optimizer_join_cache_level=0; +CREATE TABLE empty(a INTEGER); +CREATE TABLE ones(a INTEGER); +INSERT INTO ones VALUES(1); +CREATE TABLE it1(a INTEGER); +INSERT INTO it1 VALUES(5), (8); +CREATE TABLE it3(a INTEGER); +INSERT INTO it3 VALUES(7), (1), (0), (5), (1), (4); +CREATE TABLE it4(a INTEGER); +INSERT INTO it4 VALUES(1), (3), (5), (7), (9), (7), (3), (1); +CREATE TABLE ot1(a INTEGER); +INSERT INTO ot1 select * from it1; +CREATE TABLE nt1(a INTEGER); +INSERT INTO nt1 select * from it1; +CREATE TABLE nt4(a INTEGER); +INSERT INTO nt4 select * from it4; +EXPLAIN +SELECT * +FROM nt1 AS nt2 +WHERE 1 IN (SELECT it1.a +FROM ones AS it1 JOIN 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 nt1 AS nt2 +WHERE 1 IN (SELECT it1.a +FROM ones AS it1 JOIN it3 ON it1.a=it3.a); +a +5 +8 +EXPLAIN +SELECT * +FROM nt1 AS nt2, nt4 +WHERE 1 IN (SELECT it1.a +FROM ones AS it1 JOIN 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 nt1 AS nt2, nt4 +WHERE 1 IN (SELECT it1.a +FROM ones AS it1 JOIN 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 empty as ot1, nt1 AS nt3 +WHERE ot1.a IN (SELECT it2.a +FROM ones AS it2 JOIN 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 empty as ot1, nt1 AS nt3 +WHERE ot1.a IN (SELECT it2.a +FROM ones AS it2 JOIN it4 ON it2.a=it4.a); +a a +DROP TABLE empty, ones, ot1, nt1, nt4, it1, it3, it4; +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-07-30 11:54:24 +0000 @@ -401,3 +401,80 @@ 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 empty, ones, ot1, nt1, nt4, it1, it3, it4; +--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 empty(a INTEGER); + +CREATE TABLE ones(a INTEGER); +INSERT INTO ones VALUES(1); + +CREATE TABLE it1(a INTEGER); +INSERT INTO it1 VALUES(5), (8); + +CREATE TABLE it3(a INTEGER); +INSERT INTO it3 VALUES(7), (1), (0), (5), (1), (4); + +CREATE TABLE it4(a INTEGER); +INSERT INTO it4 VALUES(1), (3), (5), (7), (9), (7), (3), (1); + +CREATE TABLE ot1(a INTEGER); +INSERT INTO ot1 select * from it1; + +CREATE TABLE nt1(a INTEGER); +INSERT INTO nt1 select * from it1; + +CREATE TABLE nt4(a INTEGER); +INSERT INTO nt4 select * from it4; + +EXPLAIN +SELECT * +FROM nt1 AS nt2 +WHERE 1 IN (SELECT it1.a + FROM ones AS it1 JOIN it3 ON it1.a=it3.a); + +SELECT * +FROM nt1 AS nt2 +WHERE 1 IN (SELECT it1.a + FROM ones AS it1 JOIN it3 ON it1.a=it3.a); + +EXPLAIN +SELECT * +FROM nt1 AS nt2, nt4 +WHERE 1 IN (SELECT it1.a + FROM ones AS it1 JOIN it3 ON it1.a=it3.a); + +SELECT * +FROM nt1 AS nt2, nt4 +WHERE 1 IN (SELECT it1.a + FROM ones AS it1 JOIN it3 ON it1.a=it3.a); + +EXPLAIN +SELECT * +FROM empty as ot1, nt1 AS nt3 +WHERE ot1.a IN (SELECT it2.a + FROM ones AS it2 JOIN it4 ON it2.a=it4.a); + +SELECT * +FROM empty as ot1, nt1 AS nt3 +WHERE ot1.a IN (SELECT it2.a + FROM ones AS it2 JOIN it4 ON it2.a=it4.a); + +DROP TABLE empty, ones, ot1, nt1, nt4, it1, it3, it4; + +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-07-30 11:54:24 +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; } --===============8830480084686470675== 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: a6e42032fb5073b65fbbb508ceae60609b26e51c # timestamp: 2010-07-30 13:54:43 +0200 # base_revision_id: roy.lyseng@stripped\ # 4ftoia6pm7120ehc # # Begin bundle IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWTn5WEsABuvfgEX0eP///3/3 3+C////+YA6/fb3W3133asve9B1dg3u7le3WMyqfXvNkKaA9enJ0672aIgO8JJRoajEnkIZkjKPU zJDxTyjIAabUeiZABptQaEnqp+VP0yKeJPKPUAAAAAAAAAAAlCZEyTQVPxNqepJ5kGVHonpAAAAA AaMmEiISak9qYU8VPYUn6pjCaATQGho9Q9QDaTR5TQw2pJT8UnqYTJp6hoAB6QAAADT1DQAABIkQ AQyAIANQaQZGhqZogYnqDJoNB1WCRu3rq+QOkghQQNwQQQRE1NdC6T81UCSeIyVF3MuVED6HCuHi UFBIjG0bbJkjQYlZzqs9Pj2svt+aulqd2zMpcsp3W4aCaQiN8M54jC+SI+f7LFGjstP04tlq73V3 Z8DvD9TSSO3p52y4vERJmiHVw5rzqrEr22222223boxlY6H4beAKsVAlRe/33uHDh5K0KqAt2fkK Kq+oDvCeXc4iPo105bJLOIvsnDTC9Mz1vfiEsURSO4638sQCysgAkEVjIR7Rkba5eRFfeIV/IFnP 4AuYveyfUty8U2xjPN+YUzpyAg1zHLaSSd5FKRHt53wgtm0FcC2H4DNPdNefwyFngc9ZcB0gjES7 KFMDuDnLmBwD4BaAVlDVzYVKDaTh1tLWa2psz+r4SaKaphxtT0POE9mvcUGgN5sZYJp3qLpsFlkZ 3AVivxBrEhivDDDDNA/3jqgfLOe+bFVdietqMrG51RpVbtETwkdloZi/HOB7C7QQDcAPACyFA0Wt MJglixYJBIkVcVTuPzvyNbHrpGV7XSZrFDiW7NSmZ6XuA4QzGYgNAJhIkMEVFqu01VBLi4uCZnVm NEjNMmVCgIBa6iNstJQmtIzMySFQeS9qh9KNESY8CQYwGQIwlJYOmhBqklVLrCbK8jvwjGyBDqkQ kOADgl4C/XRjPC9ZSc0PmXC6azL4Yeqp1rdZ5LO6TxrE2lHvVGKNkOjma5xU0zmryNyadSgwS1pO oIEJuVmGZmbdSym4RBPFh4DG20hg0I3HYYGBAzYQUH39QfjsK7/r4Ik9BpKEEhqJNRUKm6xiye2e QTpSksSoL3moQfgPT7j8vuELPbHhgGAZgwNgMN4VI7pRzT6zpDSu1LuKA5gGCR9vUHUadhnyMA+U VI9sntOzbGYsFtpH115FdG+rdR9NEq5yz18AsGDGEbBtNpwBIKAvutSUXpLxA+g6joVdNNS2qzKk 9N9Fglh3kwlmQEwDUEIDIkSEPpGGGcEBKz5UzFihSFGECxdQhmJinaVQsnImUyKLabQv6vuyXakQ qGsgdlblSzRSSBSAYkZidigyCB5cBA+SwMYmnybcA+eYhHx0xCukL6ZWtzVXr63MQ98kvhRGoUtF F5UCGU3r4H79zDPbI8pBKqg0raaVicYFxOEqulNCWeIYBSwDYYIkXhRTtRrqOIjZYGmRlnWV2b/S WW8t0hUGm8Z2b+HTVsp2QI2huBhbOBHTfC6gYb2BYJRUFRDCnfQF24Zq4SKeBRgmbqLZXC5F5BxJ 3HnvM/l05GWEBwLYAyYaxhK8RqkGUpoxZVpEaDeTpDJuEmMNcDb41bGvDOJYul5y/z8wOeg7gOgX CmjcY4PiFWKGHykShwsvlrAsuNEgIQW9shcCgkoRawuPUJ+SeuwWzGcIR5jAcRoJdpwl6GeeDeVo qwGTjvWY96wd9w7BvoxMB8u8uDfxmrzMK75HaJlJMzOQcOFpryPpYga7X7s2Rgj49UypvSLYoQZ9 pSmJqPEdIhfQUzEY9gCrXEvJ5n6a7+YnPxFLpGncOViENb7LdYhgQdYj46GZHWQGReYElxwruhce nyy7rg51LkUWtvXctDDHtyxlSaCl9ufazPRgjZR0Flgg0wqJWq7o9tYhhcwfe8VptVWGSxJnUVGM kWQXb3bN4O/ww+T8rsbht71clJFZwLmQSO4FSEhnX9C8/oZYC+4QsBnSUjtaEdYsqR2ga0iIBN0A F/oyITBkAiVB5W0AEwEwtPtAZMAYBAIxQApAOgBdYB0AoEvcAwXaLxMeRf4TILoBh1jJBcIB2f6C lZUjOKAX7ArhKBJR1f8SFGC9OhJC9gvSCMAF2wSO0kD3ygKlI25UEAghBMAldBIaK8JbUK2AoQTB GFIpEicEroBQkXAFtCaISoSOjEgBSA1AtgL9BKAVRovBUgoEoBZ6gRYgKxJcVIsbZuAmCRqFICYl aBakTx4kezSYg0uqUKZB0hAg7EweUc/NoDrcKUYWA5DVZpP3CoWcnIWbDiAQlAK4D9fce86qNnNs DqLIK56Tq5yXdBFU0AiSmYtfC/sL7gqqSV06hESEXL8daxUtluOEFchMTkLGOTWKCsP0OMwsBhWj T9lAP3IaYNXlDYMNBIrejcuILue/dvcVmQoLvslZXVdtLnXWoFNRnrKYMSAFlMmTKBgvm/mI/gdN aMDbZMCOxl53eGvWM51HiaVP5gzwKGGzkHIu4cJ9icd06j/+moHORNmGVVRKqiX0DEjBxLSVcEBS uyIRTYobPIUSRc5aMSduNQoBtg2NsfxLA3aNxxDv23osh7R0S3HUkfyF94RyMt/gZHcGwg3X5eJi frPCs7bRcFuOterrYyXZPdKckYoNkqcVo7QkKI8jiiyFJFEuctVrFd1RipYvcENOzo2ltpdx6jnI VR8iRx34aBO9Ni2hjW9rIuCsTFtCDjFdxntwOlHGW+0VDQHOQaDXEQ1FDncaDMs/qbe+44t6b1+X pPIRmagqDhHlRhpbp8IO4L0bEkd//rjecrClLoETUzmIjVKw6lUAQF3LxgWKaKHrxfaQ7dcTJjRU TJzYDpCJwKwV3t0IziUETScV00zZ7TnnS4ZQWCgxSxnONM/axsqGEqkrj6rILyLA9dIt1iXWgt5L ToGLWHcKfb6DcdrJlAxEj0EyoVYWC4bSPQetcqzhv7CFj8I75D/2B52I+AqE4yx3WkNLihJazvIR 48mIuNM5hZATXfJbXI8fXSY/HgHrOSzbbaTaLjUQB3gX0BUDA8zTaG06At8PxKqTxEyqVQrFQZeb gbUrFzyNFR0dwcF5jBGzO6jdguHYlTHqq9XwvFtvM8QaWokg7d1pg0LeGbBrsTUbYStkdIuIbNNj 0C2lQqGbf7jAg93PsptLGwY89f8QTXyWptvHcKWUz6xpIP+xABEEAH1ARAEAxcQKK6zANiuVHE0K AhgWZt6u3Vni/tgzZnD4EVA2HgERETB+mxwYzJTUKVTaSAXm0eo0m3MMmMKBS5SAmFgGpEkTO1e4 LE0lXAcRYkFABMqhjuQppEnwnixJhS09tQkSKqrQjHr6tEVHsSXZHpENgHsKjUEp9BWLEjRMoMlL oXn1ntnUlKqmEK9kj10rMC1n7bglVfRcIr3FX2egqraL0cEQ8IUtfo1DizHaqQ6RmoIhWGUJaIjI pikDXSVhUoJyQD7iCVAI7hqKlGTTFCSpEwgwyN4jCYItSL1k7NNcKGrg7h0F6GJHgMPSMIYREApK 5tptHcd5Jaq9CLuZgZgjZcLD6VcSHQWydLOEgYRKIR4BBbtg0lQXBCCVh6GCK1JHPSyW10FrOwD7 TWKTCSS0iIka4VwvGhWqEayZVpa3sODBSRuW7A9K21hejFDAT1VKwWhLMcqT2GE4Wah6pvvKgKa/ eGcp5KiUkXRIsQoEat5smd4X4guzCh38BPKfVeSxsbbGmzkYiHL5n/bSMFVAnPU3qkJAQja7IMJg Y9m5GQcgGVCtPAGQxvgKqQa0XhumfPitHaI7lXPddqWIaz2A1H1aBZ6jYAMJNtDMF1q/NPPKoSnE RWpBJQ+VASJG02GZlmJsDjHN2+3PfXUXLmy4xvVgEm2Rbw6EHBSR7iesAo37rmVEviaqUul5IPzF sFQju3h8TzKzrXW224145BjTTMmbjUjI+DJBIhuyUK6BSQNUwLQGYsArdpffBEYEy1L1V4a7g6RG onZvFkz4m+biuKRTAmk2hT8lrOhDGwpaZvaux2XBIwpnc3qoJpEQ3AyFAMCAhBAMSgTSYmIbGDBN gm2DExjExH0doiwV1SClWII84qAiSzXWmlsaGxG9UQFiFeDCxiJs7A6IL351WnyMSQnzLgkkjJry rkY8jxQrMaQYU4aBby7Jomw3niFIia27FIJOV4aJo1eQi+40iJ7lgoNO4RgI72sI8vaxdi/AY/KW 5bbDeIaOpI2EZ44SdMG6iTLAki64sNJtqyra2hSpRJZ+zvGTFYU/OnuHaK4ekGGR2QqF6TExoqEc /b3aKvE+XkTSpTVt/boDj1StDJQHOehmgA6Jgq/VJU0KKHlyUDYRLMlUrpBaIY311F0185kr7mc4 9Vz/i7kinChIHPysJYA= --===============8830480084686470675==--