List:General Discussion« Previous MessageNext Message »
From:Andrew Aksyonoff Date:September 15 2008 7:40pm
Subject:Re[4]: SELECT DISTINCT with ORDER BY implementation
View as plain text  
Hello Sergey,

Monday, September 15, 2008, 10:41:31 PM, you wrote:
>> in MySQL but in general case it can't assume any order and will have
>> to re-sort the sub-select result by outer GROUP BY instead of inner
>> ORDER BY. If that sorting is stable, this should work, but can we rely
SP> Yes. This is documented behavior:
SP> http://dev.mysql.com/doc/refman/5.0/en/select.html :
SP> "If you use GROUP BY, output rows are sorted according to the GROUP BY
SP> columns as if you had an ORDER BY for the same columns. To avoid the
SP> overhead of sorting that GROUP BY produces, add ORDER BY NULL:

Well, this snippet documents how the *grouped* rows will be ordered,
but the question is about the properties of specific sorting algorithm
that is internally used to implement GROUP BY.

I'm not sure if I'm clear enough so let me provide an example. Assume
that the inner SELECT produces the following:

id=1, sortkey=123, groupkey=33
id=2, sortkey=124, groupkey=33
id=3, sortkey=125, groupkey=11
id=4, sortkey=126, groupkey=11
id=5, sortkey=127, groupkey=22
id=6, sortkey=128, groupkey=22

I suppose that 'GROUP BY groupkey' will have to sort the incoming
rows by groupkey, then go over it sequentially, keeping only the
first encountered row for every given groupkey. 

However if the specific sorting algorithm is not stable it *might*
change the order and produce something like that for temporary
sorted set:

id=4, sortkey=126, groupkey=11
id=3, sortkey=125, groupkey=11
id=6, sortkey=128, groupkey=22
id=5, sortkey=127, groupkey=22
id=1, sortkey=123, groupkey=33
id=2, sortkey=124, groupkey=33

And put id=4 instead of id=3 into the result set.

So the question is a bit more subtle :) It's whether the algorithm
that GROUP BY (and possibly everything else) uses stable or not.
I'd bet a quarter that it is but just want to make sure :)

-- 
Best regards,
 Andrew                            mailto:shodan@stripped

Thread
SELECT DISTINCT with ORDER BY implementationMariella Petrini10 Sep
  • RE: SELECT DISTINCT with ORDER BY implementationRick James10 Sep
    • RE: SELECT DISTINCT with ORDER BY implementationMariella Petrini10 Sep
RE: SELECT DISTINCT with ORDER BY implementationMariella Petrini11 Sep
  • Re: SELECT DISTINCT with ORDER BY implementationSergey Petrunia12 Sep
RE: SELECT DISTINCT with ORDER BY implementationMariella Petrini11 Sep