[sqlite] R-Tree Storage Optimization for Points

[Mohit Sindhwani]

Hello!  We are using SQLite3 for storing geographical points that can be 
queried using a bounding box (find everything that lies within this 
box).  Obviously, this query fits the capabilities of the RTree module 
very well and it is a simple 2 dimensional search using an R-Tree that 
has 5 columns.


However, since these are points that are stored in the table, x1=x2 and 
y1=y2 when we do the insertion.  As a former embedded systems engineer, 
this feels like a waste since I can see that we are inserting exactly 
the same value into the table.


INSERT into data_rtree(1000, 10, 5, 10, 5);
INSERT into data_rtree(1000, 17, 1, 17, 1);
and so on.

Is there a way that we could optimize the module so that we don't need 
to store the same value twice?  We are using this on a system with 
constrained resources, so it helps to reduce the amount of storage space 
we need for our database.


Thanks,
Mohit.

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

Re: [sqlite] Error: database is locked

[Kevin Benson]

On Wed, Jun 18, 2014 at 6:17 PM, JohnG <4par...@gmail.com> wrote:

> gelmjw@voyager /var/www/sqlite3/finviz $ cd /var/www/sqlite3/finviz/;
> sqlite3 -init finviz.init finviz.db
> ~SNIP~
> How do I clear this lock condition?
>

>
Maybe try it like this instead:

gelmjw@voyager /var/www/sqlite3/finviz $ cd /var/www/sqlite3/finviz/;
sqlite3 finviz.db http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] problem sorting data

[Igor Tandetnik]

On 6/18/2014 12:19 PM, claude.pom...@free.fr wrote:

i have query like this

SELECT SUM(apport.poid) AS poid,
SUM(apport.quantite) as nb,
provenance.provenance,
touches.label as label,
apport.ladate
FROM apport
JOIN provenance ON apport.id_provenance = provenance.id_provenance
JOIN touches ON apport.id_touches = touches.id_touches
WHERE ladate BETWEEN "2014-01-01" AND "2014-12-31"
GROUP BY apport.id_touches
ORDER BY provenance.provenance, date(apport.ladate), apport.id_touches;

in mysql result is sorted like "order by" condition but in sqlite3, the data are only 
sorted by the fist argumement of "order by" condition
removing provenance.provenance order by apport.ladate but not by 
apport.id_touches


Are you sure MySQL even accepts this query? You are selecting and 
ordering by fields that you are not grouping by, nor wrapping in 
aggregate functions. That's not valid SQL; SQLite accepts this as an 
extension, but many other systems reject it. I thought MySQL was one of 
the latter.


Anyway, in a group of rows with the same apport.id_touches, there may be 
rows with different values of provenance.provenance. Which one of those 
values do you expect to be selected, and which one do you expect to be 
used to order the group?

--
Igor Tandetnik

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

Re: [sqlite] Suggestion for SHELL impovement (built-in scripting)

[J Decker]

Stored procedures

variables, a goto(jump/branch) and a conditional so loops can be made;

On the topic of shell results; isn't there a result value of like number of
records inserted ? So something like var a = insert... select $a; and then
test the output sort of?

went searching cause I really ended up avoiding stored procedures because
of the lack of consistency I don't think SQL standard defines such
things... what I saw was very linear  top-down sort of things, which makes
querying a recursive heirarchical table kinda hard to do in a stored
procedure but I guess I was wrong; but they are all different.

http://dev.mysql.com/doc/refman/5.0/en/flow-control-statements.html  (mysql
does have loop constructs)
http://technet.microsoft.com/en-us/library/ms180796(v=sql.105).aspx ( flow
control in M$ SQL  [tsql])

http://en.wikipedia.org/wiki/SQL#Procedural_extensions (standard?) ya ...
almost as many flavors of this as there are databases.  sad.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

[sqlite] problem sorting data

[claude . pomalo]

hello

i have query like this

SELECT SUM(apport.poid) AS poid, 
SUM(apport.quantite) as nb, 
provenance.provenance, 
touches.label as label, 
apport.ladate 
FROM apport 
JOIN provenance ON apport.id_provenance = provenance.id_provenance 
JOIN touches ON apport.id_touches = touches.id_touches 
WHERE ladate BETWEEN "2014-01-01" AND "2014-12-31" 
GROUP BY apport.id_touches 
ORDER BY provenance.provenance, date(apport.ladate), apport.id_touches;

