From: Tor Didriksen
Date: October 12 2010 6:17am
Subject: bzr commit into mysql-next-mr-bugfixing branch (tor.didriksen:3226) WL#1393
List-Archive: http://lists.mysql.com/commits/120540
Message-Id: <20101012061710.1FEDD3723@atum07.norway.sun.com>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="===============8797094868444187804=="

--===============8797094868444187804==
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

 3226 Tor Didriksen	2010-10-12
      WL#1393 Optimizing filesort with small limit
      
      Many web customers have to do
      "SELECT ... ORDER BY non_index_column LIMIT X",
      
      When X * <Row Size> 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
        This is a wrapper on top of QUEUE and the queue_xxx() functions.
     @ 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.
        Remove dead code.
     @ 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 test for Bounded_queue and merge-cost estimation.

    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-08-20 09:15:16 +0000
+++ b/libmysqld/CMakeLists.txt	2010-10-12 06:17:03 +0000
@@ -44,6 +44,7 @@ SET(SQL_EMBEDDED_SOURCES emb_qcache.cc l
            ../sql-common/my_user.c ../sql-common/pack.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-09-01 12:52:09 +0000
+++ b/libmysqld/Makefile.am	2010-10-12 06:17:03 +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-10-12 06:17:03 +0000
@@ -1364,6 +1364,249 @@ 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 to memory
+
+# Select all rows, do not use PQ.
+let qq= select * from t1 order by f1 asc, f0 limit 100;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 order by f1 asc, f0 limit 30;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 order by f1 asc, f0 limit 0;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 order by f2 desc, f0 limit 30;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 order by f2 desc, f0 limit 0;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1>10 order by f2, f0 limit 20;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1>10 order by f2, f0 limit 0;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1>10 order by f2, f0 limit 10 offset 10;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1>10 order by f2, f0 limit 0 offset 10;
+eval explain $qq;
+eval $qq;
+
+################
+## Test sort when source data does not fit to 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;
+
+let qq= select * from t1 order by f1 asc, f0 limit 30;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 order by f1 asc, f0 limit 0;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 order by f2 desc, f0 limit 30;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 order by f2 desc, f0 limit 0;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1>10 order by f2, f0 limit 20;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1>10 order by f2, f0 limit 0;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1>10 order by f2, f0 limit 10 offset 10;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1>10 order by f2, f0 limit 0 offset 10;
+eval explain $qq;
+eval $qq;
+
+################
+## Test with SQL_CALC_FOUND_ROWS
+let qq= select SQL_CALC_FOUND_ROWS * from t1
+order by f1, f0 limit 30;
+eval explain $qq;
+eval $qq;
+select FOUND_ROWS();
+
+let qq= select SQL_CALC_FOUND_ROWS * from t1
+order by f1, f0 limit 0;
+eval explain $qq;
+eval $qq;
+select FOUND_ROWS();
+
+let qq= select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 20;
+eval explain $qq;
+eval $qq;
+select FOUND_ROWS();
+
+let qq= select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 0;
+eval explain $qq;
+eval $qq;
+select FOUND_ROWS();
+
+let qq= select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 10 offset 10;
+eval explain $qq;
+eval $qq;
+select FOUND_ROWS();
+
+let qq= select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 0 offset 10;
+eval explain $qq;
+eval $qq;
+select FOUND_ROWS();
+
+################
+## Test sorting with join
+## Explain thinks we cannot use PQ for these,
+## but during execution we will make_simple_join, and use PQ anyways.
+set sort_buffer_size= 327680;
+
+let qq= select * from t1 join tmp on t1.f2=tmp.f2
+order by tmp.f1, f0 limit 30;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 join tmp on t1.f2=tmp.f2
+order by tmp.f1, f0 limit 30 offset 30;
+eval explain $qq;
+eval $qq;
+
+let qq=select SQL_CALC_FOUND_ROWS * from t1 join tmp on t1.f2=tmp.f2
+order by tmp.f1, f0 limit 30 offset 30;
+eval explain $qq;
+eval $qq;
+select FOUND_ROWS();
+
+let qq= 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;
+eval explain $qq;
+eval $qq;
+select FOUND_ROWS();
+
+################
+## Test views
+create view v1 as select * from t1 order by f1, f0 limit 30;
+let qq= select * from v1;
+eval explain $qq;
+eval $qq;
+drop view v1;
+
+create view v1 as select * from t1 order by f1, f0 limit 100;
+let qq= select * from v1 order by f2, f0 limit 30;
+eval explain $qq;
+eval $qq;
+
+create view v2 as select * from t1 order by f2, f0 limit 100;
+let qq= select * from v1 join v2 on v1.f1=v2.f1 order by v1.f2,v1.f0,v2.f0
+limit 30;
+eval explain $qq;
+eval $qq;
+
+################
+## Test group & having
+let qq= select floor(f1/10) f3, count(f2) from t1
+group by 1 order by 2,1 limit 5;
+eval explain $qq;
+eval $qq;
+
+let qq= select floor(f1/10) f3, count(f2) from t1
+group by 1 order by 2,1 limit 0;
+eval explain $qq;
+eval $qq;
+
+################
+## 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
+let qq= select d1.* from t1
+left join (select * from t1 limit 30) d1 on t1.f1=d1.f1
+order by d1.f2 desc limit 30;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1 = (select f1 from t1 order by 1 limit 1);
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1 = (select f1 from t1 order by 1 limit 2);
+eval explain $qq;
+--error ER_SUBQUERY_NO_1_ROW
+eval $qq;
+
+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-09-10 09:23:27 +0000
+++ b/mysql-test/include/select.inc	2010-10-12 06:17:03 +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-10-12 06:17:03 +0000
@@ -1504,6 +1504,986 @@ 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");
+explain select * from t1 order by f1 asc, f0 limit 100;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	100	Using filesort
+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
+explain select * from t1 order by f1 asc, f0 limit 30;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	100	Using filesort
+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
+explain select * from t1 order by f1 asc, f0 limit 0;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
+select * from t1 order by f1 asc, f0 limit 0;
+f0	f1	f2
+explain select * from t1 order by f2 desc, f0 limit 30;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	100	Using filesort
+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
+explain select * from t1 order by f2 desc, f0 limit 0;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
+select * from t1 order by f2 desc, f0 limit 0;
+f0	f1	f2
+explain select * from t1 where f1>10 order by f2, f0 limit 20;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	100	Using where; Using filesort
+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
+explain select * from t1 where f1>10 order by f2, f0 limit 0;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
+select * from t1 where f1>10 order by f2, f0 limit 0;
+f0	f1	f2
+explain select * from t1 where f1>10 order by f2, f0 limit 10 offset 10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	100	Using where; Using filesort
+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
+explain select * from t1 where f1>10 order by f2, f0 limit 0 offset 10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	100	Using where; Using filesort
+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;
+explain select * from t1 order by f1 asc, f0 limit 30;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	500	Using filesort
+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
+explain select * from t1 order by f1 asc, f0 limit 0;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
+select * from t1 order by f1 asc, f0 limit 0;
+f0	f1	f2
+explain select * from t1 order by f2 desc, f0 limit 30;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	500	Using filesort
+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
+explain select * from t1 order by f2 desc, f0 limit 0;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
+select * from t1 order by f2 desc, f0 limit 0;
+f0	f1	f2
+explain select * from t1 where f1>10 order by f2, f0 limit 20;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	500	Using where; Using filesort
+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
+explain select * from t1 where f1>10 order by f2, f0 limit 0;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
+select * from t1 where f1>10 order by f2, f0 limit 0;
+f0	f1	f2
+explain select * from t1 where f1>10 order by f2, f0 limit 10 offset 10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	500	Using where; Using filesort
+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
+explain select * from t1 where f1>10 order by f2, f0 limit 0 offset 10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	500	Using where; Using filesort
+select * from t1 where f1>10 order by f2, f0 limit 0 offset 10;
+f0	f1	f2
+explain select SQL_CALC_FOUND_ROWS * from t1
+order by f1, f0 limit 30;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	500	Using filesort
+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
+explain select SQL_CALC_FOUND_ROWS * from t1
+order by f1, f0 limit 0;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	500	Using filesort
+select SQL_CALC_FOUND_ROWS * from t1
+order by f1, f0 limit 0;
+f0	f1	f2
+select FOUND_ROWS();
+FOUND_ROWS()
+500
+explain select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 20;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	500	Using where; Using filesort
+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
+explain select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 0;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	500	Using where; Using filesort
+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
+explain select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 10 offset 10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	500	Using where; Using filesort
+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
+explain select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 0 offset 10;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	500	Using where; Using filesort
+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;
+explain select * from t1 join tmp on t1.f2=tmp.f2
+order by tmp.f1, f0 limit 30;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	tmp	ALL	NULL	NULL	NULL	NULL	300	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	500	Using where; Using join buffer (BNL, regular buffers)
+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
+explain select * from t1 join tmp on t1.f2=tmp.f2
+order by tmp.f1, f0 limit 30 offset 30;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	tmp	ALL	NULL	NULL	NULL	NULL	300	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	500	Using where; Using join buffer (BNL, regular buffers)
+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
+explain select SQL_CALC_FOUND_ROWS * from t1 join tmp on t1.f2=tmp.f2
+order by tmp.f1, f0 limit 30 offset 30;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	tmp	ALL	NULL	NULL	NULL	NULL	300	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	500	Using where; Using join buffer (BNL, regular buffers)
+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
+explain 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;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	tmp	ALL	NULL	NULL	NULL	NULL	300	Using temporary; Using filesort
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	500	Using where; Using join buffer (BNL, regular buffers)
+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;
+explain select * from v1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	<derived2>	ALL	NULL	NULL	NULL	NULL	30	
+2	DERIVED	t1	ALL	NULL	NULL	NULL	NULL	500	Using filesort
+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;
+explain select * from v1 order by f2, f0 limit 30;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	<derived2>	ALL	NULL	NULL	NULL	NULL	100	Using filesort
+2	DERIVED	t1	ALL	NULL	NULL	NULL	NULL	500	Using filesort
+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;
+explain select * from v1 join v2 on v1.f1=v2.f1 order by v1.f2,v1.f0,v2.f0
+limit 30;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	<derived2>	ALL	NULL	NULL	NULL	NULL	100	Using temporary; Using filesort
+1	PRIMARY	<derived3>	ALL	NULL	NULL	NULL	NULL	100	Using where; Using join buffer (BNL, regular buffers)
+3	DERIVED	t1	ALL	NULL	NULL	NULL	NULL	500	Using filesort
+2	DERIVED	t1	ALL	NULL	NULL	NULL	NULL	500	Using filesort
+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
+explain select floor(f1/10) f3, count(f2) from t1
+group by 1 order by 2,1 limit 5;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	500	Using temporary; Using filesort
+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
+explain select floor(f1/10) f3, count(f2) from t1
+group by 1 order by 2,1 limit 0;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
+select 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|
+explain select d1.* from t1
+left join (select * from t1 limit 30) d1 on t1.f1=d1.f1
+order by d1.f2 desc limit 30;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	500	Using temporary; Using filesort
+1	PRIMARY	<derived2>	ALL	NULL	NULL	NULL	NULL	30	Using where
+2	DERIVED	t1	ALL	NULL	NULL	NULL	NULL	500	
+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
+explain select * from t1 where f1 = (select f1 from t1 order by 1 limit 1);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	500	Using where
+2	SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	500	Using filesort
+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
+explain select * from t1 where f1 = (select f1 from t1 order by 1 limit 2);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	500	Using where
+2	SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	500	Using filesort
+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-10-12 06:17:03 +0000
@@ -0,0 +1,164 @@
+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;
+set sort_buffer_size= 32768;
+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;
+FLUSH STATUS;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+explain select * from t1 order by f2 limit 100;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	229600	Using filesort
+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-09-28 15:17:29 +0000
+++ b/mysql-test/r/select_none.result	2010-10-12 06:17:03 +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-10-12 06:17:03 +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.
+#
+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; 
+
+# Test when only sortkeys fits to memory
+set sort_buffer_size= 32768; 
+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;
+
+FLUSH STATUS;
+SHOW SESSION STATUS LIKE 'Sort%';
+
+let qq=select * from t1 order by f2 limit 100;
+eval explain $qq;
+eval $qq;
+
+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-10-12 06:17:03 +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-10-12 06:17:03 +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)
@@ -492,7 +492,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 +543,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 +571,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-09-28 15:30:47 +0000
+++ b/sql/CMakeLists.txt	2010-10-12 06:17:03 +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 
@@ -105,7 +106,8 @@ ADD_DEPENDENCIES(master GenError)
 SET (SLAVE_SOURCE rpl_slave.cc rpl_reporting.cc rpl_mi.cc rpl_rli.cc)
 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-08-20 09:15:16 +0000
