List:Commits« Previous MessageNext Message »
From:Tor Didriksen Date:December 17 2010 9:42am
Subject:bzr push into mysql-trunk-bugfixing branch (tor.didriksen:3442 to 3443)
WL#1393
View as plain text  
 3443 Tor Didriksen	2010-12-17
      WL#1393 Optimizing filesort with small limit
        
      Many web customers have to do
      "SELECT ... ORDER BY non_index_column LIMIT X",
        
      When X * <Row Size> is smaller than sort_buff_size we can use
      the following algoritm to speed up the sort:
        
       - Create a queue to hold 'limit' keys.
       - Scan through the table and store the first (last if DESC) keys in the queue
       - Return values from queue
     @ libmysqld/CMakeLists.txt
        Add Bounded_queue
     @ mysql-test/include/order_by.inc
        Add new tests.
     @ mysql-test/include/select.inc
        Fix typo in bug number.
     @ mysql-test/r/explain.result
        New explain results for queries where we can skip ordering.
     @ mysql-test/r/group_by.result
        Add new tests.
     @ mysql-test/r/myisam_mrr.result
        New explain results for queries where we can skip ordering.
     @ mysql-test/r/myisam_mrr_cost.result
        New explain results for queries where we can skip ordering.
     @ mysql-test/r/myisam_mrr_cost_icp.result
        New explain results for queries where we can skip ordering.
     @ mysql-test/r/myisam_mrr_icp.result
        New explain results for queries where we can skip ordering.
     @ mysql-test/r/myisam_mrr_none.result
        New explain results for queries where we can skip ordering.
     @ mysql-test/r/order_by_icp_mrr.result
        Add new tests.
     @ mysql-test/r/order_by_none.result
        Add new tests.
     @ mysql-test/r/order_by_sortkey.result
        Add new tests.
     @ mysql-test/r/select_icp_mrr.result
        Fix typo in bug number.
     @ mysql-test/r/select_none.result
        Fix typo in bug number.
     @ mysql-test/r/subselect_innodb.result
        Add new tests.
     @ mysql-test/t/group_by.test
        Add new tests.
     @ mysql-test/t/order_by_sortkey.test
        Add new tests.
     @ mysql-test/t/subselect_innodb.test
        Add new tests.
     @ mysys/CMakeLists.txt
        Compile standalone queues test executable.
     @ mysys/queues.c
        Fix un-maintained code: s/bool/my_bool/
     @ sql/CMakeLists.txt
        Add filesort_utils.cc to Google Test library.
     @ 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.
        
        Add extra output argument to filesort: found_rows.
        Simplify usage of make_char_array(), let it allocate/initialize FILESORT_INFO.sort_keys directly.
        Rename SORTPARAM to Sort_param, and add init_for_filesort() function.
        Remove dead code (obsolete #ifdef)
        Remove dead code (indexfile was always NULL in find_all_keys())
     @ sql/filesort.h
        New argument to filesort()
     @ sql/filesort_utils.cc
        Some utility functions in a separate file, so we can unit test them.
     @ sql/filesort_utils.h
        Some utility functions in a separate file, so we can unit test them.
     @ sql/item_subselect.cc
        Don't wrap function call in DBUG_RETURN.
     @ sql/sql_const.h
        Use double, rather than int, literals (avoids lots of casting).
     @ sql/sql_delete.cc
        New argument to filesort()
     @ sql/sql_select.cc
        Handle new filesort() using priority queue:
        - Add some more DBUG_PRINT statements before calls to create_sort_index()
        - create_sort_index() can use the new PQ algorithm if (!group && tables==1)
        - use information from filesort() for FOUND_ROWS
        - in end_send(): stop if we are about to read more rows than allocated by the PQ
        - skip ordering for GROUP BY in subqueries.
     @ sql/sql_select.h
        Comment on member variable m_select_limit
     @ sql/sql_sort.h
        Rename st_sort_param/SORTPARAM to Sort_param.
        Add constructor.
        Add init_for_filesort() 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 unit test for Bounded_queue
     @ unittest/gunit/bounded_queue-t.cc
        Unit tests for Bounded_queue, and filesort cost functions.

    added:
      mysql-test/r/order_by_sortkey.result
      mysql-test/t/order_by_sortkey.test
      sql/bounded_queue.h
      sql/filesort_utils.cc
      sql/filesort_utils.h
      unittest/gunit/bounded_queue-t.cc
    modified:
      libmysqld/CMakeLists.txt
      mysql-test/include/order_by.inc
      mysql-test/include/select.inc
      mysql-test/r/explain.result
      mysql-test/r/group_by.result
      mysql-test/r/myisam_mrr.result
      mysql-test/r/myisam_mrr_cost.result
      mysql-test/r/myisam_mrr_cost_icp.result
      mysql-test/r/myisam_mrr_icp.result
      mysql-test/r/myisam_mrr_none.result
      mysql-test/r/order_by_icp_mrr.result
      mysql-test/r/order_by_none.result
      mysql-test/r/select_icp_mrr.result
      mysql-test/r/select_none.result
      mysql-test/r/subselect_innodb.result
      mysql-test/t/group_by.test
      mysql-test/t/subselect_innodb.test
      mysys/CMakeLists.txt
      mysys/queues.c
      sql/CMakeLists.txt
      sql/filesort.cc
      sql/filesort.h
      sql/item_subselect.cc
      sql/sql_const.h
      sql/sql_delete.cc
      sql/sql_select.cc
      sql/sql_select.h
      sql/sql_sort.h
      sql/sql_table.cc
      sql/sql_update.cc
      sql/uniques.cc
      unittest/gunit/CMakeLists.txt
 3442 Jorgen Loland	2010-12-17 [merge]
      BUG#59895: Merge 5.5-bugteam -> trunk-bugfixing

    modified:
      sql/sql_select.cc
=== modified file 'libmysqld/CMakeLists.txt'
--- a/libmysqld/CMakeLists.txt	2010-11-29 11:28:55 +0000
+++ b/libmysqld/CMakeLists.txt	2010-12-17 09:41:21 +0000
@@ -44,6 +44,7 @@ SET(SQL_EMBEDDED_SOURCES emb_qcache.cc l
            ../sql-common/client_plugin.c
            ../sql/password.c ../sql/discover.cc ../sql/derror.cc 
            ../sql/field.cc ../sql/field_conv.cc
+           ../sql/filesort_utils.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 'mysql-test/include/order_by.inc'
--- a/mysql-test/include/order_by.inc	2010-09-27 13:20:24 +0000
+++ b/mysql-test/include/order_by.inc	2010-12-17 09:41:21 +0000
@@ -1364,6 +1364,203 @@ ORDER BY t2.c LIMIT 1;
 
 DROP TABLE t1,t2,t3;
 
+--echo #
+--echo # WL#1393 - Optimizing filesort with small limit
+--echo #
+
+CREATE TABLE t1(f0 int auto_increment primary key, f1 int, f2 varchar(200));
+INSERT INTO t1(f1, f2) VALUES 
+(0,"0"),(1,"1"),(2,"2"),(3,"3"),(4,"4"),(5,"5"),
+(6,"6"),(7,"7"),(8,"8"),(9,"9"),(10,"10"),
+(11,"11"),(12,"12"),(13,"13"),(14,"14"),(15,"15"),
+(16,"16"),(17,"17"),(18,"18"),(19,"19"),(20,"20"),
+(21,"21"),(22,"22"),(23,"23"),(24,"24"),(25,"25"),
+(26,"26"),(27,"27"),(28,"28"),(29,"29"),(30,"30"),
+(31,"31"),(32,"32"),(33,"33"),(34,"34"),(35,"35"),
+(36,"36"),(37,"37"),(38,"38"),(39,"39"),(40,"40"),
+(41,"41"),(42,"42"),(43,"43"),(44,"44"),(45,"45"),
+(46,"46"),(47,"47"),(48,"48"),(49,"49"),(50,"50"),
+(51,"51"),(52,"52"),(53,"53"),(54,"54"),(55,"55"),
+(56,"56"),(57,"57"),(58,"58"),(59,"59"),(60,"60"),
+(61,"61"),(62,"62"),(63,"63"),(64,"64"),(65,"65"),
+(66,"66"),(67,"67"),(68,"68"),(69,"69"),(70,"70"),
+(71,"71"),(72,"72"),(73,"73"),(74,"74"),(75,"75"),
+(76,"76"),(77,"77"),(78,"78"),(79,"79"),(80,"80"),
+(81,"81"),(82,"82"),(83,"83"),(84,"84"),(85,"85"),
+(86,"86"),(87,"87"),(88,"88"),(89,"89"),(90,"90"),
+(91,"91"),(92,"92"),(93,"93"),(94,"94"),(95,"95"),
+(96,"96"),(97,"97"),(98,"98"),(99,"99");
+
+################
+## Test sort when source data fits in memory
+
+SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 100;
+SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 30;
+SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 0;
+SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 30;
+SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 0;
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 20;
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0;
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 10 OFFSET 10;
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0 OFFSET 10;
+
+################
+## Test sort when source data does not fit in memory
+set sort_buffer_size= 32768;
+CREATE TEMPORARY TABLE tmp (f1 int, f2 varchar(20));
+INSERT INTO tmp SELECT f1, f2 FROM t1;
+INSERT INTO t1(f1, f2) SELECT * FROM tmp;
+INSERT INTO tmp SELECT f1, f2 FROM t1;
+INSERT INTO t1(f1, f2) SELECT * FROM tmp;
+
+SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 30;
+SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 0;
+SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 30;
+SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 0;
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 20;
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0;
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 10 OFFSET 10;
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0 OFFSET 10;
+
+################
+## Test with SQL_CALC_FOUND_ROWS
+set sort_buffer_size= 32768;
+SELECT SQL_CALC_FOUND_ROWS * FROM t1
+ORDER BY f1, f0 LIMIT 30;
+SELECT FOUND_ROWS();
+
+SELECT SQL_CALC_FOUND_ROWS * FROM t1
+ORDER BY f1, f0 LIMIT 0;
+SELECT FOUND_ROWS();
+
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
+ORDER BY f2, f0 LIMIT 20;
+SELECT FOUND_ROWS();
+
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
+ORDER BY f2, f0 LIMIT 0;
+SELECT FOUND_ROWS();
+
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
+ORDER BY f2, f0 LIMIT 10 OFFSET 10;
+SELECT FOUND_ROWS();
+
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
+ORDER BY f2, f0 LIMIT 0 OFFSET 10;
+SELECT FOUND_ROWS();
+
+################
+## Test sorting with join
+## These are re-written to use PQ during execution.
+set sort_buffer_size= 327680;
+
+SELECT * FROM t1 JOIN tmp on t1.f2=tmp.f2
+ORDER BY tmp.f1, f0 LIMIT 30;
+
+SELECT * FROM t1 JOIN tmp on t1.f2=tmp.f2
+ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30;
+
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 JOIN tmp on t1.f2=tmp.f2
+ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30;
+SELECT FOUND_ROWS();
+
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 JOIN tmp on t1.f2=tmp.f2
+WHERE t1.f2>20
+ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30;
+SELECT FOUND_ROWS();
+
+################
+## Test views
+CREATE VIEW v1 as SELECT * FROM t1 ORDER BY f1, f0 LIMIT 30;
+SELECT * FROM v1;
+drop view v1;
+
+CREATE VIEW v1 as SELECT * FROM t1 ORDER BY f1, f0 LIMIT 100;
+SELECT * FROM v1 ORDER BY f2, f0 LIMIT 30;
+
+CREATE VIEW v2 as SELECT * FROM t1 ORDER BY f2, f0 LIMIT 100;
+SELECT * FROM v1 JOIN v2 on v1.f1=v2.f1 ORDER BY v1.f2,v1.f0,v2.f0
+LIMIT 30;
+
+################
+## Test group & having
+SELECT floor(f1/10) f3, count(f2) FROM t1
+GROUP BY 1 ORDER BY 2,1 LIMIT 5;
+
+SELECT floor(f1/10) f3, count(f2) FROM t1
+GROUP BY 1 ORDER BY 2,1 LIMIT 0;
+
+################
+## Test SP
+delimiter |;
+CREATE PROCEDURE wl1393_sp_test()
+BEGIN
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 30;
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 15 OFFSET 15;
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
+ORDER BY f2, f0 LIMIT 15 OFFSET 15;
+SELECT FOUND_ROWS();
+SELECT * FROM v1 ORDER BY f2, f0 LIMIT 30;
+END|
+CALL wl1393_sp_test()|
+DROP PROCEDURE wl1393_sp_test|
+delimiter ;|
+
+################
+## Test with subqueries
+SELECT d1.f1, d1.f2 FROM t1
+LEFT JOIN (SELECT * FROM t1 ORDER BY f1 LIMIT 30) d1 on t1.f1=d1.f1
+ORDER BY d1.f2 DESC LIMIT 30;
+
+SELECT * FROM t1 WHERE f1 = (SELECT f1 FROM t1 ORDER BY 1 LIMIT 1);
+
+--error ER_SUBQUERY_NO_1_ROW
+SELECT * FROM t1 WHERE f1 = (SELECT f1 FROM t1 ORDER BY 1 LIMIT 2);
+
+DROP TABLE t1, tmp;
+DROP VIEW v1, v2;
+
+--echo # end of WL#1393 - Optimizing filesort with small limit
+
+--echo #
+--echo # Bug #58761
+--echo # Crash in Field::is_null in field.h on subquery in WHERE clause
+--echo #
+
+CREATE TABLE t1 (
+  pk INT NOT NULL AUTO_INCREMENT,
+  col_int_key INT DEFAULT NULL,
+  col_varchar_key VARCHAR(1) DEFAULT NULL,
+  PRIMARY KEY (pk),
+  KEY col_varchar_key (col_varchar_key,col_int_key)
+);
+
+INSERT INTO t1 VALUES (27,7,'x');
+INSERT INTO t1 VALUES (28,6,'m');
+INSERT INTO t1 VALUES (29,4,'c');
+
+CREATE TABLE where_subselect
+  SELECT DISTINCT `pk` AS field1 , `pk` AS field2 
+  FROM t1 AS alias1 
+  WHERE alias1 . `col_int_key` > 229 
+    OR alias1 . `col_varchar_key` IS NOT NULL
+  GROUP BY field1, field2
+;
+
+SELECT * 
+FROM where_subselect
+WHERE (field1, field2) IN (  
+  SELECT DISTINCT `pk` AS field1 , `pk` AS field2 
+  FROM t1 AS alias1 
+  WHERE alias1 . `col_int_key` > 229 
+    OR alias1 . `col_varchar_key` IS NOT NULL
+  GROUP BY field1, field2
+);
+
+DROP TABLE t1;
+DROP TABLE where_subselect;
+
+--echo # End of Bug #58761
 
 #
 # Bug#35844: Covering index for ref access not compatible with ORDER BY list

=== modified file 'mysql-test/include/select.inc'
--- a/mysql-test/include/select.inc	2010-10-26 09:10:59 +0000
+++ b/mysql-test/include/select.inc	2010-12-17 09:41:21 +0000
@@ -4140,7 +4140,7 @@ DROP TABLE t1;
 --echo End of 5.1 tests
 
 --echo #
---echo # Bug#45277: Lost HAVING clause led to a wrong result.
+--echo # Bug#45227: Lost HAVING clause led to a wrong result.
 --echo #
 CREATE TABLE `CC` (
   `int_nokey` int(11) NOT NULL,
@@ -4162,7 +4162,7 @@ SELECT `varchar_nokey` G1  FROM CC  WHER
   HAVING G1  ORDER  BY `varchar_key` LIMIT  6   ;
 
 DROP TABLE CC;
---echo # End of test#45277
+--echo # End of test#45227
 
 --echo #
 --echo # Bug#54515: Crash in opt_range.cc::get_best_group_min_max on 

=== modified file 'mysql-test/r/explain.result'
--- a/mysql-test/r/explain.result	2010-12-16 19:28:42 +0000
+++ b/mysql-test/r/explain.result	2010-12-17 09:41:21 +0000
@@ -283,7 +283,7 @@ WHERE 1 > ALL((SELECT 1 FROM t1 JOIN t1 
 WHERE t1.f1 GROUP BY t1.f1));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
-2	SUBQUERY	a	system	NULL	NULL	NULL	NULL	1	Using filesort
+2	SUBQUERY	a	system	NULL	NULL	NULL	NULL	1	
 2	SUBQUERY	t1	fulltext	f1	f1	0		1	Using where
 PREPARE stmt FROM
 'EXPLAIN SELECT 1 FROM t1
@@ -293,12 +293,12 @@ PREPARE stmt FROM
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
-2	SUBQUERY	a	system	NULL	NULL	NULL	NULL	1	Using filesort
+2	SUBQUERY	a	system	NULL	NULL	NULL	NULL	1	
 2	SUBQUERY	t1	fulltext	f1	f1	0		1	Using where
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
-2	SUBQUERY	a	system	NULL	NULL	NULL	NULL	1	Using filesort
+2	SUBQUERY	a	system	NULL	NULL	NULL	NULL	1	
 2	SUBQUERY	t1	fulltext	f1	f1	0		1	Using where
 DEALLOCATE PREPARE stmt;
 PREPARE stmt FROM
@@ -309,12 +309,12 @@ PREPARE stmt FROM
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
-2	SUBQUERY	a	system	NULL	NULL	NULL	NULL	1	Using filesort
+2	SUBQUERY	a	system	NULL	NULL	NULL	NULL	1	
 2	SUBQUERY	t1	fulltext	f1	f1	0		1	Using where
 EXECUTE stmt;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
-2	SUBQUERY	a	system	NULL	NULL	NULL	NULL	1	Using filesort
+2	SUBQUERY	a	system	NULL	NULL	NULL	NULL	1	
 2	SUBQUERY	t1	fulltext	f1	f1	0		1	Using where
 DEALLOCATE PREPARE stmt;
 DROP TABLE t1;

=== modified file 'mysql-test/r/group_by.result'
--- a/mysql-test/r/group_by.result	2010-12-16 19:28:42 +0000
+++ b/mysql-test/r/group_by.result	2010-12-17 09:41:21 +0000
@@ -1886,3 +1886,48 @@ f1	MIN(f2)	MAX(f2)
 4	00:25:00	00:25:00
 DROP TABLE t1;
 #End of test#49771
+#
+# Bug #58782
+# Missing rows with SELECT .. WHERE .. IN subquery 
+# with full GROUP BY and no aggr
+#
+CREATE TABLE t1 (
+pk INT NOT NULL,
+col_int_nokey INT,
+PRIMARY KEY (pk)
+);
+INSERT INTO t1 VALUES (10,7);
+INSERT INTO t1 VALUES (11,1);
+INSERT INTO t1 VALUES (12,5);
+INSERT INTO t1 VALUES (13,3);
+SELECT pk AS field1, col_int_nokey AS field2 
+FROM t1 
+WHERE col_int_nokey > 0
+GROUP BY field1, field2;
+field1	field2
+10	7
+11	1
+12	5
+13	3
+CREATE TABLE where_subselect
+SELECT pk AS field1, col_int_nokey AS field2
+FROM t1
+WHERE col_int_nokey > 0
+GROUP BY field1, field2
+;
+SELECT * 
+FROM where_subselect
+WHERE (field1, field2) IN (
+SELECT pk AS field1, col_int_nokey AS field2
+FROM t1
+WHERE col_int_nokey > 0
+GROUP BY field1, field2
+);
+field1	field2
+10	7
+11	1
+12	5
+13	3
+DROP TABLE t1;
+DROP TABLE where_subselect;
+# End of Bug #58782

=== modified file 'mysql-test/r/myisam_mrr.result'
--- a/mysql-test/r/myisam_mrr.result	2010-12-06 13:10:10 +0000
+++ b/mysql-test/r/myisam_mrr.result	2010-12-17 09:41:21 +0000
@@ -347,7 +347,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	ref	int_key	int_key	5	const	1	100.00	Using where; Using filesort
+2	SUBQUERY	t2	ref	int_key	int_key	5	const	1	100.00	Using where
 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/myisam_mrr_cost.result'
--- a/mysql-test/r/myisam_mrr_cost.result	2010-12-06 13:10:10 +0000
+++ b/mysql-test/r/myisam_mrr_cost.result	2010-12-17 09:41:21 +0000
@@ -347,7 +347,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	ref	int_key	int_key	5	const	1	100.00	Using where; Using filesort
+2	SUBQUERY	t2	ref	int_key	int_key	5	const	1	100.00	Using where
 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/myisam_mrr_cost_icp.result'
--- a/mysql-test/r/myisam_mrr_cost_icp.result	2010-12-06 13:10:10 +0000
+++ b/mysql-test/r/myisam_mrr_cost_icp.result	2010-12-17 09:41:21 +0000
@@ -347,7 +347,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	ref	int_key	int_key	5	const	1	100.00	Using index condition; Using where; Using filesort
+2	SUBQUERY	t2	ref	int_key	int_key	5	const	1	100.00	Using index condition
 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/myisam_mrr_icp.result'
--- a/mysql-test/r/myisam_mrr_icp.result	2010-12-06 13:10:10 +0000
+++ b/mysql-test/r/myisam_mrr_icp.result	2010-12-17 09:41:21 +0000
@@ -347,7 +347,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	ref	int_key	int_key	5	const	1	100.00	Using index condition; Using where; Using filesort
+2	SUBQUERY	t2	ref	int_key	int_key	5	const	1	100.00	Using index condition
 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/myisam_mrr_none.result'
--- a/mysql-test/r/myisam_mrr_none.result	2010-12-16 17:38:26 +0000
+++ b/mysql-test/r/myisam_mrr_none.result	2010-12-17 09:41:21 +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	ref	int_key	int_key	5	const	1	100.00	Using where; Using filesort
+2	SUBQUERY	t2	ref	int_key	int_key	5	const	1	100.00	Using where
 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_icp_mrr.result'
--- a/mysql-test/r/order_by_icp_mrr.result	2010-11-30 13:55:22 +0000
+++ b/mysql-test/r/order_by_icp_mrr.result	2010-12-17 09:41:21 +0000
@@ -1505,6 +1505,890 @@ ORDER BY t2.c LIMIT 1;
 d
 52.5
 DROP TABLE t1,t2,t3;
+#
+# WL#1393 - Optimizing filesort with small limit
+#
+CREATE TABLE t1(f0 int auto_increment primary key, f1 int, f2 varchar(200));
+INSERT INTO t1(f1, f2) VALUES 
+(0,"0"),(1,"1"),(2,"2"),(3,"3"),(4,"4"),(5,"5"),
+(6,"6"),(7,"7"),(8,"8"),(9,"9"),(10,"10"),
+(11,"11"),(12,"12"),(13,"13"),(14,"14"),(15,"15"),
+(16,"16"),(17,"17"),(18,"18"),(19,"19"),(20,"20"),
+(21,"21"),(22,"22"),(23,"23"),(24,"24"),(25,"25"),
+(26,"26"),(27,"27"),(28,"28"),(29,"29"),(30,"30"),
+(31,"31"),(32,"32"),(33,"33"),(34,"34"),(35,"35"),
+(36,"36"),(37,"37"),(38,"38"),(39,"39"),(40,"40"),
+(41,"41"),(42,"42"),(43,"43"),(44,"44"),(45,"45"),
+(46,"46"),(47,"47"),(48,"48"),(49,"49"),(50,"50"),
+(51,"51"),(52,"52"),(53,"53"),(54,"54"),(55,"55"),
+(56,"56"),(57,"57"),(58,"58"),(59,"59"),(60,"60"),
+(61,"61"),(62,"62"),(63,"63"),(64,"64"),(65,"65"),
+(66,"66"),(67,"67"),(68,"68"),(69,"69"),(70,"70"),
+(71,"71"),(72,"72"),(73,"73"),(74,"74"),(75,"75"),
+(76,"76"),(77,"77"),(78,"78"),(79,"79"),(80,"80"),
+(81,"81"),(82,"82"),(83,"83"),(84,"84"),(85,"85"),
+(86,"86"),(87,"87"),(88,"88"),(89,"89"),(90,"90"),
+(91,"91"),(92,"92"),(93,"93"),(94,"94"),(95,"95"),
+(96,"96"),(97,"97"),(98,"98"),(99,"99");
+SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 100;
+f0	f1	f2
+1	0	0
+2	1	1
+3	2	2
+4	3	3
+5	4	4
+6	5	5
+7	6	6
+8	7	7
+9	8	8
+10	9	9
+11	10	10
+12	11	11
+13	12	12
+14	13	13
+15	14	14
+16	15	15
+17	16	16
+18	17	17
+19	18	18
+20	19	19
+21	20	20
+22	21	21
+23	22	22
+24	23	23
+25	24	24
+26	25	25
+27	26	26
+28	27	27
+29	28	28
+30	29	29
+31	30	30
+32	31	31
+33	32	32
+34	33	33
+35	34	34
+36	35	35
+37	36	36
+38	37	37
+39	38	38
+40	39	39
+41	40	40
+42	41	41
+43	42	42
+44	43	43
+45	44	44
+46	45	45
+47	46	46
+48	47	47
+49	48	48
+50	49	49
+51	50	50
+52	51	51
+53	52	52
+54	53	53
+55	54	54
+56	55	55
+57	56	56
+58	57	57
+59	58	58
+60	59	59
+61	60	60
+62	61	61
+63	62	62
+64	63	63
+65	64	64
+66	65	65
+67	66	66
+68	67	67
+69	68	68
+70	69	69
+71	70	70
+72	71	71
+73	72	72
+74	73	73
+75	74	74
+76	75	75
+77	76	76
+78	77	77
+79	78	78
+80	79	79
+81	80	80
+82	81	81
+83	82	82
+84	83	83
+85	84	84
+86	85	85
+87	86	86
+88	87	87
+89	88	88
+90	89	89
+91	90	90
+92	91	91
+93	92	92
+94	93	93
+95	94	94
+96	95	95
+97	96	96
+98	97	97
+99	98	98
+100	99	99
+SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 30;
+f0	f1	f2
+1	0	0
+2	1	1
+3	2	2
+4	3	3
+5	4	4
+6	5	5
+7	6	6
+8	7	7
+9	8	8
+10	9	9
+11	10	10
+12	11	11
+13	12	12
+14	13	13
+15	14	14
+16	15	15
+17	16	16
+18	17	17
+19	18	18
+20	19	19
+21	20	20
+22	21	21
+23	22	22
+24	23	23
+25	24	24
+26	25	25
+27	26	26
+28	27	27
+29	28	28
+30	29	29
+SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 0;
+f0	f1	f2
+SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 30;
+f0	f1	f2
+100	99	99
+99	98	98
+98	97	97
+97	96	96
+96	95	95
+95	94	94
+94	93	93
+93	92	92
+92	91	91
+91	90	90
+10	9	9
+90	89	89
+89	88	88
+88	87	87
+87	86	86
+86	85	85
+85	84	84
+84	83	83
+83	82	82
+82	81	81
+81	80	80
+9	8	8
+80	79	79
+79	78	78
+78	77	77
+77	76	76
+76	75	75
+75	74	74
+74	73	73
+73	72	72
+SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 0;
+f0	f1	f2
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 20;
+f0	f1	f2
+12	11	11
+13	12	12
+14	13	13
+15	14	14
+16	15	15
+17	16	16
+18	17	17
+19	18	18
+20	19	19
+21	20	20
+22	21	21
+23	22	22
+24	23	23
+25	24	24
+26	25	25
+27	26	26
+28	27	27
+29	28	28
+30	29	29
+31	30	30
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0;
+f0	f1	f2
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 10 OFFSET 10;
+f0	f1	f2
+22	21	21
+23	22	22
+24	23	23
+25	24	24
+26	25	25
+27	26	26
+28	27	27
+29	28	28
+30	29	29
+31	30	30
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0 OFFSET 10;
+f0	f1	f2
+set sort_buffer_size= 32768;
+CREATE TEMPORARY TABLE tmp (f1 int, f2 varchar(20));
+INSERT INTO tmp SELECT f1, f2 FROM t1;
+INSERT INTO t1(f1, f2) SELECT * FROM tmp;
+INSERT INTO tmp SELECT f1, f2 FROM t1;
+INSERT INTO t1(f1, f2) SELECT * FROM tmp;
+SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 30;
+f0	f1	f2
+1	0	0
+101	0	0
+201	0	0
+301	0	0
+401	0	0
+2	1	1
+102	1	1
+202	1	1
+302	1	1
+402	1	1
+3	2	2
+103	2	2
+203	2	2
+303	2	2
+403	2	2
+4	3	3
+104	3	3
+204	3	3
+304	3	3
+404	3	3
+5	4	4
+105	4	4
+205	4	4
+305	4	4
+405	4	4
+6	5	5
+106	5	5
+206	5	5
+306	5	5
+406	5	5
+SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 0;
+f0	f1	f2
+SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 30;
+f0	f1	f2
+100	99	99
+200	99	99
+300	99	99
+400	99	99
+500	99	99
+99	98	98
+199	98	98
+299	98	98
+399	98	98
+499	98	98
+98	97	97
+198	97	97
+298	97	97
+398	97	97
+498	97	97
+97	96	96
+197	96	96
+297	96	96
+397	96	96
+497	96	96
+96	95	95
+196	95	95
+296	95	95
+396	95	95
+496	95	95
+95	94	94
+195	94	94
+295	94	94
+395	94	94
+495	94	94
+SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 0;
+f0	f1	f2
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 20;
+f0	f1	f2
+12	11	11
+112	11	11
+212	11	11
+312	11	11
+412	11	11
+13	12	12
+113	12	12
+213	12	12
+313	12	12
+413	12	12
+14	13	13
+114	13	13
+214	13	13
+314	13	13
+414	13	13
+15	14	14
+115	14	14
+215	14	14
+315	14	14
+415	14	14
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0;
+f0	f1	f2
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 10 OFFSET 10;
+f0	f1	f2
+14	13	13
+114	13	13
+214	13	13
+314	13	13
+414	13	13
+15	14	14
+115	14	14
+215	14	14
+315	14	14
+415	14	14
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0 OFFSET 10;
+f0	f1	f2
+set sort_buffer_size= 32768;
+SELECT SQL_CALC_FOUND_ROWS * FROM t1
+ORDER BY f1, f0 LIMIT 30;
+f0	f1	f2
+1	0	0
+101	0	0
+201	0	0
+301	0	0
+401	0	0
+2	1	1
+102	1	1
+202	1	1
+302	1	1
+402	1	1
+3	2	2
+103	2	2
+203	2	2
+303	2	2
+403	2	2
+4	3	3
+104	3	3
+204	3	3
+304	3	3
+404	3	3
+5	4	4
+105	4	4
+205	4	4
+305	4	4
+405	4	4
+6	5	5
+106	5	5
+206	5	5
+306	5	5
+406	5	5
+SELECT FOUND_ROWS();
+FOUND_ROWS()
+500
+SELECT SQL_CALC_FOUND_ROWS * FROM t1
+ORDER BY f1, f0 LIMIT 0;
+f0	f1	f2
+SELECT FOUND_ROWS();
+FOUND_ROWS()
+500
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
+ORDER BY f2, f0 LIMIT 20;
+f0	f1	f2
+12	11	11
+112	11	11
+212	11	11
+312	11	11
+412	11	11
+13	12	12
+113	12	12
+213	12	12
+313	12	12
+413	12	12
+14	13	13
+114	13	13
+214	13	13
+314	13	13
+414	13	13
+15	14	14
+115	14	14
+215	14	14
+315	14	14
+415	14	14
+SELECT FOUND_ROWS();
+FOUND_ROWS()
+445
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
+ORDER BY f2, f0 LIMIT 0;
+f0	f1	f2
+SELECT FOUND_ROWS();
+FOUND_ROWS()
+445
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
+ORDER BY f2, f0 LIMIT 10 OFFSET 10;
+f0	f1	f2
+14	13	13
+114	13	13
+214	13	13
+314	13	13
+414	13	13
+15	14	14
+115	14	14
+215	14	14
+315	14	14
+415	14	14
+SELECT FOUND_ROWS();
+FOUND_ROWS()
+445
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
+ORDER BY f2, f0 LIMIT 0 OFFSET 10;
+f0	f1	f2
+SELECT FOUND_ROWS();
+FOUND_ROWS()
+445
+set sort_buffer_size= 327680;
+SELECT * FROM t1 JOIN tmp on t1.f2=tmp.f2
+ORDER BY tmp.f1, f0 LIMIT 30;
+f0	f1	f2	f1	f2
+1	0	0	0	0
+1	0	0	0	0
+1	0	0	0	0
+101	0	0	0	0
+101	0	0	0	0
+101	0	0	0	0
+201	0	0	0	0
+201	0	0	0	0
+201	0	0	0	0
+301	0	0	0	0
+301	0	0	0	0
+301	0	0	0	0
+401	0	0	0	0
+401	0	0	0	0
+401	0	0	0	0
+2	1	1	1	1
+2	1	1	1	1
+2	1	1	1	1
+102	1	1	1	1
+102	1	1	1	1
+102	1	1	1	1
+202	1	1	1	1
+202	1	1	1	1
+202	1	1	1	1
+302	1	1	1	1
+302	1	1	1	1
+302	1	1	1	1
+402	1	1	1	1
+402	1	1	1	1
+402	1	1	1	1
+SELECT * FROM t1 JOIN tmp on t1.f2=tmp.f2
+ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30;
+f0	f1	f2	f1	f2
+3	2	2	2	2
+3	2	2	2	2
+3	2	2	2	2
+103	2	2	2	2
+103	2	2	2	2
+103	2	2	2	2
+203	2	2	2	2
+203	2	2	2	2
+203	2	2	2	2
+303	2	2	2	2
+303	2	2	2	2
+303	2	2	2	2
+403	2	2	2	2
+403	2	2	2	2
+403	2	2	2	2
+4	3	3	3	3
+4	3	3	3	3
+4	3	3	3	3
+104	3	3	3	3
+104	3	3	3	3
+104	3	3	3	3
+204	3	3	3	3
+204	3	3	3	3
+204	3	3	3	3
+304	3	3	3	3
+304	3	3	3	3
+304	3	3	3	3
+404	3	3	3	3
+404	3	3	3	3
+404	3	3	3	3
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 JOIN tmp on t1.f2=tmp.f2
+ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30;
+f0	f1	f2	f1	f2
+3	2	2	2	2
+3	2	2	2	2
+3	2	2	2	2
+103	2	2	2	2
+103	2	2	2	2
+103	2	2	2	2
+203	2	2	2	2
+203	2	2	2	2
+203	2	2	2	2
+303	2	2	2	2
+303	2	2	2	2
+303	2	2	2	2
+403	2	2	2	2
+403	2	2	2	2
+403	2	2	2	2
+4	3	3	3	3
+4	3	3	3	3
+4	3	3	3	3
+104	3	3	3	3
+104	3	3	3	3
+104	3	3	3	3
+204	3	3	3	3
+204	3	3	3	3
+204	3	3	3	3
+304	3	3	3	3
+304	3	3	3	3
+304	3	3	3	3
+404	3	3	3	3
+404	3	3	3	3
+404	3	3	3	3
+SELECT FOUND_ROWS();
+FOUND_ROWS()
+1500
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 JOIN tmp on t1.f2=tmp.f2
+WHERE t1.f2>20
+ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30;
+f0	f1	f2	f1	f2
+24	23	23	23	23
+24	23	23	23	23
+24	23	23	23	23
+124	23	23	23	23
+124	23	23	23	23
+124	23	23	23	23
+224	23	23	23	23
+224	23	23	23	23
+224	23	23	23	23
+324	23	23	23	23
+324	23	23	23	23
+324	23	23	23	23
+424	23	23	23	23
+424	23	23	23	23
+424	23	23	23	23
+25	24	24	24	24
+25	24	24	24	24
+25	24	24	24	24
+125	24	24	24	24
+125	24	24	24	24
+125	24	24	24	24
+225	24	24	24	24
+225	24	24	24	24
+225	24	24	24	24
+325	24	24	24	24
+325	24	24	24	24
+325	24	24	24	24
+425	24	24	24	24
+425	24	24	24	24
+425	24	24	24	24
+SELECT FOUND_ROWS();
+FOUND_ROWS()
+1185
+CREATE VIEW v1 as SELECT * FROM t1 ORDER BY f1, f0 LIMIT 30;
+SELECT * FROM v1;
+f0	f1	f2
+1	0	0
+101	0	0
+201	0	0
+301	0	0
+401	0	0
+2	1	1
+102	1	1
+202	1	1
+302	1	1
+402	1	1
+3	2	2
+103	2	2
+203	2	2
+303	2	2
+403	2	2
+4	3	3
+104	3	3
+204	3	3
+304	3	3
+404	3	3
+5	4	4
+105	4	4
+205	4	4
+305	4	4
+405	4	4
+6	5	5
+106	5	5
+206	5	5
+306	5	5
+406	5	5
+drop view v1;
+CREATE VIEW v1 as SELECT * FROM t1 ORDER BY f1, f0 LIMIT 100;
+SELECT * FROM v1 ORDER BY f2, f0 LIMIT 30;
+f0	f1	f2
+1	0	0
+101	0	0
+201	0	0
+301	0	0
+401	0	0
+2	1	1
+102	1	1
+202	1	1
+302	1	1
+402	1	1
+11	10	10
+111	10	10
+211	10	10
+311	10	10
+411	10	10
+12	11	11
+112	11	11
+212	11	11
+312	11	11
+412	11	11
+13	12	12
+113	12	12
+213	12	12
+313	12	12
+413	12	12
+14	13	13
+114	13	13
+214	13	13
+314	13	13
+414	13	13
+CREATE VIEW v2 as SELECT * FROM t1 ORDER BY f2, f0 LIMIT 100;
+SELECT * FROM v1 JOIN v2 on v1.f1=v2.f1 ORDER BY v1.f2,v1.f0,v2.f0
+LIMIT 30;
+f0	f1	f2	f0	f1	f2
+1	0	0	1	0	0
+1	0	0	101	0	0
+1	0	0	201	0	0
+1	0	0	301	0	0
+1	0	0	401	0	0
+101	0	0	1	0	0
+101	0	0	101	0	0
+101	0	0	201	0	0
+101	0	0	301	0	0
+101	0	0	401	0	0
+201	0	0	1	0	0
+201	0	0	101	0	0
+201	0	0	201	0	0
+201	0	0	301	0	0
+201	0	0	401	0	0
+301	0	0	1	0	0
+301	0	0	101	0	0
+301	0	0	201	0	0
+301	0	0	301	0	0
+301	0	0	401	0	0
+401	0	0	1	0	0
+401	0	0	101	0	0
+401	0	0	201	0	0
+401	0	0	301	0	0
+401	0	0	401	0	0
+2	1	1	2	1	1
+2	1	1	102	1	1
+2	1	1	202	1	1
+2	1	1	302	1	1
+2	1	1	402	1	1
+SELECT floor(f1/10) f3, count(f2) FROM t1
+GROUP BY 1 ORDER BY 2,1 LIMIT 5;
+f3	count(f2)
+0	50
+1	50
+2	50
+3	50
+4	50
+SELECT floor(f1/10) f3, count(f2) FROM t1
+GROUP BY 1 ORDER BY 2,1 LIMIT 0;
+f3	count(f2)
+CREATE PROCEDURE wl1393_sp_test()
+BEGIN
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 30;
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 15 OFFSET 15;
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
+ORDER BY f2, f0 LIMIT 15 OFFSET 15;
+SELECT FOUND_ROWS();
+SELECT * FROM v1 ORDER BY f2, f0 LIMIT 30;
+END|
+CALL wl1393_sp_test()|
+f0	f1	f2
+12	11	11
+112	11	11
+212	11	11
+312	11	11
+412	11	11
+13	12	12
+113	12	12
+213	12	12
+313	12	12
+413	12	12
+14	13	13
+114	13	13
+214	13	13
+314	13	13
+414	13	13
+15	14	14
+115	14	14
+215	14	14
+315	14	14
+415	14	14
+16	15	15
+116	15	15
+216	15	15
+316	15	15
+416	15	15
+17	16	16
+117	16	16
+217	16	16
+317	16	16
+417	16	16
+f0	f1	f2
+15	14	14
+115	14	14
+215	14	14
+315	14	14
+415	14	14
+16	15	15
+116	15	15
+216	15	15
+316	15	15
+416	15	15
+17	16	16
+117	16	16
+217	16	16
+317	16	16
+417	16	16
+f0	f1	f2
+15	14	14
+115	14	14
+215	14	14
+315	14	14
+415	14	14
+16	15	15
+116	15	15
+216	15	15
+316	15	15
+416	15	15
+17	16	16
+117	16	16
+217	16	16
+317	16	16
+417	16	16
+FOUND_ROWS()
+445
+f0	f1	f2
+1	0	0
+101	0	0
+201	0	0
+301	0	0
+401	0	0
+2	1	1
+102	1	1
+202	1	1
+302	1	1
+402	1	1
+11	10	10
+111	10	10
+211	10	10
+311	10	10
+411	10	10
+12	11	11
+112	11	11
+212	11	11
+312	11	11
+412	11	11
+13	12	12
+113	12	12
+213	12	12
+313	12	12
+413	12	12
+14	13	13
+114	13	13
+214	13	13
+314	13	13
+414	13	13
+DROP PROCEDURE wl1393_sp_test|
+SELECT d1.f1, d1.f2 FROM t1
+LEFT JOIN (SELECT * FROM t1 ORDER BY f1 LIMIT 30) d1 on t1.f1=d1.f1
+ORDER BY d1.f2 DESC LIMIT 30;
+f1	f2
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+4	4
+4	4
+4	4
+4	4
+4	4
+SELECT * FROM t1 WHERE f1 = (SELECT f1 FROM t1 ORDER BY 1 LIMIT 1);
+f0	f1	f2
+1	0	0
+101	0	0
+201	0	0
+301	0	0
+401	0	0
+SELECT * FROM t1 WHERE f1 = (SELECT f1 FROM t1 ORDER BY 1 LIMIT 2);
+ERROR 21000: Subquery returns more than 1 row
+DROP TABLE t1, tmp;
+DROP VIEW v1, v2;
+# end of WL#1393 - Optimizing filesort with small limit
+#
+# Bug #58761
+# Crash in Field::is_null in field.h on subquery in WHERE clause
+#
+CREATE TABLE t1 (
+pk INT NOT NULL AUTO_INCREMENT,
+col_int_key INT DEFAULT NULL,
+col_varchar_key VARCHAR(1) DEFAULT NULL,
+PRIMARY KEY (pk),
+KEY col_varchar_key (col_varchar_key,col_int_key)
+);
+INSERT INTO t1 VALUES (27,7,'x');
+INSERT INTO t1 VALUES (28,6,'m');
+INSERT INTO t1 VALUES (29,4,'c');
+CREATE TABLE where_subselect
+SELECT DISTINCT `pk` AS field1 , `pk` AS field2 
+FROM t1 AS alias1 
+WHERE alias1 . `col_int_key` > 229 
+OR alias1 . `col_varchar_key` IS NOT NULL
+GROUP BY field1, field2
+;
+SELECT * 
+FROM where_subselect
+WHERE (field1, field2) IN (  
+SELECT DISTINCT `pk` AS field1 , `pk` AS field2 
+FROM t1 AS alias1 
+WHERE alias1 . `col_int_key` > 229 
+OR alias1 . `col_varchar_key` IS NOT NULL
+GROUP BY field1, field2
+);
+field1	field2
+27	27
+28	28
+29	29
+DROP TABLE t1;
+DROP TABLE where_subselect;
+# End of Bug #58761
 CREATE TABLE t1 (
 id1 INT NULL,
 id2 INT  NOT NULL,

=== modified file 'mysql-test/r/order_by_none.result'
--- a/mysql-test/r/order_by_none.result	2010-11-29 13:30:18 +0000
+++ b/mysql-test/r/order_by_none.result	2010-12-17 09:41:21 +0000
@@ -1504,6 +1504,890 @@ ORDER BY t2.c LIMIT 1;
 d
 52.5
 DROP TABLE t1,t2,t3;
+#
+# WL#1393 - Optimizing filesort with small limit
+#
+CREATE TABLE t1(f0 int auto_increment primary key, f1 int, f2 varchar(200));
+INSERT INTO t1(f1, f2) VALUES 
+(0,"0"),(1,"1"),(2,"2"),(3,"3"),(4,"4"),(5,"5"),
+(6,"6"),(7,"7"),(8,"8"),(9,"9"),(10,"10"),
+(11,"11"),(12,"12"),(13,"13"),(14,"14"),(15,"15"),
+(16,"16"),(17,"17"),(18,"18"),(19,"19"),(20,"20"),
+(21,"21"),(22,"22"),(23,"23"),(24,"24"),(25,"25"),
+(26,"26"),(27,"27"),(28,"28"),(29,"29"),(30,"30"),
+(31,"31"),(32,"32"),(33,"33"),(34,"34"),(35,"35"),
+(36,"36"),(37,"37"),(38,"38"),(39,"39"),(40,"40"),
+(41,"41"),(42,"42"),(43,"43"),(44,"44"),(45,"45"),
+(46,"46"),(47,"47"),(48,"48"),(49,"49"),(50,"50"),
+(51,"51"),(52,"52"),(53,"53"),(54,"54"),(55,"55"),
+(56,"56"),(57,"57"),(58,"58"),(59,"59"),(60,"60"),
+(61,"61"),(62,"62"),(63,"63"),(64,"64"),(65,"65"),
+(66,"66"),(67,"67"),(68,"68"),(69,"69"),(70,"70"),
+(71,"71"),(72,"72"),(73,"73"),(74,"74"),(75,"75"),
+(76,"76"),(77,"77"),(78,"78"),(79,"79"),(80,"80"),
+(81,"81"),(82,"82"),(83,"83"),(84,"84"),(85,"85"),
+(86,"86"),(87,"87"),(88,"88"),(89,"89"),(90,"90"),
+(91,"91"),(92,"92"),(93,"93"),(94,"94"),(95,"95"),
+(96,"96"),(97,"97"),(98,"98"),(99,"99");
+SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 100;
+f0	f1	f2
+1	0	0
+2	1	1
+3	2	2
+4	3	3
+5	4	4
+6	5	5
+7	6	6
+8	7	7
+9	8	8
+10	9	9
+11	10	10
+12	11	11
+13	12	12
+14	13	13
+15	14	14
+16	15	15
+17	16	16
+18	17	17
+19	18	18
+20	19	19
+21	20	20
+22	21	21
+23	22	22
+24	23	23
+25	24	24
+26	25	25
+27	26	26
+28	27	27
+29	28	28
+30	29	29
+31	30	30
+32	31	31
+33	32	32
+34	33	33
+35	34	34
+36	35	35
+37	36	36
+38	37	37
+39	38	38
+40	39	39
+41	40	40
+42	41	41
+43	42	42
+44	43	43
+45	44	44
+46	45	45
+47	46	46
+48	47	47
+49	48	48
+50	49	49
+51	50	50
+52	51	51
+53	52	52
+54	53	53
+55	54	54
+56	55	55
+57	56	56
+58	57	57
+59	58	58
+60	59	59
+61	60	60
+62	61	61
+63	62	62
+64	63	63
+65	64	64
+66	65	65
+67	66	66
+68	67	67
+69	68	68
+70	69	69
+71	70	70
+72	71	71
+73	72	72
+74	73	73
+75	74	74
+76	75	75
+77	76	76
+78	77	77
+79	78	78
+80	79	79
+81	80	80
+82	81	81
+83	82	82
+84	83	83
+85	84	84
+86	85	85
+87	86	86
+88	87	87
+89	88	88
+90	89	89
+91	90	90
+92	91	91
+93	92	92
+94	93	93
+95	94	94
+96	95	95
+97	96	96
+98	97	97
+99	98	98
+100	99	99
+SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 30;
+f0	f1	f2
+1	0	0
+2	1	1
+3	2	2
+4	3	3
+5	4	4
+6	5	5
+7	6	6
+8	7	7
+9	8	8
+10	9	9
+11	10	10
+12	11	11
+13	12	12
+14	13	13
+15	14	14
+16	15	15
+17	16	16
+18	17	17
+19	18	18
+20	19	19
+21	20	20
+22	21	21
+23	22	22
+24	23	23
+25	24	24
+26	25	25
+27	26	26
+28	27	27
+29	28	28
+30	29	29
+SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 0;
+f0	f1	f2
+SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 30;
+f0	f1	f2
+100	99	99
+99	98	98
+98	97	97
+97	96	96
+96	95	95
+95	94	94
+94	93	93
+93	92	92
+92	91	91
+91	90	90
+10	9	9
+90	89	89
+89	88	88
+88	87	87
+87	86	86
+86	85	85
+85	84	84
+84	83	83
+83	82	82
+82	81	81
+81	80	80
+9	8	8
+80	79	79
+79	78	78
+78	77	77
+77	76	76
+76	75	75
+75	74	74
+74	73	73
+73	72	72
+SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 0;
+f0	f1	f2
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 20;
+f0	f1	f2
+12	11	11
+13	12	12
+14	13	13
+15	14	14
+16	15	15
+17	16	16
+18	17	17
+19	18	18
+20	19	19
+21	20	20
+22	21	21
+23	22	22
+24	23	23
+25	24	24
+26	25	25
+27	26	26
+28	27	27
+29	28	28
+30	29	29
+31	30	30
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0;
+f0	f1	f2
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 10 OFFSET 10;
+f0	f1	f2
+22	21	21
+23	22	22
+24	23	23
+25	24	24
+26	25	25
+27	26	26
+28	27	27
+29	28	28
+30	29	29
+31	30	30
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0 OFFSET 10;
+f0	f1	f2
+set sort_buffer_size= 32768;
+CREATE TEMPORARY TABLE tmp (f1 int, f2 varchar(20));
+INSERT INTO tmp SELECT f1, f2 FROM t1;
+INSERT INTO t1(f1, f2) SELECT * FROM tmp;
+INSERT INTO tmp SELECT f1, f2 FROM t1;
+INSERT INTO t1(f1, f2) SELECT * FROM tmp;
+SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 30;
+f0	f1	f2
+1	0	0
+101	0	0
+201	0	0
+301	0	0
+401	0	0
+2	1	1
+102	1	1
+202	1	1
+302	1	1
+402	1	1
+3	2	2
+103	2	2
+203	2	2
+303	2	2
+403	2	2
+4	3	3
+104	3	3
+204	3	3
+304	3	3
+404	3	3
+5	4	4
+105	4	4
+205	4	4
+305	4	4
+405	4	4
+6	5	5
+106	5	5
+206	5	5
+306	5	5
+406	5	5
+SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 0;
+f0	f1	f2
+SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 30;
+f0	f1	f2
+100	99	99
+200	99	99
+300	99	99
+400	99	99
+500	99	99
+99	98	98
+199	98	98
+299	98	98
+399	98	98
+499	98	98
+98	97	97
+198	97	97
+298	97	97
+398	97	97
+498	97	97
+97	96	96
+197	96	96
+297	96	96
+397	96	96
+497	96	96
+96	95	95
+196	95	95
+296	95	95
+396	95	95
+496	95	95
+95	94	94
+195	94	94
+295	94	94
+395	94	94
+495	94	94
+SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 0;
+f0	f1	f2
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 20;
+f0	f1	f2
+12	11	11
+112	11	11
+212	11	11
+312	11	11
+412	11	11
+13	12	12
+113	12	12
+213	12	12
+313	12	12
+413	12	12
+14	13	13
+114	13	13
+214	13	13
+314	13	13
+414	13	13
+15	14	14
+115	14	14
+215	14	14
+315	14	14
+415	14	14
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0;
+f0	f1	f2
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 10 OFFSET 10;
+f0	f1	f2
+14	13	13
+114	13	13
+214	13	13
+314	13	13
+414	13	13
+15	14	14
+115	14	14
+215	14	14
+315	14	14
+415	14	14
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0 OFFSET 10;
+f0	f1	f2
+set sort_buffer_size= 32768;
+SELECT SQL_CALC_FOUND_ROWS * FROM t1
+ORDER BY f1, f0 LIMIT 30;
+f0	f1	f2
+1	0	0
+101	0	0
+201	0	0
+301	0	0
+401	0	0
+2	1	1
+102	1	1
+202	1	1
+302	1	1
+402	1	1
+3	2	2
+103	2	2
+203	2	2
+303	2	2
+403	2	2
+4	3	3
+104	3	3
+204	3	3
+304	3	3
+404	3	3
+5	4	4
+105	4	4
+205	4	4
+305	4	4
+405	4	4
+6	5	5
+106	5	5
+206	5	5
+306	5	5
+406	5	5
+SELECT FOUND_ROWS();
+FOUND_ROWS()
+500
+SELECT SQL_CALC_FOUND_ROWS * FROM t1
+ORDER BY f1, f0 LIMIT 0;
+f0	f1	f2
+SELECT FOUND_ROWS();
+FOUND_ROWS()
+500
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
+ORDER BY f2, f0 LIMIT 20;
+f0	f1	f2
+12	11	11
+112	11	11
+212	11	11
+312	11	11
+412	11	11
+13	12	12
+113	12	12
+213	12	12
+313	12	12
+413	12	12
+14	13	13
+114	13	13
+214	13	13
+314	13	13
+414	13	13
+15	14	14
+115	14	14
+215	14	14
+315	14	14
+415	14	14
+SELECT FOUND_ROWS();
+FOUND_ROWS()
+445
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
+ORDER BY f2, f0 LIMIT 0;
+f0	f1	f2
+SELECT FOUND_ROWS();
+FOUND_ROWS()
+445
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
+ORDER BY f2, f0 LIMIT 10 OFFSET 10;
+f0	f1	f2
+14	13	13
+114	13	13
+214	13	13
+314	13	13
+414	13	13
+15	14	14
+115	14	14
+215	14	14
+315	14	14
+415	14	14
+SELECT FOUND_ROWS();
+FOUND_ROWS()
+445
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
+ORDER BY f2, f0 LIMIT 0 OFFSET 10;
+f0	f1	f2
+SELECT FOUND_ROWS();
+FOUND_ROWS()
+445
+set sort_buffer_size= 327680;
+SELECT * FROM t1 JOIN tmp on t1.f2=tmp.f2
+ORDER BY tmp.f1, f0 LIMIT 30;
+f0	f1	f2	f1	f2
+1	0	0	0	0
+1	0	0	0	0
+1	0	0	0	0
+101	0	0	0	0
+101	0	0	0	0
+101	0	0	0	0
+201	0	0	0	0
+201	0	0	0	0
+201	0	0	0	0
+301	0	0	0	0
+301	0	0	0	0
+301	0	0	0	0
+401	0	0	0	0
+401	0	0	0	0
+401	0	0	0	0
+2	1	1	1	1
+2	1	1	1	1
+2	1	1	1	1
+102	1	1	1	1
+102	1	1	1	1
+102	1	1	1	1
+202	1	1	1	1
+202	1	1	1	1
+202	1	1	1	1
+302	1	1	1	1
+302	1	1	1	1
+302	1	1	1	1
+402	1	1	1	1
+402	1	1	1	1
+402	1	1	1	1
+SELECT * FROM t1 JOIN tmp on t1.f2=tmp.f2
+ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30;
+f0	f1	f2	f1	f2
+3	2	2	2	2
+3	2	2	2	2
+3	2	2	2	2
+103	2	2	2	2
+103	2	2	2	2
+103	2	2	2	2
+203	2	2	2	2
+203	2	2	2	2
+203	2	2	2	2
+303	2	2	2	2
+303	2	2	2	2
+303	2	2	2	2
+403	2	2	2	2
+403	2	2	2	2
+403	2	2	2	2
+4	3	3	3	3
+4	3	3	3	3
+4	3	3	3	3
+104	3	3	3	3
+104	3	3	3	3
+104	3	3	3	3
+204	3	3	3	3
+204	3	3	3	3
+204	3	3	3	3
+304	3	3	3	3
+304	3	3	3	3
+304	3	3	3	3
+404	3	3	3	3
+404	3	3	3	3
+404	3	3	3	3
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 JOIN tmp on t1.f2=tmp.f2
+ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30;
+f0	f1	f2	f1	f2
+3	2	2	2	2
+3	2	2	2	2
+3	2	2	2	2
+103	2	2	2	2
+103	2	2	2	2
+103	2	2	2	2
+203	2	2	2	2
+203	2	2	2	2
+203	2	2	2	2
+303	2	2	2	2
+303	2	2	2	2
+303	2	2	2	2
+403	2	2	2	2
+403	2	2	2	2
+403	2	2	2	2
+4	3	3	3	3
+4	3	3	3	3
+4	3	3	3	3
+104	3	3	3	3
+104	3	3	3	3
+104	3	3	3	3
+204	3	3	3	3
+204	3	3	3	3
+204	3	3	3	3
+304	3	3	3	3
+304	3	3	3	3
+304	3	3	3	3
+404	3	3	3	3
+404	3	3	3	3
+404	3	3	3	3
+SELECT FOUND_ROWS();
+FOUND_ROWS()
+1500
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 JOIN tmp on t1.f2=tmp.f2
+WHERE t1.f2>20
+ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30;
+f0	f1	f2	f1	f2
+24	23	23	23	23
+24	23	23	23	23
+24	23	23	23	23
+124	23	23	23	23
+124	23	23	23	23
+124	23	23	23	23
+224	23	23	23	23
+224	23	23	23	23
+224	23	23	23	23
+324	23	23	23	23
+324	23	23	23	23
+324	23	23	23	23
+424	23	23	23	23
+424	23	23	23	23
+424	23	23	23	23
+25	24	24	24	24
+25	24	24	24	24
+25	24	24	24	24
+125	24	24	24	24
+125	24	24	24	24
+125	24	24	24	24
+225	24	24	24	24
+225	24	24	24	24
+225	24	24	24	24
+325	24	24	24	24
+325	24	24	24	24
+325	24	24	24	24
+425	24	24	24	24
+425	24	24	24	24
+425	24	24	24	24
+SELECT FOUND_ROWS();
+FOUND_ROWS()
+1185
+CREATE VIEW v1 as SELECT * FROM t1 ORDER BY f1, f0 LIMIT 30;
+SELECT * FROM v1;
+f0	f1	f2
+1	0	0
+101	0	0
+201	0	0
+301	0	0
+401	0	0
+2	1	1
+102	1	1
+202	1	1
+302	1	1
+402	1	1
+3	2	2
+103	2	2
+203	2	2
+303	2	2
+403	2	2
+4	3	3
+104	3	3
+204	3	3
+304	3	3
+404	3	3
+5	4	4
+105	4	4
+205	4	4
+305	4	4
+405	4	4
+6	5	5
+106	5	5
+206	5	5
+306	5	5
+406	5	5
+drop view v1;
+CREATE VIEW v1 as SELECT * FROM t1 ORDER BY f1, f0 LIMIT 100;
+SELECT * FROM v1 ORDER BY f2, f0 LIMIT 30;
+f0	f1	f2
+1	0	0
+101	0	0
+201	0	0
+301	0	0
+401	0	0
+2	1	1
+102	1	1
+202	1	1
+302	1	1
+402	1	1
+11	10	10
+111	10	10
+211	10	10
+311	10	10
+411	10	10
+12	11	11
+112	11	11
+212	11	11
+312	11	11
+412	11	11
+13	12	12
+113	12	12
+213	12	12
+313	12	12
+413	12	12
+14	13	13
+114	13	13
+214	13	13
+314	13	13
+414	13	13
+CREATE VIEW v2 as SELECT * FROM t1 ORDER BY f2, f0 LIMIT 100;
+SELECT * FROM v1 JOIN v2 on v1.f1=v2.f1 ORDER BY v1.f2,v1.f0,v2.f0
+LIMIT 30;
+f0	f1	f2	f0	f1	f2
+1	0	0	1	0	0
+1	0	0	101	0	0
+1	0	0	201	0	0
+1	0	0	301	0	0
+1	0	0	401	0	0
+101	0	0	1	0	0
+101	0	0	101	0	0
+101	0	0	201	0	0
+101	0	0	301	0	0
+101	0	0	401	0	0
+201	0	0	1	0	0
+201	0	0	101	0	0
+201	0	0	201	0	0
+201	0	0	301	0	0
+201	0	0	401	0	0
+301	0	0	1	0	0
+301	0	0	101	0	0
+301	0	0	201	0	0
+301	0	0	301	0	0
+301	0	0	401	0	0
+401	0	0	1	0	0
+401	0	0	101	0	0
+401	0	0	201	0	0
+401	0	0	301	0	0
+401	0	0	401	0	0
+2	1	1	2	1	1
+2	1	1	102	1	1
+2	1	1	202	1	1
+2	1	1	302	1	1
+2	1	1	402	1	1
+SELECT floor(f1/10) f3, count(f2) FROM t1
+GROUP BY 1 ORDER BY 2,1 LIMIT 5;
+f3	count(f2)
+0	50
+1	50
+2	50
+3	50
+4	50
+SELECT floor(f1/10) f3, count(f2) FROM t1
+GROUP BY 1 ORDER BY 2,1 LIMIT 0;
+f3	count(f2)
+CREATE PROCEDURE wl1393_sp_test()
+BEGIN
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 30;
+SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 15 OFFSET 15;
+SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
+ORDER BY f2, f0 LIMIT 15 OFFSET 15;
+SELECT FOUND_ROWS();
+SELECT * FROM v1 ORDER BY f2, f0 LIMIT 30;
+END|
+CALL wl1393_sp_test()|
+f0	f1	f2
+12	11	11
+112	11	11
+212	11	11
+312	11	11
+412	11	11
+13	12	12
+113	12	12
+213	12	12
+313	12	12
+413	12	12
+14	13	13
+114	13	13
+214	13	13
+314	13	13
+414	13	13
+15	14	14
+115	14	14
+215	14	14
+315	14	14
+415	14	14
+16	15	15
+116	15	15
+216	15	15
+316	15	15
+416	15	15
+17	16	16
+117	16	16
+217	16	16
+317	16	16
+417	16	16
+f0	f1	f2
+15	14	14
+115	14	14
+215	14	14
+315	14	14
+415	14	14
+16	15	15
+116	15	15
+216	15	15
+316	15	15
+416	15	15
+17	16	16
+117	16	16
+217	16	16
+317	16	16
+417	16	16
+f0	f1	f2
+15	14	14
+115	14	14
+215	14	14
+315	14	14
+415	14	14
+16	15	15
+116	15	15
+216	15	15
+316	15	15
+416	15	15
+17	16	16
+117	16	16
+217	16	16
+317	16	16
+417	16	16
+FOUND_ROWS()
+445
+f0	f1	f2
+1	0	0
+101	0	0
+201	0	0
+301	0	0
+401	0	0
+2	1	1
+102	1	1
+202	1	1
+302	1	1
+402	1	1
+11	10	10
+111	10	10
+211	10	10
+311	10	10
+411	10	10
+12	11	11
+112	11	11
+212	11	11
+312	11	11
+412	11	11
+13	12	12
+113	12	12
+213	12	12
+313	12	12
+413	12	12
+14	13	13
+114	13	13
+214	13	13
+314	13	13
+414	13	13
+DROP PROCEDURE wl1393_sp_test|
+SELECT d1.f1, d1.f2 FROM t1
+LEFT JOIN (SELECT * FROM t1 ORDER BY f1 LIMIT 30) d1 on t1.f1=d1.f1
+ORDER BY d1.f2 DESC LIMIT 30;
+f1	f2
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+5	5
+4	4
+4	4
+4	4
+4	4
+4	4
+SELECT * FROM t1 WHERE f1 = (SELECT f1 FROM t1 ORDER BY 1 LIMIT 1);
+f0	f1	f2
+1	0	0
+101	0	0
+201	0	0
+301	0	0
+401	0	0
+SELECT * FROM t1 WHERE f1 = (SELECT f1 FROM t1 ORDER BY 1 LIMIT 2);
+ERROR 21000: Subquery returns more than 1 row
+DROP TABLE t1, tmp;
+DROP VIEW v1, v2;
+# end of WL#1393 - Optimizing filesort with small limit
+#
+# Bug #58761
+# Crash in Field::is_null in field.h on subquery in WHERE clause
+#
+CREATE TABLE t1 (
+pk INT NOT NULL AUTO_INCREMENT,
+col_int_key INT DEFAULT NULL,
+col_varchar_key VARCHAR(1) DEFAULT NULL,
+PRIMARY KEY (pk),
+KEY col_varchar_key (col_varchar_key,col_int_key)
+);
+INSERT INTO t1 VALUES (27,7,'x');
+INSERT INTO t1 VALUES (28,6,'m');
+INSERT INTO t1 VALUES (29,4,'c');
+CREATE TABLE where_subselect
+SELECT DISTINCT `pk` AS field1 , `pk` AS field2 
+FROM t1 AS alias1 
+WHERE alias1 . `col_int_key` > 229 
+OR alias1 . `col_varchar_key` IS NOT NULL
+GROUP BY field1, field2
+;
+SELECT * 
+FROM where_subselect
+WHERE (field1, field2) IN (  
+SELECT DISTINCT `pk` AS field1 , `pk` AS field2 
+FROM t1 AS alias1 
+WHERE alias1 . `col_int_key` > 229 
+OR alias1 . `col_varchar_key` IS NOT NULL
+GROUP BY field1, field2
+);
+field1	field2
+27	27
+28	28
+29	29
+DROP TABLE t1;
+DROP TABLE where_subselect;
+# End of Bug #58761
 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-12-17 09:41:21 +0000
@@ -0,0 +1,159 @@
+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");
+CREATE TEMPORARY TABLE tmp (f1 int, f2 varchar(20));
+INSERT INTO tmp SELECT f1,f2 FROM t1;
+INSERT INTO t1(f1,f2) SELECT * FROM tmp;
+INSERT INTO tmp SELECT f1,f2 FROM t1;
+INSERT INTO t1(f1,f2) SELECT * FROM tmp;
+INSERT INTO t1(f1,f2) SELECT * FROM tmp;
+INSERT INTO tmp SELECT f1,f2 FROM t1;
+INSERT INTO t1(f1,f2) SELECT * FROM tmp;
+INSERT INTO tmp SELECT f1,f2 FROM t1;
+INSERT INTO t1(f1,f2) SELECT * FROM tmp;
+INSERT INTO tmp SELECT f1,f2 FROM t1;
+INSERT INTO t1(f1,f2) SELECT * FROM tmp;
+INSERT INTO tmp SELECT f1,f2 FROM t1;
+INSERT INTO t1(f1,f2) SELECT * FROM tmp;
+INSERT INTO tmp SELECT f1,f2 FROM t1;
+INSERT INTO t1(f1,f2) SELECT * FROM tmp;
+set sort_buffer_size= 32768;
+FLUSH STATUS;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	0
+Sort_scan	0
+SELECT * FROM t1 ORDER BY f2 LIMIT 100;
+f0	f1	f2
+1	0	0
+101	0	0
+201	0	0
+301	0	0
+401	0	0
+501	0	0
+601	0	0
+701	0	0
+801	0	0
+901	0	0
+1001	0	0
+1101	0	0
+1201	0	0
+1301	0	0
+1401	0	0
+1501	0	0
+1601	0	0
+1701	0	0
+1801	0	0
+1901	0	0
+2001	0	0
+2101	0	0
+2201	0	0
+2301	0	0
+2401	0	0
+2501	0	0
+2601	0	0
+2701	0	0
+2801	0	0
+2901	0	0
+3001	0	0
+3101	0	0
+3201	0	0
+3301	0	0
+3401	0	0
+3501	0	0
+3601	0	0
+3701	0	0
+3801	0	0
+3901	0	0
+4001	0	0
+4101	0	0
+4201	0	0
+4301	0	0
+4401	0	0
+4501	0	0
+4601	0	0
+4701	0	0
+4801	0	0
+4901	0	0
+5001	0	0
+5101	0	0
+5201	0	0
+5301	0	0
+5401	0	0
+5501	0	0
+5601	0	0
+5701	0	0
+5801	0	0
+5901	0	0
+6001	0	0
+6101	0	0
+6201	0	0
+6301	0	0
+6401	0	0
+6501	0	0
+6601	0	0
+6701	0	0
+6801	0	0
+6901	0	0
+7001	0	0
+7101	0	0
+7201	0	0
+7301	0	0
+7401	0	0
+7501	0	0
+7601	0	0
+7701	0	0
+7801	0	0
+7901	0	0
+8001	0	0
+8101	0	0
+8201	0	0
+8301	0	0
+8401	0	0
+8501	0	0
+8601	0	0
+8701	0	0
+8801	0	0
+8901	0	0
+9001	0	0
+9101	0	0
+9201	0	0
+9301	0	0
+9401	0	0
+9501	0	0
+9601	0	0
+9701	0	0
+9801	0	0
+9901	0	0
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name	Value
+Sort_merge_passes	0
+Sort_range	0
+Sort_rows	100
+Sort_scan	1
+DROP TABLE t1, tmp;

=== modified file 'mysql-test/r/select_icp_mrr.result'
--- a/mysql-test/r/select_icp_mrr.result	2010-11-30 13:55:22 +0000
+++ b/mysql-test/r/select_icp_mrr.result	2010-12-17 09:41:21 +0000
@@ -4876,7 +4876,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,
@@ -4905,7 +4905,7 @@ Warning	1292	Truncated incorrect DOUBLE 
 Warning	1292	Truncated incorrect DOUBLE value: 'q'
 Warning	1292	Truncated incorrect DOUBLE value: 'm'
 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/select_none.result'
--- a/mysql-test/r/select_none.result	2010-11-29 13:30:18 +0000
+++ b/mysql-test/r/select_none.result	2010-12-17 09:41:21 +0000
@@ -4875,7 +4875,7 @@ SELECT 1 FROM t1 ORDER BY a COLLATE lati
 DROP TABLE t1;
 End of 5.1 tests
 #
-# Bug#45277: Lost HAVING clause led to a wrong result.
+# Bug#45227: Lost HAVING clause led to a wrong result.
 #
 CREATE TABLE `CC` (
 `int_nokey` int(11) NOT NULL,
@@ -4904,7 +4904,7 @@ Warning	1292	Truncated incorrect DOUBLE 
 Warning	1292	Truncated incorrect DOUBLE value: 'm'
 Warning	1292	Truncated incorrect DOUBLE value: 'j'
 DROP TABLE CC;
-# End of test#45277
+# End of test#45227
 #
 # Bug#54515: Crash in opt_range.cc::get_best_group_min_max on 
 #            SELECT from VIEW with GROUP BY

=== modified file 'mysql-test/r/subselect_innodb.result'
--- a/mysql-test/r/subselect_innodb.result	2010-12-06 12:55:03 +0000
+++ b/mysql-test/r/subselect_innodb.result	2010-12-17 09:41:21 +0000
@@ -392,3 +392,44 @@ and t2.a='1' AND t1.a=t3.b) > 0;
 a
 2
 DROP TABLE t1,t2,t3;
+#
+# Bug #58756
+# Crash in heap_rrnd on query with HAVING ... IN (subquery) + LIMIT
+#
+CREATE TABLE t1 (
+col_time_key time DEFAULT NULL,
+col_datetime_key datetime DEFAULT NULL,
+col_varchar_nokey varchar(1) DEFAULT NULL,
+KEY col_time_key (col_time_key),
+KEY col_datetime_key (col_datetime_key)
+) ENGINE=InnoDB DEFAULT CHARSET=latin1;
+INSERT INTO t1 VALUES ('17:53:30','2005-11-10 12:40:29','h');
+INSERT INTO t1 VALUES ('11:35:49','2009-04-25 00:00:00','b');
+INSERT INTO t1 VALUES (NULL,'2002-11-27 00:00:00','s');
+INSERT INTO t1 VALUES ('06:01:40','2004-01-26 20:32:32','e');
+INSERT INTO t1 VALUES ('05:45:11','2007-10-26 11:41:40','j');
+INSERT INTO t1 VALUES ('00:00:00','2005-10-07 00:00:00','e');
+INSERT INTO t1 VALUES ('00:00:00','2000-07-15 05:00:34','f');
+INSERT INTO t1 VALUES ('06:11:01','2000-04-03 16:33:32','v');
+INSERT INTO t1 VALUES ('13:02:46',NULL,'x');
+INSERT INTO t1 VALUES ('21:44:25','2001-04-25 01:26:12','m');
+INSERT INTO t1 VALUES ('22:43:58','2000-12-27 00:00:00','c');
+CREATE TABLE t2 (
+col_time_key time DEFAULT NULL,
+col_datetime_key datetime DEFAULT NULL,
+col_varchar_nokey varchar(1) DEFAULT NULL,
+KEY col_time_key (col_time_key),
+KEY col_datetime_key (col_datetime_key)
+) ENGINE=InnoDB DEFAULT CHARSET=latin1;
+INSERT INTO t2 VALUES ('11:28:45','2004-10-11 18:13:16','w');
+SELECT col_time_key, col_datetime_key
+FROM 
+( SELECT * FROM t1 ) AS table1 
+HAVING ( 'r' , 'e' ) IN 
+( SELECT col_varchar_nokey , col_varchar_nokey FROM t2 )
+ORDER BY col_datetime_key 
+LIMIT 10;
+col_time_key	col_datetime_key
+DROP TABLE t1;
+DROP TABLE t2;
+# End of Bug #58756

=== modified file 'mysql-test/t/group_by.test'
--- a/mysql-test/t/group_by.test	2010-12-16 19:28:42 +0000
+++ b/mysql-test/t/group_by.test	2010-12-17 09:41:21 +0000
@@ -1273,3 +1273,52 @@ SELECT f1,MIN(f2),MAX(f2) FROM t1 GROUP 
 
 DROP TABLE t1;
 --echo #End of test#49771
+
+--echo #
+--echo # Bug #58782
+--echo # Missing rows with SELECT .. WHERE .. IN subquery 
+--echo # with full GROUP BY and no aggr
+--echo #
+
+CREATE TABLE t1 (
+  pk INT NOT NULL,
+  col_int_nokey INT,
+  PRIMARY KEY (pk)
+);
+
+INSERT INTO t1 VALUES (10,7);
+INSERT INTO t1 VALUES (11,1);
+INSERT INTO t1 VALUES (12,5);
+INSERT INTO t1 VALUES (13,3);
+
+## original query:
+
+SELECT pk AS field1, col_int_nokey AS field2 
+FROM t1 
+WHERE col_int_nokey > 0
+GROUP BY field1, field2;
+
+## store query results in a new table:
+
+CREATE TABLE where_subselect
+  SELECT pk AS field1, col_int_nokey AS field2
+  FROM t1
+  WHERE col_int_nokey > 0
+  GROUP BY field1, field2
+;
+
+## query the new table and compare to original using WHERE ... IN():
+
+SELECT * 
+FROM where_subselect
+WHERE (field1, field2) IN (
+  SELECT pk AS field1, col_int_nokey AS field2
+  FROM t1
+  WHERE col_int_nokey > 0
+  GROUP BY field1, field2
+);
+
+DROP TABLE t1;
+DROP TABLE where_subselect;
+
+--echo # End of Bug #58782

=== 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-12-17 09:41:21 +0000
@@ -0,0 +1,64 @@
+#
+# WL#1393 - ORDER BY with LIMIT tests
+#
+# A big test in a separate file, so that we can run the original
+# order_by test with --debug without timeout.
+#
+# All the sort keys fit in memory, but the addon fields do not.
+#
+CREATE TABLE t1(
+  f0 int auto_increment PRIMARY KEY,
+  f1 int,
+  f2 varchar(200)
+);
+
+INSERT INTO t1(f1, f2) VALUES 
+(0,"0"),(1,"1"),(2,"2"),(3,"3"),(4,"4"),(5,"5"),
+(6,"6"),(7,"7"),(8,"8"),(9,"9"),(10,"10"),
+(11,"11"),(12,"12"),(13,"13"),(14,"14"),(15,"15"),
+(16,"16"),(17,"17"),(18,"18"),(19,"19"),(20,"20"),
+(21,"21"),(22,"22"),(23,"23"),(24,"24"),(25,"25"),
+(26,"26"),(27,"27"),(28,"28"),(29,"29"),(30,"30"),
+(31,"31"),(32,"32"),(33,"33"),(34,"34"),(35,"35"),
+(36,"36"),(37,"37"),(38,"38"),(39,"39"),(40,"40"),
+(41,"41"),(42,"42"),(43,"43"),(44,"44"),(45,"45"),
+(46,"46"),(47,"47"),(48,"48"),(49,"49"),(50,"50"),
+(51,"51"),(52,"52"),(53,"53"),(54,"54"),(55,"55"),
+(56,"56"),(57,"57"),(58,"58"),(59,"59"),(60,"60"),
+(61,"61"),(62,"62"),(63,"63"),(64,"64"),(65,"65"),
+(66,"66"),(67,"67"),(68,"68"),(69,"69"),(70,"70"),
+(71,"71"),(72,"72"),(73,"73"),(74,"74"),(75,"75"),
+(76,"76"),(77,"77"),(78,"78"),(79,"79"),(80,"80"),
+(81,"81"),(82,"82"),(83,"83"),(84,"84"),(85,"85"),
+(86,"86"),(87,"87"),(88,"88"),(89,"89"),(90,"90"),
+(91,"91"),(92,"92"),(93,"93"),(94,"94"),(95,"95"),
+(96,"96"),(97,"97"),(98,"98"),(99,"99");
+
+CREATE TEMPORARY TABLE tmp (f1 int, f2 varchar(20));
+INSERT INTO tmp SELECT f1,f2 FROM t1;
+INSERT INTO t1(f1,f2) SELECT * FROM tmp;
+INSERT INTO tmp SELECT f1,f2 FROM t1;
+INSERT INTO t1(f1,f2) SELECT * FROM tmp; 
+INSERT INTO t1(f1,f2) SELECT * FROM tmp;
+INSERT INTO tmp SELECT f1,f2 FROM t1;
+INSERT INTO t1(f1,f2) SELECT * FROM tmp; 
+INSERT INTO tmp SELECT f1,f2 FROM t1;
+INSERT INTO t1(f1,f2) SELECT * FROM tmp; 
+INSERT INTO tmp SELECT f1,f2 FROM t1;
+INSERT INTO t1(f1,f2) SELECT * FROM tmp; 
+INSERT INTO tmp SELECT f1,f2 FROM t1;
+INSERT INTO t1(f1,f2) SELECT * FROM tmp; 
+INSERT INTO tmp SELECT f1,f2 FROM t1;
+INSERT INTO t1(f1,f2) SELECT * FROM tmp; 
+
+# Test when only sortkeys fits to memory
+set sort_buffer_size= 32768; 
+
+FLUSH STATUS;
+SHOW SESSION STATUS LIKE 'Sort%';
+
+SELECT * FROM t1 ORDER BY f2 LIMIT 100;
+
+SHOW SESSION STATUS LIKE 'Sort%';
+
+DROP TABLE t1, tmp;

=== modified file 'mysql-test/t/subselect_innodb.test'
--- a/mysql-test/t/subselect_innodb.test	2010-08-14 07:28:31 +0000
+++ b/mysql-test/t/subselect_innodb.test	2010-12-17 09:41:21 +0000
@@ -402,3 +402,50 @@ SELECT t1.* FROM t1 WHERE (SELECT COUNT(
 
 DROP TABLE t1,t2,t3;
 
+--echo #
+--echo # Bug #58756
+--echo # Crash in heap_rrnd on query with HAVING ... IN (subquery) + LIMIT
+--echo #
+
+CREATE TABLE t1 (
+  col_time_key time DEFAULT NULL,
+  col_datetime_key datetime DEFAULT NULL,
+  col_varchar_nokey varchar(1) DEFAULT NULL,
+  KEY col_time_key (col_time_key),
+  KEY col_datetime_key (col_datetime_key)
+) ENGINE=InnoDB DEFAULT CHARSET=latin1;
+
+INSERT INTO t1 VALUES ('17:53:30','2005-11-10 12:40:29','h');
+INSERT INTO t1 VALUES ('11:35:49','2009-04-25 00:00:00','b');
+INSERT INTO t1 VALUES (NULL,'2002-11-27 00:00:00','s');
+INSERT INTO t1 VALUES ('06:01:40','2004-01-26 20:32:32','e');
+INSERT INTO t1 VALUES ('05:45:11','2007-10-26 11:41:40','j');
+INSERT INTO t1 VALUES ('00:00:00','2005-10-07 00:00:00','e');
+INSERT INTO t1 VALUES ('00:00:00','2000-07-15 05:00:34','f');
+INSERT INTO t1 VALUES ('06:11:01','2000-04-03 16:33:32','v');
+INSERT INTO t1 VALUES ('13:02:46',NULL,'x');
+INSERT INTO t1 VALUES ('21:44:25','2001-04-25 01:26:12','m');
+INSERT INTO t1 VALUES ('22:43:58','2000-12-27 00:00:00','c');
+
+CREATE TABLE t2 (
+  col_time_key time DEFAULT NULL,
+  col_datetime_key datetime DEFAULT NULL,
+  col_varchar_nokey varchar(1) DEFAULT NULL,
+  KEY col_time_key (col_time_key),
+  KEY col_datetime_key (col_datetime_key)
+) ENGINE=InnoDB DEFAULT CHARSET=latin1;
+
+INSERT INTO t2 VALUES ('11:28:45','2004-10-11 18:13:16','w');
+
+SELECT col_time_key, col_datetime_key
+FROM 
+( SELECT * FROM t1 ) AS table1 
+HAVING ( 'r' , 'e' ) IN 
+  ( SELECT col_varchar_nokey , col_varchar_nokey FROM t2 )
+ORDER BY col_datetime_key 
+LIMIT 10;
+
+DROP TABLE t1;
+DROP TABLE t2;
+
+--echo # End of Bug #58756

=== modified file 'mysys/CMakeLists.txt'
--- a/mysys/CMakeLists.txt	2010-08-12 15:27:53 +0000
+++ b/mysys/CMakeLists.txt	2010-12-17 09:41:21 +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-12-17 09:41:21 +0000
@@ -370,8 +370,8 @@ void queue_fix(QUEUE *queue)
    A test program for the priority queue implementation.
    It can also be used to benchmark changes of the implementation
    Build by doing the following in the directory mysys
-   make test_priority_queue
-   ./test_priority_queue
+   make queues
+   ./queues
 
    Written by Mikael Ronström, 2005
  */
@@ -381,11 +381,11 @@ static uint tot_no_parts= 0;
 static uint tot_no_loops= 0;
 static uint expected_part= 0;
 static uint expected_num= 0;
-static bool max_ind= 0;
-static bool fix_used= 0;
+static my_bool max_ind= 0;
+static my_bool fix_used= 0;
 static ulonglong start_time= 0;
 
-static bool is_divisible_by(uint num, uint divisor)
+static my_bool is_divisible_by(uint num, uint divisor)
 {
   uint quotient= num / divisor;
   if (quotient * divisor == num)
@@ -479,6 +479,7 @@ static int test_compare(void *null_arg, 
   uint a_num= (*(uint*)a) & 0x3FFFFF;
   uint b_num= (*(uint*)b) & 0x3FFFFF;
   uint a_part, b_part;
+  (void) null_arg;
   if (a_num > b_num)
     return +1;
   if (a_num < b_num)
@@ -492,7 +493,7 @@ static int test_compare(void *null_arg, 
   return 0;
 }
 
-bool check_num(uint num_part)
+my_bool check_num(uint num_part)
 {
   uint part= num_part >> 22;
   uint num= num_part & 0x3FFFFF;
@@ -543,7 +544,7 @@ void perform_insert(QUEUE *queue)
   }
 }
 
-bool perform_ins_del(QUEUE *queue, bool max_ind)
+my_bool perform_ins_del(QUEUE *queue, my_bool max_ind)
 {
   uint i= 0, no_loops= tot_no_loops, j= tot_no_parts;
   do
@@ -571,10 +572,10 @@ bool perform_ins_del(QUEUE *queue, bool 
   return FALSE;
 }
 
-bool do_test(uint no_parts, uint l_max_ind, bool l_fix_used)
+my_bool do_test(uint no_parts, uint l_max_ind, my_bool l_fix_used)
 {
   QUEUE queue;
-  bool result;
+  my_bool result;
   max_ind= l_max_ind;
   fix_used= l_fix_used;
   init_queue(&queue, no_parts, 0, max_ind, test_compare, NULL);

=== modified file 'sql/CMakeLists.txt'
--- a/sql/CMakeLists.txt	2010-11-29 13:21:04 +0000
+++ b/sql/CMakeLists.txt	2010-12-17 09:41:21 +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 
+               filesort_utils.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 
@@ -110,7 +111,8 @@ SET (SLAVE_SOURCE rpl_slave.cc rpl_repor
 		  rpl_info_table_access.cc server_ids.h)
 ADD_LIBRARY(slave ${SLAVE_SOURCE})
 ADD_DEPENDENCIES(slave GenError)
-ADD_LIBRARY(sqlgunitlib mdl.cc sql_list.cc sql_string.cc thr_malloc.cc)
+ADD_LIBRARY(sqlgunitlib
+  filesort_utils.cc mdl.cc sql_list.cc sql_string.cc thr_malloc.cc)
 ADD_DEPENDENCIES(sqlgunitlib GenError)
 
 

=== added file 'sql/bounded_queue.h'
--- a/sql/bounded_queue.h	1970-01-01 00:00:00 +0000
+++ b/sql/bounded_queue.h	2010-12-17 09:41:21 +0000
@@ -0,0 +1,195 @@
+/* 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 <string.h>
+#include "my_global.h"
+#include "my_base.h"
+#include "my_sys.h"
+#include "queues.h"
+
+class Sort_param;
+
+/**
+  A priority queue with a fixed, limited size.
+
+  This is a wrapper on top of QUEUE and the queue_xxx() functions.
+  It keeps the top-N elements which are inserted.
+
+  Elements of type Element_type are pushed into the queue.
+  For each element, we call a user-supplied keymaker_function,
+  to generate a key of type Key_type for the element.
+  Instances of Key_type are compared with the user-supplied compare_function.
+
+  The underlying QUEUE implementation needs one extra element for replacing
+  the lowest/highest element when pushing into a full queue.
+ */
+template<typename Element_type, typename Key_type>
+class Bounded_queue
+{
+public:
+  Bounded_queue()
+  {
+    memset(&m_queue, 0, sizeof(m_queue));
+  }
+
+  ~Bounded_queue()
+  {
+    delete_queue(&m_queue);
+  }
+
+  /**
+     Function for making sort-key from input data.
+     @param param Sort parameters.
+     @param to    Where to put the key.
+     @param from  The input data.
+  */
+  typedef void (*keymaker_function)(Sort_param *param,
+                                    Key_type *to,
+                                    Element_type *from);
+
+  /**
+     Function for comparing two keys.
+     @param  n Pointer to number of bytes to compare.
+     @param  a First key.
+     @param  b Second key.
+     @retval -1, 0, or 1 depending on whether the left argument is 
+             less than, equal to, or greater than the right argument.
+   */
+  typedef int (*compare_function)(size_t *n, Key_type **a, Key_type **b);
+
+  /**
+    Initialize the queue.
+
+    @param max_elements   The size of the queue.
+    @param max_at_top     Set to true if you want biggest element on top.
+           false: We keep the n largest elements.
+                  pop() will return the smallest key in the result set.
+           true:  We keep the n smallest elements.
+                  pop() will return the largest key in the result set.
+    @param compare        Compare function for elements, takes 3 arguments.
+                          If NULL, we use get_ptr_compare(compare_length).
+    @param compare_length Length of the data (i.e. the keys) used for sorting.
+    @param keymaker       Function which generates keys for elements.
+    @param sort_param     Sort parameters.
+    @param sort_keys      Array of pointers to keys to sort.
+
+    @retval 0 OK, 1 Could not allocate memory.
+
+    We do *not* take ownership of any of the input pointer arguments.
+   */
+  int init(ha_rows max_elements, bool max_at_top,
+           compare_function compare, size_t compare_length,
+           keymaker_function keymaker, Sort_param *sort_param,
+           Key_type **sort_keys);
+
+  /**
+    Pushes an element on the queue.
+    If the queue is already full, we discard one element.
+    Calls keymaker_function to generate a key for the element.
+
+    @param element        The element to be pushed.
+   */
+  void push(Element_type *element);
+
+  /**
+    Removes the top element from the queue.
+
+    @retval Pointer to the (key of the) removed element.
+
+    @note This function is for unit testing, where we push elements into to the
+          queue, and test that the appropriate keys are retained.
+          Interleaving of push() and pop() operations has not been tested.
+   */
+  Key_type **pop()
+  {
+    // Don't return the extra element to the client code.
+    if (queue_is_full((&m_queue)))
+      queue_remove(&m_queue, 0);
+    DBUG_ASSERT(m_queue.elements > 0);
+    if (m_queue.elements == 0)
+      return NULL;
+    return reinterpret_cast<Key_type**>(queue_remove(&m_queue, 0));
+  }
+
+  /**
+    The number of elements in the queue.
+   */
+  uint num_elements() const { return m_queue.elements; }
+
+  /**
+    Is the queue initialized?
+   */
+  bool is_initialized() const { return m_queue.max_elements > 0; }
+
+private:
+  Key_type         **m_sort_keys;
+  size_t             m_compare_length;
+  keymaker_function  m_keymaker;
+  Sort_param        *m_sort_param;
+  st_queue           m_queue;
+};
+
+
+template<typename Element_type, typename Key_type>
+int Bounded_queue<Element_type, Key_type>::init(ha_rows max_elements,
+                                                bool max_at_top,
+                                                compare_function compare,
+                                                size_t compare_length,
+                                                keymaker_function keymaker,
+                                                Sort_param *sort_param,
+                                                Key_type **sort_keys)
+{
+  DBUG_ASSERT(sort_keys != NULL);
+
+  m_sort_keys=      sort_keys;
+  m_compare_length= compare_length;
+  m_keymaker=       keymaker;
+  m_sort_param=     sort_param;
+  // init_queue() takes an uint, and also does (max_elements + 1)
+  if (max_elements >= (UINT_MAX - 1))
+    return 1;
+  if (compare == NULL)
+    compare=
+      reinterpret_cast<compare_function>(get_ptr_compare(compare_length));
+  // We allocate space for one extra element, for replace when queue is full.
+  return init_queue(&m_queue, (uint) max_elements + 1,
+                    0, max_at_top,
+                    reinterpret_cast<queue_compare>(compare),
+                    &m_compare_length);
+}
+
+
+template<typename Element_type, typename Key_type>
+void Bounded_queue<Element_type, Key_type>::push(Element_type *element)
+{
+  DBUG_ASSERT(is_initialized());
+  if (queue_is_full((&m_queue)))
+  {
+    // Replace top element with new key, and re-order the queue.
+    Key_type **pq_top= reinterpret_cast<Key_type **>(queue_top(&m_queue));
+    (*m_keymaker)(m_sort_param, *pq_top, element);
+    queue_replaced(&m_queue);
+  } else {
+    // Insert new key into the queue.
+    (*m_keymaker)(m_sort_param, m_sort_keys[m_queue.elements], element);
+    queue_insert(&m_queue,
+                 reinterpret_cast<uchar*>(&m_sort_keys[m_queue.elements]));
+  }
+}
+
+#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-12-17 09:41:21 +0000
@@ -32,42 +32,83 @@
 #include "probes_mysql.h"
 #include "sql_test.h"                           // TEST_filesort
 #include "opt_range.h"                          // SQL_SELECT
+#include "bounded_queue.h"
+#include "filesort_utils.h"
+#include "sql_select.h"
 
 #ifndef THREAD
 #define SKIP_DBUG_IN_FILESORT
 #endif
 
-/// How to write record_ref.
-#define WRITE_REF(file,from) \
-if (my_b_write((file),(uchar*) (from),param->ref_length)) \
-  DBUG_RETURN(1);
+#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION
+template class Bounded_queue<uchar, uchar>;
+#endif
 
 	/* functions defined in this file */
 
-static char **make_char_array(char **old_pos, register uint fields,
-                              uint length, myf my_flag);
+static void make_char_array(FILESORT_INFO *info, uint fields, uint length);
 static uchar *read_buffpek_from_file(IO_CACHE *buffer_file, uint count,
                                      uchar *buf);
-static ha_rows find_all_keys(SORTPARAM *param,SQL_SELECT *select,
-			     uchar * *sort_keys, IO_CACHE *buffer_file,
-			     IO_CACHE *tempfile,IO_CACHE *indexfile);
-static int write_keys(SORTPARAM *param,uchar * *sort_keys,
-		      uint count, IO_CACHE *buffer_file, IO_CACHE *tempfile);
-static void make_sortkey(SORTPARAM *param,uchar *to, uchar *ref_pos);
-static void register_used_fields(SORTPARAM *param);
-static int merge_index(SORTPARAM *param,uchar *sort_buffer,
-		       BUFFPEK *buffpek,
-		       uint maxbuffer,IO_CACHE *tempfile,
-		       IO_CACHE *outfile);
-static bool save_index(SORTPARAM *param,uchar **sort_keys, uint count, 
+static ha_rows find_all_keys(Sort_param *param,SQL_SELECT *select,
+                             uchar **sort_keys, IO_CACHE *buffer_file,
+                             IO_CACHE *tempfile,
+                             Bounded_queue<uchar, uchar> *pq,
+                             ha_rows *found_rows);
+static int write_keys(Sort_param *param,uchar * *sort_keys,
+                      uint count, IO_CACHE *buffer_file, IO_CACHE *tempfile);
+static void make_sortkey(Sort_param *param,uchar *to, uchar *ref_pos);
+static void register_used_fields(Sort_param *param);
+static int merge_index(Sort_param *param,uchar *sort_buffer,
+                       BUFFPEK *buffpek,
+                       uint maxbuffer,IO_CACHE *tempfile,
+                       IO_CACHE *outfile);
+static bool save_index(Sort_param *param,uchar **sort_keys, uint count, 
                        FILESORT_INFO *table_sort);
 static uint suffix_length(ulong string_length);
 static uint sortlength(THD *thd, SORT_FIELD *sortorder, uint s_length,
 		       bool *multi_byte_charset);
-static SORT_ADDON_FIELD *get_addon_fields(THD *thd, Field **ptabfield,
+static SORT_ADDON_FIELD *get_addon_fields(ulong max_length_for_sort_data,
+                                          Field **ptabfield,
                                           uint sortlength, uint *plength);
 static void unpack_addon_fields(struct st_sort_addon_field *addon_field,
                                 uchar *buff);
+static bool check_if_pq_applicable(Sort_param *param, FILESORT_INFO *info,
+                                   TABLE *table,
+                                   ha_rows records, ulong memory_available);
+
+
+void Sort_param::init_for_filesort(uint sortlen, TABLE *table,
+                                   ulong max_length_for_sort_data,
+                                   ha_rows maxrows, bool sort_positions)
+{
+  sort_length= sortlen;
+  ref_length= table->file->ref_length;
+  if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) &&
+      !table->fulltext_searched && !sort_positions)
+  {
+    /* 
+      Get the descriptors of all fields whose values are appended 
+      to sorted fields and get its total length in addon_length.
+    */
+    addon_field= get_addon_fields(max_length_for_sort_data,
+                                  table->field, sort_length, &addon_length);
+  }
+  if (addon_field)
+    res_length= addon_length;
+  else
+  {
+    res_length= ref_length;
+    /* 
+      The reference to the record is considered 
+      as an additional sorted field
+    */
+    sort_length+= ref_length;
+  }
+  rec_length= sort_length + addon_length;
+  max_rows= maxrows;
+}
+
+
 /**
   Sort a table.
   Creates a set of pointers that can be used to read the rows
@@ -80,18 +121,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[out] found_rows     Store the number of found rows here.
 
-  @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 +140,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,
+                 ha_rows *found_rows)
 {
   int error;
-  ulong memavl, min_sort_memory;
+  ulong memory_available= thd->variables.sortbuff_size;
   uint maxbuffer;
   BUFFPEK *buffpek;
-  ha_rows records= HA_POS_ERROR;
-  uchar **sort_keys= 0;
-  IO_CACHE tempfile, buffpek_pointers, *selected_records_file, *outfile; 
-  SORTPARAM param;
+  ha_rows num_rows= HA_POS_ERROR;
+  uchar **sort_keys= NULL;
+  IO_CACHE tempfile, buffpek_pointers, *outfile; 
+  Sort_param param;
   bool multi_byte_charset;
+  Bounded_queue<uchar, uchar> 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 +180,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 +188,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_for_filesort(sortlength(thd, sortorder, s_length,
+                                     &multi_byte_charset),
+                          table,
+                          thd->variables.max_length_for_sort_data,
+                          max_rows, sort_positions);
   /* filesort cannot handle zero-length records. */
   DBUG_ASSERT(param.sort_length);
-  param.ref_length= table->file->ref_length;
-  param.addon_field= 0;
-  param.addon_length= 0;
-  if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) &&
-      !table->fulltext_searched && !sort_positions)
-  {
-    /* 
-      Get the descriptors of all fields whose values are appended 
-      to sorted fields and get its total length in param.spack_length.
-    */
-    param.addon_field= get_addon_fields(thd, table->field, 
-                                        param.sort_length,
-                                        &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;
+  if (param.max_rows != HA_POS_ERROR &&
+      check_if_pq_applicable(&param, &table_sort,
+                             table, num_rows, memory_available))
+  {
+    DBUG_PRINT("info", ("filesort PQ is applicable"));
+    const size_t compare_length= param.sort_length;
+    if (pq.init(param.max_rows,
+                true,                           // max_at_top
+                NULL,                           // compare_function
+                compare_length,
+                &make_sortkey, &param, table_sort.sort_keys))
+    {
+      // If failed to init pq, fall back to merge-sort.
+      DBUG_PRINT("info", ("failed to allocate PQ, fallback to sort-merge"));
+      my_free(table_sort.sort_keys);
+      table_sort.sort_keys= NULL;
+    }
   }
-  sort_keys= table_sort.sort_keys;
-  if (memavl < min_sort_memory)
+  else
   {
-    my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR+ME_WAITTANG));
-    goto err;
+    DBUG_PRINT("info", ("filesort PQ is not applicable"));
+
+    const ulong min_sort_memory=
+      max(MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2);
+    while (memory_available >= min_sort_memory)
+    {
+      ulong keys= memory_available / (param.rec_length + sizeof(char*));
+      param.max_keys_per_buffer= (uint) min(num_rows, keys);
+      make_char_array(&table_sort, param.max_keys_per_buffer, param.rec_length);
+      if (table_sort.sort_keys)
+        break;
+      ulong old_memory_available= memory_available;
+      memory_available= memory_available/4*3;
+      if (memory_available < min_sort_memory &&
+          old_memory_available > min_sort_memory)
+        memory_available= min_sort_memory;
+    }
+    if (memory_available < min_sort_memory)
+    {
+      my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR+ME_WAITTANG));
+      goto err;
+    }
   }
+
+  sort_keys= table_sort.sort_keys;
   if (open_cached_file(&buffpek_pointers,mysql_tmpdir,TEMP_PREFIX,
 		       DISK_BUFFER_SIZE, MYF(MY_WME)))
     goto err;
 
-  param.keys--;  			/* TODO: check why we do this */
   param.sort_form= table;
   param.end=(param.local_sortorder=sortorder)+s_length;
-  if ((records=find_all_keys(&param,select,sort_keys, &buffpek_pointers,
-			     &tempfile, selected_records_file)) ==
-      HA_POS_ERROR)
+  num_rows= find_all_keys(&param, select, sort_keys, &buffpek_pointers,
+                          &tempfile, 
+                          pq.is_initialized() ? &pq : NULL,
+                          found_rows);
+  if (num_rows == HA_POS_ERROR)
     goto err;
-  maxbuffer= (uint) (my_b_tell(&buffpek_pointers)/sizeof(*buffpek));
 
+  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 +308,9 @@ ha_rows filesort(THD *thd, TABLE *table,
       Use also the space previously used by string pointers in sort_buffer
       for temporary key storage.
     */
-    param.keys=((param.keys*(param.rec_length+sizeof(char*))) /
-		param.rec_length-1);
+    param.max_keys_per_buffer=((param.max_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 +322,13 @@ ha_rows filesort(THD *thd, TABLE *table,
 		    outfile))
       goto err;
   }
-  if (records > param.max_rows)
-    records=param.max_rows;
-  error =0;
+
+  if (num_rows > param.max_rows)
+  {
+    // If find_all_keys() produced more results than the query LIMIT.
+    num_rows= param.max_rows;
+  }
+  error= 0;
 
  err:
   my_free(param.tmp_buffer);
@@ -332,15 +359,17 @@ 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 found_rows: %ld",
+              (long) num_rows, (long) *examined_rows, (long) *found_rows));
+  MYSQL_FILESORT_DONE(error, num_rows);
+  DBUG_RETURN(error ? HA_POS_ERROR : num_rows);
 } /* filesort */
 
 
@@ -364,25 +393,34 @@ void filesort_free_buffers(TABLE *table,
   table->sort.addon_field= NULL;
 }
 
-/** Make a array of string pointers. */
+/**
+  Makes an array of string pointers for info->sort_keys.
+
+  @param info         FILESORT_INFO struct owning the allocated array.
+  @param num_records  Number of records.
+  @param length       Length of each record.
+*/
 
-static char **make_char_array(char **old_pos, register uint fields,
-                              uint length, myf my_flag)
+static void make_char_array(FILESORT_INFO *info, uint num_records, 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)))
+  DBUG_PRINT("info", ("num_records %u length %u", num_records, length));
+
+  if (!info->sort_keys)
+    info->sort_keys= 
+      (uchar**) my_malloc(num_records * (length + sizeof(uchar*)), MYF(0));
+
+  if (info->sort_keys)
   {
-    pos=old_pos; char_pos=((char*) (pos+fields)) -length;
-    while (fields--) *(pos++) = (char_pos+= length);
+    uchar **pos= info->sort_keys;
+    uchar *char_pos= ((uchar*) (pos+num_records)) - length;
+    while (num_records--)
+      *(pos++)= (char_pos+= length);
   }
 
-  DBUG_RETURN(old_pos);
-} /* make_char_array */
+  DBUG_VOID_RETURN;
+}
 
 
 /** Read 'count' number of buffer pointers into memory. */
