From: Ole John Aske Date: December 3 2010 2:45pm Subject: bzr commit into mysql-5.1 branch (ole.john.aske:3477) Bug#57030 List-Archive: http://lists.mysql.com/commits/125941 X-Bug: 57030 Message-Id: <20101203144600.36961222@fimafeng09.norway.sun.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============0015750039318829345==" --===============0015750039318829345== MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Content-Disposition: inline #At file:///net/fimafeng09/export/home/tmp/oleja/mysql/mysql-5.1/ based on revid:georgi.kodinov@stripped 3477 Ole John Aske 2010-12-03 Alternative fix for bug#57030: 'BETWEEN' evaluation is incorrect This is a more extensive, but IMHO a more correct fix for handling BETWEEN optimization. It introduce some refactoring where a BETWEEN condition is rewritten to a 'GE AND LE' condition inside add_key_fields() and optimized as such. The special condition 'field' BETWEEN and is still detected and rewritten to 'field' EQ . ALternative (shorter and more hacky) fix is at: http://lists.mysql.com/commits/125940 .................. Root cause for this bug is that the optimizer try to detect & optimize the special case: ' BETWEEN c1 AND c1' and handle this as the condition ' = c1' This was implemented inside add_key_field(.. *field, *value[]...) which assumed field to refer key Field, and value[] to refer a [low...high] constant pair. value[0] and value[1] was then compared for equality. In a 'normal' BETWEEN condition of the form ' BETWEEN val1 and val2' the BETWEEN operation is represented with an argementlist containing the values [, val1, val2] - add_key_field() is then called with parameters field= , *value=val1. However, if the BETWEEN predicate specified: 1) ' BETWEEN AND the 'field' and 'value' arguments to add_key_field() had to be swapped. This was implemented by trying the cheat add_key_field() to handle it like: 2) ' GE AND LE ' As we didn't really replace the BETWEEN operation with 'ge' and 'le', add_key_field() still handled it as a 'BETWEEN' and compared the (swapped) arguments and for equality. If they was equal, the condition 1) was incorrectly 'optimized' to: 3) ' EQ ' This fix replace the BETWEEN with a 'GE AND LE' pair and let add_key_field() extract any key equalities / ranges from from this transformed condition. modified: mysql-test/r/range.result mysql-test/t/range.test sql/sql_select.cc === modified file 'mysql-test/r/range.result' --- a/mysql-test/r/range.result 2010-08-24 15:51:32 +0000 +++ b/mysql-test/r/range.result 2010-12-03 14:45:55 +0000 @@ -1666,4 +1666,91 @@ c_key c_notkey 1 1 3 3 DROP TABLE t1; +# +# Bug #57030: 'BETWEEN' evaluation is incorrect +# +CREATE TABLE t1(pk INT PRIMARY KEY, i4 INT); +CREATE UNIQUE INDEX i4_uq ON t1(i4); +INSERT INTO t1 VALUES (1,10), (2,20), (3,30); +EXPLAIN +SELECT * FROM t1 WHERE i4 BETWEEN 10 AND 10; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 const i4_uq i4_uq 5 const 1 +SELECT * FROM t1 WHERE i4 BETWEEN 10 AND 10; +pk i4 +1 10 +EXPLAIN +SELECT * FROM t1 WHERE 10 BETWEEN i4 AND i4; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range i4_uq i4_uq 5 NULL 1 Using where +SELECT * FROM t1 WHERE 10 BETWEEN i4 AND i4; +pk i4 +1 10 +EXPLAIN +SELECT * FROM t1 WHERE 10 BETWEEN 10 AND i4; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range i4_uq i4_uq 5 NULL 3 Using where +SELECT * FROM t1 WHERE 10 BETWEEN 10 AND i4; +pk i4 +1 10 +2 20 +3 30 +EXPLAIN +SELECT * FROM t1 WHERE 10 BETWEEN i4 AND 10; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range i4_uq i4_uq 5 NULL 1 Using where +SELECT * FROM t1 WHERE 10 BETWEEN i4 AND 10; +pk i4 +1 10 +EXPLAIN +SELECT * FROM t1 WHERE 10 BETWEEN 10 AND 10; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 3 +SELECT * FROM t1 WHERE 10 BETWEEN 10 AND 10; +pk i4 +1 10 +2 20 +3 30 +EXPLAIN +SELECT * FROM t1 WHERE 10 BETWEEN 11 AND 11; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE +SELECT * FROM t1 WHERE 10 BETWEEN 11 AND 11; +pk i4 +EXPLAIN +SELECT * FROM t1 WHERE 10 BETWEEN 100 AND 0; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE +SELECT * FROM t1 WHERE 10 BETWEEN 100 AND 0; +pk i4 +EXPLAIN +SELECT * FROM t1 WHERE i4 BETWEEN 100 AND 0; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables +SELECT * FROM t1 WHERE i4 BETWEEN 100 AND 0; +pk i4 +EXPLAIN +SELECT * FROM t1 WHERE i4 BETWEEN 10 AND 99999999999999999; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range i4_uq i4_uq 5 NULL 2 Using where +SELECT * FROM t1 WHERE i4 BETWEEN 10 AND 99999999999999999; +pk i4 +1 10 +2 20 +3 30 +EXPLAIN +SELECT * FROM t1 WHERE i4 BETWEEN 999999999999999 AND 30; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables +SELECT * FROM t1 WHERE i4 BETWEEN 999999999999999 AND 30; +pk i4 +EXPLAIN +SELECT * FROM t1 WHERE i4 BETWEEN 10 AND '20'; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 range i4_uq i4_uq 5 NULL 1 Using where +SELECT * FROM t1 WHERE i4 BETWEEN 10 AND '20'; +pk i4 +1 10 +2 20 +DROP TABLE t1; End of 5.1 tests === modified file 'mysql-test/t/range.test' --- a/mysql-test/t/range.test 2010-08-24 15:51:32 +0000 +++ b/mysql-test/t/range.test 2010-12-03 14:45:55 +0000 @@ -1325,4 +1325,63 @@ SELECT * FROM t1 WHERE 2 NOT BETWEEN c_n DROP TABLE t1; +--echo # +--echo # Bug #57030: 'BETWEEN' evaluation is incorrect +--echo # + +# Test some BETWEEN predicates which does *not* follow the +# 'normal' pattern of BETWEEN AND + +CREATE TABLE t1(pk INT PRIMARY KEY, i4 INT); +CREATE UNIQUE INDEX i4_uq ON t1(i4); + +INSERT INTO t1 VALUES (1,10), (2,20), (3,30); + +EXPLAIN +SELECT * FROM t1 WHERE i4 BETWEEN 10 AND 10; +SELECT * FROM t1 WHERE i4 BETWEEN 10 AND 10; + +EXPLAIN +SELECT * FROM t1 WHERE 10 BETWEEN i4 AND i4; +SELECT * FROM t1 WHERE 10 BETWEEN i4 AND i4; + +EXPLAIN +SELECT * FROM t1 WHERE 10 BETWEEN 10 AND i4; +SELECT * FROM t1 WHERE 10 BETWEEN 10 AND i4; + +EXPLAIN +SELECT * FROM t1 WHERE 10 BETWEEN i4 AND 10; +SELECT * FROM t1 WHERE 10 BETWEEN i4 AND 10; + +EXPLAIN +SELECT * FROM t1 WHERE 10 BETWEEN 10 AND 10; +SELECT * FROM t1 WHERE 10 BETWEEN 10 AND 10; + +EXPLAIN +SELECT * FROM t1 WHERE 10 BETWEEN 11 AND 11; +SELECT * FROM t1 WHERE 10 BETWEEN 11 AND 11; + +EXPLAIN +SELECT * FROM t1 WHERE 10 BETWEEN 100 AND 0; +SELECT * FROM t1 WHERE 10 BETWEEN 100 AND 0; + +EXPLAIN +SELECT * FROM t1 WHERE i4 BETWEEN 100 AND 0; +SELECT * FROM t1 WHERE i4 BETWEEN 100 AND 0; + +EXPLAIN +SELECT * FROM t1 WHERE i4 BETWEEN 10 AND 99999999999999999; +SELECT * FROM t1 WHERE i4 BETWEEN 10 AND 99999999999999999; + +EXPLAIN +SELECT * FROM t1 WHERE i4 BETWEEN 999999999999999 AND 30; +SELECT * FROM t1 WHERE i4 BETWEEN 999999999999999 AND 30; + +EXPLAIN +SELECT * FROM t1 WHERE i4 BETWEEN 10 AND '20'; +SELECT * FROM t1 WHERE i4 BETWEEN 10 AND '20'; + + +DROP TABLE t1; + --echo End of 5.1 tests === modified file 'sql/sql_select.cc' --- a/sql/sql_select.cc 2010-10-29 08:23:06 +0000 +++ b/sql/sql_select.cc 2010-12-03 14:45:55 +0000 @@ -3348,26 +3348,7 @@ add_key_field(KEY_FIELD **key_fields,uin eq_func is NEVER true when num_values > 1 */ if (!eq_func) - { - /* - Additional optimization: if we're processing - "t.key BETWEEN c1 AND c1" then proceed as if we were processing - "t.key = c1". - TODO: This is a very limited fix. A more generic fix is possible. - There are 2 options: - A) Make equality propagation code be able to handle BETWEEN - (including cases like t1.key BETWEEN t2.key AND t3.key) - B) Make range optimizer to infer additional "t.key = c" equalities - and use them in equality propagation process (see details in - OptimizerKBAndTodo) - */ - if ((cond->functype() != Item_func::BETWEEN) || - ((Item_func_between*) cond)->negated || - !value[0]->eq(value[1], field->binary())) - return; - eq_func= TRUE; - } - + return; if (field->result_type() == STRING_RESULT) { if ((*value)->result_type() != STRING_RESULT) @@ -3563,9 +3544,49 @@ add_key_fields(JOIN *join, KEY_FIELD **k case Item_func::OPTIMIZE_KEY: { Item **values; - // BETWEEN, IN, NE - if (is_local_field (cond_func->key_item()) && - !(cond_func->used_tables() & OUTER_REF_TABLE_BIT)) + /* + 'a BETWEEN low AND high' is transformed to + 'a >= low AND a <= high' before further key optimization: + */ + if (cond_func->functype() == Item_func::BETWEEN) + { + values= cond_func->arguments(); + /* + Additional optimization: If 'low = high', transform to + "t.key = low". + */ + if (!((Item_func_between*)cond_func)->negated && + values[0]->real_item()->type() == Item::FIELD_ITEM && + values[1]->const_item() && + values[1]->eq(values[2], ((Item_field*)values[0]->real_item())->field->binary())) + { + Item_bool_func *eq= new Item_equal(values[1],((Item_field*)values[0]->real_item())); + if (eq) + { + add_key_fields(join, key_fields, and_level, eq, usable_tables, + sargables); + } + } + else + { + Item_bool_func2 *ge= new Item_func_ge(values[0],values[1]); + if (ge) + { + add_key_fields(join, key_fields, and_level, ge, usable_tables, + sargables); + } + Item_bool_func2 *le= new Item_func_le(values[0],values[2]); + if (le) + { + add_key_fields(join, key_fields, and_level, le, usable_tables, + sargables); + } + } + } + + // IN, NE + else if (is_local_field (cond_func->key_item()) && + !(cond_func->used_tables() & OUTER_REF_TABLE_BIT)) { values= cond_func->arguments()+1; if (cond_func->functype() == Item_func::NE_FUNC && @@ -3579,21 +3600,6 @@ add_key_fields(JOIN *join, KEY_FIELD **k cond_func->argument_count()-1, usable_tables, sargables); } - if (cond_func->functype() == Item_func::BETWEEN) - { - values= cond_func->arguments(); - for (uint i= 1 ; i < cond_func->argument_count() ; i++) - { - Item_field *field_item; - if (is_local_field (cond_func->arguments()[i])) - { - field_item= (Item_field *) (cond_func->arguments()[i]->real_item()); - add_key_equal_fields(key_fields, *and_level, cond_func, - field_item, 0, values, 1, usable_tables, - sargables); - } - } - } break; } case Item_func::OPTIMIZE_OP: --===============0015750039318829345== MIME-Version: 1.0 Content-Type: text/bzr-bundle; charset="us-ascii"; name="bzr/ole.john.aske@stripped" Content-Transfer-Encoding: 7bit Content-Disposition: inline # Bazaar merge directive format 2 (Bazaar 0.90) # revision_id: ole.john.aske@stripped\ # zbvxbceg9ack7k9y # target_branch: file:///net/fimafeng09/export/home/tmp/oleja/mysql\ # /mysql-5.1/ # testament_sha1: 5dac7494434bd12fa52e34ac36b433ddf25d34c4 # timestamp: 2010-12-03 15:46:00 +0100 # base_revision_id: georgi.kodinov@stripped\ # l819wohslm0k87fn # # Begin bundle IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWaItZ/cAB89/gH17AgB59/// f///6r////pgDr5PPstXuguWm69HkJS47QK069ePbaDesUVbaRFdspUvDJEZDUn6g1MNJlPNJslH pqep+kTR6mmRoaZAA0eoAYEpCGjAQmmgRNqntGlNPU9Q9NR6gAA9QAAAPUHMmmhkADEZBkANMEDE A0aaADIGgASmSIk0aNJkaemRGjTJ6JtBAaABoANAAACKQhGjQKemIBHqj9QNT1PU/UTJtTRkDRo9 JpkGTQPTUEigQEaMjU0yaBpTwSaYmp6nqBpoepoaGgyABoXAJw8Hu8LJY4wgo+0ae5SgfAERCj3g opXDZVL9lLw+lLbVP+UmpWntU9anrUuWoSKh1z72o7dHfxREjQibqQypdkqjjSMZ1D82L10fR+DB alXtXKn3W6ZLMDOttiAWYoQtpwtKjAdIFRsXL9bBaXwrXwE9JIeIEoWcCFqK+7tLl8dqSSyk0kk1 KaSlErkp8RkbLjZgbG2S2NsbZRsls6DY7A363yig6GRaUcDjphCk4bffeke+U7ZJE4+EsdW4CCyQ QmXHgmbsjiIBIkJBEKNOwLt2+hY8wESo1fpeOcoIXPe7QyfuQQWveEAUtBlQRj4AEj73sYyRjYry FhyltjbaMtwH9kcuXGrXV3gjxATAsBMGHKhf2Lk40bEzaFAor2bVSNDuhYGJ4OOmi86ta6dPHM+H j9vV3GjAFqabTbeQfOEArWgsm6TGMe5g0kklAgSEkKBB1bYynQB5m0iq1yyeAIQmvk80zvInSeXj qxUon+pDWdXedzyR+BlFhsICgRAgnmTTpw12f3pbfi9SmCgSYhcCCQbsNeq8BYa5j3I+FToujdg/ +oXsjYyt9pXwJctH3UcuyVOe8klmNawcxnDxppW04Pb3VRU6jqTyzVwzA5AQeVgfwQZIeoFbMmYs Q0bMM7XX5KgFUML1cpV3IxMSZYjsuFsYyjBF3HVWV2ah+jJwPW1oLxUved4IhEwBpcI3mpnnGHWq prLqmDF4cg2tWF+9kIWFrWJRVilDKy21cRGLr1Wr+nw6ztp1+/oNY4OTflPDJr3KCYUIPPx8iIUS ZQzAIDnGq9nS4l+BeqmBQhT8NVJ2BsBgvoGg6mcn+zt8LCFqI5tRjQXJMqZrGTTgMrMOzuycJHRd XcUy6Yhgwn9379Uge0CZFroVBmEpaGM8B1C2ASM1+0OfohJce7tPAnivowzbh7Z2SRg+vkU7XFRu Nwwp0ptMg5gCJrKsbTJgpaIrerDiOgO205TIM2oDKtQmcGAi2xse+jaLyMcoUIJbveXQ8OJFkoMA JmSs1RIhqMAngBpFOKmlOJsByMfJImu3p6A6wZyG9lyF+Rg25BmA0CKAxlCsgSFSoSaxrVigoIoR wogkFthVhaIaoIy0KsmXX6LiUkUFAUNBBscGOAnA/yKqsw9R2p3rc2sz6HzdheKFJMhxiYrQw0FT ryJBVSXIdaUQSO/1kANQg5slBe8/jYY1Au5hQIyiG44zEuvJX3kuqkefnqt5hhJT4o1EloEQPtw5 yJ0mAW22F0CGnvw85fGTWs4ttYqCwbb7EYHbhkueaxL3njzB5NXCuCSM9du8tLg9MN5mCDxDPcsF 80EWZG6+jQiZobXurTcoTamjaSnXPx8hR5tPSGZ60VXvtfKfAot5nejMLSAjjcElidgc5FTInXGm XwKoFLpkdZbxO29ZEiRabjmLy3q/BuxSNODcBJOMC02a1MOlwKECrZGoiSQqhkBFBlNssh6wuEiB s1HXopedpo9uRQ3ieqdUNOCYjY8fDnhExsdpK43jLEQrHiDKGNQQfrafGjgskWZ3lGSPg0EyovKu w7RuvlfotuCuCVlc9ExxUKSZQ41NFcYRwJDrjLNEWM7DQYede4d/AZTea88ycTM4mlW3H5tcdxjL sIzIz6ih1vJpHSguB0mnTqgnOaxBo/UopBWCC6TSexGXEIjMlRR9qPex9w1JNkBVpYLuyqXQXOow 1aSyZQ0zJY4yOOkAyAxyfFd4jEhWpiMNW/fC/D1cE3cTjBkw6JQqZuhp4cMOrYUVkwKxuoZZFtq3 LbLG2jrI43TPcQUqqJ2OxRRQUpRynMyqKMAUFEJKEbuSGkaXfHs+98K2cJhUXoz4uyIhWCrr77Ua Cl6YQE4lEEWdx4IE6gtUg+lPUKbek22AhfoPgH0cpzugNsGQSBNi4BL/39UVzKBIFPuFGRcDLpEf 7nB7zKFBSgwF0gU6lVn0/uCleBVcJ0gDQpaeFVf1MYp1F2pTPgBTDBuGQAdN/35ivIpoFJNRA6DJ pmYgqJf4x+BEQmUUPYKZYUnfCCYKS3EHDAMM/4BTdBCQCyIWUwRgrqJAYUQ3d0zApWQRptPYKaFK GEtIAH3hnyGkEjgTNY82MEjmMUiwEjURLmXhfYEsplqq12sR7jQVIhQzXJIzqrAA3gG4g1MkCRFG LZ3+LgxlBUEKJucq7pdraDwe0hiiHuQImFNvM5WLK2wSiBXRSbmrjLYzWljJTwi+hTOnJEQ+Nvgd nzYbx5Ce7OZq/S5Sxh8zDlPsuEjQAjayac6k/xMUzPAxvNRoM/AoPJUExwMD7Ce09J40x9Z3yjZS lQpY4MF0oANISVnpzeg6MoOYxsTzuU0BAj/cSFy2K61w4UVKbI7RcK/LNFZGuEYx7BzeolYdByk4 3jMdBXUbDKVnpE0HPe4OJTsKwDaVLA7fIsV4jsxN8AWvdGAw7qlkfSpGflA8mHI+qs2j0nn3rQd2 4uKyOAiBfGFt4qkiLALBB9OdD6n8EzNh7xm0BnFmlN+w0rQxAyPSYJElE10MEhKECKzMSOEiEoME PUL2LdxYzLuwYyxOMniMF1iwhRNgkNOLk4zAZhPJaS3C8R3QmclclfExuJBZXpShWeSLRIkkWbfS elDXrf7mZK2Ct8ke8qRbcrQdJt0mb/Rk27L2djm+S0ryaIIYmp7I7+BIlbW6c5znUedhDm2VaNS2 LXRI4Xs2OEgqEqxNbcxO86lipK10EoQd7xHpjKUpxlCM6HDVUbTs69vM48KJGdRBcNQivWPHccF2 8+l7+UDJAGQl9f17gDnOhpEDoK4bA6Cx4JqKK01f48uk+z1xDG96YFL+6EewmLt1EglifFnTGk0o gpY5fioiEVS4nPjytTroPEwTLy1GtXLi75MEMG8p9mQc0QvoE7hSdPnjG0Nos4HoHltOPmsvOKNI Dg2WCy8HHFLXyeJkBs7XBzIUWGtmtxlevMcUbIO9IkYydoK6WXu5jwLk2A+u8RwTUkZXed0haatk BQwUobUNe70c+Z4nqouvxD1+LaZ4GZGPQBkKiS+PGcVeJs66LXIqGy4FUrLrD4jGit7ALdKZw9qR MSW8gCQMFx1sSvKXj4im9hU08K3i9PeV54ELTb7P1GDdYYYI9mZagtSKlmvRAN4sa7jL25I28pqx burruwSLGNjB1noK8mxptDbLMhYEjejqCOkD5dQ4lReaMwmEE1P71Z5ny+jvSNS5epC6YGZIT42N ImPkhTJ2VMGp1CQ81FJqfLiMkx23kW6LzAzGGtPNNQBlBSzl5JqfxJqpaShNAGxTywGBobcm7oyK 3KWO2G+LgFtyXGBSpBy0mLs5fYqBxwXHNeSdo/GBxov3sByevqLICIeph0Kqj4ax2oggJKEGIij3 RK1dImoL0bZvuGlfWe7W1zLArPEGCymvWXI3i9HLftqKDbBwzsZtimMl8iZUw7x4KqRQDIYXSCEE KAqIgmkw1rxjWpgpgsIcDlMivcbtFaka/EuAJRCDSkMDsEmm3HwG4wBvxnqcJpyGw6uJTaw5XtHq CHr7MuE7ohuEBuCkA8cIGJ8te8ZSUJwxnMCdSukdRON9nM8BCXJv8tTCumuIO3VJqOFejrGVS+aM 0Fx1lpbivkqN8U0PMiHgAu25Xl6xtSPUZGZaVMPYkSLTylpKsJXoGC9zHJYtY26gMdMxdTtBmlkG euUFYkSSTYp82tHLzGzGpVgVhM5GN5LS4tUozQhnyvzaN2ochY4YjCyZZZ9waDOW5m7E7CvVrSLE VOuECq6BC5I4pEwi56AWg5kcJAkkqMN6h0qKGQoZzyQis6uZG3q/54jNf2WRilnc6lW8amA4qnXc rUedMwyqdzCpszhm+5VHScl6W23BYdBGBAx6UlfWYSgNNIadZkKUJLHxJ7JyOKLOauFl1KeyV/om qt8K4EDdSxY70tII1gc9pIsYPIMXlLFLC+FdRZZjKTvSMSYJG4q7e4ifp13XeSiYCdwQR4tItYe2 raqT1nOckpBQGNtNmNWVpcNKwUZroNccgVFMY1S26aScHHmJmlTSpyYbKjg5U0OsxSHwQj9p2yyf DQPUmQQndpEs5bVLVbXPYc4qj7GbVy9/RIhD5+8/Oeb2TkSlvtrcxo52Q6jxZxMzRgNBumYdVGQH lID72wopiC7m5RKiRAHnUgGwqk9nNKc8c6gjqekkoSUECkQj0aCgCoke8PMmZakzARANIQPeI69w aBzYR4ypQUewXckU4UJCiLWf3A== --===============0015750039318829345==--