[Commits] Rev 3428: MDEV-415: Back-port of the WL task #1393 from the mysql-5.6 code line. in file:///home/igor/maria/maria-10.0-mdev415/

Igor Babaev igor at askmonty.org
Sat Sep 1 02:51:56 EEST 2012


At file:///home/igor/maria/maria-10.0-mdev415/

------------------------------------------------------------
revno: 3428
revision-id: igor at askmonty.org-20120831235152-qnaf5ybb09p25xds
parent: monty at askmonty.org-20120706161018-y5teinbuqpchle2m
committer: Igor Babaev <igor at askmonty.org>
branch nick: maria-10.0-mdev415
timestamp: Fri 2012-08-31 16:51:52 -0700
message:
  MDEV-415: Back-port of the WL task #1393 from the mysql-5.6 code line.
  The task adds a more efficient handling of the queries with 
  ORDER BY order LIMIT n, such that n is small enough and
  no indexes are used for order.
-------------- next part --------------
=== modified file 'include/my_sys.h'
--- a/include/my_sys.h	2012-05-29 21:37:55 +0000
+++ b/include/my_sys.h	2012-08-31 23:51:52 +0000
@@ -712,6 +712,7 @@
 extern void handle_recived_signals(void);
 
 extern sig_handler my_set_alarm_variable(int signo);
+extern my_bool radixsort_is_appliccable(uint n_items, size_t size_of_element);
 extern void my_string_ptr_sort(uchar *base,uint items,size_t size);
 extern void radixsort_for_str_ptr(uchar* base[], uint number_of_elements,
 				  size_t size_of_element,uchar *buffer[]);

=== modified file 'libmysqld/CMakeLists.txt'
--- a/libmysqld/CMakeLists.txt	2012-05-22 09:04:32 +0000
+++ b/libmysqld/CMakeLists.txt	2012-08-31 23:51:52 +0000
@@ -44,6 +44,7 @@
            ../sql-common/client_plugin.c ../sql-common/mysql_async.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/slave.cc
            ../sql/signal_handler.cc
            ../sql/handler.cc ../sql/hash_filo.cc ../sql/hostname.cc 

=== modified file 'mysql-test/r/filesort_debug.result'
--- a/mysql-test/r/filesort_debug.result	2012-04-10 06:28:13 +0000
+++ b/mysql-test/r/filesort_debug.result	2012-08-31 23:51:52 +0000
@@ -4,7 +4,7 @@
 #
 CREATE TABLE t1(f0 int auto_increment primary key, f1 int);
 INSERT INTO t1(f1) VALUES (0),(1),(2),(3),(4),(5);
-SET session debug_dbug= '+d,make_sort_keys_alloc_fail';
+SET session debug_dbug= '+d,alloc_sort_buffer_fail';
 CALL mtr.add_suppression("Out of sort memory");
 SELECT * FROM t1 ORDER BY f1 ASC, f0;
 ERROR HY001: Out of sort memory, consider increasing server sort buffer size

=== modified file 'mysql-test/r/group_by.result'
--- a/mysql-test/r/group_by.result	2012-05-21 18:54:41 +0000
+++ b/mysql-test/r/group_by.result	2012-08-31 23:51:52 +0000
@@ -2149,3 +2149,48 @@
 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/order_by.result'
--- a/mysql-test/r/order_by.result	2012-02-15 17:08:08 +0000
+++ b/mysql-test/r/order_by.result	2012-08-31 23:51:52 +0000
@@ -1439,6 +1439,7 @@
 select * from t1 order by b;
 ERROR HY001: Out of sort memory, consider increasing server sort buffer size
 drop table t1;
+set session sort_buffer_size= 30000;
 #
 # Bug #39844: Query Crash Mysql Server 5.0.67
 #
@@ -1533,6 +1534,890 @@
 ppfcz1	DE	ppfcz1	14	9	59.5
 ppfcz1	DE	ppfcz1	14	10	61.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	2012-08-31 23:51:52 +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/subselect_innodb.result'
--- a/mysql-test/r/subselect_innodb.result	2012-06-06 19:26:40 +0000
+++ b/mysql-test/r/subselect_innodb.result	2012-08-31 23:51:52 +0000
@@ -248,6 +248,47 @@
 drop procedure p1;
 drop tables 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
+#
 # Bug#60085 crash in Item::save_in_field() with time data type
 #
 CREATE TABLE t1(a date, b int, unique(b), unique(a), key(b)) engine=innodb;

=== modified file 'mysql-test/r/subselect_mat_cost_bugs.result'
--- a/mysql-test/r/subselect_mat_cost_bugs.result	2012-06-20 11:01:28 +0000
+++ b/mysql-test/r/subselect_mat_cost_bugs.result	2012-08-31 23:51:52 +0000
@@ -148,7 +148,7 @@
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE noticed after reading const tables
 2	SUBQUERY	t1	system	NULL	NULL	NULL	NULL	1	
