Non-Deterministic Order for SELECT With LIMIT

In 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.