Re: [sqlite] Optmize queries on ranges

[Keith Medcalf]

You also need to make sure the "no hit" does not degenerate into a table scan.  
RTree works well for this but is overall significantly slower than not using 
RTree since the purpose of RTree is to find the "small number of candidate 
records" that could possibly satisfy the query out of a haystack of records 
(that is, find the candidate needles in the haystack, so that you only need to 
closely examine that small number of candidates to find the needle rather than 
test the whole haystack).  

However, if you know that there can only be one possible record which can 
satisfy the query (ie, there is only one possible needle in the haystack, and 
only one possible candidate, and you can find this candidate directly for 
testing), then the overhead of using RTree where it is not needed exceeds the 
benefits of using it.

I see that the performance of the RTree is significantly slower than the 
equivalent "direct" method.  Am I doing something wrong here or is that 
overhead simply because of the data structures that the RTRee implementation 
must maintain (which are not required in this case).

Without RTree:
>py -3 test.py
Created 10 random ranges in 00:00:00.681118 Creation Rate = 146817 
Ranges/Second
Looked up 1102019 random range values in 00:00:04.598245 Lookup Rate = 239660 
Values/Second
Failure Rate = 257270 Values/Second
Success Rate = 228828 Values/Second

With RTree:
>py -3 test.py --rtree
Created 10 random ranges in 00:00:02.139742 Creation Rate = 46734 
Ranges/Second
Looked up 1100681 random range values in 00:00:13.662556 Lookup Rate = 80561 
Values/Second
Failure Rate = 119874 Values/Second
Success Rate = 65627 Values/Second

And that came from the following test program (in python) where the only 
difference is the SQL statements being used.  Because the ranges are random and 
the lookups are random, the timings given are subject to differences on every 
run, however, the averaged rates are relatively stable given a large number of 
random ranges and query values.

--- test.py ---
from __future__ import absolute_import, division, print_function, 
unicode_literals

import datetime
import random
import sys
import time

import sqlite3

# Convert a value in seconds to HMS format
HMS = lambda t: (datetime.datetime.min + 
datetime.timedelta(seconds=t)).time().isoformat()

# Create constants for the SQL statements we will use

if '--rtree' in sys.argv:
create_sql = 'create virtual table ranges using rtree(id, start, stop, 
+value);'
query_sql = 'select value from ranges where ? between start and stop;'
else:
create_sql = 'create table ranges (start integer primary key, stop integer 
not null, value integer not null);'
query_sql = 'select value from (select stop, value from ranges where start 
<= ?1 order by start desc limit 1) where ?1 <= stop;'

insert_sql = 'insert into ranges (start, stop, value) values (?, ?, ?);'


# Open our database and do not use automagical transactions
db = sqlite3.connect(':memory:', isolation_level=None)

# Create our table
db.execute(create_sql)

# Create our random range data
recs = 10
start = 0
st = time.time()
for cnt in range(recs):
start += random.randint(1, 10)
stop = start + random.randint(1, 10)
value = int((start + stop) / 2)
db.execute(insert_sql, (start, stop, value))
start = stop
stop = stop + random.randint(1, 10)
et = time.time() - st
print('Created', recs, 'random ranges in', HMS(et), 'Creation Rate =', int(recs 
/ et), 'Ranges/Second')

db.execute('analyze;')

# Generate a bunch of random values and perform the range query
eta = 0.0
ets = 0.0
etf = 0.0
fcnt = 0
scnt = 0
tcnt = 0
for i in range(stop):
x = random.randint(0, stop)
lst = time.time()
row = db.execute(query_sql, (x, )).fetchone()
let = time.time() - lst
if row:
value = row[0]
ets += let
scnt += 1
else:
value = None
etf += let
fcnt += 1
eta += let
tcnt += 1
print('Looked up', stop, 'random range values in', HMS(eta), 'Lookup Rate =', 
int(tcnt / eta), 'Values/Second')
print('Failure Rate =', int(fcnt / etf), 'Values/Second')
print('Success Rate =', int(scnt / ets), 'Values/Second')

---
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 E.Pasma
>Sent: Friday, 26 October, 2018 16:28
>To: SQLite mailing list
>Subject: Re: [sqlite] Optmize queries on ranges
>
>About the rtree extension, which was the first idea.
>
>The extension appears available without any special installation
>option. This is easier than what is mentioned in
>https://sqlite.org/rtree.html  chapter
>2: "Compiling The R*Tree Module".
>This chapter may as well be left out?
>
>With test data where the ranges are mostly non-overlapping, the query
>now runs faster than without rtree. Even 