-3	SUBQUERY	internal_tmp_table	ALL	group_key	NULL	NULL	NULL	1	Using temporary; Using filesort
+3	SUBQUERY	internal_tmp_table	ALL	group_key	NULL	NULL	NULL	2	Using temporary; Using filesort
 drop table t1, t2, t3;
 #
 # LP BUG#715034 Item_sum_distinct::clear(): Assertion `tree != 0' failed

=== modified file 'mysql-test/t/filesort_debug.test'
--- a/mysql-test/t/filesort_debug.test	2012-04-10 06:28:13 +0000
+++ b/mysql-test/t/filesort_debug.test	2012-08-31 23:51:52 +0000
@@ -11,7 +11,7 @@
 CREATE TABLE t1(f0 int auto_increment primary key, f1 int);
 INSERT INTO t1(f1) VALUES (0),(1),(2),(3),(4),(5);
 
-SET session debug_dbug= '+d,make_sort_keys_alloc_fail';
+SET session debug_dbug= '+d,alloc_sort_buffer_fail';
 CALL mtr.add_suppression("Out of sort memory");
 --error ER_OUT_OF_SORTMEMORY
 SELECT * FROM t1 ORDER BY f1 ASC, f0;

=== modified file 'mysql-test/t/group_by.test'
--- a/mysql-test/t/group_by.test	2012-05-21 18:54:41 +0000
+++ b/mysql-test/t/group_by.test	2012-08-31 23:51:52 +0000
@@ -1493,3 +1493,52 @@
 
 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

=== modified file 'mysql-test/t/order_by.test'
--- a/mysql-test/t/order_by.test	2012-02-15 17:08:08 +0000
+++ b/mysql-test/t/order_by.test	2012-08-31 23:51:52 +0000
@@ -865,6 +865,7 @@
 --error ER_OUT_OF_SORTMEMORY
 select * from t1 order by b;
 drop table t1;
+set session sort_buffer_size= 30000;
 
 --echo #
 --echo # Bug #39844: Query Crash Mysql Server 5.0.67
@@ -1391,7 +1392,205 @@
 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
 #
 

=== 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	2012-08-31 23:51:52 +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	2012-06-04 15:26:11 +0000
+++ b/mysql-test/t/subselect_innodb.test	2012-08-31 23:51:52 +0000
@@ -244,6 +244,54 @@
 drop tables 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
+
+--echo #
 --echo # Bug#60085 crash in Item::save_in_field() with time data type
 --echo #
 

=== modified file 'mysys/mf_radix.c'
--- a/mysys/mf_radix.c	2007-05-10 09:59:39 +0000
+++ b/mysys/mf_radix.c	2012-08-31 23:51:52 +0000
@@ -25,6 +25,11 @@
 
 	/* Radixsort */
 
+my_bool radixsort_is_appliccable(uint n_items, size_t size_of_element)
+{
+  return size_of_element <= 20 && n_items >= 1000 && n_items < 100000;
+}
+
 void radixsort_for_str_ptr(uchar **base, uint number_of_elements, size_t size_of_element, uchar **buffer)
 {
   uchar **end,**ptr,**buffer_ptr;

=== modified file 'mysys/mf_sort.c'
--- a/mysys/mf_sort.c	2011-06-30 15:46:53 +0000
+++ b/mysys/mf_sort.c	2012-08-31 23:51:52 +0000
@@ -23,7 +23,7 @@
 #if INT_MAX > 65536L
   uchar **ptr=0;
 
-  if (size <= 20 && items >= 1000 && items < 100000 &&
+  if (radixsort_is_appliccable(items, size) &&
       (ptr= (uchar**) my_malloc(items*sizeof(char*),MYF(0))))
   {
     radixsort_for_str_ptr((uchar**) base,items,size,ptr);

=== modified file 'sql/CMakeLists.txt'
--- a/sql/CMakeLists.txt	2012-05-22 09:04:32 +0000
+++ b/sql/CMakeLists.txt	2012-08-31 23:51:52 +0000
@@ -39,6 +39,7 @@
 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
                signal_handler.cc
                handler.cc hash_filo.h sql_plugin_services.h

=== modified file 'sql/filesort.cc'
--- a/sql/filesort.cc	2012-05-21 13:30:25 +0000
+++ b/sql/filesort.cc	2012-08-31 23:51:52 +0000
@@ -34,6 +34,9 @@
 #include "sql_base.h"                           // update_virtual_fields
 #include "sql_test.h"                           // TEST_filesort
 #include "opt_range.h"                          // SQL_SELECT
+#include "bounded_queue.h"
+#include "filesort_utils.h"
+#include "sql_select.h"
 #include "log_slow.h"
 #include "debug_sync.h"
 
@@ -42,26 +45,72 @@
 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 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, uchar *sort_keys_buf,
-                             IO_CACHE *buffer_file, IO_CACHE *tempfile);
-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 bool save_index(SORTPARAM *param,uchar **sort_keys, uint count, 
-                       FILESORT_INFO *table_sort);
+static ha_rows find_all_keys(Sort_param *param,SQL_SELECT *select,
+                             Filesort_info *fs_info,
+                             IO_CACHE *buffer_file,
+                             IO_CACHE *tempfile,
+                             Bounded_queue<uchar, uchar> *pq,
+                             ha_rows *found_rows);
+static int write_keys(Sort_param *param, Filesort_info *fs_info,
+                      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 bool save_index(Sort_param *param, uint count,
+                       Filesort_info *table_sort);
+static void make_sortkey(Sort_param *param, uchar *to, uchar *ref_pos);
 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, uchar *buff_end);
+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
@@ -74,15 +123,17 @@
   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 or
+                              when rowids are required by executor)
+  @param[out] examined_rows  Store number of examined rows here
+  @param[out] found_rows     Store the number of found rows here
 
   @note
     If we sort by position (like if sort_positions is 1) filesort() will
@@ -92,30 +143,30 @@
     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 memory_available= thd->variables.sortbuff_size;
-  ulong min_sort_memory;
   uint maxbuffer;
   BUFFPEK *buffpek;
   ha_rows num_rows= HA_POS_ERROR;
-  uchar **sort_keys= 0;
   IO_CACHE tempfile, buffpek_pointers, *outfile; 
-  SORTPARAM param;
+  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;
+  Filesort_info table_sort= table->sort;
   TABLE_LIST *tab= table->pos_in_table_list;
   Item_subselect *subselect= tab ? tab->containing_subselect() : 0;
 
@@ -133,7 +184,6 @@
     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));
   table->sort.io_cache= NULL;
   
   outfile= table_sort.io_cache;
