SQL: ranking without self join, revisited

This post follows SQL: Ranking without self join and On user variables evaluation order. I wish to share some insights with regard to user variables evaluation, as well as provide yet another ranking solution, which attempts to overcome the uncertainty factor with user variables.

There will be hand waving in this post (albeit empirical hand waving). Stop here if you don’t like hand waving. Continue if you feel curious or wish to contradict my assumptions.

Recap

The order of evaluation of user variables is undefined. The documentation has some contradicting example (bug 47514), but states that variables should not be read and assigned in different parts of the same statement (just what is a different part? Bug 47516).

Looking for a solution

There doesn’t seem to be a problem with reading and assigning variables in the very same part of the statement. For example, SELECT @a := @a+1… is exactly such a case.

So I was looking for means to setup all the variables in one single “part” of the statement, which is to say, a single column. I’ve found several solutions, here’s one:

COALESCE()

The COALESCE() function accepts any number of parameters (>=1), and returns the first non-NULL parameter. Tests show that it iterates the parameters and stops iterating at the first non-NULL parameter. So, parameter #3 is not even evaluated if parameter #2 is proven to be non-NULL.

This makes for a very interesting property: there is a known order of evaluation of parameters in this function.

So, for example:

SET @a := 0, @b := 0;
SELECT COALESCE(@a := @a+1, @b := @a+3);
+----------------------------------+
| COALESCE(@a := @a+1, @b := @a+3) |
+----------------------------------+
|                                1 |
+----------------------------------+

SELECT @a, @b;
+------+------+
| @a   | @b   |
+------+------+
| 1    | 0    |
+------+------+

We know that @a+1 is first evaluated, and only if it turns to be NULL, @a+3 is evaluated (which isn’t the case here).

PS: CASE statements also work this way, but COALESCE() is more compact, so I’ll use it instead.

We still can’t be sure that the assignment takes place at that time. For example, is it possible that @a+1 is first evaluated, then (assuming it’s NULL) @a+3 is evaluated, and only then @a and @b get the assignment?

I find this extremely unlikely. That would mean, code-wise, creating a temporary map which caches every internal, intermediate result, until column value is finally evaluated, only then to be iterated and mapped to the variables. To give an extreme example, look at:

SELECT @a := (@b := 3 + (@c := @c + 2*(@d := SIN(id)))) FROM world.City

Would SIN(id), 2*SIN(id), @c + 2*SIN(id), 3 + (@c + 2*SIN(id)) all be cached even while the result is being evaluated? Not only is this unlikely, user variables common usage indicates the opposite. I think it’s safe to say that @d is first assigned, then @c, then @b, and @a being the last.

ORDER BY

Yet another issue is: if q query has an ORDER BY, how can I be certain that user variables are iterated after ordering takes place, and not during sort merge passes?

Apart from:

• Promising I’ll try and read the source code
• Wait for qualified answers from the programmers
• Empirically testing this is not the case

Let me have one last hand waving: if that were the case, we wouldn’t be using user variables anytime, anywhere; everything would be too fragile.

Ranking without self join

Roland Bouman presented another ranking trick. A very cool one! Why not settle with that solution?

The thing which bothers me with it is the memory required to create the concatenated score values. We need to build an in-memory string representation of all scores. So the memory requirements for his algorithm are O(n), whereas I strive to use an O(1) amount of memory. The problem with O(n) is that it may not work well (or not at all) for very large datasets. Even for tables indexed by the score column, that amount of memory must be allocated. Then parsed; and then parsed again; and again; and each time the parsing should take longer, since each time we’re looking at a later token.

So I wish to present yet another solution, which relies on the COALESCE() properties discussed above. I’ll force all COALESCE() parameters but last one to be NULL, thereby forcing COALESCE() to keep iterating and evaluate all parameters, in an expected order. Again, I’ll be using a simple score table (download score.sql):

SELECT
  score_id, student_name, score,
  @rank := COALESCE(
    NULL + (@prev := @curr),
    NULL + (@curr := score),
    IF(@prev = @curr, @rank, @rank+1)
  ) AS rank
FROM
 score,
 (SELECT @curr := null, @prev := null, @rank := 0) sel1
ORDER BY score DESC
;
+----------+--------------+-------+------+
| score_id | student_name | score | rank |
+----------+--------------+-------+------+
|        2 | Gromit       |    97 |    1 |
|        1 | Wallace      |    95 |    2 |
|        4 | McGraw       |    92 |    3 |
|        5 | Preston      |    92 |    3 |
|        3 | Shaun        |    85 |    4 |
+----------+--------------+-------+------+

I’ve tried the above with several variations, with GROUP BY on score_id; on score_id, other columns; with GROUP BY mixed with ORDER BY; to always reach the same result set.