Skip to content

Commit 07b1d30

Browse files
author
Tor Didriksen
committed
WL#1393 Optimizing filesort with small limit
 Many web customers have to do "SELECT ... ORDER BY non_index_column LIMIT X", When X * <Row Size> is smaller than sort_buff_size we can use the following algoritm to speed up the sort: - Create a queue to hold 'limit' keys. - Scan through the table and store the first (last if DESC) keys in the queue - Return values from queue
1 parent 0554429 commit 07b1d30

38 files changed

Lines changed: 3719 additions & 293 deletions

‎libmysqld/CMakeLists.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,7 @@ SET(SQL_EMBEDDED_SOURCES emb_qcache.cc libmysqld.c lib_sql.cc
4444
../sql-common/client_plugin.c
4545
../sql/password.c ../sql/discover.cc ../sql/derror.cc
4646
../sql/field.cc ../sql/field_conv.cc
47+
../sql/filesort_utils.cc
4748
../sql/filesort.cc ../sql/gstream.cc
4849
../sql/handler.cc ../sql/hash_filo.cc ../sql/hostname.cc
4950
../sql/init.cc ../sql/item_buff.cc ../sql/item_cmpfunc.cc

‎mysql-test/include/order_by.inc‎

Lines changed: 197 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1364,6 +1364,203 @@ ORDER BY t2.c LIMIT 1;
13641364

13651365
DROP TABLE t1,t2,t3;
13661366

1367+
--echo #
1368+
--echo # WL#1393 - Optimizing filesort with small limit
1369+
--echo #
1370+
1371+
CREATE TABLE t1(f0 int auto_increment primary key, f1 int, f2 varchar(200));
1372+
INSERT INTO t1(f1, f2) VALUES
1373+
(0,"0"),(1,"1"),(2,"2"),(3,"3"),(4,"4"),(5,"5"),
1374+
(6,"6"),(7,"7"),(8,"8"),(9,"9"),(10,"10"),
1375+
(11,"11"),(12,"12"),(13,"13"),(14,"14"),(15,"15"),
1376+
(16,"16"),(17,"17"),(18,"18"),(19,"19"),(20,"20"),
1377+
(21,"21"),(22,"22"),(23,"23"),(24,"24"),(25,"25"),
1378+
(26,"26"),(27,"27"),(28,"28"),(29,"29"),(30,"30"),
1379+
(31,"31"),(32,"32"),(33,"33"),(34,"34"),(35,"35"),
1380+
(36,"36"),(37,"37"),(38,"38"),(39,"39"),(40,"40"),
1381+
(41,"41"),(42,"42"),(43,"43"),(44,"44"),(45,"45"),
1382+
(46,"46"),(47,"47"),(48,"48"),(49,"49"),(50,"50"),
1383+
(51,"51"),(52,"52"),(53,"53"),(54,"54"),(55,"55"),
1384+
(56,"56"),(57,"57"),(58,"58"),(59,"59"),(60,"60"),
1385+
(61,"61"),(62,"62"),(63,"63"),(64,"64"),(65,"65"),
1386+
(66,"66"),(67,"67"),(68,"68"),(69,"69"),(70,"70"),
1387+
(71,"71"),(72,"72"),(73,"73"),(74,"74"),(75,"75"),
1388+
(76,"76"),(77,"77"),(78,"78"),(79,"79"),(80,"80"),
1389+
(81,"81"),(82,"82"),(83,"83"),(84,"84"),(85,"85"),
1390+
(86,"86"),(87,"87"),(88,"88"),(89,"89"),(90,"90"),
1391+
(91,"91"),(92,"92"),(93,"93"),(94,"94"),(95,"95"),
1392+
(96,"96"),(97,"97"),(98,"98"),(99,"99");
1393+
1394+
################
1395+
## Test sort when source data fits in memory
1396+
1397+
SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 100;
1398+
SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 30;
1399+
SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 0;
1400+
SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 30;
1401+
SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 0;
1402+
SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 20;
1403+
SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0;
1404+
SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 10 OFFSET 10;
1405+
SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0 OFFSET 10;
1406+
1407+
################
1408+
## Test sort when source data does not fit in memory
1409+
set sort_buffer_size= 32768;
1410+
CREATE TEMPORARY TABLE tmp (f1 int, f2 varchar(20));
1411+
INSERT INTO tmp SELECT f1, f2 FROM t1;
1412+
INSERT INTO t1(f1, f2) SELECT * FROM tmp;
1413+
INSERT INTO tmp SELECT f1, f2 FROM t1;
1414+
INSERT INTO t1(f1, f2) SELECT * FROM tmp;
1415+
1416+
SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 30;
1417+
SELECT * FROM t1 ORDER BY f1 ASC, f0 LIMIT 0;
1418+
SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 30;
1419+
SELECT * FROM t1 ORDER BY f2 DESC, f0 LIMIT 0;
1420+
SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 20;
1421+
SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0;
1422+
SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 10 OFFSET 10;
1423+
SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 0 OFFSET 10;
1424+
1425+
################
1426+
## Test with SQL_CALC_FOUND_ROWS
1427+
set sort_buffer_size= 32768;
1428+
SELECT SQL_CALC_FOUND_ROWS * FROM t1
1429+
ORDER BY f1, f0 LIMIT 30;
1430+
SELECT FOUND_ROWS();
1431+
1432+
SELECT SQL_CALC_FOUND_ROWS * FROM t1
1433+
ORDER BY f1, f0 LIMIT 0;
1434+
SELECT FOUND_ROWS();
1435+
1436+
SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
1437+
ORDER BY f2, f0 LIMIT 20;
1438+
SELECT FOUND_ROWS();
1439+
1440+
SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
1441+
ORDER BY f2, f0 LIMIT 0;
1442+
SELECT FOUND_ROWS();
1443+
1444+
SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
1445+
ORDER BY f2, f0 LIMIT 10 OFFSET 10;
1446+
SELECT FOUND_ROWS();
1447+
1448+
SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
1449+
ORDER BY f2, f0 LIMIT 0 OFFSET 10;
1450+
SELECT FOUND_ROWS();
1451+
1452+
################
1453+
## Test sorting with join
1454+
## These are re-written to use PQ during execution.
1455+
set sort_buffer_size= 327680;
1456+
1457+
SELECT * FROM t1 JOIN tmp on t1.f2=tmp.f2
1458+
ORDER BY tmp.f1, f0 LIMIT 30;
1459+
1460+
SELECT * FROM t1 JOIN tmp on t1.f2=tmp.f2
1461+
ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30;
1462+
1463+
SELECT SQL_CALC_FOUND_ROWS * FROM t1 JOIN tmp on t1.f2=tmp.f2
1464+
ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30;
1465+
SELECT FOUND_ROWS();
1466+
1467+
SELECT SQL_CALC_FOUND_ROWS * FROM t1 JOIN tmp on t1.f2=tmp.f2
1468+
WHERE t1.f2>20
1469+
ORDER BY tmp.f1, f0 LIMIT 30 OFFSET 30;
1470+
SELECT FOUND_ROWS();
1471+
1472+
################
1473+
## Test views
1474+
CREATE VIEW v1 as SELECT * FROM t1 ORDER BY f1, f0 LIMIT 30;
1475+
SELECT * FROM v1;
1476+
drop view v1;
1477+
1478+
CREATE VIEW v1 as SELECT * FROM t1 ORDER BY f1, f0 LIMIT 100;
1479+
SELECT * FROM v1 ORDER BY f2, f0 LIMIT 30;
1480+
1481+
CREATE VIEW v2 as SELECT * FROM t1 ORDER BY f2, f0 LIMIT 100;
1482+
SELECT * FROM v1 JOIN v2 on v1.f1=v2.f1 ORDER BY v1.f2,v1.f0,v2.f0
1483+
LIMIT 30;
1484+
1485+
################
1486+
## Test group & having
1487+
SELECT floor(f1/10) f3, count(f2) FROM t1
1488+
GROUP BY 1 ORDER BY 2,1 LIMIT 5;
1489+
1490+
SELECT floor(f1/10) f3, count(f2) FROM t1
1491+
GROUP BY 1 ORDER BY 2,1 LIMIT 0;
1492+
1493+
################
1494+
## Test SP
1495+
delimiter |;
1496+
CREATE PROCEDURE wl1393_sp_test()
1497+
BEGIN
1498+
SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 30;
1499+
SELECT * FROM t1 WHERE f1>10 ORDER BY f2, f0 LIMIT 15 OFFSET 15;
1500+
SELECT SQL_CALC_FOUND_ROWS * FROM t1 WHERE f1>10
1501+
ORDER BY f2, f0 LIMIT 15 OFFSET 15;
1502+
SELECT FOUND_ROWS();
1503+
SELECT * FROM v1 ORDER BY f2, f0 LIMIT 30;
1504+
END|
1505+
CALL wl1393_sp_test()|
1506+
DROP PROCEDURE wl1393_sp_test|
1507+
delimiter ;|
1508+
1509+
################
1510+
## Test with subqueries
1511+
SELECT d1.f1, d1.f2 FROM t1
1512+
LEFT JOIN (SELECT * FROM t1 ORDER BY f1 LIMIT 30) d1 on t1.f1=d1.f1
1513+
ORDER BY d1.f2 DESC LIMIT 30;
1514+
1515+
SELECT * FROM t1 WHERE f1 = (SELECT f1 FROM t1 ORDER BY 1 LIMIT 1);
1516+
1517+
--error ER_SUBQUERY_NO_1_ROW
1518+
SELECT * FROM t1 WHERE f1 = (SELECT f1 FROM t1 ORDER BY 1 LIMIT 2);
1519+
1520+
DROP TABLE t1, tmp;
1521+
DROP VIEW v1, v2;
1522+
1523+
--echo # end of WL#1393 - Optimizing filesort with small limit
1524+
1525+
--echo #
1526+
--echo # Bug #58761
1527+
--echo # Crash in Field::is_null in field.h on subquery in WHERE clause
1528+
--echo #
1529+
1530+
CREATE TABLE t1 (
1531+
pk INT NOT NULL AUTO_INCREMENT,
1532+
col_int_key INT DEFAULT NULL,
1533+
col_varchar_key VARCHAR(1) DEFAULT NULL,
1534+
PRIMARY KEY (pk),
1535+
KEY col_varchar_key (col_varchar_key,col_int_key)
1536+
);
1537+
1538+
INSERT INTO t1 VALUES (27,7,'x');
1539+
INSERT INTO t1 VALUES (28,6,'m');
1540+
INSERT INTO t1 VALUES (29,4,'c');
1541+
1542+
CREATE TABLE where_subselect
1543+
SELECT DISTINCT `pk` AS field1 , `pk` AS field2
1544+
FROM t1 AS alias1
1545+
WHERE alias1 . `col_int_key` > 229
1546+
OR alias1 . `col_varchar_key` IS NOT NULL
1547+
GROUP BY field1, field2
1548+
;
1549+
1550+
SELECT *
1551+
FROM where_subselect
1552+
WHERE (field1, field2) IN (
1553+
SELECT DISTINCT `pk` AS field1 , `pk` AS field2
1554+
FROM t1 AS alias1
1555+
WHERE alias1 . `col_int_key` > 229
1556+
OR alias1 . `col_varchar_key` IS NOT NULL
1557+
GROUP BY field1, field2
1558+
);
1559+
1560+
DROP TABLE t1;
1561+
DROP TABLE where_subselect;
1562+
1563+
--echo # End of Bug #58761
13671564

13681565
#
13691566
# Bug#35844: Covering index for ref access not compatible with ORDER BY list

‎mysql-test/include/select.inc‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -4140,7 +4140,7 @@ DROP TABLE t1;
41404140
--echo End of 5.1 tests
41414141

41424142
--echo #
4143-
--echo # Bug#45277: Lost HAVING clause led to a wrong result.
4143+
--echo # Bug#45227: Lost HAVING clause led to a wrong result.
41444144
--echo #
41454145
CREATE TABLE `CC` (
41464146
`int_nokey` int(11) NOT NULL,
@@ -4162,7 +4162,7 @@ SELECT `varchar_nokey` G1 FROM CC WHERE `int_nokey` AND `int_key` <= 4
41624162
HAVING G1 ORDER BY `varchar_key` LIMIT 6 ;
41634163

41644164
DROP TABLE CC;
4165-
--echo # End of test#45277
4165+
--echo # End of test#45227
41664166

41674167
--echo #
41684168
--echo # Bug#54515: Crash in opt_range.cc::get_best_group_min_max on

‎mysql-test/r/explain.result‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -283,7 +283,7 @@ WHERE 1 > ALL((SELECT 1 FROM t1 JOIN t1 a ON (MATCH(t1.f1) AGAINST (""))
283283
WHERE t1.f1 GROUP BY t1.f1));
284284
id select_type table type possible_keys key key_len ref rows Extra
285285
1 PRIMARY t1 system NULL NULL NULL NULL 1
286-
2 SUBQUERY a system NULL NULL NULL NULL 1 Using filesort
286+
2 SUBQUERY a system NULL NULL NULL NULL 1
287287
2 SUBQUERY t1 fulltext f1 f1 0 1 Using where
288288
PREPARE stmt FROM
289289
'EXPLAIN SELECT 1 FROM t1
@@ -293,12 +293,12 @@ PREPARE stmt FROM
293293
EXECUTE stmt;
294294
id select_type table type possible_keys key key_len ref rows Extra
295295
1 PRIMARY t1 system NULL NULL NULL NULL 1
296-
2 SUBQUERY a system NULL NULL NULL NULL 1 Using filesort
296+
2 SUBQUERY a system NULL NULL NULL NULL 1
297297
2 SUBQUERY t1 fulltext f1 f1 0 1 Using where
298298
EXECUTE stmt;
299299
id select_type table type possible_keys key key_len ref rows Extra
300300
1 PRIMARY t1 system NULL NULL NULL NULL 1
301-
2 SUBQUERY a system NULL NULL NULL NULL 1 Using filesort
301+
2 SUBQUERY a system NULL NULL NULL NULL 1
302302
2 SUBQUERY t1 fulltext f1 f1 0 1 Using where
303303
DEALLOCATE PREPARE stmt;
304304
PREPARE stmt FROM
@@ -309,12 +309,12 @@ PREPARE stmt FROM
309309
EXECUTE stmt;
310310
id select_type table type possible_keys key key_len ref rows Extra
311311
1 PRIMARY t1 system NULL NULL NULL NULL 1
312-
2 SUBQUERY a system NULL NULL NULL NULL 1 Using filesort
312+
2 SUBQUERY a system NULL NULL NULL NULL 1
313313
2 SUBQUERY t1 fulltext f1 f1 0 1 Using where
314314
EXECUTE stmt;
315315
id select_type table type possible_keys key key_len ref rows Extra
316316
1 PRIMARY t1 system NULL NULL NULL NULL 1
317-
2 SUBQUERY a system NULL NULL NULL NULL 1 Using filesort
317+
2 SUBQUERY a system NULL NULL NULL NULL 1
318318
2 SUBQUERY t1 fulltext f1 f1 0 1 Using where
319319
DEALLOCATE PREPARE stmt;
320320
DROP TABLE t1;

‎mysql-test/r/group_by.result‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1886,3 +1886,48 @@ f1 MIN(f2) MAX(f2)
18861886
4 00:25:00 00:25:00
18871887
DROP TABLE t1;
18881888
#End of test#49771
1889+
#
1890+
# Bug #58782
1891+
# Missing rows with SELECT .. WHERE .. IN subquery
1892+
# with full GROUP BY and no aggr
1893+
#
1894+
CREATE TABLE t1 (
1895+
pk INT NOT NULL,
1896+
col_int_nokey INT,
1897+
PRIMARY KEY (pk)
1898+
);
1899+
INSERT INTO t1 VALUES (10,7);
1900+
INSERT INTO t1 VALUES (11,1);
1901+
INSERT INTO t1 VALUES (12,5);
1902+
INSERT INTO t1 VALUES (13,3);
1903+
SELECT pk AS field1, col_int_nokey AS field2
1904+
FROM t1
1905+
WHERE col_int_nokey > 0
1906+
GROUP BY field1, field2;
1907+
field1 field2
1908+
10 7
1909+
11 1
1910+
12 5
1911+
13 3
1912+
CREATE TABLE where_subselect
1913+
SELECT pk AS field1, col_int_nokey AS field2
1914+
FROM t1
1915+
WHERE col_int_nokey > 0
1916+
GROUP BY field1, field2
1917+
;
1918+
SELECT *
1919+
FROM where_subselect
1920+
WHERE (field1, field2) IN (
1921+
SELECT pk AS field1, col_int_nokey AS field2
1922+
FROM t1
1923+
WHERE col_int_nokey > 0
1924+
GROUP BY field1, field2
1925+
);
1926+
field1 field2
1927+
10 7
1928+
11 1
1929+
12 5
1930+
13 3
1931+
DROP TABLE t1;
1932+
DROP TABLE where_subselect;
1933+
# End of Bug #58782

‎mysql-test/r/myisam_mrr.result‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -347,7 +347,7 @@ GROUP BY t2.pk
347347
);
348348
id select_type table type possible_keys key key_len ref rows filtered Extra
349349
1 PRIMARY NULL NULL NULL NULL NULL NULL NULL NULL Impossible WHERE
350-
2 SUBQUERY t2 ref int_key int_key 5 const 1 100.00 Using where; Using filesort
350+
2 SUBQUERY t2 ref int_key int_key 5 const 1 100.00 Using where
351351
Warnings:
352352
Note 1003 select min(`test`.`t1`.`pk`) AS `MIN(t1.pk)` from `test`.`t1` where 0
353353
DROP TABLE t1, t2;

‎mysql-test/r/myisam_mrr_cost.result‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -347,7 +347,7 @@ GROUP BY t2.pk
347347
);
348348
id select_type table type possible_keys key key_len ref rows filtered Extra
349349
1 PRIMARY NULL NULL NULL NULL NULL NULL NULL NULL Impossible WHERE
350-
2 SUBQUERY t2 ref int_key int_key 5 const 1 100.00 Using where; Using filesort
350+
2 SUBQUERY t2 ref int_key int_key 5 const 1 100.00 Using where
351351
Warnings:
352352
Note 1003 select min(`test`.`t1`.`pk`) AS `MIN(t1.pk)` from `test`.`t1` where 0
353353
DROP TABLE t1, t2;