@@ -141,43 +191,21 @@
   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.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 param.spack_length.
-    */
-    param.addon_field= get_addon_fields(thd, table->field, 
-                                        param.sort_length,
-                                        &param.addon_length);
-  }
+
+  param.init_for_filesort(sortlength(thd, sortorder, s_length,
+                                     &multi_byte_charset),
+                          table,
+                          thd->variables.max_length_for_sort_data,
+                          max_rows, sort_positions);
 
   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))))
-      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 (param.addon_field &&
+      !(table_sort.addon_buf=
+        (uchar *) my_malloc(param.addon_length, MYF(MY_WME))))
+    goto err;
 
   if (select && select->quick)
     status_var_increment(thd->status_var.filesort_range_count);
@@ -192,20 +220,54 @@
       !(param.tmp_buffer= (char*) my_malloc(param.sort_length,MYF(MY_WME))))
     goto err;
 
-  min_sort_memory= max(MIN_SORT_MEMORY, param.sort_length * MERGEBUFF2);
-  if (!table_sort.sort_keys)
-  {
+  if (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.get_sort_keys()))
+    {
+      /*
+       If we fail to init pq, we have to give up:
+       out of memory means my_malloc() will call my_error().
+      */
+      DBUG_PRINT("info", ("failed to allocate PQ"));
+      table_sort.free_sort_buffer();
+      DBUG_ASSERT(thd->is_error());
+      goto err;
+    }
+    // For PQ queries (with limit) we initialize all pointers.
+    table_sort.init_record_pointers();
+  }
+  else
+  {
+    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*));
-      table_sort.keys= (uint) min(num_rows, keys);
-
-      DBUG_EXECUTE_IF("make_sort_keys_alloc_fail",
-                      DBUG_SET("+d,simulate_out_of_memory"););
-
-      if ((table_sort.sort_keys=
-           (uchar**) my_malloc(table_sort.keys*(param.rec_length+sizeof(char*)),
-                               MYF(0))))
+      param.max_keys_per_buffer= (uint) min(num_rows, keys);
+      if (table_sort.get_sort_keys())
+      {
+        // If we have already allocated a buffer, it better have same size!
+        if (!table_sort.check_sort_buffer_properties(param.max_keys_per_buffer,
+                                                     param.rec_length))
+        {
+          /*
+            table->sort will still have a pointer to the same buffer,
+            but that will be overwritten by the assignment below.
+          */
+          table_sort.free_sort_buffer();
+        }
+      }
+      table_sort.alloc_sort_buffer(param.max_keys_per_buffer, param.rec_length);
+      if (table_sort.get_sort_keys())
         break;
       ulong old_memory_available= memory_available;
       memory_available= memory_available/4*3;
@@ -213,40 +275,37 @@
           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_FATALERROR));
+      goto err;
+    }
   }
 
-  sort_keys= table_sort.sort_keys;
-  param.keys= table_sort.keys;
-  if (memory_available < min_sort_memory)
-  {
-    my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR + ME_FATALERROR));
-    goto err;
-  }
   if (open_cached_file(&buffpek_pointers,mysql_tmpdir,TEMP_PREFIX,
-		       DISK_BUFFER_SIZE, MYF(ME_ERROR | MY_WME)))
+		       DISK_BUFFER_SIZE, MYF(MY_WME)))
     goto err;
 
   param.sort_form= table;
   param.end=(param.local_sortorder=sortorder)+s_length;
