How to find next and previous records in SQL at Xaprb

How to find next and previous records in SQL

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?

Written by Xaprb

April 28th, 2006 at 9:43 pm

Posted in SQL

30 Responses to 'How to find next and previous records in SQL'

Subscribe to comments with RSS

Wow, respect! I found this article very useful – all in one. Thanks a lot.

Anonymous

5 Jul 06 at 7:46 am
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?

Keith

3 Apr 07 at 4:23 pm
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.

Xaprb

3 Apr 07 at 4:50 pm
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

Jeff

15 May 07 at 3:45 am
Amazing tip, very usefull i spend alot of time researching a way to do this. Very good :) Thanks.

CÃ©sar Couto

6 Sep 07 at 8:11 am
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.

Francesco

30 Oct 07 at 6:05 pm
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.

Xaprb

30 Oct 07 at 8:24 pm
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

Francesco

31 Oct 07 at 3:33 am
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.

Kapil

1 Dec 07 at 5:19 pm
Love it!

SeC

12 Dec 07 at 1:22 am
This does not work on mysql > 5. Only on 4 versions or under.
In 5 it only and always returns next value.
Any help ?

|X-Crap|

28 Dec 07 at 10:42 am

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)

Xaprb

28 Dec 07 at 11:06 am

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

:\

|X-Crap|

28 Dec 07 at 12:25 pm
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.

Xaprb

28 Dec 07 at 12:46 pm
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 :\

|X-Crap|

28 Dec 07 at 12:55 pm
Argh.. the script cuts me alot of code..
Here is the really correct code i used:

http://www.acores.net/code.txt

|X-Crap|

28 Dec 07 at 12:58 pm
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…

Almanca tercÃ¼man

15 Jan 08 at 11:33 am
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;

Anthony Altemara

26 Feb 08 at 1:40 pm
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

Anthony Altemara

26 Feb 08 at 2:10 pm
Brilliant solution – clever SQL, very nice!

Loughlin McSweeney

30 Mar 08 at 2:53 pm
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

Anthony Altemara

30 Mar 08 at 3:15 pm
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;

Anthony Altemara

30 Mar 08 at 3:23 pm
To Anthony Altemara

Your query doesn’t work if we use it for last element. Query returns just empty :-(

soid

6 May 08 at 9:21 am
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,

soid

6 May 08 at 10:06 am
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…

Anthony

6 May 08 at 2:22 pm
Luckly I bookmarked this topic.

Man, I’d be very grateful if you could help me to adpat this solution to my table, even in MySQL 5+, I’m not very familiar wity queries.

The table:

id (primary key unsigned id)
dt (datetime)

The order of the elements (sign) is by “dt”.

I’d like to get next/prev id’s given an id, based upon “dt” sorting.

Example:

id | dt
————————-
1 | ‘2007-09-17 17:20:00′
2 | ‘2007-09-17 17:22:00′
3 | ‘2007-09-17 17:10:00′
4 | ‘2007-09-17 17:28:00′
5 | ‘2007-09-17 17:27:00′

Thanks very much for any help.

Francesco

9 Oct 08 at 8:42 am
Xaprb; great solution! I was working on a similiar query for a PHP Image gallery; while sucessful, I was using subqueries and etc. It is truly a pleasure to see ppl still cutting SQL to this degree of elegance! Wish I’d seen this article before :)

Cheers

Dan

8 Mar 09 at 1:38 pm
I have another similar situation but I can’t seem to add the extra columns in. I have a table with column id, cost, date. I want to pull the previous record for that id on that date. Basically, I want to bring in the id, cost date column and then add 2 more columns such as prev date and prev cost.

Example:

Id Date Cost PrevDate PrevCost
123 3/2/09 $14 2/2/09 $12
123 2/2/09 $12 1/2/09 $10
123 1/2/09 $10
167 3/3/09 $20 1/2/09 $15
167 1/2/09 $15

Thanks very much for any help.

Jen

10 Mar 09 at 7:21 pm
CREATE PROCEDURE dbo.[GetPrevNext]
@CityID INT,
@LocationID INT
AS
DECLARE
@Prev INT,
@Next INT,
@Row INT,
@Rows INT
BEGIN
SET NOCOUNT ON
DECLARE @locations TABLE (Row INT IDENTITY(1, 1), LocationID INT)

INSERT @locations
select
– to add and order by enable this
– and disable identit on row column in temp table
–Row = ROW_NUMBER() OVER (ORDER BY A.LocationID ASC),
LocationID = A.LocationID
from
Gmap_Locations AS A
where
A.CityID = @CityID

SET NOCOUNT OFF

SET @Rows = (SELECT COUNT(*) FROM @locations)

– set currunt
if(@LocationID = 0 or @LocationID is null)
BEGIN
SET @LocationID = null
END

IF(@Rows > 0 and @Rows is not null)
BEGIN
print ‘Row Count = ‘ + CONVERT(NVARCHAR(100), @Rows)

– find the current row
SET @Row = (SELECT A.Row FROM @locations as A WHERE A.LocationID = @LocationID)
print ‘Row number = ‘ + CONVERT(NVARCHAR(100), @Row)

– find prev location
if(@Row = 1)
begin
set @Prev = null
end
else
begin
set @Prev = (select A.LocationID from @locations as A where A.Row = @Row – 1)
end

– find next location
if(@Rows = 1)
begin
set @Next = null
end
else
begin
set @Next = (select A.LocationID from @locations as A where A.Row = @Row + 1)
end
END

– Return values
SELECT PrevLocation = @Prev, CurrentLocation = @LocationID, NextLocation = @Next
END
GO
EXEC dbo.[GetPrevNext] @CityID = 3022, @LocationID = 6535

–locationIDs for testing
–28941
–20990
–57976
–5744
–6535

tSQL

12 Aug 09 at 9:25 am
SELECT id FROM table_name WHERE primarykey 5 ORDER BY ID LIMIT 1

Feroz

16 Feb 10 at 7:53 pm

Xaprb