in mysql result is sorted like "order by" condition but in sqlite3, the data 
are only sorted by the fist argumement of "order by" condition
removing provenance.provenance order by apport.ladate but not by 
apport.id_touches

any idea?

thank
Claude

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

Re: [sqlite] Suggestion for SHELL impovement (built-in scripting)

[Nico Williams]

My suggestion is to have a sqlite_... table in which to start
statements to run at DB open time, so as to:

 - automatically CREATE temp tables, indexes, views
 - automatically ATTACH related DBs
 - automatically load extensions (this should require explicit
acquiescence from the API caller though)

This would allow the use of the sqlite3 shell with apps fully
contained in the DB.

This is almost what you want, but not quite.  This is better because
all it does is initial setup.  Application logic would still be
restricted to being in the schema, but now that could include temp
schema that "persists" -- not entirely an oxymoron.

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

Re: [sqlite] Suggestion for SHELL impovement (built-in scripting)

[Roger Binns]

On 06/18/2014 02:47 PM, to...@acm.org wrote:

But you need bash, or TCL, or Perl, or Python, or whatever other than
sqlite3.exe
So, you're suggesting that an innocent SQLite user should install any of
those programming packages just to run SQLite.  Hmm... no, thanks!


Yes.  Quite simply you'll start wanting if statements and variables, and 
loops, and stronger matching primitives etc.  That is why I said "add 
puny inadequate incomplete scripting into the C based shell".  Unless 
you can show that what you asked for is the limit of functionality 
needed for all users of your proposed feature for the foreseeable 
future, extra scripting stuff would be added.


It is far more sensible to use an existing one than invent an arbitrary 
new one.


Roger


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

Re: [sqlite] Suggestion for SHELL impovement (built-in scripting)

[jose isaias cabrera]

to...@acm.org wrote...


Hi all,

...
So here’s my suggestion for what (I feel) is a significant improvement for 
the SHELL version of SQLite without being too much of a programming 
complication in my view.  (Those who usually attack any new concept, 
please pause a moment and give it some thought, then attack as usual!)

Funny...
...
...
This capability would make the shell capable of supporting very complex 
script-based command-line applications all stored within the same single 
database file!


I happen to think that this is a great idea.  I can see many ways where I 
can use it. 


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

[sqlite] Error: database is locked

[JohnG]

gelmjw@voyager /var/www/sqlite3/finviz $ sqlite3 -version
3.7.9 2011-11-01 00:52:41 c7c6050ef060877ebe77b41d959e9df13f8c9b5e
gelmjw@voyager /var/www/sqlite3/finviz $

gelmjw@voyager /var/www/sqlite3/finviz $ uname -a
Linux voyager 3.2.0-23-generic #36-Ubuntu SMP Tue Apr 10 20:39:51 UTC 
2012 x86_64 x86_64 x86_64 GNU/Linux

gelmjw@voyager /var/www/sqlite3/finviz $


gelmjw@voyager /var/www/sqlite3/finviz $ cat finviz.init
.stats on
.timer on
.mode columns
.headers on
select load_Extension('libsqlitefunctions.so');
gelmjw@voyager /var/www/sqlite3/finviz $ fuser finviz.db 
<-no one is using the file <--
gelmjw@voyager /var/www/sqlite3/finviz $ cd /var/www/sqlite3/finviz/; 
sqlite3 -init finviz.init finviz.db

-- Loading resources from finviz.init
load_Extension('libsqlitefunctions.so')
---

