Wrong "Order by"

[filhodanuvem]

Order by is wrong :
The "operator" just sorts a page, the result itself.

Eg:.
select author, message from commits

author	message
cloudson	1
hgfischer	2
jeanpimentel	3

select author message from commits order by message desc limit 2

author	message
hgfischer	2
cloudson	1

It happens because :

1. gitql executes select author from commits limit 2
2. it sorts the result page by message field

Why the obvious solution is a bad idea?
Because we would need:

1. gitql executes select author from commits
2. it sorts all commits (god, could be a lot of memory)
3. choose just the two first lines

[vmeurisse]

Actually, you don't need to sort the full dataset to get the n first sorted.

You can take a look at https://en.wikipedia.org/wiki/Partial_sorting for some ideas.

[filhodanuvem]

Thanks @vmeurisse ! You are right about partial sorting, Gitql would sort just rows that match with where.
But I am unhappy about memory allocation.

Example:

author	message
cloudson	1
cloudson	2
cloudson	3

For now, with select message from commits where author = 'cloudson' limit 2 gitql runs on O(k) - k >= 2 .
With the new solution, gitql always will run on O(n) - n is the total number for rows matched.
And O(k) < O(n) in best case.

I'm thinking that there is no other way.

References:

• http://nilinfobin.com/2011/08/how-mysql-does-sorting-with-order-by/
• http://javalandscape.blogspot.com.br/2009/09/how-things-works-sql-order-by-clause.html