In this article I’ll show you how to find the “next” and “previous” records (define these terms any way you like) in a set of records. My solution uses no subqueries or unions, so it works on old versions of MySQL, and returns both the next and the previous records in a single efficient query.
Motivation
I’m working on a project right now that requires me to use MySQL 3.23, because that’s what the production server uses. This means I’m digging out my old hacks and neat tricks to get around such limitations as the lack of subqueries. One of the really great things about this is that it makes me think hard about queries instead of just reaching for the familiar ways of doing things.
One of the pages displays a record in a series. I want a link to the next and previous in the series, if they exist. I want to do it in one query. I want my query to return the data, all the data, and nothing but the data.
My data’s primary key is a foreign key to another table, and a sequence number. Suppose it’s log entries, as in my post about surrogate keys. Here’s my test suite (I’m omitting the message column):
| t1 | seq |
|---|---|
| 5 | 98 |
| 5 | 99 |
| 5 | 100 |
| 5 | 101 |
| 5 | 105 |
Stuff that doesn’t work
It’s easy to do this in two queries. Given entry 5:100, I can write one query that finds the next entry, if it exists:
select min(seq) from t1log where t1=5 and seq > 100;
I can do the same thing for the previous entry. But I can’t write both “min-where-greater” and “max-where-less” into one WHERE clause without subqueries or unions. I could get around that with mutex tables, but there’s got to be a better way.
First try
If I sort the entries by how far away they are from the current entry, I can select the closest two.
select
case when seq > 100 then 'next' else 'prev' end as 'direction',
seq
from t1log
where t1 = 5
and seq <> 100
order by abs(100 - seq), seq
limit 2;
There are two problems with this query. If the magic number is the last entry, it’ll select the two previous records. And a gap in the sequence will make it select the wrong values too. Try it with 100, 101, and 105, and you’ll see what I mean. Sometimes it works, sometimes not.
One right way
If I can partition my data into two groups, those greater than and those less than, and select the minimum from the greater-than and maximum from the less-than, then I can do what I wished I could do above. Here I’ll use the SIGN function for brevity, but a CASE statement would work too:
select
case when sign(seq - 100) > 0 then 'next' else 'prev' end as dir,
case when sign(seq - 100) > 0 then min(seq) else max(seq) end as seq
from t1log
where t1 = 5
and seq <> 100
group by sign(seq - 100)
order by sign(seq - 100)
The trick is to find the right query to partition the data. That will depend on the meaning of “next” and “previous” in the specific application. In this case, partitioning by integer greater-than and less-than is easy.
MySQL likes this query, too. It uses the index well, so it’s nice and efficient. You can EXPLAIN the query to see how it does it — basically, it can constrain its search to a range of values in the primary key itself, since it doesn’t need any data other than the key (no bookmark lookups needed). It would be even more efficient to do it with a UNION, but that’s not available in MySQL 3.23.
So there you have it, another solution in search of a problem. I hope you enjoyed it. There are probably other ways to do it, but this is at least one way that works.
Update 2006-09-26
I noticed a bug with MySQL 3.23: though it makes no sense at all, I have to rewrite the query with another then clause instead of else, like this:
select
case when sign(seq - 100) > 0 then 'next' else 'prev' end as dir,
case when sign(seq - 100) > 0 then min(seq)
when sign(seq - 100) < 0 then max(seq) end as seq
from t1log
where t1 = 5
and seq <> 100
group by sign(seq - 100)
order by sign(seq - 100)
If I don’t do this, the “prev” seq value is NULL. For some reason, the “prev” dir value is not null in the same query. Very odd, no?
Wow, respect! I found this article very useful - all in one. Thanks a lot.
Elegant. Very close to what I’m looking for. Can this be tweaked to create a database view that can be queried to find next and/or previous values for a given value?
That would be platform-dependent, I guess. I don’t think it would work in any system I know. How would you make the view aware of the value? A user variable? I don’t know of a system where user variables can appear in a view definition. A stored procedure — definitely. Even a user function, in systems like SQL Server where a function can return a table.
Great stuff. Always a pleasure to see someone take a step back, and use a database engine for what it is designed for. To manipulate data.
Thanks for the query… saved me loads of time and effort.
J
Amazing tip, very usefull i spend alot of time researching a way to do this. Very good :) Thanks.
Hi, that’s veyr useful.
But, why do you use sign() ? The expression inside is already negative or positive and it will do for the > 0 test… or am I wrong?
Best regards.
In which place? Can you rewrite the query or part of the query and get the same results? If it’s simpler, I’m all for it.
Mmh, I think I was wrong, I thought you can do the positive/negative test even without sign() (i.e. seq - 100 > 0 or seq - 100
select
case when sign(seq - 100) > 0 then ‘next’ else ‘prev’ end as dir,
case when sign(seq - 100) > 0 then min(seq) else max(seq) end as seq
from t1log
where t1 = 5
and seq 100
group by sign(seq - 100);
is sufficient.
order by clause is not required.
Love it!
This does not work on mysql > 5. Only on 4 versions or under.
In 5 it only and always returns next value.
Any help ?
It works fine for me on MySQL 5.0.45:
mysql> select version(); +------------------------------+ | version() | +------------------------------+ | 5.0.45-Debian_1ubuntu3.1-log | +------------------------------+ 1 row in set (0.00 sec) mysql> create table t1log(t1 int, seq int); Query OK, 0 rows affected (0.01 sec) mysql> insert into t1log values(5,98),(5,99),(5,100),(5,101),(5,105); Query OK, 5 rows affected (0.00 sec) Records: 5 Duplicates: 0 Warnings: 0 mysql> select * from t1log; +------+------+ | t1 | seq | +------+------+ | 5 | 98 | | 5 | 99 | | 5 | 100 | | 5 | 101 | | 5 | 105 | +------+------+ 5 rows in set (0.00 sec) mysql> select -> case when sign(seq - 100) > 0 then 'next' else 'prev' end as dir, -> case when sign(seq - 100) > 0 then min(seq) else max(seq) end as seq -> from t1log -> where t1 = 5 -> and seq <> 100 -> group by sign(seq - 100) -> order by sign(seq - 100); +------+------+ | dir | seq | +------+------+ | prev | 99 | | next | 101 | +------+------+ 2 rows in set (0.00 sec)CREATE TABLE `acores_imagens` (
`imgid` mediumint(6) unsigned NOT NULL auto_increment,
`imguser` mediumint(6) unsigned NOT NULL default ‘0′,
`imgpequena` varchar(25) NOT NULL default ”,
`imggrande` varchar(25) NOT NULL default ”,
`cat` tinyint(2) unsigned NOT NULL default ‘0′,
`imgdata` datetime NOT NULL default ‘0000-00-00 00:00:00′,
`vis` mediumint(6) unsigned NOT NULL default ‘0′,
`descricao` varchar(150) NOT NULL default ”,
`palavraschave` varchar(40) NOT NULL default ”,
`rating` mediumint(4) unsigned NOT NULL default ‘0′,
`rating_votes` mediumint(2) unsigned NOT NULL default ‘0′,
`nc` tinyint(3) unsigned NOT NULL default ‘0′,
PRIMARY KEY (`imgid`),
KEY `imguser` (`imguser`),
KEY `cat` (`cat`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1 AUTO_INCREMENT=379122 ;
INSERT INTO `acores_imagens` (`imgid`, `imguser`, `imgpequena`, `imggrande`, `cat`, `imgdata`, `vis`, `descricao`, `palavraschave`, `rating`, `rating_votes`, `nc`) VALUES
(1, 1, ‘bla’, ‘bla’, 0, ‘0000-00-00 00:00:00′, 0, ”, ”, 0, 0, 0),
(2, 1, ”, ”, 0, ‘0000-00-00 00:00:00′, 0, ”, ”, 0, 0, 0),
(3, 1, ”, ”, 0, ‘0000-00-00 00:00:00′, 0, ”, ”, 0, 0, 0),
(4, 1, ”, ”, 0, ‘0000-00-00 00:00:00′, 0, ”, ”, 0, 0, 0),
(5, 1, ”, ”, 0, ‘0000-00-00 00:00:00′, 0, ”, ”, 0, 0, 0),
(379121, 0, ”, ‘6′, 1, ‘0000-00-00 00:00:00′, 0, ”, ”, 0, 0, 0);
select
case when sign(imgid - 3) > 0 then ‘next’ else ‘prev’ end as dir,
case when sign(imgid - 3) > 0 then min(imgid) else max(imgid) end as imgid
from acores_imagens
where imguser = ‘1′
and imgid ‘3′
group by sign(imgid - 3)
order by sign(imgid - 3);
in mysql 4.1.22 i got correct results:
dir | imgid
prev | 2
next | 4
in mysql 5.0.48 i got this..
dir | imgid
next | 1
:\\\
Unless the comment form has mangled your reply, the problem is this line:
and imgid ‘3′
That’s invalid SQL. If I change it to this, it’s still a problem:
and imgid = ‘3′
Why? Because it limits the input to the GROUP BY to one row. You can’t find the next and previous in this case, because there’s only one row.
To see the effect this has, run the query without the GROUP BY clause.
Why this worked on 4.1 I don’t know, but I suspect a bug.
Sorry
I copied the wrong code
The correct code that i tested was:
select
case when sign(imgid - 4) > 0 then ‘next’ else ‘prev’ end as dir,
case when sign(imgid - 4) > 0 then min(imgid) else max(imgid) end as imgid
from acores_imagens where imguser=1 and imgid 4
group by sign(imgid - 4)
order by sign(imgid - 4);
But i still got one row in mysql 5.0.48 and 2 rows(correct) on other versions. Can this be a 5.0.48 bug ? I’ve search for bugs on this perticular version but i didn’t find one that could match to this kinds of querys :\
Argh.. the script cuts me alot of code..
Here is the really correct code i used:
http://www.acores.net/code.txt
In which place? Can you rewrite the query or part of the query and get the same results? If it’s simpler, I’m all for it…
I’ve done something similiar with:
SELECT table.*, next.id AS next_id, prev.id AS prev_id
FROM table
LEFT JOIN table AS next ON next.position > table.position
LEFT JOIN table AS prev ON prev.position < table.position
WHERE table.id = 21
ORDER BY position LIMIT 1;
correction on my last post… The query is incorrect. It will always return the first record as the prev_id… I had to add another ORDER BY on the end
Here’s the updated query:
SELECT table.*, next.id AS next_id, prev.id AS prev_id
FROM table
LEFT JOIN table AS next ON next.position > table.position
LEFT JOIN table AS prev ON prev.position
Brilliant solution - clever SQL, very nice!
Darn! I swear I keep posting the complete query….
SELECT table.*, next.id AS next_id, prev.id AS prev_id
FROM table
LEFT JOIN table AS next ON next.position > table.position
LEFT JOIN table AS prev ON prev.position
Ok… I’ll try encoding the >’s and <’s….
SELECT table.*, next.id AS next_id, prev.id AS prev_id
FROM table
LEFT JOIN table AS next ON next.position > table.position
LEFT JOIN table AS prev ON prev.position < table.position
WHERE table.id = ?
ORDER BY position ASC, prev_id DESC LIMIT 1;
To Anthony Altemara
Your query doesn’t work if we use it for last element. Query returns just empty :-(
To Xaprb
I have MySql of 5.0.44 version and your method doesn’t work. So I found the error when I make a query like this:
SELECT t1, sign(t1-100), t1-100 FROM table
And I received something like that:
98 | 1 | 18446744073709551613
99 | 1 | 18446744073709551612
101 | 1 | 1
102 | 1 | 2
..etc..
So I solved the problem when I take off an “unsigned” flag for the id column (sh*t, MySql Query Browser uses it by default!).
And so I see X-Crap has a similar problem when he creates table:
CREATE TABLE `acores_imagens` (
`imgid` mediumint(6) unsigned NOT NULL auto_increment,
To: soid
Thanks! I see the problem. I think what I need instead of a LEFT JOIN, is a FULL OUTER JOIN. The corrected query would be…
SELECT table.*, next.id AS next_id, prev.id AS prev_id
FROM table
FULL OUTER JOIN table AS next ON next.position > table.position
FULL OUTER JOIN table AS prev ON prev.position < table.position
WHERE table.id = ?
ORDER BY position ASC, prev_id DESC LIMIT 1;
Note: This is UNTESTED…