Memory Used: 75064 (max 76472) bytes
Number of Outstanding Allocations:   101 (max 102)
Number of Pcache Overflow Bytes: 1024 (max 1024) bytes
Number of Scratch Overflow Bytes:0 (max 0) bytes
Largest Allocation:  64000 bytes
Largest Pcache Allocation:   1024 bytes
Largest Scratch Allocation:  0 bytes
Lookaside Slots Used:0 (max 0)
Successful lookaside attempts:   0
Lookaside failures due to size:  0
Lookaside failures due to OOM:   0
Pager Heap Usage:1696 bytes
Page cache hits: 0
Page cache misses:   0
Schema Heap Usage:   0 bytes
Statement Heap/Lookaside Usage:  1664 bytes
Fullscan Steps:  0
Sort Operations: 0
Autoindex Inserts:   0
CPU Time: user 0.00 sys 0.004000
SQLite version 3.7.9 2011-11-01 00:52:41
Enter ".help" for instructions
Enter SQL statements terminated with a ";"
sqlite> .tables
fvall  v110   v120   v130   v140   v160   v170
sqlite> delete from v110;
Memory Used: 13570240 (max 1249828600) bytes
Number of Outstanding Allocations:   4425 (max 977900)
Number of Pcache Overflow Bytes: 5090048 (max 123800) bytes
Number of Scratch Overflow Bytes:0 (max 0) bytes
Largest Allocation:  8388608 bytes
Largest Pcache Allocation:   1272 bytes
Largest Scratch Allocation:  0 bytes
Lookaside Slots Used:0 (max 0)
Successful lookaside attempts:   0
Lookaside failures due to size:  0
Lookaside failures due to OOM:   0
Pager Heap Usage:5091288 bytes
Page cache hits: 974845
Page cache misses:   974845
Schema Heap Usage:   14960 bytes
Statement Heap/Lookaside Usage:  1296 bytes
Fullscan Steps:  0
Sort Operations: 0
Autoindex Inserts:   0
CPU Time: user 5.016314 sys 19.457216
Error: database is locked
sqlite>

Why? No one was using finviz.db beforehand. Who locked it?


Now, I open another terminal

gelmjw@voyager /var/www/sqlite3/finviz $ fuser finviz.db
/var/www/sqlite3/finviz/finviz.db: 26235
gelmjw@voyager /var/www/sqlite3/finviz $ ps aux |grep 26235
gelmjw   26235 23.5 30.7 1280028 1245304 pts/1 S+   16:53   0:24 sqlite3 
-init finviz.init finviz.db
gelmjw   26250  0.0  0.0  13588   896 pts/2S+   16:55   0:00 grep 
--colour=auto 26235

gelmjw@voyager /var/www/sqlite3/finviz $
===
Well, that is me trying to 'delete from v110;' !!!

So, I am keeping me from deleting?

How do I clear this lock condition?

Regards;
John Gelm



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

[sqlite] Suggestion for SHELL impovement (built-in scripting)

[tonyp]

Hi all,

First of all, this is not about using SQLite as an embedded library from C, 
or whatever other language.  It does not affect the sqlite3.c file at all. 
It only applies to the shell (so logically, it only affects shell.c)


So here’s my suggestion for what (I feel) is a significant improvement for 
the SHELL version of SQLite without being too much of a programming 
complication in my view.  (Those who usually attack any new concept, please 
pause a moment and give it some thought, then attack as usual!)


Because I primarily use SQLite as a tool (from the shell), and given that 
SQLite does not (yet, if ever) support stored procedures, I often find 
myself (as I believe most people on this list) writing scripts that will do 
a certain task, and then run those using the shell with something like 
“sqlite3 my.db < script.sql”


I think we can all agree that the single most important advantage of SQLite 
is the one-file-holds-everything deal (both for the database file, and for 
the application or library file).  On that principle,...


The problem with having all those scripts separate from the database file 
somehow violate the previous assertion.  Plus, there is the problem that 
scripts cannot be made to have parameters (AFAIK).

So, two birds with one stone, ...

Wouldn’t it be nice if we could have those scripts somehow saved in the 
sqlite_master table (or some other new system table, if this one would cause 
compatibility issues), and then be able to call them very easily from the 
shell with some special prefix (e.g., :SCRIPTNAME parm1 parm2 parm3 ... – or 
some similar simple syntax).  The : character could be some other special 
character (except for . used for built in commands.)


Then the shell, using the simplest of macro expansion techniques of plain 
text replacement, would read each line from the saved script, convert 
occurrence of the each parameter to the text appearing in the invocation and 
run it as if it was just typed on the keyboard.


For example, if my script was:

SELECT ~1~ from ~2~ where name like (‘%~3~%’);

giving the shell command:

:SCRIPTNAME * my_table some_name

would be executed as:

SELECT * from my_table where name like (‘%some_name%’);

