#At file:///export/home/didrik/repo/next-mr-opt-team-wl1393-merge/ based on revid:tor.didriksen@stripped
3223 Tor Didriksen 2010-09-07
WL#1393 Optimizing filesort with small limit
note: there are some extra DBUG_PRINTs here that should go away in the final version ....
When limit*(sort_key_length+extra) is smaller than sort_buff_size we can use
the following algoritm to speed up the sort:
- Create a queue to hold 'limit' keys.
- Scan through the table and store the first (last if DESC) keys in the queue
- Return values from queue
@ libmysqld/CMakeLists.txt
Add Bounded_queue
@ libmysqld/Makefile.am
Add Bounded_queue
@ mysql-test/include/order_by.inc
Add new tests.
@ mysql-test/include/select.inc
Fix typo in bug number.
@ mysql-test/include/subquery.inc
Add explain to filesort subquery.
@ mysql-test/r/join_cache_jcl1.result
New explain result (key is not used when scanning tmp table)
@ mysql-test/r/myisam_mrr_none.result
New explain result when using PQ.
@ mysql-test/r/order_by_none.result
New explain results when using PQ.
Added new tests.
@ mysql-test/r/order_by_sortkey.result
New test.
@ mysql-test/r/select_none.result
New explain results when using PQ.
Fix typo in bug number.
@ mysql-test/r/subquery_none.result
New explain results when using PQ.
@ mysql-test/r/view.result
New explain result when using PQ.
@ mysql-test/t/order_by_sortkey.test
New test.
@ mysys/CMakeLists.txt
Compile standalone queues test executable.
@ mysys/queues.c
Fix un-maintained code: s/bool/my_bool/
@ sql/CMakeLists.txt
Add Bounded_queue to gunit tests.
@ sql/Makefile.am
Add Bounded_queue
@ sql/bounded_queue.cc
This is a wrapper on top of QUEUE and the queue_xxx() functions.
@ sql/bounded_queue.h
This is a wrapper on top of QUEUE and the queue_xxx() functions.
@ sql/filesort.cc
Add support for Priority Queue sort for queries with a LIMIT.
Remove dead code.
@ sql/filesort.h
New argument to filesort()
New function explain_filesort().
@ sql/sql_const.h
Use double, rather than int, literals (avoids lots of casting).
@ sql/sql_delete.cc
New argument to filesort()
@ sql/sql_select.cc
Handle new filesort() and explain_filesort() using priority queue:
- in JOIN::optimize(), don't do early return if we have SELECT_DESCRIBE,
since we need the tmp table to do proper explain.
- Add some more DBUG_PRINT statements before calls to create_sort_index()
- create_sort_index() can use the new PQ algorithm if (!group && tables==1)
- use information from filesort() if we have OPTION_FOUND_ROWS
- cleanup initialization of KEYUSE instance (debug and valgrind showed uninitialized data)
- in end_send(): stop if we are about to read more rows than allocated by the PQ
- pass OPTION_FOUND_ROWS on to filesort() for single-table queries.
- use explain_filesort()
@ sql/sql_sort.h
Rename st_sort_param/SORTPARAM to Sort_param.
Add constructor.
Add init() function.
@ sql/sql_table.cc
New argument to filesort()
@ sql/sql_update.cc
New argument to filesort()
@ sql/uniques.cc
Rename SORTPARAM to Sort_param.
@ unittest/gunit/CMakeLists.txt
Add gunit test for Bounded_queue
@ unittest/gunit/bounded_queue-t.cc
Add new unit test for Bounded_queue and merge-cost estimation.
added:
mysql-test/r/order_by_sortkey.result
mysql-test/t/order_by_sortkey.test
sql/bounded_queue.cc
sql/bounded_queue.h
unittest/gunit/bounded_queue-t.cc
modified:
libmysqld/CMakeLists.txt
libmysqld/Makefile.am
mysql-test/include/order_by.inc
mysql-test/include/select.inc
mysql-test/include/subquery.inc
mysql-test/r/join_cache_jcl1.result
mysql-test/r/myisam_mrr_none.result
mysql-test/r/order_by_none.result
mysql-test/r/select_none.result
mysql-test/r/subquery_none.result
mysql-test/r/view.result
mysys/CMakeLists.txt
mysys/queues.c
sql/CMakeLists.txt
sql/Makefile.am
sql/filesort.cc
sql/filesort.h
sql/sql_const.h
sql/sql_delete.cc
sql/sql_select.cc
sql/sql_sort.h
sql/sql_table.cc
sql/sql_update.cc
sql/uniques.cc
unittest/gunit/CMakeLists.txt
=== modified file 'libmysqld/CMakeLists.txt'
--- a/libmysqld/CMakeLists.txt 2010-08-20 09:15:16 +0000
+++ b/libmysqld/CMakeLists.txt 2010-09-07 05:45:36 +0000
@@ -44,6 +44,7 @@ SET(SQL_EMBEDDED_SOURCES emb_qcache.cc l
../sql-common/my_user.c ../sql-common/pack.c
../sql/password.c ../sql/discover.cc ../sql/derror.cc
../sql/field.cc ../sql/field_conv.cc
+ ../sql/bounded_queue.cc
../sql/filesort.cc ../sql/gstream.cc
../sql/handler.cc ../sql/hash_filo.cc ../sql/hostname.cc
../sql/init.cc ../sql/item_buff.cc ../sql/item_cmpfunc.cc
=== modified file 'libmysqld/Makefile.am'
--- a/libmysqld/Makefile.am 2010-09-01 12:52:09 +0000
+++ b/libmysqld/Makefile.am 2010-09-07 05:45:36 +0000
@@ -44,6 +44,7 @@ libmysqlsources = errmsg.c get_password.
noinst_HEADERS = embedded_priv.h emb_qcache.h
sqlsources = derror.cc field.cc field_conv.cc strfunc.cc filesort.cc \
+ bounded_queue.cc \
ha_ndbcluster.cc ha_ndbcluster_cond.cc \
ha_ndbcluster_binlog.cc ha_partition.cc \
handler.cc sql_handler.cc \
=== modified file 'mysql-test/include/order_by.inc'
--- a/mysql-test/include/order_by.inc 2010-06-25 09:34:37 +0000
+++ b/mysql-test/include/order_by.inc 2010-09-07 05:45:36 +0000
@@ -1364,6 +1364,249 @@ ORDER BY t2.c LIMIT 1;
DROP TABLE t1,t2,t3;
+--echo #
+--echo # WL#1393 - Optimizing filesort with small limit
+--echo #
+
+create table t1(f0 int auto_increment primary key, f1 int, f2 varchar(200));
+insert into t1(f1, f2) values
+(0,"0"),(1,"1"),(2,"2"),(3,"3"),(4,"4"),(5,"5"),
+(6,"6"),(7,"7"),(8,"8"),(9,"9"),(10,"10"),
+(11,"11"),(12,"12"),(13,"13"),(14,"14"),(15,"15"),
+(16,"16"),(17,"17"),(18,"18"),(19,"19"),(20,"20"),
+(21,"21"),(22,"22"),(23,"23"),(24,"24"),(25,"25"),
+(26,"26"),(27,"27"),(28,"28"),(29,"29"),(30,"30"),
+(31,"31"),(32,"32"),(33,"33"),(34,"34"),(35,"35"),
+(36,"36"),(37,"37"),(38,"38"),(39,"39"),(40,"40"),
+(41,"41"),(42,"42"),(43,"43"),(44,"44"),(45,"45"),
+(46,"46"),(47,"47"),(48,"48"),(49,"49"),(50,"50"),
+(51,"51"),(52,"52"),(53,"53"),(54,"54"),(55,"55"),
+(56,"56"),(57,"57"),(58,"58"),(59,"59"),(60,"60"),
+(61,"61"),(62,"62"),(63,"63"),(64,"64"),(65,"65"),
+(66,"66"),(67,"67"),(68,"68"),(69,"69"),(70,"70"),
+(71,"71"),(72,"72"),(73,"73"),(74,"74"),(75,"75"),
+(76,"76"),(77,"77"),(78,"78"),(79,"79"),(80,"80"),
+(81,"81"),(82,"82"),(83,"83"),(84,"84"),(85,"85"),
+(86,"86"),(87,"87"),(88,"88"),(89,"89"),(90,"90"),
+(91,"91"),(92,"92"),(93,"93"),(94,"94"),(95,"95"),
+(96,"96"),(97,"97"),(98,"98"),(99,"99");
+
+################
+## Test sort when source data fits to memory
+
+# Select all rows, do not use PQ.
+let qq= select * from t1 order by f1 asc, f0 limit 100;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 order by f1 asc, f0 limit 30;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 order by f1 asc, f0 limit 0;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 order by f2 desc, f0 limit 30;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 order by f2 desc, f0 limit 0;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1>10 order by f2, f0 limit 20;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1>10 order by f2, f0 limit 0;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1>10 order by f2, f0 limit 10 offset 10;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1>10 order by f2, f0 limit 0 offset 10;
+eval explain $qq;
+eval $qq;
+
+################
+## Test sort when source data does not fit to memory
+set sort_buffer_size= 32768;
+create temporary table tmp (f1 int, f2 varchar(20));
+insert into tmp select f1, f2 from t1;
+insert into t1(f1, f2) select * from tmp;
+insert into tmp select f1, f2 from t1;
+insert into t1(f1, f2) select * from tmp;
+
+let qq= select * from t1 order by f1 asc, f0 limit 30;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 order by f1 asc, f0 limit 0;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 order by f2 desc, f0 limit 30;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 order by f2 desc, f0 limit 0;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1>10 order by f2, f0 limit 20;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1>10 order by f2, f0 limit 0;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1>10 order by f2, f0 limit 10 offset 10;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1>10 order by f2, f0 limit 0 offset 10;
+eval explain $qq;
+eval $qq;
+
+################
+## Test with SQL_CALC_FOUND_ROWS
+let qq= select SQL_CALC_FOUND_ROWS * from t1
+order by f1, f0 limit 30;
+eval explain $qq;
+eval $qq;
+select FOUND_ROWS();
+
+let qq= select SQL_CALC_FOUND_ROWS * from t1
+order by f1, f0 limit 0;
+eval explain $qq;
+eval $qq;
+select FOUND_ROWS();
+
+let qq= select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 20;
+eval explain $qq;
+eval $qq;
+select FOUND_ROWS();
+
+let qq= select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 0;
+eval explain $qq;
+eval $qq;
+select FOUND_ROWS();
+
+let qq= select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 10 offset 10;
+eval explain $qq;
+eval $qq;
+select FOUND_ROWS();
+
+let qq= select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 0 offset 10;
+eval explain $qq;
+eval $qq;
+select FOUND_ROWS();
+
+################
+## Test sorting with join
+## Explain thinks we cannot use PQ for these,
+## but during execution we will make_simple_join, and use PQ anyways.
+set sort_buffer_size= 327680;
+
+let qq= select * from t1 join tmp on t1.f2=tmp.f2
+order by tmp.f1, f0 limit 30;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 join tmp on t1.f2=tmp.f2
+order by tmp.f1, f0 limit 30 offset 30;
+eval explain $qq;
+eval $qq;
+
+let qq=select SQL_CALC_FOUND_ROWS * from t1 join tmp on t1.f2=tmp.f2
+order by tmp.f1, f0 limit 30 offset 30;
+eval explain $qq;
+eval $qq;
+select FOUND_ROWS();
+
+let qq= select SQL_CALC_FOUND_ROWS * from t1 join tmp on t1.f2=tmp.f2
+where t1.f2>20
+order by tmp.f1, f0 limit 30 offset 30;
+eval explain $qq;
+eval $qq;
+select FOUND_ROWS();
+
+################
+## Test views
+create view v1 as select * from t1 order by f1, f0 limit 30;
+let qq= select * from v1;
+eval explain $qq;
+eval $qq;
+drop view v1;
+
+create view v1 as select * from t1 order by f1, f0 limit 100;
+let qq= select * from v1 order by f2, f0 limit 30;
+eval explain $qq;
+eval $qq;
+
+create view v2 as select * from t1 order by f2, f0 limit 100;
+let qq= select * from v1 join v2 on v1.f1=v2.f1 order by v1.f2,v1.f0,v2.f0
+limit 30;
+eval explain $qq;
+eval $qq;
+
+################
+## Test group & having
+let qq= select floor(f1/10) f3, count(f2) from t1
+group by 1 order by 2,1 limit 5;
+eval explain $qq;
+eval $qq;
+
+let qq= select floor(f1/10) f3, count(f2) from t1
+group by 1 order by 2,1 limit 0;
+eval explain $qq;
+eval $qq;
+
+################
+## Test SP
+delimiter |;
+create procedure wl1393_sp_test()
+begin
+select * from t1 where f1>10 order by f2, f0 limit 30;
+select * from t1 where f1>10 order by f2, f0 limit 15 offset 15;
+select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 15 offset 15;
+select FOUND_ROWS();
+select * from v1 order by f2, f0 limit 30;
+end|
+call wl1393_sp_test()|
+drop procedure wl1393_sp_test|
+delimiter ;|
+
+################
+## Test with subqueries
+let qq= select d1.* from t1
+left join (select * from t1 limit 30) d1 on t1.f1=d1.f1
+order by d1.f2 desc limit 30;
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1 = (select f1 from t1 order by 1 limit 1);
+eval explain $qq;
+eval $qq;
+
+let qq= select * from t1 where f1 = (select f1 from t1 order by 1 limit 2);
+eval explain $qq;
+--error ER_SUBQUERY_NO_1_ROW
+eval $qq;
+
+drop table t1, tmp;
+drop view v1,v2;
+
+--echo # end of WL#1393 - Optimizing filesort with small limit
#
# Bug#35844: Covering index for ref access not compatible with ORDER BY list
=== modified file 'mysql-test/include/select.inc'
--- a/mysql-test/include/select.inc 2010-07-23 17:51:11 +0000
+++ b/mysql-test/include/select.inc 2010-09-07 05:45:36 +0000
@@ -4145,7 +4145,7 @@ DROP TABLE t1;
--echo End of 5.1 tests
--echo #
---echo # Bug#45277: Lost HAVING clause led to a wrong result.
+--echo # Bug#45227: Lost HAVING clause led to a wrong result.
--echo #
CREATE TABLE `CC` (
`int_nokey` int(11) NOT NULL,
@@ -4167,7 +4167,7 @@ SELECT `varchar_nokey` G1 FROM CC WHER
HAVING G1 ORDER BY `varchar_key` LIMIT 6 ;
DROP TABLE CC;
---echo # End of test#45277
+--echo # End of test#45227
--echo #
--echo # Bug#54515: Crash in opt_range.cc::get_best_group_min_max on
=== modified file 'mysql-test/include/subquery.inc'
--- a/mysql-test/include/subquery.inc 2010-08-16 06:58:42 +0000
+++ b/mysql-test/include/subquery.inc 2010-09-07 05:45:36 +0000
@@ -2510,14 +2510,18 @@ insert into t2(y,z) select t1.b, RAND()*
enable_query_log;
SET SESSION sort_buffer_size = 32 * 1024;
-SELECT SQL_NO_CACHE COUNT(*)
+let qq= SELECT SQL_NO_CACHE COUNT(*)
FROM (SELECT a, b, (SELECT x FROM t2 WHERE y=b ORDER BY z DESC LIMIT 1) c
FROM t1) t;
+eval explain $qq;
+eval $qq;
SET SESSION sort_buffer_size = 8 * 1024 * 1024;
-SELECT SQL_NO_CACHE COUNT(*)
+let qq= SELECT SQL_NO_CACHE COUNT(*)
FROM (SELECT a, b, (SELECT x FROM t2 WHERE y=b ORDER BY z DESC LIMIT 1) c
FROM t1) t;
+eval explain $qq;
+eval $qq;
DROP TABLE t1,t2,t3;
=== modified file 'mysql-test/r/join_cache_jcl1.result'
--- a/mysql-test/r/join_cache_jcl1.result 2010-09-23 09:10:02 +0000
+++ b/mysql-test/r/join_cache_jcl1.result 2010-09-07 05:45:36 +0000
@@ -2219,7 +2219,7 @@ GROUP BY t1.col_int_key
ORDER BY t1.col_int_key, t1.col_datetime
LIMIT 2;
id select_type table type possible_keys key key_len ref rows Extra
-1 SIMPLE t1 index NULL col_int_key 5 NULL 2 Using temporary; Using filesort
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2 Using temporary; Using filesort
1 SIMPLE t2 ref col_int_key col_int_key 5 const 1 Using where
SELECT t1.col_int_key, t1.col_datetime
FROM t1,t2
=== modified file 'mysql-test/r/myisam_mrr_none.result'
--- a/mysql-test/r/myisam_mrr_none.result 2010-07-16 11:51:02 +0000
+++ b/mysql-test/r/myisam_mrr_none.result 2010-09-07 05:45:36 +0000
@@ -346,7 +346,7 @@ GROUP BY t2.pk
);
id select_type table type possible_keys key key_len ref rows filtered Extra
1 PRIMARY NULL NULL NULL NULL NULL NULL NULL NULL Impossible WHERE
-2 SUBQUERY t2 ALL int_key int_key 5 const 3 33.33 Using filesort
+2 SUBQUERY t2 ALL int_key int_key 5 const 3 33.33 Using filesort(PQ)
Warnings:
Note 1003 select min(`test`.`t1`.`pk`) AS `MIN(t1.pk)` from `test`.`t1` where 0
DROP TABLE t1, t2;
=== modified file 'mysql-test/r/order_by_none.result'
--- a/mysql-test/r/order_by_none.result 2010-07-04 15:07:55 +0000
+++ b/mysql-test/r/order_by_none.result 2010-09-07 05:45:36 +0000
@@ -1101,13 +1101,13 @@ id select_type table type possible_keys
1 SIMPLE t2 index k2 k3 5 NULL 111 Using where
EXPLAIN SELECT id,c3 FROM t2 WHERE c2=11 ORDER BY c3 LIMIT 4000;
id select_type table type possible_keys key key_len ref rows Extra
-1 SIMPLE t2 ref k2 k2 5 const 7341 Using where; Using filesort
+1 SIMPLE t2 ref k2 k2 5 const 7341 Using where; Using filesort(PQ)
EXPLAIN SELECT id,c3 FROM t2 WHERE c2 BETWEEN 10 AND 12 ORDER BY c3 LIMIT 20;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t2 index k2 k3 5 NULL 73 Using where
EXPLAIN SELECT id,c3 FROM t2 WHERE c2 BETWEEN 20 AND 30 ORDER BY c3 LIMIT 4000;
id select_type table type possible_keys key key_len ref rows Extra
-1 SIMPLE t2 range k2 k2 5 NULL 386 Using where; Using filesort
+1 SIMPLE t2 range k2 k2 5 NULL 386 Using where; Using filesort(PQ)
SELECT id,c3 FROM t2 WHERE c2=11 ORDER BY c3 LIMIT 20;
id c3
6 14
@@ -1504,6 +1504,986 @@ ORDER BY t2.c LIMIT 1;
d
52.5
DROP TABLE t1,t2,t3;
+#
+# WL#1393 - Optimizing filesort with small limit
+#
+create table t1(f0 int auto_increment primary key, f1 int, f2 varchar(200));
+insert into t1(f1, f2) values
+(0,"0"),(1,"1"),(2,"2"),(3,"3"),(4,"4"),(5,"5"),
+(6,"6"),(7,"7"),(8,"8"),(9,"9"),(10,"10"),
+(11,"11"),(12,"12"),(13,"13"),(14,"14"),(15,"15"),
+(16,"16"),(17,"17"),(18,"18"),(19,"19"),(20,"20"),
+(21,"21"),(22,"22"),(23,"23"),(24,"24"),(25,"25"),
+(26,"26"),(27,"27"),(28,"28"),(29,"29"),(30,"30"),
+(31,"31"),(32,"32"),(33,"33"),(34,"34"),(35,"35"),
+(36,"36"),(37,"37"),(38,"38"),(39,"39"),(40,"40"),
+(41,"41"),(42,"42"),(43,"43"),(44,"44"),(45,"45"),
+(46,"46"),(47,"47"),(48,"48"),(49,"49"),(50,"50"),
+(51,"51"),(52,"52"),(53,"53"),(54,"54"),(55,"55"),
+(56,"56"),(57,"57"),(58,"58"),(59,"59"),(60,"60"),
+(61,"61"),(62,"62"),(63,"63"),(64,"64"),(65,"65"),
+(66,"66"),(67,"67"),(68,"68"),(69,"69"),(70,"70"),
+(71,"71"),(72,"72"),(73,"73"),(74,"74"),(75,"75"),
+(76,"76"),(77,"77"),(78,"78"),(79,"79"),(80,"80"),
+(81,"81"),(82,"82"),(83,"83"),(84,"84"),(85,"85"),
+(86,"86"),(87,"87"),(88,"88"),(89,"89"),(90,"90"),
+(91,"91"),(92,"92"),(93,"93"),(94,"94"),(95,"95"),
+(96,"96"),(97,"97"),(98,"98"),(99,"99");
+explain select * from t1 order by f1 asc, f0 limit 100;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 100 Using filesort
+select * from t1 order by f1 asc, f0 limit 100;
+f0 f1 f2
+1 0 0
+2 1 1
+3 2 2
+4 3 3
+5 4 4
+6 5 5
+7 6 6
+8 7 7
+9 8 8
+10 9 9
+11 10 10
+12 11 11
+13 12 12
+14 13 13
+15 14 14
+16 15 15
+17 16 16
+18 17 17
+19 18 18
+20 19 19
+21 20 20
+22 21 21
+23 22 22
+24 23 23
+25 24 24
+26 25 25
+27 26 26
+28 27 27
+29 28 28
+30 29 29
+31 30 30
+32 31 31
+33 32 32
+34 33 33
+35 34 34
+36 35 35
+37 36 36
+38 37 37
+39 38 38
+40 39 39
+41 40 40
+42 41 41
+43 42 42
+44 43 43
+45 44 44
+46 45 45
+47 46 46
+48 47 47
+49 48 48
+50 49 49
+51 50 50
+52 51 51
+53 52 52
+54 53 53
+55 54 54
+56 55 55
+57 56 56
+58 57 57
+59 58 58
+60 59 59
+61 60 60
+62 61 61
+63 62 62
+64 63 63
+65 64 64
+66 65 65
+67 66 66
+68 67 67
+69 68 68
+70 69 69
+71 70 70
+72 71 71
+73 72 72
+74 73 73
+75 74 74
+76 75 75
+77 76 76
+78 77 77
+79 78 78
+80 79 79
+81 80 80
+82 81 81
+83 82 82
+84 83 83
+85 84 84
+86 85 85
+87 86 86
+88 87 87
+89 88 88
+90 89 89
+91 90 90
+92 91 91
+93 92 92
+94 93 93
+95 94 94
+96 95 95
+97 96 96
+98 97 97
+99 98 98
+100 99 99
+explain select * from t1 order by f1 asc, f0 limit 30;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 100 Using filesort(PQ)
+select * from t1 order by f1 asc, f0 limit 30;
+f0 f1 f2
+1 0 0
+2 1 1
+3 2 2
+4 3 3
+5 4 4
+6 5 5
+7 6 6
+8 7 7
+9 8 8
+10 9 9
+11 10 10
+12 11 11
+13 12 12
+14 13 13
+15 14 14
+16 15 15
+17 16 16
+18 17 17
+19 18 18
+20 19 19
+21 20 20
+22 21 21
+23 22 22
+24 23 23
+25 24 24
+26 25 25
+27 26 26
+28 27 27
+29 28 28
+30 29 29
+explain select * from t1 order by f1 asc, f0 limit 0;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE
+select * from t1 order by f1 asc, f0 limit 0;
+f0 f1 f2
+explain select * from t1 order by f2 desc, f0 limit 30;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 100 Using filesort(PQ)
+select * from t1 order by f2 desc, f0 limit 30;
+f0 f1 f2
+100 99 99
+99 98 98
+98 97 97
+97 96 96
+96 95 95
+95 94 94
+94 93 93
+93 92 92
+92 91 91
+91 90 90
+10 9 9
+90 89 89
+89 88 88
+88 87 87
+87 86 86
+86 85 85
+85 84 84
+84 83 83
+83 82 82
+82 81 81
+81 80 80
+9 8 8
+80 79 79
+79 78 78
+78 77 77
+77 76 76
+76 75 75
+75 74 74
+74 73 73
+73 72 72
+explain select * from t1 order by f2 desc, f0 limit 0;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE
+select * from t1 order by f2 desc, f0 limit 0;
+f0 f1 f2
+explain select * from t1 where f1>10 order by f2, f0 limit 20;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 100 Using where; Using filesort(PQ)
+select * from t1 where f1>10 order by f2, f0 limit 20;
+f0 f1 f2
+12 11 11
+13 12 12
+14 13 13
+15 14 14
+16 15 15
+17 16 16
+18 17 17
+19 18 18
+20 19 19
+21 20 20
+22 21 21
+23 22 22
+24 23 23
+25 24 24
+26 25 25
+27 26 26
+28 27 27
+29 28 28
+30 29 29
+31 30 30
+explain select * from t1 where f1>10 order by f2, f0 limit 0;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE
+select * from t1 where f1>10 order by f2, f0 limit 0;
+f0 f1 f2
+explain select * from t1 where f1>10 order by f2, f0 limit 10 offset 10;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 100 Using where; Using filesort(PQ)
+select * from t1 where f1>10 order by f2, f0 limit 10 offset 10;
+f0 f1 f2
+22 21 21
+23 22 22
+24 23 23
+25 24 24
+26 25 25
+27 26 26
+28 27 27
+29 28 28
+30 29 29
+31 30 30
+explain select * from t1 where f1>10 order by f2, f0 limit 0 offset 10;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 100 Using where; Using filesort(PQ)
+select * from t1 where f1>10 order by f2, f0 limit 0 offset 10;
+f0 f1 f2
+set sort_buffer_size= 32768;
+create temporary table tmp (f1 int, f2 varchar(20));
+insert into tmp select f1, f2 from t1;
+insert into t1(f1, f2) select * from tmp;
+insert into tmp select f1, f2 from t1;
+insert into t1(f1, f2) select * from tmp;
+explain select * from t1 order by f1 asc, f0 limit 30;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 500 Using filesort(PQ)
+select * from t1 order by f1 asc, f0 limit 30;
+f0 f1 f2
+1 0 0
+101 0 0
+201 0 0
+301 0 0
+401 0 0
+2 1 1
+102 1 1
+202 1 1
+302 1 1
+402 1 1
+3 2 2
+103 2 2
+203 2 2
+303 2 2
+403 2 2
+4 3 3
+104 3 3
+204 3 3
+304 3 3
+404 3 3
+5 4 4
+105 4 4
+205 4 4
+305 4 4
+405 4 4
+6 5 5
+106 5 5
+206 5 5
+306 5 5
+406 5 5
+explain select * from t1 order by f1 asc, f0 limit 0;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE
+select * from t1 order by f1 asc, f0 limit 0;
+f0 f1 f2
+explain select * from t1 order by f2 desc, f0 limit 30;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 500 Using filesort(PQ)
+select * from t1 order by f2 desc, f0 limit 30;
+f0 f1 f2
+100 99 99
+200 99 99
+300 99 99
+400 99 99
+500 99 99
+99 98 98
+199 98 98
+299 98 98
+399 98 98
+499 98 98
+98 97 97
+198 97 97
+298 97 97
+398 97 97
+498 97 97
+97 96 96
+197 96 96
+297 96 96
+397 96 96
+497 96 96
+96 95 95
+196 95 95
+296 95 95
+396 95 95
+496 95 95
+95 94 94
+195 94 94
+295 94 94
+395 94 94
+495 94 94
+explain select * from t1 order by f2 desc, f0 limit 0;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE
+select * from t1 order by f2 desc, f0 limit 0;
+f0 f1 f2
+explain select * from t1 where f1>10 order by f2, f0 limit 20;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 500 Using where; Using filesort(PQ)
+select * from t1 where f1>10 order by f2, f0 limit 20;
+f0 f1 f2
+12 11 11
+112 11 11
+212 11 11
+312 11 11
+412 11 11
+13 12 12
+113 12 12
+213 12 12
+313 12 12
+413 12 12
+14 13 13
+114 13 13
+214 13 13
+314 13 13
+414 13 13
+15 14 14
+115 14 14
+215 14 14
+315 14 14
+415 14 14
+explain select * from t1 where f1>10 order by f2, f0 limit 0;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE
+select * from t1 where f1>10 order by f2, f0 limit 0;
+f0 f1 f2
+explain select * from t1 where f1>10 order by f2, f0 limit 10 offset 10;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 500 Using where; Using filesort(PQ)
+select * from t1 where f1>10 order by f2, f0 limit 10 offset 10;
+f0 f1 f2
+14 13 13
+114 13 13
+214 13 13
+314 13 13
+414 13 13
+15 14 14
+115 14 14
+215 14 14
+315 14 14
+415 14 14
+explain select * from t1 where f1>10 order by f2, f0 limit 0 offset 10;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 500 Using where; Using filesort(PQ)
+select * from t1 where f1>10 order by f2, f0 limit 0 offset 10;
+f0 f1 f2
+explain select SQL_CALC_FOUND_ROWS * from t1
+order by f1, f0 limit 30;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 500 Using filesort(PQ)
+select SQL_CALC_FOUND_ROWS * from t1
+order by f1, f0 limit 30;
+f0 f1 f2
+1 0 0
+101 0 0
+201 0 0
+301 0 0
+401 0 0
+2 1 1
+102 1 1
+202 1 1
+302 1 1
+402 1 1
+3 2 2
+103 2 2
+203 2 2
+303 2 2
+403 2 2
+4 3 3
+104 3 3
+204 3 3
+304 3 3
+404 3 3
+5 4 4
+105 4 4
+205 4 4
+305 4 4
+405 4 4
+6 5 5
+106 5 5
+206 5 5
+306 5 5
+406 5 5
+select FOUND_ROWS();
+FOUND_ROWS()
+500
+explain select SQL_CALC_FOUND_ROWS * from t1
+order by f1, f0 limit 0;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 500 Using filesort(PQ)
+select SQL_CALC_FOUND_ROWS * from t1
+order by f1, f0 limit 0;
+f0 f1 f2
+select FOUND_ROWS();
+FOUND_ROWS()
+500
+explain select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 20;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 500 Using where; Using filesort(PQ)
+select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 20;
+f0 f1 f2
+12 11 11
+112 11 11
+212 11 11
+312 11 11
+412 11 11
+13 12 12
+113 12 12
+213 12 12
+313 12 12
+413 12 12
+14 13 13
+114 13 13
+214 13 13
+314 13 13
+414 13 13
+15 14 14
+115 14 14
+215 14 14
+315 14 14
+415 14 14
+select FOUND_ROWS();
+FOUND_ROWS()
+445
+explain select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 0;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 500 Using where; Using filesort(PQ)
+select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 0;
+f0 f1 f2
+select FOUND_ROWS();
+FOUND_ROWS()
+445
+explain select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 10 offset 10;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 500 Using where; Using filesort(PQ)
+select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 10 offset 10;
+f0 f1 f2
+14 13 13
+114 13 13
+214 13 13
+314 13 13
+414 13 13
+15 14 14
+115 14 14
+215 14 14
+315 14 14
+415 14 14
+select FOUND_ROWS();
+FOUND_ROWS()
+445
+explain select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 0 offset 10;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 500 Using where; Using filesort(PQ)
+select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 0 offset 10;
+f0 f1 f2
+select FOUND_ROWS();
+FOUND_ROWS()
+445
+set sort_buffer_size= 327680;
+explain select * from t1 join tmp on t1.f2=tmp.f2
+order by tmp.f1, f0 limit 30;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE tmp ALL NULL NULL NULL NULL 300 Using temporary; Using filesort
+1 SIMPLE t1 ALL NULL NULL NULL NULL 500 Using where; Using join buffer (BNL, regular buffers)
+select * from t1 join tmp on t1.f2=tmp.f2
+order by tmp.f1, f0 limit 30;
+f0 f1 f2 f1 f2
+1 0 0 0 0
+1 0 0 0 0
+1 0 0 0 0
+101 0 0 0 0
+101 0 0 0 0
+101 0 0 0 0
+201 0 0 0 0
+201 0 0 0 0
+201 0 0 0 0
+301 0 0 0 0
+301 0 0 0 0
+301 0 0 0 0
+401 0 0 0 0
+401 0 0 0 0
+401 0 0 0 0
+2 1 1 1 1
+2 1 1 1 1
+2 1 1 1 1
+102 1 1 1 1
+102 1 1 1 1
+102 1 1 1 1
+202 1 1 1 1
+202 1 1 1 1
+202 1 1 1 1
+302 1 1 1 1
+302 1 1 1 1
+302 1 1 1 1
+402 1 1 1 1
+402 1 1 1 1
+402 1 1 1 1
+explain select * from t1 join tmp on t1.f2=tmp.f2
+order by tmp.f1, f0 limit 30 offset 30;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE tmp ALL NULL NULL NULL NULL 300 Using temporary; Using filesort
+1 SIMPLE t1 ALL NULL NULL NULL NULL 500 Using where; Using join buffer (BNL, regular buffers)
+select * from t1 join tmp on t1.f2=tmp.f2
+order by tmp.f1, f0 limit 30 offset 30;
+f0 f1 f2 f1 f2
+3 2 2 2 2
+3 2 2 2 2
+3 2 2 2 2
+103 2 2 2 2
+103 2 2 2 2
+103 2 2 2 2
+203 2 2 2 2
+203 2 2 2 2
+203 2 2 2 2
+303 2 2 2 2
+303 2 2 2 2
+303 2 2 2 2
+403 2 2 2 2
+403 2 2 2 2
+403 2 2 2 2
+4 3 3 3 3
+4 3 3 3 3
+4 3 3 3 3
+104 3 3 3 3
+104 3 3 3 3
+104 3 3 3 3
+204 3 3 3 3
+204 3 3 3 3
+204 3 3 3 3
+304 3 3 3 3
+304 3 3 3 3
+304 3 3 3 3
+404 3 3 3 3
+404 3 3 3 3
+404 3 3 3 3
+explain select SQL_CALC_FOUND_ROWS * from t1 join tmp on t1.f2=tmp.f2
+order by tmp.f1, f0 limit 30 offset 30;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE tmp ALL NULL NULL NULL NULL 300 Using temporary; Using filesort
+1 SIMPLE t1 ALL NULL NULL NULL NULL 500 Using where; Using join buffer (BNL, regular buffers)
+select SQL_CALC_FOUND_ROWS * from t1 join tmp on t1.f2=tmp.f2
+order by tmp.f1, f0 limit 30 offset 30;
+f0 f1 f2 f1 f2
+3 2 2 2 2
+3 2 2 2 2
+3 2 2 2 2
+103 2 2 2 2
+103 2 2 2 2
+103 2 2 2 2
+203 2 2 2 2
+203 2 2 2 2
+203 2 2 2 2
+303 2 2 2 2
+303 2 2 2 2
+303 2 2 2 2
+403 2 2 2 2
+403 2 2 2 2
+403 2 2 2 2
+4 3 3 3 3
+4 3 3 3 3
+4 3 3 3 3
+104 3 3 3 3
+104 3 3 3 3
+104 3 3 3 3
+204 3 3 3 3
+204 3 3 3 3
+204 3 3 3 3
+304 3 3 3 3
+304 3 3 3 3
+304 3 3 3 3
+404 3 3 3 3
+404 3 3 3 3
+404 3 3 3 3
+select FOUND_ROWS();
+FOUND_ROWS()
+1500
+explain select SQL_CALC_FOUND_ROWS * from t1 join tmp on t1.f2=tmp.f2
+where t1.f2>20
+order by tmp.f1, f0 limit 30 offset 30;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE tmp ALL NULL NULL NULL NULL 300 Using temporary; Using filesort
+1 SIMPLE t1 ALL NULL NULL NULL NULL 500 Using where; Using join buffer (BNL, regular buffers)
+select SQL_CALC_FOUND_ROWS * from t1 join tmp on t1.f2=tmp.f2
+where t1.f2>20
+order by tmp.f1, f0 limit 30 offset 30;
+f0 f1 f2 f1 f2
+24 23 23 23 23
+24 23 23 23 23
+24 23 23 23 23
+124 23 23 23 23
+124 23 23 23 23
+124 23 23 23 23
+224 23 23 23 23
+224 23 23 23 23
+224 23 23 23 23
+324 23 23 23 23
+324 23 23 23 23
+324 23 23 23 23
+424 23 23 23 23
+424 23 23 23 23
+424 23 23 23 23
+25 24 24 24 24
+25 24 24 24 24
+25 24 24 24 24
+125 24 24 24 24
+125 24 24 24 24
+125 24 24 24 24
+225 24 24 24 24
+225 24 24 24 24
+225 24 24 24 24
+325 24 24 24 24
+325 24 24 24 24
+325 24 24 24 24
+425 24 24 24 24
+425 24 24 24 24
+425 24 24 24 24
+select FOUND_ROWS();
+FOUND_ROWS()
+1185
+create view v1 as select * from t1 order by f1, f0 limit 30;
+explain select * from v1;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY <derived2> ALL NULL NULL NULL NULL 30
+2 DERIVED t1 ALL NULL NULL NULL NULL 500 Using filesort(PQ)
+select * from v1;
+f0 f1 f2
+1 0 0
+101 0 0
+201 0 0
+301 0 0
+401 0 0
+2 1 1
+102 1 1
+202 1 1
+302 1 1
+402 1 1
+3 2 2
+103 2 2
+203 2 2
+303 2 2
+403 2 2
+4 3 3
+104 3 3
+204 3 3
+304 3 3
+404 3 3
+5 4 4
+105 4 4
+205 4 4
+305 4 4
+405 4 4
+6 5 5
+106 5 5
+206 5 5
+306 5 5
+406 5 5
+drop view v1;
+create view v1 as select * from t1 order by f1, f0 limit 100;
+explain select * from v1 order by f2, f0 limit 30;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY <derived2> ALL NULL NULL NULL NULL 100 Using filesort(PQ)
+2 DERIVED t1 ALL NULL NULL NULL NULL 500 Using filesort(PQ)
+select * from v1 order by f2, f0 limit 30;
+f0 f1 f2
+1 0 0
+101 0 0
+201 0 0
+301 0 0
+401 0 0
+2 1 1
+102 1 1
+202 1 1
+302 1 1
+402 1 1
+11 10 10
+111 10 10
+211 10 10
+311 10 10
+411 10 10
+12 11 11
+112 11 11
+212 11 11
+312 11 11
+412 11 11
+13 12 12
+113 12 12
+213 12 12
+313 12 12
+413 12 12
+14 13 13
+114 13 13
+214 13 13
+314 13 13
+414 13 13
+create view v2 as select * from t1 order by f2, f0 limit 100;
+explain select * from v1 join v2 on v1.f1=v2.f1 order by v1.f2,v1.f0,v2.f0
+limit 30;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY <derived2> ALL NULL NULL NULL NULL 100 Using temporary; Using filesort
+1 PRIMARY <derived3> ALL NULL NULL NULL NULL 100 Using where; Using join buffer (BNL, regular buffers)
+3 DERIVED t1 ALL NULL NULL NULL NULL 500 Using filesort(PQ)
+2 DERIVED t1 ALL NULL NULL NULL NULL 500 Using filesort(PQ)
+select * from v1 join v2 on v1.f1=v2.f1 order by v1.f2,v1.f0,v2.f0
+limit 30;
+f0 f1 f2 f0 f1 f2
+1 0 0 1 0 0
+1 0 0 101 0 0
+1 0 0 201 0 0
+1 0 0 301 0 0
+1 0 0 401 0 0
+101 0 0 1 0 0
+101 0 0 101 0 0
+101 0 0 201 0 0
+101 0 0 301 0 0
+101 0 0 401 0 0
+201 0 0 1 0 0
+201 0 0 101 0 0
+201 0 0 201 0 0
+201 0 0 301 0 0
+201 0 0 401 0 0
+301 0 0 1 0 0
+301 0 0 101 0 0
+301 0 0 201 0 0
+301 0 0 301 0 0
+301 0 0 401 0 0
+401 0 0 1 0 0
+401 0 0 101 0 0
+401 0 0 201 0 0
+401 0 0 301 0 0
+401 0 0 401 0 0
+2 1 1 2 1 1
+2 1 1 102 1 1
+2 1 1 202 1 1
+2 1 1 302 1 1
+2 1 1 402 1 1
+explain select floor(f1/10) f3, count(f2) from t1
+group by 1 order by 2,1 limit 5;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 500 Using temporary; Using filesort
+select floor(f1/10) f3, count(f2) from t1
+group by 1 order by 2,1 limit 5;
+f3 count(f2)
+0 50
+1 50
+2 50
+3 50
+4 50
+explain select floor(f1/10) f3, count(f2) from t1
+group by 1 order by 2,1 limit 0;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE NULL NULL NULL NULL NULL NULL NULL Impossible WHERE
+select floor(f1/10) f3, count(f2) from t1
+group by 1 order by 2,1 limit 0;
+f3 count(f2)
+create procedure wl1393_sp_test()
+begin
+select * from t1 where f1>10 order by f2, f0 limit 30;
+select * from t1 where f1>10 order by f2, f0 limit 15 offset 15;
+select SQL_CALC_FOUND_ROWS * from t1 where f1>10
+order by f2, f0 limit 15 offset 15;
+select FOUND_ROWS();
+select * from v1 order by f2, f0 limit 30;
+end|
+call wl1393_sp_test()|
+f0 f1 f2
+12 11 11
+112 11 11
+212 11 11
+312 11 11
+412 11 11
+13 12 12
+113 12 12
+213 12 12
+313 12 12
+413 12 12
+14 13 13
+114 13 13
+214 13 13
+314 13 13
+414 13 13
+15 14 14
+115 14 14
+215 14 14
+315 14 14
+415 14 14
+16 15 15
+116 15 15
+216 15 15
+316 15 15
+416 15 15
+17 16 16
+117 16 16
+217 16 16
+317 16 16
+417 16 16
+f0 f1 f2
+15 14 14
+115 14 14
+215 14 14
+315 14 14
+415 14 14
+16 15 15
+116 15 15
+216 15 15
+316 15 15
+416 15 15
+17 16 16
+117 16 16
+217 16 16
+317 16 16
+417 16 16
+f0 f1 f2
+15 14 14
+115 14 14
+215 14 14
+315 14 14
+415 14 14
+16 15 15
+116 15 15
+216 15 15
+316 15 15
+416 15 15
+17 16 16
+117 16 16
+217 16 16
+317 16 16
+417 16 16
+FOUND_ROWS()
+445
+f0 f1 f2
+1 0 0
+101 0 0
+201 0 0
+301 0 0
+401 0 0
+2 1 1
+102 1 1
+202 1 1
+302 1 1
+402 1 1
+11 10 10
+111 10 10
+211 10 10
+311 10 10
+411 10 10
+12 11 11
+112 11 11
+212 11 11
+312 11 11
+412 11 11
+13 12 12
+113 12 12
+213 12 12
+313 12 12
+413 12 12
+14 13 13
+114 13 13
+214 13 13
+314 13 13
+414 13 13
+drop procedure wl1393_sp_test|
+explain select d1.* from t1
+left join (select * from t1 limit 30) d1 on t1.f1=d1.f1
+order by d1.f2 desc limit 30;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 500 Using temporary; Using filesort
+1 PRIMARY <derived2> ALL NULL NULL NULL NULL 30 Using where
+2 DERIVED t1 ALL NULL NULL NULL NULL 500
+select d1.* from t1
+left join (select * from t1 limit 30) d1 on t1.f1=d1.f1
+order by d1.f2 desc limit 30;
+f0 f1 f2
+10 9 9
+10 9 9
+10 9 9
+10 9 9
+10 9 9
+9 8 8
+9 8 8
+9 8 8
+9 8 8
+9 8 8
+8 7 7
+8 7 7
+8 7 7
+8 7 7
+8 7 7
+7 6 6
+7 6 6
+7 6 6
+7 6 6
+7 6 6
+6 5 5
+6 5 5
+6 5 5
+6 5 5
+6 5 5
+5 4 4
+5 4 4
+5 4 4
+5 4 4
+5 4 4
+explain select * from t1 where f1 = (select f1 from t1 order by 1 limit 1);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 500 Using where
+2 SUBQUERY t1 ALL NULL NULL NULL NULL 500 Using filesort(PQ)
+select * from t1 where f1 = (select f1 from t1 order by 1 limit 1);
+f0 f1 f2
+1 0 0
+101 0 0
+201 0 0
+301 0 0
+401 0 0
+explain select * from t1 where f1 = (select f1 from t1 order by 1 limit 2);
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY t1 ALL NULL NULL NULL NULL 500 Using where
+2 SUBQUERY t1 ALL NULL NULL NULL NULL 500 Using filesort(PQ)
+select * from t1 where f1 = (select f1 from t1 order by 1 limit 2);
+ERROR 21000: Subquery returns more than 1 row
+drop table t1, tmp;
+drop view v1,v2;
+# end of WL#1393 - Optimizing filesort with small limit
CREATE TABLE t1 (
id1 INT NULL,
id2 INT NOT NULL,
=== added file 'mysql-test/r/order_by_sortkey.result'
--- a/mysql-test/r/order_by_sortkey.result 1970-01-01 00:00:00 +0000
+++ b/mysql-test/r/order_by_sortkey.result 2010-09-07 05:45:36 +0000
@@ -0,0 +1,164 @@
+create table t1(
+f0 int auto_increment primary key,
+f1 int,
+f2 varchar(200)
+) ENGINE=MyISAM;
+insert into t1(f1, f2) values
+(0,"0"),(1,"1"),(2,"2"),(3,"3"),(4,"4"),(5,"5"),
+(6,"6"),(7,"7"),(8,"8"),(9,"9"),(10,"10"),
+(11,"11"),(12,"12"),(13,"13"),(14,"14"),(15,"15"),
+(16,"16"),(17,"17"),(18,"18"),(19,"19"),(20,"20"),
+(21,"21"),(22,"22"),(23,"23"),(24,"24"),(25,"25"),
+(26,"26"),(27,"27"),(28,"28"),(29,"29"),(30,"30"),
+(31,"31"),(32,"32"),(33,"33"),(34,"34"),(35,"35"),
+(36,"36"),(37,"37"),(38,"38"),(39,"39"),(40,"40"),
+(41,"41"),(42,"42"),(43,"43"),(44,"44"),(45,"45"),
+(46,"46"),(47,"47"),(48,"48"),(49,"49"),(50,"50"),
+(51,"51"),(52,"52"),(53,"53"),(54,"54"),(55,"55"),
+(56,"56"),(57,"57"),(58,"58"),(59,"59"),(60,"60"),
+(61,"61"),(62,"62"),(63,"63"),(64,"64"),(65,"65"),
+(66,"66"),(67,"67"),(68,"68"),(69,"69"),(70,"70"),
+(71,"71"),(72,"72"),(73,"73"),(74,"74"),(75,"75"),
+(76,"76"),(77,"77"),(78,"78"),(79,"79"),(80,"80"),
+(81,"81"),(82,"82"),(83,"83"),(84,"84"),(85,"85"),
+(86,"86"),(87,"87"),(88,"88"),(89,"89"),(90,"90"),
+(91,"91"),(92,"92"),(93,"93"),(94,"94"),(95,"95"),
+(96,"96"),(97,"97"),(98,"98"),(99,"99");
+create temporary table tmp (f1 int, f2 varchar(20));
+insert into tmp select f1,f2 from t1;
+insert into t1(f1,f2) select * from tmp;
+insert into tmp select f1,f2 from t1;
+insert into t1(f1,f2) select * from tmp;
+set sort_buffer_size= 32768;
+insert into t1(f1,f2) select * from tmp;
+insert into tmp select f1,f2 from t1;
+insert into t1(f1,f2) select * from tmp;
+insert into tmp select f1,f2 from t1;
+insert into t1(f1,f2) select * from tmp;
+insert into tmp select f1,f2 from t1;
+insert into t1(f1,f2) select * from tmp;
+insert into tmp select f1,f2 from t1;
+insert into t1(f1,f2) select * from tmp;
+insert into tmp select f1,f2 from t1;
+insert into t1(f1,f2) select * from tmp;
+insert into tmp select f1,f2 from t1;
+insert into t1(f1,f2) select * from tmp;
+FLUSH STATUS;
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name Value
+Sort_merge_passes 0
+Sort_range 0
+Sort_rows 0
+Sort_scan 0
+explain select * from t1 order by f2 limit 100;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 229600 Using filesort(PQ)
+select * from t1 order by f2 limit 100;
+f0 f1 f2
+1 0 0
+101 0 0
+201 0 0
+301 0 0
+401 0 0
+501 0 0
+601 0 0
+701 0 0
+801 0 0
+901 0 0
+1001 0 0
+1101 0 0
+1201 0 0
+1301 0 0
+1401 0 0
+1501 0 0
+1601 0 0
+1701 0 0
+1801 0 0
+1901 0 0
+2001 0 0
+2101 0 0
+2201 0 0
+2301 0 0
+2401 0 0
+2501 0 0
+2601 0 0
+2701 0 0
+2801 0 0
+2901 0 0
+3001 0 0
+3101 0 0
+3201 0 0
+3301 0 0
+3401 0 0
+3501 0 0
+3601 0 0
+3701 0 0
+3801 0 0
+3901 0 0
+4001 0 0
+4101 0 0
+4201 0 0
+4301 0 0
+4401 0 0
+4501 0 0
+4601 0 0
+4701 0 0
+4801 0 0
+4901 0 0
+5001 0 0
+5101 0 0
+5201 0 0
+5301 0 0
+5401 0 0
+5501 0 0
+5601 0 0
+5701 0 0
+5801 0 0
+5901 0 0
+6001 0 0
+6101 0 0
+6201 0 0
+6301 0 0
+6401 0 0
+6501 0 0
+6601 0 0
+6701 0 0
+6801 0 0
+6901 0 0
+7001 0 0
+7101 0 0
+7201 0 0
+7301 0 0
+7401 0 0
+7501 0 0
+7601 0 0
+7701 0 0
+7801 0 0
+7901 0 0
+8001 0 0
+8101 0 0
+8201 0 0
+8301 0 0
+8401 0 0
+8501 0 0
+8601 0 0
+8701 0 0
+8801 0 0
+8901 0 0
+9001 0 0
+9101 0 0
+9201 0 0
+9301 0 0
+9401 0 0
+9501 0 0
+9601 0 0
+9701 0 0
+9801 0 0
+9901 0 0
+SHOW SESSION STATUS LIKE 'Sort%';
+Variable_name Value
+Sort_merge_passes 0
+Sort_range 0
+Sort_rows 100
+Sort_scan 1
+drop table t1, tmp;
=== modified file 'mysql-test/r/select_none.result'
--- a/mysql-test/r/select_none.result 2010-09-09 18:21:34 +0000
+++ b/mysql-test/r/select_none.result 2010-09-07 05:45:36 +0000
@@ -4578,7 +4578,7 @@ a b c
2
EXPLAIN SELECT * FROM t1 ORDER BY a, b, c LIMIT 5;
id select_type table type possible_keys key key_len ref rows Extra
-1 SIMPLE t1 ALL NULL NULL NULL NULL 24492 Using filesort
+1 SIMPLE t1 ALL NULL NULL NULL NULL 24492 Using filesort(PQ)
SELECT * FROM t1 ORDER BY a, b, c LIMIT 5;
a b c
0
@@ -4588,7 +4588,7 @@ a b c
0
EXPLAIN SELECT * FROM t1 ORDER BY c, a LIMIT 5;
id select_type table type possible_keys key key_len ref rows Extra
-1 SIMPLE t1 ALL NULL NULL NULL NULL 24492 Using filesort
+1 SIMPLE t1 ALL NULL NULL NULL NULL 24492 Using filesort(PQ)
SELECT * FROM t1 ORDER BY c, a LIMIT 5;
a b c
0
@@ -4880,7 +4880,7 @@ SELECT 1 FROM t1 ORDER BY a COLLATE lati
DROP TABLE t1;
End of 5.1 tests
#
-# Bug#45277: Lost HAVING clause led to a wrong result.
+# Bug#45227: Lost HAVING clause led to a wrong result.
#
CREATE TABLE `CC` (
`int_nokey` int(11) NOT NULL,
@@ -4898,7 +4898,7 @@ INSERT INTO `CC` VALUES
EXPLAIN SELECT `varchar_nokey` G1 FROM CC WHERE `int_nokey` AND `int_key` <= 4
HAVING G1 ORDER BY `varchar_key` LIMIT 6 ;
id select_type table type possible_keys key key_len ref rows Extra
-1 SIMPLE CC range int_key int_key 4 NULL 10 Using where; Using filesort
+1 SIMPLE CC range int_key int_key 4 NULL 10 Using where; Using filesort(PQ)
SELECT `varchar_nokey` G1 FROM CC WHERE `int_nokey` AND `int_key` <= 4
HAVING G1 ORDER BY `varchar_key` LIMIT 6 ;
G1
@@ -4909,7 +4909,7 @@ Warning 1292 Truncated incorrect DOUBLE
Warning 1292 Truncated incorrect DOUBLE value: 'm'
Warning 1292 Truncated incorrect DOUBLE value: 'j'
DROP TABLE CC;
-# End of test#45277
+# End of test#45227
#
# Bug#54515: Crash in opt_range.cc::get_best_group_min_max on
# SELECT from VIEW with GROUP BY
=== modified file 'mysql-test/r/subquery_none.result'
--- a/mysql-test/r/subquery_none.result 2010-08-27 06:36:54 +0000
+++ b/mysql-test/r/subquery_none.result 2010-09-07 05:45:36 +0000
@@ -182,7 +182,7 @@ a b
explain extended (select * from t2 where t2.b=(select a from t3 order by 1 desc limit 1)) union (select * from t4 where t4.b=(select max(t2.a)*4 from t2) order by a);
id select_type table type possible_keys key key_len ref rows filtered Extra
1 PRIMARY t2 ALL NULL NULL NULL NULL 2 100.00 Using where
-2 SUBQUERY t3 ALL NULL NULL NULL NULL 3 100.00 Using filesort
+2 SUBQUERY t3 ALL NULL NULL NULL NULL 3 100.00 Using filesort(PQ)
3 UNION t4 ALL NULL NULL NULL NULL 3 100.00 Using where
4 SUBQUERY t2 ALL NULL NULL NULL NULL 2 100.00
NULL UNION RESULT <union1,3> ALL NULL NULL NULL NULL NULL NULL
@@ -201,7 +201,7 @@ explain extended select (select t3.a fro
id select_type table type possible_keys key key_len ref rows filtered Extra
1 PRIMARY <derived3> system NULL NULL NULL NULL 1 100.00
3 DERIVED t2 ALL NULL NULL NULL NULL 2 100.00 Using where
-2 SUBQUERY t3 ALL NULL NULL NULL NULL 3 100.00 Using where; Using filesort
+2 SUBQUERY t3 ALL NULL NULL NULL NULL 3 100.00 Using where; Using filesort(PQ)
Warnings:
Note 1003 select (select `test`.`t3`.`a` from `test`.`t3` where (`test`.`t3`.`a` < 8) order by 1 desc limit 1) AS `(select t3.a from t3 where a<8 order by 1 desc limit 1)`,'2' AS `a` from dual
select * from t1 where t1.a=(select t2.a from t2 where t2.b=(select max(a) from t3) order by 1 desc limit 1);
@@ -3464,12 +3464,26 @@ insert into t1 select RAND()*1000, A.a +
from t3 A, t3 B, t3 C, t3 D where D.a<3;
insert into t2(y,z) select t1.b, RAND()*1000 from t1, t3;
SET SESSION sort_buffer_size = 32 * 1024;
+explain SELECT SQL_NO_CACHE COUNT(*)
+FROM (SELECT a, b, (SELECT x FROM t2 WHERE y=b ORDER BY z DESC LIMIT 1) c
+FROM t1) t;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY NULL NULL NULL NULL NULL NULL NULL Select tables optimized away
+2 DERIVED t1 ALL NULL NULL NULL NULL 3000
+3 DEPENDENT SUBQUERY t2 ALL y y 5 test.t1.b 30000 Using filesort(PQ)
SELECT SQL_NO_CACHE COUNT(*)
FROM (SELECT a, b, (SELECT x FROM t2 WHERE y=b ORDER BY z DESC LIMIT 1) c
FROM t1) t;
COUNT(*)
3000
SET SESSION sort_buffer_size = 8 * 1024 * 1024;
+explain SELECT SQL_NO_CACHE COUNT(*)
+FROM (SELECT a, b, (SELECT x FROM t2 WHERE y=b ORDER BY z DESC LIMIT 1) c
+FROM t1) t;
+id select_type table type possible_keys key key_len ref rows Extra
+1 PRIMARY NULL NULL NULL NULL NULL NULL NULL Select tables optimized away
+2 DERIVED t1 ALL NULL NULL NULL NULL 3000
+3 DEPENDENT SUBQUERY t2 ALL y y 5 test.t1.b 30000 Using filesort(PQ)
SELECT SQL_NO_CACHE COUNT(*)
FROM (SELECT a, b, (SELECT x FROM t2 WHERE y=b ORDER BY z DESC LIMIT 1) c
FROM t1) t;
=== modified file 'mysql-test/r/view.result'
--- a/mysql-test/r/view.result 2010-08-30 06:38:09 +0000
+++ b/mysql-test/r/view.result 2010-09-07 05:45:36 +0000
@@ -303,7 +303,7 @@ a+1
explain select * from v1;
id select_type table type possible_keys key key_len ref rows Extra
1 PRIMARY <derived2> ALL NULL NULL NULL NULL 2
-2 DERIVED t1 ALL NULL NULL NULL NULL 4 Using filesort
+2 DERIVED t1 ALL NULL NULL NULL NULL 4 Using filesort(PQ)
drop view v1;
drop table t1;
create table t1 (a int);
=== added file 'mysql-test/t/order_by_sortkey.test'
--- a/mysql-test/t/order_by_sortkey.test 1970-01-01 00:00:00 +0000
+++ b/mysql-test/t/order_by_sortkey.test 2010-09-07 05:45:36 +0000
@@ -0,0 +1,66 @@
+#
+# WL#1393 - ORDER BY with LIMIT tests
+#
+# A big test in a separate file, so that we can run the original
+# order_by test with --debug without timeout.
+#
+create table t1(
+ f0 int auto_increment primary key,
+ f1 int,
+ f2 varchar(200)
+) ENGINE=MyISAM;
+
+insert into t1(f1, f2) values
+(0,"0"),(1,"1"),(2,"2"),(3,"3"),(4,"4"),(5,"5"),
+(6,"6"),(7,"7"),(8,"8"),(9,"9"),(10,"10"),
+(11,"11"),(12,"12"),(13,"13"),(14,"14"),(15,"15"),
+(16,"16"),(17,"17"),(18,"18"),(19,"19"),(20,"20"),
+(21,"21"),(22,"22"),(23,"23"),(24,"24"),(25,"25"),
+(26,"26"),(27,"27"),(28,"28"),(29,"29"),(30,"30"),
+(31,"31"),(32,"32"),(33,"33"),(34,"34"),(35,"35"),
+(36,"36"),(37,"37"),(38,"38"),(39,"39"),(40,"40"),
+(41,"41"),(42,"42"),(43,"43"),(44,"44"),(45,"45"),
+(46,"46"),(47,"47"),(48,"48"),(49,"49"),(50,"50"),
+(51,"51"),(52,"52"),(53,"53"),(54,"54"),(55,"55"),
+(56,"56"),(57,"57"),(58,"58"),(59,"59"),(60,"60"),
+(61,"61"),(62,"62"),(63,"63"),(64,"64"),(65,"65"),
+(66,"66"),(67,"67"),(68,"68"),(69,"69"),(70,"70"),
+(71,"71"),(72,"72"),(73,"73"),(74,"74"),(75,"75"),
+(76,"76"),(77,"77"),(78,"78"),(79,"79"),(80,"80"),
+(81,"81"),(82,"82"),(83,"83"),(84,"84"),(85,"85"),
+(86,"86"),(87,"87"),(88,"88"),(89,"89"),(90,"90"),
+(91,"91"),(92,"92"),(93,"93"),(94,"94"),(95,"95"),
+(96,"96"),(97,"97"),(98,"98"),(99,"99");
+
+create temporary table tmp (f1 int, f2 varchar(20));
+insert into tmp select f1,f2 from t1;
+insert into t1(f1,f2) select * from tmp;
+insert into tmp select f1,f2 from t1;
+insert into t1(f1,f2) select * from tmp;
+
+# Test when only sortkeys fits to memory
+set sort_buffer_size= 32768;
+insert into t1(f1,f2) select * from tmp;
+insert into tmp select f1,f2 from t1;
+insert into t1(f1,f2) select * from tmp;
+insert into tmp select f1,f2 from t1;
+insert into t1(f1,f2) select * from tmp;
+insert into tmp select f1,f2 from t1;
+insert into t1(f1,f2) select * from tmp;
+insert into tmp select f1,f2 from t1;
+insert into t1(f1,f2) select * from tmp;
+insert into tmp select f1,f2 from t1;
+insert into t1(f1,f2) select * from tmp;
+insert into tmp select f1,f2 from t1;
+insert into t1(f1,f2) select * from tmp;
+
+FLUSH STATUS;
+SHOW SESSION STATUS LIKE 'Sort%';
+
+let qq=select * from t1 order by f2 limit 100;
+eval explain $qq;
+eval $qq;
+
+SHOW SESSION STATUS LIKE 'Sort%';
+
+drop table t1, tmp;
=== modified file 'mysys/CMakeLists.txt'
--- a/mysys/CMakeLists.txt 2010-08-12 15:27:53 +0000
+++ b/mysys/CMakeLists.txt 2010-09-07 05:45:36 +0000
@@ -77,3 +77,8 @@ DTRACE_INSTRUMENT(mysys)
ADD_EXECUTABLE(thr_lock thr_lock.c)
TARGET_LINK_LIBRARIES(thr_lock mysys)
SET_TARGET_PROPERTIES(thr_lock PROPERTIES COMPILE_FLAGS "-DMAIN")
+
+ADD_EXECUTABLE(queues queues.c)
+TARGET_LINK_LIBRARIES(queues mysys)
+SET_TARGET_PROPERTIES(queues PROPERTIES COMPILE_FLAGS "-DMAIN")
+ADD_TEST(queues_test queues)
=== modified file 'mysys/queues.c'
--- a/mysys/queues.c 2010-07-08 21:20:08 +0000
+++ b/mysys/queues.c 2010-09-07 05:45:36 +0000
@@ -381,11 +381,11 @@ static uint tot_no_parts= 0;
static uint tot_no_loops= 0;
static uint expected_part= 0;
static uint expected_num= 0;
-static bool max_ind= 0;
-static bool fix_used= 0;
+static my_bool max_ind= 0;
+static my_bool fix_used= 0;
static ulonglong start_time= 0;
-static bool is_divisible_by(uint num, uint divisor)
+static my_bool is_divisible_by(uint num, uint divisor)
{
uint quotient= num / divisor;
if (quotient * divisor == num)
@@ -492,7 +492,7 @@ static int test_compare(void *null_arg,
return 0;
}
-bool check_num(uint num_part)
+my_bool check_num(uint num_part)
{
uint part= num_part >> 22;
uint num= num_part & 0x3FFFFF;
@@ -543,7 +543,7 @@ void perform_insert(QUEUE *queue)
}
}
-bool perform_ins_del(QUEUE *queue, bool max_ind)
+my_bool perform_ins_del(QUEUE *queue, my_bool max_ind)
{
uint i= 0, no_loops= tot_no_loops, j= tot_no_parts;
do
@@ -571,10 +571,10 @@ bool perform_ins_del(QUEUE *queue, bool
return FALSE;
}
-bool do_test(uint no_parts, uint l_max_ind, bool l_fix_used)
+my_bool do_test(uint no_parts, uint l_max_ind, my_bool l_fix_used)
{
QUEUE queue;
- bool result;
+ my_bool result;
max_ind= l_max_ind;
fix_used= l_fix_used;
init_queue(&queue, no_parts, 0, max_ind, test_compare, NULL);
=== modified file 'sql/CMakeLists.txt'
--- a/sql/CMakeLists.txt 2010-09-02 22:34:48 +0000
+++ b/sql/CMakeLists.txt 2010-09-07 05:45:36 +0000
@@ -40,6 +40,7 @@ ENDIF()
SET (SQL_SOURCE
../sql-common/client.c derror.cc des_key_file.cc
discover.cc ../libmysql/errmsg.c field.cc field_conv.cc
+ bounded_queue.cc
filesort.cc gstream.cc sha2.cc
handler.cc hash_filo.h sql_plugin_services.h
hostname.cc init.cc item.cc item_buff.cc item_cmpfunc.cc
@@ -105,7 +106,8 @@ ADD_DEPENDENCIES(master GenError)
SET (SLAVE_SOURCE rpl_slave.cc rpl_reporting.cc rpl_mi.cc rpl_rli.cc)
ADD_LIBRARY(slave ${SLAVE_SOURCE})
ADD_DEPENDENCIES(slave GenError)
-ADD_LIBRARY(sqlgunitlib mdl.cc sql_list.cc sql_string.cc thr_malloc.cc)
+ADD_LIBRARY(sqlgunitlib
+ bounded_queue.cc mdl.cc sql_list.cc sql_string.cc thr_malloc.cc)
ADD_DEPENDENCIES(sqlgunitlib GenError)
=== modified file 'sql/Makefile.am'
--- a/sql/Makefile.am 2010-08-20 09:15:16 +0000
+++ b/sql/Makefile.am 2010-09-07 05:45:36 +0000
@@ -159,6 +159,7 @@ mysqld_SOURCES = sql_lex.cc sql_handler.
log.cc init.cc derror.cc sql_acl.cc \
unireg.cc des_key_file.cc \
discover.cc sql_time.cc opt_range.cc opt_sum.cc \
+ bounded_queue.cc \
records.cc filesort.cc handler.cc \
ha_partition.cc \
debug_sync.cc \
=== added file 'sql/bounded_queue.cc'
--- a/sql/bounded_queue.cc 1970-01-01 00:00:00 +0000
+++ b/sql/bounded_queue.cc 2010-09-07 05:45:36 +0000
@@ -0,0 +1,132 @@
+/* Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; version 2 of the License.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
+
+#include <string.h>
+#include "bounded_queue.h"
+#include "sql_const.h"
+#include "sql_sort.h"
+
+Bounded_queue::Bounded_queue()
+{
+ memset(&m_queue, 0, sizeof(m_queue));
+}
+
+
+Bounded_queue::~Bounded_queue()
+{
+ delete_queue(&m_queue);
+}
+
+
+int Bounded_queue::init(ha_rows max_elements, uint offset_to_key,
+ pbool max_at_top,
+ queue_compare compare, size_t compare_length,
+ keymaker_function keymaker, Sort_param *sort_param,
+ uchar **sort_keys)
+{
+ DBUG_ASSERT(sort_keys != NULL);
+
+ m_sort_keys= sort_keys;
+ m_compare_length= compare_length;
+ m_keymaker= keymaker;
+ m_sort_param= sort_param;
+ // init_queue() takes an uint, and also does (max_elements + 1)
+ if (max_elements >= (UINT_MAX - 1))
+ return 1;
+ // We allocate space for one extra element, for replace when queue is full.
+ return init_queue(&m_queue, (uint) max_elements + 1, offset_to_key, max_at_top,
+ compare, &m_compare_length);
+}
+
+
+void Bounded_queue::push(uchar *element)
+{
+ DBUG_ASSERT(is_initialized());
+ if (queue_is_full((&m_queue)))
+ {
+ uchar **pq_top= (uchar **) queue_top(&m_queue);
+ (*m_keymaker)(m_sort_param, *pq_top, element);
+ queue_replaced(&m_queue);
+ } else {
+ (*m_keymaker)(m_sort_param, m_sort_keys[m_queue.elements], element);
+ queue_insert(&m_queue, (uchar*)&m_sort_keys[m_queue.elements]);
+ }
+}
+
+
+uchar* Bounded_queue::pop()
+{
+ return queue_remove(&m_queue, 0);
+}
+
+
+double get_merge_many_buffs_cost_fast(ha_rows num_buffers, ha_rows max_n_elems,
+ ha_rows last_n_elems, uint elem_size)
+{
+ double total_cost;
+ const double MERGEBUFF_double= (double) MERGEBUFF;
+
+ /* Calc CPU cost of sorting each buffer */
+ total_cost= ( num_buffers * max_n_elems * log(1.0 + max_n_elems) +
+ last_n_elems * log(1.0 + last_n_elems) )
+ / TIME_FOR_COMPARE_ROWID;
+
+ /* Simulate behavior of merge_many_buff(). */
+ while (num_buffers >= MERGEBUFF2)
+ {
+ /* Calculate # of calls to merge_buffers() */
+ ha_rows loop_limit= num_buffers - MERGEBUFF*3/2;
+ ha_rows num_merge_calls= 1 + loop_limit/MERGEBUFF;
+ ha_rows i_end_value= num_merge_calls * MERGEBUFF;
+
+ /* Cost of merge sort 'num_merge_calls' */
+ total_cost+= num_merge_calls *
+ ( 2.0 * (max_n_elems * MERGEBUFF_double * elem_size) / IO_SIZE
+ + max_n_elems * MERGEBUFF_double * log(MERGEBUFF_double) /
+ (TIME_FOR_COMPARE_ROWID * M_LN2));
+
+ /* # of records in last buffer */
+ last_n_elems+= (num_buffers - i_end_value) * max_n_elems;
+
+ /* cost of merge sort of last buffer */
+ total_cost+= 2.0 * ((double)last_n_elems * elem_size) / IO_SIZE
+ + double(last_n_elems) * log(MERGEBUFF_double) /
+ (TIME_FOR_COMPARE_ROWID * M_LN2);
+
+ if (FALSE)
+ {
+ fprintf(stdout,
+ "total_cost %e num_buffers %llu max_n_elems %llu "
+ "loop_limit %llu num_merge_calls %llu i_end_value %llu\n",
+ total_cost, num_buffers, max_n_elems,
+ loop_limit, num_merge_calls, i_end_value);
+ fflush(stdout);
+ }
+ num_buffers= num_merge_calls;
+ max_n_elems*= MERGEBUFF;
+ }
+
+ /* Simulate final merge_buff call. */
+ last_n_elems+= max_n_elems*num_buffers;
+ total_cost+= 2.0 * ((double)last_n_elems * elem_size) / IO_SIZE
+ + double(last_n_elems) * log(num_buffers + 1.0) /
+ (TIME_FOR_COMPARE_ROWID * M_LN2);
+ if (FALSE)
+ fprintf(stdout, "total_cost %e num_buffers %llu max_n_elems %llu\n\n",
+ total_cost, num_buffers, max_n_elems);
+ return total_cost;
+}
+
+
=== added file 'sql/bounded_queue.h'
--- a/sql/bounded_queue.h 1970-01-01 00:00:00 +0000
+++ b/sql/bounded_queue.h 2010-09-07 05:45:36 +0000
@@ -0,0 +1,119 @@
+/* Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; version 2 of the License.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
+
+#ifndef BOUNDED_QUEUE_INCLUDED
+#define BOUNDED_QUEUE_INCLUDED
+
+#include "my_global.h"
+#include "my_base.h"
+#include "queues.h"
+
+class Sort_param;
+
+/**
+ Function for making sort-key from input data.
+ @param param Sort parameters.
+ @param to Where to put the key.
+ @param pos The input data.
+ */
+typedef void (*keymaker_function)(Sort_param *param, uchar *to, uchar *pos);
+
+/**
+ A priority queue with a fixed, limited size.
+
+ This is a wrapper on top of QUEUE and the queue_xxx() functions.
+ It keeps the top N elements which are inserted.
+ */
+class Bounded_queue
+{
+public:
+ Bounded_queue();
+ ~Bounded_queue();
+
+ /**
+ Initialize the queue.
+
+ @param max_elements The size of the queue.
+ @param offset_to_key Offset to key in elements stored in the queue.
+ @param max_at_top Set to 1 if you want biggest element on top.
+ @param compare Compare function for elements, takes 3 arguments.
+ @parem compare_length Lenght of the data used for sorting.
+ @param keymaker Function which generates keys for elements.
+ @param sort_param Sort parameters.
+ @param sort_keys Array of pointers to keys to sort.
+
+ @retval 0 OK, 1 Could not allocate memory.
+
+ We do *not* take ownership of any of the input pointer arguments.
+ */
+ int init(ha_rows max_elements, uint offset_to_key, pbool max_at_top,
+ queue_compare compare, size_t compare_length,
+ keymaker_function keymaker, Sort_param *sort_param,
+ uchar **sort_keys);
+
+ /**
+ Pushes an element on the queue.
+ If the queue is already full, we discard the smallest (or biggest) element.
+
+ @param element The element to be pushed.
+ */
+ void push(uchar *element);
+
+ /**
+ Removes an element from the queue.
+
+ @retval Pointer to the removed element.
+ */
+ uchar *pop();
+
+ /**
+ The number of elements in the queue.
+ */
+ uint num_elements() const { return m_queue.elements; }
+
+ /**
+ Is the queue initialized?
+ */
+ bool is_initialized() const { return m_queue.max_elements > 0; }
+
+private:
+ uchar **m_sort_keys;
+ size_t m_compare_length;
+ keymaker_function m_keymaker;
+ Sort_param *m_sort_param;
+ st_queue m_queue;
+};
+
+/*
+ Calculate cost of merge sort
+
+ @param num_buffers # of merge buffers
+ @param max_n_elems max # of keys in memory buffer
+ @param last_n_elems # of keys in last buffer
+ @param elem_size Size of each element.
+
+ Calculates cost of merge sort by simulating call to merge_many_buff().
+
+ @retval
+ computed cost of merge sort
+
+ @note
+ Declared here in order to be able to unit test it,
+ since library dependencies have not been sorted out yet.
+*/
+double get_merge_many_buffs_cost_fast(ha_rows num_buffers, ha_rows max_n_elems,
+ ha_rows last_n_elems, uint elem_size);
+
+#endif // BOUNDED_QUEUE_INCLUDED
=== modified file 'sql/filesort.cc'
--- a/sql/filesort.cc 2010-08-04 10:34:01 +0000
+++ b/sql/filesort.cc 2010-09-07 05:45:36 +0000
@@ -32,11 +32,23 @@
#include "probes_mysql.h"
#include "sql_test.h" // TEST_filesort
#include "opt_range.h" // SQL_SELECT
+#include "bounded_queue.h"
+#include "sql_select.h"
#ifndef THREAD
#define SKIP_DBUG_IN_FILESORT
#endif
+/*
+ How much Priority Queue sort is slower than qsort.
+ For qsort we have an average case complexity of O(n*log(n)) comparisons.
+ When using a priority queue, we have log(n) comparisons each time we
+ push a new element. For PQ we also call qsort at the end.
+ Assuming there is some extra overhead in QUEUE,
+ we set this constant to 3.0 (rather than 2.0)
+ */
+static double PQ_slowness= 3.0;
+
/// How to write record_ref.
#define WRITE_REF(file,from) \
if (my_b_write((file),(uchar*) (from),param->ref_length)) \
@@ -44,22 +56,24 @@ if (my_b_write((file),(uchar*) (from),pa
/* functions defined in this file */
-static char **make_char_array(char **old_pos, register uint fields,
- uint length, myf my_flag);
+static uchar **make_char_array(uchar **old_pos, register uint fields,
+ uint length);
static uchar *read_buffpek_from_file(IO_CACHE *buffer_file, uint count,
uchar *buf);
-static ha_rows find_all_keys(SORTPARAM *param,SQL_SELECT *select,
- uchar * *sort_keys, IO_CACHE *buffer_file,
- IO_CACHE *tempfile,IO_CACHE *indexfile);
-static int write_keys(SORTPARAM *param,uchar * *sort_keys,
- uint count, IO_CACHE *buffer_file, IO_CACHE *tempfile);
-static void make_sortkey(SORTPARAM *param,uchar *to, uchar *ref_pos);
-static void register_used_fields(SORTPARAM *param);
-static int merge_index(SORTPARAM *param,uchar *sort_buffer,
- BUFFPEK *buffpek,
- uint maxbuffer,IO_CACHE *tempfile,
- IO_CACHE *outfile);
-static bool save_index(SORTPARAM *param,uchar **sort_keys, uint count,
+static ha_rows find_all_keys(Sort_param *param,SQL_SELECT *select,
+ uchar **sort_keys, IO_CACHE *buffer_file,
+ IO_CACHE *tempfile,
+ Bounded_queue *pq,
+ ha_rows *found_rows);
+static int write_keys(Sort_param *param,uchar * *sort_keys,
+ uint count, IO_CACHE *buffer_file, IO_CACHE *tempfile);
+static void make_sortkey(Sort_param *param,uchar *to, uchar *ref_pos);
+static void register_used_fields(Sort_param *param);
+static int merge_index(Sort_param *param,uchar *sort_buffer,
+ BUFFPEK *buffpek,
+ uint maxbuffer,IO_CACHE *tempfile,
+ IO_CACHE *outfile);
+static bool save_index(Sort_param *param,uchar **sort_keys, uint count,
FILESORT_INFO *table_sort);
static uint suffix_length(ulong string_length);
static uint sortlength(THD *thd, SORT_FIELD *sortorder, uint s_length,
@@ -68,6 +82,98 @@ static SORT_ADDON_FIELD *get_addon_field
uint sortlength, uint *plength);
static void unpack_addon_fields(struct st_sort_addon_field *addon_field,
uchar *buff);
+static uchar **check_if_pq_applicable(Sort_param *param, FILESORT_INFO *info,
+ TABLE *table,
+ ha_rows records, ulong memavl);
+
+
+void Sort_param::init(uint sortlen, TABLE *table, THD *thd,
+ ha_rows maxrows, bool sort_positions)
+{
+ sort_length= sortlen;
+ ref_length= table->file->ref_length;
+ if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) &&
+ !table->fulltext_searched && !sort_positions)
+ {
+ /*
+ Get the descriptors of all fields whose values are appended
+ to sorted fields and get its total length in addon_length.
+ */
+ addon_field= get_addon_fields(thd, table->field, sort_length, &addon_length);
+ }
+ if (addon_field)
+ res_length= addon_length;
+ else
+ {
+ res_length= ref_length;
+ /*
+ The reference to the record is considered
+ as an additional sorted field
+ */
+ sort_length+= ref_length;
+ }
+ rec_length= sort_length + addon_length;
+ max_rows= maxrows;
+}
+
+
+static const char explain_with_pq[]= "; Using filesort(PQ)";
+static const char explain_without_pq[]= "; Using filesort";
+
+const char *explain_filesort(THD *thd, JOIN *join, TABLE *table)
+{
+ DBUG_ENTER("explain_filesort");
+ const ha_rows maxrows=
+ (join->group || join->tables > 1)
+ ? HA_POS_ERROR : join->unit->select_limit_cnt;
+ if (maxrows == HA_POS_ERROR)
+ {
+ DBUG_PRINT("info", ("explain PQ is not applicable, maxrows = HA_POS_ERROR"));
+ DBUG_RETURN(explain_without_pq);
+ }
+
+ if (table->s->tmp_table)
+ table->file->info(HA_STATUS_VARIABLE);
+
+ uint length= 0;
+ for (ORDER *ord= join->order; ord; ord= ord->next)
+ ++length;
+ if (!(join->sortorder=
+ make_unireg_sortorder(join->order, &length, join->sortorder)))
+ DBUG_RETURN(explain_without_pq);
+
+ bool multi_byte_charset;
+ const ha_rows num_rows= table->file->estimate_rows_upper_bound();
+ const ulong memavl= thd->variables.sortbuff_size;
+ Sort_param param;
+ DBUG_PRINT("info",("group %d "
+ "join->tables %d "
+ "join->select_limit %llu "
+ "join->unit->select_limit_cnt %llu",
+ join->group,
+ join->tables,
+ join->select_limit,
+ join->unit->select_limit_cnt));
+
+ param.init(sortlength(thd, join->sortorder, length, &multi_byte_charset),
+ table, thd, maxrows, FALSE);
+
+ FILESORT_INFO table_sort= table->sort;
+ uchar **sort_keys=
+ check_if_pq_applicable(¶m, &table_sort, table, num_rows, memavl);
+
+ if (sort_keys)
+ {
+ DBUG_PRINT("info", ("explain PQ is applicable"));
+ if (sort_keys != table_sort.sort_keys)
+ my_free(sort_keys);
+ DBUG_RETURN(explain_with_pq);
+ }
+ DBUG_PRINT("info", ("explain PQ is not applicable"));
+ DBUG_RETURN(explain_without_pq);
+}
+
+
/**
Sort a table.
Creates a set of pointers that can be used to read the rows
@@ -80,18 +186,17 @@ static void unpack_addon_fields(struct s
The result set is stored in table->io_cache or
table->record_pointers.
- @param thd Current thread
- @param table Table to sort
- @param sortorder How to sort the table
- @param s_length Number of elements in sortorder
- @param select condition to apply to the rows
- @param max_rows Return only this many rows
- @param sort_positions Set to 1 if we want to force sorting by position
- (Needed by UPDATE/INSERT or ALTER TABLE)
- @param examined_rows Store number of examined rows here
+ @param thd Current thread
+ @param table Table to sort
+ @param sortorder How to sort the table
+ @param s_length Number of elements in sortorder
+ @param select Condition to apply to the rows
+ @param max_rows Return only this many rows
+ @param sort_positions Set to TRUE if we want to force sorting by position
+ (Needed by UPDATE/INSERT or ALTER TABLE)
+ @param[out] examined_rows Store number of examined rows here
+ @param options 0 or OPTION_FOUND_ROWS
- @todo
- check why we do this (param.keys--)
@note
If we sort by position (like if sort_positions is 1) filesort() will
call table->prepare_for_position().
@@ -100,29 +205,30 @@ static void unpack_addon_fields(struct s
HA_POS_ERROR Error
@retval
\# Number of rows
- @retval
- examined_rows will be set to number of examined rows
*/
ha_rows filesort(THD *thd, TABLE *table, SORT_FIELD *sortorder, uint s_length,
SQL_SELECT *select, ha_rows max_rows,
- bool sort_positions, ha_rows *examined_rows)
+ bool sort_positions, ha_rows *examined_rows,
+ ulonglong options)
{
int error;
- ulong memavl, min_sort_memory;
+ ulong memavl;
uint maxbuffer;
BUFFPEK *buffpek;
- ha_rows records= HA_POS_ERROR;
- uchar **sort_keys= 0;
- IO_CACHE tempfile, buffpek_pointers, *selected_records_file, *outfile;
- SORTPARAM param;
+ ha_rows num_rows= HA_POS_ERROR;
+ uchar **sort_keys= NULL;
+ IO_CACHE tempfile, buffpek_pointers, *outfile;
+ Sort_param param;
bool multi_byte_charset;
+ ha_rows found_rows;
+ Bounded_queue pq;
+
DBUG_ENTER("filesort");
DBUG_EXECUTE("info",TEST_filesort(sortorder,s_length););
#ifdef SKIP_DBUG_IN_FILESORT
DBUG_PUSH(""); /* No DBUG here */
#endif
- FILESORT_INFO table_sort;
TABLE_LIST *tab= table->pos_in_table_list;
Item_subselect *subselect= tab ? tab->containing_subselect() : 0;
@@ -139,7 +245,7 @@ ha_rows filesort(THD *thd, TABLE *table,
QUICK_INDEX_MERGE_SELECT. Work with a copy and put it back at the end
when index_merge select has finished with it.
*/
- memcpy(&table_sort, &table->sort, sizeof(FILESORT_INFO));
+ FILESORT_INFO table_sort= table->sort;
table->sort.io_cache= NULL;
outfile= table_sort.io_cache;
@@ -147,117 +253,98 @@ ha_rows filesort(THD *thd, TABLE *table,
my_b_clear(&buffpek_pointers);
buffpek=0;
error= 1;
- bzero((char*) ¶m,sizeof(param));
- param.sort_length= sortlength(thd, sortorder, s_length, &multi_byte_charset);
+
+ param.init(sortlength(thd, sortorder, s_length, &multi_byte_charset),
+ table, thd, max_rows, sort_positions);
/* filesort cannot handle zero-length records. */
DBUG_ASSERT(param.sort_length);
- param.ref_length= table->file->ref_length;
- param.addon_field= 0;
- param.addon_length= 0;
- if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) &&
- !table->fulltext_searched && !sort_positions)
- {
- /*
- Get the descriptors of all fields whose values are appended
- to sorted fields and get its total length in param.spack_length.
- */
- param.addon_field= get_addon_fields(thd, table->field,
- param.sort_length,
- ¶m.addon_length);
- }
table_sort.addon_buf= 0;
table_sort.addon_length= param.addon_length;
table_sort.addon_field= param.addon_field;
table_sort.unpack= unpack_addon_fields;
- if (param.addon_field)
- {
- param.res_length= param.addon_length;
- if (!(table_sort.addon_buf= (uchar *) my_malloc(param.addon_length,
- MYF(MY_WME))))
+ if (param.addon_field &&
+ !(table_sort.addon_buf=
+ (uchar *) my_malloc(param.addon_length, MYF(MY_WME))))
goto err;
- }
- else
- {
- param.res_length= param.ref_length;
- /*
- The reference to the record is considered
- as an additional sorted field
- */
- param.sort_length+= param.ref_length;
- }
- param.rec_length= param.sort_length+param.addon_length;
- param.max_rows= max_rows;
if (select && select->quick)
- {
status_var_increment(thd->status_var.filesort_range_count);
- }
else
- {
status_var_increment(thd->status_var.filesort_scan_count);
- }
-#ifdef CAN_TRUST_RANGE
- if (select && select->quick && select->quick->records > 0L)
- {
- records=min((ha_rows) (select->quick->records*2+EXTRA_RECORDS*2),
- table->file->stats.records)+EXTRA_RECORDS;
- selected_records_file=0;
- }
- else
-#endif
- {
- records= table->file->estimate_rows_upper_bound();
- /*
- If number of records is not known, use as much of sort buffer
- as possible.
- */
- if (records == HA_POS_ERROR)
- records--; // we use 'records+1' below.
- selected_records_file= 0;
- }
+
+ /*
+ If number of rows is not known, use as much of sort buffer as possible.
+ */
+ num_rows= table->file->estimate_rows_upper_bound();
if (multi_byte_charset &&
!(param.tmp_buffer= (char*) my_malloc(param.sort_length,MYF(MY_WME))))
goto err;
memavl= thd->variables.sortbuff_size;
- min_sort_memory= max(MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2);
- while (memavl >= min_sort_memory)
- {
- ulong old_memavl;
- ulong keys= memavl/(param.rec_length+sizeof(char*));
- param.keys=(uint) min(records+1, keys);
- if ((table_sort.sort_keys=
- (uchar **) make_char_array((char **) table_sort.sort_keys,
- param.keys, param.rec_length, MYF(0))))
- break;
- old_memavl=memavl;
- if ((memavl=memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
- memavl= min_sort_memory;
+
+ table_sort.sort_keys=
+ check_if_pq_applicable(¶m, &table_sort, table, num_rows, memavl);
+ if (table_sort.sort_keys)
+ {
+ DBUG_PRINT("info", ("filesort PQ is applicable"));
+ const size_t compare_length= param.sort_length;
+ if (pq.init(param.max_rows, 0, 1,
+ (queue_compare) (get_ptr_compare(compare_length)),
+ compare_length,
+ &make_sortkey, ¶m, table_sort.sort_keys))
+ {
+ // If failed to init pq, fall back to merge-sort.
+ my_free(table_sort.sort_keys);
+ table_sort.sort_keys= NULL;
+ }
}
- sort_keys= table_sort.sort_keys;
- if (memavl < min_sort_memory)
+ else
+ DBUG_PRINT("info", ("filesort PQ is not applicable"));
+
+ if (!table_sort.sort_keys)
{
- my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR+ME_WAITTANG));
- goto err;
+ const ulong min_sort_memory=
+ max(MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2);
+ while (memavl >= min_sort_memory)
+ {
+ ulong old_memavl;
+ ulong keys= memavl/(param.rec_length+sizeof(char*));
+ param.num_keys_per_buffer= (uint) min(num_rows, keys);
+ if ((table_sort.sort_keys=
+ make_char_array(table_sort.sort_keys,
+ param.num_keys_per_buffer, param.rec_length)))
+ break;
+ old_memavl=memavl;
+ if ((memavl=memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
+ memavl= min_sort_memory;
+ }
+ if (memavl < min_sort_memory)
+ {
+ my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR+ME_WAITTANG));
+ goto err;
+ }
}
+
+ sort_keys= table_sort.sort_keys;
if (open_cached_file(&buffpek_pointers,mysql_tmpdir,TEMP_PREFIX,
DISK_BUFFER_SIZE, MYF(MY_WME)))
goto err;
- param.keys--; /* TODO: check why we do this */
param.sort_form= table;
param.end=(param.local_sortorder=sortorder)+s_length;
- if ((records=find_all_keys(¶m,select,sort_keys, &buffpek_pointers,
- &tempfile, selected_records_file)) ==
+ if ((num_rows= find_all_keys(¶m, select, sort_keys, &buffpek_pointers,
+ &tempfile,
+ pq.is_initialized() ? &pq : NULL,
+ &found_rows)) ==
HA_POS_ERROR)
goto err;
maxbuffer= (uint) (my_b_tell(&buffpek_pointers)/sizeof(*buffpek));
if (maxbuffer == 0) // The whole set is in memory
{
- if (save_index(¶m,sort_keys,(uint) records, &table_sort))
+ if (save_index(¶m, sort_keys, (uint) num_rows, &table_sort))
goto err;
}
else
@@ -286,8 +373,9 @@ ha_rows filesort(THD *thd, TABLE *table,
Use also the space previously used by string pointers in sort_buffer
for temporary key storage.
*/
- param.keys=((param.keys*(param.rec_length+sizeof(char*))) /
- param.rec_length-1);
+ param.num_keys_per_buffer=((param.num_keys_per_buffer *
+ (param.rec_length + sizeof(char*))) /
+ param.rec_length - 1);
maxbuffer--; // Offset from 0
if (merge_many_buff(¶m,(uchar*) sort_keys,buffpek,&maxbuffer,
&tempfile))
@@ -299,9 +387,17 @@ ha_rows filesort(THD *thd, TABLE *table,
outfile))
goto err;
}
- if (records > param.max_rows)
- records=param.max_rows;
- error =0;
+
+ if (pq.is_initialized() && (options & OPTION_FOUND_ROWS))
+ {
+ DBUG_PRINT("info", ("PQ and OPTION_FOUND_ROWS !!"));
+ }
+
+ if (options & OPTION_FOUND_ROWS)
+ num_rows= found_rows;
+ else if (num_rows > param.max_rows)
+ num_rows= param.max_rows;
+ error= 0;
err:
my_free(param.tmp_buffer);
@@ -332,15 +428,16 @@ ha_rows filesort(THD *thd, TABLE *table,
MYF(ME_ERROR+ME_WAITTANG));
else
statistic_add(thd->status_var.filesort_rows,
- (ulong) records, &LOCK_status);
+ (ulong) num_rows, &LOCK_status);
*examined_rows= param.examined_rows;
#ifdef SKIP_DBUG_IN_FILESORT
DBUG_POP(); /* Ok to DBUG */
#endif
- memcpy(&table->sort, &table_sort, sizeof(FILESORT_INFO));
- DBUG_PRINT("exit",("records: %ld", (long) records));
- MYSQL_FILESORT_DONE(error, records);
- DBUG_RETURN(error ? HA_POS_ERROR : records);
+ table->sort= table_sort;
+ DBUG_PRINT("exit",("num_rows: %ld examined_rows: %ld",
+ (long) num_rows, (long) *examined_rows));
+ MYSQL_FILESORT_DONE(error, num_rows);
+ DBUG_RETURN(error ? HA_POS_ERROR : num_rows);
} /* filesort */
@@ -366,23 +463,23 @@ void filesort_free_buffers(TABLE *table,
/** Make a array of string pointers. */
-static char **make_char_array(char **old_pos, register uint fields,
- uint length, myf my_flag)
+static uchar **make_char_array(uchar **old_pos, register uint fields,
+ uint length)
{
- register char **pos;
- char *char_pos;
DBUG_ENTER("make_char_array");
if (old_pos ||
- (old_pos= (char**) my_malloc((uint) fields*(length+sizeof(char*)),
- my_flag)))
+ (old_pos=
+ (uchar**) my_malloc((uint) fields * (length + sizeof(char*)), MYF(0))))
{
- pos=old_pos; char_pos=((char*) (pos+fields)) -length;
- while (fields--) *(pos++) = (char_pos+= length);
+ uchar **pos= old_pos;
+ uchar *char_pos= ((uchar*) (pos+fields)) - length;
+ while (fields--)
+ *(pos++) = (char_pos+= length);
}
DBUG_RETURN(old_pos);
-} /* make_char_array */
+}
/** Read 'count' number of buffer pointers into memory. */
@@ -470,20 +567,26 @@ static void dbug_print_record(TABLE *tab
@param buffpek_pointers File to write BUFFPEKs describing sorted segments
in tempfile.
@param tempfile File to write sorted sequences of sortkeys to.
- @param indexfile If !NULL, use it for source data (contains rowids)
+ @param pq If !NULL, use it for keeping top N elements
+ @param [out] found_rows The number of FOUND_ROWS().
@note
Basic idea:
@verbatim
while (get_next_sortkey())
{
- if (no free space in sort_keys buffers)
+ if (using priority queue)
+ push sort key into queue
+ else
{
- sort sort_keys buffer;
- dump sorted sequence to 'tempfile';
- dump BUFFPEK describing sequence location into 'buffpek_pointers';
+ if (no free space in sort_keys buffers)
+ {
+ sort sort_keys buffer;
+ dump sorted sequence to 'tempfile';
+ dump BUFFPEK describing sequence location into 'buffpek_pointers';
+ }
+ put sort key into 'sort_keys';
}
- put sort key into 'sort_keys';
}
if (sort_keys has some elements && dumped at least once)
sort-dump-dump as above;
@@ -497,10 +600,12 @@ static void dbug_print_record(TABLE *tab
HA_POS_ERROR on error.
*/
-static ha_rows find_all_keys(SORTPARAM *param, SQL_SELECT *select,
- uchar **sort_keys,
- IO_CACHE *buffpek_pointers,
- IO_CACHE *tempfile, IO_CACHE *indexfile)
+static ha_rows find_all_keys(Sort_param *param, SQL_SELECT *select,
+ uchar **sort_keys,
+ IO_CACHE *buffpek_pointers,
+ IO_CACHE *tempfile,
+ Bounded_queue *pq,
+ ha_rows *found_rows)
{
int error,flag,quick_select;
uint idx,indexpos,ref_length;
@@ -512,11 +617,12 @@ static ha_rows find_all_keys(SORTPARAM *
handler *file;
MY_BITMAP *save_read_set, *save_write_set;
bool skip_record;
+
DBUG_ENTER("find_all_keys");
DBUG_PRINT("info",("using: %s",
(select ? select->quick ? "ranges" : "where":
"every row")));
-
+
idx=indexpos=0;
error=quick_select=0;
sort_form=param->sort_form;
@@ -525,12 +631,12 @@ static ha_rows find_all_keys(SORTPARAM *
ref_pos= ref_buff;
quick_select=select && select->quick;
record=0;
- flag= ((!indexfile && file->ha_table_flags() & HA_REC_NOT_IN_SEQ)
- || quick_select);
- if (indexfile || flag)
+ *found_rows= 0;
+ flag= ((file->ha_table_flags() & HA_REC_NOT_IN_SEQ) || quick_select);
+ if (flag)
ref_pos= &file->ref[0];
next_pos=ref_pos;
- if (! indexfile && ! quick_select)
+ if (!quick_select)
{
next_pos=(uchar*) 0; /* Find records in sequence */
file->ha_rnd_init(1);
@@ -577,16 +683,6 @@ static ha_rows find_all_keys(SORTPARAM *
}
else /* Not quick-select */
{
- if (indexfile)
- {
- if (my_b_read(indexfile,(uchar*) ref_pos,ref_length)) /* purecov: deadcode */
- {
- error= my_errno ? my_errno : -1; /* Abort */
- break;
- }
- error= file->ha_rnd_pos(sort_form->record[0], next_pos);
- }
- else
{
error= file->ha_rnd_next(sort_form->record[0]);
if (!flag)
@@ -604,7 +700,7 @@ static ha_rows find_all_keys(SORTPARAM *
if (*killed)
{
DBUG_PRINT("info",("Sort killed by user"));
- if (!indexfile && !quick_select)
+ if (!quick_select)
{
(void) file->extra(HA_EXTRA_NO_CACHE);
file->ha_rnd_end();
@@ -616,14 +712,23 @@ static ha_rows find_all_keys(SORTPARAM *
if (!error && (!select ||
(!select->skip_record(thd, &skip_record) && !skip_record)))
{
- if (idx == param->keys)
+ ++(*found_rows);
+ if (pq)
{
- if (write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
- DBUG_RETURN(HA_POS_ERROR);
- idx=0;
- indexpos++;
+ pq->push(ref_pos);
+ idx= pq->num_elements();
+ }
+ else
+ {
+ if (idx == param->num_keys_per_buffer)
+ {
+ if (write_keys(param,sort_keys, idx, buffpek_pointers, tempfile))
+ DBUG_RETURN(HA_POS_ERROR);
+ idx= 0;
+ indexpos++;
+ }
+ make_sortkey(param, sort_keys[idx++], ref_pos);
}
- make_sortkey(param,sort_keys[idx++],ref_pos);
}
else
file->unlock_row();
@@ -653,9 +758,11 @@ static ha_rows find_all_keys(SORTPARAM *
if (indexpos && idx &&
write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
DBUG_RETURN(HA_POS_ERROR); /* purecov: inspected */
- DBUG_RETURN(my_b_inited(tempfile) ?
- (ha_rows) (my_b_tell(tempfile)/param->rec_length) :
- idx);
+ const ha_rows retval=
+ my_b_inited(tempfile) ?
+ (ha_rows) (my_b_tell(tempfile)/param->rec_length) : idx;
+ DBUG_PRINT("info", ("find_all_keys return %u", (uint) retval));
+ DBUG_RETURN(retval);
} /* find_all_keys */
@@ -682,7 +789,7 @@ static ha_rows find_all_keys(SORTPARAM *
*/
static int
-write_keys(SORTPARAM *param, register uchar **sort_keys, uint count,
+write_keys(Sort_param *param, register uchar **sort_keys, uint count,
IO_CACHE *buffpek_pointers, IO_CACHE *tempfile)
{
size_t sort_length, rec_length;
@@ -745,8 +852,8 @@ static inline void store_length(uchar *t
/** Make a sort-key from record. */
-static void make_sortkey(register SORTPARAM *param,
- register uchar *to, uchar *ref_pos)
+static void make_sortkey(register Sort_param *param,
+ register uchar *to, uchar *ref_pos)
{
reg3 Field *field;
reg1 SORT_FIELD *sort_field;
@@ -998,7 +1105,7 @@ static void make_sortkey(register SORTPA
Register fields used by sorting in the sorted table's read set
*/
-static void register_used_fields(SORTPARAM *param)
+static void register_used_fields(Sort_param *param)
{
reg1 SORT_FIELD *sort_field;
TABLE *table=param->sort_form;
@@ -1036,17 +1143,17 @@ static void register_used_fields(SORTPAR
}
-static bool save_index(SORTPARAM *param, uchar **sort_keys, uint count,
+static bool save_index(Sort_param *param, uchar **sort_keys, uint count,
FILESORT_INFO *table_sort)
{
uint offset,res_length;
uchar *to;
DBUG_ENTER("save_index");
- my_string_ptr_sort((uchar*) sort_keys, (uint) count, param->sort_length);
+ my_string_ptr_sort((uchar*) sort_keys, count, param->sort_length);
res_length= param->res_length;
offset= param->rec_length-res_length;
- if ((ha_rows) count > param->max_rows)
+ if ((ha_rows) count > param->max_rows && param->max_rows > 0)
count=(uint) param->max_rows;
if (!(to= table_sort->record_pointers=
(uchar*) my_malloc(res_length*count, MYF(MY_WME))))
@@ -1060,10 +1167,131 @@ static bool save_index(SORTPARAM *param,
}
+/**
+ Test whether priority queue is worth using to get top elements of an
+ ordered result set. If it is then allocates buffer for required amount of
+ records
+
+ @param param Sort parameters.
+ @param info Filesort information.
+ @param table Table to sort.
+ @param num_rows Estimate of number of rows in source record set.
+ @param memavl Memory available for sorting.
+
+ DESCRIPTION
+ Function tests applicability of PQ to get L top records for queries like
+ SELECT ... FROM t ORDER BY a1,...,an LIMIT max_rows;
+ It tests whether there is enough memory to contain max_rows elements,
+ whether max_rows is small enough to make PQ perform faster that qsort
+ on table containing 'num_rows' records. If available memory is enough to
+ store only 'max_rows' sort keys without addon data, it modifies 'table'
+ to sort with references to tuples instead of additional data. In evaluations
+ it uses 'param' to get sort key, addon data and reference sizes, 'table' -
+ to get table scan time.
+
+ @retval
+ allocated buffer - if it's ok to use PQ
+ NULL - PQ will be slower than merge-sort, or there is not enough memory.
+*/
+
+uchar **check_if_pq_applicable(Sort_param *param, FILESORT_INFO *info,
+ TABLE *table, ha_rows num_rows, ulong memavl)
+{
+ DBUG_ENTER("check_if_pq_applicable");
+
+ if (param->max_rows == HA_POS_ERROR)
+ {
+ DBUG_PRINT("info", ("max_rows = HA_POS_ERROR"));
+ DBUG_RETURN(NULL);
+ }
+
+ if (param->max_rows + 2 >= UINT_MAX)
+ {
+ DBUG_PRINT("info", ("Too large LIMIT"));
+ DBUG_RETURN(NULL);
+ }
+
+ uchar **sort_keys;
+ ulong num_available_keys= memavl/(param->rec_length + sizeof(char*));
+ param->num_keys_per_buffer= (uint) param->max_rows + 1;
+ if (num_rows < num_available_keys)
+ {
+ /* The whole source set fits into memory. */
+ if (param->max_rows < num_rows/PQ_slowness )
+ {
+ if ((sort_keys= make_char_array(info->sort_keys,
+ param->num_keys_per_buffer,
+ param->rec_length)))
+ DBUG_RETURN(sort_keys);
+ }
+ else
+ {
+ /* PQ will be slower */
+ DBUG_RETURN(NULL);
+ }
+ }
+
+ if (param->max_rows + 1 < num_available_keys &&
+ (sort_keys= make_char_array(info->sort_keys,
+ param->num_keys_per_buffer,
+ param->rec_length)))
+ DBUG_RETURN(sort_keys);
+
+ /* Try to strip off addon fields */
+ if (param->addon_field)
+ {
+ const ulong row_lenght=
+ param->sort_length + param->ref_length + sizeof(char*);
+ num_available_keys= memavl / row_lenght;
+
+ if (param->max_rows + 1 < num_available_keys)
+ {
+ const double merge_cost=
+ get_merge_many_buffs_cost_fast(num_rows / num_available_keys,
+ num_available_keys,
+ num_rows % num_available_keys,
+ row_lenght);
+ const double pq_cost=
+ (PQ_slowness * num_rows + param->max_rows + 1)*
+ log(param->max_rows + 1.0) / TIME_FOR_COMPARE_ROWID +
+ param->max_rows * table->file->scan_time();
+
+ fprintf(stdout, "check_if_pq_applicable merge_cost %e pq_cost %e\n",
+ merge_cost, pq_cost);
+ fflush(stdout);
+
+ if (merge_cost < pq_cost)
+ DBUG_RETURN(NULL);
+
+ sort_keys= make_char_array(info->sort_keys,
+ param->num_keys_per_buffer,
+ param->rec_length);
+ if (sort_keys)
+ {
+ // Make attached data to be references instead of fields.
+ my_free(info->addon_buf);
+ my_free(info->addon_field);
+ info->addon_buf= NULL;
+ info->addon_field= 0;
+ param->addon_field= NULL;
+ param->addon_length= 0;
+
+ param->res_length= param->ref_length;
+ param->sort_length+= param->ref_length;
+ param->rec_length= param->sort_length + param->addon_length;
+
+ DBUG_RETURN(sort_keys);
+ }
+ }
+ }
+ DBUG_RETURN(NULL);
+}
+
+
/** Merge buffers to make < MERGEBUFF2 buffers. */
-int merge_many_buff(SORTPARAM *param, uchar *sort_buffer,
- BUFFPEK *buffpek, uint *maxbuffer, IO_CACHE *t_file)
+int merge_many_buff(Sort_param *param, uchar *sort_buffer,
+ BUFFPEK *buffpek, uint *maxbuffer, IO_CACHE *t_file)
{
register uint i;
IO_CACHE t_file2,*from_file,*to_file,*temp;
@@ -1192,7 +1420,7 @@ void reuse_freed_buff(QUEUE *queue, BUFF
other error
*/
-int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
+int merge_buffers(Sort_param *param, IO_CACHE *from_file,
IO_CACHE *to_file, uchar *sort_buffer,
BUFFPEK *lastbuff, BUFFPEK *Fb, BUFFPEK *Tb,
int flag)
@@ -1224,7 +1452,7 @@ int merge_buffers(SORTPARAM *param, IO_C
res_length= param->res_length;
sort_length= param->sort_length;
offset= rec_length-res_length;
- maxcount= (ulong) (param->keys/((uint) (Tb-Fb) +1));
+ maxcount= (ulong) (param->num_keys_per_buffer / ((uint) (Tb-Fb) +1));
to_start_filepos= my_b_tell(to_file);
strpos= (uchar*) sort_buffer;
org_max_rows=max_rows= param->max_rows;
@@ -1249,8 +1477,7 @@ int merge_buffers(SORTPARAM *param, IO_C
{
buffpek->base= strpos;
buffpek->max_keys= maxcount;
- strpos+= (uint) (error= (int) read_to_buffer(from_file, buffpek,
- rec_length));
+ strpos+= (uint) (error= (int)read_to_buffer(from_file, buffpek, rec_length));
if (error == -1)
goto err; /* purecov: inspected */
buffpek->max_keys= buffpek->mem_count; // If less data in buffers than expected
@@ -1340,7 +1567,7 @@ int merge_buffers(SORTPARAM *param, IO_C
}
buffpek= (BUFFPEK*) queue_top(&queue);
buffpek->base= sort_buffer;
- buffpek->max_keys= param->keys;
+ buffpek->max_keys= param->num_keys_per_buffer;
/*
As we know all entries in the buffer are unique, we only have to
@@ -1400,9 +1627,9 @@ err:
/* Do a merge to output-file (save only positions) */
-static int merge_index(SORTPARAM *param, uchar *sort_buffer,
- BUFFPEK *buffpek, uint maxbuffer,
- IO_CACHE *tempfile, IO_CACHE *outfile)
+static int merge_index(Sort_param *param, uchar *sort_buffer,
+ BUFFPEK *buffpek, uint maxbuffer,
+ IO_CACHE *tempfile, IO_CACHE *outfile)
{
DBUG_ENTER("merge_index");
if (merge_buffers(param,tempfile,outfile,sort_buffer,buffpek,buffpek,
=== modified file 'sql/filesort.h'
--- a/sql/filesort.h 2010-07-02 02:58:51 +0000
+++ b/sql/filesort.h 2010-09-07 05:45:36 +0000
@@ -21,6 +21,7 @@ class SQL_SELECT;
#include "my_global.h" /* uint, uchar */
#include "my_base.h" /* ha_rows */
+class JOIN;
class SQL_SELECT;
class THD;
struct TABLE;
@@ -29,7 +30,26 @@ typedef struct st_sort_field SORT_FIELD;
ha_rows filesort(THD *thd, TABLE *table, st_sort_field *sortorder,
uint s_length, SQL_SELECT *select,
ha_rows max_rows, bool sort_positions,
- ha_rows *examined_rows);
+ ha_rows *examined_rows, ulonglong options);
+/**
+ Provides an appropriate EXPLAIN text for filesort().
+
+ @param thd Thread handle.
+ @param join Join handle.
+ @param table Table to sort.
+
+ @retval "; Using filesort" or "; Using filesort(PQ)"
+
+ Performs the same cost analysis as filesort() in order to determine
+ whether priority queue (PQ) is appliccable for the sort or not.
+
+ @note
+ Some joins are actually simplified during execution, @sa make_simple_join()
+ and may thus be sorted using a PQ. This will not be shown in the explain text.
+ */
+const char *explain_filesort(THD *thd, JOIN *join, TABLE *table);
+
+
void filesort_free_buffers(TABLE *table, bool full);
void change_double_for_sort(double nr,uchar *to);
=== modified file 'sql/sql_const.h'
--- a/sql/sql_const.h 2010-07-13 17:29:44 +0000
+++ b/sql/sql_const.h 2010-09-07 05:45:36 +0000
@@ -161,13 +161,13 @@
instead of reading with keys. The number says how many evaluation of the
WHERE clause is comparable to reading one extra row from a table.
*/
-#define TIME_FOR_COMPARE 5 // 5 compares == one read
+#define TIME_FOR_COMPARE 5.0 // 5 compares == one read
/**
Number of comparisons of table rowids equivalent to reading one row from a
table.
*/
-#define TIME_FOR_COMPARE_ROWID (TIME_FOR_COMPARE*2)
+#define TIME_FOR_COMPARE_ROWID (TIME_FOR_COMPARE*2.0)
/*
For sequential disk seeks the cost formula is:
=== modified file 'sql/sql_delete.cc'
--- a/sql/sql_delete.cc 2010-08-12 00:26:10 +0000
+++ b/sql/sql_delete.cc 2010-09-07 05:45:36 +0000
@@ -243,7 +243,7 @@ bool mysql_delete(THD *thd, TABLE_LIST *
if (!(sortorder= make_unireg_sortorder(order, &length, NULL)) ||
(table->sort.found_records = filesort(thd, table, sortorder, length,
select, HA_POS_ERROR, 1,
- &examined_rows))
+ &examined_rows, 0))
== HA_POS_ERROR)
{
delete select;
=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc 2010-09-22 11:37:38 +0000
+++ b/sql/sql_select.cc 2010-09-07 05:45:36 +0000
@@ -2462,7 +2462,10 @@ JOIN::optimize()
if (select_options & SELECT_DESCRIBE)
{
error= 0;
- DBUG_RETURN(0);
+ // We need get_tmp_table_field() to return NON-NIL
+ // when explain_filesort() does make_unireg_sortorder()
+ // so we need to create the tmp table below.
+ // DBUG_RETURN(0);
}
having= 0;
@@ -2560,6 +2563,7 @@ JOIN::optimize()
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
{
+ DBUG_PRINT("info",("Sorting for order"));
thd_proc_info(thd, "Sorting for order");
if (create_sort_index(thd, this, order,
HA_POS_ERROR, HA_POS_ERROR, TRUE))
@@ -2737,6 +2741,8 @@ JOIN::exec()
int tmp_error;
DBUG_ENTER("JOIN::exec");
+ const bool has_group_by= this->group;
+
thd_proc_info(thd, "executing");
error= 0;
if (procedure)
@@ -3022,11 +3028,12 @@ JOIN::exec()
}
if (curr_join->group_list)
{
- thd_proc_info(thd, "Creating sort index");
if (curr_join->join_tab == join_tab && save_join_tab())
{
DBUG_VOID_RETURN;
}
+ DBUG_PRINT("info",("Sorting for index"));
+ thd_proc_info(thd, "Creating sort index");
if (create_sort_index(thd, curr_join, curr_join->group_list,
HA_POS_ERROR, HA_POS_ERROR, FALSE) ||
make_group_fields(this, curr_join))
@@ -3252,12 +3259,29 @@ JOIN::exec()
the query. XXX: it's never shown in EXPLAIN!
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
*/
- if (create_sort_index(thd, curr_join,
- curr_join->group_list ?
- curr_join->group_list : curr_join->order,
- curr_join->select_limit,
- (select_options & OPTION_FOUND_ROWS ?
- HA_POS_ERROR : unit->select_limit_cnt),
+ DBUG_PRINT("info",("Sorting for order by/group by"));
+ DBUG_PRINT("info",("has_group_by %d "
+ "curr_join->tables %d "
+ "curr_join->select_limit %llu "
+ "unit->select_limit_cnt %llu",
+ has_group_by,
+ curr_join->tables,
+ curr_join->select_limit,
+ unit->select_limit_cnt));
+ ORDER *order_arg=
+ curr_join->group_list ? curr_join->group_list : curr_join->order;
+ const ha_rows filesort_limit_arg=
+ (has_group_by || curr_join->tables > 1)
+ ? curr_join->select_limit : unit->select_limit_cnt;
+ const ha_rows select_limit_arg=
+ select_options & OPTION_FOUND_ROWS
+ ? HA_POS_ERROR : unit->select_limit_cnt;
+
+ if (create_sort_index(thd,
+ curr_join,
+ order_arg,
+ filesort_limit_arg,
+ select_limit_arg,
curr_join->group_list ? FALSE : TRUE))
DBUG_VOID_RETURN;
sortorder= curr_join->sortorder;
@@ -3290,6 +3314,15 @@ JOIN::exec()
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
error= do_select(curr_join, curr_fields_list, NULL, procedure);
thd->limit_found_rows= curr_join->send_records;
+ if (curr_join->order &&
+ curr_join->sortorder &&
+ curr_join->select_options & OPTION_FOUND_ROWS)
+ {
+ /* Use info provided by filesort. */
+ DBUG_ASSERT(curr_join->tables > curr_join->const_tables);
+ JOIN_TAB *tab= curr_join->join_tab + curr_join->const_tables;
+ thd->limit_found_rows= tab->records;
+ }
/* Accumulate the counts from all join iterations of all join parts. */
thd->examined_row_count+= curr_join->examined_rows;
@@ -5837,7 +5870,6 @@ add_key_part(DYNAMIC_ARRAY *keyuse_array
{
Field *field=key_field->field;
TABLE *form= field->table;
- KEYUSE keyuse;
if (key_field->eq_func && !(key_field->optimize & KEY_OPTIMIZE_EXISTS))
{
@@ -5853,20 +5885,21 @@ add_key_part(DYNAMIC_ARRAY *keyuse_array
{
if (field->eq(form->key_info[key].key_part[part].field))
{
- keyuse.table= field->table;
- keyuse.val = key_field->val;
- keyuse.key = key;
- keyuse.keypart=part;
- keyuse.keypart_map= (key_part_map) 1 << part;
- keyuse.used_tables=key_field->val->used_tables();
- keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL;
- keyuse.null_rejecting= key_field->null_rejecting;
- keyuse.cond_guard= key_field->cond_guard;
- keyuse.sj_pred_no= key_field->sj_pred_no;
- if (insert_dynamic(keyuse_array,(uchar*) &keyuse))
- return TRUE;
+ KEYUSE keyuse;
+ keyuse.table= field->table;
+ keyuse.val= key_field->val;
+ keyuse.used_tables= key_field->val->used_tables();
+ keyuse.key= key;
+ keyuse.keypart= part;
+ keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL;
+ keyuse.keypart_map= (key_part_map) 1 << part;
/* This will be set accordingly in optimize_keyuse */
keyuse.ref_table_rows= ~(ha_rows) 0;
+ keyuse.null_rejecting= key_field->null_rejecting;
+ keyuse.cond_guard= key_field->cond_guard;
+ keyuse.sj_pred_no= key_field->sj_pred_no;
+ if (insert_dynamic(keyuse_array,(uchar*) &keyuse))
+ return TRUE;
}
}
}
@@ -18270,8 +18303,26 @@ end_send(JOIN *join, JOIN_TAB *join_tab
error=join->result->send_data(*join->fields);
if (error)
DBUG_RETURN(NESTED_LOOP_ERROR); /* purecov: inspected */
- if (++join->send_records >= join->unit->select_limit_cnt &&
- join->do_send_rows)
+
+ ++join->send_records;
+ if (join->send_records >= join->unit->select_limit_cnt &&
+ !join->do_send_rows)
+ {
+ /*
+ If filesort is used for sorting, stop after select_limit_cnt+1
+ records are read. Because of optimization in some cases it can
+ provide only select_limit_cnt+1 records.
+ */
+ if (join->order &&
+ join->sortorder &&
+ join->select_options & OPTION_FOUND_ROWS)
+ {
+ DBUG_PRINT("info", ("filesort NESTED_LOOP_QUERY_LIMIT"));
+ DBUG_RETURN(NESTED_LOOP_QUERY_LIMIT);
+ }
+ }
+ if (join->send_records >= join->unit->select_limit_cnt &&
+ join->do_send_rows)
{
if (join->select_options & OPTION_FOUND_ROWS)
{
@@ -19883,7 +19934,7 @@ use_filesort:
SYNOPSIS
create_sort_index()
thd Thread handler
- tab Table to sort (in join structure)
+ join The join
order How table should be sorted
filesort_limit Max number of rows that needs to be sorted
select_limit Max number of rows in final output
@@ -19985,9 +20036,11 @@ create_sort_index(THD *thd, JOIN *join,
if (table->s->tmp_table)
table->file->info(HA_STATUS_VARIABLE); // Get record count
- table->sort.found_records=filesort(thd, table,join->sortorder, length,
- select, filesort_limit, 0,
- &examined_rows);
+ table->sort.found_records= filesort(thd, table,join->sortorder, length,
+ select, filesort_limit, 0,
+ &examined_rows,
+ join->tables != 1 ? 0 :
+ join->select_options & OPTION_FOUND_ROWS);
tab->records= table->sort.found_records; // For SQL_CALC_ROWS
if (select)
{
@@ -20334,7 +20387,7 @@ SORT_FIELD *make_unireg_sortorder(ORDER
pos= sort= sortorder;
if (!pos)
- return 0;
+ DBUG_RETURN(0);
for (;order;order=order->next,pos++)
{
@@ -20351,6 +20404,7 @@ SORT_FIELD *make_unireg_sortorder(ORDER
else
pos->item= *order->item;
pos->reverse=! order->asc;
+ DBUG_ASSERT(pos->field != NULL || pos->item != NULL);
}
*length=count;
DBUG_RETURN(sort);
@@ -22703,7 +22757,7 @@ void select_describe(JOIN *join, bool ne
if (need_order)
{
need_order=0;
- extra.append(STRING_WITH_LEN("; Using filesort"));
+ extra.append(explain_filesort(thd, join, table));
}
if (distinct & test_all_bits(used_tables,thd->used_tables))
extra.append(STRING_WITH_LEN("; Distinct"));
=== modified file 'sql/sql_sort.h'
--- a/sql/sql_sort.h 2010-07-02 18:15:21 +0000
+++ b/sql/sql_sort.h 2010-09-07 05:45:36 +0000
@@ -26,7 +26,7 @@ typedef struct st_sort_field SORT_FIELD;
class Field;
struct TABLE;
-
+class THD;
/* Defines used by filesort and uniques */
@@ -71,15 +71,17 @@ struct BUFFPEK_COMPARE_CONTEXT
void *key_compare_arg;
};
-typedef struct st_sort_param {
- uint rec_length; /* Length of sorted records */
- uint sort_length; /* Length of sorted columns */
- uint ref_length; /* Length of record ref. */
- uint addon_length; /* Length of added packed fields */
- uint res_length; /* Length of records in final sorted file/buffer */
- uint keys; /* Max keys / buffer */
- ha_rows max_rows,examined_rows;
- TABLE *sort_form; /* For quicker make_sortkey */
+class Sort_param {
+public:
+ uint rec_length; /* Length of sorted records */
+ uint sort_length; /* Length of sorted columns */
+ uint ref_length; /* Length of record ref. */
+ uint addon_length; /* Length of added packed fields */
+ uint res_length; /* Length of records in final sorted file/buffer */
+ uint num_keys_per_buffer; /* Max keys / buffer */
+ ha_rows max_rows; /* Select limit, or HA_POS_ERROR if unlimited */
+ ha_rows examined_rows; /* Number of examined rows */
+ TABLE *sort_form; /* For quicker make_sortkey */
SORT_FIELD *local_sortorder;
SORT_FIELD *end;
SORT_ADDON_FIELD *addon_field; /* Descriptors for companion fields */
@@ -89,15 +91,22 @@ typedef struct st_sort_param {
/* The fields below are used only by Unique class */
qsort2_cmp compare;
BUFFPEK_COMPARE_CONTEXT cmp_context;
-} SORTPARAM;
+
+ Sort_param()
+ {
+ memset(this, 0, sizeof(*this));
+ }
+ void init(uint sortlen, TABLE *table, THD *thd,
+ ha_rows maxrows, bool sort_positions);
+};
-int merge_many_buff(SORTPARAM *param, uchar *sort_buffer,
+int merge_many_buff(Sort_param *param, uchar *sort_buffer,
BUFFPEK *buffpek,
uint *maxbuffer, IO_CACHE *t_file);
uint read_to_buffer(IO_CACHE *fromfile,BUFFPEK *buffpek,
uint sort_length);
-int merge_buffers(SORTPARAM *param,IO_CACHE *from_file,
+int merge_buffers(Sort_param *param,IO_CACHE *from_file,
IO_CACHE *to_file, uchar *sort_buffer,
BUFFPEK *lastbuff,BUFFPEK *Fb,
BUFFPEK *Tb,int flag);
=== modified file 'sql/sql_table.cc'
--- a/sql/sql_table.cc 2010-09-01 13:13:01 +0000
+++ b/sql/sql_table.cc 2010-09-07 05:45:36 +0000
@@ -7091,7 +7091,7 @@ copy_data_between_tables(TABLE *from,TAB
!(sortorder= make_unireg_sortorder(order, &length, NULL)) ||
(from->sort.found_records= filesort(thd, from, sortorder, length,
(SQL_SELECT *) 0, HA_POS_ERROR,
- 1, &examined_rows)) ==
+ 1, &examined_rows, 0)) ==
HA_POS_ERROR)
goto err;
}
=== modified file 'sql/sql_update.cc'
--- a/sql/sql_update.cc 2010-08-16 06:58:42 +0000
+++ b/sql/sql_update.cc 2010-09-07 05:45:36 +0000
@@ -424,7 +424,7 @@ int mysql_update(THD *thd,
if (!(sortorder=make_unireg_sortorder(order, &length, NULL)) ||
(table->sort.found_records= filesort(thd, table, sortorder, length,
select, limit, 1,
- &examined_rows))
+ &examined_rows, 0))
== HA_POS_ERROR)
{
goto err;
=== modified file 'sql/uniques.cc'
--- a/sql/uniques.cc 2010-07-08 21:42:23 +0000
+++ b/sql/uniques.cc 2010-09-07 05:45:36 +0000
@@ -577,7 +577,6 @@ bool Unique::walk(tree_walk_action actio
bool Unique::get(TABLE *table)
{
- SORTPARAM sort_param;
table->sort.found_records=elements+tree.elements_in_tree;
if (my_b_tell(&file) == 0)
@@ -612,19 +611,20 @@ bool Unique::get(TABLE *table)
return 1;
reinit_io_cache(outfile,WRITE_CACHE,0L,0,0);
- bzero((char*) &sort_param,sizeof(sort_param));
+ Sort_param sort_param;
sort_param.max_rows= elements;
sort_param.sort_form=table;
sort_param.rec_length= sort_param.sort_length= sort_param.ref_length=
size;
- sort_param.keys= (uint) (max_in_memory_size / sort_param.sort_length);
+ sort_param.num_keys_per_buffer=
+ (uint) (max_in_memory_size / sort_param.sort_length);
sort_param.not_killable=1;
- if (!(sort_buffer=(uchar*) my_malloc((sort_param.keys+1) *
+ if (!(sort_buffer=(uchar*) my_malloc((sort_param.num_keys_per_buffer + 1) *
sort_param.sort_length,
MYF(0))))
return 1;
- sort_param.unique_buff= sort_buffer+(sort_param.keys*
+ sort_param.unique_buff= sort_buffer+(sort_param.num_keys_per_buffer *
sort_param.sort_length);
sort_param.compare= (qsort2_cmp) buffpek_compare;
=== modified file 'unittest/gunit/CMakeLists.txt'
--- a/unittest/gunit/CMakeLists.txt 2010-07-30 08:34:23 +0000
+++ b/unittest/gunit/CMakeLists.txt 2010-09-07 05:45:36 +0000
@@ -207,7 +207,7 @@ IF (CMAKE_CXX_COMPILER_ID STREQUAL "SunP
ENDIF()
# Add tests (link them with sql library)
-SET(TESTS sql_list mdl mdl_mytap my_regex thread_utils)
+SET(TESTS bounded_queue sql_list mdl mdl_mytap my_regex thread_utils)
FOREACH(test ${TESTS})
ADD_EXECUTABLE(${test}-t ${test}-t.cc)
TARGET_LINK_LIBRARIES(${test}-t gunit sqlgunitlib strings dbug regex)
=== added file 'unittest/gunit/bounded_queue-t.cc'
--- a/unittest/gunit/bounded_queue-t.cc 1970-01-01 00:00:00 +0000
+++ b/unittest/gunit/bounded_queue-t.cc 2010-09-07 05:45:36 +0000
@@ -0,0 +1,179 @@
+/* Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; version 2 of the License.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
+
+// First include (the generated) my_config.h, to get correct platform defines,
+// then gtest.h (before any other MySQL headers), to avoid min() macros etc ...
+#include "my_config.h"
+#include <gtest/gtest.h>
+#include <algorithm>
+
+#include "bounded_queue.h"
+#include "my_sys.h"
+
+namespace {
+
+const int num_elements= 14;
+const int num_keys= 1 + num_elements / 2;
+
+// A simple helper function to determine array size.
+template <class T, int size>
+int array_size(const T (&)[size])
+{
+ return size;
+}
+
+
+static int int_ptr_compare(void *cmp_arg, uchar *a, uchar *b)
+{
+ size_t first_arg= *(size_t*) cmp_arg;
+ EXPECT_EQ(first_arg, sizeof(int));
+
+ int a_num= (**(int**)a);
+ int b_num= (**(int**)b);
+ if (a_num > b_num)
+ return +1;
+ if (a_num < b_num)
+ return -1;
+ return 0;
+}
+
+
+// We use the data value itself as key.
+void mock_keymaker(Sort_param *sp, uchar *to, uchar *ref_pos)
+{
+ memcpy(to, ref_pos, sizeof(int));
+}
+
+
+class Bounded_queue_test : public ::testing::Test
+{
+protected:
+ Bounded_queue_test() : m_element_size(sizeof(int))
+ {
+ }
+
+ virtual void SetUp()
+ {
+ int ix;
+ for (ix=0; ix < array_size(m_test_data); ++ix)
+ m_test_data[ix]= ix;
+ std::random_shuffle(&m_test_data[0], &m_test_data[array_size(m_test_data)]);
+
+ for (ix=0; ix < array_size(m_key_ptrs); ++ix)
+ m_key_ptrs[ix]= (uchar*) &m_key_data[ix];
+ }
+
+ // Key pointers and data, used by the queue_xxx() functions.
+ uchar* m_key_ptrs[num_keys];
+ int m_key_data[num_keys];
+ // Some random intput data, to be sorted.
+ int m_test_data[num_elements];
+
+ size_t m_element_size;
+ Bounded_queue m_queue;
+private:
+ GTEST_DISALLOW_COPY_AND_ASSIGN_(Bounded_queue_test);
+};
+
+
+// googletest recommends DeathTest suffix for classes use in death tests.
+typedef Bounded_queue_test Bounded_queue_DeathTest;
+
+#if GTEST_HAS_DEATH_TEST && !defined(DBUG_OFF)
+/*
+ Verifies that we DBUG_ASSERT if trying to push to an un-initialized queue.
+ */
+TEST_F(Bounded_queue_DeathTest, die_if_not_initialized)
+{
+ ::testing::FLAGS_gtest_death_test_style = "threadsafe";
+ int foo= 1;
+ EXPECT_DEATH(m_queue.push((uchar*) &foo),
+ ".*Assertion .*is_initialized.*");
+}
+#endif // GTEST_HAS_DEATH_TEST && !defined(DBUG_OFF)
+
+
+/*
+ Verifies that construct, initialize, destroy works.
+ */
+TEST_F(Bounded_queue_test, construct_and_destruct)
+{
+ EXPECT_EQ(0, m_queue.init(num_elements/2, 0, TRUE,
+ (queue_compare) (get_ptr_compare(m_element_size)),
+ m_element_size,
+ &mock_keymaker, NULL, m_key_ptrs));
+}
+
+
+/*
+ Verifies that we reject too large queues.
+ */
+TEST_F(Bounded_queue_test, too_many_elements)
+{
+ EXPECT_EQ(1, m_queue.init(UINT_MAX, 0, TRUE,
+ (queue_compare) (get_ptr_compare(m_element_size)),
+ m_element_size,
+ &mock_keymaker, NULL, m_key_ptrs));
+ EXPECT_EQ(1, m_queue.init(UINT_MAX - 1, 0, TRUE,
+ (queue_compare) (get_ptr_compare(m_element_size)),
+ m_element_size,
+ &mock_keymaker, NULL, m_key_ptrs));
+}
+
+/*
+ Verifies that sorting, and bounded size, works.
+ */
+TEST_F(Bounded_queue_test, sort_buffer)
+{
+ EXPECT_EQ(0, m_queue.init(num_elements/2, 0, TRUE, int_ptr_compare,
+ m_element_size,
+ &mock_keymaker, NULL, m_key_ptrs));
+ for (int ix= 0; ix < array_size(m_test_data); ++ix)
+ {
+ m_queue.push((uchar*) &m_test_data[ix]);
+ }
+ int prev_element= num_elements;
+ int expected_value= num_elements / 2;
+ while (!m_queue.num_elements())
+ {
+ uchar *top_p= m_queue.pop();
+ int *top= *(int**) top_p;
+ EXPECT_GT(prev_element, *top);
+ EXPECT_EQ(expected_value--, *top);
+ prev_element= *top;
+ }
+}
+
+TEST(Cost_estimation_test, merge_many_buff)
+{
+ ha_rows num_rows= 512;
+ ulong num_keys= 100;
+ ulong row_lenght= 100;
+ double prev_cost= 0.0;
+ while (num_rows <= MAX_FILE_SIZE/4)
+ {
+ double merge_cost=
+ get_merge_many_buffs_cost_fast(num_rows / num_keys,
+ num_keys,
+ num_rows % num_keys,
+ row_lenght);
+ EXPECT_LT(0.0, merge_cost);
+ EXPECT_LT(prev_cost, merge_cost);
+ num_rows*= 2;
+ prev_cost= merge_cost;
+ }
+}
+
+} // namespace
Attachment: [text/bzr-bundle] bzr/tor.didriksen@oracle.com-20100907054536-lr0t00v2um0wt0z3.bundle
| Thread |
|---|
| • bzr commit into mysql-next-mr-opt-team branch (tor.didriksen:3223) WL#1393 | Tor Didriksen | 24 Sep |
