Strategies to reduce page-loads?

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

Strategies to reduce page-loads?

tf@qvgps.com
Hi Guys,

we are using SQlite for storing OpenStreetMap ways (lines).
Once filled its readonly.
Then the lines is queried for specific areas to draw a map.

Structure is  simple:
CREATE TABLE Lines(Id LONG PRIMARY KEY, Label VARCHAR(50), Coordinates
BLOB, Flags INT, StyleId INT);
And an rtree-index:
CREATE VIRTUAL TABLE Lines_bb USING rtree (Id LONG PRIMARY KEY, X0
FLOAT, X1 FLOAT, Y0 FLOAT, Y1 FLOAT, Z0 FLOAT, Z1 FLOAT);

Queries are always all lines of a specific geographical ares, which is
very fast because of the rtree.
SELECT Lines.* FROM Lines_bb , Lines WHERE y0 < ? AND y1 > ? AND x0 < ?
AND x1 > ? AND ? BETWEEN z0 AND z1 AND Lines_bb.Id = Lines.Id ;

Then the rows are fetched and here starts the problems:
var stmt = SQLite3.Prepare2 (handle, select);
while (SQLite3.Step(stmt) == SQLite3.Result.Row)
{
// fetch row
}

The larger the db, the slower is the fetching!

We compared a small db (50mb) and a big db (500mb), both containing the
same small area:
Reading the same area of  for example 1000 lines from the small db is 2x
faster then from the large db.
After doing some profiling, it turned out, that the extra time was spent
in SQLite3.Step.

My assumption is, that in the big db, these 1000 lines are just spread
over a much higher count of pages.
So more page-loads resulting in more time.

We changed page_size to the maximum value of 64k and it became much
better, but still I would lke to improve it.

Thanks,
Tom



/****************************************
** Flemming Software Development CC
** Thomas Flemming
** PO Box 81244
** Windhoek, Namibia
** http://www.quovadis-gps.com
** mail [hidden email]
** +264 (0)81 3329923 Nam mobile
** +49 (0)175 7313081 D mobile
** +49 (0)6182 8492599 D office
***************************************/
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Strategies to reduce page-loads?

Clemens Ladisch
[hidden email] wrote:
> The larger the db, the slower is the fetching!
>
> My assumption is, that in the big db, these 1000 lines are just spread over a much higher count of pages.
> So more page-loads resulting in more time.

Correct.

> We changed page_size to the maximum value of 64k and it became much better, but still I would lke to improve it.

