On Tue, Dec 14, 2010 at 05:09:04PM +0000, Simon Slavin wrote:
> I recently found out that when you use LIMIT in SQLite the engine
> still processes all applicable records even if it only has to return
> the number you asked for. I suspect that this makes something I used
> to do inefficient. So let me ask for what I want and see what the
> list comes up with.
>
> I start with three things:
>
> * an arbitrary table which definitely has an explicitly defined field
> 'id' which is always an alias to SQLite's use of 'rowid'. The table
> may have tens of thousands of rows.
>
> * the value of 'id' of a particular record
Use this to get the values of the columns desired for the ORDER BY.
> * an ORDER BY string that can be applied to this table, e.g.
> 'surname,age DESC'
Once you have those values do two SELECTs. One SELECT will be for the
desired ORDER BY with WHERE matching all rows that would match the rows
following the one whose id you have, LIMIT 1. You can build the WHERE
expressions based on the columns retrieved in the above step. The other
SELECT will have the sort order in the ORDER BY reversed, and the
matching direction in the WHERE expressions reversed as well.
E.g.,
CREATE TABLE toy(id integer primary key, a int, b int, c int);
CREATE INDEX toy_abc ON toy (a ASC, b DESC, c ASC);
INSERT INTO toy (a, b, c) VALUES (random(), random(), random());
INSERT INTO toy (a, b, c) VALUES (random(), random(), random());
INSERT INTO toy (a, b, c) VALUES (random(), random(), random());
INSERT INTO toy (a, b, c) VALUES (random(), random(), random());
INSERT INTO toy (a, b, c) VALUES (random(), random(), random());
INSERT INTO toy (a, b, c) VALUES (random(), random(), random());
INSERT INTO toy (a, b, c) VALUES (random(), random(), random());
INSERT INTO toy (a, b, c) VALUES (random(), random(), random());
INSERT INTO toy (a, b, c) VALUES (random(), random(), random());
INSERT INTO toy (a, b, c) VALUES (random(), random(), random());
INSERT INTO toy (a, b, c) VALUES (random(), random(), random());
INSERT INTO toy (a, b, c) VALUES (random(), random(), random());
INSERT INTO toy (a, b, c) VALUES (random(), random(), random());
INSERT INTO toy (a, b, c) VALUES (random(), random(), random());
SELECT * FROM toy ORDER BY a ASC, b DESC, c ASC LIMIT 1;
7|-9084516558209846371|5509077441613329789|-6039970258732513679
4|-8048386703128611944|6994995616875512667|8999476370168858025
3|-7424117500756575148|4942101875445443496|1450545533195196343
8|-5743400534550269237|389208812082260818|-6076412160162338146
5|-5670534775733401701|1663837058082466530|-4342108509867877155
6|-3182970629602473541|-5223987460270046935|1484365513264068016
1|-3041202902673535746|-2810235477737418946|-6552445179965515592
12|-2658836410255605115|1738314160220639562|-5959979395208249554
11|-189594377855007160|-8847915915461491005|3035343813815035327
9|61938152197633097|23466571579391398|5202656507889790288
2|872885551150985642|-6337095019136234251|-283494106466248099
14|3088016326372574532|-562863847042835080|-7774010663666943917
13|4053781913908032366|297289804958612507|3778649002432168869
10|7412852161679323896|-1652518713928674542|2034739374121838177
-- given row id, say, 6, get the values we need below
SELECT a, b, c FROM toy WHERE id = 6;
-- Just for this example I'm not using '?', so you can try it with the
-- command shell.
-- Get the row id of the row immediately following the above row:
SELECT * FROM toy
WHERE
a >= (SELECT a FROM toy WHERE id = 6) OR
(a = (SELECT a FROM toy WHERE id = 6) AND
b <= (SELECT b FROM toy WHERE id = 6)) OR
(a = (SELECT a FROM toy WHERE id = 6) AND
b = (SELECT b FROM toy WHERE id = 6) AND
c >= (SELECT c FROM toy WHERE id = 6))
ORDER BY a ASC, b DESC, c ASC LIMIT 1 OFFSET 1;
-- the above returns:
1|-3041202902673535746|-2810235477737418946|-6552445179965515592
-- get the row id of the row immediately preceding it:
SELECT * FROM toy
WHERE
a <= (SELECT a FROM toy WHERE id = 6) OR
(a = (SELECT a FROM toy WHERE id = 6) AND
b >= (SELECT b FROM toy WHERE id = 6)) OR
(a = (SELECT a FROM toy WHERE id = 6) AND
b = (SELECT b FROM toy WHERE id = 6) AND
c <= (SELECT c FROM toy WHERE id = 6))
ORDER BY a DESC, b ASC, c DESC LIMIT 1 OFFSET 1;
-- which return:
5|-5670534775733401701|1663837058082466530|-4342108509867877155
Now check the query plan. I get this sort of thing:
0 0 TABLE toy VIA MULTI-INDEX UNION
0 0 TABLE toy WITH INDEX toy_abc
0 0 TABLE toy USING PRIMARY KEY
0 0 TABLE toy WITH INDEX toy_abc
0 0 TABLE toy USING PRIMARY KEY
0 0 TABLE toy USING PRIMARY KEY
0 0 TABLE toy WITH INDEX toy_abc
0 0 TABLE toy USING PRIMARY KEY
0 0 TABLE toy USING PRIMARY KEY
0 0 TABLE toy USING PRIMARY KEY
Which looks about right.
> I can guarantee that there is an index on whatever my ORDER BY string
> is.
Yes, you need that.
> What I want: to be able to find the ids of the records before and
> after the one I have.
See above. I think the above should work and be efficient given the
necessary indexes.
Nico
--
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