@@ -461,7 +499,8 @@ static void dbug_print_record(TABLE *tab
 #endif 
 
 /**
-  Search after sort_keys and write them into tempfile.
+  Search after sort_keys, and write them into tempfile
+  (if we run out of space in the sort_keys buffer).
   All produced sequences are guaranteed to be non-empty.
 
   @param param             Sorting parameter
@@ -470,20 +509,28 @@ 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().
+                           For a query with LIMIT, this value will typically
+                           be larger than the function return value.
 
   @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 +544,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<uchar, uchar> *pq,
+                             ha_rows *found_rows)
 {
   int error,flag,quick_select;
   uint idx,indexpos,ref_length;
@@ -512,6 +561,7 @@ 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":
@@ -525,12 +575,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 +627,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 +644,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 +656,23 @@ static ha_rows find_all_keys(SORTPARAM *
     if (!error && (!select ||
                    (!select->skip_record(thd, &skip_record) && !skip_record)))
     {
-      if (idx == param->keys)
+      ++(*found_rows);
+      if (pq)
+      {
+        pq->push(ref_pos);
+        idx= pq->num_elements();
+      }
+      else
       {
-	if (write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
-	  DBUG_RETURN(HA_POS_ERROR);
-	idx=0;
-	indexpos++;
+        if (idx == param->max_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 +702,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 +733,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 +796,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 +1049,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,18 +1087,16 @@ 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)
-    count=(uint) param->max_rows;
   if (!(to= table_sort->record_pointers= 
         (uchar*) my_malloc(res_length*count, MYF(MY_WME))))
     DBUG_RETURN(1);                 /* purecov: inspected */
@@ -1060,10 +1109,150 @@ static bool save_index(SORTPARAM *param,
 }
 
 
+/**
+  Test whether priority queue is worth using to get top elements of an
+  ordered result set. If it is, then allocates buffer for required amount of
+  records
+
+  @param param            Sort parameters.
+  @param filesort_info    Filesort information.
+  @param table            Table to sort.
+  @param num_rows         Estimate of number of rows in source record set.
+  @param memory_available Memory available for sorting.
+
+  DESCRIPTION
+    Given a query like this:
+      SELECT ... FROM t ORDER BY a1,...,an LIMIT max_rows;
+    This function tests whether a priority queue should be used to keep
+    the result. Necessary conditions are:
+    - estimate that it is actually cheaper than merge-sort
+    - enough memory to store the <max_rows> records.
+
+    If we don't have space for <max_rows> records, but we *do* have
+    space for <max_rows> keys, we may rewrite 'table' to sort with
+    references to records instead of additional data.
+    (again, based on estimates that it will actually be cheaper).
+
+   @retval
+    true  - if it's ok to use PQ
+    false - PQ will be slower than merge-sort, or there is not enough memory.
+*/
+
+bool check_if_pq_applicable(Sort_param *param,
+                            FILESORT_INFO *filesort_info,
+                            TABLE *table, ha_rows num_rows,
+                            ulong memory_available)
+{
+  DBUG_ENTER("check_if_pq_applicable");
+
+  /*
+    How much Priority Queue sort is slower than qsort.
+    Measurements (see unit test) indicate that PQ is roughly 3 times slower.
+  */
+  const double PQ_slowness= 3.0;
+
+  if (param->max_rows == HA_POS_ERROR)
+  {
+    DBUG_PRINT("info", ("No LIMIT"));
+    DBUG_RETURN(NULL);
+  }
+
+  if (param->max_rows + 2 >= UINT_MAX)
+  {
+    DBUG_PRINT("info", ("Too large LIMIT"));
+    DBUG_RETURN(NULL);
+  }
+
+  ulong num_available_keys=
+    memory_available / (param->rec_length + sizeof(char*));
+  // We need 1 extra record in the buffer, when using PQ.
+  param->max_keys_per_buffer= (uint) param->max_rows + 1;
+
+  if (num_rows < num_available_keys)
+  {
+    // The whole source set fits into memory.
+    if (param->max_rows < num_rows/PQ_slowness )
+    {
+      make_char_array(filesort_info,
+                      param->max_keys_per_buffer, param->rec_length);
+      DBUG_RETURN(filesort_info->sort_keys != NULL);
+    }
+    else
+    {
+      // PQ will be slower.
+      DBUG_RETURN(false);
+    }
+  }
+
+  // Do we have space for LIMIT rows in memory?
+  if (param->max_keys_per_buffer < num_available_keys)
+  {
+    make_char_array(filesort_info,
+                    param->max_keys_per_buffer, param->rec_length);
+    DBUG_RETURN(filesort_info->sort_keys != NULL);
+  }
+
+  // Try to strip off addon fields.
+  if (param->addon_field)
+  {
+    const ulong row_length=
+      param->sort_length + param->ref_length + sizeof(char*);
+    num_available_keys= memory_available / row_length;
+
+    // Can we fit all the keys in memory?
+    if (param->max_keys_per_buffer < num_available_keys)
+    {
+      const double sort_merge_cost=
+        get_merge_many_buffs_cost_fast(num_rows,
+                                       num_available_keys,
+                                       row_length);
+      /*
+        PQ has cost:
+        (insert + qsort) * log(queue size) / TIME_FOR_COMPARE_ROWID +
+        cost of file lookup afterwards.
+        The lookup cost is a bit pessimistic: we take scan_time and assume
+        that on average we find the row after scanning half of the file.
+        A better estimate would be lookup cost, but note that we are doing
+        random lookups here, rather than sequential scan.
+      */
+      const double pq_cpu_cost= 
+        (PQ_slowness * num_rows + param->max_keys_per_buffer) *
+        log((double) param->max_keys_per_buffer) / TIME_FOR_COMPARE_ROWID;
+      const double pq_io_cost=
+        param->max_rows * table->file->scan_time() / 2.0;
+      const double pq_cost= pq_cpu_cost + pq_io_cost;
+
+      if (sort_merge_cost < pq_cost)
+        DBUG_RETURN(false);
+
+      make_char_array(filesort_info,
+                      param->max_keys_per_buffer, param->rec_length);
+      if (filesort_info->sort_keys)
+      {
+        // Make attached data to be references instead of fields.
+        my_free(filesort_info->addon_buf);
+        my_free(filesort_info->addon_field);
+        filesort_info->addon_buf= NULL;
+        filesort_info->addon_field= NULL;
+        param->addon_field= NULL;
+        param->addon_length= 0;
+
+        param->res_length= param->ref_length;
+        param->sort_length+= param->ref_length;
+        param->rec_length= param->sort_length;
+
+        DBUG_RETURN(true);
+      }
+    }
+  }
+  DBUG_RETURN(false);
+}
+
+
 /** Merge buffers to make < MERGEBUFF2 buffers. */
 
-int merge_many_buff(SORTPARAM *param, uchar *sort_buffer,
-		    BUFFPEK *buffpek, uint *maxbuffer, IO_CACHE *t_file)
+int merge_many_buff(Sort_param *param, uchar *sort_buffer,
+                    BUFFPEK *buffpek, uint *maxbuffer, IO_CACHE *t_file)
 {
   register uint i;
   IO_CACHE t_file2,*from_file,*to_file,*temp;
@@ -1192,7 +1381,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 +1413,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->max_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 +1438,8 @@ 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 +1529,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->max_keys_per_buffer;
 
   /*
     As we know all entries in the buffer are unique, we only have to
@@ -1400,9 +1589,9 @@ err:
 
 	/* Do a merge to output-file (save only positions) */
 
-static int merge_index(SORTPARAM *param, uchar *sort_buffer,
-		       BUFFPEK *buffpek, uint maxbuffer,
-		       IO_CACHE *tempfile, IO_CACHE *outfile)
+static int merge_index(Sort_param *param, uchar *sort_buffer,
+                       BUFFPEK *buffpek, uint maxbuffer,
+                       IO_CACHE *tempfile, IO_CACHE *outfile)
 {
   DBUG_ENTER("merge_index");
   if (merge_buffers(param,tempfile,outfile,sort_buffer,buffpek,buffpek,
@@ -1554,7 +1743,8 @@ sortlength(THD *thd, SORT_FIELD *sortord
 */
 
 static SORT_ADDON_FIELD *
-get_addon_fields(THD *thd, Field **ptabfield, uint sortlength, uint *plength)
+get_addon_fields(ulong max_length_for_sort_data,
+                 Field **ptabfield, uint sortlength, uint *plength)
 {
   Field **pfield;
   Field *field;
@@ -1590,7 +1780,7 @@ get_addon_fields(THD *thd, Field **ptabf
     return 0;
   length+= (null_fields+7)/8;
 
-  if (length+sortlength > thd->variables.max_length_for_sort_data ||
+  if (length+sortlength > max_length_for_sort_data ||
       !(addonf= (SORT_ADDON_FIELD *) my_malloc(sizeof(SORT_ADDON_FIELD)*
                                                (fields+1), MYF(MY_WME))))
     return 0;

=== modified file 'sql/filesort.h'
--- a/sql/filesort.h	2010-07-02 02:58:51 +0000
+++ b/sql/filesort.h	2010-12-17 09:41:21 +0000
@@ -29,7 +29,7 @@ typedef struct st_sort_field SORT_FIELD;
 ha_rows filesort(THD *thd, TABLE *table, st_sort_field *sortorder,
                  uint s_length, SQL_SELECT *select,
                  ha_rows max_rows, bool sort_positions,
-                 ha_rows *examined_rows);
+                 ha_rows *examined_rows, ha_rows *found_rows);
 void filesort_free_buffers(TABLE *table, bool full);
 void change_double_for_sort(double nr,uchar *to);
 

=== added file 'sql/filesort_utils.cc'
--- a/sql/filesort_utils.cc	1970-01-01 00:00:00 +0000
+++ b/sql/filesort_utils.cc	2010-12-17 09:41:21 +0000
@@ -0,0 +1,86 @@
+/* Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved. 
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+#include "filesort_utils.h"
+#include "sql_const.h"
+#include "sql_sort.h"
+
+
+namespace {
+/**
+  A local helper function. See comments for get_merge_buffers_cost().
+ */
+double get_merge_cost(ha_rows num_elements, ha_rows num_buffers, uint elem_size)
+{
+  return 
+    2.0 * ((double) num_elements * elem_size) / IO_SIZE
+    + (double) num_elements * log((double) num_buffers) /
+      (TIME_FOR_COMPARE_ROWID * M_LN2);
+}
+}
+
+/**
+  This is a simplified, and faster version of @see get_merge_many_buffs_cost().
+  We calculate the cost of merging buffers, by simulating the actions
+  of @see merge_many_buff. For explanations of formulas below,
+  see comments for get_merge_buffers_cost().
+  TODO: Use this function for Unique::get_use_cost().
+*/
+double get_merge_many_buffs_cost_fast(ha_rows num_rows,
+                                      ha_rows num_keys_per_buffer,
+                                      uint    elem_size)
+{
+  ha_rows num_buffers= num_rows / num_keys_per_buffer;
+  ha_rows last_n_elems= num_rows % num_keys_per_buffer;
+  double total_cost;
+
+  // Calculate CPU cost of sorting buffers.
+  total_cost=
+    ( num_buffers * num_keys_per_buffer * log(1.0 + num_keys_per_buffer) +
+      last_n_elems * log(1.0 + last_n_elems) )
+    / TIME_FOR_COMPARE_ROWID;
+  
+  // Simulate behavior of merge_many_buff().
+  while (num_buffers >= MERGEBUFF2)
+  {
+    // Calculate # of calls to merge_buffers().
+    const ha_rows loop_limit= num_buffers - MERGEBUFF*3/2;
+    const ha_rows num_merge_calls= 1 + loop_limit/MERGEBUFF;
+    const ha_rows num_remaining_buffs=
+      num_buffers - num_merge_calls * MERGEBUFF;
+
+    // Cost of merge sort 'num_merge_calls'.
+    total_cost+=
+      num_merge_calls *
+      get_merge_cost(num_keys_per_buffer * MERGEBUFF, MERGEBUFF, elem_size);
+
+    // # of records in remaining buffers.
+    last_n_elems+= num_remaining_buffs * num_keys_per_buffer;
+
+    // Cost of merge sort of remaining buffers.
+    total_cost+=
+      get_merge_cost(last_n_elems, 1 + num_remaining_buffs, elem_size);
+
+    num_buffers= num_merge_calls;
+    num_keys_per_buffer*= MERGEBUFF;
+  }
+
+  // Simulate final merge_buff call.
+  last_n_elems+= num_keys_per_buffer * num_buffers;
+  total_cost+= get_merge_cost(last_n_elems, 1 + num_buffers, elem_size);
+  return total_cost;
+}
+
+

=== added file 'sql/filesort_utils.h'
--- a/sql/filesort_utils.h	1970-01-01 00:00:00 +0000
+++ b/sql/filesort_utils.h	2010-12-17 09:41:21 +0000
@@ -0,0 +1,29 @@
+#ifndef FILESORT_UTILS_INCLUDED
+
+#include "my_base.h"
+
+/*
+  Calculate cost of merge sort
+
+    @param num_rows            Total number of rows.
+    @param num_keys_per_buffer Number of keys per buffer.
+    @param elem_size           Size of each element.
+
+    Calculates cost of merge sort by simulating call to merge_many_buff().
+
+  @retval
+    Computed cost of merge sort in disk seeks.
+
+  @note
+    Declared here in order to be able to unit test it,
+    since library dependencies have not been sorted out yet.
+
+    See also comments get_merge_many_buffs_cost().
+*/
+
+#define FILESORT_UTILS_INCLUDED
+double get_merge_many_buffs_cost_fast(ha_rows num_rows,
+                                      ha_rows num_keys_per_buffer,
+                                      uint    elem_size);
+
+#endif  // FILESORT_UTILS_INCLUDED

=== modified file 'sql/item_subselect.cc'
--- a/sql/item_subselect.cc	2010-12-16 19:28:42 +0000
+++ b/sql/item_subselect.cc	2010-12-17 09:41:21 +0000
@@ -2043,7 +2043,8 @@ Item_allany_subselect::select_transforme
   exec_method= EXEC_EXISTS;
   if (upper_item)
     upper_item->show= 1;
-  DBUG_RETURN(select_in_like_transformer(join, func));
+  trans_res retval= select_in_like_transformer(join, func);
+  DBUG_RETURN(retval);
 }
 
 

=== modified file 'sql/sql_const.h'
--- a/sql/sql_const.h	2010-07-13 17:29:44 +0000
+++ b/sql/sql_const.h	2010-12-17 09:41:21 +0000
@@ -161,13 +161,13 @@
   instead of reading with keys.  The number says how many evaluation of the
   WHERE clause is comparable to reading one extra row from a table.
 */
-#define TIME_FOR_COMPARE   5	// 5 compares == one read
+#define TIME_FOR_COMPARE   5.0	// 5 compares == one read
 
 /**
   Number of comparisons of table rowids equivalent to reading one row from a 
   table.
 */
-#define TIME_FOR_COMPARE_ROWID  (TIME_FOR_COMPARE*2)
+#define TIME_FOR_COMPARE_ROWID  (TIME_FOR_COMPARE*2.0)
 
 /*
   For sequential disk seeks the cost formula is:

=== modified file 'sql/sql_delete.cc'
--- a/sql/sql_delete.cc	2010-10-21 11:34:17 +0000
+++ b/sql/sql_delete.cc	2010-12-17 09:41:21 +0000
@@ -227,6 +227,7 @@ bool mysql_delete(THD *thd, TABLE_LIST *
     uint         length= 0;
     SORT_FIELD  *sortorder;
     ha_rows examined_rows;
+    ha_rows found_rows;
     
     table->update_const_key_parts(conds);
     order= simple_remove_const(order, conds);
@@ -241,9 +242,10 @@ bool mysql_delete(THD *thd, TABLE_LIST *
                                                    MYF(MY_FAE | MY_ZEROFILL));
     
       if (!(sortorder= make_unireg_sortorder(order, &length, NULL)) ||
-	  (table->sort.found_records = filesort(thd, table, sortorder, length,
-                                                select, HA_POS_ERROR, 1,
-                                                &examined_rows))
+	  (table->sort.found_records= filesort(thd, table, sortorder, length,
+                                               select, HA_POS_ERROR,
+                                               true,
+                                               &examined_rows, &found_rows))
 	  == HA_POS_ERROR)
       {
         delete select;

=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc	2010-12-17 09:18:58 +0000
+++ b/sql/sql_select.cc	2010-12-17 09:41:21 +0000
@@ -1763,11 +1763,11 @@ JOIN::optimize()
 
   row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
 	      unit->select_limit_cnt);
-  /* select_limit is used to decide if we are likely to scan the whole table */
-  select_limit= unit->select_limit_cnt;
+  // m_select_limit is used to decide if we are likely to scan the whole table.
+  m_select_limit= unit->select_limit_cnt;
   if (having || (select_options & OPTION_FOUND_ROWS))
-    select_limit= HA_POS_ERROR;
-  do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
+    m_select_limit= HA_POS_ERROR;
+  do_send_rows = (unit->select_limit_cnt > 0) ? 1 : 0;
   // Ignore errors of execution if option IGNORE present
   if (thd->lex->ignore)
     thd->lex->current_select->no_error= 1;
@@ -2099,9 +2099,10 @@ JOIN::optimize()
         We have found that grouping can be removed since groups correspond to
         only one row anyway, but we still have to guarantee correct result
         order. The line below effectively rewrites the query from GROUP BY
-        <fields> to ORDER BY <fields>. There are two exceptions:
+        <fields> to ORDER BY <fields>. There are three exceptions:
         - if skip_sort_order is set (see above), then we can simply skip
           GROUP BY;
+        - if we are in a subquery, we don't have to maintain order
         - we can only rewrite ORDER BY if the ORDER BY fields are 'compatible'
           with the GROUP BY ones, i.e. either one is a prefix of another.
           We only check if the ORDER BY is a prefix of GROUP BY. In this case
@@ -2111,7 +2112,13 @@ JOIN::optimize()
           'order' as is.
        */
       if (!order || test_if_subpart(group_list, order))
-          order= skip_sort_order ? 0 : group_list;
+      {
+        if (skip_sort_order ||
+            select_lex->master_unit()->item) // This is a subquery
+          order= NULL;
+        else
+          order= group_list;
+      }
       /*
         If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be 
         rewritten to IGNORE INDEX FOR ORDER BY(fields).
@@ -2155,18 +2162,18 @@ JOIN::optimize()
     JOIN_TAB *tab= &join_tab[const_tables];
     bool all_order_fields_used;
     if (order)
-      skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1, 
+      skip_sort_order= test_if_skip_sort_order(tab, order, m_select_limit, 1, 
         &tab->table->keys_in_use_for_order_by);
     if ((group_list=create_distinct_group(thd, select_lex->ref_pointer_array,
                                           order, fields_list, all_fields,
 				          &all_order_fields_used)))
     {
       bool skip_group= (skip_sort_order &&
-        test_if_skip_sort_order(tab, group_list, select_limit, 1, 
+        test_if_skip_sort_order(tab, group_list, m_select_limit, 1, 
                                 &tab->table->keys_in_use_for_group_by) != 0);
       count_field_types(select_lex, &tmp_table_param, all_fields, 0);
       if ((skip_group && all_order_fields_used) ||
-	  select_limit == HA_POS_ERROR ||
+	  m_select_limit == HA_POS_ERROR ||
 	  (order && !skip_sort_order))
       {
 	/*  Change DISTINCT to GROUP BY */
@@ -2510,7 +2517,7 @@ JOIN::optimize()
     ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
                              !tmp_group &&
                              !thd->lex->current_select->with_sum_func) ?
-                            select_limit : HA_POS_ERROR;
+                            m_select_limit : HA_POS_ERROR;
 
     if (!(exec_tmp_table1=
 	  create_tmp_table(thd, &tmp_table_param, all_fields,
@@ -2560,6 +2567,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))
@@ -2740,6 +2748,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)
@@ -2848,7 +2858,7 @@ JOIN::exec()
 	(const_tables == tables ||
  	 ((simple_order || skip_sort_order) &&
 	  test_if_skip_sort_order(&join_tab[const_tables], order,
-				  select_limit, 0, 
+				  m_select_limit, 0, 
                                   &join_tab[const_tables].table->
                                     keys_in_use_for_query))))
       order=0;
@@ -3025,11 +3035,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))
@@ -3218,7 +3229,7 @@ JOIN::exec()
     }
     {
       if (group)
-	curr_join->select_limit= HA_POS_ERROR;
+	curr_join->m_select_limit= HA_POS_ERROR;
       else
       {
 	/*
@@ -3237,7 +3248,7 @@ JOIN::exec()
 	      (curr_table->keyuse && !curr_table->first_inner))
 	  {
 	    /* We have to sort all rows */
-	    curr_join->select_limit= HA_POS_ERROR;
+	    curr_join->m_select_limit= HA_POS_ERROR;
 	    break;
 	  }
 	}
@@ -3255,12 +3266,38 @@ JOIN::exec()
 	the query. XXX: it's never shown in EXPLAIN!
 	OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
       */
-      if (create_sort_index(thd, curr_join,
-			    curr_join->group_list ? 
-			    curr_join->group_list : curr_join->order,
-			    curr_join->select_limit,
-			    (select_options & OPTION_FOUND_ROWS ?
-			     HA_POS_ERROR : unit->select_limit_cnt),
+      DBUG_PRINT("info",("Sorting for order by/group by"));
+      ORDER *order_arg=
+        curr_join->group_list ? curr_join->group_list : curr_join->order;
+      /*
+        filesort_limit:	 Return only this many rows from filesort().
+        We can use select_limit_cnt only if we have no group_by and 1 table.
+        This allows us to use Bounded_queue for queries like:
+          "select SQL_CALC_FOUND_ROWS * from t1 order by b desc limit 1;"
+        m_select_limit == HA_POS_ERROR (we need a full table scan)
+        unit->select_limit_cnt == 1 (we only need one row in the result set)
+       */
+      const ha_rows filesort_limit_arg=
+        (has_group_by || curr_join->tables > 1)
+        ? curr_join->m_select_limit : unit->select_limit_cnt;
+      const ha_rows select_limit_arg=
+        select_options & OPTION_FOUND_ROWS
+        ? HA_POS_ERROR : unit->select_limit_cnt;
+
+      DBUG_PRINT("info", ("has_group_by %d "
+                          "curr_join->tables %d "
+                          "curr_join->m_select_limit %d "
+                          "unit->select_limit_cnt %d",
+                          has_group_by,
+                          curr_join->tables,
+                          (int) curr_join->m_select_limit,
+                          (int) 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;
@@ -3293,6 +3330,14 @@ 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)
+  {
+    /* 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;
@@ -18402,8 +18447,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)
       {
@@ -20082,6 +20145,8 @@ create_sort_index(THD *thd, JOIN *join, 
 {
   uint length= 0;
   ha_rows examined_rows;
+  ha_rows found_rows;
+  ha_rows filesort_retval= HA_POS_ERROR;
   TABLE *table;
   SQL_SELECT *select;
   JOIN_TAB *tab;
@@ -20154,10 +20219,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);
-  tab->records= table->sort.found_records;	// For SQL_CALC_ROWS
+  filesort_retval= filesort(thd, table, join->sortorder, length,
+                            select, filesort_limit, 0,
+                            &examined_rows, &found_rows);
+  table->sort.found_records= filesort_retval;
+  tab->records= found_rows;                     // For SQL_CALC_ROWS
   if (select)
   {
     /*
@@ -20186,7 +20252,7 @@ create_sort_index(THD *thd, JOIN *join, 
   tab->read_first_record= join_init_read_record;
   tab->join->examined_rows+=examined_rows;
   table->set_keyread(FALSE); // Restore if we used indexes
-  DBUG_RETURN(table->sort.found_records == HA_POS_ERROR);
+  DBUG_RETURN(filesort_retval == HA_POS_ERROR);
 err:
   DBUG_RETURN(-1);
 }
@@ -20503,7 +20569,7 @@ SORT_FIELD *make_unireg_sortorder(ORDER 
   pos= sort= sortorder;
 
   if (!pos)
-    return 0;
+    DBUG_RETURN(0);
 
   for (;order;order=order->next,pos++)
   {
@@ -20520,6 +20586,7 @@ SORT_FIELD *make_unireg_sortorder(ORDER 
     else
       pos->item= *order->item;
     pos->reverse=! order->asc;
+    DBUG_ASSERT(pos->field != NULL || pos->item != NULL);
   }
   *length=count;
   DBUG_RETURN(sort);

=== modified file 'sql/sql_select.h'
--- a/sql/sql_select.h	2010-12-16 17:38:26 +0000
+++ b/sql/sql_select.h	2010-12-17 09:41:21 +0000
@@ -1647,7 +1647,9 @@ public:
   table_map outer_join;
   /* Number of records produced after join + group operation */
   ha_rows  send_records;
-  ha_rows found_records,examined_rows,row_limit, select_limit;
+  ha_rows found_records,examined_rows,row_limit;
+  // m_select_limit is used to decide if we are likely to scan the whole table.
+  ha_rows m_select_limit;
   /**
     Used to fetch no more than given amount of rows per one
     fetch operation of server side cursor.

=== modified file 'sql/sql_sort.h'
--- a/sql/sql_sort.h	2010-07-02 18:15:21 +0000
+++ b/sql/sql_sort.h	2010-12-17 09:41:21 +0000
@@ -16,6 +16,7 @@
    along with this program; if not, write to the Free Software Foundation,
    51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA */
 
+#include "m_string.h"                           /* memset */
 #include "my_global.h"                          /* uchar */
 #include "my_base.h"                            /* ha_rows */
 #include "my_sys.h"                             /* qsort2_cmp */
@@ -27,7 +28,6 @@ typedef struct st_sort_field SORT_FIELD;
 class Field;
 struct TABLE;
 
-
 /* Defines used by filesort and uniques */
 
 #define MERGEBUFF		7
@@ -71,36 +71,46 @@ 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 max_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 */
+  SORT_ADDON_FIELD *addon_field; // Descriptors for companion fields.
   uchar *unique_buff;
   bool not_killable;
   char* tmp_buffer;
-  /* The fields below are used only by Unique class */
+  // 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_for_filesort(uint sortlen, TABLE *table,
+                         ulong max_length_for_sort_data,
+                         ha_rows maxrows, bool sort_positions);
+};
 
 
-int merge_many_buff(SORTPARAM *param, uchar *sort_buffer,
+int merge_many_buff(Sort_param *param, uchar *sort_buffer,
 		    BUFFPEK *buffpek,
 		    uint *maxbuffer, IO_CACHE *t_file);
 uint read_to_buffer(IO_CACHE *fromfile,BUFFPEK *buffpek,
 		    uint sort_length);
-int merge_buffers(SORTPARAM *param,IO_CACHE *from_file,
-		  IO_CACHE *to_file, uchar *sort_buffer,
-		  BUFFPEK *lastbuff,BUFFPEK *Fb,
-		  BUFFPEK *Tb,int flag);
+int merge_buffers(Sort_param *param,IO_CACHE *from_file,
+                  IO_CACHE *to_file, uchar *sort_buffer,
+                  BUFFPEK *lastbuff,BUFFPEK *Fb,
+                  BUFFPEK *Tb,int flag);
 void reuse_freed_buff(QUEUE *queue, BUFFPEK *reuse, uint key_length);
 
 #endif /* SQL_SORT_INCLUDED */

=== modified file 'sql/sql_table.cc'
--- a/sql/sql_table.cc	2010-11-29 16:27:58 +0000
+++ b/sql/sql_table.cc	2010-12-17 09:41:21 +0000
@@ -7074,6 +7074,7 @@ copy_data_between_tables(TABLE *from,TAB
   List<Item>   fields;
   List<Item>   all_fields;
   ha_rows examined_rows;
+  ha_rows found_rows;
   bool auto_increment_field_copied= 0;
   sql_mode_t save_sql_mode;
   ulonglong prev_insert_id;
@@ -7154,8 +7155,9 @@ copy_data_between_tables(TABLE *from,TAB
                       &tables, fields, all_fields, order) ||
           !(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)) ==
+                                              NULL, HA_POS_ERROR,
+                                              true,
+                                              &examined_rows, &found_rows)) ==
           HA_POS_ERROR)
         goto err;
     }

