List:Commits« Previous MessageNext Message »
From:Evgeny Potemkin Date:September 7 2010 9:20am
Subject:Re: bzr commit into mysql-next-mr-opt-team branch (tor.didriksen:3215)
WL#1393
View as plain text  
Hi Tor,

Good work! It's much more than I expected:)
Still I have few minor objections, please see below.
This is a preliminary review, so no need to re-commit it right now.

Regards, Evgen.

On 09/07/10 09:45, Tor Didriksen wrote:
> #At file:///export/home/didrik/repo/next-mr-opt-team-wl1393-merge/ based on
> revid:epotemkin@stripped
>
>   3215 Tor Didriksen	2010-09-07
>        WL#1393 Optimizing filesort with small limit
>
>        note: there are some extra DBUG_PRINTs here that should go away in the final
> version ....
>
>        When limit*(sort_key_length+extra) 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/include/subquery.inc
>          Add explain to filesort subquery.
>       @ mysql-test/r/join_cache_jcl1.result
>          New explain result (key is not used when scanning tmp table)
>       @ mysql-test/r/myisam_mrr_none.result
>          New explain result when using PQ.
>       @ mysql-test/r/order_by_none.result
>          New explain results when using PQ.
>          Added new tests.
>       @ mysql-test/r/order_by_sortkey.result
>          New test.
>       @ mysql-test/r/select_none.result
>          New explain results when using PQ.
>          Fix typo in bug number.
>       @ mysql-test/r/subquery_none.result
>          New explain results when using PQ.
>       @ mysql-test/r/view.result
>          New explain result when using PQ.
>       @ 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()
>          New function explain_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() and explain_filesort() using priority queue:
>          - in JOIN::optimize(), don't do early return if we have SELECT_DESCRIBE,
>            since we need the tmp table to do proper explain.
>          - 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
>          - cleanup initialization of KEYUSE instance (debug and valgrind showed
> uninitialized data)
>          - 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.
>          - use explain_filesort()
>       @ 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/include/subquery.inc
>        mysql-test/r/join_cache_jcl1.result
>        mysql-test/r/myisam_mrr_none.result
>        mysql-test/r/order_by_none.result
>        mysql-test/r/select_none.result
>        mysql-test/r/subquery_none.result
>        mysql-test/r/view.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-09-07 05:45:36 +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-08-20 09:15:16 +0000
> +++ b/libmysqld/Makefile.am	2010-09-07 05:45:36 +0000
> @@ -48,6 +48,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-06-25 09:34:37 +0000
> +++ b/mysql-test/include/order_by.inc	2010-09-07 05:45:36 +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-07-23 17:51:11 +0000
> +++ b/mysql-test/include/select.inc	2010-09-07 05:45:36 +0000
> @@ -4145,7 +4145,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,
> @@ -4167,7 +4167,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/include/subquery.inc'
> --- a/mysql-test/include/subquery.inc	2010-08-16 06:58:42 +0000
> +++ b/mysql-test/include/subquery.inc	2010-09-07 05:45:36 +0000
> @@ -2510,14 +2510,18 @@ insert into t2(y,z) select t1.b, RAND()*
>   enable_query_log;
>
>   SET SESSION sort_buffer_size = 32 * 1024;
> -SELECT SQL_NO_CACHE COUNT(*)
> +let qq= SELECT SQL_NO_CACHE COUNT(*)
>     FROM (SELECT  a, b, (SELECT x FROM t2 WHERE y=b ORDER BY z DESC LIMIT 1) c
>             FROM t1) t;
> +eval explain $qq;
> +eval $qq;
>
>   SET SESSION sort_buffer_size = 8 * 1024 * 1024;
> -SELECT SQL_NO_CACHE COUNT(*)
> +let qq= SELECT SQL_NO_CACHE COUNT(*)
>     FROM (SELECT  a, b, (SELECT x FROM t2 WHERE y=b ORDER BY z DESC LIMIT 1) c
>             FROM t1) t;
> +eval explain $qq;
> +eval $qq;
>
>   DROP TABLE t1,t2,t3;
>
>
> === modified file 'mysql-test/r/join_cache_jcl1.result'
> --- a/mysql-test/r/join_cache_jcl1.result	2010-08-14 07:28:31 +0000
> +++ b/mysql-test/r/join_cache_jcl1.result	2010-09-07 05:45:36 +0000
> @@ -2219,7 +2219,7 @@ GROUP BY t1.col_int_key
>   ORDER BY t1.col_int_key, t1.col_datetime
>   LIMIT 2;
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> -1	SIMPLE	t1	index	NULL	col_int_key	5	NULL	2	Using temporary; Using filesort
> +1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	2	Using temporary; Using filesort
>   1	SIMPLE	t2	ref	col_int_key	col_int_key	5	const	1	Using where
>   SELECT t1.col_int_key, t1.col_datetime
>   FROM t1,t2
>
> === modified file 'mysql-test/r/myisam_mrr_none.result'
> --- a/mysql-test/r/myisam_mrr_none.result	2010-07-16 11:51:02 +0000
> +++ b/mysql-test/r/myisam_mrr_none.result	2010-09-07 05:45:36 +0000
> @@ -346,7 +346,7 @@ GROUP BY t2.pk
>   );
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
>   1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
> -2	SUBQUERY	t2	ALL	int_key	int_key	5	const	3	33.33	Using filesort
> +2	SUBQUERY	t2	ALL	int_key	int_key	5	const	3	33.33	Using filesort(PQ)
>   Warnings:
>   Note	1003	select min(`test`.`t1`.`pk`) AS `MIN(t1.pk)` from `test`.`t1` where 0
>   DROP TABLE t1, t2;
>
> === modified file 'mysql-test/r/order_by_none.result'
> --- a/mysql-test/r/order_by_none.result	2010-07-04 15:07:55 +0000
> +++ b/mysql-test/r/order_by_none.result	2010-09-07 05:45:36 +0000
> @@ -1101,13 +1101,13 @@ id	select_type	table	type	possible_keys	
>   1	SIMPLE	t2	index	k2	k3	5	NULL	111	Using where
>   EXPLAIN SELECT id,c3 FROM t2 WHERE c2=11 ORDER BY c3 LIMIT 4000;
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> -1	SIMPLE	t2	ref	k2	k2	5	const	7341	Using where; Using filesort
> +1	SIMPLE	t2	ref	k2	k2	5	const	7341	Using where; Using filesort(PQ)
>   EXPLAIN SELECT id,c3 FROM t2 WHERE c2 BETWEEN 10 AND 12 ORDER BY c3 LIMIT 20;
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
>   1	SIMPLE	t2	index	k2	k3	5	NULL	73	Using where
>   EXPLAIN SELECT id,c3 FROM t2 WHERE c2 BETWEEN 20 AND 30 ORDER BY c3 LIMIT 4000;
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> -1	SIMPLE	t2	range	k2	k2	5	NULL	386	Using where; Using filesort
> +1	SIMPLE	t2	range	k2	k2	5	NULL	386	Using where; Using filesort(PQ)
>   SELECT id,c3 FROM t2 WHERE c2=11 ORDER BY c3 LIMIT 20;
>   id	c3
>   6	14
> @@ -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(PQ)
> +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(PQ)
> +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(PQ)
> +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(PQ)
> +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(PQ)
> +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(PQ)
> +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(PQ)
> +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(PQ)
> +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(PQ)
> +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(PQ)
> +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(PQ)
> +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(PQ)
> +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(PQ)
> +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(PQ)
> +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(PQ)
> +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(PQ)
> +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(PQ)
> +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(PQ)
> +2	DERIVED	t1	ALL	NULL	NULL	NULL	NULL	500	Using filesort(PQ)
> +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(PQ)
> +2	DERIVED	t1	ALL	NULL	NULL	NULL	NULL	500	Using filesort(PQ)
> +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(PQ)
> +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(PQ)
> +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-09-07 05:45:36 +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(PQ)
> +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-08-27 06:36:54 +0000
> +++ b/mysql-test/r/select_none.result	2010-09-07 05:45:36 +0000
> @@ -4578,7 +4578,7 @@ a	b	c
>   		2
>   EXPLAIN SELECT * FROM t1 ORDER BY a, b, c LIMIT 5;
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> -1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	24492	Using filesort
> +1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	24492	Using filesort(PQ)
>   SELECT * FROM t1 ORDER BY a, b, c LIMIT 5;
>   a	b	c
>   		0
> @@ -4588,7 +4588,7 @@ a	b	c
>   		0
>   EXPLAIN SELECT * FROM t1 ORDER BY c, a LIMIT 5;
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> -1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	24492	Using filesort
> +1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	24492	Using filesort(PQ)
>   SELECT * FROM t1 ORDER BY c, a LIMIT 5;
>   a	b	c
>   		0
> @@ -4880,7 +4880,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,
> @@ -4898,7 +4898,7 @@ INSERT INTO `CC` VALUES
>   EXPLAIN SELECT `varchar_nokey` G1  FROM CC  WHERE `int_nokey` AND `int_key`<= 4
>   HAVING G1  ORDER  BY `varchar_key` LIMIT  6   ;
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> -1	SIMPLE	CC	range	int_key	int_key	4	NULL	10	Using where; Using filesort
> +1	SIMPLE	CC	range	int_key	int_key	4	NULL	10	Using where; Using filesort(PQ)
>   SELECT `varchar_nokey` G1  FROM CC  WHERE `int_nokey` AND `int_key`<= 4
>   HAVING G1  ORDER  BY `varchar_key` LIMIT  6   ;
>   G1
> @@ -4909,7 +4909,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
>
> === modified file 'mysql-test/r/subquery_none.result'
> --- a/mysql-test/r/subquery_none.result	2010-08-27 06:36:54 +0000
> +++ b/mysql-test/r/subquery_none.result	2010-09-07 05:45:36 +0000
> @@ -182,7 +182,7 @@ a	b
>   explain extended (select * from t2 where t2.b=(select a from t3 order by 1 desc
> limit 1)) union (select * from t4 where t4.b=(select max(t2.a)*4 from t2) order by a);
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
>   1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where
> -2	SUBQUERY	t3	ALL	NULL	NULL	NULL	NULL	3	100.00	Using filesort
> +2	SUBQUERY	t3	ALL	NULL	NULL	NULL	NULL	3	100.00	Using filesort(PQ)
>   3	UNION	t4	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where
>   4	SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	2	100.00	
>   NULL	UNION RESULT	<union1,3>	ALL	NULL	NULL	NULL	NULL	NULL	NULL	
> @@ -201,7 +201,7 @@ explain extended select (select t3.a fro
>   id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
>   1	PRIMARY	<derived3>	system	NULL	NULL	NULL	NULL	1	100.00	
>   3	DERIVED	t2	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where
> -2	SUBQUERY	t3	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using filesort
> +2	SUBQUERY	t3	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using filesort(PQ)
>   Warnings:
>   Note	1003	select (select `test`.`t3`.`a` from `test`.`t3` where
> (`test`.`t3`.`a`<  8) order by 1 desc limit 1) AS `(select t3.a from t3 where a<8
> order by 1 desc limit 1)`,'2' AS `a` from dual
>   select * from t1 where t1.a=(select t2.a from t2 where t2.b=(select max(a) from t3)
> order by 1 desc limit 1);
> @@ -3464,12 +3464,26 @@ insert into t1 select RAND()*1000, A.a +
>   from t3 A, t3 B, t3 C, t3 D where D.a<3;
>   insert into t2(y,z) select t1.b, RAND()*1000 from t1, t3;
>   SET SESSION sort_buffer_size = 32 * 1024;
> +explain SELECT SQL_NO_CACHE COUNT(*)
> +FROM (SELECT  a, b, (SELECT x FROM t2 WHERE y=b ORDER BY z DESC LIMIT 1) c
> +FROM t1) t;
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Select tables optimized away
> +2	DERIVED	t1	ALL	NULL	NULL	NULL	NULL	3000	
> +3	DEPENDENT SUBQUERY	t2	ALL	y	y	5	test.t1.b	30000	Using filesort(PQ)
>   SELECT SQL_NO_CACHE COUNT(*)
>   FROM (SELECT  a, b, (SELECT x FROM t2 WHERE y=b ORDER BY z DESC LIMIT 1) c
>   FROM t1) t;
>   COUNT(*)
>   3000
>   SET SESSION sort_buffer_size = 8 * 1024 * 1024;
> +explain SELECT SQL_NO_CACHE COUNT(*)
> +FROM (SELECT  a, b, (SELECT x FROM t2 WHERE y=b ORDER BY z DESC LIMIT 1) c
> +FROM t1) t;
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Select tables optimized away
> +2	DERIVED	t1	ALL	NULL	NULL	NULL	NULL	3000	
> +3	DEPENDENT SUBQUERY	t2	ALL	y	y	5	test.t1.b	30000	Using filesort(PQ)
>   SELECT SQL_NO_CACHE COUNT(*)
>   FROM (SELECT  a, b, (SELECT x FROM t2 WHERE y=b ORDER BY z DESC LIMIT 1) c
>   FROM t1) t;
>
> === modified file 'mysql-test/r/view.result'
> --- a/mysql-test/r/view.result	2010-08-04 10:34:01 +0000
> +++ b/mysql-test/r/view.result	2010-09-07 05:45:36 +0000
> @@ -303,7 +303,7 @@ a+1
>   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	2	
> -2	DERIVED	t1	ALL	NULL	NULL	NULL	NULL	4	Using filesort
> +2	DERIVED	t1	ALL	NULL	NULL	NULL	NULL	4	Using filesort(PQ)
>   drop view v1;
>   drop table t1;
>   create table t1 (a int);
>
> === 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-09-07 05:45:36 +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-09-07 05:45:36 +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-09-07 05:45:36 +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-08-20 09:15:16 +0000
> +++ b/sql/CMakeLists.txt	2010-09-07 05:45:36 +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-09-07 05:45:36 +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-09-07 05:45:36 +0000
> @@ -0,0 +1,132 @@
> +/* 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)
It would be better to place this function near get_merge_many_buffs_cost to
gradually deprecate and remove the latter.
> +{
> +  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);
> +
> +    if (FALSE)
> +    {
> +      fprintf(stdout,
> +              "total_cost %e num_buffers %llu max_n_elems %llu "
> +              "loop_limit %llu num_merge_calls %llu i_end_value %llu\n",
> +              total_cost, num_buffers, max_n_elems,
> +              loop_limit, num_merge_calls, i_end_value);
> +      fflush(stdout);
> +    }
> +    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);
> +  if (FALSE)
> +    fprintf(stdout, "total_cost %e num_buffers %llu max_n_elems %llu\n\n",
> +            total_cost, num_buffers, max_n_elems);
Is it worth converting this into DBUG_PRINT with info level?
> +  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-09-07 05:45:36 +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-09-07 05:45:36 +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,24 @@ 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, register 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 +82,98 @@ 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;
> +}
> +
> +
> +static const char explain_with_pq[]= "; Using filesort(PQ)";
> +static const char explain_without_pq[]= "; Using filesort";
> +
> +const char *explain_filesort(THD *thd, JOIN *join, TABLE *table)
It's not worth bothering with. There is WL#5558 which addresses EXPLAIN issue.
It's expected to be implemented soon. Sorry, I noticed this too late.
> +{
> +  DBUG_ENTER("explain_filesort");
> +  const ha_rows maxrows=
> +    (join->group || join->tables>  1)
> +    ? HA_POS_ERROR : join->unit->select_limit_cnt;
> +  if (maxrows == HA_POS_ERROR)
> +  {
> +    DBUG_PRINT("info", ("explain PQ is not applicable, maxrows = HA_POS_ERROR"));
> +    DBUG_RETURN(explain_without_pq);
> +  }
> +
> +  if (table->s->tmp_table)
> +    table->file->info(HA_STATUS_VARIABLE);
> +
> +  uint length= 0;
> +  for (ORDER *ord= join->order; ord; ord= ord->next)
> +    ++length;
> +  if (!(join->sortorder=
> +        make_unireg_sortorder(join->order,&length, join->sortorder)))
> +    DBUG_RETURN(explain_without_pq);
> +
> +  bool multi_byte_charset;
> +  const ha_rows num_rows= table->file->estimate_rows_upper_bound();
> +  const ulong   memavl= thd->variables.sortbuff_size;
> +  Sort_param param;
> +  DBUG_PRINT("info",("group %d "
> +                     "join->tables %d "
> +                     "join->select_limit %llu "
> +                     "join->unit->select_limit_cnt %llu",
> +                     join->group,
> +                     join->tables,
> +                     join->select_limit,
> +                     join->unit->select_limit_cnt));
> +
> +  param.init(sortlength(thd, join->sortorder, length,&multi_byte_charset),
> +             table, thd, maxrows, FALSE);
> +
> +  FILESORT_INFO table_sort= table->sort;
> +  uchar **sort_keys=
> +    check_if_pq_applicable(&param,&table_sort, table, num_rows, memavl);
> +
> +  if (sort_keys)
> +  {
> +    DBUG_PRINT("info", ("explain PQ is applicable"));
> +    if (sort_keys != table_sort.sort_keys)
> +      my_free(sort_keys);
> +    DBUG_RETURN(explain_with_pq);
> +  }
> +  DBUG_PRINT("info", ("explain PQ is not applicable"));
> +  DBUG_RETURN(explain_without_pq);
> +}
> +
> +
>   /**
>     Sort a table.
>     Creates a set of pointers that can be used to read the rows
> @@ -80,18 +186,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 +205,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 +245,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 +253,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 +373,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 +387,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 +428,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 +463,23 @@ 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, register 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((uint) 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 +567,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 +600,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 +617,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 +631,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 +683,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 +700,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 +712,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 +758,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 +789,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 +852,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 +1105,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 +1143,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 +1167,131 @@ 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();
> +
> +      fprintf(stdout, "check_if_pq_applicable merge_cost %e pq_cost %e\n",
> +              merge_cost, pq_cost);
> +      fflush(stdout);
> +
> +      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 +1420,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 +1452,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 +1477,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 +1567,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 +1627,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-09-07 05:45:36 +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,26 @@ 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);
> +/**
> +  Provides an appropriate EXPLAIN text for filesort().
> +
> +  @param thd        Thread handle.
> +  @param join       Join handle.
> +  @param table      Table to sort.
> +
> +  @retval "; Using filesort" or "; Using filesort(PQ)"
> +
> +  Performs the same cost analysis as filesort() in order to determine
> +  whether priority queue (PQ) is appliccable for the sort or not.
> +
> +  @note
> +  Some joins are actually simplified during execution, @sa make_simple_join()
> +  and may thus be sorted using a PQ. This will not be shown in the explain text.
> + */
> +const char *explain_filesort(THD *thd, JOIN *join, TABLE *table);
> +
> +
>   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-09-07 05:45:36 +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-09-07 05:45:36 +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-01 14:00:12 +0000
> +++ b/sql/sql_select.cc	2010-09-07 05:45:36 +0000
> @@ -2329,7 +2329,10 @@ JOIN::optimize()
>     if (select_options&  SELECT_DESCRIBE)
>     {
>       error= 0;
> -    DBUG_RETURN(0);
> +    // We need get_tmp_table_field() to return NON-NIL
> +    // when explain_filesort() does make_unireg_sortorder()
> +    // so we need to create the tmp table below.
> +    // DBUG_RETURN(0);
>     }
>     having= 0;
>
> @@ -2427,6 +2430,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))
> @@ -2604,6 +2608,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)
> @@ -2889,11 +2895,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))
> @@ -3119,12 +3126,29 @@ 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"));
> +      DBUG_PRINT("info",("has_group_by %d "
> +                         "curr_join->tables %d "
> +                         "curr_join->select_limit %llu "
> +                         "unit->select_limit_cnt %llu",
> +                         has_group_by,
> +                         curr_join->tables,
> +                         curr_join->select_limit,
> +                         unit->select_limit_cnt));
> +      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;
> @@ -3157,6 +3181,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;
> @@ -5640,7 +5673,6 @@ add_key_part(DYNAMIC_ARRAY *keyuse_array
>   {
>     Field *field=key_field->field;
>     TABLE *form= field->table;
> -  KEYUSE keyuse;
>
>     if (key_field->eq_func&&  !(key_field->optimize& 
> KEY_OPTIMIZE_EXISTS))
>     {
> @@ -5656,20 +5688,21 @@ add_key_part(DYNAMIC_ARRAY *keyuse_array
>         {
>   	if (field->eq(form->key_info[key].key_part[part].field))
>   	{
> -	  keyuse.table= field->table;
> -	  keyuse.val =  key_field->val;
> -	  keyuse.key =  key;
> -	  keyuse.keypart=part;
> -	  keyuse.keypart_map= (key_part_map) 1<<  part;
> -	  keyuse.used_tables=key_field->val->used_tables();
> -	  keyuse.optimize= key_field->optimize&  KEY_OPTIMIZE_REF_OR_NULL;
> -          keyuse.null_rejecting= key_field->null_rejecting;
> -          keyuse.cond_guard= key_field->cond_guard;
> -          keyuse.sj_pred_no= key_field->sj_pred_no;
> -	  if (insert_dynamic(keyuse_array,(uchar*)&keyuse))
> -            return TRUE;
> +          KEYUSE keyuse;
> +          keyuse.table=          field->table;
> +          keyuse.val=            key_field->val;
> +          keyuse.used_tables=    key_field->val->used_tables();
> +          keyuse.key=            key;
> +          keyuse.keypart=        part;
> +          keyuse.optimize=       key_field->optimize& 
> KEY_OPTIMIZE_REF_OR_NULL;
> +          keyuse.keypart_map=    (key_part_map) 1<<  part;
>             /* This will be set accordingly in optimize_keyuse */
>             keyuse.ref_table_rows= ~(ha_rows) 0;
> +          keyuse.null_rejecting= key_field->null_rejecting;
> +          keyuse.cond_guard=     key_field->cond_guard;
> +          keyuse.sj_pred_no=     key_field->sj_pred_no;
> +          if (insert_dynamic(keyuse_array,(uchar*)&keyuse))
> +            return TRUE;
>   	}
>         }
>       }
> @@ -18056,8 +18089,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)
>         {
> @@ -19640,7 +19691,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
> @@ -19742,9 +19793,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)
>     {
> @@ -20091,7 +20144,7 @@ SORT_FIELD *make_unireg_sortorder(ORDER
>     pos= sort= sortorder;
>
>     if (!pos)
> -    return 0;
> +    DBUG_RETURN(0);
>
>     for (;order;order=order->next,pos++)
>     {
> @@ -20108,6 +20161,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);
> @@ -22435,7 +22489,7 @@ void select_describe(JOIN *join, bool ne
>           if (need_order)
>           {
>             need_order=0;
> -          extra.append(STRING_WITH_LEN("; Using filesort"));
> +          extra.append(explain_filesort(thd, join, table));
>           }
>           if (distinct&  test_all_bits(used_tables,thd->used_tables))
>             extra.append(STRING_WITH_LEN("; Distinct"));
>
> === modified file 'sql/sql_sort.h'
> --- a/sql/sql_sort.h	2010-07-02 18:15:21 +0000
> +++ b/sql/sql_sort.h	2010-09-07 05:45:36 +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-08-24 12:59:07 +0000
> +++ b/sql/sql_table.cc	2010-09-07 05:45:36 +0000
> @@ -7081,7 +7081,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-09-07 05:45:36 +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-09-07 05:45:36 +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-09-07 05:45:36 +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-09-07 05:45:36 +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 GTEST_HAS_DEATH_TEST&&  !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(m_queue.push((uchar*)&foo),
> +               ".*Assertion .*is_initialized.*");
> +}
> +#endif  // GTEST_HAS_DEATH_TEST&&  !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
>
>
>
>
>
Thread
bzr commit into mysql-next-mr-opt-team branch (tor.didriksen:3215) WL#1393Tor Didriksen7 Sep
  • Re: bzr commit into mysql-next-mr-opt-team branch (tor.didriksen:3215)WL#1393Evgeny Potemkin7 Sep
    • Re: bzr commit into mysql-next-mr-opt-team branch (tor.didriksen:3215)WL#1393Tor Didriksen7 Sep
  • Re: bzr commit into mysql-next-mr-opt-team branch (tor.didriksen:3215)WL#1393Konstantin Osipov16 Sep
    • Re: bzr commit into mysql-next-mr-opt-team branch (tor.didriksen:3215)WL#1393Tor Didriksen16 Sep
      • Re: bzr commit into mysql-next-mr-opt-team branch (tor.didriksen:3215)WL#1393Konstantin Osipov16 Sep
        • Re: bzr commit into mysql-next-mr-opt-team branch (tor.didriksen:3215)WL#1393Tor Didriksen16 Sep
      • Re: bzr commit into mysql-next-mr-opt-team branch (tor.didriksen:3215)WL#1393Konstantin Osipov16 Sep
        • Re: bzr commit into mysql-next-mr-opt-team branch (tor.didriksen:3215)WL#1393Tor Didriksen16 Sep
          • Re: bzr commit into mysql-next-mr-opt-team branch (tor.didriksen:3215)WL#1393Konstantin Osipov16 Sep
            • Re: bzr commit into mysql-next-mr-opt-team branch (tor.didriksen:3215)WL#1393Tor Didriksen17 Sep