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