<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
I see.<br>
<br>
I did not know about the column count/index problem for SQLite.<br>
I can see that in a purely MapGuide context, there would be great
benefit from inital parsing of all geometry.<br>
I was thinking in a more general context, where the database would
open/close regularly.<br>
In such a context, creating a search tree from scratch seems like a big
deal.<br>
<br>
Thank you for clearing that up.<br>
<br>
<pre class="moz-signature" cols="72">Regards, Kenneth, GEOGRAF A/S
</pre>
<br>
<br>
Traian Stanev skrev:
<blockquote
cite="mid:D20FC5C02CA4AB41891CFE76D91C57A925300D69D9@ADSK-NAMSG-02.MGDADSK.autodesk.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; ">
<meta name="Generator" content="Microsoft Word 12 (filtered medium)">
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]-->
<style>
<!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";
color:black;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0in;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";
color:black;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;
color:black;}
span.EmailStyle19
{mso-style-type:personal;
font-family:"Calibri","sans-serif";
color:windowtext;}
span.EmailStyle20
{mso-style-type:personal;
font-family:"Calibri","sans-serif";
color:#1F497D;}
span.EmailStyle21
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page Section1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.Section1
{page:Section1;}
-->
</style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
<div class="Section1">
<p class="MsoNormal">>>I can't figure out how to
extract/compute the BBOX
from an SQLite BLOB, without parsing the geometry.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">You are right, there is no other way to get the
bounding
box. <o:p></o:p></p>
<p class="MsoNormal"><br>
>>I belive that it is faster to read the BBOX values rather than
a
potentially large BLOB field.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">This is debatable. One thing about SQLite is
that its read performance
is *<b>VERY</b>* sensitive to how many columns there are in the table.
If the
BBOX columns are the last ones in a 50 column table, and the geometry
is the
first column, you can probably compute the bounds faster than you can
offset
all the way to the end of the row. On the other hand, if you put the
BBOX
columns first, you handicap access to all other columns by 4 columns.
Also, in
a huge segment of GIS data (namely point data), computing the bounds
from the
BLOB would be faster than getting it from the BBOX columns.<br>
<br>
>>I agree that it would use some space to add the columns, but
adding the
columns would enable a fast filtering of unused features.<br>
>>As for the 4 times index, one could merely add index for the x
values,
and then use sequential filtering for the y values. <o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Yes, such a scheme is possible and you would
reduce the
spatial search to two B-Tree searches. It also means you end up with a
linear
worst case search, if your search bounds is really wide but not very
tall for
example. This sounds like a lousy deal for adding ~40 bytes’ worth of
stuff to every row, not counting the index tables, of which you need
two (one
for minx and one for maxx). Index tables would cost something like 10
bytes per
row at least (I am not sure exactly how SQLite implements indexes, but
you have
to figure it has at least the double value in there, plus a row offset
for it).<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><br>
>> Is your internal spatial index algorithm absolutely without
benefit
from added BBOX columns?<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">It computes bounding boxes and the spatial index
on the fly,
during the first table scan after the FDO connection is open. This will
play
well with FDO clients like MapGuide which keep connections pooled. In
my
benchmarks, computing bounding boxes has not been a big overhead. The
cost of
the spatial index in its prototype form, per feature, is roughly 20
bytes in
RAM.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">So to sum up, you can add BBOX columns to your
SQLite
databases if it helps you with spatial searches. The provider does not
need
them, so it will not require them. It will also not complain if they
are there –
it would treat them as regular columns.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Traian<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><br>
<br>
<span style="color: rgb(31, 73, 125);"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="color: rgb(31, 73, 125);"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="color: rgb(31, 73, 125);"><o:p> </o:p></span></p>
<div
style="border-style: none none none solid; border-color: -moz-use-text-color -moz-use-text-color -moz-use-text-color blue; border-width: medium medium medium 1.5pt; padding: 0in 0in 0in 4pt;">
<div>
<div
style="border-style: solid none none; border-color: rgb(181, 196, 223) -moz-use-text-color -moz-use-text-color; border-width: 1pt medium medium; padding: 3pt 0in 0in;">
<p class="MsoNormal"><b><span
style="font-size: 10pt; font-family: "Tahoma","sans-serif"; color: windowtext;">From:</span></b><span
style="font-size: 10pt; font-family: "Tahoma","sans-serif"; color: windowtext;">
<a class="moz-txt-link-abbreviated" href="mailto:fdo-internals-bounces@lists.osgeo.org">fdo-internals-bounces@lists.osgeo.org</a>
[<a class="moz-txt-link-freetext" href="mailto:fdo-internals-bounces@lists.osgeo.org">mailto:fdo-internals-bounces@lists.osgeo.org</a>] <b>On Behalf Of </b>Kenneth,
GEOGRAF A/S<br>
<b>Sent:</b> Tuesday, March 25, 2008 4:54 PM<br>
<b>To:</b> FDO Internals Mail List<br>
<b>Subject:</b> Re: [fdo-internals] FDO RFC 16 - FDO Provider for
SQLite<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I can't figure out how to extract/compute the
BBOX from an
SQLite BLOB, without parsing the geometry.<br>
I belive that it is faster to read the BBOX values rather than a
potentially
large BLOB field.<br>
<br>
I agree that it would use some space to add the columns, but adding the
columns
would enable a fast filtering of unused features.<br>
As for the 4 times index, one could merely add index for the x values,
and then
use sequential filtering for the y values. <br>
<br>
Is your internal spatial index algorithm absolutely without benefit
from added
BBOX columns?<br>
<br>
<br>
<o:p></o:p></p>
<pre>Regards, Kenneth, GEOGRAF A/S<o:p></o:p></pre>
<p class="MsoNormal"><br>
<br>
Traian Stanev skrev: <o:p></o:p></p>
<p class="MsoNormal"><span style="color: rgb(31, 73, 125);"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="color: rgb(31, 73, 125);">It’s a
waste of space to
store BBOX. It would cost at least 32 bytes per feature, not counting
the
indexes.</span><o:p></o:p></p>
<p class="MsoNormal"><span style="color: rgb(31, 73, 125);"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="color: rgb(31, 73, 125);">Also, you
can easily compute the
bounding box and add those 4 columns very quickly when you need them,
given
that SQLite is pretty fast to read from. Indexing on the 4 BBOX columns
would
make spatial queries have to compute the intersection of the results of
4 tree
searches. SQLite is fast, but it’s not *<b>that</b>* fast.</span><o:p></o:p></p>
<p class="MsoNormal"><span style="color: rgb(31, 73, 125);"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="color: rgb(31, 73, 125);">Anyway,
the nice thing about
this format is that you can create the BBOX columns anyway, and use
them. The
FDO provider will not be using it though, for performance reasons.</span><o:p></o:p></p>
<p class="MsoNormal"><span style="color: rgb(31, 73, 125);"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="color: rgb(31, 73, 125);"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="color: rgb(31, 73, 125);">Traian</span><o:p></o:p></p>
<p class="MsoNormal"><span style="color: rgb(31, 73, 125);"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="color: rgb(31, 73, 125);"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="color: rgb(31, 73, 125);"> </span><o:p></o:p></p>
<div
style="border-style: none none none solid; border-color: -moz-use-text-color -moz-use-text-color -moz-use-text-color blue; border-width: medium medium medium 1.5pt; padding: 0in 0in 0in 4pt;">
<div>
<div
style="border-style: solid none none; border-color: -moz-use-text-color; border-width: 1pt medium medium; padding: 3pt 0in 0in;">
<p class="MsoNormal"><b><span
style="font-size: 10pt; font-family: "Tahoma","sans-serif"; color: windowtext;">From:</span></b><span
style="font-size: 10pt; font-family: "Tahoma","sans-serif"; color: windowtext;">
<a moz-do-not-send="true"
href="mailto:fdo-internals-bounces@lists.osgeo.org">fdo-internals-bounces@lists.osgeo.org</a>
[<a moz-do-not-send="true"
href="mailto:fdo-internals-bounces@lists.osgeo.org">mailto:fdo-internals-bounces@lists.osgeo.org</a>]
<b>On Behalf Of </b>Kenneth, GEOGRAF A/S<br>
<b>Sent:</b> Tuesday, March 25, 2008 7:12 AM<br>
<b>To:</b> FDO Internals Mail List<br>
<b>Subject:</b> Re: [fdo-internals] FDO RFC 16 - FDO Provider for
SQLite</span><o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">I just re-read the RFC.<br>
<br>
What are your reasons for not storing BBOX releated data in the data
table?<o:p></o:p></p>
<p class="MsoNormal"><br>
<br>
I would suggest adding four columns, like minx, maxx, miny, max
(perhaps name
them via. the geometry_columns table?).<br>
With that approach, and index on the pairs would move the BBOX query
load/optimization into the DBMS.<br>
BBOX queries are simple, and does not require reading the actual column
data.<br>
<br>
Your extended spatial index algorithm might read these values to
produce the
search tree.<br>
<br>
Another suggestion, would be to store the search tree in a blob column.<br>
That would enable a much faster load of data.<br>
<br>
To avoid the requirement that all data updaters know the algorithm, it
might be
legal to just clear the BLOB data on updates.<br>
<br>
I wrote a short paper on a similar mechanism some time ago, with a
friend:<br>
<a moz-do-not-send="true"
href="http://www.hexad.dk/opensource/spatialdbms.pdf">http://www.hexad.dk/opensource/spatialdbms.pdf</a><br>
<br>
<br>
<br>
<br>
<o:p></o:p></p>
<pre>Regards, Kenneth, GEOGRAF A/S<o:p></o:p></pre>
<p class="MsoNormal"><br>
<br>
Traian Stanev skrev: <o:p></o:p></p>
<p class="MsoNormal">Hello,<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">I just posted FDO RFC #16. Fresh off the virtual
presses
(printed on 100% recycled electrons, for you green-minded folks):<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><a moz-do-not-send="true"
href="http://trac.osgeo.org/fdo/wiki/FDORfc16">http://trac.osgeo.org/fdo/wiki/FDORfc16</a><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">Thanks,<o:p></o:p></p>
<p class="MsoNormal">Traian<o:p></o:p></p>
<pre> <o:p></o:p></pre>
<pre style="text-align: center;"><o:p> </o:p></pre>
<pre style="text-align: center;">
<hr align="center" size="4" width="90%">
</pre>
<pre style="text-align: center;"><o:p> </o:p></pre>
<pre style="text-align: center;"><o:p> </o:p></pre>
<pre style="text-align: center;"> <o:p></o:p></pre>
<pre> <o:p></o:p></pre>
<pre>_______________________________________________<o:p></o:p></pre>
<pre>fdo-internals mailing list<o:p></o:p></pre>
<pre><a moz-do-not-send="true"
href="mailto:fdo-internals@lists.osgeo.org">fdo-internals@lists.osgeo.org</a><o:p></o:p></pre>
<pre><a moz-do-not-send="true"
href="http://lists.osgeo.org/mailman/listinfo/fdo-internals">http://lists.osgeo.org/mailman/listinfo/fdo-internals</a><o:p></o:p></pre>
<pre> <o:p></o:p></pre>
</div>
<pre><o:p> </o:p></pre>
<pre style="text-align: center;">
<hr align="center" size="4" width="90%">
</pre>
<pre><o:p> </o:p></pre>
<pre>_______________________________________________<o:p></o:p></pre>
<pre>fdo-internals mailing list<o:p></o:p></pre>
<pre><a moz-do-not-send="true"
href="mailto:fdo-internals@lists.osgeo.org">fdo-internals@lists.osgeo.org</a><o:p></o:p></pre>
<pre><a moz-do-not-send="true"
href="http://lists.osgeo.org/mailman/listinfo/fdo-internals">http://lists.osgeo.org/mailman/listinfo/fdo-internals</a><o:p></o:p></pre>
<pre> <o:p></o:p></pre>
</div>
</div>
<pre wrap="">
<hr size="4" width="90%">
_______________________________________________
fdo-internals mailing list
<a class="moz-txt-link-abbreviated" href="mailto:fdo-internals@lists.osgeo.org">fdo-internals@lists.osgeo.org</a>
<a class="moz-txt-link-freetext" href="http://lists.osgeo.org/mailman/listinfo/fdo-internals">http://lists.osgeo.org/mailman/listinfo/fdo-internals</a>
</pre>
</blockquote>
</body>
</html>