Witam.
Masz 2 wyjścia, dla małej tabeli sortuj u usera np https://plugins.jquery.com/tablesorter/
A dla dużej musisz stworzyć cache i pytać o niego.
Jeśli tablica jest mała, to jest mieści się w pamięci, to rozważyłbym propozycje @drobok-a.
W przypadku tablicy, która nie mieści się do pamięci i tak musisz zastosować paginację. Tu nie przejmowałbym się tym, że leci to z BD. Wystarczy dobrze założyć indeksy, dobrze napisać zapytania stronicujące i o ile to możliwe skonfigurować w bazie trzymanie indeksu w RAM. W zasadzie nie powinieneś odczuć tego, że często sortujesz. W przypadku, gdyby to było za mało, dobrym rozwiązaniem będzie też Lucene/Solr. Są dwie zalety takiego rozwiązania nad samą BD. Przewagą Solr jest to, że został on napisany głownie z myślą o wyszukiwaniu (ma bardzo dobre algorytmy przeszukujące indeks) oraz najważniejsze NIE JEST transakcyjny (w tym należy rozumieć, że nie posiada właściwości ACID, etc.). Dzięki temu jest z definicji szybszy jeśli chodzi o przeszukiwanie niż BD. Ponadto z powodu braku transakcji można go łatwo sklastrować. Dzięki temu, jeśli nie wystarczy ci moc jednego serwera, może go uruchomić na 16 czy 32, czy ilu zechcesz serwerach i w zasadzie możesz przyjąć dowolny ruch.
Zapamiętaj złotą zasadę. If you program works too slow buy more webservers it’s cheaper than development.