I have used ~number~ as a parameter placeholder, but anything that works 
without ambiguities in the grammar would work.


And, then the next line of the script would be executing in a similar manner 
until the whole script is exhausted.


This capability would make the shell capable of supporting very complex 
script-based command-line applications all stored within the same single 
database file!


Thanks for listening (hopefully).

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

Re: [sqlite] slowish R*Tree performance

[Cory Nelson]

On Wed, Jun 18, 2014 at 3:00 PM, Eric Rubin-Smith  wrote:

> Cory Nelson wrote:
>
> > Expand the prefix into the full feed:beef::etc
> >
> > Insert into a table (start binary(16), mask_length int)
> >
> > select top 1 binary,length from table where start <= @input order by
> > binary desc
> >
> > Check if the row is inside the range returned.  This will take a single
> > index seek.
>
> Looking at this again, I do not think the solution is correct.  E.g.
> assume you have populated 10m prefixes, one of which is ::/0.  Assume
> the search key is ::::::: and ::/0
> is the only covering prefix.  Then your scheme will not find ::/0.  And
> simple extensions of your scheme involve searching through the whole set
> to find ::/0.
>
>
Correct, this will not work with overlapping blocks.

-- 
Cory Nelson
http://int64.org
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] slowish R*Tree performance

[Eric Rubin-Smith]

Cory Nelson wrote: 

> Expand the prefix into the full feed:beef::etc 
> 
> Insert into a table (start binary(16), mask_length int) 
> 
> select top 1 binary,length from table where start <= @input order by 
> binary desc 
> 
> Check if the row is inside the range returned.  This will take a single 
> index seek.  

Looking at this again, I do not think the solution is correct.  E.g.  
assume you have populated 10m prefixes, one of which is ::/0.  Assume 
the search key is ::::::: and ::/0 
is the only covering prefix.  Then your scheme will not find ::/0.  And 
simple extensions of your scheme involve searching through the whole set 
to find ::/0.  

-- 
Eric A. Rubin-Smith

Money is the root of all wealth.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] slowish R*Tree performance

[Eric Rubin-Smith]

Cory Nelson wrote: 

> The phrase you're looking for here is "CIDR block".  

Well, I was avoiding the phrase on purpose :-).  I was worried that 
using another bit of jargon -- one that is even more opaque than 
"prefix" to someone unfamiliar with the space -- did not seem likely to 
help get the idea across.  But since you and this forum probably do not 
have a burning interest in the minutiae of my flawed writing process, I 
press on.  

> The way I'd handle this is something like this: 
> 
> Expand the prefix into the full feed:beef::etc 
> 
> Insert into a table (start binary(16), mask_length int) 
> 
> select top 1 binary,length from table where start <= @input order by 
> binary desc 
> 
> Check if the row is inside the range returned.  This will take a single 
> index seek.  

Um.  This looks, wow, much simpler and better than the R*Tree trick.

I guess the only question is whether the binary search into the 
(traditional) index will cost more than the R*Tree traversal.  In a set 
of 10m records we expect to bounce 23 times in a traditional index, if 
my math is right.  Not sure how that compares to the R*Tree.  

I'll see if I can get an apples-to-apples performance comparison 
going (and will reply back with the results, in case folks are still 
interested).  

Thank you!

-- 
Eric A. Rubin-Smith

I'm just glad it'll be Clark Gable who's falling on his face and 
not Gary Cooper.
-- Gary Cooper on his decision not to take the leading role in 
   "Gone With The Wind."
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] slowish R*Tree performance

[Eric Rubin-Smith]

Carlos Ferreira wrote: 

> Regarding the R.Tree performance problem, 
> 
> What is the original problem that is causing slow performance in the 
> SQlite R-Tree implementation?  

I was populating my DB with bad data.  In particular, I was first 
choosing a random prefix length, then filling up that number of bits to 
create a random prefix.  I was then just blindly sticking that into the 
database.  

For very short prefix lengths, the chance of an exact collision was 
therefore very high.  E.g.  if prefix length 0 is chosen, then the 
chances of collision are 100%.  And prefix length 0 is chosen 1% of the 
time.  

Collisions on the large bounding boxes are exactly what you don't want, 
because of the way an R*Tree works.  (Collisions in small bounding boxes 
only matter for the rare searches that happen to fall within them.)  

