Oh, Mighty LJ Brain: SQL for "next" and "previous" entries?

[elfs]

Oh, mightly LJ brain, riddle me this:

I have a table in a MySQL (well, okay, it's Sqlite3 right now, but it'll my MySQL in production) database, and the primary keys are known to not be contiguous. That's important.

It's possible to construct a WHERE clause giving you a single item, if that items qualties are unique enough. Is it possible, using some magic combination of WHERE and ORDER BY and something I don't know, to say "give me unique item N, and using the rule of the ORDER BY clause, also give me the next and previous objects?"

Comments

[zanfur.livejournal.com]

I've had to deal with this exact problem. Assuming that the "next" and "previous" semantics refer to "next larger" and "next smaller" primary key values, it's done by using multiple selects. This is a limitation of the relational algebra; I don't think there's a way around it. You first need the id of unique item X, then you need the max(id)<X and the min(id)>X, which is a select for the original id (however you get it), a select for the aggregate max(), and a select for the aggregate min().

Basically:

select max(id) from items where id < X;
select min(id) from items where id > X;

It's constant time if you have btree indexes for the primary key. Don't use a hash index, even though it might make otherwise sense for non-contiguous data. The MySQL compiler should realize that this is a simple btree lookup, and not even bother scanning. You *can* combine the two aggregate functions into a single query using a GROUP BY clause on a calculated field...but don't. It's horribly inefficient for large tables. Just use the separate queries above, which are optimized into simple index lookups:

mysql> explain select max(id) previd from items where id<11;
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra                        |
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+
|  1 | SIMPLE      | NULL  | NULL | NULL          | NULL | NULL    | NULL | NULL | Select tables optimized away | 
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+
1 row in set (0.00 sec)

If you want it all in a single DB call, use a stored procedure -- then you can just call the stored procedure with the itemid in question (this is what I recommend):

DELIMITER //
CREATE PROCEDURE prevcurnext_items(
  IN itemid INT
)
BEGIN
  DECLARE previd INT;
  DECLARE nextid INT;
  SELECT max(id) INTO previd FROM items WHERE id < itemid;
  SELECT min(id) INTO nextid FROM items WHERE id > itemid;
  SELECT * FROM items WHERE id in (previd,itemid,nextid);
END//
DELIMITER ;

Hope this helps somewhat.

(I actually tested all of the above code, using a test items table that had an INT "id" field and a "content" field, with the first 10 prime numbers as the id's and the first ten letters as the content, on MySQL 5.0.)

[zanfur.livejournal.com]

If you're fine using subselects, this works like a champ, with N being the id of the unique item in question:

select * from items where id >= (select max(id) from items where id < N) limit 3

The subselect is (as above) is optimized away to a constant-time index lookup, and the item retrieval is done by walking along the index (signified by the type of "range"), making it also constant-time:

mysql> explain select * from items where id >= (select max(id) from items where id < 11) limit 3;
+----+-------------+-------+-------+---------------+---------+---------+------+------+------------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra                        |
+----+-------------+-------+-------+---------------+---------+---------+------+------+------------------------------+
|  1 | PRIMARY     | items | range | PRIMARY       | PRIMARY | 4       | NULL |    7 | Using where                  | 
|  2 | SUBQUERY    | NULL  | NULL  | NULL          | NULL    | NULL    | NULL | NULL | Select tables optimized away | 
+----+-------------+-------+-------+---------------+---------+---------+------+------+------------------------------+
2 rows in set (0.00 sec)

(I say "constant time"...btree lookups are actually O(logN), but with a *very* high logarithmic base. Also, the entire index is usually in memory, so it's blazingly fast even for millions of rows in the table.)

+1 upvote :-)

[(Anonymous)]

--Cat Typist