36

I understand how ORDER BY clause works and how the FIELD() function works. What i want to understand is how the both of them work together to sort. How are the rows retrieved and how is the sort order derived

+----+---------+
| id |  name   |
+----+---------+
|  1 | stan    |
|  2 | kyle    |
|  3 | kenny   |
|  4 | cartman |
+----+---------+ 

SELECT * FROM mytable WHERE id IN (3,2,1,4) ORDER BY FIELD(id,3,2,1,4)

The query above will result in

+----+---------+
| id |  name   |
+----+---------+
|  3 | kenny   |
|  2 | kyle    |
|  1 | stan    |
|  4 | cartman |
+----+---------+ 

something similar to saying ORDER BY 3, 2, 1, 4

QUESTIONS

  • How does this work internally?
  • How does MySQL get the rows, and calculate the sort order ?
  • How does MySQL know it has to sort by the id column ?
  • 1
    try this variation of your query: SELECT *, FIELD(id,3,2,1,4) AS f FROM mytable WHERE id IN (3,2,1,4); Then add ORDER BY f or ORDER BY FIELD(id,3,2,1,4) and try again. – ypercubeᵀᴹ Aug 5 '15 at 20:10
63

For the record

SELECT * FROM mytable WHERE id IN (1,2,3,4) ORDER BY FIELD(id,3,2,1,4);

should work as well because you do not have to order the list in the WHERE clause

As for how it works,

  • FIELD() is a function that returns the index position of a comma-delimited list if the value you are searching for exists.

  • The ORDER BY values are evaluated by what FIELD() returns

You can create all sorts of fancy orders

For example, using the IF() function

SELECT * FROM mytable
WHERE id IN (1,2,3,4)
ORDER BY IF(FIELD(id,3,2,1,4)=0,1,0),FIELD(id,3,2,1,4);

This will cause the first 4 ids to appear at the top of the list, Otherwise, it appears at the bottom. Why?

In the ORDER BY, you either get 0 or 1.

  • If the first column is 0, make any of the first 4 ids appear
  • If the first column is 1, make it appear afterwards

Let's flip it with DESC in the first column

SELECT * FROM mytable
WHERE id IN (1,2,3,4)
ORDER BY IF(FIELD(id,3,2,1,4)=0,1,0) DESC,FIELD(id,3,2,1,4);

In the ORDER BY, you still either get 0 or 1.

  • If the first column is 1, make anything but the first 4 ids appear.
  • If the first column is 0, make the first 4 ids appear in the original order

YOUR ACTUAL QUESTION

If you seriously want internals on this, goto pages 189 and 192 of the Book

MySQL Internals

for a real deep dive.

In essence, there is a C++ class called ORDER *order (The ORDER BY expression tree). In JOIN::prepare, *order is used in a function called setup_order(). Why in the middle of the JOIN class? Every query, even a query against a single table is always processed as a JOIN (See my post Is there an execution difference between a JOIN condition and a WHERE condition?)

The source code for all this is sql/sql_select.cc

Evidently, the ORDER BY tree is going to hold the evaluation of FIELD(id,3,2,1,4). Thus, the numbers 0,1,2,3,4 are the values being sorted while carrying a reference to the row involved.

  • 1
    This is an outstandingly excellent explanation. Using these methods I was able to get 3 orders, a primary first value that is the max of the set, then by the FIELD, then by another column for the ones not in the FIELD set. Something I wouldn't have dreamed of some time ago. Thanks for taking the time to really explain how this actually works. – Lizardx May 4 '16 at 23:03
  • @naveen i know this is a old question. i know some parts of the MySQL source code and internals.. But never looked into MySQL's FIELD(..) function.. i suspect FIELD(id,3,2,1,4) is more or less a short "marco" in the MySQL optimizer/executioner for the more standard ANSI SQL way CASE WHEN id = 3 THEN 1 WHEN id = 2 THEN 2 WHEN id = 1 THEN 3 WHEN id = 4 THEN 4 ELSE 5 END – Raymond Nijland Jan 1 at 2:56
  • Suppose that there are N values in both IN and FIELD. In this example N=4. Do I understand correctly that this query is going to perform at least ~N^2 operations. Because each FIELD computation makes ~N comparisons once for each row. If so this is quite slow for big N Maybe it's not a very good approach? – Gherman Mar 15 at 15:53
  • @Gherman The FIELD() function should be an O(1) operation because FIELD() has an numerical index id. So I do not see anything else but O(n) based on rows. I don't see FIELD() doing any iterative operation such as GREATEST() would need to do. – RolandoMySQLDBA Mar 15 at 18:03
  • @RolandoMySQLDBA My point is that if FIELD has N arguments to compare with then it will execute N comparisons. How else is it going to compare one number with N other numbers if not by doing O(N)? The only possibility I can think of is some kind of optimisation through a special data structure like a hash or a tree of arguments. Actually I know that IN does has such optimization. I don't know about FIELD. What do you mean by a "numerical index"? – Gherman Mar 15 at 20:18
1

Maybe this will be too far from actual code so not low level enough from what you wanted:

When MySQL cannot use index to retrieve data in sorted order, it creates a temporary table/resultset with all selected columns and some additional data - one of those is some kind of a column for storing the results of ORDER BY expression value for each row - then it sends this tmp table to a "filesort" rutine with info which column to sort by. After that the rows are in sorted order so it can pick them one by one and return selected columns.

  • This explanation does not take into account how FIELD function in computed. I am afraid it may have a significant impact on performance. – Gherman Mar 15 at 16:07
  • @Gherman I don't think so, unless you are using very long list of arguments (as the function is linear to number of arguments. Data access is an order of magnitude slower than simple comparisons. – jkavalik Mar 15 at 17:23
  • Yes, long list of arguments. There are as many arguments as there are records in this example. – Gherman Mar 15 at 20:20
  • I would only label hundreds or thousands as many, and then you get other problems anyway (query size etc.) – jkavalik Mar 15 at 20:42
  • why not hundreds results? Is it many? – Gherman Mar 15 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.