Fixed by checking for the existence of an identical bounding box, and 
removing it if it does exist.  (This population prototype code might 
eventually feed production code, which will find it more useful to have 
INSERT OR REPLACE semantics than INSERT OR IGNORE semantics.)  

The above, however, raises an interesting point.  Even when exact 
collisions are detected and avoided, the above randomized scheme does 
create a significant "matrioshka" structure that may not be present 
in real-world datasets.  That is, again, there is a 1/128 chance that 
length 0 is chosen.  There is an 8/128 or 6% chance that a prefix of 
length <= 8 is chosen.  I.e.  we are creating a lot of large bounding 
boxes that likely cover smaller ones, and that may or may not reflect
reality.

-- 
Eric A. Rubin-Smith

Computer programs don't like being anthropomorphized.
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] slowish R*Tree performance

[Cory Nelson]

On Wed, Jun 18, 2014 at 12:18 PM, Eric Rubin-Smith 
wrote:

> Carlos Ferreira wrote:
>
> > 1 - There a data type named IPV6 Address.  2 - there is a table where
> > this data type must be in.  ( can be a set of fields, one blob, one
> string
> > ...)
> >
> > You want to:
> >
> > Given a certain IPV6, find in the database the existent IPV6 record with
> > the longest equal prefix to the given IPV6 value.
>
> Not quite.  Perhaps you were confused by my (probably unclear) use of
> the word "prefix".
>
> The data structure contains a set of IPv6 *network prefixes*.  A prefix
> is the first N bits of an IPv6 address and is denoted as an IP address
> with a suffix of (128-N) bits of zeros, along with the length of the
> prefix:
>
> feed:beef::/32
>
> (here N==32).
>
> An IPv6 address is inside this prefix iff its first 32 bits are equal to
> feed:beef.


The phrase you're looking for here is "CIDR block". The way I'd handle this
is something like this:

Expand the prefix into the full feed:beef::etc

Insert into a table (start binary(16), mask_length int)

select top 1 binary,length from table where start <= @input order by binary
desc

Check if the row is inside the range returned. This will take a single
index seek.

-- 
Cory Nelson
http://int64.org
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] slowish R*Tree performance

[Eric Rubin-Smith]

Simon Slavin wrote: 

> Strongly suspect that although R*Trees produce an elegant solution to 
> your problem, the fact that they're a general case tool will make them too 
> slow to use for something like this.  
> 
> I propose an alternative solution, though I have not tried it and do not 
> have time to try it (sorry).  
> 
> 1) A function which turns a numeric IP address or a block into some 
> standard easy-to-process representation in string form.  Possibly a 
> pair of strings with the first string being an address the second being 
> something indicating the extent of the block, perhaps something like 
> '2001:0db8:8500:::::v::ff00:::::'.
>   
> You could make it shorter by leaving out the colons but my experience is 
> that although this leads to less data stored on disk it doesn't speed up 
> processing by much.  But if you have a great deal of data you might want 
> to do it anyway.  
> 
> 2) A comparator function (maybe a SQLite function, maybe not) which 
> takes two such addresses or blocks and returns a value indicating whether 
> they're identical, whether block A contains block or address B, or 
> neither.  
> 
> The closest I got to the above was when I needed a program which 
> intensively searched and sorted individual IPv4 addresses.  I got best 
> results by defining a SQLite function which converted IP addresses of all 
> formats into 'standard format' where each byte was two hex digits.  All 
> values stored in the database were stored in my 'standard' format.  This 
> allowed easy collation using standard text sorting.  

Thanks for the suggestion, Simon.  

My use case is intensive on the search side, but will incur occasional 
updates to the structure.  No sorting necessary from an application 
perspective.  Perhaps I am being dense, but don't see how your 
representation eases the burden of longest-prefix matching from within 
SQL queries.  

> Everything else turned out faster to implement in my own programming 
> language than it was to build as SQLite functions.  

Yeah, I agree that the performance of a dedicated data structure will be 
far better.  Again, just wondering if I can stretch SQLite to solve this 
problem, because it would be oh-so-nice to leverage all the other stuff 
SQLite gives us.  

-- 
Eric A. Rubin-Smith

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