Re: [sqlite] Optmize queries on ranges

[E.Pasma]

About the rtree extension, which was the first idea.

The extension appears available without any special installation option. This 
is easier than what is mentioned in https://sqlite.org/rtree.html 
 chapter 2: "Compiling The R*Tree Module". 
This chapter may as well be left out?

With test data where the ranges are mostly non-overlapping, the query now runs 
faster than without rtree. Even though both run within a millisecond rtree is 
ten times faster.
With order by and limit the timing remains superior. But this relies on 
strictly non-overlapping ranges.
Below my test script


/* query 1: using rtree built-in extension */
;
create virtual table ranges using rtree(id, minX, maxX, +value);
with r as (select 0 as r union all select r+1 from r where r<100)
insert into ranges (minX, maxX, value) 
select r*10+1,r*10+10,r*10+5 from r
;
select value from ranges where 123456 between minx and maxx
;
123455
Run Time: real 0.000 user 0.000135 sys 0.18

/* query 2: using index on minx+maxx */
drop table ranges
;
create table ranges (minx int, maxx int, value int)
;
with r as (select 0 as r union all select r+1 from r where r<100)
insert into ranges (minX, maxX, value) 
select r*10+1,r*10+10,r*10+5 from r
;
create unique index ranges_minx_maxx on ranges(minx,maxx)
;
select value from ranges where 123456 between minx and maxx
;
123455
Run Time: real 0.002 user 0.001415 sys 0.16

/* query 3: same, assuming non-overlapping ranges */
select value from ranges where 123456 between minx and maxx
order by minx desc limit 1
;
123455
Run Time: real 0.000 user 0.57 sys 0.00

 

___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Exception handling during create table from a virtual one

[Max Vlasov]

On Fri, Oct 26, 2018 at 5:50 PM Clemens Ladisch  wrote:

> > Аfter the exception is thrown 
> >  If I continue the execution
>
> You must return from the callback function normally, or abort the process.
> Anything else will corrupt SQLite's internal state.
>
>
Thanks, probably it's better for me to wrap any sensitive callback handler
in an exception catcher with SQLITE_ERROR code return.
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Regarding CoC

[Petite Abeille]

> On Oct 26, 2018, at 3:21 PM, Thomas Kurz  wrote:
> 
>> What'da ya think?
> 
> That's a great idea. I've already had some concerns that SQLite development 
> might cease now. Hoping for great new features in the next release :-)

MERGE! :D

___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Invalid results on join and duplicate where clause (in-memory db only)

[Richard Hipp]

On 10/26/18, Sebastian Zwack  wrote:
>
> Out of curiosity, why do in-memory and file based differ here? Are these
> query optimizations only done for the in-memory db?
>

I observe the problem regardless of whether the database is on-disk or
in-memory.  Perhaps your system is somehow using a different (older)
version of SQLite that predates the problem when accessing database
file from disk?

-- 
D. Richard Hipp
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Invalid results on join and duplicate where clause (in-memory db only)

[Sebastian Zwack]

On Thu, Oct 25, 2018, at 16:20, Richard Hipp wrote:
> Sebastian:  Presumably this problem arose for you in a much larger and
> more complex application.  Can you please apply the patch from the
> check-in above (or recompile using the latest trunk version of SQLite)
> and verify for us that this fixes the problem for you?
> 

You're right, of course the origin is an ORM generating this duplicate clauses. 
And as I couldn't think of a bug in sqlite it took me some time to narrow that 
down.

Can confirm, this patch fixes the problem for me and my tests are running fine 
again.

Out of curiosity, why do in-memory and file based differ here? Are these query 
optimizations only done for the in-memory db?

Thanks,
Sebastian
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Exception handling during create table from a virtual one

[Clemens Ladisch]

Max Vlasov wrote:
> I have a virtual table that raises an unhandled exception during a create
> table

SQLite is written in C.  The C language does not have exceptions.

> Аfter the exception is thrown 
>  If I continue the execution

You must return from the callback function normally, or abort the process.
Anything else will corrupt SQLite's internal state.


Regards,
Clemens
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Using SQLite in C# without System.Data.SQLite

