Add serial in specific order?

[Poul Jensen <flyvholm@xxxxxxxxx>]

I have ~25 columns in my database and need to order the rows by all 
columns to do queries like:

SELECT a FROM table ORDER BY a, b, c, ...., z;

I suspect it would be highly ineffective to order by all columns for 
every query! Hence I'd like to do the ordering only once and add a 
serial to the database specifying the order so all subsequent queries 
can be done like:

SELECT b FROM table ORDER BY added_serial;

The optimal ordering is found from analysis of the database and is not 
known at build time. Is it possible to add the serial without having to 
rebuild the database? It has millions of rows, by the way...

Thanks for any advice.

Poul Jensen