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

Item N, N+-1

[(Anonymous)]

sqlite> create table t(i int);
sqlite> insert into t values(1);
sqlite> insert into t values(2);
sqlite> insert into t values(3);
sqlite> insert into t values(4);
sqlite> insert into t values(6);
sqlite> insert into t values(7);
sqlite> insert into t values(10);
sqlite> insert into t values(11);
sqlite> select b.i,count(*) from t a join t b on a.i<b.i group by b.i;
i|count(*)
2|1
3|2
4|3
6|4
7|5
10|6
11|7
sqlite> select * from (select b.i,count(*) as N from t a join t b on a.i<b.i group by b.i) x where x.N=3;
i|N
4|3

Now ask for N+1 and N-1.

Re: Item N, N+-1

[(Anonymous)]

Oh, the derived table is necessary in sqlite, but IIRC not in ANSI-SQL compatible databases.

Re: Item N, N+-1

[zanfur.livejournal.com]

This is insanely inefficient, and simply unworkable for large datasets.

Re: Item N, N+-1

[zanfur.livejournal.com]

This is also incorrect. It chops off the lowest item (id "1" is missing from the output above, even). You can make it correct by changing the "<" to "<=". Observe:

mysql> create table t(i int primary key);
Query OK, 0 rows affected (0.01 sec)

mysql> insert into t values (1),(2),(3),(4),(6),(7),(10),(11);
Query OK, 8 rows affected (0.00 sec)
Records: 8  Duplicates: 0  Warnings: 0

mysql> select b.i,count(*) from t a join t b on a.i<=b.i group by b.i;
+----+----------+
| i  | count(*) |
+----+----------+
|  1 |        1 | 
|  2 |        2 | 
|  3 |        3 | 
|  4 |        4 | 
|  6 |        5 | 
|  7 |        6 | 
| 10 |        7 | 
| 11 |        8 | 
+----+----------+
8 rows in set (0.01 sec)

mysql> explain select b.i,count(*) from t a join t b on a.i<=b.i group by b.i;
+----+-------------+-------+-------+---------------+---------+---------+------+------+----------------------------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra                                        |
+----+-------------+-------+-------+---------------+---------+---------+------+------+----------------------------------------------+
|  1 | SIMPLE      | a     | index | PRIMARY       | PRIMARY | 4       | NULL |    8 | Using index; Using temporary; Using filesort | 
|  1 | SIMPLE      | b     | index | PRIMARY       | PRIMARY | 4       | NULL |    8 | Using where; Using index                     | 
+----+-------------+-------+-------+---------------+---------+---------+------+------+----------------------------------------------+
2 rows in set (0.00 sec)

mysql> select * from (select b.i,count(*) as N from t a join t b on a.i<=b.i group by b.i) x where x.N=3;
+---+---+
| i | N |
+---+---+
| 3 | 3 | 
+---+---+
1 row in set (0.00 sec)

mysql> explain select * from (select b.i,count(*) as N from t a join t b on a.i<=b.i group by b.i) x where x.N=3;
+----+-------------+------------+-------+---------------+---------+---------+------+------+----------------------------------------------+
| id | select_type | table      | type  | possible_keys | key     | key_len | ref  | rows | Extra                                        |
+----+-------------+------------+-------+---------------+---------+---------+------+------+----------------------------------------------+
|  1 | PRIMARY     | <derived2> | ALL   | NULL          | NULL    | NULL    | NULL |    8 | Using where                                  | 
|  2 | DERIVED     | a          | index | PRIMARY       | PRIMARY | 4       | NULL |    8 | Using index; Using temporary; Using filesort | 
|  2 | DERIVED     | b          | index | PRIMARY       | PRIMARY | 4       | NULL |    8 | Using where; Using index                     | 
+----+-------------+------------+-------+---------------+---------+---------+------+------+----------------------------------------------+
3 rows in set (0.00 sec)

Note also that it's horribly inefficient, requiring an O(N²) calculation on the entire index to get the position field, and then -- here's the really horrible part -- scanning the entire derived table for specific values, which is unindexed. I strongly recommend against this approach. Especially because you typically want to find "next" and "prev" id's for forward and back links, which means on *every* page view of a potentially large corpus.

Re: Item N, N+-1

[(Anonymous)]

select b.i,count(*) as N from t a join t b on a.i<=b.i group by b.i having N=3;

No derived table necessary, as stated above.