Store the table entries so that nearby objects are stored nearby.  One
way to do that would be to insert the ways ordered first by Z, then by
the position on a space-filling curve (e.g., Morton order
<https://en.wikipedia.org/wiki/Z-order_(curve)>).


Regards,
Clemens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Strategies to reduce page-loads?

Richard Hipp-3
In reply to this post by tf@qvgps.com
On 8/30/18, [hidden email] <[hidden email]> wrote:
>
> Structure is  simple:
> CREATE TABLE Lines(Id LONG PRIMARY KEY, Label VARCHAR(50), Coordinates
> BLOB, Flags INT, StyleId INT);
> And an rtree-index:
> CREATE VIRTUAL TABLE Lines_bb USING rtree (Id LONG PRIMARY KEY, X0
> FLOAT, X1 FLOAT, Y0 FLOAT, Y1 FLOAT, Z0 FLOAT, Z1 FLOAT);

Three points that might help, either separately or in combination:

(1) Use exactly "INTEGER PRIMARY KEY".  "LONG PRIMARY KEY" and "INT
PRIMARY KEY" are not the same thing and do not work as well.

(2) In the very latest versions of SQLite, 3.24,0 and the beta for
3.25.0, you can put the "Lines" information directly in the RTree:

   CREATE VIRTUAL TABLE Lines_bb USING rtree(id, x0, x1, y0, y1, z0,
z1, +Label, +Coordinates, +Flags, +StyleId);

The extra columns in r-tree are prefaced by a "+" character so that
the r-tree module knows that they are auxiliary columns and not extra
coordinates.

(3) Consider deliberating choosing INTEGER PRIMARY KEY values based on
a "Morton code" or "Z-Order curve" of the coordinates.
(https://en.wikipedia.org/wiki/Z-order_curve)  That will cause
features that are close together geographically to tend to be close
together within the file.  There is are two extension functions in the
https://www.sqlite.org/src/artifact/b0ff58fa643afa1d file of the
SQLite source tree that might help you with this.  Or you can do the
same using your own functions.
--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Strategies to reduce page-loads?

tf@qvgps.com
Thanks guys for quick and competent answers!

After first sight, this "Z-Order curve" looks very promising, will give
it a try.

The LONG PRIMARY KEY is because  I need a 64-bit integer (osm-id).
I only learned now, that sqlite-int is also 64 bit long.
Will change to INT PRIMARY KEY now.

Tom


------ Originalnachricht ------
Von: "Richard Hipp" <[hidden email]>
An: "SQLite mailing list" <[hidden email]>
Gesendet: 30.08.2018 13:48:30
Betreff: Re: [sqlite] Strategies to reduce page-loads?

>On 8/30/18, [hidden email] <[hidden email]> wrote:
>>
>>Structure is  simple:
>>CREATE TABLE Lines(Id LONG PRIMARY KEY, Label VARCHAR(50), Coordinates
>>BLOB, Flags INT, StyleId INT);
>>And an rtree-index:
>>CREATE VIRTUAL TABLE Lines_bb USING rtree (Id LONG PRIMARY KEY, X0
>>FLOAT, X1 FLOAT, Y0 FLOAT, Y1 FLOAT, Z0 FLOAT, Z1 FLOAT);
>
>Three points that might help, either separately or in combination:
>
>(1) Use exactly "INTEGER PRIMARY KEY".  "LONG PRIMARY KEY" and "INT
>PRIMARY KEY" are not the same thing and do not work as well.
>
>(2) In the very latest versions of SQLite, 3.24,0 and the beta for
>3.25.0, you can put the "Lines" information directly in the RTree:
>
>   CREATE VIRTUAL TABLE Lines_bb USING rtree(id, x0, x1, y0, y1, z0,
>z1, +Label, +Coordinates, +Flags, +StyleId);
>
>The extra columns in r-tree are prefaced by a "+" character so that
>the r-tree module knows that they are auxiliary columns and not extra
>coordinates.
>
>(3) Consider deliberating choosing INTEGER PRIMARY KEY values based on
>a "Morton code" or "Z-Order curve" of the coordinates.
>(https://en.wikipedia.org/wiki/Z-order_curve)  That will cause
>features that are close together geographically to tend to be close
>together within the file.  There is are two extension functions in the
>https://www.sqlite.org/src/artifact/b0ff58fa643afa1d file of the
>SQLite source tree that might help you with this.  Or you can do the
>same using your own functions.
>--
>D. Richard Hipp
>[hidden email]
>_______________________________________________
>sqlite-users mailing list
>[hidden email]
>http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Strategies to reduce page-loads?

Richard Hipp-3
On 8/30/18, [hidden email] <[hidden email]> wrote:
> Will change to INT PRIMARY KEY now.

It must be INTEGER PRIMARY KEY - spelled out.  INT PRIMARY KEY won't
work.  This is a quirk of SQLite.
--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Strategies to reduce page-loads?

David Raymond
In reply to this post by tf@qvgps.com
People being very specific about "integer primary key" is about another optimization by the way, and not because using "long" or "int" as a your data type is wrong in any way. Simply that "integer" primary key is needed for the optimization.

See: https://www.sqlite.org/lang_createtable.html#rowid



-----Original Message-----
From: sqlite-users [mailto:[hidden email]] On Behalf Of [hidden email]
Sent: Thursday, August 30, 2018 8:18 AM
To: SQLite mailing list
Subject: Re: [sqlite] Strategies to reduce page-loads?

Thanks guys for quick and competent answers!

After first sight, this "Z-Order curve" looks very promising, will give
it a try.

The LONG PRIMARY KEY is because  I need a 64-bit integer (osm-id).
I only learned now, that sqlite-int is also 64 bit long.
Will change to INT PRIMARY KEY now.

Tom


------ Originalnachricht ------
Von: "Richard Hipp" <[hidden email]>
An: "SQLite mailing list" <[hidden email]>
Gesendet: 30.08.2018 13:48:30
Betreff: Re: [sqlite] Strategies to reduce page-loads?

>On 8/30/18, [hidden email] <[hidden email]> wrote:
>>
>>Structure is  simple:
>>CREATE TABLE Lines(Id LONG PRIMARY KEY, Label VARCHAR(50), Coordinates
>>BLOB, Flags INT, StyleId INT);
>>And an rtree-index:
>>CREATE VIRTUAL TABLE Lines_bb USING rtree (Id LONG PRIMARY KEY, X0
>>FLOAT, X1 FLOAT, Y0 FLOAT, Y1 FLOAT, Z0 FLOAT, Z1 FLOAT);
>
>Three points that might help, either separately or in combination:
>
>(1) Use exactly "INTEGER PRIMARY KEY".  "LONG PRIMARY KEY" and "INT
>PRIMARY KEY" are not the same thing and do not work as well.
>
>(2) In the very latest versions of SQLite, 3.24,0 and the beta for
>3.25.0, you can put the "Lines" information directly in the RTree:
>
>   CREATE VIRTUAL TABLE Lines_bb USING rtree(id, x0, x1, y0, y1, z0,
>z1, +Label, +Coordinates, +Flags, +StyleId);
>
>The extra columns in r-tree are prefaced by a "+" character so that
>the r-tree module knows that they are auxiliary columns and not extra
>coordinates.
>
>(3) Consider deliberating choosing INTEGER PRIMARY KEY values based on
>a "Morton code" or "Z-Order curve" of the coordinates.
>(https://en.wikipedia.org/wiki/Z-order_curve)  That will cause
>features that are close together geographically to tend to be close
>together within the file.  There is are two extension functions in the
>https://www.sqlite.org/src/artifact/b0ff58fa643afa1d file of the
>SQLite source tree that might help you with this.  Or you can do the
>same using your own functions.
>--
>D. Richard Hipp
>[hidden email]
>_______________________________________________
>sqlite-users mailing list
>[hidden email]
>http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Strategies to reduce page-loads?

tf@qvgps.com
In reply to this post by Richard Hipp-3
It would be interesting to "measure" the effect of these ideas during
the process of optimizing.
I can profile and measure the execution times, but also interesting
would be to know, how much pages are involved in a specific query.

Is there maybe a way to get the count of pages currently used?



------ Originalnachricht ------
Von: "Richard Hipp" <[hidden email]>
An: "SQLite mailing list" <[hidden email]>
Gesendet: 30.08.2018 13:48:30
Betreff: Re: [sqlite] Strategies to reduce page-loads?

>On 8/30/18, [hidden email] <[hidden email]> wrote:
>>
>>Structure is  simple:
>>CREATE TABLE Lines(Id LONG PRIMARY KEY, Label VARCHAR(50), Coordinates
>>BLOB, Flags INT, StyleId INT);
>>And an rtree-index:
>>CREATE VIRTUAL TABLE Lines_bb USING rtree (Id LONG PRIMARY KEY, X0
>>FLOAT, X1 FLOAT, Y0 FLOAT, Y1 FLOAT, Z0 FLOAT, Z1 FLOAT);
>
>Three points that might help, either separately or in combination:
>
>(1) Use exactly "INTEGER PRIMARY KEY".  "LONG PRIMARY KEY" and "INT
>PRIMARY KEY" are not the same thing and do not work as well.
>
>(2) In the very latest versions of SQLite, 3.24,0 and the beta for
>3.25.0, you can put the "Lines" information directly in the RTree:
>
>   CREATE VIRTUAL TABLE Lines_bb USING rtree(id, x0, x1, y0, y1, z0,
>z1, +Label, +Coordinates, +Flags, +StyleId);
>
>The extra columns in r-tree are prefaced by a "+" character so that
>the r-tree module knows that they are auxiliary columns and not extra
>coordinates.
>
>(3) Consider deliberating choosing INTEGER PRIMARY KEY values based on
>a "Morton code" or "Z-Order curve" of the coordinates.
>(https://en.wikipedia.org/wiki/Z-order_curve)  That will cause
>features that are close together geographically to tend to be close
>together within the file.  There is are two extension functions in the
>https://www.sqlite.org/src/artifact/b0ff58fa643afa1d file of the
>SQLite source tree that might help you with this.  Or you can do the
>same using your own functions.
>--
>D. Richard Hipp
>[hidden email]
>_______________________________________________
>sqlite-users mailing list
>[hidden email]
>http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Strategies to reduce page-loads?

David Raymond
I know the CLI has the .stats option and the .scanstats option. I don't exactly what they implement, but here's an example output from a very quick query on something after turning both of those on. I think the page cache numbers are probably what you're most interested in. (I vaguely recall that things like the Virtual Machine steps will quietly overflow, so may show negative or way lower than you might expect)

More interesting queries will probably give more interesting numbers to look at.


sqlite> select recordtype, count(*) from foo where bar = 'something' group by recordtype order by recordtype;
QUERY PLAN
`--SEARCH TABLE foo USING COVERING INDEX idx_foo (bar=?)
recordtype|count(*)
F|48
G|1
H|540
P|68
S|2133
Memory Used:                         885360 (max 888328) bytes
Number of Outstanding Allocations:   1142 (max 1166)
Number of Pcache Overflow Bytes:     710416 (max 710416) bytes
Largest Allocation:                  120000 bytes
Largest Pcache Allocation:           4360 bytes
Lookaside Slots Used:                45 (max 100)
Successful lookaside attempts:       906
Lookaside failures due to size:      20
Lookaside failures due to OOM:       35
Pager Heap Usage:                    708616 bytes
Page cache hits:                     46
Page cache misses:                   162
Page cache writes:                   0
Page cache spills:                   0
Schema Heap Usage:                   46624 bytes
Statement Heap/Lookaside Usage:      37168 bytes
Fullscan Steps:                      0
Sort Operations:                     0
Autoindex Inserts:                   0
Virtual Machine Steps:               22395
Reprepare operations:                0
Number of times run:                 1
Memory used by prepared stmt:        37168
-------- scanstats --------
-------- subquery 8 -------
Loop  1: SEARCH TABLE foo USING COVERING INDEX idx_foo (bar=?)
         nLoop=1        nRow=2790     estRow=1024     estRow/Loop=1024
---------------------------
Run Time: real 0.032 user 0.000000 sys 0.000000

sqlite>



-----Original Message-----
From: sqlite-users [mailto:[hidden email]] On Behalf Of [hidden email]
Sent: Thursday, August 30, 2018 12:28 PM
To: SQLite mailing list
Subject: Re: [sqlite] Strategies to reduce page-loads?

It would be interesting to "measure" the effect of these ideas during
the process of optimizing.
I can profile and measure the execution times, but also interesting
would be to know, how much pages are involved in a specific query.

Is there maybe a way to get the count of pages currently used?



------ Originalnachricht ------
Von: "Richard Hipp" <[hidden email]>
An: "SQLite mailing list" <[hidden email]>
Gesendet: 30.08.2018 13:48:30
Betreff: Re: [sqlite] Strategies to reduce page-loads?

>On 8/30/18, [hidden email] <[hidden email]> wrote:
>>
>>Structure is  simple:
>>CREATE TABLE Lines(Id LONG PRIMARY KEY, Label VARCHAR(50), Coordinates
>>BLOB, Flags INT, StyleId INT);
>>And an rtree-index:
>>CREATE VIRTUAL TABLE Lines_bb USING rtree (Id LONG PRIMARY KEY, X0
>>FLOAT, X1 FLOAT, Y0 FLOAT, Y1 FLOAT, Z0 FLOAT, Z1 FLOAT);
>
>Three points that might help, either separately or in combination:
>
>(1) Use exactly "INTEGER PRIMARY KEY".  "LONG PRIMARY KEY" and "INT
>PRIMARY KEY" are not the same thing and do not work as well.
>
>(2) In the very latest versions of SQLite, 3.24,0 and the beta for
>3.25.0, you can put the "Lines" information directly in the RTree:
>
>   CREATE VIRTUAL TABLE Lines_bb USING rtree(id, x0, x1, y0, y1, z0,
>z1, +Label, +Coordinates, +Flags, +StyleId);
>
>The extra columns in r-tree are prefaced by a "+" character so that
>the r-tree module knows that they are auxiliary columns and not extra
>coordinates.
>
>(3) Consider deliberating choosing INTEGER PRIMARY KEY values based on
>a "Morton code" or "Z-Order curve" of the coordinates.
>(https://en.wikipedia.org/wiki/Z-order_curve)  That will cause
>features that are close together geographically to tend to be close
>together within the file.  There is are two extension functions in the
>https://www.sqlite.org/src/artifact/b0ff58fa643afa1d file of the
>SQLite source tree that might help you with this.  Or you can do the
>same using your own functions.
>--
>D. Richard Hipp
>[hidden email]
>_______________________________________________
>sqlite-users mailing list
>[hidden email]
>http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Strategies to reduce page-loads?

tf@qvgps.com
In reply to this post by Richard Hipp-3
>
>(3) Consider deliberating choosing INTEGER PRIMARY KEY values based on
>a "Morton code" or "Z-Order curve" of the coordinates.
>(https://en.wikipedia.org/wiki/Z-order_curve)  That will cause
>features that are close together geographically to tend to be close
>together within the file.

My primary key is actually the Id of the specific object in the
OpenStreetMap-database, and we also need this osm-id in the app.
I was trying just to order all rows by the "Z-Order curve"-value first
before inserting them.

for each (line in lines.ordered.by.zvalue)
{
     insert line  into lines
     insert line  into lines_rtree
}

But this doesn't seem to work.
At least, I don't see any improvements in page-usage.

So is it just the value of the primary key controlling in which page the
row is stored?





_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Strategies to reduce page-loads?

Richard Hipp-3
On 8/31/18, [hidden email] <[hidden email]> wrote:
>
> So is it just the value of the primary key controlling in which page the
> row is stored?

The page on which content is stored is determine (approximately) by
the value of the ROWID, which is the same as the INTEGER PRIMARY KEY
as long as you declare the primary key to be of type "INTEGER".  If
you declare the PRIMARY KEY to be something other than "INTEGER" (for
example: "INT" or "LONG") then the ROWID and the primary key are
different and the primary key has no influence over where the content
is stored.

Or if you create a WITHOUT ROWID table, then the PRIMARY KEY is the
value that determines (approximately) on which page the content is
stored.
--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Strategies to reduce page-loads?

tf@qvgps.com
Ok, then WITHOUT ROWID will most properly fit best in our use case.
Then I can fill the PRIMARY KEY with the z-order and store the osm-id
just in another column.

But do I still need to fill the table in the correct order according to
z-order?
I mean, we are talking about 1mio rows or so.
At which point during insert are the pages actually written?


------ Originalnachricht ------
Von: "Richard Hipp" <[hidden email]>
An: "SQLite mailing list" <[hidden email]>
Gesendet: 31.08.2018 15:10:15
Betreff: Re: [sqlite] Strategies to reduce page-loads?

>On 8/31/18, [hidden email] <[hidden email]> wrote:
>>
>>So is it just the value of the primary key controlling in which page
>>the
>>row is stored?
>
>The page on which content is stored is determine (approximately) by
>the value of the ROWID, which is the same as the INTEGER PRIMARY KEY
>as long as you declare the primary key to be of type "INTEGER".  If
>you declare the PRIMARY KEY to be something other than "INTEGER" (for
>example: "INT" or "LONG") then the ROWID and the primary key are
>different and the primary key has no influence over where the content
>is stored.
>
>Or if you create a WITHOUT ROWID table, then the PRIMARY KEY is the
>value that determines (approximately) on which page the content is
>stored.
>--
>D. Richard Hipp
>[hidden email]
>_______________________________________________
>sqlite-users mailing list
>[hidden email]
>http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Strategies to reduce page-loads?

Richard Hipp-3
On 8/31/18, [hidden email] <[hidden email]> wrote:
> Ok, then WITHOUT ROWID will most properly fit best in our use case.
> Then I can fill the PRIMARY KEY with the z-order and store the osm-id
> just in another column.

I would think that your best approach is to make the INTEGER PRIMARY
KEY be the Morton code and then store the osm-id in a separate UNIQUE
column.

>
> But do I still need to fill the table in the correct order according to
> z-order?
> I mean, we are talking about 1mio rows or so.
> At which point during insert are the pages actually written?

The table-fill will go much faster if you do the inserts in ROWID or
INTEGER PRIMARY KEY order, then do a "CREATE UNIQUE INDEX" on the
osm-id after all inserts have completed.  But it will work in either
case.

--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Strategies to reduce page-loads?

J Decker
In reply to this post by Richard Hipp-3
On Thu, Aug 30, 2018 at 4:48 AM Richard Hipp <[hidden email]> wrote:

> On 8/30/18, [hidden email] <[hidden email]> wrote:
> >
> > Structure is  simple:
> > CREATE TABLE Lines(Id LONG PRIMARY KEY, Label VARCHAR(50), Coordinates
> > BLOB, Flags INT, StyleId INT);
> > And an rtree-index:
> > CREATE VIRTUAL TABLE Lines_bb USING rtree (Id LONG PRIMARY KEY, X0
> > FLOAT, X1 FLOAT, Y0 FLOAT, Y1 FLOAT, Z0 FLOAT, Z1 FLOAT);
>
> Three points that might help, either separately or in combination:
>
> (1) Use exactly "INTEGER PRIMARY KEY".  "LONG PRIMARY KEY" and "INT
> PRIMARY KEY" are not the same thing and do not work as well.
>
> (2) In the very latest versions of SQLite, 3.24,0 and the beta for
> 3.25.0, you can put the "Lines" information directly in the RTree:
>
>    CREATE VIRTUAL TABLE Lines_bb USING rtree(id, x0, x1, y0, y1, z0,
> z1, +Label, +Coordinates, +Flags, +StyleId);
>
> The extra columns in r-tree are prefaced by a "+" character so that
> the r-tree module knows that they are auxiliary columns and not extra
> coordinates.
>
> (3) Consider deliberating choosing INTEGER PRIMARY KEY values based on
> a "Morton code" or "Z-Order curve" of the coordinates.
>

Morton code and zorder curves look, initially, to be good for keeping near
things near, but the average distance for two elements is much greater than
the row skip in a similar linear col + n*rows type flat array; and more
often will span +4 distinct pages instead of being just 1 or 2 for here
and +/- 1 page for rows above/below

On the 2^n boundaries, the skips become very significant, and grabbing
random queries is guaranteed to cover more space.  so like at 15,15,15 to
16,16,16 there is a huge jump in space ( 4096) instead of a constant offset.

There was a voxel engine that was claiming they were going to move to a
morton encoding; and I was working with a different engine, so I built a
simulator to test averge lookup distances; it was far more efficient to
keep sectors of voxels (32x32x32) in flat indexing, which made the maximum
distance 1025 ( but along that row is +1023, 1024, 1025, which are all in
the same page, where morton would be like +512, +1024, +2048, which makes
it much more likely to overflow to yet another page.  (since the cells
arent' just bytes, all indexes should be mulitplied by cell structure size)

(https://en.wikipedia.org/wiki/Z-order_curve)  That will cause

> features that are close together geographically to tend to be close
> together within the file.  There is are two extension functions in the
> https://www.sqlite.org/src/artifact/b0ff58fa643afa1d file of the
> SQLite source tree that might help you with this.  Or you can do the
> same using your own functions.
> --
> D. Richard Hipp
> [hidden email]
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Strategies to reduce page-loads?

Simon Slavin-3
On 31 Aug 2018, at 2:46pm, J Decker <[hidden email]> wrote:

> There was a voxel engine that was claiming they were going to move to a
> morton encoding; and I was working with a different engine, so I built a
> simulator to test averge lookup distances; it was far more efficient to
> keep sectors of voxels (32x32x32) in flat indexing, which made the maximum
> distance 1025

I can confirm that SatNav units do not keep their maps in Morton code order.  It's not a no-brainer go-to solution for mapping.  However, the analysis done to figure out a good storage order is rather complicated and off-topic for this list.

Simon.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Strategies to reduce page-loads?

tf@qvgps.com
Right.

Was trying it out now, compiling some osm-dbs with primary key generated
with this morton encoding from lat,lon and the performance is even
worse.
Debugging with the sqlite-tool shows, that the page counts for specific
queries are almost double then before.

Seems like, from the sqlite-side the only options is to have page size
as big as possible and line-data in the blob-field as much compressed as
possible.



------ Originalnachricht ------
Von: "Simon Slavin" <[hidden email]>
An: "SQLite mailing list" <[hidden email]>
Gesendet: 31.08.2018 19:07:36
Betreff: Re: [sqlite] Strategies to reduce page-loads?

>On 31 Aug 2018, at 2:46pm, J Decker <[hidden email]> wrote:
>
>>There was a voxel engine that was claiming they were going to move to
>>a
>>morton encoding; and I was working with a different engine, so I built
>>a
>>simulator to test averge lookup distances; it was far more efficient
>>to
>>keep sectors of voxels (32x32x32) in flat indexing, which made the
>>maximum
>>distance 1025
>
>I can confirm that SatNav units do not keep their maps in Morton code
>order.  It's not a no-brainer go-to solution for mapping.  However, the
>analysis done to figure out a good storage order is rather complicated
>and off-topic for this list.
>
>Simon.
>_______________________________________________
>sqlite-users mailing list
>[hidden email]
>http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users