What is the default order of records for a SELECT statement in MySQL?

Question

Suppose you have the following table and data:

create table t (
    k int,
    v int,
    index k(k)
    ) engine=memory;

insert into t (k, v)
values (10, 1),
       (10, 2),
       (10, 3);

When issuing select * from t where k = 10 with no order by clause, how does MySQL sort the records by default?

Answer 1

Reposting my answer to a similar question regarding SQL Server:

In the SQL world, order is not an inherent property of a set of data. Thus, you get no guarantees from your RDBMS that your data will come back in a certain order -- or even in a consistent order -- unless you query your data with an ORDER BY clause.

So, to answer your question:

• MySQL sorts the records however it wants without any guarantee of consistency.
• If you intend to rely on this order for anything, you must specify your desired order using ORDER BY. To do anything else is to set yourself up for unwelcome surprises.

This is a property of all SQL, not just MySQL. The relevant text in the SQL-92 spec is:

If an <order by clause> is not specified, then the ordering of the rows of Q is implementation-dependent.

There are similar bits of text in the spec for cursors.

Answer 2

The order of the rows in the absence of ORDER BY clause may be:

• different between any two storage engines;
• if you use the same storage engine, it might be different between any two versions of the same storage engine; Example here, scroll down to "Ordering of Rows".
• if the storage engine version is the same, but MySQL version is different, it might be different because of the query optimizer changes between those versions;
• if everything is the same, it could be different due to the moon phase and that is OK.

Answer 3

Insertion is unordered, chaotic, on arrival. The index which is created does have order where elements are inserted in proper location in the linked list which is the index. Think of a triply linked list for an index, where you have a forward moving link from one index element to the next, a backward looking link for the traversal and integrity purposes, and then a set of pointers to the actual records in the table which match the indexed element in question.

Actual data, chaotic in storage. Index associated with the data, ordered in storage and construction. Actual pull of data, ordered or unordered, depends upon the query involved.

Answer 4

When it comes to the MEMORY storage engine, I would expect the order to be by the order of insertion because the default index layout is HASH instead of BTREE and neither aspect of index layout is being used. Since you indexed k, and k is the same value, all keys enter the same hash bucket. Since there is no reason to assume added complexity to populating a hash bucket, order of insertion makes the most sense.

I took your same sample table and data and ran 30 INSERTs and I got this:

mysql> use test
Database changed
mysql> drop table if exists t;
Query OK, 0 rows affected (0.00 sec)

mysql> create table t(k int, v int,index k(k)) engine=memory;
Query OK, 0 rows affected (0.00 sec)

mysql> insert into t values
    -> (10, 1), (10, 2), (10, 3), (10, 1), (10, 2), (10, 3),
    -> (10, 1), (10, 2), (10, 3), (10, 1), (10, 2), (10, 3),
    -> (10, 1), (10, 2), (10, 3), (10, 1), (10, 2), (10, 3),
    -> (10, 1), (10, 2), (10, 3), (10, 1), (10, 2), (10, 3),
    -> (10, 1), (10, 2), (10, 3), (10, 1), (10, 2), (10, 3);
Query OK, 30 rows affected (0.00 sec)
Records: 30  Duplicates: 0  Warnings: 0

mysql> select * from t;
+------+------+
| k    | v    |
+------+------+
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
+------+------+
30 rows in set (0.00 sec)

mysql>

I decided to test adding two different values for k : 10 and 11 I got this:

mysql> use test
Database changed
mysql> drop table if exists t;
Query OK, 0 rows affected (0.02 sec)

mysql> create table t(k int, v int,index k(k)) engine=memory;
Query OK, 0 rows affected (0.01 sec)

mysql> insert into t values
    -> (11, 1), (11, 2), (11, 3), (10, 1), (10, 2), (10, 3),
    -> (11, 1), (11, 2), (11, 3), (10, 1), (10, 2), (10, 3),
    -> (10, 1), (10, 2), (10, 3), (10, 1), (10, 2), (10, 3),
    -> (10, 1), (10, 2), (10, 3), (10, 1), (10, 2), (10, 3),
    -> (10, 1), (10, 2), (10, 3), (10, 1), (10, 2), (10, 3);
Query OK, 30 rows affected (0.00 sec)
Records: 30  Duplicates: 0  Warnings: 0

mysql> select * from t;
+------+------+
| k    | v    |
+------+------+
|   11 |    1 |
|   11 |    2 |
|   11 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   11 |    1 |
|   11 |    2 |
|   11 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
+------+------+
30 rows in set (0.00 sec)

mysql>

Looks like order of insertion. k=11 was the first key hashed then 10. What about inserting 10 first instead of 11? This is what I got:

mysql> use test
Database changed
mysql> drop table if exists t;
Query OK, 0 rows affected (0.02 sec)

mysql> create table t(k int, v int,index k(k)) engine=memory;
Query OK, 0 rows affected (0.00 sec)

mysql> insert into t values
    -> (10, 1), (10, 2), (10, 3), (10, 1), (10, 2), (10, 3),
    -> (11, 1), (11, 2), (11, 3), (10, 1), (10, 2), (10, 3),
    -> (11, 1), (11, 2), (11, 3), (10, 1), (10, 2), (10, 3),
    -> (10, 1), (10, 2), (10, 3), (10, 1), (10, 2), (10, 3),
    -> (10, 1), (10, 2), (10, 3), (10, 1), (10, 2), (10, 3);
Query OK, 30 rows affected (0.00 sec)
Records: 30  Duplicates: 0  Warnings: 0

mysql> select * from t;
+------+------+
| k    | v    |
+------+------+
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   11 |    1 |
|   11 |    2 |
|   11 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   11 |    1 |
|   11 |    2 |
|   11 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
|   10 |    1 |
|   10 |    2 |
|   10 |    3 |
+------+------+
30 rows in set (0.00 sec)

mysql>

It's unanimous !!! ORDER OF INSERTION is the answer.

Sidenotes on using indexes for the MEMORY storage engine

Range searches for MEMORY would have comparably horrific performance.

When creating an index, you can specify USING BTREE clause along with the definition of the index. This would improve things for range queries.

Searching for a specific row will yield the same result in performance with either HASH or BTREE.

UPDATE 2011-09-22 11:18 EDT

I learned something interesting today. I read the link provided by @Laurynas Biveinis from Percona: The Percona link says something about MEMORY tables for MySQL 5.5.15:

Ordering of Rows

In the absence of ORDER BY, records may be returned in a different order than the previous MEMORY implementation. This is not a bug. Any application relying on a specific order without an ORDER BY clause may deliver unexpected results. A specific order without ORDER BY is a side effect of a storage engine and query optimizer implementation which may and will change between minor MySQL releases.

This was a good link for me to see today. The answer I gave demonstrated that the table I loaded was retrieved in order I expected TODAY in MySQL 5.5.12. As just pointed out by Percona and @Laurynas Biveinis, there is no guarantee in another minor release.

So, rather than trying to defend my answer, I'd rather promote the answer from @Laurynas Biveinis because it is the most current info. Kudos and hats off for @Laurynas Biveinis. I'd also like to thank @eevar for politely pointing out not to promote version-specific answers to questions. They both get my upvote today.