=== modified file 'sql/sql_update.cc'
--- a/sql/sql_update.cc	2010-12-16 10:09:53 +0000
+++ b/sql/sql_update.cc	2010-12-17 09:41:21 +0000
@@ -479,13 +479,15 @@ int mysql_update(THD *thd,
       uint         length= 0;
       SORT_FIELD  *sortorder;
       ha_rows examined_rows;
+      ha_rows found_rows;
 
       table->sort.io_cache = (IO_CACHE *) my_malloc(sizeof(IO_CACHE),
 						    MYF(MY_FAE | MY_ZEROFILL));
       if (!(sortorder=make_unireg_sortorder(order, &length, NULL)) ||
           (table->sort.found_records= filesort(thd, table, sortorder, length,
-                                               select, limit, 1,
-                                               &examined_rows))
+                                               select, limit,
+                                               true,
+                                               &examined_rows, &found_rows))
           == HA_POS_ERROR)
       {
 	goto err;

=== modified file 'sql/uniques.cc'
--- a/sql/uniques.cc	2010-11-05 22:14:29 +0000
+++ b/sql/uniques.cc	2010-12-17 09:41:21 +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,20 +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.rec_length= sort_param.sort_length= sort_param.ref_length= size;
+  sort_param.max_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) *
-				       sort_param.sort_length,
-				       MYF(0))))
+  if (!(sort_buffer=(uchar*) my_malloc((sort_param.max_keys_per_buffer + 1) *
+                                       sort_param.sort_length,
+                                       MYF(0))))
     return 1;
