SQL: ranking without self join, revisited

September 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    |
+------+------+

tags:
posted in MySQL by shlomi

« | »

Follow comments via the RSS Feed | Leave a comment | Trackback URL

9 Comments to "SQL: ranking without self join, revisited"

  1. Roland Bouman wrote:

    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 :)

  2. Roland Bouman wrote:

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

  3. shlomi wrote:

    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

  4. shlomi wrote:

    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

  5. Kleyber Derick wrote:

    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.

  6. shlomi wrote:

    @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.

  7. Kleyber Derick wrote:

    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.

  8. Kleyber Derick wrote:

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

  9. Kleyber Derick wrote:

    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

Leave Your Comment

 

 
Powered by Wordpress and MySQL. Theme by openark.org