Slow MySQL retreival of the row with the largest value in indexed column

Question

I have a SQL table readings something like:

id int
client_id int
device_id int
unique index(client_id, device_id)

I do not understand why the following query is so slow:

SELECT client_id FROM `readings` WHERE device_id = 10 ORDER BY client_id DESC LIMIT 1

My understanding with the index is that mysql keeps an ordered list (one property of a btree) of each row in the table sorted first by client_id and then by device_id. When I execute an explain on this query it says that it will use the index, but that it will need to look at every row. This makes sense since in the worst case, there may only be one row with device_id = 10 and that may also be the row with the smallest client_id and thus at the end of it's search. However, in practice, this is not true. My table has ~10 million rows, and rows with device_id = 10 are spread fairly evenly throughout that table. Why then doesn't MySQL start at the end of the index and scan until it finds the first row with device_id = 10, stop and return that value? It does not seem possible that this is what is happening since the query takes ~30 seconds to execute.

Is it that my unique key is implemented as a hash somehow and thus not accessible in a list form? PHPMyAdmin is telling me that it is implemented as a b-tree, which makes me think that it should be able to do the scan as I mentioned above and quit with the first instance.

Where is my error and how can I make this query execute more quickly?

Thanks

Answer 1

Try switching the column order in the index:

unique index(device_id, client_id)

Since you are filtering on device_id, you would want that to be the first column in the index.

Answer 2

First, I'm assuming that you have good statistics for this table. If not, you'll want to analyze the table to make sure the optimizer can figure out what the best option is.

Here's another approach you could try that might work better. I could be that MySQL is not understanding your intent well enough to optimize correctly:

SELECT MAX(client_id) from readings where device_id = 10

Otherwise you could modify the index to be by device_id first, then client_id. Or you could add another index by just device_id.

Answer 3

You have a compound index on (client_id, device_id), these will(more or less) be concatenated for the purpose of indexing and the index will only be considered if you use the first of the column(s). Your query is using 'device_id' which is the last of them, you could provide a separate index on that column, or swap the columns around in the index.

Also, check the output of EXPLAIN on your queries.