-  sort_param.unique_buff= sort_buffer+(sort_param.keys*
-				       sort_param.sort_length);
+  sort_param.unique_buff= sort_buffer+(sort_param.max_keys_per_buffer *
+                                       sort_param.sort_length);
 
   sort_param.compare= (qsort2_cmp) buffpek_compare;
   sort_param.cmp_context.key_compare= tree.compare;

=== modified file 'unittest/gunit/CMakeLists.txt'
--- a/unittest/gunit/CMakeLists.txt	2010-11-19 23:57:22 +0000
+++ b/unittest/gunit/CMakeLists.txt	2010-12-17 09:41:21 +0000
@@ -206,8 +206,17 @@ IF (CMAKE_CXX_COMPILER_ID STREQUAL "SunP
   ADD_DEFINITIONS("-library=stlport4")
 ENDIF()
 
-# Add tests (link them with sql library) 
-SET(TESTS dbug sql_list mdl mdl_mytap my_regex thread_utils)
+# Add tests (link them with gunit library) 
+SET(TESTS
+  bounded_queue
+  dbug
+  mdl
+  mdl_mytap
+  my_regex
+  sql_list
+  thread_utils
+  )
+
 FOREACH(test ${TESTS})
   ADD_EXECUTABLE(${test}-t ${test}-t.cc)
   TARGET_LINK_LIBRARIES(${test}-t gunit sqlgunitlib strings dbug regex)

=== added file 'unittest/gunit/bounded_queue-t.cc'
--- a/unittest/gunit/bounded_queue-t.cc	1970-01-01 00:00:00 +0000
+++ b/unittest/gunit/bounded_queue-t.cc	2010-12-17 09:41:21 +0000
@@ -0,0 +1,453 @@
+/* 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 <stddef.h>
+
+#include "bounded_queue.h"
+#include "filesort_utils.h"
+#include "my_sys.h"
+
+namespace {
+
+const int num_elements= 14;
+
+// A simple helper function to determine array size.
+template <class T, int size>
+int array_size(const T (&)[size])
+{
+  return size;
+}
+
+
+/*
+  Elements to be sorted by tests below.
+  We put some data in front of 'val' to verify (when debugging)
+  that all the reinterpret_casts involved when using QUEUE are correct.
+*/
+struct Test_element
+{
+  Test_element()      { *this= -1; }
+  Test_element(int i) { *this= i; }
+
+  Test_element &operator=(int i)
+  {
+    val= i;
+    snprintf(text, array_size(text), "%4d", i);
+    return *this;
+  }
+
+  char text[8]; // Some data.
+  int  val;     // The value we use for generating the key.
+};
+
+
+/*
+  The key, which is actually sorted by queue_xxx() functions.
+  We sort on the key only.
+ */
+struct Test_key
+{
+  Test_key() : element(NULL), key(-1) {}
+
+  Test_element *element; // The actual data element.
+  int           key;     // The generated key for the data element.
+};
+
+
+/*
+  Comparison function for Test_key objects.
+ */
+int test_key_compare(size_t *cmp_arg, Test_key **a, Test_key **b)
+{
+  EXPECT_EQ(*cmp_arg, sizeof(int));
+
+  int a_num= (*a)->key;
+  int b_num= (*b)->key;
+
+  if (a_num > b_num)
+    return +1;
+  if (a_num < b_num)
+    return -1;
+  return 0;
+}
+
+
+/*
+  Generates a Test_key for a given Test_element.
+ */
+void test_keymaker(Sort_param *sp, Test_key *key, Test_element *element)
+{
+  key->element= element;
+  key->key= element->val;
+}
+
+
+/*
+  A struct to wrap the actual keys, and an array of pointers to the keys.
+ */
+template<int sz, typename Key_type>
+struct Key_container
+{
+  Key_container()
+  {
+    for (int ix= 0; ix <= sz; ++ix)
+      key_ptrs[ix]= &key_data[ix];
+  }
+
+  Key_type *key_ptrs[sz+1];
+  Key_type  key_data[sz+1];
+};
+
+
+class BoundedQueueTest : public ::testing::Test
+{
+protected:
+  BoundedQueueTest() : m_key_size(sizeof(int))
+  {
+  }
+
+  virtual void SetUp()
+  {
+    int ix;
+    for (ix=0; ix < array_size(m_test_data); ++ix)
+      m_test_data[ix]= ix;
+    std::random_shuffle(&m_test_data[0], &m_test_data[array_size(m_test_data)]);
+  }
+
+  void insert_test_data()
+  {
+    for (int ix= 0; ix < array_size(m_test_data); ++ix)
+      m_queue.push(&m_test_data[ix]);
+  }
+
+  // Key pointers and data, used by the queue_xxx() functions.
+  Key_container<num_elements / 2, Test_key> m_keys;
+
+  // Some random intput data, to be sorted.
+  Test_element  m_test_data[num_elements];
+
+  size_t m_key_size;
+  Bounded_queue<Test_element, Test_key> m_queue;
+private:
+  GTEST_DISALLOW_COPY_AND_ASSIGN_(BoundedQueueTest);
+};
+
+
+// Google Test recommends DeathTest suffix for classes used in death tests.
+typedef BoundedQueueTest BoundedQueueDeathTest;
+
+#if !defined(DBUG_OFF)
+/*
+  Verifies that we DBUG_ASSERT if trying to push to an un-initialized queue.
+ */
+TEST_F(BoundedQueueDeathTest, die_if_not_initialized)
+{
+  ::testing::FLAGS_gtest_death_test_style = "threadsafe";
+  Test_element foo= 1;
+  EXPECT_DEATH_IF_SUPPORTED(m_queue.push(&foo),
+                            ".*Assertion .*is_initialized.*");
+}
+
+/*
+  Verifies that popping an empty queue hits a DBUG_ASSERT.
+ */
+TEST_F(BoundedQueueDeathTest, die_if_popping_empty_queue)
+{
+  EXPECT_EQ(0, m_queue.init(0, true, test_key_compare,
+                            m_key_size,
+                            &test_keymaker, NULL, m_keys.key_ptrs));
+  ::testing::FLAGS_gtest_death_test_style = "threadsafe";
+  EXPECT_DEATH_IF_SUPPORTED(m_queue.pop(),
+                            ".*Assertion .*elements > 0.*");
+}
+#endif  // !defined(DBUG_OFF)
+
+
+/*
+  Verifies that construct, initialize, destroy works.
+ */
+TEST_F(BoundedQueueTest, construct_and_destruct)
+{
+  EXPECT_EQ(0, m_queue.init(num_elements/2, true,
+                            test_key_compare,
+                            m_key_size,
+                            &test_keymaker, NULL, m_keys.key_ptrs));
+}
+
+
+/*
+  Verifies that we reject too large queues.
+ */
+TEST_F(BoundedQueueTest, too_many_elements)
+{
+  EXPECT_EQ(1, m_queue.init(UINT_MAX, true,
+                            test_key_compare,
+                            m_key_size,
+                            &test_keymaker, NULL, m_keys.key_ptrs));
+  EXPECT_EQ(1, m_queue.init(UINT_MAX - 1, true,
+                            test_key_compare,
+                            m_key_size,
+                            &test_keymaker, NULL, m_keys.key_ptrs));
+}
+
+
+/*
+  Verifies that zero-size queue works.
+ */
+TEST_F(BoundedQueueTest, zero_size_queue)
+{
+  EXPECT_EQ(0, m_queue.init(0, true, test_key_compare,
+                            m_key_size,
+                            &test_keymaker, NULL, m_keys.key_ptrs));
+  insert_test_data();
+  EXPECT_EQ(1U, m_queue.num_elements());
+}
+
+
+/*
+  Verifies that push and bounded size works, and that pop() gives sorted order.
+ */
+TEST_F(BoundedQueueTest, push_and_pop_keep_largest)
+{
+  EXPECT_EQ(0, m_queue.init(num_elements/2, false, test_key_compare,
+                            m_key_size,
+                            &test_keymaker, NULL, m_keys.key_ptrs));
+  insert_test_data();
+  // We expect the queue to contain [7 .. 13]
+  const int max_key_val= array_size(m_test_data) - 1;
+  while (m_queue.num_elements() > 0)
+  {
+    Test_key **top= m_queue.pop();
+    int expected_key_val= max_key_val - m_queue.num_elements();
+    int key_val= (*top)->key;
+    EXPECT_EQ(expected_key_val, key_val);
+    Test_element *element= (*top)->element;
+    EXPECT_EQ(expected_key_val, element->val);
+  }
+}
+
+
+/*
+  Verifies that push and bounded size works, and that pop() gives sorted order.
+  Note that with max_at_top == true, we will pop() in reverse order.
+ */
+TEST_F(BoundedQueueTest, push_and_pop_keep_smallest)
+{
+  EXPECT_EQ(0, m_queue.init(num_elements/2, true, test_key_compare,
+                            m_key_size,
+                            &test_keymaker, NULL, m_keys.key_ptrs));
+  insert_test_data();
+  // We expect the queue to contain [6 .. 0]
+  while (m_queue.num_elements() > 0)
+  {
+    Test_key **top= m_queue.pop();
+    int expected_key_val= m_queue.num_elements();
+    int key_val= (*top)->key;
+    EXPECT_EQ(expected_key_val, key_val);
+    Test_element *element= (*top)->element;
+    EXPECT_EQ(expected_key_val, element->val);
+  }
+}
+
+
+/*
+  Verifies that push, with bounded size, followed by sort() works.
+ */
+TEST_F(BoundedQueueTest, insert_and_sort)
+{
+  EXPECT_EQ(0, m_queue.init(num_elements/2, true, test_key_compare,
+                            m_key_size,
+                            &test_keymaker, NULL, m_keys.key_ptrs));
+  insert_test_data();
+  uchar *base=  (uchar*) &m_keys.key_ptrs[0];
+  size_t size=  sizeof(Test_key);
+  // We sort our keys as strings, so erase all the element pointers first.
+  for (int ii= 0; ii < array_size(m_keys.key_data); ++ii)
+    m_keys.key_data[ii].element= NULL;
+
+  my_string_ptr_sort(base, array_size(m_keys.key_ptrs), size);
+  for (int ii= 0; ii < num_elements/2; ++ii)
+  {
+    Test_key *sorted_key= m_keys.key_ptrs[ii];
+    EXPECT_EQ(ii, sorted_key->key);
+  }
+}
+
+
+/*
+  A test of the function get_merge_many_buffs_cost_fast()
+ */
+TEST(CostEstimationTest, merge_many_buff)
+{
+  ha_rows num_rows= 512;
+  ulong num_keys= 100;
+  ulong row_lenght= 100;
+  double prev_cost= 0.0;
+  while (num_rows <= MAX_FILE_SIZE/4)
+  {
+    double merge_cost=
+      get_merge_many_buffs_cost_fast(num_rows, num_keys, row_lenght);
+    EXPECT_LT(0.0, merge_cost);
+    EXPECT_LT(prev_cost, merge_cost);
+    num_rows*= 2;
+    prev_cost= merge_cost;
+  }
+}
+
+
+/*
+  Comparison function for integers.
+ */
+int int_ptr_compare(size_t *cmp_arg, int **a, int **b)
+{
+  EXPECT_EQ(*cmp_arg, sizeof(int));
+
+  int a_num= **a;
+  int b_num= **b;
+
+  if (a_num > b_num)
+    return +1;
+  if (a_num < b_num)
+    return -1;
+  return 0;
+}
+
+
+/*
+  Generates an integer key for a given integer element.
+ */
+void int_keymaker(Sort_param *sp, int *to, int *from)
+{
+  memcpy(to, from, sizeof(int));
+}
+
+
+/*
+  Some basic performance testing, to compute the overhead of Bounded_queue.
+  Run the with 'bounded_queue-t --disable-tap-output' to see the
+  millisecond output from Google Test.
+ */
+const int num_rows= 10000;
+const int row_limit= 100;
+const int num_iterations= 1000;
+
+class PerfTestSmall : public ::testing::Test
+{
+public:
+  /*
+    The extra overhead of malloc/free should be part of the measurement,
+    so we do not define the key container as a member here.
+  */
+  typedef Key_container<row_limit, int> Container;
+  enum { limit= row_limit };
+};
+
+class PerfTestLarge : public ::testing::Test
+{
+public:
+  /*
+    The extra overhead of malloc/free should be part of the measurement,
+    so we do not define the key container as a member here.
+  */
+  typedef Key_container<num_rows, int> Container;
+  enum { limit= num_rows };
+};
+
+
+template <int limit>
+void insert_and_sort()
+{
+  typedef Key_container<limit, int> Container;
+  for (int it= 0; it < num_iterations; ++it)
+  {
+    Container *keys= new Container;
+    srand(0);
+    Bounded_queue<int, int> queue;
+    EXPECT_EQ(0, queue.init(limit, true, int_ptr_compare,
+                            sizeof(int), &int_keymaker, NULL, keys->key_ptrs));
+    for (int ix= 0; ix < num_rows; ++ix)
+    {
+      int data= rand();
+      queue.push(&data);
+    }
+    my_string_ptr_sort((uchar*) &keys->key_ptrs[0],
+                       queue.num_elements(), sizeof(int));
+    delete keys;
+  }
+}
+
+
+/*
+  Test with Bounded_queue size == <limit>.
+ */
+TEST_F(PerfTestSmall, insert_and_sort)
+{
+  insert_and_sort<limit>();
+}
+
+
+/*
+  Test with Bounded_queue size == <number of rows>
+ */
+TEST_F(PerfTestLarge, insert_and_sort)
+{
+  insert_and_sort<limit>();
+}
+
+
+/*
+  Test without bounded queue, i.e. insert keys into array, and sort it.
+ */
+TEST_F(PerfTestLarge, without_queue)
+{
+  for (int it= 0; it < num_iterations; ++it)
+  {
+    Container *keys= new Container;
+    srand(0);
+    for (int ix= 0; ix < limit; ++ix)
+    {
+      int data= rand();
+      keys->key_data[ix]= data;
+    }
+    my_string_ptr_sort((uchar*) &keys->key_ptrs[0], limit, sizeof(int));
+    delete keys;
+  }
+}
+
+
+/*
+  Computes the overhead of setting up sort arrays, and rand() calls.
+ */
+TEST_F(PerfTestLarge, no_sorting)
+{
+  for (int it= 0; it < num_iterations; ++it)
+  {
+    Container *keys= new Container;
+    srand(0);
+    for (int ix= 0; ix < limit; ++ix)
+    {
+      int data= rand();
+      keys->key_data[ix]= data;
+    }
+    delete keys;
+  }
+}
+
+}  // namespace

No bundle (reason: useless for push emails).
Thread
bzr push into mysql-trunk-bugfixing branch (tor.didriksen:3442 to 3443)WL#1393Tor Didriksen17 Dec