large data set: paginating, sorting - application? database? stored procedure?

- My ultimate goal is to paginate a large data set (to have something
that looks like a data grid)

- I am using paginating_find (but am open to other suggestions)

- Being able to resort the data set by column is a must have. The two
options I have are: (1) retrieve the data set and sort it in the
application (model or controller) - this is expensive and probably
won't scale for large data sets, and (2) do the sorting in the
database

- My actual find/select query is somewhat hairy:

Classname.find(:all,
:select => "some_fields_go_here,
if ( (some calculation) > (another calculation),
return_certain_field ...",
:joins => [ "inner join on something ... left join on
something_else ... inner join on another_thing" ],
:conditions => [ "some conditions" ],
:order => some_order )

- Naturally, I am trying to avoid having many db calls (I mean, it's a
large data set - potentially tens of thousands of records)

What is the best/recommended way to handle this (this meaning a
relatively complex query with joins, calculations, pagination, and
sorting)? Should I be building stored procedures (I am using MySQL)?
Is there a clever way to do this on the application side without
incurring a huge cost when sorting? Any help would be appreciated.

Thanks so much,

--sasha