<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:x="urn:schemas-microsoft-com:office:excel" xmlns:p="urn:schemas-microsoft-com:office:powerpoint" xmlns:a="urn:schemas-microsoft-com:office:access" xmlns:dt="uuid:C2F41010-65B3-11d1-A29F-00AA00C14882" xmlns:s="uuid:BDC6E3F0-6DA3-11d1-A2A3-00AA00C14882" xmlns:rs="urn:schemas-microsoft-com:rowset" xmlns:z="#RowsetSchema" xmlns:b="urn:schemas-microsoft-com:office:publisher" xmlns:ss="urn:schemas-microsoft-com:office:spreadsheet" xmlns:c="urn:schemas-microsoft-com:office:component:spreadsheet" xmlns:oa="urn:schemas-microsoft-com:office:activation" xmlns:html="http://www.w3.org/TR/REC-html40" xmlns:q="http://schemas.xmlsoap.org/soap/envelope/" xmlns:D="DAV:" xmlns:x2="http://schemas.microsoft.com/office/excel/2003/xml" xmlns:ois="http://schemas.microsoft.com/sharepoint/soap/ois/" xmlns:dir="http://schemas.microsoft.com/sharepoint/soap/directory/" xmlns:ds="http://www.w3.org/2000/09/xmldsig#" xmlns:dsp="http://schemas.microsoft.com/sharepoint/dsp" xmlns:udc="http://schemas.microsoft.com/data/udc" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:sub="http://schemas.microsoft.com/sharepoint/soap/2002/1/alerts/" xmlns:ec="http://www.w3.org/2001/04/xmlenc#" xmlns:sp="http://schemas.microsoft.com/sharepoint/" xmlns:sps="http://schemas.microsoft.com/sharepoint/soap/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:udcxf="http://schemas.microsoft.com/data/udc/xmlfile" xmlns:wf="http://schemas.microsoft.com/sharepoint/soap/workflow/" xmlns:mver="http://schemas.openxmlformats.org/markup-compatibility/2006" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns:mrels="http://schemas.openxmlformats.org/package/2006/relationships" xmlns:ex12t="http://schemas.microsoft.com/exchange/services/2006/types" xmlns:ex12m="http://schemas.microsoft.com/exchange/services/2006/messages" 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: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;
font-family:"Calibri","sans-serif";
color:#1F497D;}
span.EmailStyle22
{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><span style='color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='color:#1F497D'>Yes, in a use case where the
file is opened and closed a lot, without the ability to keep any cache context
in memory, a spatial index which is also in a file (but not necessarily the
same file) would be better. This is not the case, at least with the FDO client
apps that I know of, so for now there is no need to serialize the spatial
index. It would be easy to do so if there is such a need in the future.<o:p></o:p></span></p>
<p class=MsoNormal><span style='color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='color:#1F497D'>Traian<o:p></o:p></span></p>
<p class=MsoNormal><span style='color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='color:#1F497D'><o:p> </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> Wednesday, March 26, 2008 7:25 AM<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 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>
<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>>>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>
<br>
<o:p></o:p></p>
<p class=MsoNormal><span style='color:#1F497D'> </span><o:p></o:p></p>
<p class=MsoNormal><span style='color:#1F497D'> </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 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</span><o:p></o:p></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>
<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'> </span><o:p></o:p></p>
<p class=MsoNormal><span style='color:#1F497D'>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:#1F497D'> </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’s not *<b>that</b>* fast.</span><o:p></o:p></p>
<p class=MsoNormal><span style='color:#1F497D'> </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'> </span><o:p></o:p></p>
<p class=MsoNormal><span style='color:#1F497D'> </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'> </span><o:p></o:p></p>
<p class=MsoNormal><span style='color:#1F497D'> </span><o:p></o:p></p>
<p class=MsoNormal><span style='color:#1F497D'> </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'>
<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> <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>
<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 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'><o:p> </o:p></pre><pre style='text-align:center'>
<hr size=4 width="90%" align=center>
</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
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
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> <o:p></o:p></pre></div>
<pre> <o:p></o:p></pre><pre style='text-align:center'><o:p> </o:p></pre><pre
style='text-align:center'>
<hr size=4 width="90%" align=center>
</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
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> <o:p></o:p></pre></div>
<pre><o:p> </o:p></pre><pre style='text-align:center'>
<hr size=4 width="90%" align=center>
</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
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> <o:p></o:p></pre></div>
</div>
</body>
</html>