[Bernd Lehmkuhl]

Thank you so much for your reply. I sill surely look at the options you 
gave me.



I ask because I run into errors a lot, using the System.Data.SQLite 
libraries. It easily crashes, trhows exceptions and similar issues... I 
found out that it matters which target platform is selected...



So thanks once again.


Regards, Jordy



I dare claim that you're doing something wrong using System.Data.SQLite.
I've been using this library extensively over the past seven or eight 
years - starting when it wasn't yet maintained by the SQLite team - and 
never had any severe problems. Several gotchas for sure, but certainly 
not enough to find it unreliable.
That said I've only coded for windows desktop, so should you be 
struggling with Win CE or the kind, I apologize for making my first 
claim, as I can't say anything about the library's stability on these 
platforms.
As always - examples where your code crashes are a valuable resource to 
giving advice what might be done differently (if there is something done 
wrong).


Best regards, Bernd

___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Regarding CoC

[Thomas Kurz]

> What'da ya think?

That's a great idea. I've already had some concerns that SQLite development 
might cease now. Hoping for great new features in the next release :-)

-- 
D. Richard Hipp
d...@sqlite.org
___
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

Re: [sqlite] Regarding CoC

[Richard Hipp]

Hey, Y'all:

Thanks for all the input.  But we've strayed off-topic.  In keeping
with both the Code of Conduct and the Code of Ethics, maybe its time
we shut this discussion down (or move it to some other venue) and get
back to talking about the worlds greatest embedded database.  What'da
ya think?

-- 
D. Richard Hipp
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Regarding CoC

[Philip Warner]

On 26/10/2018 11:02 PM, Gary R. Schmidt wrote:


On 26/10/2018 14:12, Philip Warner wrote:
I agree with the humour. As a satirical statement on the horrors of building 
a good CoC/CoE it is quite effective.


But...if it is a CoC/E, then I think it would be beneficial to have one that 
many people won't start by knowingly and deliberately ignoring large chunks, 
and broadly disagreeing with even more, and laughing at the rest.


Of course, after all, that's how christianity developed, by picking and 
choosing the various bits of whatever else was around that were in tune with 
the various prejudices and predilections of those involved.


Although the "laughing at the rest" was more often "kill them, and the horses 
they rode in on."


Lol. Love it. Perhaps that should be the disclaimer:

Code of Conduct

...etc...

TL;DR: to put this in historical context, given it's broad lack of 
applicability, it has in large part often reduced to "kill them, and the horses 
they rode in on". YMMV.



___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Regarding CoC

[Gary R. Schmidt]

On 26/10/2018 14:12, Philip Warner wrote:

On 25/10/2018 9:59 PM, Mike King wrote:


I’m a good atheist but I love the CoC. Not bothered by the religious bits
but I get the sentiment. I guess it appeals to my British sense of irony
and odd sense of humour :)


I agree with the humour. As a satirical statement on the horrors of 
building a good CoC/CoE it is quite effective.


But...if it is a CoC/E, then I think it would be beneficial to have one 
that many people won't start by knowingly and deliberately ignoring 
large chunks, and broadly disagreeing with even more, and laughing at 
the rest.
Of course, after all, that's how christianity developed, by picking and 
choosing the various bits of whatever else was around that were in tune 
with the various prejudices and predilections of those involved.


Although the "laughing at the rest" was more often "kill them, and the 
horses they rode in on."


Cheers,
GaryB-)
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

[sqlite] Exception handling during create table from a virtual one

[Max Vlasov]

Hi,

I have a virtual table that raises an unhandled exception during a create
table ... as select * from {myvirtualtable} command, inside xColumn
callback. I already fixed the error inside my library to handle the
situation reasonably, but there's something I noticed for the non-handled
exception scenario.

Аfter the exception is thrown 

 If I continue the execution, then the following symptoms are shown:
- The sqlite returns "unknown" error for this query
- Select * from sqlite_master reveals an empty row.
- integrity_check:  *** in database main *** Page 2 is never used
- after I reopen this db, Pragma encoding query and probably other queries
produces "schema is malformed" error

.. If I halt the process when the debugger stops at the exception
- The db is restored (rolled back) to correct state (no new table created,
no integrity errors)

Is this expected? I mean, sqlite usually handles well unexpected halts and
this is something that might be desired (for example, computers might shut
down abruptly), but unexpected exception is something about code control
flow which no sane library can guarantee to handle well.

