Based on your assumptions being correct
(a) start is unique
(b) start end ranges do not overlap
create table ranges
(
start integer primary key,
stop integer not null,
value integer not null
);
INSERT INTO ranges values (1, 10, 5);
INSERT INTO ranges values (15, 29, 8);
INSERT INTO ranges values (30, 32, 9);
select value
from (select stop, value
from ranges
where start <= ?1
order by start desc
limit 1)
where ?1 <= stop;
If your data does not meet the constraints you have specified then the query
will not work properly. The resulting value (if there is one) will be returned
with a single index lookup and a single comparison. (Note that you can create
a covering index on your existing table if you do not want to remake it).
This works as it does because the answer, if there is one, can only be located
on the row where start <= ?1 (for the biggest numerical value of start) and
then only if the correspondingly found row also meets the requirement that ?1
<= stop
Python 3.7.0 (v3.7.0:1bf9cc5093, Jun 27 2018, 04:59:51) [MSC v.1914 64 bit
(AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import apsw
>>> db = apsw.Connection(':memory:')
>>>
>>> create_sql = """create table ranges
... (
... start integer primary key,
... stop integer not null,
... value integer not null
... );
...
... INSERT INTO ranges values (1, 10, 5);
... INSERT INTO ranges values (15, 29, 8);
... INSERT INTO ranges values (30, 32, 9);
... """
>>>
>>> sql = """select value
... from (select stop, value
... from ranges
... where start <= ?1
... order by start desc
... limit 1)
... where ?1 <= stop;
... """
>>>
>>> db.execute(create_sql)
<apsw.Cursor object at 0x0000020F7EB583F0>
>>> for row in db.execute('select * from ranges;'):
... print(row)
...
Row(start=1, stop=10, value=5)
Row(start=15, stop=29, value=8)
Row(start=30, stop=32, value=9)
>>> for i in range(35):
... for row in db.execute(sql, (i, )):
... print(i, row)
...
1 Row(value=5)
2 Row(value=5)
3 Row(value=5)
4 Row(value=5)
5 Row(value=5)
6 Row(value=5)
7 Row(value=5)
8 Row(value=5)
9 Row(value=5)
10 Row(value=5)
15 Row(value=8)
16 Row(value=8)
17 Row(value=8)
18 Row(value=8)
19 Row(value=8)
20 Row(value=8)
21 Row(value=8)
22 Row(value=8)
23 Row(value=8)
24 Row(value=8)
25 Row(value=8)
26 Row(value=8)
27 Row(value=8)
28 Row(value=8)
29 Row(value=8)
30 Row(value=9)
31 Row(value=9)
32 Row(value=9)
>>>
---
The fact that there's a Highway to Hell but only a Stairway to Heaven says a
lot about anticipated traffic volume.
>-----Original Message-----
>From: sqlite-users [mailto:sqlite-users-
>boun...@mailinglists.sqlite.org] On Behalf Of siscia
>Sent: Friday, 26 October, 2018 01:27
>To: sqlite-users@mailinglists.sqlite.org
>Subject: Re: [sqlite] Optmize queries on ranges
>
>Hi all,
>
>thanks for your suggestions, unfortunately, I already tried all of
>them,
>except for the rtrees.
>
>Actually, my request for help wasn't complete.
>
>The ranges I am storing in the table are not overlapping.
>
>To make an example in SQL.
>
>The following can be in the dataset:
>INSERT INTO ranges(1, 10, 5);
>INSERT INTO ranges(15, 29, 8);
>INSERT INTO ranges(30, 32, 9);
>
>However, there will never be something like:
>INSERT INTO ranges(1, 10, 5);
>INSERT INTO ranges(5, 15, 8); -- impossible, overlap with the first
>one
>
>So all the queries are actually:
>
>`SELECT value FROM ranges WHERE (? BETWEEN start AND end) LIMIT 1`
>
>Now suppose there is an index on start and so we are looking for
>(start < ?)
>
>What happen could be that we begin from (start = 0) and move up to
>(start <=
>?) which is basically a full scan.
>Or we could begin from (start <= ?) and move down towards (start = 0)
>which
>would be optimal.
>
>I am afraid that we are hitting the first case, which really is a
>pity.
>
>Is there a way to suggest to the index how to work on these cases?
>
>Cheers,
>
>Simone
>
>
>
>
>
>
>
>--
>Sent from: http://sqlite.1065341.n5.nabble.com/
>_______________________________________________
>sqlite-users mailing list
>sqlite-users@mailinglists.sqlite.org
>http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