Re: [sqlite] slowish R*Tree performance

[Eric Rubin-Smith]

Carlos Ferreira wrote: 

> 1 - There a data type named IPV6 Address.  2 - there is a table where 
> this data type must be in.  ( can be a set of fields, one blob, one string 
> ...)  
> 
> You want to: 
> 
> Given a certain IPV6, find in the database the existent IPV6 record with 
> the longest equal prefix to the given IPV6 value.  

Not quite.  Perhaps you were confused by my (probably unclear) use of 
the word "prefix".  

The data structure contains a set of IPv6 *network prefixes*.  A prefix 
is the first N bits of an IPv6 address and is denoted as an IP address 
with a suffix of (128-N) bits of zeros, along with the length of the 
prefix: 

feed:beef::/32 

(here N==32).  

An IPv6 address is inside this prefix iff its first 32 bits are equal to 
feed:beef.  

Note that one prefix can be contained within another: 

feed:beef:f00d::/48 is fully contained within feed:beef::/32.  We say 
that feed:beef:f00d::/48 is "more specific" than feed:beef::/32.  

The problem (one that comes up quite often, e.g.  in routers) is this: 
given an IP address, find the longest-length prefix containing the 
address.  I.e.  find the most specific prefix containing the address.  

This is different from the problem you stated.  One key thing to note is 
that the two prefixes feed:beef::/32 and feed:beef::/48 are different, 
even though the bits in the address parts are identical.  

> Again, if the problem is as I understood, the simplest solution is ( 
> again I am discussing it as if it could be implemented or available in 
> SQLite..I do not know..)  
> 
> 1 - encode the IPV6 field as a unique blob 2 - Implement an index to 
> this field so that this particular field can be ordered 3 - Make sure that 
> the ordering compare function is a binary incremental compare counting 
> from the left ( in terms of the data...not sure how you will represent 
> it in the field ) 4 - Each time you want to find the closed and longest 
> prefix, you just need to simulate an insert command.  Try to insert the 
> given value.  Instead of inserting, just return the ordered position where 
> it would be inserted.  Check what is the record actually standing in that 
> ordered position...That would be your result!!  