-  num_rows= find_all_keys(&param,
-                          select,
-                          sort_keys,
-                          (uchar *)(sort_keys+param.keys),
+  num_rows= find_all_keys(&param, select,
+                          &table_sort,
                           &buffpek_pointers,
-                          &tempfile);
+                          &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));
 
   if (maxbuffer == 0)			// The whole set is in memory
   {
-    if (save_index(&param,sort_keys,(uint) num_rows, &table_sort))
+    if (save_index(&param, (uint) num_rows, &table_sort))
       goto err;
   }
   else
   {
-    thd->query_plan_flags|= QPLAN_FILESORT_DISK;
-
     /* filesort cannot handle zero-length records during merge. */
     DBUG_ASSERT(param.sort_length != 0);
 
@@ -265,7 +324,7 @@
 	/* Open cached file if it isn't open */
     if (! my_b_inited(outfile) &&
 	open_cached_file(outfile,mysql_tmpdir,TEMP_PREFIX,READ_RECORD_BUFFER,
-			  MYF(ME_ERROR | MY_WME)))
+			  MYF(MY_WME)))
       goto err;
     if (reinit_io_cache(outfile,WRITE_CACHE,0L,0,0))
       goto err;
@@ -274,18 +333,20 @@
       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,
+    if (merge_many_buff(&param,
+                        (uchar*) table_sort.get_sort_keys(),
+                        buffpek,&maxbuffer,
 			&tempfile))
       goto err;
     if (flush_io_cache(&tempfile) ||
 	reinit_io_cache(&tempfile,READ_CACHE,0L,0,0))
       goto err;
     if (merge_index(&param,
-                    (uchar*) sort_keys,
+                    (uchar*) table_sort.get_sort_keys(),
                     buffpek,
                     maxbuffer,
                     &tempfile,
@@ -300,12 +361,11 @@
   }
   error= 0;
 
- err:
+  err:
   my_free(param.tmp_buffer);
   if (!subselect || !subselect->is_uncacheable())
   {
-    my_free(sort_keys);
-    table_sort.sort_keys= 0;
+    table_sort.free_sort_buffer();
     my_free(buffpek);
     table_sort.buffpek= 0;
     table_sort.buffpek_len= 0;
@@ -336,7 +396,7 @@
                     thd->killed == ABORT_QUERY ? "" : thd->stmt_da->message());
 
     if (global_system_variables.log_warnings > 1)
-    {
+    { 
       sql_print_warning("%s, host: %s, user: %s, thread: %lu, query: %-.4096s",
                         ER_THD(thd, ER_FILSORT_ABORT),
                         thd->security_ctx->host_or_ip,
@@ -352,8 +412,13 @@
 #ifdef SKIP_DBUG_IN_FILESORT
   DBUG_POP();			/* Ok to DBUG */
 #endif
-  memcpy(&table->sort, &table_sort, sizeof(FILESORT_INFO));
-  DBUG_PRINT("exit",("num_rows: %ld", (long) num_rows));
+
+  // Assign the copy back!
+  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 */
@@ -361,13 +426,13 @@
 
 void filesort_free_buffers(TABLE *table, bool full)
 {
+  DBUG_ENTER("filesort_free_buffers");
   my_free(table->sort.record_pointers);
   table->sort.record_pointers= NULL;
 
   if (full)
   {
-    my_free(table->sort.sort_keys);
-    table->sort.sort_keys= NULL;
+    table->sort.free_sort_buffer();
     my_free(table->sort.buffpek);
     table->sort.buffpek= NULL;
     table->sort.buffpek_len= 0;
@@ -377,6 +442,7 @@
   my_free(table->sort.addon_field);
   table->sort.addon_buf= NULL;
   table->sort.addon_field= NULL;
+  DBUG_VOID_RETURN;
 }
 
 
@@ -455,8 +521,10 @@
 }
 #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
@@ -465,19 +533,28 @@
   @param buffpek_pointers  File to write BUFFPEKs describing sorted segments
                            in tempfile.
   @param tempfile          File to write sorted sequences of sortkeys to.
+  @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;
@@ -491,10 +568,12 @@
     HA_POS_ERROR on error.
 */
 
-static ha_rows find_all_keys(SORTPARAM *param, SQL_SELECT *select,
-			     uchar **sort_keys, uchar *sort_keys_buf,
+static ha_rows find_all_keys(Sort_param *param, SQL_SELECT *select,
+                             Filesort_info *fs_info,
 			     IO_CACHE *buffpek_pointers,
-			     IO_CACHE *tempfile)
+                             IO_CACHE *tempfile,
+                             Bounded_queue<uchar, uchar> *pq,
+                             ha_rows *found_rows)
 {
   int error,flag,quick_select;
   uint idx,indexpos,ref_length;
@@ -505,7 +584,7 @@
   volatile killed_state *killed= &thd->killed;
   handler *file;
   MY_BITMAP *save_read_set, *save_write_set, *save_vcol_set;
-  uchar *next_sort_key= sort_keys_buf;
+  
   DBUG_ENTER("find_all_keys");
   DBUG_PRINT("info",("using: %s",
                      (select ? select->quick ? "ranges" : "where":
@@ -519,6 +598,7 @@
   ref_pos= ref_buff;
   quick_select=select && select->quick;
   record=0;
+  *found_rows= 0;
   flag= ((file->ha_table_flags() & HA_REC_NOT_IN_SEQ) || quick_select);
   if (flag)
     ref_pos= &file->ref[0];
@@ -532,7 +612,6 @@
 		    current_thd->variables.read_buff_size);
   }
 
-
   /* Remember original bitmaps */
   save_read_set=  sort_form->read_set;
   save_write_set= sort_form->write_set;
@@ -631,18 +710,23 @@
 
     if (write_record)
     {
-      if (idx == param->keys)
-      {
-	if (write_keys(param, sort_keys,
-                       idx, buffpek_pointers, tempfile))
-	  DBUG_RETURN(HA_POS_ERROR);
-	idx= 0;
-        next_sort_key= sort_keys_buf;
-	indexpos++;
-      }
-      sort_keys[idx++]= next_sort_key;
-      make_sortkey(param, next_sort_key, ref_pos);
-      next_sort_key+= param->rec_length;
+       ++(*found_rows);
+      if (pq)
+      {
+        pq->push(ref_pos);
+        idx= pq->num_elements();
+      }
+      else
+      {
+        if (idx == param->max_keys_per_buffer)
+        {
+          if (write_keys(param, fs_info, idx, buffpek_pointers, tempfile))
+             DBUG_RETURN(HA_POS_ERROR);
+	  idx= 0;
+	  indexpos++;
+        }
+        make_sortkey(param, fs_info->get_record_buffer(idx++), ref_pos);
+      }
     }
     else
       file->unlock_row();
@@ -671,12 +755,12 @@
     DBUG_RETURN(HA_POS_ERROR);			/* purecov: inspected */
   }
   if (indexpos && idx &&
-      write_keys(param, sort_keys,
-                 idx, buffpek_pointers, tempfile))
+      write_keys(param, fs_info, idx, buffpek_pointers, tempfile))
     DBUG_RETURN(HA_POS_ERROR);			/* purecov: inspected */
   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 */
 
@@ -704,21 +788,19 @@
 */
 
 static int
-write_keys(SORTPARAM *param, register uchar **sort_keys, uint count,
+write_keys(Sort_param *param,  Filesort_info *fs_info, uint count,
            IO_CACHE *buffpek_pointers, IO_CACHE *tempfile)
 {
-  size_t sort_length, rec_length;
+  size_t rec_length;
   uchar **end;
   BUFFPEK buffpek;
   DBUG_ENTER("write_keys");
 
-  sort_length= param->sort_length;
   rec_length= param->rec_length;
-#ifdef MC68000
-  quicksort(sort_keys,count,sort_length);
-#else
-  my_string_ptr_sort((uchar*) sort_keys, (uint) count, sort_length);
-#endif
+  uchar **sort_keys= fs_info->get_sort_keys();
+
+  fs_info->sort_buffer(param, count);
+
   if (!my_b_inited(tempfile) &&
       open_cached_file(tempfile, mysql_tmpdir, TEMP_PREFIX, DISK_BUFFER_SIZE,
                        MYF(MY_WME)))
@@ -767,8 +849,8 @@
 
 /** 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;
@@ -786,9 +868,9 @@
 	if (field->is_null())
 	{
 	  if (sort_field->reverse)
-	    bfill(to,sort_field->length+1,(char) 255);
+	    memset(to, 255, sort_field->length+1);
 	  else
-	    bzero((char*) to,sort_field->length+1);
+	    memset(to, 0, sort_field->length+1);
 	  to+= sort_field->length+1;
 	  continue;
 	}
@@ -804,7 +886,7 @@
       switch (sort_field->result_type) {
       case STRING_RESULT:
       {
-        CHARSET_INFO *cs=item->collation.collation;
+        const CHARSET_INFO *cs=item->collation.collation;
         char fill_char= ((cs->state & MY_CS_BINSORT) ? (char) 0 : ' ');
         int diff;
         uint sort_field_length;
@@ -817,7 +899,7 @@
         if (!res)
         {
           if (maybe_null)
-            bzero((char*) to-1,sort_field->length+1);
+            memset(to-1, 0, sort_field->length+1);
           else
           {
             /* purecov: begin deadcode */
@@ -829,7 +911,7 @@
             DBUG_ASSERT(0);
             DBUG_PRINT("warning",
                        ("Got null on something that shouldn't be null"));
-            bzero((char*) to,sort_field->length);	// Avoid crash
+            memset(to, 0, sort_field->length);	// Avoid crash
             /* purecov: end */
           }
           break;
@@ -885,12 +967,19 @@
           }
           if (maybe_null)
           {
-            if (item->null_value)
-            {
-              bzero((char*) to++, sort_field->length+1);
-              break;
-            }
 	    *to++=1;				/* purecov: inspected */
+            if (item->null_value)
+            {
+              if (maybe_null)
+                memset(to-1, 0, sort_field->length+1);
+              else
+              {
+                DBUG_PRINT("warning",
+                           ("Got null on something that shouldn't be null"));
+                memset(to, 0, sort_field->length);
+              }
+              break;
+            }
           }
 	  to[7]= (uchar) value;
 	  to[6]= (uchar) (value >> 8);
@@ -912,7 +1001,8 @@
           {
             if (item->null_value)
             { 
-              bzero((char*) to++, sort_field->length+1);
+              memset(to, 0, sort_field->length+1);
+              to++;
               break;
             }
             *to++=1;
@@ -929,7 +1019,7 @@
           {
             if (item->null_value)
             {
-              bzero((char*) to,sort_field->length+1);
+              memset(to, 0, sort_field->length+1);
               to++;
               break;
             }
@@ -971,7 +1061,7 @@
     SORT_ADDON_FIELD *addonf= param->addon_field;
     uchar *nulls= to;
     DBUG_ASSERT(addonf != 0);
-    bzero((char *) nulls, addonf->offset);
+    memset(nulls, 0, addonf->offset);
     to+= addonf->offset;
     for ( ; (field= addonf->field) ; addonf++)
     {
@@ -1010,7 +1100,7 @@
   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;
@@ -1055,21 +1145,19 @@
 }
 
 
-static bool save_index(SORTPARAM *param, uchar **sort_keys, uint count, 
-                       FILESORT_INFO *table_sort)
+static bool save_index(Sort_param *param, 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);
+  table_sort->sort_buffer(param, count);
   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 */
+  uchar **sort_keys= table_sort->get_sort_keys();
   for (uchar **end= sort_keys+count ; sort_keys != end ; sort_keys++)
   {
     memcpy(to, *sort_keys+offset, res_length);
@@ -1079,10 +1167,150 @@
 }
 
 
+/**
+  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 )
+    {
+      filesort_info->alloc_sort_buffer(param->max_keys_per_buffer,
+                                       param->rec_length);
+      DBUG_RETURN(filesort_info->get_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)
+  {
+    filesort_info->alloc_sort_buffer(param->max_keys_per_buffer,
+                                     param->rec_length);
+    DBUG_RETURN(filesort_info->get_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);
+
+      filesort_info->alloc_sort_buffer(param->max_keys_per_buffer,
+                                       param->sort_length + param->ref_length);
+      if (filesort_info->get_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;
@@ -1213,7 +1441,7 @@
     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)
@@ -1255,7 +1483,7 @@
            (flag && min_dupl_count ? sizeof(dupl_count) : 0)-res_length);
   uint wr_len= flag ? res_length : rec_length;
   uint wr_offset= flag ? offset : 0;
-  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= sort_buffer;
   org_max_rows=max_rows= param->max_rows;
@@ -1396,7 +1624,7 @@
   }
   buffpek= (BUFFPEK*) queue_top(&queue);
   buffpek->base= (uchar*) 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
@@ -1486,9 +1714,9 @@
 
 	/* Do a merge to output-file (save only positions) */
 
-int merge_index(SORTPARAM *param, uchar *sort_buffer,
-		       BUFFPEK *buffpek, uint maxbuffer,
-		       IO_CACHE *tempfile, IO_CACHE *outfile)
+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,
@@ -1534,7 +1762,7 @@
            bool *multi_byte_charset)
 {
   reg2 uint length;
-  CHARSET_INFO *cs;
+  const CHARSET_INFO *cs;
   *multi_byte_charset= 0;
 
   length=0;
@@ -1635,7 +1863,8 @@
 */
 
 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;
@@ -1672,7 +1901,7 @@
     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;
@@ -1755,7 +1984,7 @@
   if (nr == 0.0)
   {						/* Change to zero string */
     tmp[0]=(uchar) 128;
-    bzero((char*) tmp+1,sizeof(nr)-1);
+    memset(tmp+1, 0, sizeof(nr)-1);
   }
   else
   {

=== modified file 'sql/filesort.h'
--- a/sql/filesort.h	2011-11-03 18:17:05 +0000
+++ b/sql/filesort.h	2012-08-31 23:51:52 +0000
@@ -29,10 +29,8 @@
 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);
-double get_merge_many_buffs_cost(uint *buffer, uint last_n_elems,
-                                 int elem_size);
 void change_double_for_sort(double nr,uchar *to);
 
 #endif /* FILESORT_INCLUDED */

=== modified file 'sql/sql_array.h'
--- a/sql/sql_array.h	2011-11-03 18:17:05 +0000
+++ b/sql/sql_array.h	2012-08-31 23:51:52 +0000
@@ -19,6 +19,77 @@
 
 #include <my_sys.h>
 
+/**
+   A wrapper class which provides array bounds checking.
+   We do *not* own the array, we simply have a pointer to the first element,
+   and a length.
+
+   @remark
+   We want the compiler-generated versions of:
+   - the copy CTOR (memberwise initialization)
+   - the assignment operator (memberwise assignment)
+
+   @param Element_type The type of the elements of the container.
+ */
+template <typename Element_type> class Bounds_checked_array
+{
+public:
+  Bounds_checked_array() : m_array(NULL), m_size(0) {}
+
+  Bounds_checked_array(Element_type *el, size_t size)
+    : m_array(el), m_size(size)
+  {}
+
+  void reset() { m_array= NULL; m_size= 0; }
+ 
+  void reset(Element_type *array, size_t size)
+  {
+    m_array= array;
+    m_size= size;
+  }
+
+  /**
+    Set a new bound on the array. Does not resize the underlying
+    array, so the new size must be smaller than or equal to the
+    current size.
+   */
+  void resize(size_t new_size)
+  {
+    DBUG_ASSERT(new_size <= m_size);
+    m_size= new_size;
+  }
+
+  Element_type &operator[](size_t n)
+  {
+    DBUG_ASSERT(n < m_size);
+    return m_array[n];
+  }
+
+  const Element_type &operator[](size_t n) const
+  {
+    DBUG_ASSERT(n < m_size);
+    return m_array[n];
+  }
+
+  size_t element_size() const { return sizeof(Element_type); }
+  size_t size() const         { return m_size; }
+
+  bool is_null() const { return m_array == NULL; }
+
+  void pop_front()
+  {
+    DBUG_ASSERT(m_size > 0);
+    m_array+= 1;
+    m_size-= 1;
+  }
+
+  Element_type *array() const { return m_array; }
+
+private:
+  Element_type *m_array;
+  size_t        m_size;
+};
+
 /*
   A typesafe wrapper around DYNAMIC_ARRAY
 */

=== modified file 'sql/sql_delete.cc'
--- a/sql/sql_delete.cc	2012-05-17 10:46:05 +0000
+++ b/sql/sql_delete.cc	2012-08-31 23:51:52 +0000
@@ -244,6 +244,7 @@
     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);
@@ -264,9 +265,10 @@
                                                    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	2012-07-06 16:04:52 +0000
+++ b/sql/sql_select.cc	2012-08-31 23:51:52 +0000
@@ -1435,9 +1435,10 @@
         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
@@ -1447,7 +1448,13 @@
           '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).
@@ -1853,6 +1860,7 @@
 
       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))
@@ -2177,6 +2185,8 @@
   int      tmp_error;
   DBUG_ENTER("JOIN::exec");
 
+  const bool has_group_by= this->group;
+
   thd_proc_info(thd, "executing");
   error= 0;
   if (procedure)
@@ -2515,11 +2525,12 @@
       }
       if (curr_join->group_list)
       {
+	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 (curr_join->join_tab == join_tab && save_join_tab())
-	{
-	  DBUG_VOID_RETURN;
-	}
 	if (create_sort_index(thd, curr_join, curr_join->group_list,
 			      HA_POS_ERROR, HA_POS_ERROR, FALSE) ||
 	    make_group_fields(this, curr_join))
@@ -2785,13 +2796,39 @@
 	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),
-                            curr_join->group_list ? TRUE : FALSE))
+      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;"
+        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->table_count > 1)
+        ? curr_join->select_limit : unit->select_limit_cnt;
+      const ha_rows select_limit_arg=
+        select_options & OPTION_FOUND_ROWS
+        ? HA_POS_ERROR : unit->select_limit_cnt;
+
+      DBUG_PRINT("info", ("has_group_by %d "
+                          "curr_join->table_count %d "
+                          "curr_join->m_select_limit %d "
+                          "unit->select_limit_cnt %d",
+                          has_group_by,
+                          curr_join->table_count,
+                          (int) curr_join->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;
       if (curr_join->const_tables != curr_join->table_count &&
@@ -2823,6 +2860,14 @@
                                    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->table_count > 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;
@@ -17163,7 +17208,25 @@
       if ((error= join->result->send_data(*join->fields)))
         DBUG_RETURN(error < 0 ? NESTED_LOOP_OK : NESTED_LOOP_ERROR);
     }
-    if (++join->send_records >= join->unit->select_limit_cnt &&
+
+    ++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)
@@ -18848,6 +18911,8 @@
 {
   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;
@@ -18925,10 +18990,11 @@
     goto err;
   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)
   {
     /*
@@ -18957,7 +19023,7 @@
   tab->read_first_record= join_init_read_record;
   tab->join->examined_rows+=examined_rows;
   table->disable_keyread(); // 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);
 }
@@ -19288,7 +19354,7 @@
   pos= sort= sortorder;
 
   if (!pos)
-    return 0;
+    DBUG_RETURN(0);
 
   for (;order;order=order->next,pos++)
   {
@@ -19305,6 +19371,7 @@
     else
       pos->item= *order->item;
     pos->reverse=! order->asc;
+    DBUG_ASSERT(pos->field != NULL || pos->item != NULL);
   }
   *length=count;
   DBUG_RETURN(sort);

=== modified file 'sql/sql_sort.h'
--- a/sql/sql_sort.h	2011-11-03 18:17:05 +0000
+++ b/sql/sql_sort.h	2012-08-31 23:51:52 +0000
@@ -16,6 +16,7 @@
    along with this program; if not, write to the Free Software
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  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 @@
 class Field;
 struct TABLE;
 
-
 /* Defines used by filesort and uniques */
 
 #define MERGEBUFF		7
@@ -65,41 +65,51 @@
   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 */
+
+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.
   uint min_dupl_count;
-  ha_rows max_rows,examined_rows;
-  TABLE *sort_form;			/* For quicker make_sortkey */
+  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;
-
-
-int merge_many_buff(SORTPARAM *param, uchar *sort_buffer,
+
+  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(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_index(SORTPARAM *param, uchar *sort_buffer,
+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);
+int merge_index(Sort_param *param, uchar *sort_buffer,
 		BUFFPEK *buffpek, uint maxbuffer,
 		IO_CACHE *tempfile, IO_CACHE *outfile);
-
 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	2012-06-16 07:03:07 +0000
+++ b/sql/sql_table.cc	2012-08-31 23:51:52 +0000
@@ -7201,6 +7201,7 @@
   List<Item>   fields;
   List<Item>   all_fields;
   ha_rows examined_rows;
+  ha_rows found_rows;
   bool auto_increment_field_copied= 0;
   ulonglong save_sql_mode= thd->variables.sql_mode;
   ulonglong prev_insert_id, time_to_report_progress;
@@ -7284,8 +7285,9 @@
                       &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	2012-05-17 10:46:05 +0000
+++ b/sql/sql_update.cc	2012-08-31 23:51:52 +0000
@@ -498,13 +498,15 @@
       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/table.h'
--- a/sql/table.h	2012-06-09 05:15:49 +0000
+++ b/sql/table.h	2012-08-31 23:51:52 +0000
@@ -29,6 +29,7 @@
 #include "handler.h"                /* row_type, ha_choice, handler */
 #include "mysql_com.h"              /* enum_field_types */
 #include "thr_lock.h"                  /* thr_lock_type */
+#include "filesort_utils.h"
 
 /* Structs that defines the TABLE */
 
@@ -299,11 +300,14 @@
 };
 enum release_type { RELEASE_NORMAL, RELEASE_WAIT_FOR_DROP };
 
-typedef struct st_filesort_info
+
+class Filesort_info
 {
+  /// Buffer for sorting keys.
+  Filesort_buffer filesort_buffer;
+
+public:
   IO_CACHE *io_cache;           /* If sorted through filesort */
-  uchar     **sort_keys;        /* Buffer for sorting keys */
-  uint      keys;               /* Number of key pointers in buffer */
   uchar     *buffpek;           /* Buffer for buffpek structures */
   uint      buffpek_len;        /* Max number of buffpeks in the buffer */
   uchar     *addon_buf;         /* Pointer to a buffer if sorted with fields */
@@ -312,7 +316,38 @@
   void    (*unpack)(struct st_sort_addon_field *, uchar *, uchar *); /* To unpack back */
   uchar     *record_pointers;    /* If sorted in memory */
   ha_rows   found_records;      /* How many records in sort */
-} FILESORT_INFO;
+
+  /** Sort filesort_buffer */
+  void sort_buffer(Sort_param *param, uint count)
+  { filesort_buffer.sort_buffer(param, count); }
+
+  /**
+     Accessors for Filesort_buffer (which @c).
+  */
+  uchar *get_record_buffer(uint idx)
+  { return filesort_buffer.get_record_buffer(idx); }
+
+  uchar **get_sort_keys()
+  { return filesort_buffer.get_sort_keys(); }
+
+  uchar **alloc_sort_buffer(uint num_records, uint record_length)
+  { return filesort_buffer.alloc_sort_buffer(num_records, record_length); }
+
+  bool check_sort_buffer_properties(uint num_records, uint record_length)
+  {
+    return filesort_buffer.check_sort_buffer_properties(num_records,
+                                                        record_length);
+  }
+
+  void free_sort_buffer()
+  { filesort_buffer.free_sort_buffer(); }
+
+  void init_record_pointers()
+  { filesort_buffer.init_record_pointers(); }
+
+  size_t sort_buffer_size() const
+  { return filesort_buffer.sort_buffer_size(); }
+};
 
 
 /*
@@ -1136,7 +1171,7 @@
   REGINFO reginfo;			/* field connections */
   MEM_ROOT mem_root;
   GRANT_INFO grant;
-  FILESORT_INFO sort;
+  Filesort_info sort;
   /*
     The arena which the items for expressions from the table definition
     are associated with.  

=== modified file 'sql/uniques.cc'
--- a/sql/uniques.cc	2012-01-13 14:50:02 +0000
+++ b/sql/uniques.cc	2012-08-31 23:51:52 +0000
@@ -620,7 +620,6 @@
 
 bool Unique::get(TABLE *table)
 {
-  SORTPARAM sort_param;
   table->sort.found_records=elements+tree.elements_in_tree;
   if (my_b_tell(&file) == 0)
   {
@@ -660,6 +659,7 @@
     return 1;
   reinit_io_cache(outfile,WRITE_CACHE,0L,0,0);
 
+  Sort_param sort_param; 
   bzero((char*) &sort_param,sizeof(sort_param));
   sort_param.max_rows= elements;
   sort_param.sort_form=table;
@@ -667,14 +667,15 @@
    full_size;
   sort_param.min_dupl_count= min_dupl_count;
   sort_param.res_length= 0;
-  sort_param.keys= (uint) (max_in_memory_size / sort_param.sort_length);
+  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) *
+  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.unique_buff= sort_buffer+(sort_param.max_keys_per_buffer *
 				       sort_param.sort_length);
 
   sort_param.compare= (qsort2_cmp) buffpek_compare;



More information about the commits mailing list