Non-Deterministic Order for SELECT With LIMIT
Don't rely on the order of your rows if your query doesn't use ORDER BY. Rows with the same values can still be sorted differently. Learn how to fix this issue.
Join the DZone community and get the full member experience.
Join For FreeIn this blog, we’ll look at how queries in systems with parallel processing can return rows in a non-deterministic order (and how to fix it).
Short Story
Do not rely on the order of your rows if your query does not use ORDER BY
. Even with ORDER BY
, rows with the same values can be sorted differently. To fix this issue, always add ORDER BY ... ID
when you have LIMIT N
.
Long Story
While playing with MariaDB ColumnStore and Yandex ClickHouse, I came across a very simple case. In MariaDB ColumnStore and Yandex ClickHouse, the simple query (which I used for testing) select * from <table> where ... limit 10
returns results in a non-deterministic order.
This is totally expected. SELECT * from <table> WHERE ... LIMIT 10
means “give me any ten rows, and as there is no order they can be anything that matches the WHERE
condition.” What we used to get in vanilla MySQL plus InnoDB, however, is different;SELECT * from <table> WHERE ... LIMIT 10
gives us the rows sorted by primary key. Even with MyISAM in MySQL, if the data doesn’t change, the results are repeatable:
mysql> select * from City where CountryCode = 'USA' limit 10;
+------+--------------+-------------+--------------+------------+
| ID | Name | CountryCode | District | Population |
+------+--------------+-------------+--------------+------------+
| 3793 | New York | USA | New York | 8008278 |
| 3794 | Los Angeles | USA | California | 3694820 |
| 3795 | Chicago | USA | Illinois | 2896016 |
| 3796 | Houston | USA | Texas | 1953631 |
| 3797 | Philadelphia | USA | Pennsylvania | 1517550 |
| 3798 | Phoenix | USA | Arizona | 1321045 |
| 3799 | San Diego | USA | California | 1223400 |
| 3800 | Dallas | USA | Texas | 1188580 |
| 3801 | San Antonio | USA | Texas | 1144646 |
| 3802 | Detroit | USA | Michigan | 951270 |
+------+--------------+-------------+--------------+------------+
10 rows in set (0.01 sec)
mysql> select * from City where CountryCode = 'USA' limit 10;
+------+--------------+-------------+--------------+------------+
| ID | Name | CountryCode | District | Population |
+------+--------------+-------------+--------------+------------+
| 3793 | New York | USA | New York | 8008278 |
| 3794 | Los Angeles | USA | California | 3694820 |
| 3795 | Chicago | USA | Illinois | 2896016 |
| 3796 | Houston | USA | Texas | 1953631 |
| 3797 | Philadelphia | USA | Pennsylvania | 1517550 |
| 3798 | Phoenix | USA | Arizona | 1321045 |
| 3799 | San Diego | USA | California | 1223400 |
| 3800 | Dallas | USA | Texas | 1188580 |
| 3801 | San Antonio | USA | Texas | 1144646 |
| 3802 | Detroit | USA | Michigan | 951270 |
+------+--------------+-------------+--------------+------------+
10 rows in set (0.00 sec)
The results are ordered by ID here. In most cases, when the data doesn’t change and the query is the same, the order of results will be deterministic: open the file, read ten lines from the beginning, close the file. (When using indexes it can be different if different indexes are selected. For the same query, the database will probably select the same index if the data is static.)
But this is still not guaranteed. Here’s why. Imagine we now introduce parallelism, split our table into ten pieces, and run ten threads. Each will work on its own piece. Then, unless we specifically wait on each thread to finish and order the results, it will give us a random order of results. Let’s simulate this in a bash script:
for y in {2000..2010}
do
sql="select YearD, count(*), sum(ArrDelayMinutes) from ontime where yeard=$y and carrier='DL' limit 1"
mysql -Nb ontime -e "$sql" &
done
wait
The script’s purpose is to perform aggregation faster by taking advantage of multiple CPU cores on the server in parallel. It opens ten connections to MySQL and returns results as they arrive:
$ ./parallel_test.sh
2009 428007 5003632
2007 475889 5915443
2008 451931 5839658
2006 506086 6219275
2003 660617 5917398
2004 687638 8384465
2002 728758 7381821
2005 658302 8143431
2010 732973 9169167
2001 835236 8339276
2000 908029 11105058
$ ./parallel_test.sh
2009 428007 5003632
2008 451931 5839658
2007 475889 5915443
2006 506086 6219275
2005 658302 8143431
2003 660617 5917398
2004 687638 8384465
2002 728758 7381821
2010 732973 9169167
2001 835236 8339276
2000 908029 11105058
In this case, the faster queries arrive first and are on top, with the slower on the bottom. If the network was involved (think about different nodes in a cluster connected via a network), then the response time from each node can be much more random due to non-deterministic network latency.
In the case of MariaDB ColumnStore or Yandex ClickHouse, where scans are performed in parallel, the order of the results can also be non-deterministic. An example for ClickHouse:
:) select * from wikistat where project = 'en' limit 1;
SELECT *
FROM wikistat
WHERE project = 'en'
LIMIT 1
┌───────date─┬────────────────time─┬─project─┬─subproject─┬─path─────┬─hits─┬──size─┐
│ 2008-07-11 │ 2008-07-11 14:00:00 │ en │ │ Retainer │ 14 │ 96857 │
└────────────┴─────────────────────┴─────────┴────────────┴──────────┴──────┴───────┘
1 rows in set. Elapsed: 0.031 sec. Processed 2.03 million rows, 41.40 MB (65.44 million rows/s., 1.33 GB/s.)
:) select * from wikistat where project = 'en' limit 1;
SELECT *
FROM wikistat
WHERE project = 'en'
LIMIT 1
┌───────date─┬────────────────time─┬─project─┬─subproject─┬─path─────────┬─hits─┬───size─┐
│ 2008-12-15 │ 2008-12-15 14:00:00 │ en │ │ Graeme_Obree │ 18 │ 354504 │
└────────────┴─────────────────────┴─────────┴────────────┴──────────────┴──────┴────────┘
1 rows in set. Elapsed: 0.023 sec. Processed 1.90 million rows, 68.19 MB (84.22 million rows/s., 3.02 GB/s.)
An example for ColumnStore:
MariaDB [wikistat]> select * from wikistat limit 1
date: 2008-01-18
time: 2008-01-18 06:00:00
project: en
subproject: NULL
path: Doctor_Who:_Original_Television_Soundtrack
hits: 2
size: 2
1 row in set (1.63 sec)
MariaDB [wikistat]> select * from wikistat limit 1
date: 2008-01-31
time: 2008-01-31 10:00:00
project: de
subproject: NULL
path: Haramaki
hits: 1
size: 1
1 row in set (1.58 sec)
In another case (bug#72076) we use RDER BY
, but the rows being sorted are the same. MySQL 5.7 contains the “ORDER BY” + LIMIT optimization:
If multiple rows have identical values in the ORDER BY columns, the
server is free to return those rows in any order, and may do so
differently depending on the overall execution plan. In other words,
the sort order of those rows is nondeterministic with respect to
the nonordered columns.
Conclusion
In systems that involve parallel processing, queries like select * from table where ... limit N
can return rows in a random order (even if the data doesn’t change between the calls). This is due to the async nature of the parallel calls: whoever serves results faster wins. In MySQL, you run select * from table limit 1
three times and get the same data in the same order (especially if the table data doesn’t change), but the response time will be slightly different. In a massively parallel system, the difference in the response times can cause the rows to be ordered differently.
To fix: always add ORDER BY ... ID
when you have LIMIT N
.
Published at DZone with permission of Alexander Rubin, DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.
Comments