The problem has many solutions outside of SQL.  The most common data 
structure is a "trie" (pronounced "tree" and short for "reTRIEval 
tree"), though it turns out that in many subsets of this problem space 
other data structures turn out to be more efficient.  

The present motivation, however, is to see if we can leverage all 
the ancillary sexiness of SQLite while still getting reasonably fast 
searches within this problem space.  Turns out we can do pretty darn 
well with SQLite in this regard.  

The key part is coming up with an isomorphism between overlapping 
IPv6 prefixes and the overlapping geometric boxes represented in a 
5-dimensional R*Tree.  Not just any isomorphism, but one with the 
property that for prefixes P1 and P2, P1 contains P2 if and only if 
bbox(P1) fully contains bbox(P2).  (It follows that the volume of 
bbox(P1) is larger than the volume of bbox(P2), so you can sort by the 
volumes of all the covering bboxes to find the most specific prefix.  
Though my SQL had a bug in that regard, so treat it with care if you use 
it.:-) 

Again, the 5 dimensions are only needed because the R*Tree's integers 
are only 32 bits wide.  If they were 128 bits wide, you could just 
represent an IPv6 prefix as an interval on the line segment [0, 
2^128-1], and store those intervals in a 1-dimensional R*Tree (which 
works great for IPv4, btw).

-- 
Eric A. Rubin-Smith

I still maintain the point that designing a monolithic kernel in 
1991 is a fundamental error.  Be thankful you are not my student.  
You would not get a high grade for such a design.
-- Andrew Tanenbaum, to Linus Torvalds
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Help forming query

[Simon Slavin]

On 18 Jun 2014, at 7:01am, David M. Cotter  wrote:

> also: if this query isn't *very* fast, then i'm fine with just "give me the 
> value of the first cell where there is data in that column"

SQL does not have a concept of 'first' row.  Rows in a table do not have any 
order.  You can retrieve the values, and then find a that row with that value 
that has the lowest rowid, but that's your own interpretation of 'first'.

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

Re: [sqlite] Performance regression with multiple lower bound tests

[David Empson]

On 16/06/2014, at 11:36 pm, Richard Hipp  wrote:

> On Mon, Jun 16, 2014 at 5:07 AM, David Empson  wrote:
> 
>> It appears SQLite 3.8.1 removed an optimisation where earlier versions of
>> the query planner were checking for two or more "lower bound" comparisons
>> against the key for an index, and combining them so the greater of the two
>> values was used as a lower bound.
>> 
>> 
> There never has been any such optimization in SQLite.  If it picked the
> better lower bound in 3.8.0, then that was purely by luck.

OK thanks, that makes sense.

> I suggest you rewrite your query.  Instead of
> 
> ... WHERE x BETWEEN ?1 AND ?2 AND x>?3
> 
> Consider using
> 
> ... WHERE x BETWEEN max(?1,?3) AND ?2 AND x>?3

I assume that was supposed to be WHERE x BETWEEN max(?1,?3) AND ?2.

I agree, that seems a reasonable solution. Something like that was on 
tomorrow's todo list.

> Also, when running EXPLAIN, please first give the command-line shell the
> ".explain" command in order to set output formatting up to show the program
> listing in a more readable format.

Noted, thanks for the tip.

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

Re: [sqlite] Help forming query

[Bradley Giesbrecht]

On Jun 17, 2014, at 11:01 PM, David M. Cotter  wrote:

> also: if this query isn't *very* fast, then i'm fine with just "give me the 
> value of the first cell where there is data in that column"
> 
> in the below case, i'd get a "1".  
> i would then proceed to delete everything with a "1" in it (from this and 
> other tables)
> then i'd ask again, this time i'd get a 4, repeat above
> then ask again, get nothing, and i'd be done
> 
> On Jun 17, 2014, at 10:54 PM, David M. Cotter  wrote:
> 
>> i have a table with a numeric column (not the key column)
>> i want to obtain from this table a list of unique numbers appearing in that 
>> one column
>> 
>> some cells in the column may have nothing, some may have duplicate numbers 
>> eg:
>> 
>>> 1
>>> 1
>>> 1
>>> 4
>>> _
>>> _
>>> 4
>>> _
>> 
>> note that "_" means "no data".  i want to get a list with [1, 4] as the 
>> result.  what is the proper SQLite query for this?


You want "distinct":
select distinct column from table where column is not null;

or "group by":
select column from table where column is not null group by column;


Regards,
Bradley Giesbrecht (pixilla)



signature.asc
Description: Message signed with OpenPGP using GPGMail
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Help forming query

[David Empson]

On 18/06/2014, at 5:54 pm, David M. Cotter  wrote:

> i have a table with a numeric column (not the key column)
> i want to obtain from this table a list of unique numbers appearing in that 
> one column
> 
> some cells in the column may have nothing, some may have duplicate numbers eg:
> 
>> 1
>> 1
>> 1
>> 4
>> _
>> _
>> 4
>> _
> 
> note that "_" means "no data". i want to get a list with [1, 4] as the 
> result.  what is the proper SQLite query for this?

SELECT DISTINCT column FROM table;

This will return a row for each unique value in table.column, with the values 
in no particular order.

Eliminating the "no data" entry can be done by checking the results, or if you 
want to eliminate it automatically you could use something like:

SELECT DISTINCT column FROM table WHERE column not NULL;

This assumes your "no data" is represented as NULL. If you have used something 
else to represent "no data" then you would need to compare against that.

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

Re: [sqlite] Help forming query

[David M. Cotter]

also: if this query isn't *very* fast, then i'm fine with just "give me the 
value of the first cell where there is data in that column"

in the below case, i'd get a "1".  
i would then proceed to delete everything with a "1" in it (from this and other 
tables)
then i'd ask again, this time i'd get a 4, repeat above
then ask again, get nothing, and i'd be done

On Jun 17, 2014, at 10:54 PM, David M. Cotter  wrote:

> i have a table with a numeric column (not the key column)
> i want to obtain from this table a list of unique numbers appearing in that 
> one column
> 
> some cells in the column may have nothing, some may have duplicate numbers eg:
> 
>> 1
>> 1
>> 1
>> 4
>> _
>> _
>> 4
>> _
> 
> note that "_" means "no data".  i want to get a list with [1, 4] as the 
> result.  what is the proper SQLite query for this?

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