From: Tor Didriksen Date: November 24 2010 1:24pm Subject: bzr commit into mysql-trunk branch (tor.didriksen:3247) WL#1393 List-Archive: http://lists.mysql.com/commits/124870 Message-Id: <20101124132422.958FA37A3@atum07.norway.sun.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============6439206237089482492==" --===============6439206237089482492== MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Content-Disposition: inline #At file:///export/home/didrik/repo/next-mr-opt-team-wl1393-merge/ based on revid:tor.didriksen@stripped 3247 Tor Didriksen 2010-11-24 WL#1393 Optimizing filesort with small limit Many web customers have to do "SELECT ... ORDER BY non_index_column LIMIT X", When X * is smaller than sort_buff_size we can use the following algoritm to speed up the sort: - Create a queue to hold 'limit' keys. - Scan through the table and store the first (last if DESC) keys in the queue - Return values from queue @ libmysqld/CMakeLists.txt Add Bounded_queue @ libmysqld/Makefile.am Add Bounded_queue @ mysql-test/include/order_by.inc Add new tests. @ mysql-test/include/select.inc Fix typo in bug number. @ mysql-test/r/order_by_none.result Added new tests. @ mysql-test/r/order_by_sortkey.result New test. @ mysql-test/r/select_none.result Fix typo in bug number. @ mysql-test/t/order_by_sortkey.test New test. @ mysys/CMakeLists.txt Compile standalone queues test executable. @ mysys/queues.c Fix un-maintained code: s/bool/my_bool/ @ sql/CMakeLists.txt Add Bounded_queue to gunit tests. @ sql/Makefile.am Add Bounded_queue @ sql/bounded_queue.cc Since Bounded_queue is templatized, the entire implementation must go in the .h file The free function get_merge_many_buffs_cost_fast is here so that we can unit test it. @ sql/bounded_queue.h This is a wrapper on top of QUEUE and the queue_xxx() functions. @ sql/filesort.cc Add support for Priority Queue sort for queries with a LIMIT. Simplify usage of make_char_array(), let it allocate/initialize FILESORT_INFO.sort_keys directly. Rename SORTPARAM to Sort_param, and add init() function. Remove dead code (obsolete #ifdef) Remove dead code (indexfile was alwayss NULL in find_all_keys()) @ sql/filesort.h New argument to filesort() @ sql/sql_const.h Use double, rather than int, literals (avoids lots of casting). @ sql/sql_delete.cc New argument to filesort() @ sql/sql_select.cc Handle new filesort() using priority queue: - Add some more DBUG_PRINT statements before calls to create_sort_index() - create_sort_index() can use the new PQ algorithm if (!group && tables==1) - use information from filesort() if we have OPTION_FOUND_ROWS - in end_send(): stop if we are about to read more rows than allocated by the PQ - pass OPTION_FOUND_ROWS on to filesort() for single-table queries. @ sql/sql_sort.h Rename st_sort_param/SORTPARAM to Sort_param. Add constructor. Add init() function. @ sql/sql_table.cc New argument to filesort() @ sql/sql_update.cc New argument to filesort() @ sql/uniques.cc Rename SORTPARAM to Sort_param. @ unittest/gunit/CMakeLists.txt Add gunit test for Bounded_queue @ unittest/gunit/bounded_queue-t.cc Add new unit tests for Bounded_queue and merge-cost estimation. Add performance tests for Bounded_queue. added: mysql-test/r/order_by_sortkey.result mysql-test/t/order_by_sortkey.test sql/bounded_queue.cc sql/bounded_queue.h unittest/gunit/bounded_queue-t.cc modified: libmysqld/CMakeLists.txt libmysqld/Makefile.am mysql-test/include/order_by.inc mysql-test/include/select.inc mysql-test/r/order_by_none.result mysql-test/r/select_none.result mysys/CMakeLists.txt mysys/queues.c sql/CMakeLists.txt sql/Makefile.am sql/filesort.cc sql/filesort.h sql/sql_const.h sql/sql_delete.cc sql/sql_select.cc sql/sql_sort.h sql/sql_table.cc sql/sql_update.cc sql/uniques.cc unittest/gunit/CMakeLists.txt === modified file 'libmysqld/CMakeLists.txt' --- a/libmysqld/CMakeLists.txt 2010-11-04 15:40:18 +0000 +++ b/libmysqld/CMakeLists.txt 2010-11-24 13:24:14 +0000 @@ -45,6 +45,7 @@ SET(SQL_EMBEDDED_SOURCES emb_qcache.cc l ../sql-common/client_plugin.c ../sql/password.c ../sql/discover.cc ../sql/derror.cc ../sql/field.cc ../sql/field_conv.cc + ../sql/bounded_queue.cc ../sql/filesort.cc ../sql/gstream.cc ../sql/handler.cc ../sql/hash_filo.cc ../sql/hostname.cc ../sql/init.cc ../sql/item_buff.cc ../sql/item_cmpfunc.cc === modified file 'libmysqld/Makefile.am' --- a/libmysqld/Makefile.am 2010-11-04 15:40:18 +0000 +++ b/libmysqld/Makefile.am 2010-11-24 13:24:14 +0000 @@ -44,6 +44,7 @@ libmysqlsources = errmsg.c get_password. noinst_HEADERS = embedded_priv.h emb_qcache.h sqlsources = derror.cc field.cc field_conv.cc strfunc.cc filesort.cc \ + bounded_queue.cc \ ha_ndbcluster.cc ha_ndbcluster_cond.cc \ ha_ndbcluster_binlog.cc ha_partition.cc \ handler.cc sql_handler.cc \ === modified file 'mysql-test/include/order_by.inc' --- a/mysql-test/include/order_by.inc 2010-09-27 13:20:24 +0000 +++ b/mysql-test/include/order_by.inc 2010-11-24 13:24:14 +0000 @@ -1364,6 +1364,163 @@ ORDER BY t2.c LIMIT 1; DROP TABLE t1,t2,t3; +--echo # +--echo # WL#1393 - Optimizing filesort with small limit +--echo # + +CREATE TABLE t1(f0 int auto_increment primary key, f1 int, f2 varchar(200)); +INSERT INTO t1(f1, f2) VALUES +(0,"0"),(1,"1"),(2,"2"),(3,"3"),(4,"4"),(5,"5"), +(6,"6"),(7,"7"),(8,"8"),(9,"9"),(10,"10"), +(11,"11"),(12,"12"),(13,"13"),(14,"14"),(15,"15"), +(16,"16"),(17,"17"),(18,"18"),(19,"19"),(20,"20"), +(21,"21"),(22,"22"),(23,"23"),(24,"24"),(25,"25"), +(26,"26"),(27,"27"),(28,"28"),(29,"29"),(30,"30"), +(31,"31"),(32,"32"),(33,"33"),(34,"34"),(35,"35"), +(36,"36"),(37,"37"),(38,"38"),(39,"39"),(40,"40"), +(41,"41"),(42,"42"),(43,"43"),(44,"44"),(45,"45"), +(46,"46"),(47,"47"),(48,"48"),(49,"49"),(50,"50"), +(51,"51"),(52,"52"),(53,"53"),(54,"54"),(55,"55"), +(56,"56"),(57,"57"),(58,"58"),(59,"59"),(60,"60"), +(61,"61"),(62,"62"),(63,"63"),(64,"64"),(65,"65"), +(66,"66"),(67,"67"),(68,"68"),(69,"69"),(70,"70"), +(71,"71"),(72,"72"),(73,"73"),(74,"74"),(75,"75"), +(76,"76"),(77,"77"),(78,"78"),(79,"79"),(80,"80"), +(81,"81"),(82,"82"),(83,"83"),(84,"84"),(85,"85"), +(86,"86"),(87,"87"),(88,"88"),(89,"89"),(90,"90"), +(91,"91"),(92,"92"),(93,"93"),(94,"94"),(95,"95"), +(96,"96"),(97,"97"),(98,"98"),(99,"99"); + +################ +## Test sort when source data fits in memory + +SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 100; +SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 30; +SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 0; +SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 30; +SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 0; +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 20; +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0; +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 10 OFFSET 10; +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0 OFFSET 10; + +################ +## Test sort when source data does not fit in memory +set sort_buffer_size= 32768; +CREATE TEMPORARY TABLE tmp (f1 int, f2 varchar(20)); +INSERT INTO tmp SELECT f1, f2 FROM t1; +INSERT INTO t1(f1, f2) SELECT * FROM tmp; +INSERT INTO tmp SELECT f1, f2 FROM t1; +INSERT INTO t1(f1, f2) SELECT * FROM tmp; + +SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 30; +SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 0; +SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 30; +SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 0; +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 20; +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0; +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 10 OFFSET 10; +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0 OFFSET 10; + +################ +## Test with SQL_CALC_FOUND_ROWS +set sort_buffer_size= 32768; +SELECT SQL_CALC_FOUND_ROWS * FROM t1 +ORDER BY f1, f0 LIMIT 30; +SELECT FOUND_ROWS(); + +SELECT SQL_CALC_FOUND_ROWS * FROM t1 +ORDER BY f1, f0 LIMIT 0; +SELECT FOUND_ROWS(); + +SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10 +ORDER BY f2, f0 LIMIT 20; +SELECT FOUND_ROWS(); + +SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10 +ORDER BY f2, f0 LIMIT 0; +SELECT FOUND_ROWS(); + +SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10 +ORDER BY f2, f0 LIMIT 10 OFFSET 10; +SELECT FOUND_ROWS(); + +SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10 +ORDER BY f2, f0 LIMIT 0 OFFSET 10; +SELECT FOUND_ROWS(); + +################ +## Test sorting with join +## These are re-written to use PQ during execution. +set sort_buffer_size= 327680; + +SELECT * FROM t1 JOIN tmp on t1.f2=tmp.f2 +ORDER BY tmp.f1, f0 LIMIT 30; + +SELECT * FROM t1 JOIN tmp on t1.f2=tmp.f2 +ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30; + +SELECT SQL_CALC_FOUND_ROWS * FROM t1 JOIN tmp on t1.f2=tmp.f2 +ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30; +SELECT FOUND_ROWS(); + +SELECT SQL_CALC_FOUND_ROWS * FROM t1 JOIN tmp on t1.f2=tmp.f2 +WHERE t1.f2>20 +ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30; +SELECT FOUND_ROWS(); + +################ +## Test views +CREATE VIEW v1 as SELECT * FROM t1 ORDER BY f1, f0 LIMIT 30; +SELECT * FROM v1; +drop view v1; + +CREATE VIEW v1 as SELECT * FROM t1 ORDER BY f1, f0 LIMIT 100; +SELECT * FROM v1 ORDER BY f2, f0 LIMIT 30; + +CREATE VIEW v2 as SELECT * FROM t1 ORDER BY f2, f0 LIMIT 100; +SELECT * FROM v1 JOIN v2 on v1.f1=v2.f1 ORDER BY v1.f2,v1.f0,v2.f0 +LIMIT 30; + +################ +## Test group & having +SELECT floor(f1/10) f3, count(f2) FROM t1 +group by 1 ORDER BY 2,1 LIMIT 5; + +SELECT floor(f1/10) f3, count(f2) FROM t1 +group by 1 ORDER BY 2,1 LIMIT 0; + +################ +## Test SP +delimiter |; +CREATE PROCEDURE wl1393_sp_test() +BEGIN +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 30; +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 15 OFFSET 15; +SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10 +ORDER BY f2, f0 LIMIT 15 OFFSET 15; +SELECT FOUND_ROWS(); +SELECT * FROM v1 ORDER BY f2, f0 LIMIT 30; +END| +CALL wl1393_sp_test()| +DROP PROCEDURE wl1393_sp_test| +delimiter ;| + +################ +## Test with subqueries +SELECT d1.* FROM t1 +LEFT JOIN (SELECT * FROM t1 LIMIT 30) d1 on t1.f1=d1.f1 +ORDER BY d1.f2 DESC LIMIT 30; + +SELECT * FROM t1 WHERE f1 = (SELECT f1 FROM t1 ORDER BY 1 LIMIT 1); + +--error ER_SUBQUERY_NO_1_ROW +SELECT * FROM t1 WHERE f1 = (SELECT f1 FROM t1 ORDER BY 1 LIMIT 2); + +DROP TABLE t1, tmp; +DROP VIEW v1, v2; + +--echo # end of WL#1393 - Optimizing filesort with small limit # # Bug#35844: Covering index for ref access not compatible with ORDER BY list === modified file 'mysql-test/include/select.inc' --- a/mysql-test/include/select.inc 2010-10-26 09:10:59 +0000 +++ b/mysql-test/include/select.inc 2010-11-24 13:24:14 +0000 @@ -4140,7 +4140,7 @@ DROP TABLE t1; --echo End of 5.1 tests --echo # ---echo # Bug#45277: Lost HAVING clause led to a wrong result. +--echo # Bug#45227: Lost HAVING clause led to a wrong result. --echo # CREATE TABLE `CC` ( `int_nokey` int(11) NOT NULL, @@ -4162,7 +4162,7 @@ SELECT `varchar_nokey` G1 FROM CC WHER HAVING G1 ORDER BY `varchar_key` LIMIT 6 ; DROP TABLE CC; ---echo # End of test#45277 +--echo # End of test#45227 --echo # --echo # Bug#54515: Crash in opt_range.cc::get_best_group_min_max on === modified file 'mysql-test/r/order_by_none.result' --- a/mysql-test/r/order_by_none.result 2010-09-27 13:20:24 +0000 +++ b/mysql-test/r/order_by_none.result 2010-11-24 13:24:14 +0000 @@ -1504,6 +1504,853 @@ ORDER BY t2.c LIMIT 1; d 52.5 DROP TABLE t1,t2,t3; +# +# WL#1393 - Optimizing filesort with small limit +# +CREATE TABLE t1(f0 int auto_increment primary key, f1 int, f2 varchar(200)); +INSERT INTO t1(f1, f2) VALUES +(0,"0"),(1,"1"),(2,"2"),(3,"3"),(4,"4"),(5,"5"), +(6,"6"),(7,"7"),(8,"8"),(9,"9"),(10,"10"), +(11,"11"),(12,"12"),(13,"13"),(14,"14"),(15,"15"), +(16,"16"),(17,"17"),(18,"18"),(19,"19"),(20,"20"), +(21,"21"),(22,"22"),(23,"23"),(24,"24"),(25,"25"), +(26,"26"),(27,"27"),(28,"28"),(29,"29"),(30,"30"), +(31,"31"),(32,"32"),(33,"33"),(34,"34"),(35,"35"), +(36,"36"),(37,"37"),(38,"38"),(39,"39"),(40,"40"), +(41,"41"),(42,"42"),(43,"43"),(44,"44"),(45,"45"), +(46,"46"),(47,"47"),(48,"48"),(49,"49"),(50,"50"), +(51,"51"),(52,"52"),(53,"53"),(54,"54"),(55,"55"), +(56,"56"),(57,"57"),(58,"58"),(59,"59"),(60,"60"), +(61,"61"),(62,"62"),(63,"63"),(64,"64"),(65,"65"), +(66,"66"),(67,"67"),(68,"68"),(69,"69"),(70,"70"), +(71,"71"),(72,"72"),(73,"73"),(74,"74"),(75,"75"), +(76,"76"),(77,"77"),(78,"78"),(79,"79"),(80,"80"), +(81,"81"),(82,"82"),(83,"83"),(84,"84"),(85,"85"), +(86,"86"),(87,"87"),(88,"88"),(89,"89"),(90,"90"), +(91,"91"),(92,"92"),(93,"93"),(94,"94"),(95,"95"), +(96,"96"),(97,"97"),(98,"98"),(99,"99"); +SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 100; +f0 f1 f2 +1 0 0 +2 1 1 +3 2 2 +4 3 3 +5 4 4 +6 5 5 +7 6 6 +8 7 7 +9 8 8 +10 9 9 +11 10 10 +12 11 11 +13 12 12 +14 13 13 +15 14 14 +16 15 15 +17 16 16 +18 17 17 +19 18 18 +20 19 19 +21 20 20 +22 21 21 +23 22 22 +24 23 23 +25 24 24 +26 25 25 +27 26 26 +28 27 27 +29 28 28 +30 29 29 +31 30 30 +32 31 31 +33 32 32 +34 33 33 +35 34 34 +36 35 35 +37 36 36 +38 37 37 +39 38 38 +40 39 39 +41 40 40 +42 41 41 +43 42 42 +44 43 43 +45 44 44 +46 45 45 +47 46 46 +48 47 47 +49 48 48 +50 49 49 +51 50 50 +52 51 51 +53 52 52 +54 53 53 +55 54 54 +56 55 55 +57 56 56 +58 57 57 +59 58 58 +60 59 59 +61 60 60 +62 61 61 +63 62 62 +64 63 63 +65 64 64 +66 65 65 +67 66 66 +68 67 67 +69 68 68 +70 69 69 +71 70 70 +72 71 71 +73 72 72 +74 73 73 +75 74 74 +76 75 75 +77 76 76 +78 77 77 +79 78 78 +80 79 79 +81 80 80 +82 81 81 +83 82 82 +84 83 83 +85 84 84 +86 85 85 +87 86 86 +88 87 87 +89 88 88 +90 89 89 +91 90 90 +92 91 91 +93 92 92 +94 93 93 +95 94 94 +96 95 95 +97 96 96 +98 97 97 +99 98 98 +100 99 99 +SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 30; +f0 f1 f2 +1 0 0 +2 1 1 +3 2 2 +4 3 3 +5 4 4 +6 5 5 +7 6 6 +8 7 7 +9 8 8 +10 9 9 +11 10 10 +12 11 11 +13 12 12 +14 13 13 +15 14 14 +16 15 15 +17 16 16 +18 17 17 +19 18 18 +20 19 19 +21 20 20 +22 21 21 +23 22 22 +24 23 23 +25 24 24 +26 25 25 +27 26 26 +28 27 27 +29 28 28 +30 29 29 +SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 0; +f0 f1 f2 +SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 30; +f0 f1 f2 +100 99 99 +99 98 98 +98 97 97 +97 96 96 +96 95 95 +95 94 94 +94 93 93 +93 92 92 +92 91 91 +91 90 90 +10 9 9 +90 89 89 +89 88 88 +88 87 87 +87 86 86 +86 85 85 +85 84 84 +84 83 83 +83 82 82 +82 81 81 +81 80 80 +9 8 8 +80 79 79 +79 78 78 +78 77 77 +77 76 76 +76 75 75 +75 74 74 +74 73 73 +73 72 72 +SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 0; +f0 f1 f2 +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 20; +f0 f1 f2 +12 11 11 +13 12 12 +14 13 13 +15 14 14 +16 15 15 +17 16 16 +18 17 17 +19 18 18 +20 19 19 +21 20 20 +22 21 21 +23 22 22 +24 23 23 +25 24 24 +26 25 25 +27 26 26 +28 27 27 +29 28 28 +30 29 29 +31 30 30 +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0; +f0 f1 f2 +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 10 OFFSET 10; +f0 f1 f2 +22 21 21 +23 22 22 +24 23 23 +25 24 24 +26 25 25 +27 26 26 +28 27 27 +29 28 28 +30 29 29 +31 30 30 +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0 OFFSET 10; +f0 f1 f2 +set sort_buffer_size= 32768; +CREATE TEMPORARY TABLE tmp (f1 int, f2 varchar(20)); +INSERT INTO tmp SELECT f1, f2 FROM t1; +INSERT INTO t1(f1, f2) SELECT * FROM tmp; +INSERT INTO tmp SELECT f1, f2 FROM t1; +INSERT INTO t1(f1, f2) SELECT * FROM tmp; +SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 30; +f0 f1 f2 +1 0 0 +101 0 0 +201 0 0 +301 0 0 +401 0 0 +2 1 1 +102 1 1 +202 1 1 +302 1 1 +402 1 1 +3 2 2 +103 2 2 +203 2 2 +303 2 2 +403 2 2 +4 3 3 +104 3 3 +204 3 3 +304 3 3 +404 3 3 +5 4 4 +105 4 4 +205 4 4 +305 4 4 +405 4 4 +6 5 5 +106 5 5 +206 5 5 +306 5 5 +406 5 5 +SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 0; +f0 f1 f2 +SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 30; +f0 f1 f2 +100 99 99 +200 99 99 +300 99 99 +400 99 99 +500 99 99 +99 98 98 +199 98 98 +299 98 98 +399 98 98 +499 98 98 +98 97 97 +198 97 97 +298 97 97 +398 97 97 +498 97 97 +97 96 96 +197 96 96 +297 96 96 +397 96 96 +497 96 96 +96 95 95 +196 95 95 +296 95 95 +396 95 95 +496 95 95 +95 94 94 +195 94 94 +295 94 94 +395 94 94 +495 94 94 +SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 0; +f0 f1 f2 +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 20; +f0 f1 f2 +12 11 11 +112 11 11 +212 11 11 +312 11 11 +412 11 11 +13 12 12 +113 12 12 +213 12 12 +313 12 12 +413 12 12 +14 13 13 +114 13 13 +214 13 13 +314 13 13 +414 13 13 +15 14 14 +115 14 14 +215 14 14 +315 14 14 +415 14 14 +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0; +f0 f1 f2 +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 10 OFFSET 10; +f0 f1 f2 +14 13 13 +114 13 13 +214 13 13 +314 13 13 +414 13 13 +15 14 14 +115 14 14 +215 14 14 +315 14 14 +415 14 14 +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0 OFFSET 10; +f0 f1 f2 +set sort_buffer_size= 32768; +SELECT SQL_CALC_FOUND_ROWS * FROM t1 +ORDER BY f1, f0 LIMIT 30; +f0 f1 f2 +1 0 0 +101 0 0 +201 0 0 +301 0 0 +401 0 0 +2 1 1 +102 1 1 +202 1 1 +302 1 1 +402 1 1 +3 2 2 +103 2 2 +203 2 2 +303 2 2 +403 2 2 +4 3 3 +104 3 3 +204 3 3 +304 3 3 +404 3 3 +5 4 4 +105 4 4 +205 4 4 +305 4 4 +405 4 4 +6 5 5 +106 5 5 +206 5 5 +306 5 5 +406 5 5 +SELECT FOUND_ROWS(); +FOUND_ROWS() +500 +SELECT SQL_CALC_FOUND_ROWS * FROM t1 +ORDER BY f1, f0 LIMIT 0; +f0 f1 f2 +SELECT FOUND_ROWS(); +FOUND_ROWS() +500 +SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10 +ORDER BY f2, f0 LIMIT 20; +f0 f1 f2 +12 11 11 +112 11 11 +212 11 11 +312 11 11 +412 11 11 +13 12 12 +113 12 12 +213 12 12 +313 12 12 +413 12 12 +14 13 13 +114 13 13 +214 13 13 +314 13 13 +414 13 13 +15 14 14 +115 14 14 +215 14 14 +315 14 14 +415 14 14 +SELECT FOUND_ROWS(); +FOUND_ROWS() +445 +SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10 +ORDER BY f2, f0 LIMIT 0; +f0 f1 f2 +SELECT FOUND_ROWS(); +FOUND_ROWS() +445 +SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10 +ORDER BY f2, f0 LIMIT 10 OFFSET 10; +f0 f1 f2 +14 13 13 +114 13 13 +214 13 13 +314 13 13 +414 13 13 +15 14 14 +115 14 14 +215 14 14 +315 14 14 +415 14 14 +SELECT FOUND_ROWS(); +FOUND_ROWS() +445 +SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10 +ORDER BY f2, f0 LIMIT 0 OFFSET 10; +f0 f1 f2 +SELECT FOUND_ROWS(); +FOUND_ROWS() +445 +set sort_buffer_size= 327680; +SELECT * FROM t1 JOIN tmp on t1.f2=tmp.f2 +ORDER BY tmp.f1, f0 LIMIT 30; +f0 f1 f2 f1 f2 +1 0 0 0 0 +1 0 0 0 0 +1 0 0 0 0 +101 0 0 0 0 +101 0 0 0 0 +101 0 0 0 0 +201 0 0 0 0 +201 0 0 0 0 +201 0 0 0 0 +301 0 0 0 0 +301 0 0 0 0 +301 0 0 0 0 +401 0 0 0 0 +401 0 0 0 0 +401 0 0 0 0 +2 1 1 1 1 +2 1 1 1 1 +2 1 1 1 1 +102 1 1 1 1 +102 1 1 1 1 +102 1 1 1 1 +202 1 1 1 1 +202 1 1 1 1 +202 1 1 1 1 +302 1 1 1 1 +302 1 1 1 1 +302 1 1 1 1 +402 1 1 1 1 +402 1 1 1 1 +402 1 1 1 1 +SELECT * FROM t1 JOIN tmp on t1.f2=tmp.f2 +ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30; +f0 f1 f2 f1 f2 +3 2 2 2 2 +3 2 2 2 2 +3 2 2 2 2 +103 2 2 2 2 +103 2 2 2 2 +103 2 2 2 2 +203 2 2 2 2 +203 2 2 2 2 +203 2 2 2 2 +303 2 2 2 2 +303 2 2 2 2 +303 2 2 2 2 +403 2 2 2 2 +403 2 2 2 2 +403 2 2 2 2 +4 3 3 3 3 +4 3 3 3 3 +4 3 3 3 3 +104 3 3 3 3 +104 3 3 3 3 +104 3 3 3 3 +204 3 3 3 3 +204 3 3 3 3 +204 3 3 3 3 +304 3 3 3 3 +304 3 3 3 3 +304 3 3 3 3 +404 3 3 3 3 +404 3 3 3 3 +404 3 3 3 3 +SELECT SQL_CALC_FOUND_ROWS * FROM t1 JOIN tmp on t1.f2=tmp.f2 +ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30; +f0 f1 f2 f1 f2 +3 2 2 2 2 +3 2 2 2 2 +3 2 2 2 2 +103 2 2 2 2 +103 2 2 2 2 +103 2 2 2 2 +203 2 2 2 2 +203 2 2 2 2 +203 2 2 2 2 +303 2 2 2 2 +303 2 2 2 2 +303 2 2 2 2 +403 2 2 2 2 +403 2 2 2 2 +403 2 2 2 2 +4 3 3 3 3 +4 3 3 3 3 +4 3 3 3 3 +104 3 3 3 3 +104 3 3 3 3 +104 3 3 3 3 +204 3 3 3 3 +204 3 3 3 3 +204 3 3 3 3 +304 3 3 3 3 +304 3 3 3 3 +304 3 3 3 3 +404 3 3 3 3 +404 3 3 3 3 +404 3 3 3 3 +SELECT FOUND_ROWS(); +FOUND_ROWS() +1500 +SELECT SQL_CALC_FOUND_ROWS * FROM t1 JOIN tmp on t1.f2=tmp.f2 +WHERE t1.f2>20 +ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30; +f0 f1 f2 f1 f2 +24 23 23 23 23 +24 23 23 23 23 +24 23 23 23 23 +124 23 23 23 23 +124 23 23 23 23 +124 23 23 23 23 +224 23 23 23 23 +224 23 23 23 23 +224 23 23 23 23 +324 23 23 23 23 +324 23 23 23 23 +324 23 23 23 23 +424 23 23 23 23 +424 23 23 23 23 +424 23 23 23 23 +25 24 24 24 24 +25 24 24 24 24 +25 24 24 24 24 +125 24 24 24 24 +125 24 24 24 24 +125 24 24 24 24 +225 24 24 24 24 +225 24 24 24 24 +225 24 24 24 24 +325 24 24 24 24 +325 24 24 24 24 +325 24 24 24 24 +425 24 24 24 24 +425 24 24 24 24 +425 24 24 24 24 +SELECT FOUND_ROWS(); +FOUND_ROWS() +1185 +CREATE VIEW v1 as SELECT * FROM t1 ORDER BY f1, f0 LIMIT 30; +SELECT * FROM v1; +f0 f1 f2 +1 0 0 +101 0 0 +201 0 0 +301 0 0 +401 0 0 +2 1 1 +102 1 1 +202 1 1 +302 1 1 +402 1 1 +3 2 2 +103 2 2 +203 2 2 +303 2 2 +403 2 2 +4 3 3 +104 3 3 +204 3 3 +304 3 3 +404 3 3 +5 4 4 +105 4 4 +205 4 4 +305 4 4 +405 4 4 +6 5 5 +106 5 5 +206 5 5 +306 5 5 +406 5 5 +drop view v1; +CREATE VIEW v1 as SELECT * FROM t1 ORDER BY f1, f0 LIMIT 100; +SELECT * FROM v1 ORDER BY f2, f0 LIMIT 30; +f0 f1 f2 +1 0 0 +101 0 0 +201 0 0 +301 0 0 +401 0 0 +2 1 1 +102 1 1 +202 1 1 +302 1 1 +402 1 1 +11 10 10 +111 10 10 +211 10 10 +311 10 10 +411 10 10 +12 11 11 +112 11 11 +212 11 11 +312 11 11 +412 11 11 +13 12 12 +113 12 12 +213 12 12 +313 12 12 +413 12 12 +14 13 13 +114 13 13 +214 13 13 +314 13 13 +414 13 13 +CREATE VIEW v2 as SELECT * FROM t1 ORDER BY f2, f0 LIMIT 100; +SELECT * FROM v1 JOIN v2 on v1.f1=v2.f1 ORDER BY v1.f2,v1.f0,v2.f0 +LIMIT 30; +f0 f1 f2 f0 f1 f2 +1 0 0 1 0 0 +1 0 0 101 0 0 +1 0 0 201 0 0 +1 0 0 301 0 0 +1 0 0 401 0 0 +101 0 0 1 0 0 +101 0 0 101 0 0 +101 0 0 201 0 0 +101 0 0 301 0 0 +101 0 0 401 0 0 +201 0 0 1 0 0 +201 0 0 101 0 0 +201 0 0 201 0 0 +201 0 0 301 0 0 +201 0 0 401 0 0 +301 0 0 1 0 0 +301 0 0 101 0 0 +301 0 0 201 0 0 +301 0 0 301 0 0 +301 0 0 401 0 0 +401 0 0 1 0 0 +401 0 0 101 0 0 +401 0 0 201 0 0 +401 0 0 301 0 0 +401 0 0 401 0 0 +2 1 1 2 1 1 +2 1 1 102 1 1 +2 1 1 202 1 1 +2 1 1 302 1 1 +2 1 1 402 1 1 +SELECT floor(f1/10) f3, count(f2) FROM t1 +group by 1 ORDER BY 2,1 LIMIT 5; +f3 count(f2) +0 50 +1 50 +2 50 +3 50 +4 50 +SELECT floor(f1/10) f3, count(f2) FROM t1 +group by 1 ORDER BY 2,1 LIMIT 0; +f3 count(f2) +CREATE PROCEDURE wl1393_sp_test() +BEGIN +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 30; +SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 15 OFFSET 15; +SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10 +ORDER BY f2, f0 LIMIT 15 OFFSET 15; +SELECT FOUND_ROWS(); +SELECT * FROM v1 ORDER BY f2, f0 LIMIT 30; +END| +CALL wl1393_sp_test()| +f0 f1 f2 +12 11 11 +112 11 11 +212 11 11 +312 11 11 +412 11 11 +13 12 12 +113 12 12 +213 12 12 +313 12 12 +413 12 12 +14 13 13 +114 13 13 +214 13 13 +314 13 13 +414 13 13 +15 14 14 +115 14 14 +215 14 14 +315 14 14 +415 14 14 +16 15 15 +116 15 15 +216 15 15 +316 15 15 +416 15 15 +17 16 16 +117 16 16 +217 16 16 +317 16 16 +417 16 16 +f0 f1 f2 +15 14 14 +115 14 14 +215 14 14 +315 14 14 +415 14 14 +16 15 15 +116 15 15 +216 15 15 +316 15 15 +416 15 15 +17 16 16 +117 16 16 +217 16 16 +317 16 16 +417 16 16 +f0 f1 f2 +15 14 14 +115 14 14 +215 14 14 +315 14 14 +415 14 14 +16 15 15 +116 15 15 +216 15 15 +316 15 15 +416 15 15 +17 16 16 +117 16 16 +217 16 16 +317 16 16 +417 16 16 +FOUND_ROWS() +445 +f0 f1 f2 +1 0 0 +101 0 0 +201 0 0 +301 0 0 +401 0 0 +2 1 1 +102 1 1 +202 1 1 +302 1 1 +402 1 1 +11 10 10 +111 10 10 +211 10 10 +311 10 10 +411 10 10 +12 11 11 +112 11 11 +212 11 11 +312 11 11 +412 11 11 +13 12 12 +113 12 12 +213 12 12 +313 12 12 +413 12 12 +14 13 13 +114 13 13 +214 13 13 +314 13 13 +414 13 13 +DROP PROCEDURE wl1393_sp_test| +SELECT d1.* FROM t1 +LEFT JOIN (SELECT * FROM t1 LIMIT 30) d1 on t1.f1=d1.f1 +ORDER BY d1.f2 DESC LIMIT 30; +f0 f1 f2 +10 9 9 +10 9 9 +10 9 9 +10 9 9 +10 9 9 +9 8 8 +9 8 8 +9 8 8 +9 8 8 +9 8 8 +8 7 7 +8 7 7 +8 7 7 +8 7 7 +8 7 7 +7 6 6 +7 6 6 +7 6 6 +7 6 6 +7 6 6 +6 5 5 +6 5 5 +6 5 5 +6 5 5 +6 5 5 +5 4 4 +5 4 4 +5 4 4 +5 4 4 +5 4 4 +SELECT * FROM t1 WHERE f1 = (SELECT f1 FROM t1 ORDER BY 1 LIMIT 1); +f0 f1 f2 +1 0 0 +101 0 0 +201 0 0 +301 0 0 +401 0 0 +SELECT * FROM t1 WHERE f1 = (SELECT f1 FROM t1 ORDER BY 1 LIMIT 2); +ERROR 21000: Subquery returns more than 1 row +DROP TABLE t1, tmp; +DROP VIEW v1, v2; +# end of WL#1393 - Optimizing filesort with small limit CREATE TABLE t1 ( id1 INT NULL, id2 INT NOT NULL, === added file 'mysql-test/r/order_by_sortkey.result' --- a/mysql-test/r/order_by_sortkey.result 1970-01-01 00:00:00 +0000 +++ b/mysql-test/r/order_by_sortkey.result 2010-11-24 13:24:14 +0000 @@ -0,0 +1,161 @@ +CREATE TABLE t1( +f0 int auto_increment PRIMARY KEY, +f1 int, +f2 varchar(200) +) ENGINE=MyISAM; +INSERT INTO t1(f1, f2) VALUES +(0,"0"),(1,"1"),(2,"2"),(3,"3"),(4,"4"),(5,"5"), +(6,"6"),(7,"7"),(8,"8"),(9,"9"),(10,"10"), +(11,"11"),(12,"12"),(13,"13"),(14,"14"),(15,"15"), +(16,"16"),(17,"17"),(18,"18"),(19,"19"),(20,"20"), +(21,"21"),(22,"22"),(23,"23"),(24,"24"),(25,"25"), +(26,"26"),(27,"27"),(28,"28"),(29,"29"),(30,"30"), +(31,"31"),(32,"32"),(33,"33"),(34,"34"),(35,"35"), +(36,"36"),(37,"37"),(38,"38"),(39,"39"),(40,"40"), +(41,"41"),(42,"42"),(43,"43"),(44,"44"),(45,"45"), +(46,"46"),(47,"47"),(48,"48"),(49,"49"),(50,"50"), +(51,"51"),(52,"52"),(53,"53"),(54,"54"),(55,"55"), +(56,"56"),(57,"57"),(58,"58"),(59,"59"),(60,"60"), +(61,"61"),(62,"62"),(63,"63"),(64,"64"),(65,"65"), +(66,"66"),(67,"67"),(68,"68"),(69,"69"),(70,"70"), +(71,"71"),(72,"72"),(73,"73"),(74,"74"),(75,"75"), +(76,"76"),(77,"77"),(78,"78"),(79,"79"),(80,"80"), +(81,"81"),(82,"82"),(83,"83"),(84,"84"),(85,"85"), +(86,"86"),(87,"87"),(88,"88"),(89,"89"),(90,"90"), +(91,"91"),(92,"92"),(93,"93"),(94,"94"),(95,"95"), +(96,"96"),(97,"97"),(98,"98"),(99,"99"); +CREATE TEMPORARY TABLE tmp (f1 int, f2 varchar(20)); +INSERT INTO tmp SELECT f1,f2 FROM t1; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +INSERT INTO tmp SELECT f1,f2 FROM t1; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +INSERT INTO tmp SELECT f1,f2 FROM t1; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +INSERT INTO tmp SELECT f1,f2 FROM t1; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +INSERT INTO tmp SELECT f1,f2 FROM t1; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +INSERT INTO tmp SELECT f1,f2 FROM t1; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +INSERT INTO tmp SELECT f1,f2 FROM t1; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +INSERT INTO tmp SELECT f1,f2 FROM t1; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +set sort_buffer_size= 32768; +FLUSH STATUS; +SHOW SESSION STATUS LIKE 'Sort%'; +Variable_name Value +Sort_merge_passes 0 +Sort_range 0 +Sort_rows 0 +Sort_scan 0 +SELECT * FROM t1 ORDER BY f2 LIMIT 100; +f0 f1 f2 +1 0 0 +101 0 0 +201 0 0 +301 0 0 +401 0 0 +501 0 0 +601 0 0 +701 0 0 +801 0 0 +901 0 0 +1001 0 0 +1101 0 0 +1201 0 0 +1301 0 0 +1401 0 0 +1501 0 0 +1601 0 0 +1701 0 0 +1801 0 0 +1901 0 0 +2001 0 0 +2101 0 0 +2201 0 0 +2301 0 0 +2401 0 0 +2501 0 0 +2601 0 0 +2701 0 0 +2801 0 0 +2901 0 0 +3001 0 0 +3101 0 0 +3201 0 0 +3301 0 0 +3401 0 0 +3501 0 0 +3601 0 0 +3701 0 0 +3801 0 0 +3901 0 0 +4001 0 0 +4101 0 0 +4201 0 0 +4301 0 0 +4401 0 0 +4501 0 0 +4601 0 0 +4701 0 0 +4801 0 0 +4901 0 0 +5001 0 0 +5101 0 0 +5201 0 0 +5301 0 0 +5401 0 0 +5501 0 0 +5601 0 0 +5701 0 0 +5801 0 0 +5901 0 0 +6001 0 0 +6101 0 0 +6201 0 0 +6301 0 0 +6401 0 0 +6501 0 0 +6601 0 0 +6701 0 0 +6801 0 0 +6901 0 0 +7001 0 0 +7101 0 0 +7201 0 0 +7301 0 0 +7401 0 0 +7501 0 0 +7601 0 0 +7701 0 0 +7801 0 0 +7901 0 0 +8001 0 0 +8101 0 0 +8201 0 0 +8301 0 0 +8401 0 0 +8501 0 0 +8601 0 0 +8701 0 0 +8801 0 0 +8901 0 0 +9001 0 0 +9101 0 0 +9201 0 0 +9301 0 0 +9401 0 0 +9501 0 0 +9601 0 0 +9701 0 0 +9801 0 0 +9901 0 0 +SHOW SESSION STATUS LIKE 'Sort%'; +Variable_name Value +Sort_merge_passes 0 +Sort_range 0 +Sort_rows 100 +Sort_scan 1 +DROP TABLE t1, tmp; === modified file 'mysql-test/r/select_none.result' --- a/mysql-test/r/select_none.result 2010-10-26 09:10:59 +0000 +++ b/mysql-test/r/select_none.result 2010-11-24 13:24:14 +0000 @@ -4875,7 +4875,7 @@ SELECT 1 FROM t1 ORDER BY a COLLATE lati DROP TABLE t1; End of 5.1 tests # -# Bug#45277: Lost HAVING clause led to a wrong result. +# Bug#45227: Lost HAVING clause led to a wrong result. # CREATE TABLE `CC` ( `int_nokey` int(11) NOT NULL, @@ -4904,7 +4904,7 @@ Warning 1292 Truncated incorrect DOUBLE Warning 1292 Truncated incorrect DOUBLE value: 'm' Warning 1292 Truncated incorrect DOUBLE value: 'j' DROP TABLE CC; -# End of test#45277 +# End of test#45227 # # Bug#54515: Crash in opt_range.cc::get_best_group_min_max on # SELECT from VIEW with GROUP BY === added file 'mysql-test/t/order_by_sortkey.test' --- a/mysql-test/t/order_by_sortkey.test 1970-01-01 00:00:00 +0000 +++ b/mysql-test/t/order_by_sortkey.test 2010-11-24 13:24:14 +0000 @@ -0,0 +1,66 @@ +# +# WL#1393 - ORDER BY with LIMIT tests +# +# A big test in a separate file, so that we can run the original +# order_by test with --debug without timeout. +# +# All the sort keys fit in memory, but the addon fields do not. +# +CREATE TABLE t1( + f0 int auto_increment PRIMARY KEY, + f1 int, + f2 varchar(200) +) ENGINE=MyISAM; + +INSERT INTO t1(f1, f2) VALUES +(0,"0"),(1,"1"),(2,"2"),(3,"3"),(4,"4"),(5,"5"), +(6,"6"),(7,"7"),(8,"8"),(9,"9"),(10,"10"), +(11,"11"),(12,"12"),(13,"13"),(14,"14"),(15,"15"), +(16,"16"),(17,"17"),(18,"18"),(19,"19"),(20,"20"), +(21,"21"),(22,"22"),(23,"23"),(24,"24"),(25,"25"), +(26,"26"),(27,"27"),(28,"28"),(29,"29"),(30,"30"), +(31,"31"),(32,"32"),(33,"33"),(34,"34"),(35,"35"), +(36,"36"),(37,"37"),(38,"38"),(39,"39"),(40,"40"), +(41,"41"),(42,"42"),(43,"43"),(44,"44"),(45,"45"), +(46,"46"),(47,"47"),(48,"48"),(49,"49"),(50,"50"), +(51,"51"),(52,"52"),(53,"53"),(54,"54"),(55,"55"), +(56,"56"),(57,"57"),(58,"58"),(59,"59"),(60,"60"), +(61,"61"),(62,"62"),(63,"63"),(64,"64"),(65,"65"), +(66,"66"),(67,"67"),(68,"68"),(69,"69"),(70,"70"), +(71,"71"),(72,"72"),(73,"73"),(74,"74"),(75,"75"), +(76,"76"),(77,"77"),(78,"78"),(79,"79"),(80,"80"), +(81,"81"),(82,"82"),(83,"83"),(84,"84"),(85,"85"), +(86,"86"),(87,"87"),(88,"88"),(89,"89"),(90,"90"), +(91,"91"),(92,"92"),(93,"93"),(94,"94"),(95,"95"), +(96,"96"),(97,"97"),(98,"98"),(99,"99"); + +CREATE TEMPORARY TABLE tmp (f1 int, f2 varchar(20)); +INSERT INTO tmp SELECT f1,f2 FROM t1; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +INSERT INTO tmp SELECT f1,f2 FROM t1; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +INSERT INTO tmp SELECT f1,f2 FROM t1; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +INSERT INTO tmp SELECT f1,f2 FROM t1; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +INSERT INTO tmp SELECT f1,f2 FROM t1; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +INSERT INTO tmp SELECT f1,f2 FROM t1; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +INSERT INTO tmp SELECT f1,f2 FROM t1; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; +INSERT INTO tmp SELECT f1,f2 FROM t1; +INSERT INTO t1(f1,f2) SELECT * FROM tmp; + +# Test when only sortkeys fits to memory +set sort_buffer_size= 32768; + +FLUSH STATUS; +SHOW SESSION STATUS LIKE 'Sort%'; + +SELECT * FROM t1 ORDER BY f2 LIMIT 100; + +SHOW SESSION STATUS LIKE 'Sort%'; + +DROP TABLE t1, tmp; === modified file 'mysys/CMakeLists.txt' --- a/mysys/CMakeLists.txt 2010-08-12 15:27:53 +0000 +++ b/mysys/CMakeLists.txt 2010-11-24 13:24:14 +0000 @@ -77,3 +77,8 @@ DTRACE_INSTRUMENT(mysys) ADD_EXECUTABLE(thr_lock thr_lock.c) TARGET_LINK_LIBRARIES(thr_lock mysys) SET_TARGET_PROPERTIES(thr_lock PROPERTIES COMPILE_FLAGS "-DMAIN") + +ADD_EXECUTABLE(queues queues.c) +TARGET_LINK_LIBRARIES(queues mysys) +SET_TARGET_PROPERTIES(queues PROPERTIES COMPILE_FLAGS "-DMAIN") +ADD_TEST(queues_test queues) === modified file 'mysys/queues.c' --- a/mysys/queues.c 2010-07-08 21:20:08 +0000 +++ b/mysys/queues.c 2010-11-24 13:24:14 +0000 @@ -381,11 +381,11 @@ static uint tot_no_parts= 0; static uint tot_no_loops= 0; static uint expected_part= 0; static uint expected_num= 0; -static bool max_ind= 0; -static bool fix_used= 0; +static my_bool max_ind= 0; +static my_bool fix_used= 0; static ulonglong start_time= 0; -static bool is_divisible_by(uint num, uint divisor) +static my_bool is_divisible_by(uint num, uint divisor) { uint quotient= num / divisor; if (quotient * divisor == num) @@ -479,6 +479,7 @@ static int test_compare(void *null_arg, uint a_num= (*(uint*)a) & 0x3FFFFF; uint b_num= (*(uint*)b) & 0x3FFFFF; uint a_part, b_part; + (void) null_arg; if (a_num > b_num) return +1; if (a_num < b_num) @@ -492,7 +493,7 @@ static int test_compare(void *null_arg, return 0; } -bool check_num(uint num_part) +my_bool check_num(uint num_part) { uint part= num_part >> 22; uint num= num_part & 0x3FFFFF; @@ -543,7 +544,7 @@ void perform_insert(QUEUE *queue) } } -bool perform_ins_del(QUEUE *queue, bool max_ind) +my_bool perform_ins_del(QUEUE *queue, my_bool max_ind) { uint i= 0, no_loops= tot_no_loops, j= tot_no_parts; do @@ -571,10 +572,10 @@ bool perform_ins_del(QUEUE *queue, bool return FALSE; } -bool do_test(uint no_parts, uint l_max_ind, bool l_fix_used) +my_bool do_test(uint no_parts, uint l_max_ind, my_bool l_fix_used) { QUEUE queue; - bool result; + my_bool result; max_ind= l_max_ind; fix_used= l_fix_used; init_queue(&queue, no_parts, 0, max_ind, test_compare, NULL); === modified file 'sql/CMakeLists.txt' --- a/sql/CMakeLists.txt 2010-11-14 18:09:32 +0000 +++ b/sql/CMakeLists.txt 2010-11-24 13:24:14 +0000 @@ -40,6 +40,7 @@ ENDIF() SET (SQL_SOURCE ../sql-common/client.c derror.cc des_key_file.cc discover.cc ../libmysql/errmsg.c field.cc field_conv.cc + bounded_queue.cc filesort.cc gstream.cc sha2.cc handler.cc hash_filo.h sql_plugin_services.h hostname.cc init.cc item.cc item_buff.cc item_cmpfunc.cc @@ -109,7 +110,8 @@ SET (SLAVE_SOURCE rpl_slave.cc rpl_repor rpl_info_factory.cc server_ids.h) ADD_LIBRARY(slave ${SLAVE_SOURCE}) ADD_DEPENDENCIES(slave GenError) -ADD_LIBRARY(sqlgunitlib mdl.cc sql_list.cc sql_string.cc thr_malloc.cc) +ADD_LIBRARY(sqlgunitlib + bounded_queue.cc mdl.cc sql_list.cc sql_string.cc thr_malloc.cc) ADD_DEPENDENCIES(sqlgunitlib GenError) === modified file 'sql/Makefile.am' --- a/sql/Makefile.am 2010-11-09 20:10:44 +0000 +++ b/sql/Makefile.am 2010-11-24 13:24:14 +0000 @@ -162,6 +162,7 @@ mysqld_SOURCES = sql_lex.cc sql_handler. log.cc init.cc derror.cc sql_acl.cc \ unireg.cc des_key_file.cc \ discover.cc sql_time.cc opt_range.cc opt_sum.cc \ + bounded_queue.cc \ records.cc filesort.cc handler.cc \ ha_partition.cc \ debug_sync.cc \ === added file 'sql/bounded_queue.cc' --- a/sql/bounded_queue.cc 1970-01-01 00:00:00 +0000 +++ b/sql/bounded_queue.cc 2010-11-24 13:24:14 +0000 @@ -0,0 +1,86 @@ +/* Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ + +#include "bounded_queue.h" +#include "sql_const.h" +#include "sql_sort.h" + + +namespace { +/** + A local helper function. See comments for get_merge_buffers_cost(). + */ +double get_merge_cost(ha_rows num_elements, ha_rows num_buffers, uint elem_size) +{ + return + 2.0 * ((double) num_elements * elem_size) / IO_SIZE + + (double) num_elements * log((double) num_buffers) / + (TIME_FOR_COMPARE_ROWID * M_LN2); +} +} + +/** + This is a simplified, and faster version of @see get_merge_many_buffs_cost(). + We calculate the cost of merging buffers, by simulating the actions + of @see merge_many_buff. For explanations of formulas below, + see comments for get_merge_buffers_cost(). + TODO: Use this function for Unique::get_use_cost(). +*/ +double get_merge_many_buffs_cost_fast(ha_rows num_rows, + ha_rows num_keys_per_buffer, + uint elem_size) +{ + ha_rows num_buffers= num_rows / num_keys_per_buffer; + ha_rows last_n_elems= num_rows % num_keys_per_buffer; + double total_cost; + + /* Calculate CPU cost of sorting buffers. */ + total_cost= + ( num_buffers * num_keys_per_buffer * log(1.0 + num_keys_per_buffer) + + last_n_elems * log(1.0 + last_n_elems) ) + / TIME_FOR_COMPARE_ROWID; + + /* Simulate behavior of merge_many_buff(). */ + while (num_buffers >= MERGEBUFF2) + { + /* Calculate # of calls to merge_buffers() */ + const ha_rows loop_limit= num_buffers - MERGEBUFF*3/2; + const ha_rows num_merge_calls= 1 + loop_limit/MERGEBUFF; + const ha_rows i_end_value= num_merge_calls * MERGEBUFF; + + /* Cost of merge sort 'num_merge_calls' */ + total_cost+= + num_merge_calls * + get_merge_cost(num_keys_per_buffer * MERGEBUFF, MERGEBUFF, elem_size); + + /* # of records in remaining buffers. */ + last_n_elems+= (num_buffers - i_end_value) * num_keys_per_buffer; + + /* Cost of merge sort of remaining buffers. */ + total_cost+= get_merge_cost(last_n_elems, + num_buffers - i_end_value, elem_size); + + num_buffers= num_merge_calls; + num_keys_per_buffer*= MERGEBUFF; + } + + /* Simulate final merge_buff call. */ + last_n_elems+= num_keys_per_buffer * num_buffers; + total_cost+= get_merge_cost(last_n_elems, num_buffers, elem_size); + + return total_cost; +} + + === added file 'sql/bounded_queue.h' --- a/sql/bounded_queue.h 1970-01-01 00:00:00 +0000 +++ b/sql/bounded_queue.h 2010-11-24 13:24:14 +0000 @@ -0,0 +1,199 @@ +/* Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ + +#ifndef BOUNDED_QUEUE_INCLUDED +#define BOUNDED_QUEUE_INCLUDED + +#include +#include "my_global.h" +#include "my_base.h" +#include "my_sys.h" +#include "queues.h" + +class Sort_param; + +/** + A priority queue with a fixed, limited size. + + This is a wrapper on top of QUEUE and the queue_xxx() functions. + It keeps the top-N elements which are inserted. + + Elements of type Element_type are pushed into the queue. + For each element, we call a user-supplied keymaker_function, + to generate a key of type Key_type for the element. + Instances of Key_type are compared with the user-supplied compare_function. + */ +template +class Bounded_queue +{ +public: + Bounded_queue() + { + memset(&m_queue, 0, sizeof(m_queue)); + } + + ~Bounded_queue() + { + delete_queue(&m_queue); + } + + /** + Function for making sort-key from input data. + @param param Sort parameters. + @param to Where to put the key. + @param from The input data. + */ + typedef void (*keymaker_function)(Sort_param *param, + Key_type *to, + Element_type *from); + + /** + Function for comparing two keys. + @param n Pointer to number of bytes to compare. + @param a First key. + @param b Second key. + @retval -1, 0, or 1 depending on whether the left argument is + less than, equal to, or greater than the right argument. + */ + typedef int (*compare_function)(size_t *v, Key_type **a, Key_type **b); + + /** + Initialize the queue. + + @param max_elements The size of the queue. + @param offset_to_key Offset to key in elements stored in the queue. + @param max_at_top Set to 1 if you want biggest element on top. + @param compare Compare function for elements, takes 3 arguments. + If NULL, we use get_ptr_compare(compare_length). + @param compare_length Length of the data (i.e. the keys) used for sorting. + @param keymaker Function which generates keys for elements. + @param sort_param Sort parameters. + @param sort_keys Array of pointers to keys to sort. + + @retval 0 OK, 1 Could not allocate memory. + + We do *not* take ownership of any of the input pointer arguments. + */ + int init(ha_rows max_elements, uint offset_to_key, bool max_at_top, + compare_function compare, size_t compare_length, + keymaker_function keymaker, Sort_param *sort_param, + Key_type **sort_keys); + + /** + Pushes an element on the queue. + If the queue is already full, we discard one element. + Calls keymaker_function to generate a key for the element. + + @param element The element to be pushed. + */ + void push(Element_type *element); + + /** + Removes the top element from the queue. + + @retval Pointer to the (key of the) removed element. + */ + Key_type **pop() + { + // Don't return the extra element to the client code. + if (queue_is_full((&m_queue))) + queue_remove(&m_queue, 0); + return reinterpret_cast(queue_remove(&m_queue, 0)); + } + + /** + The number of elements in the queue. + */ + uint num_elements() const { return m_queue.elements; } + + /** + Is the queue initialized? + */ + bool is_initialized() const { return m_queue.max_elements > 0; } + +private: + Key_type **m_sort_keys; + size_t m_compare_length; + keymaker_function m_keymaker; + Sort_param *m_sort_param; + st_queue m_queue; +}; + + +template +int Bounded_queue::init(ha_rows max_elements, + uint offset_to_key, + bool max_at_top, + compare_function compare, + size_t compare_length, + keymaker_function keymaker, + Sort_param *sort_param, + Key_type **sort_keys) +{ + DBUG_ASSERT(sort_keys != NULL); + + m_sort_keys= sort_keys; + m_compare_length= compare_length; + m_keymaker= keymaker; + m_sort_param= sort_param; + // init_queue() takes an uint, and also does (max_elements + 1) + if (max_elements >= (UINT_MAX - 1)) + return 1; + if (compare == NULL) + compare= reinterpret_cast(get_ptr_compare(compare_length)); + // We allocate space for one extra element, for replace when queue is full. + return init_queue(&m_queue, (uint) max_elements + 1, offset_to_key, max_at_top, + reinterpret_cast(compare), &m_compare_length); +} + + +template +void Bounded_queue::push(Element_type *element) +{ + DBUG_ASSERT(is_initialized()); + if (queue_is_full((&m_queue))) + { + Key_type **pq_top= reinterpret_cast(queue_top(&m_queue)); + (*m_keymaker)(m_sort_param, *pq_top, element); + queue_replaced(&m_queue); + } else { + (*m_keymaker)(m_sort_param, m_sort_keys[m_queue.elements], element); + queue_insert(&m_queue, + reinterpret_cast(&m_sort_keys[m_queue.elements])); + } +} + + +/* + Calculate cost of merge sort + + @param num_rows Total number of rows. + @param num_keys_per_buffer Number of keys per buffer. + @param elem_size Size of each element. + + Calculates cost of merge sort by simulating call to merge_many_buff(). + + @retval + computed cost of merge sort + + @note + Declared here in order to be able to unit test it, + since library dependencies have not been sorted out yet. +*/ +double get_merge_many_buffs_cost_fast(ha_rows num_rows, + ha_rows num_keys_per_buffer, + uint elem_size); + +#endif // BOUNDED_QUEUE_INCLUDED === modified file 'sql/filesort.cc' --- a/sql/filesort.cc 2010-08-04 10:34:01 +0000 +++ b/sql/filesort.cc 2010-11-24 13:24:14 +0000 @@ -32,11 +32,17 @@ #include "probes_mysql.h" #include "sql_test.h" // TEST_filesort #include "opt_range.h" // SQL_SELECT +#include "bounded_queue.h" +#include "sql_select.h" #ifndef THREAD #define SKIP_DBUG_IN_FILESORT #endif +#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION +template class Bounded_queue; +#endif + /// How to write record_ref. #define WRITE_REF(file,from) \ if (my_b_write((file),(uchar*) (from),param->ref_length)) \ @@ -44,30 +50,68 @@ if (my_b_write((file),(uchar*) (from),pa /* functions defined in this file */ -static char **make_char_array(char **old_pos, register uint fields, - uint length, myf my_flag); +static void make_char_array(FILESORT_INFO *info, uint fields, uint length); static uchar *read_buffpek_from_file(IO_CACHE *buffer_file, uint count, uchar *buf); -static ha_rows find_all_keys(SORTPARAM *param,SQL_SELECT *select, - uchar * *sort_keys, IO_CACHE *buffer_file, - IO_CACHE *tempfile,IO_CACHE *indexfile); -static int write_keys(SORTPARAM *param,uchar * *sort_keys, - uint count, IO_CACHE *buffer_file, IO_CACHE *tempfile); -static void make_sortkey(SORTPARAM *param,uchar *to, uchar *ref_pos); -static void register_used_fields(SORTPARAM *param); -static int merge_index(SORTPARAM *param,uchar *sort_buffer, - BUFFPEK *buffpek, - uint maxbuffer,IO_CACHE *tempfile, - IO_CACHE *outfile); -static bool save_index(SORTPARAM *param,uchar **sort_keys, uint count, +static ha_rows find_all_keys(Sort_param *param,SQL_SELECT *select, + uchar **sort_keys, IO_CACHE *buffer_file, + IO_CACHE *tempfile, + Bounded_queue *pq, + ha_rows *found_rows); +static int write_keys(Sort_param *param,uchar * *sort_keys, + uint count, IO_CACHE *buffer_file, IO_CACHE *tempfile); +static void make_sortkey(Sort_param *param,uchar *to, uchar *ref_pos); +static void register_used_fields(Sort_param *param); +static int merge_index(Sort_param *param,uchar *sort_buffer, + BUFFPEK *buffpek, + uint maxbuffer,IO_CACHE *tempfile, + IO_CACHE *outfile); +static bool save_index(Sort_param *param,uchar **sort_keys, uint count, FILESORT_INFO *table_sort); static uint suffix_length(ulong string_length); static uint sortlength(THD *thd, SORT_FIELD *sortorder, uint s_length, bool *multi_byte_charset); -static SORT_ADDON_FIELD *get_addon_fields(THD *thd, Field **ptabfield, +static SORT_ADDON_FIELD *get_addon_fields(ulong max_length_for_sort_data, + Field **ptabfield, uint sortlength, uint *plength); static void unpack_addon_fields(struct st_sort_addon_field *addon_field, uchar *buff); +static bool check_if_pq_applicable(Sort_param *param, FILESORT_INFO *info, + TABLE *table, + ha_rows records, ulong memory_available); + + +void Sort_param::init(uint sortlen, TABLE *table, ulong max_length_for_sort_data, + ha_rows maxrows, bool sort_positions) +{ + sort_length= sortlen; + ref_length= table->file->ref_length; + if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) && + !table->fulltext_searched && !sort_positions) + { + /* + Get the descriptors of all fields whose values are appended + to sorted fields and get its total length in addon_length. + */ + addon_field= get_addon_fields(max_length_for_sort_data, + table->field, sort_length, &addon_length); + } + if (addon_field) + res_length= addon_length; + else + { + res_length= ref_length; + /* + The reference to the record is considered + as an additional sorted field + */ + sort_length+= ref_length; + } + rec_length= sort_length + addon_length; + max_rows= maxrows; +} + + /** Sort a table. Creates a set of pointers that can be used to read the rows @@ -80,18 +124,17 @@ static void unpack_addon_fields(struct s The result set is stored in table->io_cache or table->record_pointers. - @param thd Current thread - @param table Table to sort - @param sortorder How to sort the table - @param s_length Number of elements in sortorder - @param select condition to apply to the rows - @param max_rows Return only this many rows - @param sort_positions Set to 1 if we want to force sorting by position - (Needed by UPDATE/INSERT or ALTER TABLE) - @param examined_rows Store number of examined rows here + @param thd Current thread + @param table Table to sort + @param sortorder How to sort the table + @param s_length Number of elements in sortorder + @param select Condition to apply to the rows + @param max_rows Return only this many rows + @param sort_positions Set to TRUE if we want to force sorting by position + (Needed by UPDATE/INSERT or ALTER TABLE) + @param[out] examined_rows Store number of examined rows here + @param options 0 or OPTION_FOUND_ROWS - @todo - check why we do this (param.keys--) @note If we sort by position (like if sort_positions is 1) filesort() will call table->prepare_for_position(). @@ -100,29 +143,30 @@ static void unpack_addon_fields(struct s HA_POS_ERROR Error @retval \# Number of rows - @retval - examined_rows will be set to number of examined rows */ ha_rows filesort(THD *thd, TABLE *table, SORT_FIELD *sortorder, uint s_length, SQL_SELECT *select, ha_rows max_rows, - bool sort_positions, ha_rows *examined_rows) + bool sort_positions, ha_rows *examined_rows, + ulonglong options) { int error; - ulong memavl, min_sort_memory; + ulong memory_available= thd->variables.sortbuff_size; uint maxbuffer; BUFFPEK *buffpek; - ha_rows records= HA_POS_ERROR; - uchar **sort_keys= 0; - IO_CACHE tempfile, buffpek_pointers, *selected_records_file, *outfile; - SORTPARAM param; + ha_rows num_rows= HA_POS_ERROR; + uchar **sort_keys= NULL; + IO_CACHE tempfile, buffpek_pointers, *outfile; + Sort_param param; bool multi_byte_charset; + ha_rows found_rows; + Bounded_queue pq; + DBUG_ENTER("filesort"); DBUG_EXECUTE("info",TEST_filesort(sortorder,s_length);); #ifdef SKIP_DBUG_IN_FILESORT DBUG_PUSH(""); /* No DBUG here */ #endif - FILESORT_INFO table_sort; TABLE_LIST *tab= table->pos_in_table_list; Item_subselect *subselect= tab ? tab->containing_subselect() : 0; @@ -139,7 +183,7 @@ ha_rows filesort(THD *thd, TABLE *table, QUICK_INDEX_MERGE_SELECT. Work with a copy and put it back at the end when index_merge select has finished with it. */ - memcpy(&table_sort, &table->sort, sizeof(FILESORT_INFO)); + FILESORT_INFO table_sort= table->sort; table->sort.io_cache= NULL; outfile= table_sort.io_cache; @@ -147,117 +191,95 @@ ha_rows filesort(THD *thd, TABLE *table, my_b_clear(&buffpek_pointers); buffpek=0; error= 1; - bzero((char*) ¶m,sizeof(param)); - param.sort_length= sortlength(thd, sortorder, s_length, &multi_byte_charset); + + param.init(sortlength(thd, sortorder, s_length, &multi_byte_charset), + table, + thd->variables.max_length_for_sort_data, max_rows, sort_positions); /* filesort cannot handle zero-length records. */ DBUG_ASSERT(param.sort_length); - param.ref_length= table->file->ref_length; - param.addon_field= 0; - param.addon_length= 0; - if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) && - !table->fulltext_searched && !sort_positions) - { - /* - Get the descriptors of all fields whose values are appended - to sorted fields and get its total length in param.spack_length. - */ - param.addon_field= get_addon_fields(thd, table->field, - param.sort_length, - ¶m.addon_length); - } table_sort.addon_buf= 0; table_sort.addon_length= param.addon_length; table_sort.addon_field= param.addon_field; table_sort.unpack= unpack_addon_fields; - if (param.addon_field) - { - param.res_length= param.addon_length; - if (!(table_sort.addon_buf= (uchar *) my_malloc(param.addon_length, - MYF(MY_WME)))) + if (param.addon_field && + !(table_sort.addon_buf= + (uchar *) my_malloc(param.addon_length, MYF(MY_WME)))) goto err; - } - else - { - param.res_length= param.ref_length; - /* - The reference to the record is considered - as an additional sorted field - */ - param.sort_length+= param.ref_length; - } - param.rec_length= param.sort_length+param.addon_length; - param.max_rows= max_rows; if (select && select->quick) - { status_var_increment(thd->status_var.filesort_range_count); - } else - { status_var_increment(thd->status_var.filesort_scan_count); - } -#ifdef CAN_TRUST_RANGE - if (select && select->quick && select->quick->records > 0L) - { - records=min((ha_rows) (select->quick->records*2+EXTRA_RECORDS*2), - table->file->stats.records)+EXTRA_RECORDS; - selected_records_file=0; - } - else -#endif - { - records= table->file->estimate_rows_upper_bound(); - /* - If number of records is not known, use as much of sort buffer - as possible. - */ - if (records == HA_POS_ERROR) - records--; // we use 'records+1' below. - selected_records_file= 0; - } + + /* + If number of rows is not known, use as much of sort buffer as possible. + */ + num_rows= table->file->estimate_rows_upper_bound(); if (multi_byte_charset && !(param.tmp_buffer= (char*) my_malloc(param.sort_length,MYF(MY_WME)))) goto err; - memavl= thd->variables.sortbuff_size; - min_sort_memory= max(MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2); - while (memavl >= min_sort_memory) - { - ulong old_memavl; - ulong keys= memavl/(param.rec_length+sizeof(char*)); - param.keys=(uint) min(records+1, keys); - if ((table_sort.sort_keys= - (uchar **) make_char_array((char **) table_sort.sort_keys, - param.keys, param.rec_length, MYF(0)))) - break; - old_memavl=memavl; - if ((memavl=memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory) - memavl= min_sort_memory; + if (check_if_pq_applicable(¶m, &table_sort, + table, num_rows, memory_available)) + { + DBUG_PRINT("info", ("filesort PQ is applicable")); + const size_t compare_length= param.sort_length; + if (pq.init(param.max_rows, 0, true, + NULL, + compare_length, + &make_sortkey, ¶m, table_sort.sort_keys)) + { + // If failed to init pq, fall back to merge-sort. + my_free(table_sort.sort_keys); + table_sort.sort_keys= NULL; + } } - sort_keys= table_sort.sort_keys; - if (memavl < min_sort_memory) + else { - my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR+ME_WAITTANG)); - goto err; + DBUG_PRINT("info", ("filesort PQ is not applicable")); + + const ulong min_sort_memory= + max(MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2); + while (memory_available >= min_sort_memory) + { + ulong old_memory_available; + ulong keys= memory_available / (param.rec_length+sizeof(char*)); + param.num_keys_per_buffer= (uint) min(num_rows, keys); + make_char_array(&table_sort, param.num_keys_per_buffer, param.rec_length); + if (table_sort.sort_keys) + break; + old_memory_available= memory_available; + if ((memory_available= memory_available/4*3) < min_sort_memory && + old_memory_available > min_sort_memory) + memory_available= min_sort_memory; + } + if (memory_available < min_sort_memory) + { + my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR+ME_WAITTANG)); + goto err; + } } + + sort_keys= table_sort.sort_keys; if (open_cached_file(&buffpek_pointers,mysql_tmpdir,TEMP_PREFIX, DISK_BUFFER_SIZE, MYF(MY_WME))) goto err; - param.keys--; /* TODO: check why we do this */ param.sort_form= table; param.end=(param.local_sortorder=sortorder)+s_length; - if ((records=find_all_keys(¶m,select,sort_keys, &buffpek_pointers, - &tempfile, selected_records_file)) == + if ((num_rows= find_all_keys(¶m, select, sort_keys, &buffpek_pointers, + &tempfile, + pq.is_initialized() ? &pq : NULL, + &found_rows)) == HA_POS_ERROR) goto err; maxbuffer= (uint) (my_b_tell(&buffpek_pointers)/sizeof(*buffpek)); if (maxbuffer == 0) // The whole set is in memory { - if (save_index(¶m,sort_keys,(uint) records, &table_sort)) + if (save_index(¶m, sort_keys, (uint) num_rows, &table_sort)) goto err; } else @@ -286,8 +308,9 @@ ha_rows filesort(THD *thd, TABLE *table, Use also the space previously used by string pointers in sort_buffer for temporary key storage. */ - param.keys=((param.keys*(param.rec_length+sizeof(char*))) / - param.rec_length-1); + param.num_keys_per_buffer=((param.num_keys_per_buffer * + (param.rec_length + sizeof(char*))) / + param.rec_length - 1); maxbuffer--; // Offset from 0 if (merge_many_buff(¶m,(uchar*) sort_keys,buffpek,&maxbuffer, &tempfile)) @@ -299,9 +322,17 @@ ha_rows filesort(THD *thd, TABLE *table, outfile)) goto err; } - if (records > param.max_rows) - records=param.max_rows; - error =0; + + if (pq.is_initialized() && (options & OPTION_FOUND_ROWS)) + { + DBUG_PRINT("info", ("filesort PQ and OPTION_FOUND_ROWS")); + } + + if (options & OPTION_FOUND_ROWS) + num_rows= found_rows; + else if (num_rows > param.max_rows) + num_rows= param.max_rows; + error= 0; err: my_free(param.tmp_buffer); @@ -332,15 +363,16 @@ ha_rows filesort(THD *thd, TABLE *table, MYF(ME_ERROR+ME_WAITTANG)); else statistic_add(thd->status_var.filesort_rows, - (ulong) records, &LOCK_status); + (ulong) num_rows, &LOCK_status); *examined_rows= param.examined_rows; #ifdef SKIP_DBUG_IN_FILESORT DBUG_POP(); /* Ok to DBUG */ #endif - memcpy(&table->sort, &table_sort, sizeof(FILESORT_INFO)); - DBUG_PRINT("exit",("records: %ld", (long) records)); - MYSQL_FILESORT_DONE(error, records); - DBUG_RETURN(error ? HA_POS_ERROR : records); + table->sort= table_sort; + DBUG_PRINT("exit",("num_rows: %ld examined_rows: %ld", + (long) num_rows, (long) *examined_rows)); + MYSQL_FILESORT_DONE(error, num_rows); + DBUG_RETURN(error ? HA_POS_ERROR : num_rows); } /* filesort */ @@ -364,25 +396,26 @@ void filesort_free_buffers(TABLE *table, table->sort.addon_field= NULL; } -/** Make a array of string pointers. */ +/** Makes an array of string pointers for info->sort_keys. */ -static char **make_char_array(char **old_pos, register uint fields, - uint length, myf my_flag) +static void make_char_array(FILESORT_INFO *info, uint fields, uint length) { - register char **pos; - char *char_pos; DBUG_ENTER("make_char_array"); - if (old_pos || - (old_pos= (char**) my_malloc((uint) fields*(length+sizeof(char*)), - my_flag))) + if (!info->sort_keys) + info->sort_keys= + (uchar**) my_malloc(fields * (length + sizeof(uchar*)), MYF(0)); + + if (info->sort_keys) { - pos=old_pos; char_pos=((char*) (pos+fields)) -length; - while (fields--) *(pos++) = (char_pos+= length); + uchar **pos= info->sort_keys; + uchar *char_pos= ((uchar*) (pos+fields)) - length; + while (fields--) + *(pos++) = (char_pos+= length); } - DBUG_RETURN(old_pos); -} /* make_char_array */ + DBUG_VOID_RETURN; +} /** Read 'count' number of buffer pointers into memory. */ @@ -461,7 +494,8 @@ static void dbug_print_record(TABLE *tab #endif /** - Search after sort_keys and write them into tempfile. + Search after sort_keys, and write them into tempfile + (if we run out of space in the sort_keys buffer). All produced sequences are guaranteed to be non-empty. @param param Sorting parameter @@ -470,20 +504,26 @@ static void dbug_print_record(TABLE *tab @param buffpek_pointers File to write BUFFPEKs describing sorted segments in tempfile. @param tempfile File to write sorted sequences of sortkeys to. - @param indexfile If !NULL, use it for source data (contains rowids) + @param pq If !NULL, use it for keeping top N elements + @param [out] found_rows The number of FOUND_ROWS(). @note Basic idea: @verbatim while (get_next_sortkey()) { - if (no free space in sort_keys buffers) + if (using priority queue) + push sort key into queue + else { - sort sort_keys buffer; - dump sorted sequence to 'tempfile'; - dump BUFFPEK describing sequence location into 'buffpek_pointers'; + if (no free space in sort_keys buffers) + { + sort sort_keys buffer; + dump sorted sequence to 'tempfile'; + dump BUFFPEK describing sequence location into 'buffpek_pointers'; + } + put sort key into 'sort_keys'; } - put sort key into 'sort_keys'; } if (sort_keys has some elements && dumped at least once) sort-dump-dump as above; @@ -497,10 +537,12 @@ static void dbug_print_record(TABLE *tab HA_POS_ERROR on error. */ -static ha_rows find_all_keys(SORTPARAM *param, SQL_SELECT *select, - uchar **sort_keys, - IO_CACHE *buffpek_pointers, - IO_CACHE *tempfile, IO_CACHE *indexfile) +static ha_rows find_all_keys(Sort_param *param, SQL_SELECT *select, + uchar **sort_keys, + IO_CACHE *buffpek_pointers, + IO_CACHE *tempfile, + Bounded_queue *pq, + ha_rows *found_rows) { int error,flag,quick_select; uint idx,indexpos,ref_length; @@ -512,11 +554,12 @@ static ha_rows find_all_keys(SORTPARAM * handler *file; MY_BITMAP *save_read_set, *save_write_set; bool skip_record; + DBUG_ENTER("find_all_keys"); DBUG_PRINT("info",("using: %s", (select ? select->quick ? "ranges" : "where": "every row"))); - + idx=indexpos=0; error=quick_select=0; sort_form=param->sort_form; @@ -525,12 +568,12 @@ static ha_rows find_all_keys(SORTPARAM * ref_pos= ref_buff; quick_select=select && select->quick; record=0; - flag= ((!indexfile && file->ha_table_flags() & HA_REC_NOT_IN_SEQ) - || quick_select); - if (indexfile || flag) + *found_rows= 0; + flag= ((file->ha_table_flags() & HA_REC_NOT_IN_SEQ) || quick_select); + if (flag) ref_pos= &file->ref[0]; next_pos=ref_pos; - if (! indexfile && ! quick_select) + if (!quick_select) { next_pos=(uchar*) 0; /* Find records in sequence */ file->ha_rnd_init(1); @@ -577,16 +620,6 @@ static ha_rows find_all_keys(SORTPARAM * } else /* Not quick-select */ { - if (indexfile) - { - if (my_b_read(indexfile,(uchar*) ref_pos,ref_length)) /* purecov: deadcode */ - { - error= my_errno ? my_errno : -1; /* Abort */ - break; - } - error= file->ha_rnd_pos(sort_form->record[0], next_pos); - } - else { error= file->ha_rnd_next(sort_form->record[0]); if (!flag) @@ -604,7 +637,7 @@ static ha_rows find_all_keys(SORTPARAM * if (*killed) { DBUG_PRINT("info",("Sort killed by user")); - if (!indexfile && !quick_select) + if (!quick_select) { (void) file->extra(HA_EXTRA_NO_CACHE); file->ha_rnd_end(); @@ -616,14 +649,23 @@ static ha_rows find_all_keys(SORTPARAM * if (!error && (!select || (!select->skip_record(thd, &skip_record) && !skip_record))) { - if (idx == param->keys) + ++(*found_rows); + if (pq) + { + pq->push(ref_pos); + idx= pq->num_elements(); + } + else { - if (write_keys(param,sort_keys,idx,buffpek_pointers,tempfile)) - DBUG_RETURN(HA_POS_ERROR); - idx=0; - indexpos++; + if (idx == param->num_keys_per_buffer) + { + if (write_keys(param,sort_keys, idx, buffpek_pointers, tempfile)) + DBUG_RETURN(HA_POS_ERROR); + idx= 0; + indexpos++; + } + make_sortkey(param, sort_keys[idx++], ref_pos); } - make_sortkey(param,sort_keys[idx++],ref_pos); } else file->unlock_row(); @@ -653,9 +695,11 @@ static ha_rows find_all_keys(SORTPARAM * if (indexpos && idx && write_keys(param,sort_keys,idx,buffpek_pointers,tempfile)) DBUG_RETURN(HA_POS_ERROR); /* purecov: inspected */ - DBUG_RETURN(my_b_inited(tempfile) ? - (ha_rows) (my_b_tell(tempfile)/param->rec_length) : - idx); + const ha_rows retval= + my_b_inited(tempfile) ? + (ha_rows) (my_b_tell(tempfile)/param->rec_length) : idx; + DBUG_PRINT("info", ("find_all_keys return %u", (uint) retval)); + DBUG_RETURN(retval); } /* find_all_keys */ @@ -682,7 +726,7 @@ static ha_rows find_all_keys(SORTPARAM * */ static int -write_keys(SORTPARAM *param, register uchar **sort_keys, uint count, +write_keys(Sort_param *param, register uchar **sort_keys, uint count, IO_CACHE *buffpek_pointers, IO_CACHE *tempfile) { size_t sort_length, rec_length; @@ -745,8 +789,8 @@ static inline void store_length(uchar *t /** Make a sort-key from record. */ -static void make_sortkey(register SORTPARAM *param, - register uchar *to, uchar *ref_pos) +static void make_sortkey(register Sort_param *param, + register uchar *to, uchar *ref_pos) { reg3 Field *field; reg1 SORT_FIELD *sort_field; @@ -998,7 +1042,7 @@ static void make_sortkey(register SORTPA Register fields used by sorting in the sorted table's read set */ -static void register_used_fields(SORTPARAM *param) +static void register_used_fields(Sort_param *param) { reg1 SORT_FIELD *sort_field; TABLE *table=param->sort_form; @@ -1036,17 +1080,17 @@ static void register_used_fields(SORTPAR } -static bool save_index(SORTPARAM *param, uchar **sort_keys, uint count, +static bool save_index(Sort_param *param, uchar **sort_keys, uint count, FILESORT_INFO *table_sort) { uint offset,res_length; uchar *to; DBUG_ENTER("save_index"); - my_string_ptr_sort((uchar*) sort_keys, (uint) count, param->sort_length); + my_string_ptr_sort((uchar*) sort_keys, count, param->sort_length); res_length= param->res_length; offset= param->rec_length-res_length; - if ((ha_rows) count > param->max_rows) + if ((ha_rows) count > param->max_rows && param->max_rows > 0) count=(uint) param->max_rows; if (!(to= table_sort->record_pointers= (uchar*) my_malloc(res_length*count, MYF(MY_WME)))) @@ -1060,10 +1104,148 @@ static bool save_index(SORTPARAM *param, } +/** + Test whether priority queue is worth using to get top elements of an + ordered result set. If it is then allocates buffer for required amount of + records + + @param param Sort parameters. + @param filesort_info Filesort information. + @param table Table to sort. + @param num_rows Estimate of number of rows in source record set. + @param memory_available Memory available for sorting. + + DESCRIPTION + Given a query like this: + SELECT ... FROM t ORDER BY a1,...,an LIMIT max_rows; + This function tests whether a priority queue should be used to keep + the result. Necessary conditions are: + - estimate that it is actually cheaper than merge-sort + - enough memory to store the records. + + If we don't have space for records, but we *do* have + space for keys, we may rewrite 'table' to sort with + references to records instead of additional data. + (again, based on estimates that it will actually be cheaper). + + @retval + true - if it's ok to use PQ + false - PQ will be slower than merge-sort, or there is not enough memory. +*/ + +bool check_if_pq_applicable(Sort_param *param, + FILESORT_INFO *filesort_info, + TABLE *table, ha_rows num_rows, + ulong memory_available) +{ + DBUG_ENTER("check_if_pq_applicable"); + + /* + How much Priority Queue sort is slower than qsort. + For qsort we have an average case complexity of O(n*log(n)) comparisons. + When using a priority queue, we have log(n) comparisons each time we + push a new element. For PQ we also call qsort at the end. + Measurements show that there is some extra overhead in QUEUE, + so we set it to 3.0 rather than 2.0. + */ + const double PQ_slowness= 3.0; + + if (param->max_rows == HA_POS_ERROR) + { + DBUG_PRINT("info", ("max_rows = HA_POS_ERROR")); + DBUG_RETURN(NULL); + } + + if (param->max_rows + 2 >= UINT_MAX) + { + DBUG_PRINT("info", ("Too large LIMIT")); + DBUG_RETURN(NULL); + } + + ulong num_available_keys= + memory_available / (param->rec_length + sizeof(char*)); + param->num_keys_per_buffer= (uint) param->max_rows + 1; + + if (num_rows < num_available_keys) + { + /* The whole source set fits into memory. */ + if (param->max_rows < num_rows/PQ_slowness ) + { + make_char_array(filesort_info, + param->num_keys_per_buffer, param->rec_length); + if (filesort_info->sort_keys) + DBUG_RETURN(true); + } + else + { + /* PQ will be slower */ + DBUG_RETURN(false); + } + } + + if (param->num_keys_per_buffer < num_available_keys) + { + make_char_array(filesort_info, + param->num_keys_per_buffer, param->rec_length); + if (filesort_info->sort_keys) + DBUG_RETURN(true); + } + + /* Try to strip off addon fields */ + if (param->addon_field) + { + const ulong row_length= + param->sort_length + param->ref_length + sizeof(char*); + num_available_keys= memory_available / row_length; + + if (param->num_keys_per_buffer < num_available_keys) + { + const double sort_merge_cost= + get_merge_many_buffs_cost_fast(num_rows, + num_available_keys, + row_length); + + /* + PQ has cost: + (insert + qsort) * log(queue size) / TIME_FOR_COMPARE_ROWID + + cost of file lookup afterwards. + */ + const double pq_cost= + (PQ_slowness * num_rows + param->num_keys_per_buffer) * + log(param->max_rows + 1.0) / TIME_FOR_COMPARE_ROWID + + param->max_rows * table->file->scan_time(); + + if (sort_merge_cost < pq_cost) + DBUG_RETURN(false); + + make_char_array(filesort_info, + param->num_keys_per_buffer, param->rec_length); + if (filesort_info->sort_keys) + { + // Make attached data to be references instead of fields. + my_free(filesort_info->addon_buf); + my_free(filesort_info->addon_field); + filesort_info->addon_buf= NULL; + filesort_info->addon_field= NULL; + param->addon_field= NULL; + param->addon_length= 0; + + param->res_length= param->ref_length; + param->sort_length+= param->ref_length; + param->rec_length= param->sort_length; + + DBUG_RETURN(true); + } + } + } + DBUG_RETURN(false); +} + + /** Merge buffers to make < MERGEBUFF2 buffers. */ -int merge_many_buff(SORTPARAM *param, uchar *sort_buffer, - BUFFPEK *buffpek, uint *maxbuffer, IO_CACHE *t_file) +int merge_many_buff(Sort_param *param, uchar *sort_buffer, + BUFFPEK *buffpek, uint *maxbuffer, IO_CACHE *t_file) { register uint i; IO_CACHE t_file2,*from_file,*to_file,*temp; @@ -1192,7 +1374,7 @@ void reuse_freed_buff(QUEUE *queue, BUFF other error */ -int merge_buffers(SORTPARAM *param, IO_CACHE *from_file, +int merge_buffers(Sort_param *param, IO_CACHE *from_file, IO_CACHE *to_file, uchar *sort_buffer, BUFFPEK *lastbuff, BUFFPEK *Fb, BUFFPEK *Tb, int flag) @@ -1224,7 +1406,7 @@ int merge_buffers(SORTPARAM *param, IO_C res_length= param->res_length; sort_length= param->sort_length; offset= rec_length-res_length; - maxcount= (ulong) (param->keys/((uint) (Tb-Fb) +1)); + maxcount= (ulong) (param->num_keys_per_buffer / ((uint) (Tb-Fb) +1)); to_start_filepos= my_b_tell(to_file); strpos= (uchar*) sort_buffer; org_max_rows=max_rows= param->max_rows; @@ -1249,8 +1431,7 @@ int merge_buffers(SORTPARAM *param, IO_C { buffpek->base= strpos; buffpek->max_keys= maxcount; - strpos+= (uint) (error= (int) read_to_buffer(from_file, buffpek, - rec_length)); + strpos+= (uint) (error= (int)read_to_buffer(from_file, buffpek, rec_length)); if (error == -1) goto err; /* purecov: inspected */ buffpek->max_keys= buffpek->mem_count; // If less data in buffers than expected @@ -1340,7 +1521,7 @@ int merge_buffers(SORTPARAM *param, IO_C } buffpek= (BUFFPEK*) queue_top(&queue); buffpek->base= sort_buffer; - buffpek->max_keys= param->keys; + buffpek->max_keys= param->num_keys_per_buffer; /* As we know all entries in the buffer are unique, we only have to @@ -1400,9 +1581,9 @@ err: /* Do a merge to output-file (save only positions) */ -static int merge_index(SORTPARAM *param, uchar *sort_buffer, - BUFFPEK *buffpek, uint maxbuffer, - IO_CACHE *tempfile, IO_CACHE *outfile) +static int merge_index(Sort_param *param, uchar *sort_buffer, + BUFFPEK *buffpek, uint maxbuffer, + IO_CACHE *tempfile, IO_CACHE *outfile) { DBUG_ENTER("merge_index"); if (merge_buffers(param,tempfile,outfile,sort_buffer,buffpek,buffpek, @@ -1554,7 +1735,8 @@ sortlength(THD *thd, SORT_FIELD *sortord */ static SORT_ADDON_FIELD * -get_addon_fields(THD *thd, Field **ptabfield, uint sortlength, uint *plength) +get_addon_fields(ulong max_length_for_sort_data, + Field **ptabfield, uint sortlength, uint *plength) { Field **pfield; Field *field; @@ -1590,7 +1772,7 @@ get_addon_fields(THD *thd, Field **ptabf return 0; length+= (null_fields+7)/8; - if (length+sortlength > thd->variables.max_length_for_sort_data || + if (length+sortlength > max_length_for_sort_data || !(addonf= (SORT_ADDON_FIELD *) my_malloc(sizeof(SORT_ADDON_FIELD)* (fields+1), MYF(MY_WME)))) return 0; === modified file 'sql/filesort.h' --- a/sql/filesort.h 2010-07-02 02:58:51 +0000 +++ b/sql/filesort.h 2010-11-24 13:24:14 +0000 @@ -29,7 +29,7 @@ typedef struct st_sort_field SORT_FIELD; ha_rows filesort(THD *thd, TABLE *table, st_sort_field *sortorder, uint s_length, SQL_SELECT *select, ha_rows max_rows, bool sort_positions, - ha_rows *examined_rows); + ha_rows *examined_rows, ulonglong options); void filesort_free_buffers(TABLE *table, bool full); void change_double_for_sort(double nr,uchar *to); === modified file 'sql/sql_const.h' --- a/sql/sql_const.h 2010-07-13 17:29:44 +0000 +++ b/sql/sql_const.h 2010-11-24 13:24:14 +0000 @@ -161,13 +161,13 @@ instead of reading with keys. The number says how many evaluation of the WHERE clause is comparable to reading one extra row from a table. */ -#define TIME_FOR_COMPARE 5 // 5 compares == one read +#define TIME_FOR_COMPARE 5.0 // 5 compares == one read /** Number of comparisons of table rowids equivalent to reading one row from a table. */ -#define TIME_FOR_COMPARE_ROWID (TIME_FOR_COMPARE*2) +#define TIME_FOR_COMPARE_ROWID (TIME_FOR_COMPARE*2.0) /* For sequential disk seeks the cost formula is: === modified file 'sql/sql_delete.cc' --- a/sql/sql_delete.cc 2010-10-21 11:34:17 +0000 +++ b/sql/sql_delete.cc 2010-11-24 13:24:14 +0000 @@ -243,7 +243,7 @@ bool mysql_delete(THD *thd, TABLE_LIST * if (!(sortorder= make_unireg_sortorder(order, &length, NULL)) || (table->sort.found_records = filesort(thd, table, sortorder, length, select, HA_POS_ERROR, 1, - &examined_rows)) + &examined_rows, 0)) == HA_POS_ERROR) { delete select; === modified file 'sql/sql_select.cc' --- a/sql/sql_select.cc 2010-11-17 15:23:17 +0000 +++ b/sql/sql_select.cc 2010-11-24 13:24:14 +0000 @@ -2557,6 +2557,7 @@ JOIN::optimize() if (!group_list && ! exec_tmp_table1->distinct && order && simple_order) { + DBUG_PRINT("info",("Sorting for order")); thd_proc_info(thd, "Sorting for order"); if (create_sort_index(thd, this, order, HA_POS_ERROR, HA_POS_ERROR, TRUE)) @@ -2734,6 +2735,8 @@ JOIN::exec() int tmp_error; DBUG_ENTER("JOIN::exec"); + const bool has_group_by= this->group; + thd_proc_info(thd, "executing"); error= 0; if (procedure) @@ -3019,11 +3022,12 @@ JOIN::exec() } if (curr_join->group_list) { - thd_proc_info(thd, "Creating sort index"); if (curr_join->join_tab == join_tab && save_join_tab()) { DBUG_VOID_RETURN; } + DBUG_PRINT("info",("Sorting for index")); + thd_proc_info(thd, "Creating sort index"); if (create_sort_index(thd, curr_join, curr_join->group_list, HA_POS_ERROR, HA_POS_ERROR, FALSE) || make_group_fields(this, curr_join)) @@ -3249,12 +3253,25 @@ JOIN::exec() the query. XXX: it's never shown in EXPLAIN! OPTION_FOUND_ROWS supersedes LIMIT and is taken into account. */ - if (create_sort_index(thd, curr_join, - curr_join->group_list ? - curr_join->group_list : curr_join->order, - curr_join->select_limit, - (select_options & OPTION_FOUND_ROWS ? - HA_POS_ERROR : unit->select_limit_cnt), + DBUG_PRINT("info",("Sorting for order by/group by")); + ORDER *order_arg= + curr_join->group_list ? curr_join->group_list : curr_join->order; + /* + filesort_limit: Max number of rows that needs to be sorted. + We can use select_limit_cnt only if we have no group_by and 1 table. + */ + const ha_rows filesort_limit_arg= + (has_group_by || curr_join->tables > 1) + ? curr_join->select_limit : unit->select_limit_cnt; + const ha_rows select_limit_arg= + select_options & OPTION_FOUND_ROWS + ? HA_POS_ERROR : unit->select_limit_cnt; + + if (create_sort_index(thd, + curr_join, + order_arg, + filesort_limit_arg, + select_limit_arg, curr_join->group_list ? FALSE : TRUE)) DBUG_VOID_RETURN; sortorder= curr_join->sortorder; @@ -3287,6 +3304,15 @@ JOIN::exec() Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF); error= do_select(curr_join, curr_fields_list, NULL, procedure); thd->limit_found_rows= curr_join->send_records; + if (curr_join->order && + curr_join->sortorder && + curr_join->select_options & OPTION_FOUND_ROWS) + { + /* Use info provided by filesort. */ + DBUG_ASSERT(curr_join->tables > curr_join->const_tables); + JOIN_TAB *tab= curr_join->join_tab + curr_join->const_tables; + thd->limit_found_rows= tab->records; + } /* Accumulate the counts from all join iterations of all join parts. */ thd->examined_row_count+= curr_join->examined_rows; @@ -18385,8 +18411,26 @@ end_send(JOIN *join, JOIN_TAB *join_tab error=join->result->send_data(*join->fields); if (error) DBUG_RETURN(NESTED_LOOP_ERROR); /* purecov: inspected */ - if (++join->send_records >= join->unit->select_limit_cnt && - join->do_send_rows) + + ++join->send_records; + if (join->send_records >= join->unit->select_limit_cnt && + !join->do_send_rows) + { + /* + If filesort is used for sorting, stop after select_limit_cnt+1 + records are read. Because of optimization in some cases it can + provide only select_limit_cnt+1 records. + */ + if (join->order && + join->sortorder && + join->select_options & OPTION_FOUND_ROWS) + { + DBUG_PRINT("info", ("filesort NESTED_LOOP_QUERY_LIMIT")); + DBUG_RETURN(NESTED_LOOP_QUERY_LIMIT); + } + } + if (join->send_records >= join->unit->select_limit_cnt && + join->do_send_rows) { if (join->select_options & OPTION_FOUND_ROWS) { @@ -20033,7 +20077,7 @@ use_filesort: SYNOPSIS create_sort_index() thd Thread handler - tab Table to sort (in join structure) + join The join order How table should be sorted filesort_limit Max number of rows that needs to be sorted select_limit Max number of rows in final output @@ -20135,9 +20179,11 @@ create_sort_index(THD *thd, JOIN *join, if (table->s->tmp_table) table->file->info(HA_STATUS_VARIABLE); // Get record count - table->sort.found_records=filesort(thd, table,join->sortorder, length, - select, filesort_limit, 0, - &examined_rows); + table->sort.found_records= filesort(thd, table, join->sortorder, length, + select, filesort_limit, 0, + &examined_rows, + join->tables != 1 ? 0 : + join->select_options & OPTION_FOUND_ROWS); tab->records= table->sort.found_records; // For SQL_CALC_ROWS if (select) { @@ -20484,7 +20530,7 @@ SORT_FIELD *make_unireg_sortorder(ORDER pos= sort= sortorder; if (!pos) - return 0; + DBUG_RETURN(0); for (;order;order=order->next,pos++) { @@ -20501,6 +20547,7 @@ SORT_FIELD *make_unireg_sortorder(ORDER else pos->item= *order->item; pos->reverse=! order->asc; + DBUG_ASSERT(pos->field != NULL || pos->item != NULL); } *length=count; DBUG_RETURN(sort); === modified file 'sql/sql_sort.h' --- a/sql/sql_sort.h 2010-07-02 18:15:21 +0000 +++ b/sql/sql_sort.h 2010-11-24 13:24:14 +0000 @@ -16,6 +16,7 @@ along with this program; if not, write to the Free Software Foundation, 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA */ +#include "m_string.h" /* memset */ #include "my_global.h" /* uchar */ #include "my_base.h" /* ha_rows */ #include "my_sys.h" /* qsort2_cmp */ @@ -27,7 +28,6 @@ typedef struct st_sort_field SORT_FIELD; class Field; struct TABLE; - /* Defines used by filesort and uniques */ #define MERGEBUFF 7 @@ -71,15 +71,17 @@ struct BUFFPEK_COMPARE_CONTEXT void *key_compare_arg; }; -typedef struct st_sort_param { - uint rec_length; /* Length of sorted records */ - uint sort_length; /* Length of sorted columns */ - uint ref_length; /* Length of record ref. */ - uint addon_length; /* Length of added packed fields */ - uint res_length; /* Length of records in final sorted file/buffer */ - uint keys; /* Max keys / buffer */ - ha_rows max_rows,examined_rows; - TABLE *sort_form; /* For quicker make_sortkey */ +class Sort_param { +public: + uint rec_length; /* Length of sorted records */ + uint sort_length; /* Length of sorted columns */ + uint ref_length; /* Length of record ref. */ + uint addon_length; /* Length of added packed fields */ + uint res_length; /* Length of records in final sorted file/buffer */ + uint num_keys_per_buffer; /* Max keys / buffer */ + ha_rows max_rows; /* Select limit, or HA_POS_ERROR if unlimited */ + ha_rows examined_rows; /* Number of examined rows */ + TABLE *sort_form; /* For quicker make_sortkey */ SORT_FIELD *local_sortorder; SORT_FIELD *end; SORT_ADDON_FIELD *addon_field; /* Descriptors for companion fields */ @@ -89,18 +91,25 @@ typedef struct st_sort_param { /* The fields below are used only by Unique class */ qsort2_cmp compare; BUFFPEK_COMPARE_CONTEXT cmp_context; -} SORTPARAM; + + Sort_param() + { + memset(this, 0, sizeof(*this)); + } + void init(uint sortlen, TABLE *table, ulong max_length_for_sort_data, + ha_rows maxrows, bool sort_positions); +}; -int merge_many_buff(SORTPARAM *param, uchar *sort_buffer, +int merge_many_buff(Sort_param *param, uchar *sort_buffer, BUFFPEK *buffpek, uint *maxbuffer, IO_CACHE *t_file); uint read_to_buffer(IO_CACHE *fromfile,BUFFPEK *buffpek, uint sort_length); -int merge_buffers(SORTPARAM *param,IO_CACHE *from_file, - IO_CACHE *to_file, uchar *sort_buffer, - BUFFPEK *lastbuff,BUFFPEK *Fb, - BUFFPEK *Tb,int flag); +int merge_buffers(Sort_param *param,IO_CACHE *from_file, + IO_CACHE *to_file, uchar *sort_buffer, + BUFFPEK *lastbuff,BUFFPEK *Fb, + BUFFPEK *Tb,int flag); void reuse_freed_buff(QUEUE *queue, BUFFPEK *reuse, uint key_length); #endif /* SQL_SORT_INCLUDED */ === modified file 'sql/sql_table.cc' --- a/sql/sql_table.cc 2010-11-11 09:40:06 +0000 +++ b/sql/sql_table.cc 2010-11-24 13:24:14 +0000 @@ -7105,7 +7105,7 @@ copy_data_between_tables(TABLE *from,TAB !(sortorder= make_unireg_sortorder(order, &length, NULL)) || (from->sort.found_records= filesort(thd, from, sortorder, length, (SQL_SELECT *) 0, HA_POS_ERROR, - 1, &examined_rows)) == + 1, &examined_rows, 0)) == HA_POS_ERROR) goto err; } === modified file 'sql/sql_update.cc' --- a/sql/sql_update.cc 2010-10-21 12:18:25 +0000 +++ b/sql/sql_update.cc 2010-11-24 13:24:14 +0000 @@ -479,7 +479,7 @@ int mysql_update(THD *thd, if (!(sortorder=make_unireg_sortorder(order, &length, NULL)) || (table->sort.found_records= filesort(thd, table, sortorder, length, select, limit, 1, - &examined_rows)) + &examined_rows, 0)) == HA_POS_ERROR) { goto err; === modified file 'sql/uniques.cc' --- a/sql/uniques.cc 2010-11-05 22:14:29 +0000 +++ b/sql/uniques.cc 2010-11-24 13:24:14 +0000 @@ -577,7 +577,6 @@ bool Unique::walk(tree_walk_action actio bool Unique::get(TABLE *table) { - SORTPARAM sort_param; table->sort.found_records=elements+tree.elements_in_tree; if (my_b_tell(&file) == 0) @@ -612,19 +611,20 @@ bool Unique::get(TABLE *table) return 1; reinit_io_cache(outfile,WRITE_CACHE,0L,0,0); - bzero((char*) &sort_param,sizeof(sort_param)); + Sort_param sort_param; sort_param.max_rows= elements; sort_param.sort_form=table; sort_param.rec_length= sort_param.sort_length= sort_param.ref_length= size; - sort_param.keys= (uint) (max_in_memory_size / sort_param.sort_length); + sort_param.num_keys_per_buffer= + (uint) (max_in_memory_size / sort_param.sort_length); sort_param.not_killable=1; - if (!(sort_buffer=(uchar*) my_malloc((sort_param.keys+1) * + if (!(sort_buffer=(uchar*) my_malloc((sort_param.num_keys_per_buffer + 1) * sort_param.sort_length, MYF(0)))) return 1; - sort_param.unique_buff= sort_buffer+(sort_param.keys* + sort_param.unique_buff= sort_buffer+(sort_param.num_keys_per_buffer * sort_param.sort_length); sort_param.compare= (qsort2_cmp) buffpek_compare; === modified file 'unittest/gunit/CMakeLists.txt' --- a/unittest/gunit/CMakeLists.txt 2010-10-18 11:31:18 +0000 +++ b/unittest/gunit/CMakeLists.txt 2010-11-24 13:24:14 +0000 @@ -206,8 +206,17 @@ IF (CMAKE_CXX_COMPILER_ID STREQUAL "SunP ADD_DEFINITIONS("-library=stlport4") ENDIF() -# Add tests (link them with sql library) -SET(TESTS dbug sql_list mdl mdl_mytap my_regex thread_utils) +# Add tests (link them with gunit library) +SET(TESTS + bounded_queue + dbug + mdl + mdl_mytap + my_regex + sql_list + thread_utils + ) + FOREACH(test ${TESTS}) ADD_EXECUTABLE(${test}-t ${test}-t.cc) TARGET_LINK_LIBRARIES(${test}-t gunit sqlgunitlib strings dbug regex) === added file 'unittest/gunit/bounded_queue-t.cc' --- a/unittest/gunit/bounded_queue-t.cc 1970-01-01 00:00:00 +0000 +++ b/unittest/gunit/bounded_queue-t.cc 2010-11-24 13:24:14 +0000 @@ -0,0 +1,404 @@ +/* Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ + +// First include (the generated) my_config.h, to get correct platform defines, +// then gtest.h (before any other MySQL headers), to avoid min() macros etc ... +#include "my_config.h" +#include +#include +#include + +#include "bounded_queue.h" +#include "my_sys.h" + +namespace { + +const int num_elements= 14; + +// A simple helper function to determine array size. +template +int array_size(const T (&)[size]) +{ + return size; +} + + +/* + Elements to be sorted by tests below. + We put some data in front of 'val' to verify (when debugging) + that all the reinterpret_casts involved when using QUEUE are correct. +*/ +struct Test_element +{ + Test_element() { *this= -1; } + Test_element(int i) { *this= i; } + + Test_element &operator=(int i) + { + val= i; + snprintf(text, array_size(text), "%4d", i); + return *this; + } + + char text[8]; // Some data. + int val; // The value we use for generating the key. +}; + + +/* + The key, which is actually sorted by queue_xxx() functions. + We sort on the key only. + */ +struct Test_key +{ + Test_key() : element(NULL), key(-1) {} + + Test_element *element; // The actual data element. + int key; // The generated key for the data element. +}; + + +/* + Comparison function for Test_key objects. + */ +int test_key_compare(size_t *cmp_arg, Test_key **a, Test_key **b) +{ + EXPECT_EQ(*cmp_arg, sizeof(int)); + + int a_num= (*a)->key; + int b_num= (*b)->key; + + if (a_num > b_num) + return +1; + if (a_num < b_num) + return -1; + return 0; +} + + +/* + Generates a Test_key for a given Test_element. + */ +void test_keymaker(Sort_param *sp, Test_key *key, Test_element *element) +{ + key->element= element; + key->key= element->val; +} + + +/* + A struct to wrap the actual keys, and an array of pointers to the keys. + */ +template +struct Key_container +{ + Key_container() + { + for (int ix= 0; ix <= sz; ++ix) + key_ptrs[ix]= &key_data[ix]; + } + + Key_type *key_ptrs[sz+1]; + Key_type key_data[sz+1]; +}; + + +class BoundedQueueTest : public ::testing::Test +{ +protected: + BoundedQueueTest() : m_key_size(sizeof(int)) + { + } + + virtual void SetUp() + { + int ix; + for (ix=0; ix < array_size(m_test_data); ++ix) + m_test_data[ix]= ix; + std::random_shuffle(&m_test_data[0], &m_test_data[array_size(m_test_data)]); + } + + // Key pointers and data, used by the queue_xxx() functions. + Key_container m_keys; + + // Some random intput data, to be sorted. + Test_element m_test_data[num_elements]; + + size_t m_key_size; + Bounded_queue m_queue; +private: + GTEST_DISALLOW_COPY_AND_ASSIGN_(BoundedQueueTest); +}; + + +// Google Test recommends DeathTest suffix for classes used in death tests. +typedef BoundedQueueTest BoundedQueueDeathTest; + +#if !defined(DBUG_OFF) +/* + Verifies that we DBUG_ASSERT if trying to push to an un-initialized queue. + */ +TEST_F(BoundedQueueDeathTest, die_if_not_initialized) +{ + ::testing::FLAGS_gtest_death_test_style = "threadsafe"; + Test_element foo= 1; + EXPECT_DEATH_IF_SUPPORTED(m_queue.push(&foo), + ".*Assertion .*is_initialized.*"); +} +#endif // !defined(DBUG_OFF) + + +/* + Verifies that construct, initialize, destroy works. + */ +TEST_F(BoundedQueueTest, construct_and_destruct) +{ + EXPECT_EQ(0, m_queue.init(num_elements/2, 0, true, + test_key_compare, + m_key_size, + &test_keymaker, NULL, m_keys.key_ptrs)); +} + + +/* + Verifies that we reject too large queues. + */ +TEST_F(BoundedQueueTest, too_many_elements) +{ + EXPECT_EQ(1, m_queue.init(UINT_MAX, 0, true, + test_key_compare, + m_key_size, + &test_keymaker, NULL, m_keys.key_ptrs)); + EXPECT_EQ(1, m_queue.init(UINT_MAX - 1, 0, true, + test_key_compare, + m_key_size, + &test_keymaker, NULL, m_keys.key_ptrs)); +} + + +/* + Verifies that push and bounded size works, and that pop() gives sorted order. + */ +TEST_F(BoundedQueueTest, push_and_pop) +{ + EXPECT_EQ(0, m_queue.init(num_elements/2, 0, true, test_key_compare, + m_key_size, + &test_keymaker, NULL, m_keys.key_ptrs)); + for (int ix= 0; ix < array_size(m_test_data); ++ix) + { + m_queue.push(&m_test_data[ix]); + } + int expected_key_val= m_queue.num_elements() - 2; + while (m_queue.num_elements() > 0) + { + Test_key **top= m_queue.pop(); + int key_val= (*top)->key; + EXPECT_EQ(expected_key_val, key_val); + Test_element *element= (*top)->element; + EXPECT_EQ(expected_key_val, element->val); + --expected_key_val; + } +} + + +/* + Verifies that push, with bounded size, followed by sort() works. + */ +TEST_F(BoundedQueueTest, insert_and_sort) +{ + EXPECT_EQ(0, m_queue.init(num_elements/2, 0, true, test_key_compare, + m_key_size, + &test_keymaker, NULL, m_keys.key_ptrs)); + for (int ix= 0; ix < array_size(m_test_data); ++ix) + { + m_queue.push(&m_test_data[ix]); + } + + uchar *base= (uchar*) &m_keys.key_ptrs[0]; + uint items= m_queue.num_elements(); + size_t size= sizeof(Test_key); + // We sort our keys as strings, so erase all the element pointers first. + for (int ii= 0; ii < array_size(m_keys.key_data); ++ii) + m_keys.key_data[ii].element= NULL; + + my_string_ptr_sort(base, items, size); + for (int ii= 0; ii < num_elements/2; ++ii) + { + Test_key *sorted_key= m_keys.key_ptrs[ii]; + EXPECT_EQ(ii, sorted_key->key); + } +} + + +/* + A test of the function get_merge_many_buffs_cost_fast() + */ +TEST(CostEstimationTest, merge_many_buff) +{ + ha_rows num_rows= 512; + ulong num_keys= 100; + ulong row_lenght= 100; + double prev_cost= 0.0; + while (num_rows <= MAX_FILE_SIZE/4) + { + double merge_cost= + get_merge_many_buffs_cost_fast(num_rows, num_keys, row_lenght); + EXPECT_LT(0.0, merge_cost); + EXPECT_LT(prev_cost, merge_cost); + num_rows*= 2; + prev_cost= merge_cost; + } +} + + +/* + Comparison function for integers. + */ +int int_ptr_compare(size_t *cmp_arg, int **a, int **b) +{ + EXPECT_EQ(*cmp_arg, sizeof(int)); + + int a_num= **a; + int b_num= **b; + + if (a_num > b_num) + return +1; + if (a_num < b_num) + return -1; + return 0; +} + + +/* + Generates an integer key for a given integer element. + */ +void int_keymaker(Sort_param *sp, int *to, int *from) +{ + memcpy(to, from, sizeof(int)); +} + + +/* + Some basic performance testing, to compute the overhead of Bounded_queue. + Run the with 'bounded_queue-t --disable-tap-output' to see the + millisecond output from Google Test. + */ +const int num_rows= 10000; +const int row_limit= 100; +const int num_iterations= 1000; + +class PerfTestSmall : public ::testing::Test +{ +public: + /* + The extra overhead of malloc/free should be part of the measurement, + so we do not define the key container as a member here. + */ + typedef Key_container Container; + enum { limit= row_limit }; +}; + +class PerfTestLarge : public ::testing::Test +{ +public: + /* + The extra overhead of malloc/free should be part of the measurement, + so we do not define the key container as a member here. + */ + typedef Key_container Container; + enum { limit= num_rows }; +}; + + +template +void insert_and_sort() +{ + typedef Key_container Container; + for (int it= 0; it < num_iterations; ++it) + { + Container *keys= new Container; + srand(0); + Bounded_queue queue; + EXPECT_EQ(0, queue.init(limit, 0, true, int_ptr_compare, + sizeof(int), &int_keymaker, NULL, keys->key_ptrs)); + for (int ix= 0; ix < limit; ++ix) + { + int data= rand(); + queue.push(&data); + } + my_string_ptr_sort((uchar*) &keys->key_ptrs[0], + queue.num_elements(), sizeof(int)); + delete keys; + } +} + + +/* + Test with Bounded_queue size == . + */ +TEST_F(PerfTestSmall, insert_and_sort) +{ + insert_and_sort(); +} + + +/* + Test with Bounded_queue size == + */ +TEST_F(PerfTestLarge, insert_and_sort) +{ + insert_and_sort(); +} + + +/* + Test without bounded queue, i.e. insert keys into array, and sort it. + */ +TEST_F(PerfTestLarge, without_queue) +{ + for (int it= 0; it < num_iterations; ++it) + { + Container *keys= new Container; + srand(0); + for (int ix= 0; ix < limit; ++ix) + { + int data= rand(); + keys->key_data[ix]= data; + } + my_string_ptr_sort((uchar*) &keys->key_ptrs[0], limit, sizeof(int)); + delete keys; + } +} + + +/* + Computes the overhead of setting up sort arrays, and rand() calls. + */ +TEST_F(PerfTestLarge, no_sorting) +{ + for (int it= 0; it < num_iterations; ++it) + { + Container *keys= new Container; + srand(0); + for (int ix= 0; ix < limit; ++ix) + { + int data= rand(); + keys->key_data[ix]= data; + } + delete keys; + } +} + +} // namespace --===============6439206237089482492== MIME-Version: 1.0 Content-Type: text/bzr-bundle; charset="us-ascii"; name="bzr/tor.didriksen@stripped" Content-Transfer-Encoding: 7bit Content-Disposition: inline # Bazaar merge directive format 2 (Bazaar 0.90) # revision_id: tor.didriksen@stripped\ # aitmqw9i0vg7p7fg # target_branch: file:///export/home/didrik/repo/next-mr-opt-team-\ # wl1393-merge/ # testament_sha1: 4b305b17f391dda695d1eb18e6650fca6d675447 # timestamp: 2010-11-24 14:24:22 +0100 # base_revision_id: tor.didriksen@stripped\ # rpgit95xb2sotnfk # # Begin bundle IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWfuMr/oASMp/gH//e+37//// /////r////9gZt4D7xM+e8tn1ezHee9X0D7vlXHe56qfH2vuc9u8qhh160HvRh9Z2t65Vds2DNti r618DgfXe8N76w9V2vvLx6z3XwPd8VsvuqduvS+Pvs9lVu77b59eTvfYu3rrNd17e57nOguc+97m oPO7msnT73Xz2gdr73nQL2UDau4B3btgHOTa+d97vbe9pJfNIdSSbsNdm6fW9vX3YekdvXL6drKH Wnnw7vC5yzovO6vbKu+SPm959jH2x9WNt7vueieaeXdTrrOxRuuudnOKMY0qldtO2absdee0q6wJ p6Oq6akxGpCbA7t4AS9uortkYNUw97dsHqes7ZTtjpSvdhywkiIAAQAEyBMTRkjBFT/UwBGlPRNA 2pobUPU0PKDR6R6mEoQGgQgImUzSepNJ+hR6mIAyAAGgAAAGjQAAMIIQhBMgnpDRlT2lM0ZG0ptT 1DQ00DR6mmhoANBoBoABJpRECNCNJ5U2AozCI9GQmQ0J5TCaZGmPVPU/URoGmajIyAAiSIEAIJhJ tAIGjQymaAjU9Ej0wptEPTQ1HlNpihoB6ECpJCempoIATTKMgmk9NT8pqbRNqMjQ9QAPSGgAaAAA Gnl9pU9Az0QXdABhEfhIif8oogFv4caMclYrEGESMRJEIwUjBSMFQigDeH+RkSk+NXBWJGLCBGCR iRiSQQcILYG8SrgsBdAWgX5BQoUPUKFCh6xChD7whQh8rT8zTo06ZiugIRgxgkYRIMYqlNwJQQLB QaK0AwIg6K0qQIKYLGCxgsYLGCxuSS5CpSVECigQgAiADoyAFpQ5enp6enp6dAkWCRqQVpacunp6 enp6cgkUCRqVrUaiZcOnb09PT04JknU6enp6dvD09PTZME6nT0LMLMLMLLrNVmFmFkWGGTCzCzCz CzCzCzVZhZhZQoYWYWYWYWaLS6LS6LS6LS6LS6LS7d/s4cCbDbmkgpGKbhEzzCJR/L/TfzfTiNxq IS1NFVf1bKedMu9n2D+DCwEOSMvB1FRUdOrSZ3JXQEXFDqTAIH/qfa+R+/1ZOwQNlNMdjhx02xfT 8HRg2DH/5gVH114ayzaZtjvHg0hCRt5oxay93g4ix4ubPXLafjv8f4pj3u2Peyd0o+7Dhgce0/cW bDEu/J7/4+cNY86wouBjtYFJNfc2XXHMdIwiDz/krbA6vV+Tux1/+/5cf4y8ONHP/1T/LZ/4pI8e yrri7dE73dfZDU2l+hgaGvi2zn/TG/Q9O7ye3u9jfdKjPFumEVYmW5nsctg6HSk0/T4x5YnEwIgM uZzt/vUIVhjsYX4oMIwKqM8axNxB7EOehekLHmfRD8k5hkL1pHe4A4X/Mjq9M6Q1lAMZVBV3RORf 9kvxWZ7b8rMedaVl3YjNY2M56x0vCGE1k7sfvNzOF0cpClwqgdSgC47+eR0Wfq6fO0DGxiGnmSZq 3jvSs0qrrX1vesubWWBRcJTuQFjMOVGEDx1RIIboKbIDz48LIcouTFy7oDrvuB9hmJBaMmz6T8rZ jU3uj5MjgKUSOw9jxoet+j3/ZHBx3PvjsPMcgwORZ8izbkhJ116zAuBamHajRrSHDzpIKQJvZZRV CRPz+DzvL6OmDCofueA2FNCle7NA9+Y3YhAyXjD3rGHRh1SyysXIEB5ygMpFSvz+s94/ItK+jwt7 oOphpQVW6P/5Hmce3rHTqDWbO2zfnI8c4XdIdCSKZxAU2pRCa54w9jAvXwf1dj3+65mKXKtX2gap APhMS3xODLXJ5WYuJmaTqDWCQZyUNcmqEen1Pn0WGihIJG56sdsTzndXz8/tkgRCTU5EtYtQBkBZ DyoanwtzIxaIsiybJs8HVHBSFmzgARIISEgCooFYGZM3Mve99WhjJGAU6qALAakNSGjo4mzZFkWT ZNnRukaNGwIgSQ5EENgKwK3FYKzzzzxdNYvkYsGQzhiGJibpulkWRZNk2dGxJk3FqVKtWtKZmdWB gnEaYAGgBJAogaOjdmyLIsmybOjYkybi1sRTpYWFspmZ2x2ckkDo4yWFfGBsGjwuFhYWVwuFJkCW NpGkdLS0rWVlaTAcDUjSOsvOniXqnqnqnqmgJkIQJ09Iah6l6p5p6p6p6poS0YCY1D0hqXqXoU9C noU9CnOg899hWVhlFVlRDMMZSDrTLQyy1zedszet51Jk4nsOyuWzSrtE7tLajOsp/nklQd8AqA9k UkEQdDiZpKQ5lUOXoNNHWcnRjAtTn20TO5z+3Gg4o2mggnvFAM86ZNzk27KXVw6Ky5VuPG1vc28O GGZjXfKG/mEtgbTFR6YjtgNpDfUsi8zCqwFICyHY6bCTCdSVN2uUC8P33b68KGoJhEzID73aUYOz jusb2t9rRDoVT9qr6ATu2ylVKqxDx34znJq3VvGotzcu3i8Whi8xi7jnio2W1tajaMYE1mtPbFrU G1ttFzs8DZVti9TgVnZicCnWLjTp9Y6qxdzESUZXzQx7M/Tano0FzaTX1BIyUZmbWi+vKAx3jKCx KeCPb6ueRLTGx8BRVSqVVU37LJ5esUCLZt2Wnn+Q9J8R5MM8s+sIO+yAi7CCKARFfRBSQXgRFTAi Hp/l9dt8UwhtgdEkA1QUE0ZVk4MM/V1wasNXCdpA4ILVWsml6WmVG8qWeON8cHGB9EUfhiAHCESJ Dd8WDCRQ2IQ2MMSHu3kTArFWRDVSVBPWROz+9vZQhFDmglQIMCIPcTrjDkcsh0OMFSeKWFRmWNCx CAIJwZ3GcyQ0dEIs4oFjJDKQAnzNLdxb4b6N9icGSZlW5vFDg0Cr5i/gQFxvhxMhjRGMvvmpvRdK OzFLfBjeHLGuV8GzpTJfwzVxTaWJ6HOwYLrnmRjbOoxR9EuIXxD+TUwfQkT9rwUab4cuynHChvUN JL2kBKHYk2AJ4vKSSmPI3elxbfPi/7d0OpGIgAkEgTGfZZdjal5Th0cm4hSvIEGDXpN+/C0h/Mr6 t0NoiJSQCUQXHvogN9wl7hkVrmRVUu591SsZUN5pqLpanp/k54fKiBJ6iEZzQMh98xWxD97IO32l 1dBI+bEzSMHX6OPS0YzsGrxBU2kAOUjRm9iLnJYy0fXQc2+/UUzmDlUExThIHFUPPAm0Ic4QZILF BVIpBQWKAoLIoKKooKCyCiyISKfBqHb3zvgG/fqaxgRAliKYf/kEvKrR7vi/x+OuMrfGegRrrlpe /+8OkNvZj4ZfOfv0MzOXQF9nJsdowFQVSAQXvwwd6Mdjq0YVBLIyv3nVRl45Z3UaYuLm63QxGRG6 w64vgCw9Ph5G87W8AVji6GUZ2sLU6xEDdZQwjmavVHhbTfLl1yAY1al1zZmhZMYoGLpo+x2CEr7+ 9GDfIrDiQ2WHz9Vx1oRp31MwoRjqd9c5nGIvFXD7O3oReeXE+948zTm4CjaZoCIjaXOzZWLgN8ab tNWVLNqOKzZTomgkd5asjeoWFl6vGnpcplDJR2vWZASGyAzbAtShjbYlDWsd3njPHNnM4gVu5rUB 06QEeBXUOV9NueaWyKtjZYbSvdiukvNVpJDUvKSdPSwqWMNCI1MLdUoWE1CrZq0njLP0e34zpfNx hDNyXGz8F6RlTTJtaWhQZpfGUNkw7scG0hTOxAdu56GixWN6Ja4LSxCUorlvSD2mK+UDoYl4qcRz l+ZNXPT8akkIl6VZdLa9tOB6JJZIJpniTWHvo1kgfcu9QRllLKmZLQWsA9VubQPFBMDFpi8Iq5U6 BBz7x1BBN4QFdwJBXb9GOyXp2KwP/KDEuuvQfT6zDioYCSMhU0lsFAiYCPElqkrZhiYZeaGDpD2S bkAYk6WCwohET50AZhzmcJ9OlEOpBFfoK1nuW+eMXZyMMWJtPPNwoCqkeiw9WrS/MD8IRbdm3X47 J0gboA5Awgxg1TGOPc4Xr5Ks6qXYtwmjE959xh2piRbvCnc6DSffJ7SzKkXoEjeCPwCw6MbewQaf sD+JZZ697rXf0ObbhSdR4Pstcob3qmEOyRZRjA4hxDwDogFpapq/avWSMiKYZ63KmDjCC78JIFI4 NmogA/fygpo5cgvDIYlRku0QFyr6hi2VNhxgtfIfls2p8jURIQ6qZLL6inmcuCaEpFuCqybx/ErR Pl0v6OrWoKtjdHjhlm2oR6eG3nPKmrYS8oTPB2Ydahq8MQK9AC+Hu6E3l9wMN5h9JUoqpeTKG9rc vsGCZ4Zej9BiQqMyTvNT6IeS4tAUhXnI9sam6ngFZqcDIw6eIKSWsWCNfDRvWEF97/qpEIKRvzhz RbfdGyWUY9NzUYSHFpfOi0hPXlapCfKuU7VGgjO/teecJQanx3dPtw7n/P11HcdxebGWN7QchUOs 8DWQNenr++XQy0PpgynjBQrhrjIVsz9+3hRbN41qHPCSkr2TD9T5pINnaS1u+X2XllkJjFfq9RVL zwhKX6B5JZc7Kw/ljGPoa2tFYkBV6w4COIyzZDIjNJLDIpRnSLEPUccuDlQ2+sk1tXKyBPajE263 WvojZmotlaBBrG2u90IY5gekYojFCBUufjMRkpssJrEIkK9unOa2G4+3Dp4Z50ZKdM7PKGoxiy0Z RtaVUHInaMNlxAkwtRU6FeLWL1qOO2/iDaShNsMejx+jmB1bG38/5KxNroOVHJWYnAmh03GhkBOw E833rf7+vVs59sxQVBkPsyIT2dnf4PI0/Bsa0WlFeNrxuLsNY+TyX40PtXJ8gngMe7EGPxwUPQwE W7AZgFpNA3XpcXVFhRUXrr0nMbYXrG3psUTuOttZwlcpxYFQd9t7bJZ0wct1Ip2pOY23eUhpU4Gu SaiwlHjkR2p9TFI+bcaxjlzaMf1suyeZpDyurmUsuZqeDSQzSoePuX6SED3zehMzWVlnbO5Oi3HV BDQUIxYz59RpYZyrXlOzzRIFGkJe2Sq0ZjPEPRWPMbg9nxNJoUN85WAvbkh0sV5LuOPiBGrEkYWU ZayjM1udUMps3g1+ctGssBlI34oF14WqzS1iWN/vY2l0GTojZr0Tn9vMsP3WBVqsqLKs6eHnUj93 k9CTzEJWN9MqrT1zxM+F7GB07sTkFBso0bq5fAicWiQk+OOcAVtMTIkiFAyMjE0RcmBUBHB+g1Uo ZclfvI5y1b4FAJn5mRslKR8JZ4NdKmvk9yN86l6rjp1rrsmlOUjDE8M517vLLm1lyhAdoSvBNNYu pAqzu27+y6YybVrH98Z642Xc7SJn0d1jtSg6epOpoXvnpUcqtOx5OOvEGuwUhupJe0dchocLl28Z 7TXhsxyT15YLXeorAnnC/Huk8FnvcWRKaxGv56HwlexXriSp8wtF52l5iCQrVN97/VXjFK6NyCov HjbB7eOseK9MeG+pC7bQT7KP51ctNHW7EeLmpMwy+aMItC/yoLEgFKReJuvy7skZvAJwFxwxG3WY Hti0cm/saiy4pVvBW7zUzPeGV5ajymVg2Nksxpa0VJhS+fQWJ8lPZPrs6w8O2ZWt/vQhHsD9ghMG AhiAIjdoa6B4Yu3GMKeMsduD141JrtzGWrOeojQZ6NTzSR0PpnNnIQKV7WE2loJFbIWusLvoCN2z g9CBy6/DpeL5T52H2b3bBTDRf671oUoumWEPKMFJ8aVsxZtQzzwmBo2x+FL0pWWXWUOiTNXLDWG8 EfAD0gctYzDAjTXOQTaSmqa+T09olJVqmgF0rzUNheB3Lyb4xdfYjwcR1eMZg4pytueb3XLjEWGt c4h2T5cIQRAHxjk4CBaAaCRIQSAVovSKcVB8I6vUNbdnXeBtyHxOQunvqiO6Qjo0i+4UTWYESJsK jPUT+QF3zrVzNU+nY/QDMeHHlKGB7M9IEvkJEw03EzHmqUMeV9bWODc1sEBBloaMJejdIKl0+SeT me4Ynt3VYbyuhVwGrWNJghR5uCal6tvLzZ2zegsBVhOO2/VPTZKfMlx4IL5vr4ef5xf7ofhFiEkk Hh+uM0HkbWZbvzlko3V84kTk9ez7vV1df7W3l9xMIhHvcQYCC+D70oNcqYpFquxwpp+TuILF+f+V 9mObps2u1dE1EjyFL5S7zvfV5fd8I9D/bkGIMDFFFFFFCiiiiiiiijgdJyOo908jpOw3Fyi5cuXL lzQuXLFy5cuXMy5cuZFy5cuZFy5cuZly5cuXLly5cuXLFy5cuXNC5couXLly5c3FxcuXLly5cucd T8v9nt96T1WtPV4f2/UD6yCgoKCgoIgKEYhFAUFCRiERAIoQRCKEFBQUAUAUFBQUFCCgoSKAKEFA UBQgoDw71J+TyhYbIyVBgxSlIMWDQKMCCgjFIRFwCn3QGVWkWJRRoDAQED3CbzIsBhBCNg+yn8Ck QjBdIEtr+29/4UNBFPTSxBxzQ9G85/rfyGTFNoGj5xngPmpOMfH2OhhDQb1Fx517a3Tfk8o13h4Y mytG/zqIM1lPi7+yTf6xLQQHIdSHOHApuDAGX49MfJjGX8+1gNGsSLYqbmSOtucn3Fe7Xi2s4f6/ Y4TU+A8rPI9CjMoKKDvKKLFgooiigooiigooiigoolFFFBRRFFBRRFFBRRFFAYGBT/4ME05LuKiq XUz4Mfw+mIcMBaTX8mdU5xnYbNxwz+qZTeRO9KgWCPXracvEVy+yuw8pQQRMhcSafHKuyXIBTFUN U6zTCjes4IhuiKbqJAhIfu2YW/T0lws9MNk7j/bTqCM80ws82VZQDnxx/jH52vZNM5nOs2SdFmyb Axb/zNHsuv++Ukm6ub6+d1EzXXLfYSNvajnPP3uSTcmRuG/uYNB1u8Z/qxhxfGMZSD9cLIcH0jQq +d/t4vLaFEGbWp8x+qMSR5/w77Ik92MJ+c2EftarXUv8lB8zac+eb7GMipySZ5hrdlsBHx+pyHRT vtwhn9xA90dEgzR88fgvj2kfkX1jk1tD7fPW2MTzjvyrHf2GveX3PiwIwvtGkSTnskcqqE6D+xrz XkmqWMWZ2jJOxvze6zONbKOeyxqt/fTuWrzFDj0r3LyNu+RhGRs/4su/joDnW10Sb4ipgN9koJA5 Lb4Uk0oACOfBvyzys17BqapQUusYM72x8dUzSlRukPOImMVL+HK9JWWaUTrBaMOYqYMhVjuwfNfL p2rQ0N1sHDY9lRPhXp+GfVLOENKVgy+Tc2VsQaqy7bVAiJBjpLvhlWchS1K4pwHyONp5j8Z1AjLY llIKEoMn9BQISjG1IV3QKiY4eruTLChxBnCyH7Ige3A9cZHP9kpQLkJB8/x/FzazabsumcrjIUJT FFIZSoeWmfhyQlGMZBFIgGEBHcLmSDxoa6o9kgKXOOv5k0JRhi05xgyFA3ae/rntZaOj00cOVMG6 4vb6aoNyoumgTSErdn7LLJEPNfhFG53ClhhvcZLCJbRK1PhIsrxyaSHdlLRN4r+r5W4ZAkEsycTO V9WB3zxXPxkvKahGBrUQvtR8VIfx/Ae46zb1mbBfz0QILuyxmFUqHmUxjtp1YW0NduadiFEIFJ1w gSfCF0x0XHXydvfyk+ERHrpRGpKlLSFIqUEoNrOQocCIHfvB73IY7jcnDHT07OPvbdsoni8fTwjz 71khueKePPe8aFckTDPOe6yRRfc0Z+/WbZbq+0Z6rm7qRyn5XlTIsRzA10x59tycj4Fv1hNDQb10 kVmKkV1QY8umtzXWlJ9cxmm4VBQUPIPM9h9J9J9J90+kuYMFjBgwYMGDBuMGDBkYMGDBgwaGDBgw ZmDBgwYMzBgwYMGhgwYMGRgwYMGDBuMGDBYwYMGDBgwXMGCjBgwYMGDBg1MDBgwYMGDBgwYPZ6zy AjbY+OzbN0Qf0MTCA9LkUNOYjh7RkmXmOnZj6tsCBM69fr/98u8KYn3R822TRvGMz9sEDocm5S84 Mmj7hgWDBsm8bt2NgENbjl1nZT40e+4Pdh5zSEPKHg8nk4QZcoqi12WTzefIDvQTJqh8EdJL9AQa dYFwsBczPJl1bxR53ooafIhs7jQQMgruKo4GB3caGDyj1ECYxZ2tg7itgYo1gB5uvtp82bteHYWb cNzZ67vB2I3V0LJm7e0clcplsNM+bJVKedUyszT2bYqCf0XRj4TSjc9GeNlNFDMZD2hjdrZtCpqB CURkeqBi7HllwHj7ESL7rkcIV91bwOFvIHrmoFd8PWgqqMjCq7nkZ+U1VMcNqqdT1zSMPTSbCXo6 +tTIdfr/uhw50HF31vByy+5huTdRxOgh7msLDta9xzkomqSkZiMoW1jaaYkaSkgK9Yq5nxWdxvCH gAoIBBm87ScDfsKmOUtlYFnXjBhPXRpPJ0JsgYlne2CliQMAoCQ/HkF3HBbMoEt9KvIgsJD7dBIs E9ywqMUPjnnkDIYsp3f1/sK6amKaL++ybIP67c01x8jPnEM9Yc08L5O7zYIB7qj4LmInuUz5kksp pegeSiKnILvzJKvXqnC+EV88zHDyaskG/my7wCLyBieMYnMsR1jI7NDeZ5HmHmUgMVpdokFcaRUS ugICZAtECi7QFogWNlAWiBY2UpaKa6kbVI2oVUxQvtssjZm2aTfkltmedcZ2gJntp2RTKG2Kkl4B r267GMbQz1UJlCoF464LpEvFDVAqNRNUBbwNooKYVRU3JViMjz467aOlRvMHE4G44BUMh9Aawuw1 jART8NZGQgECSSSCTiyoChAJBIMhkMhkMhkNzF8Gc5znMUVFWISgyKiylLOc5rVIoIKgOjpM8iYk tyBAvFAYmghRkBgmxUhTmNhwybHSbjA4xcYxERERERAiIbe8zM5iInjHG8g6Wc5ZOlETrWneVa1V EeDQi7u7yrWoDwhCLu7vJ3d4u7u8Xd3eTu7wd3d3m7uzu7u70d1d3d3d6xeqM7xgmLZRLgMAAwRa ag42AA0s+ktrI4XRZgrIc5H2YMHRoiIhkQYIghig+hoRkCzUhh/KNh1CgaBoDQKEGDBgx04QiaBd GzESzoNeVrEhbUUUOA5DkNmzZs2kqdR0yBCkUSz/KizJk4SmVimTGRp6UnsH5jNnJ1ORqDmg6Kwc qrWWtvOYtpNVMzMtNOIx2CrEb0NaCyuegQMp3BnYgjRYNiXrLawroUQ3IsLGFUEKo5wZrcQHuxdF qqIpiSLy6vJkTim/IqumDKYTJoalMCZCmWOcl7gQgWbt1khEPyxf9A5HIzKN3E4m45zEvGMCJeRJ JLZy5UDGrRWfRMvsv9okL4RFxVgJkFBQUFDvsFlkZIiVhBYQYChBBLAyAs2MgdTU41ObKc5uOcNo 7ER3zg48Kv5xrvXH0Uk40mKHJFolJKjmWiWjawtGl+W29yb0NNNfgc1FmhsgFAC30uKS1Q2cHoiD LamQuBc5GMcXwBFIqjYdb7bMyWUWKRMjNZBYyQA1GEC6221sUtdwawiEwZgyDEMQyCsMRJWm5rWv ZfPB8gS5jzBnIBiGAYBgGAYBgdJ0nq5IMb5qdqdzi6ObJ0LLKWRg8CegbrE3/OjgzSxHPwj7JynI 3y++sVlWiQijl3UWUuBia5S5V0zp5dPTv6f4GzaipuxG8s4MKDA0oE4XEDhTM4lKwzExgm88MkkO t2GkdypAyrLX6pKAJ76pMSxkUY5HI3Bc2AsS2/mDnDJwzwe8S42MnU8TCrUl0ybWFHuunLOTaNly LUtQaDmuN5twsceVk2JHNNiZpwAXO13QOAWy2G9w32y3aXcm4oJC6LBFIiwOx2jC3ktbN2689l7s 1et4LV5RdK9Czg3OiM4qcY4xpHYSHTLZq6zsL+U4buHaQ5O0UeRsxmJQ01GGvn5Fno/UPeXmNpsO CxDKtKKWKUTIEgtkIU4YXhkEgkK4jXiS0nOo687bqK0SExj9HTy+oMbbFzY6l1LyW4chA7qIEqy5 jBLQcgsXJCbeDdVVNMaOiMqRO9bZDiwOl2ObHi6ni8hDXFajmcQ4hWGdcS5YQSKxp2kxJIQu2HhS K9Xq9Vq9UsmwstDAMFNPMVXTirRJfKoCZPqlWSMViFKvFPQ2GTW4B6MQpMecIUKniR8yElz999Ys mktNkV+8V2DQSpKMF4Rmi4xihDuzGrTbtK52VUhDXP0t1jVkOoEMPohPQg3PwelweDbpdnZ65Iz8 WzsZPQye/jnS2sFNhcwMw9T3z3j36eH3z2qIQSCQ7opRFekSZSInAeT1N3uOx1zme8dMYx+R5vVJ ok5YHGFBVSJYFhTYGAowMQ2UAqbtu3btNprTHUOEUsamXiSGkc43mBG5fNlvTYhGpGExaVAD3DIo wEbGjaOrhkPMMnE0N5vOJzPo2BztX3/rS2ZDkfCczkcjkcjkcjkbGy0Nfl9mnYd875lU9jg7TACV g0p2BTMgyd0dRECgkbM0ErXzZq82bJ7HaAjajU6RNR17SyFhppChwpjamg9wg6eU3mDoBgaZ7uQc grByZilJW/vYXSxFsqI6iTKQGfOx8hQMhsocqBsEvjNmEvYgY3GGTBY0VDCAJlUQLVmZDIckilY/ NBEopKb2nCdKztthZWRwIL67zY3t2W9ImqIJsNUFBexz2BkrJNDC1TSQDQEdTwGg6Uz1IJ0KRcVM ZOPoNix0MBuA+9eOA4CVJHMmRTnpMkzunq4ZDkKDtYyGQZJ6TbodupY6rNgO2A5b+i3O2Q4AuYXg OAsTukpi56HBsdyZUMAV67aDQXlSsxkO3111j1Y6pUET4vS8FhDyR1t8+ieyd7z81mxR5MO9k8Wj J1LLtz6kqeJqNHuoOBpKjSQJiBYMehSEDyWdRX4qtBYvBdJ4qxdCEyt4517+1UKj+xfaplvW40m4 QB1GwQwMLGIQj1Ij7aiOBwMOw4nMHuB5A7jVhjjy86bENy5MApCLQlIUtO2yNls7bJnWhwOBdbaG RUZ1cXhZhrBGI5xjGdxE7uxc4UaRmqzpaUnJVsxYx3+aAOFw+AXDQYDQaDkfJ0mxsfGcDY2NjY2N k8pRU0xOlL08jdzhzjYxhlB4hDc7wyMWAZHCapjLrw1cOHDfuyc4m5iGuqQl6ffjba3vucYiYCs0 pRYFqhsE02EwJWCDpg57kUL7MIjqkFTT9PjL8LyOLvDeG3HA3jqGmzBRjkpw1nlNpLBz3XQaCyT5 CNUwVIJApuL9aw9x6nJbVDAUxTC04QF21ciczB7r6LFrmg0E9tk53LlhOeiuTMtrUjkMhJO74Lli qOce+mSc7I2AwGwkqbHfuRKr15Hl1GH1xVlK40GgpFCPYYmc1JVIwS1iHEbhcK6IokhRMxQpKRwd jrqsheQkCYvKjvW010FSFw3mRoLAzkZS4vImtQLyQmLis6k5tV6FJiuK2oXdwUqvWQKRVLvVJ2Lp VoJDuIPN3BRQqUSna9SRxZdrtczyNqHg1caCtTtXawcbNLZC1my2dt7t1u7bxDCoYwYJF42gTsWU nYKNGkYDKqg0pM1LxIEbreVZNNLwlakKSk+JBQJhQPQLhYHCw3n1m83m89ZsbzebzebzTCRKTCr7 7kh1yFwkOoE5KyCuuFtG1sYtLe5apEC2FIYcGkLYFN49t7KHgiGw1GOmM4BwC+uEeFJuIlCjoUud hRjS4EaI7q121FiAtgsEkT3nqeJT0OQs7F7rNVa4XCfM35lMntCHB7krkoGF5TFyGQbmJ0cTdAn8 E2SODuF8Pmrha9IWhKgo9oddF536jQdynvua4yov1YyWPiGIXnPwKdHIG6UzutSqvcLhSwm2U6Vy HxdjQ+h0o64DAaSFFO4qcCmypIho8imCl+MBgJ3NWuy0tu84c3N0vIdJ2QxjN6J3d/wPcT64rhcF baqVZE3lziw66cHB2tGrRm7Pq+62eMdzqTjn9cSJSWk53EF04RDXOrbXD0q9ToXeujvW71oacHnO 3mJN8kWemdEKKlTxepI7nod56D1gn3TQriAMFkCmWeAIgweIgwdojKAyhsNhRU4dDB2bgjQal1tB qY41G20PNXGKY0M3VYKMs51lJkHaELqFgsEQiHgFgcKhYHMGDB6zeYMGDBuhrty5SWxxNjRxXStX Vqy1rWrZW4qkoK3tOXAxUtw+mxtZOA4CaO/ycb1Wvl5wMccJbY2cNgjyxLjoEIIsBIiNgULF5nmP iy0aXN2yGQxF8t0ObnmgikieTNwuEpRORowirBNG6djqVxsL30Gg1OPcxnJ9PpS/sVcBgKSrYlZD mJ4jw8UTnE+CWzNeeVuGgnrZeyyVB8DkiljFQsD7T3JeVsdysA0ePUkfC+xydtLprAvBzWhE0mJd YYDGJkUSyqZgaY3Gc8Fd1tDsarNGHBqdr6s1NG3omjfedK7un487uqWrguS5HFUizHJaI0+Sq4Kp aClW9SyBBmA2k5uW5CLHady9hxDvhtFzx144UOEdYVTrqnKstZQGghoUVgYQSXnTcLbL3e8LOZvD qVhuqlaUqShNmvYIhMIhEKh7gcKg4ODg4ODh7gsDg4OF6prRi2GyGAnSMmzTM85zkNpc6EVG9SE9 5bTeF4ScSFRJAaoXDiXk9RPKvHK4YCJRZCnkcDbCipyNHvSuZKu+lyGQnm+CsEWBXB0MkzgfJm11 N1NBoNV6mjAnIr7DYJFNeqzNbMaDQUgQ+NzbBjY5j5msdSYsGApzLEcW0YDg+pRH0Y3V31gNBVyG 3IoZ0kzoYM20PcMBG5CZroRElWSybo1AqE9yxgpsw8E8d9KIJtUJxqB0GKm5aZ4kTkZIExSVd89Z Uah7CwdXHivarw6js51KoXUb06FYuxaeC0LPEcRm3rvGTqecmp3ngkw+LLb3Ntspe5XCtFle9xQs KSSj18qLVbrekJLWQVlNru9L2aNITq9YTgspzjNVZmrLHhcKhUHCwOFQ8gsGAwYMGDBg9w3mDBia zilrTfLdHQ6MtK0Fwm6CEaz1rWq6eqVMaLCOMt5+RbZ1phdg2CbiYT6ycblcmCge023C2kiY2C09 g2CVfmzhT13JcS+VBKmSCnXlrQaCnWcdQRX5n0oHqlTATfnYLhO5eK70yTLB1tLamLBgHiTuJPKS LhKoVCN3FFXYXJYDzDdKFw76NtV0Ggrjoeb7onsmZIqRvnK4DAVnXxKXPAmXC9VsFglHQdV+RiWE g5ctL5IFI90h2cZdsfR0WbN8m7r4W7K319s+cib2JlOp62qnm0Yc5d2M1TV7ixq0dzVEqJzmsykI WlB2CQuwWJ0qcx3Kpd+0SFKqVQsHbOpN47HS6XS9UnpPfHee6k8M8NGbaVsClb775yFswFZ9GlnS SjaHvWsTGIl4FrE7TqJKs43WFZw8YhcLBUKhYLA4eoXB0HBwcHBwcPULA4PhSqbGwRhYyDhPJDZ4 arXWtW1YdFlllREVCIpepuVNiimMroNgelhvIc4hU8z2HIcyEjkt8hkJ4kXZN9yRYN5ODhKCCFDB gtbmULhjOAwErD7k3KdSRQsE4eqGd0262DQW0Z6DHc5ihAyTNjZSGXbkuAwFeZowc4lzspbawWCe xJNECgMTCYRoaNy51O4o5kqXOqnOXW9V0GgeMdjqUNgyjjnOMwvonMiYyKSkLyUJBiw9do5aZzQM cn0VWanZ8fJzYaLvQ28c/Xt6uPeOgdTqau52HgDsHkB0ES048oeUpiLBFwi4XGLYLuLMpVpQSlb7 6m8jNjO28ZezjVXWnaznVwMTnSLTwPFjqXjLm83GDBscDU4GpqampqampUPIHCQiVVA3Nw2xLIVC ZGOcvnOc1rQv2IXNBfjatQ2CkTYVDfXC8ETahkLBYPcgRno4J+MT2GChYON0J2z0jcNB6iQt5DwA 5nMsd+RU2QTZVrkMhedjtuQxCsDtcRLzIXC4TcughwfVE9Uk+c3iZERjAYCPI2PAYha1niWET0mX C4MghKHIlwfEQJTve8S4iS5RLhgJ9zncY3Ij4xaOESSokWHuFwnueg5sbmi14ymzZJRbc5EShA77 ECbG3skXFOVheZoumxYupgmNAkLhyQbPNXbBvF93AyaQZpCwkv+5wJPJyKw2Oku0Jfn62snCapUP o1aNOyQjMSK2E80JlM7a3B0wvwDAmHCCD0QDWrxUYECoWNDIIMggxjUReVSLskFkAvMBVmaBBoo4 psZ2b2jGzlaceZ3egEpqQmeID0e7969XpcM58PF+9jcw+LwYNvf2Q0Suv0t+NkVBM1Gd92mUhRN+ 6H7oEkXizI2u5xoc5YYCSgq+lYzidZ/vQOqpanTlEOvbpAT5Vi7DLFQPV1m6F18K2Tt+RvhckT8C LQNIIZH2/FPY9QPFnN9SPFcc2f58NqzCwlBRY1SBxxiVVos/wakobN+xnrlfW2BnWwU3s5MHmcbf a/x8Znj3zlMZQMg+Bs0YRoiwWaStYBRkPAaiek7Zn5NtAWZhIlbdRFQYva6+WQiLsZZNzka56Rba Kc+pnZbKdN3e/Xd3WzeAPa/nd7p5MOj4VTA0KqFetBosVvkSAwm2ZMID9QOdPt9XbHr+dNd+Oxa3 HHbirGc2Dwu7kE01Nl5M+jyaXpNZkmfUmFfs/cvQA9Jxb+rn1eSjz6ZGpsff9TtWaU6HWBNzEqzn 7lTgtVoJCkIJDIc8Brt+oXOs56UOzQciuXmhQEgEESkigkhFBVUiJzqUFlLERUGSArI3oE76lbdo QVfqKDkAxZ4/ghEsDfAK0XWFQUxtlwLBhhc7aMeNi2wV2mBlmP4FNkARvYZ+BeBvNfXNPWNIAFA/ lj7YNsqo1o2Mooy9T6X0t0P6VT9CvZ+T3X5TP9uKJpp/mHsbGmv+LLuLqf4iXL6mzrLJiJmP0bgD 6dVfy1jsdSMD5Q6FR4VUPy/R/Z4SayCzrSsQBRgqmCQ1n+nIcoHp/v/h+9uzsyAMkIaofjQYQf9Y Ju/eUHfROsQOB+cO15K8bfifkD4wzXVJoAat4iJoz2lCYO496jtn7btKc0P15OhuS9F+jrtVNol4 Mr6e/nGLTNzSlptDn7s6Z6wkaEz9vfbx7h0muS0dLKEmWvuudmb8XD+k9+Tn3WopPhDKaIKzFmdi xez4ctPKY1uYIG39wG7UCodgv/THFz98IU4n6jJebaCpzXjtdbuJpvEjRunWQoX3DcRMOuee+xtN icZOuanFZUi0kdEk61tRqOGoemESul4ejbS5uzYl77zUfWRfF6fx7UhA+ESeA2qwUo/jnqIWjPP1 neG7dVshShSaLSoBBTwmnT4vT/j/77NDaxqI+s/fvesTaUYIbPbK51AinuaqO48zSHTClfWCHc4B OGWcOKZSo0GmBh0Aa6pwlS6m7FMTpSISR1FILKlsQdZh7QqfBfQHmFToC3l17DgEExPTPXPVB4EP miVd/1FSEkaVoWfJbbj/v/hX7G3pkzMyE3NLPyCJp51QQeLKfV/1gEWF/C8MhMJGRuXPOkGHNIQF Q8JyQ5GOwAC8FkFsSXc8yKkt7sNcLcmBsNwp8IahD1AQ6VVcWAQdb7CkIYvzgl6W6m7pkv0u6Eka CsBkSbGJGMQPgUENLe/e/4jVVjMMD+cEjtQtjDrctLIEsDO5zunGwGWJXQQFbNpQqRgehDFxhDzU v5ouLhqUyb5ekfiseENojICVXtcA44cDFIr2vxRMt0kD0jimFIwzRojTkym0SewHn1gdsSCIIhEQ UUVYiDJAIBG3oR+AyWwnv+62QX2PLXQQVd2O8A1oa9wHM7Vu9/5xdq4mBaBv2O5cs0+GJ5OynAGJ N2sTou0zBkgB49anhB4qmh0ZZBZxaPuEy0GKidzKJAp4Olgl2gGM7EOgtjiFBaMxU3pM9JJY65IA 7AKNSGaq4OTmiulNFI9FlosxYazBuBww9Td5SxOHJxA+hWBASUBkOjSoK0pSlFKVOU4nepGxSKUJ SRQ6Hu/FkkNDQixp7iSONUZnekaOKjOMXA7ZsW1fHFD2T3sHgMHZcaRtkcF5sAPlhyp1+i+6MDR+ P1BsMdoUAealgYJ60pPCQidYCcQYECAkgkkhGId5sIdwqdZQheCtqnRTFPb7M8G1qw0nTk2/0+mh dk7tNqsJ7EAuxCYYvSPHjBAfSLOyD0VVT1kohGaYiphZmu/BXIacXHjjVKUhQ9tZXMAw4XNn7uv3 +PLO7PgKT8KBZX7iYx90lh5WeRCqzaz6kDTA97EO5wdithcnuhnQbNW9aA1N8VAGAdeoQeJpO11A PfBW+r4Q8Su1g3dhi5y3ucKHw0Ke87nezi8dI0yiGbOLC+eSJMnh3040VoSGYBOYDoHmaBA4MUtg Qs/EHKDMZPoH3vpQ7W0kUigv2K/DMwKHvTX0j8Ihfb/ghffmn/a4Zteb2+pHKKS5JBpS+EylZI6R a2neCDdVR9MgFnyqEX6rOQyH9Gm8t4LFLnfaW37VsDbuMnHDBGxz60pBd5u5X+9bZVbDLQx199+t J8UH9YT9E/rD+qrSL2h99A84xG3yvmsMxuJ+mBQxWIYpdgwwXTCWpKivksmIwCLpcxkRzsmDeRJj 2Iw5EzPnajhwZJu1QijEkrFN9WU1aEJCDjVSDuXY3wGy5EawNhN2rYb1xNHYZ4ECSFrHjsK4ECKk ANT6Q45OAWZwIOiE9W0K8ukQ4ElztYDOJQNJKFKJEScVmilFBEikwgkGVKl32YhJgJP1m7J/kfG6 ImmTAcucSGXciotIQqDah1d1FqW3d5JeEu5tskaqJxd2pHdfEdzto3JFbxcSZxgTZ8IceIWqqzIm u2rpiS8cMHFqlij+Q4E0ZVGdUQ1KUrGARGBCKUkC93TnwOWRkNOIMsVjZCODDgTCqsUGYoNo1FWw rWzZpOScxNeJmBNhw5UCyMLNwF0H52nKR1BoMSiWWOYcRhlDVdHEP6hPhacQopNAaoSQ2IHPl0DF hDnAfaqF49htQpjIRIO1Nduc4meIxzDD4xmBGmRKYNRJv/b0fgupGOhA/uNDjppppC6j0khMvldz keTJ4z+s3Pws3yODVT5ndyycH9jJqyCZEkcHJFNix2SZyKFjJAwSJFTYiSOh2VJ947ndIOxdhTCy nN+HEcW5S3FUeMlSe+bNTaN2gDvRaWEHzlCwhh+46z8P83jHOEDsc7bZ2CgeTXtiZI7jiUbS4/t/ hJ10H2/hf4tNxpdqwp7z1lllnm0eLnhO2c+rORKJPhbnY+kB7ut+CCHU/2Cj43mzfrxgGIMIMIIF VK9t93WeiO9D99u6s7SFGC+KLcfscZ5HuOr8ks8Ad+XRhZLUSp40pbJY0g7X3bhwzCj9JvGrogbi KsGKB0RQOSIWI0npCd6a9nll6z8lqCswCNEK9zsGu7WAMiTmAtqf5sA+UjiZd+C5XnAwsQ0Cd92g njio+OIRhr2CujiaKmC1FJKtLIdFSQ61PwWI4AdJoYp05uDmsH+ENuIeXjvJgBn+fdncYYb/EEmD qiQh2jdKAqjk681NIlbgPAEEZA3GGWs2k6IiOsSA7M2O+GIp17hiuRAKAoVgEChEfJmtjIRXt2Bj 7JfTHwmhrFAXJMwBYXpGcI2QH7t5cALmvenV6ZkBr/7fr1ndlr5K3ZHRH3H2sN74NKOGc7j3nzHE pmDmRPYZu4pJV4L6KCmomR0k5KWkpIdhMfEoFIhe2Uz8CPzq4yMTaVmcmNV/ZsE2ovNBIQPj82oq KMeuquJiWDDH0ObueHOdK7uxJPBqw3tWnGj4A9Dve/PDxdL0N7oeLQ9B1PnOv5X4HUJeEGSMgEYs gucCKENkQMSBgPxb+5FV+ChQ/wvqcB830s/9P5fVrpl8VoLaW8eJeJ+bs9Rxgdliw4cLCiCye2ig 2igeMQCqjGFqPRfkwZk8tPGMOUnXPBMAapFipFgD4z4OPbkk+VIgyAmiOBAJAjBwr2H00tnnat7b GgFIvcSL2nkeReea7fUcuPkWEITnpNh3nl5HqKBiVeZpvPWmMS4KhqiB3F9+wOSFcTEkmBISivNP FHQpVU6Vo/RosplFVml+h2OtOh5wji+qyZDvfX8G59iehf1epaLLSiyea7Qw+Tz3V5TWjMWbh8ls BSLrUM5YWFpiK2+m4Yg9UijEEapQKHySME61r3KwO69OOrePldnztzZgkaleczgfbTgKBdrIU8vB D4N3m4h0HJdAk7BUNdGr2dAUlnlvvfn36dDsNb+lqoG3eXA6J9qaS3nCzYwH8RTUIkchCFcvVZLK yKz7xEPX8/vWNvWHwH0Pf8B+J3+NhIyBIjIA5IOECrWqJ6k/VreM2EOklTIMXL7eNrXNtip5IVt9 IZqYlFzGkNRmiYc2kcYmDLDBpL4nVgBqqlXFBEITaDVWxCmAwGjMhSmYBCzqJ+P8vb69HKCACKUB DTHECYgQ2UPYSREsKxokBewieR7Sk7jEP7Rj1nVvwyuyq9hjcUkbRzgfB6PSeo1nVROght3tLqMj UZkLXyIL0qOASlheJGljZs0JCtKg1jlWQdUQorNA/zNNYr0gbKWGAWapVIEiSEWEiHeI8CzV4Opp 4yfF89SLSKkdkZp49TVvbNehxcD75OyWJmTwyYBdaF7xkZ2HYgTkKVjmKTwjlfVvLIrb5Ykt/3cT /mTX8TEngNLntrTEjxoB2SrnwTOBiD9L2G/fmWOp8L9r7BV1anwiPU1bplaZQ0DXQ2Ls+SsMluT5 KipQXsLCpHvnXtIKcuHYEnY9tB8TPcfN4FV5OR7vdix11UjjystoSRZlwjOu02rbKvgW5GkoF11V LirdZMdfr49vHriRwXmoLvhTMhmG57p5y1HnIOxl5YDEk7IjVUc4PKKwVZMQkWY8M0vK+krBLAkY heCW1mCwCRsJkgYTyvUK/v6vw4UI6KXUPs6zelVRtpanrYrZYxOEsDqEUd90cyeSAWGNdCAUxsLA U9J24ZloXsA5MUysCB1SJYQQ0ZkgMsOhyxmRca3mExi3G9bw5TTlyLDtyhJBOV80guUlurruqSbU m3OEmtCkUuESTZGM0R2vw+o0QmXnySgQguxtDkrcVxuVwUSTYF4NggWhHbFq0GhCi179nT1UqaKW cKcTh0DCjXBotFKHKmA0pk5UzWswY7FMCZhoTEwFaCZOMpplt6XZi4phQMFlywSu4NmCxTFnDNzU MItS/yggRZJzVFpoKKBAoMoqdAli+ZSDt2WMB4ahxxiwyzS6I8JTzJIolOwc6FEcKRyoJT2evImR tGkOsfwG0Bh67Yz546HOV3X5mq7g0xVRvaXxNDSeHW6fB5PGdF3k1fdna4KcTi4OU0ZsYdlFmZ3v DmdfCc05yqkrBpwkYHbghg2wqyD40HqKhL0do96I6Rcy2sCgMttRNUS65XtriGBqSCD5/KXkxayc BuC4qRGiFsGWEMp0UIIoqMTSdqpMDrdqRk6YYypeMT9GGY/GVFH9Sbu3FxAyWBEIBMhdp+Tr/P7B Xor2qTDBxBYN2uk7CSy3hCPaeBC+ubgowUSOdiqZ+LSzvwYmP0aCQm1LSgMexp2GiLsk+KpitywW HrBqahA2TRtmXh2YFRhaiqtKbds0x3CUWGlU1ibAtyFPctCiOKjO7jCdO6rOw8PCheuhVbbYZKn4 a29LrJBczoXSQBZjuJhoKQRKBzU5vzreg1LWqBSCl9K3rwWaUWKa5d2kRf3aczeHsfISWboZCD2v MwffqRIr78pWQU2uDz4xkBgwFZggzDAWJG4Fs1naf21fTSF29TqZOBqOadJxgiQRAhlCoEp3pkPd Qk9JrHQIfjchomD0eLVIyHVCnGjFwFXvro+o1vRwMZEnS5H0M3f70O4IQ2I/nGKgZnkBxQ6YBtiJ IgRBgl+TSiWUbHhfiVv0cOI8x6h55CMnY3Fg7kexiKY2MbGd2gQ0S54QORChwmDbtEu47Wc7gpHf tN4JtshVkzQXkG6iBx7HTA0cKzlmVKCVAsaCsRKLDAaOzdC3RYWL8BqvP30znZDaUI3xyyn7aITF Iiv5ePByEiJFSydFjpxmZZ3AvpCwRagOo46CB5u76PF5IF4nLcMLHhqZ1L3V0gFCm5rWzW5OGFMB wC4Vk7zHZg253IVOL1GstLCOniHm2lRIBIkSRiwZEYsUikIEYBl6fIlhwEJyQDn2vBqB4PaLhD7j 2Ze7kMVuE0dWglbHk45I+WBIh0utQQp0YC8g+QIQj0nydrhbfuEzfgPtCUcWF/lt3HfwMOo3REbJ 4BT+qCpBiDASKiGk6uWcekE/Q1CETxjWg4ZOygslRcXOJBjWQBSo4cMMmUYTg6Y9Z+KEhlavtx+n QPmdEkFutk+V874VrojNdClXuWTKSpVRYUFJHkavqNDRJPtO1salXAYhCEMAf6ACLrh7Ng3tIRCR lCNGfzvvPuM0Zs3GYXOt1ROiWdDWZr5NHjPsuD853O3tZMjDdZm3OludzSdzRds3ObvJl1ivA2sD BApKImccnMx9OtewUKyUsPqWcqNRkZGgiYjXqjUe/MIVRA96ggSmWwdCKlxwGr0u9o8Zp8SnQiUk hzlSH8G860ifaiJNev3/XDqrZ28wsPz0w6w9o3Y/FAj8uNvksWkZCEvWs0h9XYJh50HO6DZB9IRW el/NUc3O6ed/CrMX8V8ETahyAMmONMTsTbgyePXAed8j75SPe0QDA9c+gi+hIKGtZtOi2puc+hXp nPrhRMt4luggWYNyQ5V6jEHb5HxIets0ExuugoCYYZDJmDkpVzN58l6FSg1o9a23nbqFYRHCKVe4 jRxXlgs61pMpJig0+Bzqava38kiamDfYrjPd+SbT5U9vztWGFRKFLlNBAGAsV4d4db20Ht+Ck+6J 7leG3dnqW4bV60ycMBlmWlPhfQkd6rVW4p5MU5kL55vJZfSqdyjrVaCY/PYHb2xvHJi/8SlZlNP5 0TIQjbpAlnuGw3eSE7s5Z4SfDPNPMwniZ4qtTDRewMqBeFoFrVdA7Cy2FbSqBvYQvCn0ND0Ojgh5 HY/E4ihox1RdU7bAjzfo/wKA9wn8v10W6iiiH7IUdxydgm0FcMJYAgPuh5Sys+6gLBEVZFWKAjAF BZBE8Cd2OYHFkOYLGJ4Pz18kiVQ3ISoeBy14tPqL9iFwL54hIME+RyeDY9b4TeOzVwKfjbbBzGfB Z9LdfPPMOxjkEbO1s++ir8ZdGGxlD7PkJCkxbavMVWSipykHdbgqXkopENwNcOSyUTImVJZH6pPj mns8D8aD2o6aQOCr9lgklLLn/rvP3e+bBGidAy/aMgW6OOmKHNGCoX9FkPiVAfvX7eC8zcFH9dhV TFqtPydjJDpTUikqELC5EIJ4fXgYLpUJAKD7ypzUTL6ikJkleh98+oB2niSCOUUFtA7Ygnhjn7o5 68m5SmtRIPi3BPzMPE2Rcys4I/UaPVgOZ3cX2G21noicKMPzFJwJK1jS0O/05zjTnYcYQ6Af0yzf AQ4fYmCj7HUhz9Dm/E15+81rX8EOumEx06ZCH1cpYlLCdMDBI2ktW4+d3EzsZbnywS+Bl6rWB4RW CPbS2koeOJU/BqGNLPXSOk+VMmgllEWCIYxjAGgFKkzB/DDfHzPqGCcrAZ5cdV+d52AEikiyMQYS AvgzA9yHge+RfU4+Dl63ze8TXtANhIEYhFizrPaK5vNrOJ3w0ReQSg7kwH1hYIhgnkJvgcROmRAx 95uCTzS4JglGusoLMBLGvnYti32YFjXyD3RTIg5KcN7JEq/cKOjvZbVgUb4PF7CjueP54Wdp9b8x sXb2vStgOv5FwH7Hlzh3vVVQBkQSoJQ+GFKTZKRH6l+TfksVIbFD8/NUrrXntnkXh7D0K4lVHQp1 +3WdS+n3Ojcx8G+EDjCM0kB13D3L1F1xmXyXgt7+DaYTI98eM4L61FS+jp7487lSipDLcunwnJkT eg7IAieGpckTMkMoE64cU0FnFl7tK5l9dvu3IosMEMz0uYHoPq4NXEET623WTRiqCkX7Lfr7ro5E Qd6FUgKLIsjsHeMwSMRkwYgHhe+/V7T42zzmILzZH3avjH7sHte1VfZ5e/Nk37NZ7M9yYNWeBIIG 2UalRWwoUasYUoMT6TQ3xq+iQE1smNbIsms8kZ6XYPnYLmx0p53EzJ9etd5lgNhic1korbZIaAT1 vyx8cHx7DsWB4vBnlcD39dgixBUmRsaORq3p0vF6YaP+UCUPIPspwetoA5+qQYIbkOWe0XnmkCUM 286G7FBQeayisVWLBYIIikQY7KFIMNkgBKEetKKiwQYIWdSocxee8OtuoP90C0JVYSeKfRA62uy6 3BEZDKVDLFqkk3zyob0kfRp0b4eE2qOfVO7Bx6Hc2cQNSnKGtuPA/tnKfzXKIwjTSnw9d+Rj0bHI LhNN4TnRWDJ6oi9w0tH+O0mjIdQwMEfA9uwdUSJ3eyscgcSFM3yQu+AJtNO+yPY2Po9x1eB41mNM cUtCJrQPANytT3xTADHJV9pGKuVhSaxmN7T0ExBZUJEWUWSRYEHChKnt3RwQFBduLqJ5RqhoWSLJ WEpFCArH3Xa7XVsd/mzG8DQNurZe6B8Pm6rAGLnQW/pSd8hbt92yaQuCFN4tvvkW0JgP5ygBTYBR JQ05B/hAIh4xJTwhBVOOc2lkFmB5xS/3+5JPbCxzkoX0HkLkPPCmG3FOE+WqJM578C0vhceaFi5I ehnRB6DvCz5vubvrew78gyPOMCZE+WUnQsQTuU7GGkte5iuXw8ZHKkooiqBZRFlQ36Q8qLjAkAiE 2bHqEcaZ1vmM36PK4miHbQOaiboOBmjtMGOwNx8yOp9qDggGMH3QxgLIAWgj4gzETiI4g1FNhUTc jTiJCvkimArZVEpGYOcYrNo4+RIhm/CD89g0IBMQo5uI/6r6w5DwcqMDv848uknhrmltLQZVFpYv u9p73JUJNFigohiCgiUgIVzCgwJMCBMzzqUZlttQkFRIUowYqA1ShwBKNQTBgwm1NTtUS2TQuvu0 hM7RkQePdju25RcSmMUWg3LFCymkqSWLibBHvGvLqfmia5Eo1WkJyQkxA3OT4TGAMZpNDFJSAJZg VZGkY0lQknetmJkGwYFmrBYIQT2ilddqQLoHCo3Q58DpmhIShFGIJBiIIBtNhcDYQhxop/w1raJB YBA3RCme8+Ftmn1O5728OgRBwO1ght+ouPh4LtvXtQu1Z18DehYJzEDkyjEDPYDBPQ29j8zQL2YF ONEhJ3FUxgdbRId22ERIskmNKYNGWQSaNTQjLJGOTGDBZbIpbJMKypgGBEGA6QC2SDsJZLESQDWd XUGBhUGfgfInc/g0MM8/0CvobpE+BJgxS5lR1SzFrKV+pj40DWM1ZWbbV8zLksDKd6c4d7oIHfnl 07t8noIzCQMsEZPrIKfYN1DydssNkd0AMyIxkoS96S4wXtO1u27nwnjR000Em3Mk+VyPp5+9SPjD W+WY5mxzEE3qxPYNmhKwoQemgQfiIDR9Qwj01TpI1/dDnCzUZFcS0OUS6KG9lNsDjmSE72I/sigQ hIz0HxviA36il0IBYSQhJBlvzUOjFQsjO/aSze31d4VuRtmzSclSNIujahVDQAwmbGDA/3a+RPym r6RSDcz+gcQKJ2BBOs7z9mHr49nyeOElji8nR3A3hpVPK1k/LdZCRqP32EY9EbyRC+G8OmuKqwmC +xQCgkvLLPQu2Ub8v18ejj2pa/HS1o1ud0k9rgM4JG/peQHpcVMjHij2xTzMUgRVQhIEjFRIiQSM k1SxgBjfDRgsUE5rKeOHVANPzEDskijIP97ij1k1dsGulVUmU3lcs3Py7l/yTdyFYFeYWXbrEcxO s4hmAZQghAY9PVAc0ebiGoKmNfH85fxN+rUlJNH+79uU6S4H9dJzZ03EV7B7a+LF3+zH75uSoCSi MPYMAYc3J2xPlQPWX8sursgGQgHGd8UdLiOBApohgLwPg+ACVTSpVIFRUTrFj7rYjT3GkqD981bW LE/d6imPNZox9613GhRbWuf4s/8aXSiChyWdfQED3rIMUaGjAkLIPjO+8yYiP4HtUOlg+OD9IQer 3hKXx7zf3yx7ROKLrwZ6UdwPkfyFU3+S7EHmulZlKZp0rG+IwaE3S2IDIbOSiyRI/3wkGDfTlCBK 8zuJqzTpVjCYZiPXPOQOcDohSDEhehViljyY7mF+YyDm9UL7VQcKxv9yGQeFwJ9jo6wjun6Z1Bvr 7IHg5ElYy3eeh5HieD6vI9rZ+p/J3EgfcxO85P9XFHe5YoViXf53zvkPqfbdvoASEVTW733tqMff dz1Bby8CHz3ZZKPHIxiJ42jBQj7LYyKgRSftT0MmBIfg9nJwqsAjH7p6n71r5v6TE3fP5hR7x6B7 MAOoGHtsQGIxgJWMIjFBkYsYgjI+NsjIsjMWwVZbJYgsmUwBiiEkWgZIoVEoJlDWwLqrHczwdfW2 8ce6ef4X1O7zPqMUwgBthJJwCEWKDsCAXFyuWAuGC0Un9D8bdQC8BYJgim4YILGJ6TydYdTLdBtf bcTRziZEHAEwdYcKQVIEUPYlmiYQVRjjFTFjWNhNWiSF50+en1N/y9U6PR6F3MpakOg9+xPBsC+5 rr4PMvtF8RD0MyZelux3O6uMP5sj9H7nDIOtyLbnjvRG15XM1s3SgshAj8Y0WSEjIH2JN8u+19Fl HYPlI6xYkYqkAiQJv8g7rIeVyDq86q+HaU8+muAX/MQa2XDyAaMgGB7T8XzF3J3lXiFcUY18ztUN fsRrbsQ8IO4nPxL98d9c3kRo6H+mPyzQhAJESSERIRR9JBqLUBqBt6Gc46zoa4i8z/xkh3Ms061Q yoapSFJTSo8DOLVAuBCFSSshCkZJCCwUgoSVx87goe+7jJftdh0mTomokMSvxxtBHV1YHWVpxAoK uXtxaFIVLkFXVfXjKkeznWBeUGBYQFF6jSIShhuaGCkKQ4ByzEDcjBTEAYxMPGsYVQbcxBu+NgNW NBIOMHSKiIWaSduLiBRqeExcsjW1SEpJD1kXwX9/fWiAjnVmmHRl1ETyYaI/AvCscp585cbzNyxb jWMYXnDyYRyIgJBpDPTMrqbCIuWBhz1U6GXASG6M2O+tlI2DCpsaQScpYEwBG2IhBUzpQf0UxvUL bMUdJviJuingJTL2B33UkzyNXnO+IwZDk8DGZrAQTMm5DAMkhBgAvPe9vZ5j1c8C1z5bzJQ5XcGT yPKDxdaV1fbIgZYxnriiNoTh1wLNoQmjOuQdej0ET6+WoNEXStWvLy7uPBR9zW6HeZ3Ho1Weh5MN UhyvV2389rMwtSzpsGGCsBXqGBCI3+oEz3WfkH6FQC/o9R6vpthFCqX1380rkkkqHTEyrJrxGnOm MG2THkBxgdESANsKkOteaKG1B7zdu55Lhd3OzLbbEPjxSswxBfSduTeaRWQUFgxEYAP4XvR9ST9C YU7Yel9z3U85XtqHngHfydrk0PO88cvMXbtjJxPjQ6YJ9BMg+ZlVk/qcMxDkisrKswmjkxi5yw8N qCDDGKDTxQ6aBmTDNAmMs+L3NkLsVTIp12ZPLurrnXA5Mjz4uKbwwHVYyLFizU/uo0/FcM4jlHCM VgdudGWpvxRDYfTkh9N8VttttttttttttttttrbbbewPPpgBhdhB+Mg2MokZDTbkuhEGKaatazaq awDbByM2HnbQaRfvU+Xru+eqtVo96DU8bgmt1wGMGNALMoIwEZlmARoxLYsYsDLNXSCsDIppBkoL BgjS7qZC5JR6BDjhs+XEy0cIf2WCWpNmt1nMCxyGazVAoy17G1tjE1xMwTKjwmJSB8Yc5bZm5jyH Qh7xicjBh6KNtMfXM4DS+c0xzoMlVy4saAVoJDV7IyJEjxGDjxZAXx8q0EDK1mRieDrlAFlHIWSk 1BUGJYjOVcyAPSw0FQVQwEIcNXlICYVGUT80iYY0zjk90ANIEYJwt0xASKAuYrDDFtIbr4dOcBDg AbTCKWikKrTt1E0oBUPYRgUVWs2OKOQtBgmzSmfMb5imKahdG7WZUcNyEWAihECGCxBaDARQiYgR oRBqJNBYKTTZTjsKa28qWO1NuhQwM2aFJlTkQGHUKIlzZYNkCgjsCwKHCzXyRCsJhDdvKy2ONr3q sKc5ql2PACNlOHKhsJFGMhKKCODZPBA5hRD5T4nybn2Nni/idQbNXCFcLFSxdqmxBolnnli1Nzoq 4R5jZivNrsU8tByCAFhpaxCDAHzVbRBuWV0pQsRLKDlCQgEHIkCRYWWyFDEyZs9zW00TEhLRuN5e FrIjuOvh3LdrGnV/slI/uc//w9DHiwY1pf0qQi1bnpUg/twWIggtQHO+XmpQwlM72XytjLvX6wpT i2aSrBVggEvdX5tlg+1ywcSBocYrgUt0UWwIDZ17ZRz55GC5Y+4ooqMd+l22hraHgk05qa6ztK3I KMjjozzOABTlkPP0/I2ch5S0KSho+Z2HUOAluow9kITklnCZ39AQS5zlYQQZw3O3jskWSMiSQYNQ OuwAWQfyoUi0xZmI+HU/F5rqh1S8BC8UO3qMyWXsxop2ge62fXKfxo56dbz5qXEOXMvtDq6Z3j3R xMow79GUkIG7w4QNERFwkoK70sXBdklMWxTAWDsn5MhTCzvxtsAT/ECCNCjmODaiKKErAKkUD12V Isna9ZqdDxChzBkrUUuRClvDok906iEYEvwc+4JOgnqs6ec4+lR7Zl0PjnP68+jA+tGwa0yJQ27Z wGmVZOuNiVG3reMZkzZDnQ5cASwMMg8cA8PqcjGNgTCAe8hx9Dx3e4CazYxdvaLgRXzUnWwfI82J 5KWfr8zqe+jyfM49LofZ/XgVA3rMWITr8kDJTctP3H2dHL4GkixBkOw0QNSIB0AdgkN07IUTCSVA ULEViFapAF5RS0EqAw8D6WktcglJBgB/EgikEiL9jzkQU5eakT+w5isHY5B8noOEnzIH5uko9qwo oDs652OmcfKKonGTAeJPi01SfLSWhY/LXSgaZgq/ukki8wG07Ty9J+rUag3p+iEiyA8UULvwdfvv r3GDH75RT94rMH5lRZSfLHzSuR802aRlOv2EeaT9y34NoYlG9ggw80k9z3pg8Cd/h5JzbYxWVpWr N9mbtyMs/hfhdmOQYHSj9fjfvH0/TvB9BAYfUUeN6fU7QHqT7YeLkEztb5ZaMEubjI9b9TTzkAhA u16PffK3dz0OWSa0wrnfsFHzuvY55ORm3bjxpBJvFUrOs5vLJ/kzMwwUsn5wvuP9eCtVY+S7T73j cjxPT0BIMgQjDn1n3X8z1NP3PvjsFHQDpN/hQoOatHD3HBBoPs5jqup45IH2sHGAqhepxeBFGhSE Q0LjtILOwcGsqcpCRhISzH1vW9D33PqcNjuPKzrdY7O+venhI2DrC1JZbmjg7Hc6FMO+PBMUMzMg yAag1RUKKVkUA1Lj4yErL0rWv6FoOSjlUsGU4vUdUFFcAkGBTJiI0ETh0HLpDpfeCZ9LvbGhLUNg 1EL6CkKGA1qWYKoDg955yUs0CrusSITCAWR3ac+nB2blRYm/G4MQy1kRm6tuSwFkrLrep0DwjkYw kMofvbIHlR2o3GiA1QGCWBq+wbSDcS40I940e18O8p08jxHwPPr1ina7HWGsxFT3TRyQDxRHhEaI EIhCKDqVLRDgdz4x87k63Nwc7yvEdr4latyxXNTAgyZALQyBbVdWYi3qQDDWtSMg2C5KZUZluVa4 rYmWfJffvEl2iPpD/N+3vQKQYGvB/l/9/Yf27CWcE15iFSAf5wCpNKrYNnZswXIaUiqgM//F3JFO FCQ+4yv+gA== --===============6439206237089482492==--