‎mysql-test/r/myisam_mrr_cost_icp.result‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -347,7 +347,7 @@ GROUP BY t2.pk
347347
);
348348
id select_type table type possible_keys key key_len ref rows filtered Extra
349349
1 PRIMARY NULL NULL NULL NULL NULL NULL NULL NULL Impossible WHERE
350-
2 SUBQUERY t2 ref int_key int_key 5 const 1 100.00 Using index condition; Using where; Using filesort
350+
2 SUBQUERY t2 ref int_key int_key 5 const 1 100.00 Using index condition
351351
Warnings:
352352
Note 1003 select min(`test`.`t1`.`pk`) AS `MIN(t1.pk)` from `test`.`t1` where 0
353353
DROP TABLE t1, t2;

‎mysql-test/r/myisam_mrr_icp.result‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -347,7 +347,7 @@ GROUP BY t2.pk
347347
);
348348
id select_type table type possible_keys key key_len ref rows filtered Extra
349349
1 PRIMARY NULL NULL NULL NULL NULL NULL NULL NULL Impossible WHERE
350-
2 SUBQUERY t2 ref int_key int_key 5 const 1 100.00 Using index condition; Using where; Using filesort
350+
2 SUBQUERY t2 ref int_key int_key 5 const 1 100.00 Using index condition
351351
Warnings:
352352
Note 1003 select min(`test`.`t1`.`pk`) AS `MIN(t1.pk)` from `test`.`t1` where 0
353353
DROP TABLE t1, t2;

‎mysql-test/r/myisam_mrr_none.result‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -346,7 +346,7 @@ GROUP BY t2.pk
346346
);
347347
id select_type table type possible_keys key key_len ref rows filtered Extra
348348
1 PRIMARY NULL NULL NULL NULL NULL NULL NULL NULL Impossible WHERE
349-
2 SUBQUERY t2 ref int_key int_key 5 const 1 100.00 Using where; Using filesort
349+
2 SUBQUERY t2 ref int_key int_key 5 const 1 100.00 Using where
350350
Warnings:
351351
Note 1003 select min(`test`.`t1`.`pk`) AS `MIN(t1.pk)` from `test`.`t1` where 0
352352
DROP TABLE t1, t2;

0 commit comments

Comments
 (0)