Skip to content

# SQL: ranking without self join, revisited

MySQL SQL September 25, 2009September 25, 2009

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.

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

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

- Twitter
- LinkedIn
- WhatsApp
- Email
- Facebook
- Print

###
9
Leave a Reply

9 Comment threads
0 Thread replies
0 Followers
Most reacted comment
Hottest comment thread
3 Comment authors
Recent comment authors

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Subscribe
Notify of
Guest
Roland Bouman

Hi Shlomi!

Nice trick. I’m not entirely convinced though, but it looks promising. I’ll do my best to try and falsify the result (:p) not to bug you of course, but to achieve more certainty that this is indeed reliable.

Thanks so far 🙂

Guest
Roland Bouman

BTW: I just wanted to say I agree with your analysis regarding the limitions of using GROUP_CONCAT (as I did in my example)

Author
shlomi

Hi Roland,

Thank you. I will make an effort to get more reliable information.
I think we should avoid the situation where we say “hmmm.. we’re not sure about this so let’s not use it”, but push towards a reliable answer.

Shlomi

Author
shlomi

Yikes!!

Browsing through High Performance MySQL (2nd Ed.), I suddenly notice this has all been discussed at length, at the end of chapter 4.
Seems like I’ve mostly repeated things that have been said there; I apparently offer little new.

Shlomi

Guest
Kleyber Derick

Hi Shlomi,
I’m quite new in MySQL but I have to create a ranking based on a specific SELECT using joined tables. My original select is this:

SELECT
l.cod_loja,
l.nome_loj,
SUM(c.vlrbase) AS soma
FROM
tab_comissao c INNER JOIN tab_prot p ON (c.ade=p.ade)
INNER JOIN tab_lojas l ON (l.cod_loja=p.cod_loja)
WHERE c.ade = p.ade AND p.cod_loja = l.cod_loja
AND c.datalanc>=’2011-01-04′
AND c.datalanc<='2011-02-02'
GROUP BY l.cod_loja
ORDER BY soma DESC

Where gives me this result:

3 store-3 345874.54
7 store-7 213022.86
6 store-6 209934.94
…
…
…
57 store-57 2827.18

So, how could I do this in order to show me the correct ranking?

Thanks in advance,

Kleyber Derick

PS: I put this question on Roland Bouman's blog too.

Author
shlomi

@Kleyber,
With GROUP BY this becomes significatnly more complicated. The easiest way out is to put all this in a subquery, then select all column, adding a ranking column to that. See first code samples on SQL Pie Chart.

BTW, “WHERE c.ade = p.ade AND p.cod_loja = l.cod_loja” is redundant: you already use these conditions on the JOIN clauses.

Guest
Kleyber Derick

Thank you fr replying Shlomi. I’ve done some tests, but I really did not understand your proposal. Let me show you what I did: SELECT SUM(c.vlrbase) AS vlrloja, l.cod_loja, l.nome_loj, (SELECT SUM(c.vlrbase) AS vlrloja1 FROM tab_comissao AS c, tab_prot AS p, tab_lojas AS l WHERE c.datalanc>=’2011-01-04′ AND c.datalanc=’2011-01-04′ AND c.datalanc=’2011-01-04′ AND c.datalanc<='2011-02-02' GROUP BY l.cod_loja ORDER BY vlrloja DESC This gives me the amount, the total amount and the percentage of each row… sorry for being a newbie in this case.

Guest
Kleyber Derick

Sorry, the SELECT is not complete. I am trying to put the real one, but I can’t.

Guest
Kleyber Derick

SELECT
SUM(c.vlrbase) AS vlrloja,
l.cod_loja,
l.nome_loj,
(SELECT
SUM(c.vlrbase) AS vlrloja1
FROM
tab_comissao AS c, tab_prot AS p, tab_lojas AS l
WHERE c.datalanc>=’2011-01-04′
AND c.datalanc=’2011-01-04′
AND c.datalanc=’2011-01-04′
AND c.datalanc<='2011-02-02'
GROUP BY l.cod_loja
ORDER BY vlrloja DESC

wpDiscuz
Send to Email Address Your Name Your Email Address Cancel
Post was not sent - check your email addresses!
Email check failed, please try again
Sorry, your blog cannot share posts by email.