I'm trying to find a better way to get the next or previous record from a table. Let's say I have a blog or news table:

CREATE TABLE news (
    news_id INT UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT,
    news_datestamp DATETIME NOT NULL,
    news_author VARCHAR(100) NOT NULL,
    news_title VARCHAR(100) NOT NULL,
    news_text MEDIUMTEXT NOT NULL
);

Now on the frontend I want navigation buttons for the next or previous records, if i'm sorting by news_id, I can do something rather simple like:

SELECT MIN(news_id) AS next_news_id FROM news WHERE news_id > '$old_news_id' LIMIT 1
SELECT MAX(news_id) AS prev_news_id FROM news WHERE news_id < '$old_news_id' LIMIT 1

But the news can be sorted by any field, and I don't necessarily know which field is sorted on, so this won't work if the user sorts on news_author for example.

I've resorted to the rather ugly and inefficient method of sorting the entire table and looping through all records until I find the record I need.

$res = mysql_query("SELECT news_id FROM news ORDER BY `$sort_column` $sort_way");
$found = $prev = $next = 0;
while(list($id) = mysql_fetch_row($res)) {
    if($found) {
        $next = $id;
        break;
    }
    if($id == $old_news_id) {
        $found = true;
        continue;
    }
    $prev = $id;
}

There's got to be a better way.