+++ b/sql/Makefile.am	2010-10-12 06:17:03 +0000
@@ -159,6 +159,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-10-12 06:17:03 +0000
@@ -0,0 +1,121 @@
+/* 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 <string.h>
+#include "bounded_queue.h"
+#include "sql_const.h"
+#include "sql_sort.h"
+
+Bounded_queue::Bounded_queue()
+{
+  memset(&m_queue, 0, sizeof(m_queue));
+}
+
+
+Bounded_queue::~Bounded_queue()
+{
+  delete_queue(&m_queue);
+}
+
+
+int Bounded_queue::init(ha_rows max_elements, uint offset_to_key,
+                        pbool max_at_top,
+                        queue_compare compare, size_t compare_length,
+                        keymaker_function keymaker, Sort_param *sort_param,
+                        uchar **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;
+  // 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,
+                    compare, &m_compare_length);
+}
+
+
+void Bounded_queue::push(uchar *element)
+{
+  DBUG_ASSERT(is_initialized());
+  if (queue_is_full((&m_queue)))
+  {
+    uchar **pq_top= (uchar **) 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, (uchar*)&m_sort_keys[m_queue.elements]);
+  }
+}
+
+
+uchar* Bounded_queue::pop()
+{
+  return queue_remove(&m_queue, 0);
+}
+
+
+double get_merge_many_buffs_cost_fast(ha_rows num_buffers, ha_rows max_n_elems,
+                                      ha_rows last_n_elems, uint elem_size)
+{
+  double total_cost;
+  const double MERGEBUFF_double= (double) MERGEBUFF;
+
+  /* Calc CPU cost of sorting each buffer */
+  total_cost= ( num_buffers * max_n_elems * log(1.0 + max_n_elems) +
+                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() */
+    ha_rows loop_limit= num_buffers - MERGEBUFF*3/2;
+    ha_rows num_merge_calls= 1 + loop_limit/MERGEBUFF;
+    ha_rows i_end_value= num_merge_calls * MERGEBUFF;
+
+    /* Cost of merge sort 'num_merge_calls' */
+    total_cost+= num_merge_calls *
+      ( 2.0 * (max_n_elems * MERGEBUFF_double * elem_size) / IO_SIZE
+        + max_n_elems * MERGEBUFF_double * log(MERGEBUFF_double) /
+          (TIME_FOR_COMPARE_ROWID * M_LN2));
+
+    /* # of records in last buffer */
+    last_n_elems+= (num_buffers - i_end_value) * max_n_elems;
+
+    /* cost of merge sort of last buffer */
+    total_cost+= 2.0 * ((double)last_n_elems * elem_size) / IO_SIZE
+      + double(last_n_elems) * log(MERGEBUFF_double) /
+        (TIME_FOR_COMPARE_ROWID * M_LN2);
+
+    num_buffers= num_merge_calls;
+    max_n_elems*= MERGEBUFF;
+  }
+
+  /* Simulate final merge_buff call. */
+  last_n_elems+= max_n_elems*num_buffers;
+  total_cost+= 2.0 * ((double)last_n_elems * elem_size) / IO_SIZE
+    + double(last_n_elems) * log(num_buffers + 1.0) /
+      (TIME_FOR_COMPARE_ROWID * M_LN2);
+
+  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-10-12 06:17:03 +0000
@@ -0,0 +1,119 @@
+/* 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 "my_global.h"
+#include "my_base.h"
+#include "queues.h"
+
+class Sort_param;
+
+/**
+  Function for making sort-key from input data.
+  @param param Sort parameters.
+  @param to    Where to put the key.
+  @param pos   The input data.
+ */
+typedef void (*keymaker_function)(Sort_param *param, uchar *to, uchar *pos);
+
+/**
+  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.
+ */
+class Bounded_queue
+{
+public:
+  Bounded_queue();
+  ~Bounded_queue();
+
+  /**
+    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.
+    @parem compare_length Lenght of the data 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, pbool max_at_top,
+           queue_compare compare, size_t compare_length,
+           keymaker_function keymaker, Sort_param *sort_param,
+           uchar **sort_keys);
+
+  /**
+    Pushes an element on the queue.
+    If the queue is already full, we discard the smallest (or biggest) element.
+
+    @param element        The element to be pushed.
+   */
+  void push(uchar *element);
+
+  /**
+    Removes an element from the queue.
+
+    @retval Pointer to the removed element.
+   */
+  uchar *pop();
+
+  /**
+    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:
+  uchar            **m_sort_keys;
+  size_t             m_compare_length;
+  keymaker_function  m_keymaker;
+  Sort_param        *m_sort_param;
+  st_queue           m_queue;
+};
+
+/*
+  Calculate cost of merge sort
+
+    @param num_buffers    # of merge buffers
+    @param max_n_elems    max # of keys in memory buffer
+    @param last_n_elems   # of keys in last 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_buffers, ha_rows max_n_elems,
+                                      ha_rows last_n_elems, 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-10-12 06:17:03 +0000
@@ -32,11 +32,23 @@
 #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
 
+/*
+  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.
+  Assuming there is some extra overhead in QUEUE,
+  we set this constant to 3.0 (rather than 2.0)
+ */
+static double PQ_slowness= 3.0;
+
 /// How to write record_ref.
 #define WRITE_REF(file,from) \
 if (my_b_write((file),(uchar*) (from),param->ref_length)) \
@@ -44,22 +56,23 @@ 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 uchar **make_char_array(uchar **old_pos, 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,
@@ -68,6 +81,41 @@ static SORT_ADDON_FIELD *get_addon_field
                                           uint sortlength, uint *plength);
 static void unpack_addon_fields(struct st_sort_addon_field *addon_field,
                                 uchar *buff);
+static uchar **check_if_pq_applicable(Sort_param *param, FILESORT_INFO *info,
+                                      TABLE *table,
+                                      ha_rows records, ulong memavl);
+
+
+void Sort_param::init(uint sortlen, TABLE *table, THD *thd,
+                      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(thd, 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 +128,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 +147,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 memavl;
   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 +187,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 +195,98 @@ ha_rows filesort(THD *thd, TABLE *table,
   my_b_clear(&buffpek_pointers);
   buffpek=0;
   error= 1;
-  bzero((char*) &param,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, 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,
-                                        &param.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;
+
+  table_sort.sort_keys=
+    check_if_pq_applicable(&param, &table_sort, table, num_rows, memavl);
+  if (table_sort.sort_keys)
+  {
+    DBUG_PRINT("info", ("filesort PQ is applicable"));
+    const size_t compare_length= param.sort_length;
+    if (pq.init(param.max_rows, 0, 1,
+                (queue_compare) (get_ptr_compare(compare_length)),
+                compare_length,
+                &make_sortkey, &param, 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
+    DBUG_PRINT("info", ("filesort PQ is not applicable"));
+
+  if (!table_sort.sort_keys)
   {
-    my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR+ME_WAITTANG));
-    goto err;
+    const ulong 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.num_keys_per_buffer= (uint) min(num_rows, keys);
+      if ((table_sort.sort_keys=
+           make_char_array(table_sort.sort_keys,
+                           param.num_keys_per_buffer, param.rec_length)))
+        break;
+      old_memavl=memavl;
+      if ((memavl=memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
+        memavl= min_sort_memory;
+    }
+    if (memavl < 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(&param,select,sort_keys, &buffpek_pointers,
-			     &tempfile, selected_records_file)) ==
+  if ((num_rows= find_all_keys(&param, 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(&param,sort_keys,(uint) records, &table_sort))
+    if (save_index(&param, sort_keys, (uint) num_rows, &table_sort))
       goto err;
   }
   else
@@ -286,8 +315,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(&param,(uchar*) sort_keys,buffpek,&maxbuffer,
 			&tempfile))
@@ -299,9 +329,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", ("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 +370,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 */
 
 
@@ -366,23 +405,22 @@ void filesort_free_buffers(TABLE *table,
 
 /** Make a array of string pointers. */
 
-static char **make_char_array(char **old_pos, register uint fields,
-                              uint length, myf my_flag)
+static uchar **make_char_array(uchar **old_pos, 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)))
+      (old_pos=
+       (uchar**) my_malloc(fields * (length + sizeof(char*)), MYF(0))))
   {
-    pos=old_pos; char_pos=((char*) (pos+fields)) -length;
-    while (fields--) *(pos++) = (char_pos+= length);
+    uchar **pos= old_pos;
+    uchar *char_pos= ((uchar*) (pos+fields)) - length;
+    while (fields--)
+      *(pos++) = (char_pos+= length);
   }
 
   DBUG_RETURN(old_pos);
-} /* make_char_array */
+}
 
 
 /** Read 'count' number of buffer pointers into memory. */
@@ -470,20 +508,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 +541,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 +558,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 +572,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 +624,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 +641,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 +653,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)
       {
-	if (write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
-	  DBUG_RETURN(HA_POS_ERROR);
-	idx=0;
-	indexpos++;
+        pq->push(ref_pos);
+        idx= pq->num_elements();
+      }
+      else
+      {
+        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 +699,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 +730,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 +793,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 +1046,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 +1084,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 +1108,127 @@ 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 info      Filesort information.
+  @param table     Table to sort.
+  @param num_rows  Estimate of number of rows in source record set.
+  @param memavl    Memory available for sorting.
+
+  DESCRIPTION
+    Function tests applicability of PQ to get L top records for queries like
+    SELECT ... FROM t ORDER BY a1,...,an LIMIT max_rows;
+    It tests whether there is enough memory to contain max_rows elements,
+    whether max_rows is small enough to make PQ perform faster that qsort
+    on table containing 'num_rows' records. If available memory is enough to
+    store only 'max_rows' sort keys without addon data, it modifies 'table'
+    to sort with references to tuples instead of additional data. In evaluations
+    it uses 'param' to get sort key, addon data and reference sizes, 'table' -
+    to get table scan time.
+
+   @retval
+    allocated buffer - if it's ok to use PQ
+    NULL - PQ will be slower than merge-sort, or there is not enough memory.
+*/
+
+uchar **check_if_pq_applicable(Sort_param *param, FILESORT_INFO *info,
+                               TABLE *table, ha_rows num_rows, ulong memavl)
+{
+  DBUG_ENTER("check_if_pq_applicable");
+
+  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);
+  }
+
+  uchar **sort_keys;
+  ulong num_available_keys= memavl/(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 )
+    {
+      if ((sort_keys= make_char_array(info->sort_keys,
+                                      param->num_keys_per_buffer,
+                                      param->rec_length)))
+        DBUG_RETURN(sort_keys);
+    }
+    else
+    {
+      /* PQ will be slower */
+      DBUG_RETURN(NULL);
+    }
+  }
+
+  if (param->max_rows + 1 < num_available_keys &&
+      (sort_keys= make_char_array(info->sort_keys,
+                                  param->num_keys_per_buffer,
+                                  param->rec_length)))
+    DBUG_RETURN(sort_keys);
+
+  /* Try to strip off addon fields */
+  if (param->addon_field)
+  {
+    const ulong row_lenght=
+      param->sort_length + param->ref_length + sizeof(char*);
+    num_available_keys= memavl / row_lenght;
+
+    if (param->max_rows + 1 < num_available_keys)
+    {
+      const double merge_cost=
+        get_merge_many_buffs_cost_fast(num_rows / num_available_keys,
+                                       num_available_keys,
+                                       num_rows % num_available_keys,
+                                       row_lenght);
+      const double pq_cost=
+        (PQ_slowness * num_rows + param->max_rows + 1)*
+        log(param->max_rows + 1.0) / TIME_FOR_COMPARE_ROWID +
+        param->max_rows * table->file->scan_time();
+
+      if (merge_cost < pq_cost)
+        DBUG_RETURN(NULL);
+
+      sort_keys= make_char_array(info->sort_keys,
+                                 param->num_keys_per_buffer,
+                                 param->rec_length);
+      if (sort_keys)
+      {
+        // Make attached data to be references instead of fields.
+        my_free(info->addon_buf);
+        my_free(info->addon_field);
+        info->addon_buf= NULL;
+        info->addon_field= 0;
+        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 + param->addon_length;
+
+        DBUG_RETURN(sort_keys);
+      }
+    }
+  }
+  DBUG_RETURN(NULL);
+}
+
+
 /** 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 +1357,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 +1389,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 +1414,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 +1504,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 +1564,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,

=== modified file 'sql/filesort.h'
--- a/sql/filesort.h	2010-07-02 02:58:51 +0000
+++ b/sql/filesort.h	2010-10-12 06:17:03 +0000
@@ -21,6 +21,7 @@ class SQL_SELECT;
 #include "my_global.h"                          /* uint, uchar */
 #include "my_base.h"                            /* ha_rows */
 
+class JOIN;
 class SQL_SELECT;
 class THD;
 struct TABLE;
@@ -29,7 +30,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-10-12 06:17:03 +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-08-12 00:26:10 +0000
+++ b/sql/sql_delete.cc	2010-10-12 06:17:03 +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-09-30 14:53:11 +0000
+++ b/sql/sql_select.cc	2010-10-12 06:17:03 +0000
@@ -2569,6 +2569,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))
@@ -2746,6 +2747,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)
@@ -3031,11 +3034,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))
@@ -3261,12 +3265,21 @@ 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;
+      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;
@@ -3299,6 +3312,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;
@@ -18277,8 +18299,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)
       {
@@ -19890,7 +19930,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
@@ -19992,9 +20032,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)
   {
@@ -20341,7 +20383,7 @@ SORT_FIELD *make_unireg_sortorder(ORDER 
   pos= sort= sortorder;
 
   if (!pos)
-    return 0;
+    DBUG_RETURN(0);
 
   for (;order;order=order->next,pos++)
   {
@@ -20358,6 +20400,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-10-12 06:17:03 +0000
@@ -26,7 +26,7 @@ typedef struct st_sort_field SORT_FIELD;
 
 class Field;
 struct TABLE;
-
+class THD;
 
 /* Defines used by filesort and uniques */
 
@@ -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,15 +91,22 @@ 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, THD *thd,
+            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,
+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);

=== modified file 'sql/sql_table.cc'
--- a/sql/sql_table.cc	2010-09-28 15:17:29 +0000
+++ b/sql/sql_table.cc	2010-10-12 06:17:03 +0000
@@ -7092,7 +7092,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-08-16 06:58:42 +0000
+++ b/sql/sql_update.cc	2010-10-12 06:17:03 +0000
@@ -424,7 +424,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-07-08 21:42:23 +0000
+++ b/sql/uniques.cc	2010-10-12 06:17:03 +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-07-30 08:34:23 +0000
+++ b/unittest/gunit/CMakeLists.txt	2010-10-12 06:17:03 +0000
@@ -207,7 +207,7 @@ IF (CMAKE_CXX_COMPILER_ID STREQUAL "SunP
 ENDIF()
 
 # Add tests (link them with sql library) 
-SET(TESTS sql_list mdl mdl_mytap my_regex thread_utils)
+SET(TESTS bounded_queue sql_list mdl mdl_mytap my_regex 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-10-12 06:17:03 +0000
@@ -0,0 +1,179 @@
+/* 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 <gtest/gtest.h>
+#include <algorithm>
+
+#include "bounded_queue.h"
+#include "my_sys.h"
+
+namespace {
+
+const int num_elements= 14;
+const int num_keys= 1 + num_elements / 2;
+
+// A simple helper function to determine array size.
+template <class T, int size>
+int array_size(const T (&)[size])
+{
+  return size;
+}
+
+
+static int int_ptr_compare(void *cmp_arg, uchar *a, uchar *b)
+{
+  size_t first_arg= *(size_t*) cmp_arg;
+  EXPECT_EQ(first_arg, sizeof(int));
+
+  int a_num= (**(int**)a);
+  int b_num= (**(int**)b);
+  if (a_num > b_num)
+    return +1;
+  if (a_num < b_num)
+    return -1;
+  return 0;
+}
+
+
+// We use the data value itself as key.
+void mock_keymaker(Sort_param *sp, uchar *to, uchar *ref_pos)
+{
+  memcpy(to, ref_pos, sizeof(int));
+}
+
+
+class Bounded_queue_test : public ::testing::Test
+{
+protected:
+  Bounded_queue_test() : m_element_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)]);
+
+    for (ix=0; ix < array_size(m_key_ptrs); ++ix)
+      m_key_ptrs[ix]= (uchar*) &m_key_data[ix];
+  }
+
+  // Key pointers and data, used by the queue_xxx() functions.
+  uchar*        m_key_ptrs[num_keys];
+  int           m_key_data[num_keys];
+  // Some random intput data, to be sorted.
+  int           m_test_data[num_elements];
+
+  size_t        m_element_size;
+  Bounded_queue m_queue;
+private:
+  GTEST_DISALLOW_COPY_AND_ASSIGN_(Bounded_queue_test);
+};
+
+
+// googletest recommends DeathTest suffix for classes use in death tests.
+typedef Bounded_queue_test Bounded_queue_DeathTest;
+
+#if !defined(DBUG_OFF)
+/*
+  Verifies that we DBUG_ASSERT if trying to push to an un-initialized queue.
+ */
+TEST_F(Bounded_queue_DeathTest, die_if_not_initialized)
+{
+  ::testing::FLAGS_gtest_death_test_style = "threadsafe";
+  int foo= 1;
+  EXPECT_DEATH_IF_SUPPORTED(m_queue.push((uchar*) &foo),
+                            ".*Assertion .*is_initialized.*");
+}
+#endif  // !defined(DBUG_OFF)
+
+
+/*
+  Verifies that construct, initialize, destroy works.
+ */
+TEST_F(Bounded_queue_test, construct_and_destruct)
+{
+  EXPECT_EQ(0, m_queue.init(num_elements/2, 0, TRUE,
+                            (queue_compare) (get_ptr_compare(m_element_size)),
+                            m_element_size,
+                            &mock_keymaker, NULL, m_key_ptrs));
+}
+
+
+/*
+  Verifies that we reject too large queues.
+ */
+TEST_F(Bounded_queue_test, too_many_elements)
+{
+  EXPECT_EQ(1, m_queue.init(UINT_MAX, 0, TRUE,
+                            (queue_compare) (get_ptr_compare(m_element_size)),
+                            m_element_size,
+                            &mock_keymaker, NULL, m_key_ptrs));
+  EXPECT_EQ(1, m_queue.init(UINT_MAX - 1, 0, TRUE,
+                            (queue_compare) (get_ptr_compare(m_element_size)),
+                            m_element_size,
+                            &mock_keymaker, NULL, m_key_ptrs));
+}
+
+/*
+  Verifies that sorting, and bounded size, works.
+ */
+TEST_F(Bounded_queue_test, sort_buffer)
+{
+  EXPECT_EQ(0, m_queue.init(num_elements/2, 0, TRUE, int_ptr_compare,
+                            m_element_size,
+                            &mock_keymaker, NULL, m_key_ptrs));
+  for (int ix= 0; ix < array_size(m_test_data); ++ix)
+  {
+    m_queue.push((uchar*) &m_test_data[ix]);
+  }
+  int prev_element= num_elements;
+  int expected_value= num_elements / 2;
+  while (!m_queue.num_elements())
+  {
+    uchar *top_p= m_queue.pop();
+    int *top= *(int**) top_p;
+    EXPECT_GT(prev_element, *top);
+    EXPECT_EQ(expected_value--, *top);
+    prev_element= *top;
+  }
+}
+
+TEST(Cost_estimation_test, 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,
+                                     num_keys,
+                                     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;
+  }
+}
+
+}  // namespace


--===============8797094868444187804==
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\
#   1mkf8polyejlxpd1
# target_branch: file:///export/home/didrik/repo/next-mr-opt-team-\
#   wl1393-merge/
# testament_sha1: 026868bc328b2a3d52669ef8ce620ee42d5f7b84
# timestamp: 2010-10-12 08:17:09 +0200
# base_revision_id: tor.didriksen@stripped\
#   cao5fiah7dfi3vev
# 
# Begin bundle
IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWe7F8fQASKB/gH//fu9/////
/////r////9gX14fS+99d5Pe9Pu2u+7iZ7vQqtSXOmE829zdbePKc3sV21Hz2L199vDTXPMXO521
XwQK+9w86fT2F9697znd8Bvjr533Rs0nvr7pvZX3N75fbzZPvdx72qVpu89jrAPOW+97tHom7zeu
wde7nvAeO7gL3u6MlV7sB00aFxTb75ndyj6+30ctstWZUu7OtU99N9tF28+9kOjAsTBVu757RUu7
59E58+F5YC9577vvVsw+3QamwGjpuYDWlCQa003au40rbKnRTKgiOlakTWKPt8LZ3vGEAX28RO9e
XdleqMgAB697BCSQEAmjECMmgamExEwT1TKnsjCp71NTQPSmmh41RmownqYNJmglCaDQIQk0ajTB
Jk1T9U09E9TA0BMEAZMGhGQAwmAIDE0IQhNIxEyYTRTbVH6ieRojyjQGmagAAADQGgAAJNJIQQTS
aZNNTDUn6p6anmkaaYVPyKaNk0IB+qep4obUGgGgGnqD1MIlCAgBAAQ0TJmkyYQJpkCj9RtTIyT1
PFPTTTCRoxNNGgBUkgT0QJoJk0mTEp5qYpsoPFNplAaAek0MgAGmgBoAZ5DrEPSkV1QQIQU/dAVG
n+Gz1FSXqxWIMIkYiSIRgpGCkYKhAQH/MwJfUfjVuViRiwgRgkYkYkkEGsFqD9qF1ErcCwF9oLQF
9xIWSHyJCyQ+VCyHzIWQ/Olp9iWmTRyxFcgQjBjBIwiQYxVKNgJQIFQoGjNWoDAiDmrRUgQRzLGp
Y1LGpY1LGaSaEKlJUpGJBAYBOXSO0QYXo6u16Xpel6Xped2IhQRCHEWFhnabQ0NDQ0M4iExEIdYi
UXEBmqiYuMRtG0bRtDJknU6jUajUXGI1Go1EEtEh4aBiBiBiBioxYYgYgYQYCCRBZdZdZdZdZdZu
WXWXWUKF1l1mRQyKGS0XJaLktFyWi5LRclov6k+vQyMkP8QoI7uGvXHaCG1BR+xcBEscWoEdi25j
jFUkVKkZIjW5D/shtch2kPwEPwEOEn7SnRaWWqlSMyGliwQOkOp/9/d5/R+fcmpiYqm9lY+DPzH/
pCgIHBR07QSKrxUMqqKaHch6JHdtJP/qH3fP3R96R2wrI7GuXqvbx+dV+63/W+Xtx48vivyJPRnk
Uah3tw3kpmQCHOoPOYhffv0VHxR67MIaj9Jw4I28UeNVmBLvw7v75XOceCi7GOsAUlC+nZdj5x0Q
wiR738tPbr8H3Nj/t39nlyb9/R/9/fv5+FfX/lwu/fb/gx11uG04HPdDuty4zoGQlTs54b2TtbHo
/T6fV5PXz/e45ZVHf0W1vraDO3s3nst5HPVD+j4OaDH34FLbb/jsWOD22xaDDb5Kucw17YtdB7vO
wHbLtoh0Vu/o/TE3UxahxTgyHXsmar9JjVwfPVt5rVxo02MQg6HLyvmqXhlQOQuuUtUtlVjsTAt9
/D2Q6Z+rqOV5GezWHopefFOJp+6sLb68YtPu11lwtl0WY8oWalZdHTx1rIAGmA58W2oPsi3vi3hv
5B97RCjevSKrXEcwGC0O5qDpdw6vQ+5TYyY1PxfYYj7U82sWmEl3YvClodlY77hAW/bXGfTvC4g/
veAga71fr2pc02NfRHaryjpM9IgziIQaGtghPnmvLjzSNaFhwOuz6io37m3lGUbk1tPWYXQE8kaZ
SHCgJBUiDderv2Q5PXmMw4q7MvrA0SA99Be8Pbq8boORBncApBIMSRrjqfDt8HY7sxlTk2libb5M
47mDNHCZIEQn+jpIiwIFcX1kuqVoAZgVQ1IeJ8LYwL2iXpet63vW6LnBkL29wArYSQ0BtmxHgjxH
ujrWtdOZurEDydp9lNp27ACwByIHIgcHg2bNkWRZNk2eDdI0aNgNjoM5JBmBaAtAXIK7u8VEshXT
heQA4AogbEDY7GzZsiyLJsmzsbEmTbtSpVq1spmZ1YGCcPUAAaAEkCiBo6N2bIsiybJs6NiTJt2t
iKilhYWymZnbHceqB0cZMBXxgbCEeFwsLCyuFwpMgTA2kaR0tLStZWVhWBpEOQqRZrQ1XaJtE2ib
RNlB3FJDw0IacamNVGajVRqo1UITCLCgacaQ1MamNCogm0E2gmzwNb2XFZWGUVWVENSzolQw1sjY
5RFK2uWpq5FWPEkDaMbcaci+gQMz8AFCGEQnNkOqQ7kOdSgL2slQFAFkO7tgAlofON4YSW4379TE
mEt/X1ZBO39kbuXuv+9HWUD/qwANnv2tfF3J46itDJl6XePV5bk0kNMPAQnw+gptOnLpgh1fI1dt
sMOsnR2sUeROsYucqM2cKeUa08zaQeMu8XmnjOI6ajQxnOy22jas1WqzWwu4pTWQjgaxm1ttmIW1
5bsVtmw8+XTOOOoQFhpCe8yCkEG+fcu/LJgc8AL2dkTlnzQ3MwZEKC5SSBI4W8zv6T2nawiwheQ8
pKEIBs4QzOOWLjEjQngybtX71qty30eeetzSloYlJmv8FvYGolOADVbCH1KS6Uxjz+ICIipm166z
2fEeorfdf1BBoKKmRARRrQBe+D6YI1gg/X/sbem2uKZw4Tk/M8MkOTFE4tioTX7eMNmGyYm7J5GA
+FAKk6apLGZjQ56nhhpD7GEgeKE5ssGb+7hDQwhqAfhSoKIoH4hDzf65rIQUA9hk4TIsQY+nzShp
NVqTuaJQYxggxj3QAKMVXy3bpx6vBMH5phORiQISR5ugaV/+dFHrUdkigQDUe4r4ioubO9+83jEI
ao/CfOEWZmY+VjmDRTTX6a4tN2OpZMoJfuyIwQ2xizQjTnhJWdWZQgmjgF0Hg1MeLh6nb39dctXm
488qno5UmyofI+1OCU4p0VVcN85opMSkp/pV8jDLsHTJJIxiKQWIrUxlQkNhkkD4T5fZakfkrHf4
Nuk1ChmH7CYke+PwFnTYpoCUT9xm3//oGrikFRgPg9cBgdyyTv/jINZEJmqx8L709hcOrl4Mz4Mj
HvVHB/JzSafqR8XW0ypPt1FguvKBHz8+oQ+8g4gm4EgpIyEhISKLFixYCkUFFVGRZBSSQSQTz38a
Hy8wPNszaDcoysu/2FHPh8nMfR9EZEV8sngq6iUPqH3dXcCzZpH1s1Sm56rIIPdbaWGiHhnftYvg
zxWn43xpbyIHWXXLrxmyKW38fJiKM63UlScrYZmzO2QoTXJedqBiq1LrNmjLPNs4o7pTGJTWLM8M
hdetbhEHhYsXuunzqEvlNp2E2fnPSOF+dF5OVLoHW5uf4lfp5T7MjtPDh0LOIPEws7uO24b1h5Up
/Z6rcHGcB+jyY2HYAb3OtSCCH04wzkHOZ9Bq1SHRRyuXOkcqEN0MGcZtZeZ1WzMsLVRl5WLvd0IF
EhaqToI96W59K2vxzZ1qBURUynwgJTT38p7DjlVR06Z5LdFLKyrxDqMcRCtDSytJLhbJJKFWYLWE
GmpULEujB84TamqqcE6hx81mRk5mz7+HmvTPhWbSlvDaHK05Ci4buaplU1VTlkw+ZRZK4SMy+d26
PFdPsUc8vf8tSlzrnEH31VG35yad6cH5PssOoduunRVEssZ7iyEwKuylXS4ahDZvl+uOlCQYH+iF
58/eaPK1v1DNDWzD0++FNwbjxu+p16NKCC+csWa1aXT0ucTkSerm0bS+hV0A4JaeijKzbk9FenPf
xcFy+ZVH5WKBrrc1EC3enLhLW5BQtvkU/lCiyhhCzfaH7ieC6M+fU4wsFy8ceLUUMp8ZnWvXc7bW
qcsK6DQZWD1uxcYR2RZ2cj0/zEhwfxKtK5UbRi0lt7XLLqOTSmPyWUZLIzZomYX3S34/tTo/F97j
NDbQ6nL6C20eeuQYn41+UZg7nMYmFpjWm6dgeTtuw/wc62j8Qeoit9YHbfw1fRnf5rMIyddT2vtb
TymJq8YRvzIccNM32lrWIrqYpHLnoURcowaQFSdWdCqtpvu49Mw+1qeqNuPH/Iu0PdgTI6G85EcM
6eOjhTfPoUXQl6PZTSKYNT6ebj7L/B3x99arXBb9BoYdB7GyENWmfFJfZLFli52pVwfCt+uPUxWZ
FD+bfXmhyJnZx07izDox7fktOmt93QaF+brM05Xtq1UQhFysP35o491XIar9iCWTxkmSY4sEYEYo
ixMCpRjSLQTsTbDu24U11Z641CbAwqGy3hk9+s8RqciWU85bblxJqyp+Xau3lQJDvfy7dqt43/oz
5V6GUbovqFyALxEwIRwBF7kASldmoQ7dWXsrYHfXdKWjKPAc8ZmHmulXUJvP6oPhU9dsKuys3skS
ZBZP3L3fDjp93LUryrXnIbbdAP1M4oTM1G3RElFGWvs8qVVIPCfgBQ9EuNWXIF5u3FlcRELyS/q5
SXcGJVWvrNhecIyvwt+ZstdpVe8Y9CffB9hHaiJNKv6lOhVLa67m/pfg9L36/V5l3WZgtn7dZNkR
0vb6Nt94e3A8iAKRRjA9TFFJYkBiB0xZGRCjlkY+MJNWZq8V4UN1AmzG1px8Lnn1+0XHh4VrOSJa
2sTJaiPjPXIrFpd85fzIYa3KWZ+RmfDWLCUK2tKyuoeQocRow95Rva6M8FWyfo7WwLBs9odLo/Wg
XTX3NWrfN04MscVLFU/34bPs01G51LNRQ6hoKTqN2/VpTStYyzq8sOtWbXGtZG9qh/i6qYRgUMyH
wKKCMByjIiprpUH0U9Ig94MgxlnanwzaetVA3/PuabGl+s8hxZnweB2bprFSghCARIRzobTqry08
75P0nN1ty68SuDle+T3jT0rpQL0R7+yJn2Ue5+98a8Odh6MfxbtTROBUg7Opy0v2ydWhBos5WI3y
codbVJCQz/M6F1z3xL1LhWpuSMvkss9OX9v27SnmXjBCs63vGQ8uJVqOkyfSfxDLHGHKIUln7aS2
iswHz8fn8MPf28m6oioncFKIylqoiIiIneSFqqqiqqqvlCFq8tvJ2+fv7+ou78g+fGbsPfHeOBER
6wEcHkPKQoaOHpjzLvR2yvM6YXYg9bdtg++pkdypT0teVR5KQ5rdbPw4EbDxnFxbOplNVN6S1xxl
yZaaNNkP8sAElUEhCYLUkyeCLnOZ83BoC8LVM773M9nfdvjHW3yVBtSZYWj2s1nqNWeJpgdAgVW2
tgZyc40tdBPWKsQWtCsXALbYzL75aHkwhorw105HceeB2ra9sHyeafluk+wGBNghYE7HSKKiBVaV
PmF6JxXU/jK/VL0ZQ+unv7UM0tlWX8hfhWs19Jt1tg5Z5RXUPLhPx1+i3zUdvR5fMZ7U7+3BFArV
QiIhxS9iLc31PDl0FWU4OkUW9zrpuhsgpRv1WhpAYgtKcPTD1RIKH+QHtTw5gYrx0bXahmOyWKae
6hz8MYQc1L7sITY5D7QACiTGheTb2FFr5FLwyUX1MSOwIb8r8Zs5UeU7uDsIHl2PudPc825zZFCf
9PoP05Jf1tER7tyR7fizH3c354O5fMdBo/dIf9kH0UcDDd+eiNPos6oEDpdm8/5vj+Dxex09w92l
gx8tUctT+92fDTHZtuyL43fdy1PQKDW9NjnYNXrJ/m2tfQ9+mFNde76+rV4/l90ODurINwIIIIII
IICCCCCCCCCczgczrOZ1HUdDM0KNDQ0NDQ0MjQ0LGhoaGhoYmhoaGBoaGhoYGhoaGhiaGhoaGhoa
GhoaGhY0NDQ0NDI0NCjQ0NDQ0NDM0GhoaGhoaGhocNx831d3pk9FT3va/4esPpEFARCIgKEUIoKA
oQRAUBQUFBQUBQUIKBEEBQUAUAUBQgoKChIoIhBQIoChFAUAUIPXx0n3vtZw5CxlQVjFLKQRQbJR
RgQUEYshHIp+YBqtUiiWtZ+puApFCh8SbPgYRGUSGBU+mRUKDJObPydv9rD/kmwH4mn6vGFyIbeP
6Xsp+B/mHVNxLoHGe6iGtnm8tAgkrNPr6tGcJDT5/mxHqnqnsCytu3P0k0ghuK3HCmLcMMBfZuPr
3fz6VF2NUMKS2eOCMmzxr1L/h/N+h6jvs7z1qMSgooPkKKLFgooiigooiigooiigoolFFFBRRFFB
RRFFBRRFFBRRNY3f+MqNBOqkjkzxf3fPy5GQynnG63px8tl1/66+h5rGArQ1gym3OX/a/X1DgYQr
RVAdEKJOiwRDkjdCwvaa2etmyDcQ/lQLv08hVuHOHQfz0pDWEfHdyVdexymwfFsqaP746JaGTHj4
p/E5Iv7s254inH6JwisM3Y2f7KCdNcuPV1ZqtdLqOZ7iJS9jwZ37Jy8XEY9LC/a2Zudd11P5Ke92
kxQ4+ttP8W8hZZn9Ep5Hkqz6P9PqHt+v9uILa5s/wm/6mqj/yf7mz/l23tNaU6vXY8pYDz+l+2BF
4WYu4OxfLHye8/n83vPW3eqSgGjzQdoYjKL6McZDmTs64UfX2zJw8yI5fXpjjc9EC+8FA/6qR4aP
VpQrBIikoA+09/AyUxZZeNMb97VrOS1iR3S2PhR3R9/PfVJCfho3z6TbvLAi4u121/nVKgiAs2AA
Qg7rZQxT5+H/Shlw1LrOknIrzUbvxFZ8LRKpq9BL0Pz9FpT6eam6Zq6yMMx/mWJN6/f9yTh74bn/
Qxkz5SXrXCgdm7so1BJFe7nC2o907vbngch+cu8ZFcD6o+eiIjaG0kgfSmS0JSJBn7IyBA4t2Pqu
4bOsapE3AxK2uYfxih5J7YyOUVKx7vi9O818V6Gwi60mr8Ca+lNjilgRYsgiyIBpkh2dtJMI7s7R
oPKKnoHEojxhrTnhBgfs1HonY05cd/XyP8GpauKu5hf9kf5bYK3sHzJfbup65SKC/fOT5P9q8qqP
wuBhCeyD9Q9ddMcwCQLqjLwvG/qTddq7iVYUJ5+ZmnHze3dOv4O32FHYVqL7V4A9eyQMm4FmwhIP
Fy823Q3Pe2+YmtZfJ6PCB+IRH2KURtClSFbS1hGAxoMtrKhZTsKHBED0UoVLO8tnpho3y3hUYmVs
qITH2UtRBP/FRHhhwstRQ6RZ69tLJM3NaOw7k9h6c+lqw+gkHnzhJKiMqHpzX2+LaczkUUd55T3z
6j6j6j7B9RoXLli5cuXLly5mXLlzAuXLly5cyLly5cxLly5cuYly5cuXMi5cuXMC5cuXLlzMuXLl
i5cuXLly5oXLlFy5cuXLly5uLi5cuXLly5cuXPre8eAEbbJ2+Pnt7mSDphGc6pi1PjVJSYZmOw2U
QglHq//7tVbmg+G0knqEJShxEFyqeJDaSdA2bnwtRYMGq6xs2Y1FA0N+AdSPO1ebnut4DGEe0OLV
BlChSh4vDcpxRbNKD744SW3hBo5NgqB2X63Y7vCNX5EM+nYQbCvSTRamrEbuUTUvigPK3xKpRRNE
8CS0k5geur2eHF1MdedH4LOszRsrR53T0DrMGN7znLodTKPbrdJcoAyfZ8TdSvF6bsWUqQUdWx69
d81UCO2MIvFezMV1xycdRvdv4/nxha4L9p1PPu5ZOeeGuj8Rr09XUoocvj+1/Dk4qoYY4PY2ZgzQ
bYWmkR/ISQ5GUvQ6dRd0lIzIyhbWNpzN62UrYMgvSCsdTqGPUDQYDETEMTG8K50o0kCy3mOM860P
g7ktm1sjN6G0wUim4GTJLHkEM+mE8qMSE+uxBiD89KxB7C/R8hNpjY+f+59hXbcymyjDeP9Frtfr
TBGxFcbeq0kgWiL+eMHvhoaEKGZmxZzNjBDpijHbJLu7Gjda6K+CYjdz54INtfbjwARcgYnWMS5Y
noInh4p3noO8O8zAhpRc4gfCKGm7bvUnTlYBhGAYwCm8oGMAw5UDIgVNNFKxTRFNEUygEjlAMc8s
6WGQsUcsytJocBcHUPOAlcKAYwZdTTBxitZN022p2prsobpDTBcZJjJ2oAockrDhkdrIbIHDUnUk
CJgoIKrVA9GBEta+nRJBQMg4ZDAWDIfdDOzIrWb0xnz5OBbCZTKWMGdljAyMjgcDgaDQaDhIvgtL
GMO4qiqq4YBnBgZVVVBIDUGDUW0TAVTN775zkyQQiByKOjYigdi+2fKczIGwRYQ4SyMnJCU6nsl7
zRpZsMJuG222222G3ERxMzOG3PLXHKQdLOcwTpNzrWtarOconThzrWtarOcgDTbnWta1UREPEREP
ERETiIiURERFIiGiIiIisQsRERGWWOV2IZY1clEagNkBIhG7Ggo1ZFGheBJRk8CR8jOizghtwQyy
GRAjbA6GNhsMZGC8DIocxYNgsCQUGWWWA45aBINw2bMRKOsvyA2GRff4GWL6WvkINBqOIWWWWXCL
4MPiDGhYdTYLHuGQILMmyGFMvMfvcd5afJNVKpVJ+g0WoL0lMSE4UZXuvJqMkJ5F6UEsExmmuiLF
hWVxEKFUoWBHVAcml5NVZTROwqZFErNSEEGwPYEKOwYUC0yvDuNoYSeg1YmAEgwmLDAbRTYuhtAR
DU2mxFVcjJqmGsw06NONwNFTF9pT/3ub2be5rPJ0TZy5s6fYXcnc7+/Z0bll2rhL54uDNkwd75dJ
vt97pjHom4lUVRVFIKHvMFlkZIiVhBYQUJASAlQZAWcGQNTScVJswnSbjnDjDuQC8RdaI8JwcZu8
87FNsx9NCdXNF4lJKiwyCMh0wDIddWx0dFwRKrZOhKuVvhb2k0yScKlkVOUYRhC2rSpGXxrGbqtL
UpWK1vZzIin+AURKQDUDV97YatHe0GowELJc7rWAm3STSEzczxMjocDkdRzOo6jbgknF56c6T8qu
aD1rZljqOZzOZzOZzOZtDr1CBxGehyDkacHWbTBq7WjRjRXIaoPKDzAXlAcf7BdNIWQqC69XKnsH
Y7A4aXSgqGat7pIEVMJwJ4ESxnJSdk2VtWWVn9SstIQD07k7Z1YbDAdgJ1pkBhkZZSMs4K9pezeo
w9jtwQzfNvnSNW9SzJ0cSTcgLDTC3GHEGDhcY1SF7k7zc2S+9rylkvxGi4Rc49xUo5WuHhUtHLdv
smaR0pqTJNoLugLndyag3BSryZZ7XYKOV0KM4y51Ma4rC+qhW/fHzfJfNu2/LnwNKtqLyRE41zUc
6QygqQhcixGIkD2Eg0EMQxDBQo4LRqAYio1CZWl2uJcW/QPMuo+XA0ruSOhbl3LY3AoZ2ryGGAYB
eTrsNZQQ0JCaVDtQ9VvscZoLBpyPl1Y/MFsDq0G5dLHStV41sHGITnyqIS7eUC67YGQVEQyNpkNV
B2ZOZNVU4uvTgoMK1NMpKpXq9ADMqC3MGYNRTfJLEzrAyhcMjMVvHqJPRpPi0jg73e6He6LqNK6Q
3B0tjLlBWhjwM91rDBzXrUjOtBgVq9UsmLc94d+cJwtNYNRgWFvqoVqUVFprvsNBgtp5ErMwvKCH
buO4qm6XVUIoPx6pnFq3h1gjFAsQBffUbS06B5uIG4maiREgajgcySMSZUWm4scdVmVKEi45ik5/
auBoNQo+g787nb6e2hCCQSHdFKEU7QFqop3Di7mfldbwnlOoyTtja/z9a/oTNJxhpFgVUiWBYU7g
wKMDIcqAWHd3cu7uO46yZ0k6HJFUdQWvNOSY7QiMwzW+/etoeQ1CUpvSc6s8e4uIgMjIwFLrTWzj
WQceszMTkcS5xNj7XBB9uW5z4WME4nvHI4nE4nE4nE4m9NpaGmE+vXWndO6YVK+vOG9fn2HUL7rH
dMKJkY2hao5PQ6sxwZzhKrqpu4bMc9mp1AI5uUSuZzVQoOps1QlUsmCRMNvYtDNlNDOjFnpx39R1
GWZftZjEsIyHHTIPIZEZrkkSWmEamN8kw4AZw2D1+4ZJCSg4MFvskSSxj21ICQIBHZfBnIaCaSyn
JGuhxOU0wGZHBQcqyWGIa4wsg2iAEC3Ly0GgcpJwwKWwjHkdpkzY6WqmxhZptJBsC86YDQUm/CK0
dmTjBQ+o8EBoCde5uWw2E64pTvY336T1JAaCDswZlhbsuw2GZJFdC25GPC1EeopvftWZa4bAhOFy
bDYYK5TvRMW+lbr4KHRQsQGgOrUUpsNhce0/qHwUCrIcpZexrsxsiXJ4Jctm9ns/lBYgy0eWovLl
EpHn+68ViqjlJnIahxuKTmNJYUnFTW30mc2/CzQdBycn3nfoN53ug5m9+FqhXY976XN50e52tz0/
pfY9z6nmOoQDyHaJAgsYhCPIiPlUR2nIR4l5nDnDsCPA4ytn2wRVYgilamAcgZJhBkBkRk1JBJIk
keSGog0aH3BXFnal2otow6Ie+sb73CcqtqixCbEyryuPDPw7gYA0B8Aam85G45G8+HqTY2PfN5sb
GxsbGgepm8UY0dDhobhuom8mvhxBExhcYkQ6BU4TkK0BcJtgJELhaq6Jzjm3PFlYqllQ35locpUK
mtk4TuchMkReZS7Djy2OZnMbEgSSF048SEQwqb2fQdGz5Hcr2sqokFVmHQdBKtDgS4i8yR0ryMn2
2solxfWSG5OivBxenfvoOgdLLQRTRPudiYKp3rksWVeIC4UtSNDnvQOl16TQrrDA2EbMxVprDMGi
WF6jm1GgVTrSjJxNbBkGS8VzSTL53PMqdoDXc5M8HE9hwHkI9NseZyNj0yeCDueeOC8+3XXQdBS3
AlfMY5K2KYLIWKtQIDtV/WKInMgsuOjeuayF8vAjHrNQ4tL9eReSG7VchbtZUs5QWGYYcXjGBIkd
C2Ei0xOpcqzoWK5luQu3goropWKC/JyoU1Yulcp5n5E9ydCQ7yD0PAKKFSiU4vWkcyvWdZuDnDUh
fvv7nJ1LqYOFWi1QrVqtXTMmSZOZkDCI33G4oY2FO9DQq62UykGhE0BOIc3y2q4lUKwrvaLzNqMK
81x33oDAFAMD0nE1NjY2Pgampqe4bGpqampqTEsL10YTQYB+V94oFKKyC2Xaw+973udyMGA135MI
WKhZUta035dGJHhUmzPc3Y8zaF1oRtRN+6gOYRfHd5atiNe0rwKltJRtC/VH77DYNC2pSsxPkSUU
4Pi+fC1hVrkMhWux6dt8Hjk+KX3pYGFnvXqNBwExJQqoUQJfdRPbwTyeYYXAYBkCf3w16HY8yD7E
riLN2Oli15CtoNBfgv0Nc9R60poyY1kMg1FEdPOi3PI9u7YHpXAYDlJVY4JZX1ipLR4K5OIhu2tB
oLZHaAvMrQ5Y+Oea3HU9xPNTAmmz6NvsLxIfQEk0mITMqisIJcKhY7Hje9HahQ2OSKUoOWHdvsM5
YtJaOIkBxrVhaYGY9CuXShdq3dqs8F8jDl1nU828BdCpQ6HahAjHaeAU3nGdAeMOYXwGuFcBnBgg
VBg8ANlnhss7N5QGUNhsKKE7RQwBBCedoVxV3tjhaEa3zOyw2t5GU3vJpSbjcamJ5jU3FzUuXLlz
0mogICAgKIGN7RGvoMA81QEXS4VtVjU6a1rV017e3XyqY5OOb6zkOgom+b0p8WIBeOEJFNFQwEtW
p2CSdxOBPoORiRRSuTV9FLmg0F4K01I9oxo9qCUxhcBgH2XMJkbabTwfQWx2Fjz0GgpLb3D/Jike
irQIB43hPB3E8h4mdIb+xL6812GwfB0mUKqY8ykG35bAYCxWxS7jDGDypgxVC4XD2IIU0QT9LXNn
rNumUUGU2famiBeUmzkOU1lBYOGNJWP7VRga1UEiRtJruXgqNStXMuhdBwWkWKw1VeS1KpW9XWpg
gxA5SZzKtAyTKs50txcGwLxKgk+NYosqwc5VucpunTNg0ENCjM49CygkoWzY3dsOIVLKVYmwt0FV
sq3aMtsmJRgZGJke2XNxsXLly4QHwC4QEBAQWTexsLkLhWilaUznNc5iamkzjckEGtuiyK1DYbrc
pIW+hmwCInuK42s50bAYBiqg4oqC/FJVdVoFAexU4zUckSFvtHFJemjgvouHT7DYUsRP2nGRPp2f
RZOAqX4qvF1NhsGpw+ac7Mli16LzfKwvi+Q0F5po4LiwV+Xlg5D6qpjg68XDgNUft8CnJS1Do7bS
xfJWq3DIT5ME9fSW3wZKhGTfn44DgKeo7G9pzqevr2pEzzM+vJKdS6zMsrQ6MmKjE1m4oZPGWNAe
l8rsfGa3UPca2iO18j0PM7ESoC8qJmSWY1pUBiGAlJ1JwavkYJPBrGsaivGBQwKTSH8sYw1ptWiY
eVSUmd7uw48lrJoi2Vb7+TM3GhmcDM1PKam8uXLly5AegXCAgISISNCMkk55Oa2pmWw0FqIIeCd7
Z4vxHF+C4iCbIEWQKngmXLc5WWltjkOQtoT8xMduowcpUwRoNWrVbaDQfejFipkknzHt4OCFQZiT
DaDNlmDMF9EMr2JczzyQcFMtCuORQFgS0j6zJnbe0kVhOUgoCNGgW0dSd+owM6oLQ5tkMhPSJ5Ck
xO6OWDnnsKtwuFPWbMndy5GWPXmq4DAWqeRwG7chQwZUnRbhcKOklRSMsenWWlac7agTYQ6+eO+H
o6Nd0Mevkt3163z1cOL5JCXRk9wp7SDhHwLMZzwijDlTJk8j3J9mSByo2HWtKjAsOIriNaY03cVK
pSVaeqAgUrOKgDJc5Oj3InsD4AfEPAiX8TJjjouAXC4xi1hbwArPq0tKMoYTG94jc43jUa08Mb0s
Vai58mQMzM0NDM3G49JsXi5cuXLlz1C4QGapwcDqQ630EBXJpZ1rrWrZYskypoA7HTljgK54DgJw
c2qcq+DkqYDFDrIZCCq7F4FTk1yXcqZDOAwD7Oj4WBMeZqQg2nCxkOOdBoJ89K/sHLBFl+KHfuni
AyEZ8Ez1jmTupHJcLhTyHFjoG1g8EfcwXMmlO1c2DYVz5kxuEcgMD2CwTqdzkuWJGihcNdulyGQo
5WNbzk9/AdnFmZ7WPY53NHqOhg8zBmMiJrLiY8kWGh9JAkeI9hwkLt6MhVAWl5c8Gg9QHIewDkRP
ZijiPJFwi4XGMWLwLRJWayD18YlR6sUuVMUlWjzwWtUo1Cla0slK+PMIGBiZmZoalzebjcbjcbjc
bjceAQGaIiQKJwcBl10Fg1QectW1rWtUM1DZk2HFigcBxeqloGRt8MU0TDdCh9hBsHvkMh7kCK9H
WU9ZMYUVJmA4yhwzNkMh9Ij1o2FWGokJxIsEp4ZOlYFgTqyoaPJCBG91DzRYJZoZcW4ZCvoOghs+
sR7ZzdzIiYDAU0T8yssEyd2vRy4ie7VrRkMg0kELeoZL+Z7ib73RzYiTfAYDtTBk4YsrjYjD4QR1
wGAfBb3GzyOX8HqNtuzbKSYccYpweDj1eBcmPIqXOGJnmaSsqJkC850HaufLKUxzdRWRzMiHg4eZ
aXCCPtC9yG+BF6OY6a8fe1I8eBRt4xjApeqBBKSvwEw2UEFGiAa1arAktY0MAgyCC86bvKpGLJBg
gHLQrLkEGijiogZ74jZ42i1kRiIikEp1E3QE6mHs/Ds67X4nt0u1szHGUXiPspTkzSvpf5Hubn11
A92YI5r9VDkgEv4qwz5dqX8awjwgTYKpafVGkO1D1+LrN1CDRpiWPxOsfShHWPEj8qEIml5ax+Dq
c2jz8eXv43zcovy216Z3A05WYVTKz+7Nlsr+ycbm+5sq2bTZSosVMarnFGx0GA/QZHT+zqI55lGY
ZQDVkigfA7MDNrAxmJIaZjgkDFSoV7ZRcIheVIMI3PRCpiBiF1W0Nc2ysDCJLplRLtvFKR5MHsHE
SRL3J5X7WzlbsAPWj1IE5mPpLJX2M5ub1s5n9OZ06ZShE+iN0+p4seZ8CqFTjKHiddrnOPvk4+FR
9L7hNdi78M8qlDG10cx7no/eZfXeiMocz8m5WbTKiywMvZZe4QDciYtjz98vSBRiIrBFFUEUSIne
soUKMISQIqEkTrQaU5TSauQdH2GTtNh5QasPjh1ej76JwIGzSkjiImDQfug4xQS+DP5V9g8meUzY
7LISagfyxYKqCMUS8+97F9D6m8fyKfnF5vM+4w/jco+gRMsveUP5tH8Wzc5v8hLi2bV0AVxH5vn2
YjoMEiH0htkhqhH8nrp+/wjejJIHNKCEkGVE/3Jc/yf9jWv+f+VZYR1ILS1R99R+LnVo4VK2sUU8
vdCPJNgv8P9z3h3heBjJjrF3s7FGWeTzbv8bBth+rABoDzhR1b9V7pIZCEDdCF8HoluA2JKYjR7P
OeydxeM2XwVl4uccsIDDPJvt2IPxTYfznXFdFzAyHA1TzolFGtUdMyNv4AumoNYj9kv4ImqZUyNj
g5ukmGRmynOSiYR6cxmm51R469s3OR0m44LKS3JJ0W1G/WO2qnbz2oZy6YYZneQ/WuU9kLetcLZy
qlentdUxmIjBCihRMAphwqnV23ZMAN38NDuFhZDLtNNdYgRDPiPQ1A54czUX0LRuCbLsOUs3jwob
N98zrPGv4JmNBlJmg53vPFU87P3bk6zLzUV1gwjOdv6nHew5494Vc/0FSWSxWGdTRaH7ajtbtO5a
BQkk+EOHaHH4O3DUCAH76U3DAbkidTwnSRPOg88nE4JwbClVaaEE0RFCKwn36a0w4zZxSS6HvinP
MtPDeLld1OuqfHDtj4yTAD8NKLwNKFBAu8MLoG4D1FJ2w2/kHVIYq4IWpM4NiyZABJ5oU7noleO6
E4iiNm0aB8CHYgo7MsoQIn80DBv0iUKXaLunvTaLl2/wIY7EFaN7CKCBERG0eqkwvgynr94exmME
e74TCA+KdWtipIOGfGDaG3i3jCeb40bzmykHLfOMmm6emkenwt5xmDSbNAnHZoxXs0o9qzeq8hkT
RgFW5oX4jHsZQkChtcSzYItjAAg0BjgCaKxzSdMV4aCGM0mck3Wllh2RhGCjBRgEPDs7Ds2fj+BP
DBHHidQarItiJVONqank4d9r+NHA5tVGHegozjLw2MMPhqRPjr3cp3JSYJQtdo5Sdeafho9VCyvv
HJb0KoCEgFB4NB7A4PJ1SclGKeLl4XNdlq35Tdi10Ifg3jzc8bA928Dlvd9nNgbHmdtiHaRQ9JId
FBkrfeJTE5VrPGbhOBnLJ84EQjfA/95W2LgyPoZEPjp0Tt6aN5B6KU1ocW55nYG4JPWjR8gg7TKc
TmCi8YIFs+kXSwaukucJ9Wu5d4kGopFQnfHg82DxZG6MbIslDTDBAw5JdKTAkN6k4hNzwNrKtHyh
vq4VxdgftP54RmGG+uH3sYnuf90vvb3snrPl28UfI8S3JCwA8NKuJ0HtHkmVQ58vjvQ1PgkEYN/s
s0T7uW0r0tSi0QtH32pPBP5SalGKE/41icgAzF2Ch7X2OdZOm/R0fYE+0J+SH9JKQg9AeAD3o1/G
9VUl9g/PKDBIt42YFwWxtRKRX9tQbxyoWSBMHg+0muqWf7GrjcPuhzJui3UO6+zDec4HWIoqWYZD
hBDQ90JIkCtM0LjI5VM0BmPhMkmwgyQQDk/4A7NHgFmsEHb9PIMezY6rCPIMgc0QTAgbinYpVlUk
yNYLQiUM6NUCoLpBD9yZ3P7j88vgSVJzbLgxUmmhCkRCcTUxScRFUh3BAhDcaPdygd2vCcE69sKT
XdUYsYiI8HPAQevrNu4pLBrIKmerI2q4pkmybApiNQg/p1LtjJytFOkBCMQGAwEQlghrRz+zY7+O
BKd4JKCsWkWQLcFwTFVGMyi1Goq0K142nZPETbuNQJvu9e2JaoRkTWMQflaXuQxG4N4wvhVMBP3B
PsrKizRGqDocEjxM7eBlOGLKZA7zH6hDdnoEIHZDp5DwOIcBQgfLwxrSssYeTzf0+uKPztkMsT+g
rPwKCBsLH2Wf9/1Hga0hUFQx7x6BOJn4FxiVHJ9P47joVxSZiMTbaWGJcMcDQQUTbOx/Vg6MnJq4
3bmjvk/Sd/kgdb+vKNVb1rQh2kF9ZjZqRgDYDzlFC2k6jlPG4SNCdhrVEXtqBAbtsgLRikxN48zj
GYX6//TNqcH5Pq/TGUWTTDEsOraQgby43hpIGH7LA2GqAhMCViedI/GJs6WwISIhDo7Xd14tvqvg
FAYQYRFoTpfg0HfBQ1oUoCF9HdU4Sw/UHQcX9U+FdinFstE8VIHaFRqeCFl6qBuhr/rIpVADURVg
wEOWKBwRakKPxA+Z8mXFpaeg+21jMBSjOVIHhv+XR9Cb/Ts5ODye6kL5OHCt7HMJ2OkBPAnqoq+g
QE0HKBy6djdHMowiNGCZRUdAlCw8xY5i9teMD+Wm82agin23g3EV0+GanGBCJ1hFJXLAcI0rDESJ
l7FjUSgOYSijOQeoEsXTfvTo2oEwQJzSCLvKipPGTdPKs1GY9SqKeBIWcCQHYD7B5YgH+TtzCQsM
y96etCFt/r/PsO7Crgtj++XGPv+f5X+9iJ8DpN57K65ew9xuInewaZLQvOY8iVFMSs95A6hcUK0q
NMxy3EfFYHn7bC4YzmBp9HWm1mYyIXl8nFRWUFxQXlV9aB5iSoJketvuG6kGRhoOlUlmJrcm/w5H
S+Q/Y8/ocFQsGC0aEgRAkAjGChKwtohAZIeuJMkmB7c6K/IIUP6r+pw97P6n7f0bbae60FtLez5e
0zt/R7J2yHSREOlqiB+NirUn3xJWAkQtR/Xfy4WCHXAzHjfS1RFuiBJBkQOk9B7+jxCv1QAGREz7
YheRC9pRjFpT5T7lFq6/iXw9CikJyeApL4Eus1nieo7KDsPEgXOJGo9J6iJE8jzVJ6jTUWlJaRIF
BGB6x5QSITHjy8kUF5lyLQQJDjOxQ6Y40GswQrSwqInYSSgbzkG3jDK8cj7HOGb1JzltFbgLcgRY
YEDPADWRLyvA9ihuGN44ZmHI2HyuNZMuO+HKqGGYu0BAruecG87mptHK7AlKX2ZawCbAIh4knONO
LvDrebZ12CxVngoFsQzoZyezt6PpapRBAQVCQ3Id+z4tmPwm8aEnKKhnfWwP8KPHWn9kpJE5KXSf
wxfA2mGxPzlgdIA54rChB+cZD5vruGDbsPY+eeTxfqzikE9FFUSqhJoktl61/dWvg1gxkM5qTvGL
KFwBBV82EHyJPHNJzegG6IMwkgBaEoNUgYbLEoB18SFoVNK6EhCRSFthgNC5SLYEI519i9URYRSg
ILZpK1oEPYqWtE0SxUaneecPcaDawRj+1icgW3bdm6z0dc70WHuJjGYh7DU8b1DHsLCm1QFI5Clx
PfFui8ijpNJ7ChQU5odG7jUdppOoz5zQbTcaC81FPZNeUNig1hVKFViI0CRJCLCRxJQmYZlOTnHy
sGLuSw2NpxnUe0sNZqLDA/nSNJpWeRQRZAutJZMexiodiY9+OnHQVVGp28n/R/tM8xnWY08gqtGB
tgDpnvSsRBNgkkea6jca9w85DcoLxX0r3Akq6znELaD9aZQ2F7+VW/MrD1rendKqrT12nArU17By
mXCRcVOs91BqeppTzPfn4UVxE6/Dex00oF1FpJIPbw7Z4veeM8dJ/i7zq5O9sm/fN84t3e0cBDkQ
D2/W9C930QH2n5SzGPU6koQp6TD98kaZEIMVJlVH4tUIBNqk/rxJTKuHHIlySJn5sfh1nmoTHtgM
33SiNqRS1OjgytEjVnM3oAJF0BFmUS77apzjZsx1tTt0aqo8TV0U2OuuN058XanLqkNLqfF4LHLT
QTfOmvpJ7W3DE4m7tMbpLhkWTzrmtcugXSxQBUbslU6kvVQvvBRy6Ta69tJegnG8xD4wD2wnxVJm
mGS6jFb7JEkkhJpDvgXDIy2NtKLChlDk3QU5xDZxNCXLUk8XsFphU58pvkN9sZDIdw2kZRZZAsZU
HRGGaoTxdx8bg9j2eLlk6nTDNR3PdWbSjNwYOb229muq6vjV5G5sxYjzAHGjX66L4Y1uny9Dn7NL
q6eDa4umtBANZgWmBFSYZPO751kV1G0pHmByqp43pJEVIgPHjEjXysjjknH2iEqNSIPagw6BxiOM
WniAteaJHGJYcLDUbAjzcxWSxasRC5i2BdAkQoQrcTCyNGiYrYHM1nKeNzNnipmS4hgWKGUu8NAT
D87OvW6TrtzHKYo/Z4ijD0jsTTrURBYIATehwCC/pOo4ks1UuRQc9QHYycQk3opMr2kjWZfU0oGd
cpv50tYKlIk2tMaR/DIe8iin0VGVFJMM0lZJUFiym0EEwIOa6OU8JcIPEfQmXKe32xOU6zAz+mKt
+91pkmp0t2cheCDJN3naWRsWF8xYoFhLD43A7Xpe1DocbiJcMSmTqfheva38r9wUd3IJt5uTySns
pvVOCKh2xQJAEPMp9ZD44kUkWJAhCR90hBTQN0OgHx/B/bj7/uUetveWg+IQgUCCtYKQ62wfjgP6
LyXA/zsUwRLiAhs1Jxw8DLNgVxPZnI79ZdIk4HSfSavhP0Ie8/TrAIkQXIPGDgBqikgxBiG5iAUU
fS+sQ/NfjI8h0B/pIm9gcg97C2bGHQASTaZR9KmS7pwePOU00HjlESCS1eRe7zzfbTuI0WahURZg
UmLq+CFqayIZsjR1QvKiTdywPuGkaNTt+n4vaswyky2paGlpZQpvKZAE0obTbH3WDvKX4O3qmUi0
5ZFtT0vN53UgCqh3x3cHRu4KANiQIz0KQBSF8UfGcAAB4HlOyUhPTrsL7llQZFGBUqSCgFp5+Tmq
ayIaQDeq5EmYISgztp5yVgfFOKY4wwLzbcluEt0mw9ypVDyTaQFk9YQy6GNQXi9oQhHmE62e3dtE
xfSfzBKB79/iwiHIhpv8CJi9KI+7SREynk4T3SHcPA/YkkMHCHsM79sySqapBjUCLTZCxWEQnL7E
Uu2p9kAD2u2nAoIDV5Q8fyH1EMREubwXHEKFX4s6pUSEhIlgIChMcfy+1TeaJoiN7e2SGMKKTEPu
hQ303jC1VKCoiYzZUku/RcG0u0SzZ8KnFrE+zObF888s+hpfscl+LunNg3MXB5kian0968yHlpKL
fQ2eVqwdb1fL5HxFb2c/GrjEqGMita4jXiFkYntTxAohrHAjFcNg7GeInKIwUDSwAuVf1QPkR5x1
vO8nu9oFn72BZ+ymPbD4j88CdePjsWjFEd+ZyTs5RLeRBxsg1QXwMVnzP5KSWpb7Z0sLo5DNES2q
hZ8N1bHdfUfC9rq9hVHj41S/4580++RB2HFlrljiyPTX26IUJhtEqFGIClTf7C4BNL3eFDvauWR1
a61hJE87e9x6OY9753QhzvqenlBX4SCFoI0rDcBvsnOySRvIR7DZHA+6UyJhQzrrFzdq3li9YvA8
ykqK2QMkHlk2qCglBCAsU5zsIh9v4PCG/meIhseVKOwY73TtVBBkiiWyg3vJ86Fvv9av+ZV7VkrU
E/j4i8eN4xM+wtW1Uz9dGAkBkjUKR5Eyn0IXIrVzC9i6fBkjqZ6qFPGMqBiYzLjmpJ7ZqYjAmQm1
ELQo+NuqPG5N6HidDpfU4AhoNFGTMEd/5v3lE+PjJ5Sr/r/KpazdCp2G90LpAQtdVDUUQ6eKPccV
6r+KCSSEIrISATr9mOgeJk0BX+jE9YUoNaqDKNGsV62+1Wj8ZboQst100sgwfW4O1qex7TWOrPZR
9TXS4pyHps+p47gO5DUxxCNXW1fOArVHAhzPqHaxwsGw5zBufibhLeZ0ymlFKJQYJZQiH2A+Yt35
BeCDyQvARoYQBSZiz7swJKc+n/rgfh7uiixYocipvnNSgQ5NqmB9ukPfCSEZ+Khqr3lZT++qVkhW
lCUp+XdRTlTNR1Boo/c2Gx7GpetXgBRFdz7xOxMUH70QFrFA/XFXLyDndLlkakQpPO5z6lvPOTcQ
tMiooWogIQSUV7yAvlOKo1C/WesyhxqZxxPoIOYLMAuohy1dGmFCCTx3nuE+s8ngkj3XHL2aNmpb
HgB4IenJcmLks7fi3uEEhUDDOxtNh5Wg1PafCkvvsvmJINh8f7+sy2FkUZnlyGjQllEFixQMkpWB
096BZAmvydeNu12MAJGRgjFTm3LshzPIQfqdvtezyQy3DnEIEYhFjOPlKcOz4Nx8Dki7iUDyJcPq
CoMCo9gABmvBNlHqj/vupcpKFFkgMOJ0jUr89DR3AFxEuE2a2DS2TpYY2LGjKibHGh7GAZnrfaaH
TzP4mryHtC4fmd2o9U2xQkRCkAoBBJO1sn4X8Hgp9Lvbz4X7O9zfSZPNZ77HwOsuepv0NCoo/p5U
Hyh6/xUToh7Z7anXWHxi8oXEd6y7m8sFfqPUvmXctfB5tdNHthzuKAX2Jylw9q4CYpHrfF67wvip
dynhRqqVgh9IIc3s9vEsylZRKQpoIDJjIj9jf0ft+nUkC0MKBSEQJBSRWRE0CjzPE/RxvQ1fv/fw
MQXdzmZdfo9Q3vye85UV525yvs3ve1fkgIKxIfhJ79bQgNhaShzy4oMKVZ2y6sk+Vr7FCGFG65wq
si4PjWW+B1L3MAMnOPI4GRPmydMbDQYnDEKFMaKm4Tm/uZ5giCG9PJiQCPqn7D9VKmyjfhAkwNLU
4GzRHld7y/98wlQ3h6aNy9DRHnVDjSGUNTANi6gRmM70OWrCD3WFEVBEixEYopEGPx0pBhxAApCe
3BwEgTlVFs5iIBvLvre8cG5QTuBDysE5oGNZRYRSRZFTN6o4RzAArmCGQ6r6cqbnjxdOs4zXqBzX
QRzWwqmmISISI6/2SkB9fLXaZtwUBrryBiRZP1sDouhTRFeaLU6XZxoZj6J8uGAF5CjOaSFx0jOl
yjzOv5PQquVNNGAMSSeVgHKKA7eVqO9IGQsS3iZvR85vYKO0qHZiqN5V481KwU1kaYUJf68ohBYh
IAskHsshZ/AJwowgsGqKERWPwup3uWlvGkDAzxrUQ/L7ec6H+kOq8TFzx9uIY/Zj2ljIFwvi1+si
fTLd9M8FHTqFVGpqB7nJ6soxj3sD5jlc04i3AuZAQ5gPQFIJ6DuDjIRhtQOG3BN0/FShJlPRKxvg
X2Q+iFT04lCR4ROVDR7Gr7XnOxgTaxR/C3Hi8Gw/nXPb1dAsYxj7Hq7YHcCEgiB12h5aNI3WJZOH
B5ETS0rvntLz6PXNR47icbhENkG8yR+YUdpgx1mJ86OjwBA+PCg4ItR740oFUJhSJ6l0k60TORaj
WUjRT+tdyNuFgKsR1w6dReYuzsq8/P4faYozfme7q3jPehtAv4L4BgLBScROGoWjWZAgd/zfg2So
QOjEtuOS7e9dsatbJoaJ58rNO+1mjBM1mZmUMCBWuKOoAyz0UxNCEsm2Btk1NU5YeziWk2L86Qmc
hiQhhPC44VBbygK0dSJBCqkzpSSVLG0hPNzNjtjsCJy63JIUkwmH+0pLmi4SwAbMFWRlpKkhPTbN
SFOu0swMhO0orSqmysdI8LiwqEEhAgARYuDE3JcKSAeTLOZKgyCAzsYFj8U9MfNH0KxVZWmAiDhe
tu5lDk6y8PO9e5C9CxXmbULO0N4HZC0BxzBgA+lr878rQBsRuodRDmYHtMhpJDEooMjjBuAZZBiG
jKJjZK2wwtkJgwNqsDciQJkSAre8E4oQPtnwx6JCHNWj5/ZcVPfPfGhc3IuUrT50Oe94hqnJmM+N
LhQPmnfPud8k9yfBd6OqV9g0awW0CRe6L85HnIBdhQUL4iygloVSLlzN7XqbPh8COWzPNCac32vg
PnU8RrHqUWrNtO2JJ1Ioh+wmE3Dfuhqk+4IvF96L5s8ATloe7xlOu3RwMhRrqN8VRLIod7KNdhud
/Len90EZDznxPSOTF2q+GlIQCDiwOUiLcpOqgFHO/nlwmegsJsIx45m6HKhVTNJPucO1Xq+UjUY7
fImcLKgE5mCdRDnbeHZ19/XCSpteRxdTldQ3Vqn22ygfOwjHijaEg3S/YPHTaisPYgBQF3sN++ZP
vrzCfVGSMRUSAqxRRRRViiIKsWRCJMM/h9WvX4vNLX6qWtJSUtmL16SOghC3W8S/IXoeLHDiUTfE
PIxggyAAiyEQRIiQSIHCWMi10DdEkZGnHADxQOmKDl/QR64oSB+1vB6Zms5HPI4X+ri7vM/wZ5gT
QGcNzt8vMJ4hpvGRICQQjw44LkLyBkl2/4vkPA5Npi/s/eUTiDdfRqAoco81PiyC30FEo0WHuj4i
wNGIkC0DnJ/KIcX5ml6D47AgW92t5TPAPVlSQS0wwRORDwNn5ALJC0AqCj/YfMI/ltBafK2SoP5e
FaVWK//v3fgw1+DWtt94v0N6HIwW1/c7fXr+ne7UQUO+z1eSQmfPqAxRq3FYVQaf1eA+kUZzJgI/
W+ABDoenAqdPpE8m3soG1XYZ+xHUDh4vY/uQ97953N5uQQx0fUUTiCbFjOBc7U/MKPN4/xYqYmGB
dHqs8HvZNFyi5wppO/QCDMa/EL2AYj21VDzredD9IQuNKN1e6koJ94iPCmVdel2nYfuSIevWL+Fx
zIH65zH4ddTt9zfXleLaeV2Pz/lelq/hfx+AkD5GI/SprMhXqZLuBITAPkRXcuxdR9K49q8AQXDK
pqdr360f/wCHOCFXHc7mwfV2cPGVsyqUn3YIIIyLA+G0ZEgCwPt+b4g+J2u0lEqx+Wfifora5/GX
mrlPT3jxWTzRDnYUBIMYCFILGNhQJJYjBVIwWDLaRQSCMMcAypFQskYBWfD0lMRXU07eXneewdvb
TW+119za0XTCQNgxENAwbC32KjaEFD+h9TggBaAsEuVDUMRFjE7OP08DS+NuyUwyOfLBGx3hfRCM
YEIemWcA4gqjKASqylbEdBkJZIwm/iT9NPj6/yfJIHwfKseVtqQ8D5qS419t9175r7ReaXwBA+pm
TLvGyc5Fj3fwYCu8Iv6h3bQhM03xS/F1aGQGMaKyfkB6v4Cej6qiPhNRoUkgCeOg0hNniHZUD6HF
5cUV0h24v5CqUz0HhHES40J0tS9qUPVFpsRj7nSjbM+RGuYaYh1gimo37RLdA7Kd3kFocXr/LZzP
SEClAUhFRCCgT5C0JUJ3GZ+bkeTeLxP9cB5K2HjIhWKZBJFIXUDnCwqUFSIMiFYKqUkgkgjSV9Tc
HndmA/edJymDkOcIF8Cn9UQosM+e46BQ9wIEou5QWiD/fq9JWq6VoxQRmkbX8drrAl9bm3JKTmu1
BKc8ObBcpbrY4FNuKHillcUcYqpbjQkQjnUDiAKGIk2lliaSy4igrMh6UBK5gnVVISkHOBufu4sg
I4xZ2iQVQE00B+z79dN8CNYar8tjnNVeweV6RGTkRISMZ6YyuxCxioMJALNTXYAq1GEt0ZGMDwve
hCpaO2+czQovTN5sMNjKHFrW6oc8ovJyUiy2d0sTHuKUZVgR4WphHixUVi6aJ1mlBugwwDMAkLbv
jb5vMfhsdFvz3zJ32HNYky6QTwxPfIYuBBSOMQzmJQWDA94Dp1HeER9zt0DBXGmez69ewR8+TgnM
6ihCEIRIQhJIcCHjmgsQzptgnKj4uUIPZLS+UVKZVMRjX3sM1ySjFiICIIn+S0FUEQRBERERGSCo
qKkBUW2iiiioqLhGEKi7z5j+zmEv5PuTx/o3oibbP4b9WnvBDr7kV0WYZOPEAPRyMOLkp4FXDgMp
2HhqVDrMQO7SockXWg9LcWcsm6zsdQGEBCl1091/aiEIsghXFxBe88C/bkXxQjJFWflg9sf1wpA9
b508xxdYp5Yl7m3tAOA7feMp7kpPCJ99wAFlsqsPzOMyHNAfO4V1rTD36ViDA1lGz7weFJdS4n37
9Zs2tbXebFf81nr5Xcrc4N9h4m4+7mJ0mxLyKcGSv89Of06kDJIhs66Sw49ckPW+q22222222222
2222222223kTruL4QnywNjhkOCtt1LsZkyyy5mTLZdg6pOA+IBkJ9Fn3QkLnqfadW0fQbxlxCzLt
hdtiUxBEiIGwOKLEWQ06gqQyBsWBYJtIdlimw2vxyB3+XRtz4Q/XkxPhzczeC5UMRz/ZK43TQxbw
S6h98vKAHo+oSuuidJ6VS9OjGUpQN22Xy2Wpj9mZMgkxbhA8aSHaQEEEgCKxjJFRJsJSkqBAQnHC
DkEFdptJ9uSnaIhWAxO522sDJ0YyYgRpMpyCChirkGaGtJsmIgKCSQ1ozdD5D+PYGpOkMIHSAFMH
kwGa4uSdAgdeWKfA3faiTlrN6XXE6t244zjLVI7ZzzkanUbyOTaORKR5cqfGdZab03CjzTI4wpTg
BKIiZrMM6GbVlYYzZ7NECKb35wQys0IIhBhAtJQHluXFlA6IFhHYGAM5xXytqxEbwOI05ba9+OAE
ZKhxKdKEjGMhKFAI6GqdcD3IBwAAfmPidK/EnK9fanHlblnsfoe54QZPGc2Z8DTptMWGwmUMNgLQ
aC+StckGxVxio3yQiwcAhZTCFiJgZMc1TFOSJjCoTCMjU0IUkeQ69uwhZ71PJUT4WRbKp7tPrVOl
5Ptsi66hJnQ87eU5djvavGu98ERNzf8bW7hysHcxBgomwEApMDv1RqQMDWKkeGkUUWHA15SlRrV/
QUUVGzLO2wNbP7WSKLMulzmH6nDspKKTlavBjtLklqWhVSg0PjcjlG4CvGlJf8Bgti1BBnM54mKG
kkZIkWseaqjVB/GhRROCgA3YGT2Xc4BZPcCDXgUDPETi6xLoTl8Uo/Yjjltd+IllDdvXmDPihxnw
jfhEvgQx93E1GY80yChg7yVYpgebcIZtO2+oNAA/dBgj1DCEULohzQSsSRpDnhhCJEIM8vmDx+IE
PANipVQuhC2tJt3p5zmEYg0+LEF4D+mjya3QbSPwtfvur0P4MV8woZiYQqsDKtIvO0o0nLoaVbUX
XEoAwClaKPydNX1N2XiFui9p5UNvndvlBNBqYldzgg3Ag4lx1KJbik39PFfjrXShYLuU9KjUa+yU
uRZFwId9aBkUc+vMYefYaXpx0n3fN/5Ik2CMhyawJWmFgOMNyhoeRoRCQAkUkUGEOOCkPA8jRLBa
EEokGC/9SKC/Q8hBUOLyUQP1HGXJ5DW4huT98Q/y3lCQYJLc7vfcno0ySaQsnsxGQyP403gGHwgq
f3yRNA25TnN+JYTHSflhJIOtUC57/d6H3W1SP0lCj7ymKDInqT2PfTYdboLw3peLzi/00zQwYmQQ
PQh3+tr1Qy7nTg0o0YEcihazaNX63zOi/AOCPW/RoF72AEfoYdT6BxE4FAQhAQjL9AQX2HofkcDd
BmGM+ylgwbvG0S/rY7W+/Qzg/O/V+N82xxNLiZKWbFLaAWfM2U2wdDwecx6vbSRvpRpqP+Gx0uRT
ifEcHqeG+QZAkU35HY8TZ4cZyzxjknA50I2pi+hsr2kvdpRUeVivviQgfSwboiZPloPjLJxN1na8
zQc51QwAThABfYfpfwPlO16mOHM6XUeNnY6R8PY80plRgfSFaJVsaTo0ODzOt0FGHWNNzehmZkkH
SGmIpQoDQOd8NS1qGp6Tuftdx4nhinRIl0Q/Xrve9lOuegMuMoiWNCFnZkcocr5guBCmPK7GpaYU
qIZksRkEUlfBGCJI5eB6CsURc5nESAzCAMCIM9Y3WcFB5pnKagIq0sBi3f254eecw9JN4HH9M9UH
UhDQUolAQjZKLS7SlhKnMeDN63cKPhlHLreD0x7Xk8BtQOx1ukNJeChi3irhAWE3UaIhtBd3m8Lx
cQ/A6XFuc/BKdjwdjve9uBeEUTkgJ0ORvHrbPAibOd5k3B0DvcXPueR43wPQx4P3+pQ8y/MH5f0+
gAuhH/3kdf6JP9W4OvBKkQEXpb1mTr12JoNrFZ9N/rF3JFOFCQ7sXx9A


--===============8797094868444187804==--