<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">

<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<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]-->
</head>

<body bgcolor=white lang=EN-US link=blue vlink=purple>

<div class=Section1>

<p class=MsoNormal>&gt;&gt;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>&nbsp;</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>
&gt;&gt;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>&nbsp;</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>
&gt;&gt;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>
&gt;&gt;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>&nbsp;</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&#8217; 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>&nbsp;</o:p></p>

<p class=MsoNormal><br>
&gt;&gt; Is your internal spatial index algorithm absolutely without benefit
from added BBOX columns?<o:p></o:p></p>

<p class=MsoNormal><o:p>&nbsp;</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>&nbsp;</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 &#8211;
it would treat them as regular columns.<o:p></o:p></p>

<p class=MsoNormal><o:p>&nbsp;</o:p></p>

<p class=MsoNormal><o:p>&nbsp;</o:p></p>

<p class=MsoNormal>Traian<o:p></o:p></p>

<p class=MsoNormal><o:p>&nbsp;</o:p></p>

<p class=MsoNormal><o:p>&nbsp;</o:p></p>

<p class=MsoNormal><br>
<br>
<span style='color:#1F497D'><o:p></o:p></span></p>

<p class=MsoNormal><span style='color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<div style='border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt'>

<div>

<div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in'>

<p class=MsoNormal><b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif";
color:windowtext'>From:</span></b><span style='font-size:10.0pt;font-family:
"Tahoma","sans-serif";color:windowtext'> fdo-internals-bounces@lists.osgeo.org
[mailto:fdo-internals-bounces@lists.osgeo.org] <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>&nbsp;</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:#1F497D'>&nbsp;</span><o:p></o:p></p>

<p class=MsoNormal><span style='color:#1F497D'>It&#8217;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:#1F497D'>&nbsp;</span><o:p></o:p></p>

<p class=MsoNormal><span style='color:#1F497D'>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&#8217;s not *<b>that</b>* fast.</span><o:p></o:p></p>

<p class=MsoNormal><span style='color:#1F497D'>&nbsp;</span><o:p></o:p></p>

<p class=MsoNormal><span style='color:#1F497D'>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:#1F497D'>&nbsp;</span><o:p></o:p></p>

<p class=MsoNormal><span style='color:#1F497D'>&nbsp;</span><o:p></o:p></p>

<p class=MsoNormal><span style='color:#1F497D'>Traian</span><o:p></o:p></p>

<p class=MsoNormal><span style='color:#1F497D'>&nbsp;</span><o:p></o:p></p>

<p class=MsoNormal><span style='color:#1F497D'>&nbsp;</span><o:p></o:p></p>

<p class=MsoNormal><span style='color:#1F497D'>&nbsp;</span><o:p></o:p></p>

<div style='border:none;border-left:solid windowtext 1.5pt;padding:0in 0in 0in 4.0pt;
border-color:-moz-use-text-color -moz-use-text-color -moz-use-text-color blue'>

<div>

<div style='border:none;border-top:solid windowtext 1.0pt;padding:3.0pt 0in 0in 0in;
border-color:-moz-use-text-color -moz-use-text-color'>

<p class=MsoNormal><b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif";
color:windowtext'>From:</span></b><span style='font-size:10.0pt;font-family:
"Tahoma","sans-serif";color:windowtext'> <a
href="mailto:fdo-internals-bounces@lists.osgeo.org">fdo-internals-bounces@lists.osgeo.org</a>
[<a 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>&nbsp;<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 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>&nbsp;<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>&nbsp;<o:p></o:p></p>

<p class=MsoNormal><a href="http://trac.osgeo.org/fdo/wiki/FDORfc16">http://trac.osgeo.org/fdo/wiki/FDORfc16</a><o:p></o:p></p>

<p class=MsoNormal>&nbsp;<o:p></o:p></p>

<p class=MsoNormal>&nbsp;<o:p></o:p></p>

<p class=MsoNormal>Thanks,<o:p></o:p></p>

<p class=MsoNormal>Traian<o:p></o:p></p>

<pre>&nbsp;<o:p></o:p></pre><pre style='text-align:center'><o:p>&nbsp;</o:p></pre><pre
style='text-align:center'>

<hr size=4 width="90%" align=center>

</pre><pre style='text-align:center'><o:p>&nbsp;</o:p></pre><pre
style='text-align:center'><o:p>&nbsp;</o:p></pre><pre style='text-align:center'>&nbsp; <o:p></o:p></pre><pre>&nbsp;<o:p></o:p></pre><pre>_______________________________________________<o:p></o:p></pre><pre>fdo-internals mailing list<o:p></o:p></pre><pre><a
href="mailto:fdo-internals@lists.osgeo.org">fdo-internals@lists.osgeo.org</a><o:p></o:p></pre><pre><a
href="http://lists.osgeo.org/mailman/listinfo/fdo-internals">http://lists.osgeo.org/mailman/listinfo/fdo-internals</a><o:p></o:p></pre><pre>&nbsp; <o:p></o:p></pre></div>

<pre><o:p>&nbsp;</o:p></pre><pre style='text-align:center'>

<hr size=4 width="90%" align=center>

</pre><pre><o:p>&nbsp;</o:p></pre><pre>_______________________________________________<o:p></o:p></pre><pre>fdo-internals mailing list<o:p></o:p></pre><pre><a
href="mailto:fdo-internals@lists.osgeo.org">fdo-internals@lists.osgeo.org</a><o:p></o:p></pre><pre><a
href="http://lists.osgeo.org/mailman/listinfo/fdo-internals">http://lists.osgeo.org/mailman/listinfo/fdo-internals</a><o:p></o:p></pre><pre>&nbsp; <o:p></o:p></pre></div>

</div>

</body>

</html>