sqlite 3.25.2
If necessary I can provide small copies of the original db (1024 bytes) and
malformed (2048)

Thanks,

Max
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Regarding CoC

[Keith Medcalf]

On Friday, 26 October, 2018 03:57, Petite Abeille  
wrote:

>> On Oct 26, 2018, at 5:12 AM, Philip Warner  >wrote:

>> knowingly and deliberately ignoring large chunks, and broadly
>> disagreeing with even more, and laughing at the rest.

> Bah… Everything Is Amazing And Nobody Is Happy:
> https://www.youtube.com/watch?v=nUBtKNzoKZ4

Hilarious!  And I remember the days when you had to book long distance calls in 
advance so that you could be scheduled onto the transatlantic cable, and the 
call would be completed by operators calling station to station hop by hop.  
Hello London?  This is Toronto calling ... are we reaching?

---
The fact that there's a Highway to Hell but only a Stairway to Heaven says a 
lot about anticipated traffic volume.





___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Regarding CoC

[Petite Abeille]

> On Oct 26, 2018, at 5:12 AM, Philip Warner  wrote:
> 
> knowingly and deliberately ignoring large chunks, and broadly disagreeing 
> with even more, and laughing at the rest.

Bah… Everything Is Amazing And Nobody Is Happy: 
https://www.youtube.com/watch?v=nUBtKNzoKZ4

___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Optmize queries on ranges

[Keith Medcalf]

Limit 1 says to stop after returning 1 row.  If the "first row" being searched 
is not the one containing "the answer" then the search will continue until the 
row that does not match the index constraint is hit, after which it is known 
that no answer is possible (without returning a row).


---
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:49
>To: sqlite-users@mailinglists.sqlite.org
>Subject: Re: [sqlite] Optmize queries on ranges
>
>Ok, after the message I thought a little bit more.
>
>And it turns out that in the database the `start`s are not unique how
>they
>should.
>Making them unique, seems to solve the performance problem
>completely.
>
>However, still, I am not sure why the `LIMIT 1` does not help at all.
>
>Can you guys shed some light on this?
>
>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

Re: [sqlite] Optmize queries on ranges

[Keith Medcalf]

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)

>>> 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

Re: [sqlite] Optmize queries on ranges

[Olivier Mascia]

> Le 26 oct. 2018 à 09:27, siscia  a écrit :
> 
> 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

What if the data was structured differently?

> CREATE TABLE ranges (
>start int,
>end int,
>value int,
> );

becomes:

CREATE TABLE ranges (
   start int,
   range int,   -- on the basis that start + range = end
   value int,
);

> INSERT INTO ranges(1, 10, 5);
> INSERT INTO ranges(15, 29, 8);
> INSERT INTO ranges(30, 32, 9);

becomes:

INSERT INTO ranges(1, 9, 5);
INSERT INTO ranges(15, 14, 8);
INSERT INTO ranges(30, 2, 9);

and you have:

CREATE INDEX idx_ranges on ranges(start);

> select value from ranges
> where (? between start and end)

becomes:

SELECT value FROM ranges where (? between start AND start+range);

-- 
Best Regards, Meilleures salutations, Met vriendelijke groeten,
Olivier Mascia


___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Optmize queries on ranges

[siscia]

Sorry,

I was a little too optimistic.

Making the starts unique does help only for some queries, not for all.

Why?

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

Re: [sqlite] Optmize queries on ranges

[siscia]

Ok, after the message I thought a little bit more.

And it turns out that in the database the `start`s are not unique how they
should.
Making them unique, seems to solve the performance problem completely.

However, still, I am not sure why the `LIMIT 1` does not help at all.

Can you guys shed some light on this?

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

Re: [sqlite] Optmize queries on ranges

[Dan Kennedy]

On 10/26/2018 02:27 PM, siscia wrote:

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.



In SQL, I guess that is:

  SELECT value FROM ranges WHERE (? BETWEEN start AND end)
  ORDER BY start DESC LIMIT 1

Or, perhaps more efficient for the cases where there is no such range:

  SELECT value FROM (
SELECT value, start, end FROM ranges
WHERE start <= ?
ORDER BY start DESC LIMIT 1
  ) WHERE end >= ?

Dan.




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

Re: [sqlite] Optmize queries on ranges

[siscia]

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