Which is best to search on lat and lon or on a POINT

[Jim]

I am building a table of coordinates and other indicative information for set of locations.

Over time this table could become quite large.

The table with contain the latitude and longitude as FLOAT values and a  spatialite POINT built with the same latitude and longitude.

The table will be indexed on the  latitude and longitude  and with a SpatialIndex on the POINT.

Which is the fastest way to search the table using  latitude and longitude  , the Sqlite index or the SpatialIndex?

If the answer is the Sqlite indices, should those indices be the latitude and longitude individually or as an combined index of the latitude and longitude?

If the answer is SpatialIndex, what would that query look like?

Regards,

Jim

[a.fu...@lqt.it]

On Wed, 3 Apr 2024 09:44:55 -0700 (PDT), Jim wrote:
> I am building a table of coordinates and other indicative information
> for set of locations.
>
> Over time this table could become quite large.
>
> The table with contain the latitude and longitude as FLOAT values and
> a  spatialite POINT built with the same latitude and longitude.
>
> The table will be indexed on the  latitude and longitude  and with a
> SpatialIndex on the POINT.
>
> Which is the fastest way to search the table using  latitude and
> longitude  , the Sqlite index or the SpatialIndex?
>

Hi Jim,

I suppose that to deal with a spatial indexing problem, nothing can
beat the R*Tree, i.e. the SpatialIndex, an algorithm designed
specifically for this problem.

> If the answer is the Sqlite indices, should those indices be the
> latitude and longitude individually or as an combined index of the
> latitude and longitude?
>

Working on indices based on floats seems decidedly very unpromising
to me.
One axis will always have priority over the other, so the result
will be a very inefficient spatial filter.

perhaps it might be more promising to use Hilbert codes, but I
see it as a very theoretical possibility.
In any case, newer versions of SpatiaLite support the HilbertCode()
SQL function, but it will certainly take a lot of extra work to get
something usable.

please see for more details:
https://en.wikipedia.org/wiki/Hilbert_curve

> If the answer is SpatialIndex, what would that query look like?
>

CREATE TABLE my_table (
id INTEGER PRIMARY KEY.
... any other stuff ..);

SELECT AddGeometryColumn('my_table', 'geom', 4326, 'POINT', 'XY');
SELECT CreateSpatialIndex('my_table', 'geom'):

SELECT id [, any_other_stuff]
FROM my_table
WHERE rowid IN (SELECT ROWID FROM SpatialIndex
WHERE f_table_name = 'my_table'
AND search_frame = BuildCircleMBR(X, Y, R));

note: X, Y are the coodinates of your refence POINT
and R is the radius of the circle (beware: if you
work with Longitude ana Latitudes it should be
measured in ANGULAR DEGREES).

if for your needs a reasonable approximation
might be acceptable this trick could speed up
your query by making it unnecessary to call
ST_Distance() or any other Spatial function.

bye Sandro

[Jim]

Sandro,

Thank you for that response. I am using it and it works just fine, as I expected.

A modification if I may ask?

How can I assure that the item in the response to the query is closest to the center of the circle?

Is that builtin to the functions or could you show me the changes to the query?

I apologize for asking so much detail but I am under some pressure to get this done and Spatialite is something that I unfortunately use infreguently.

Regards,

Jim

[a.fu...@lqt.it]

On Thu, 4 Apr 2024 07:24:07 -0700 (PDT), Jim wrote:
> How can I assure that the item in the response to the query is
> closest
> to the center of the circle?
>
> Is that builtin to the functions or could you show me the changes to
> the query?
>

Hi Jim,

the SpatialIndex is based on R*Tree, which is simply a Tree
of Rectangles as the name itself suggests.

BuildCircleMbr() simply builds a circle around the given
Refernce Point, giving then the circumscribed square.
Everything that falls within that square passes through
the SpatialIndex filter.

when there are multiple Geometries satisfyind the coarse
(but very fast) filter of the square, if you want to be
sure to get only the closest to the center of the circle
then you need to calculate the distance, an operation
that certainly slows down the Query.

to avoid needlessly calling ST_Distance() more times
we'll therefore use the synthactic trick of an Inner
SubQuery something like this:

SELECT x.id, x.a, x.b, x.c
FROM (SELECT id, a, b, c,
ST_Distance(geom, MakePoint(X, Y)) AS dist
FROM my_table
WHERE ROWID IN (SELECT ROWID FROM SpatialIndex

WHERE f_table_name = 'my_table' AND

search_frame = BuildCircleMbr(X, Y, R))) AS x
ORDER BY x.dist
LIMIT 1;

this will surely return a single POINT (or none),
with the absolute guarantee that it will be the
closest one to the center of the circle.

NOTE: X and Y are the coordinates of your reference
Point and R is the radius of the circle.

it should be the most efficient Query to solve
your problem.

best regards,
Sandro

[Jim]

Sandro,

Thank you, that worked great.

If I could extend the question a bit now that I'm starting to understand the SpatialIndex a bit.

If I took the query you wrote:

SELECT id [, any_other_stuff]
FROM my_table

WHERE rowid IN (SELECT ROWID FROM SpatialIndex
   WHERE f_table_name = 'my_table'
         AND search_frame = BuildCircleMBR(X, Y, R));

  and wanted to change it to lookup the same reference point, POINT(X,Y)  but this time look up which row it was in in a database  (my_table) containing one  MultiPolygon per row called 'geom',  how would I write the  'BuildMBR' in the SpatialIndex part of the query?  

Or have I got this all wrong.

Regards,

Jim

[a.fu...@lqt.it]

On Fri, 5 Apr 2024 08:04:47 -0700 (PDT), Jim wrote:
> If I took the query you wrote:
>
> SELECT id [, any_other_stuff]
> FROM my_table
> WHERE rowid IN (SELECT ROWID FROM SpatialIndex
>    WHERE f_table_name = 'my_table'
>          AND search_frame = BuildCircleMBR(X, Y, R));
>
>   and wanted to change it to lookup the same reference point,
> POINT(X,Y)  but this time look up which row it was in in a database 
> (my_table) containing one  MultiPolygon per row called 'geom',  how
> would I write the  'BuildMBR' in the SpatialIndex part of the
> query?  
>

Jim,

it's always the same thing: it doesn't matter if the table
supported by the SpatialIndex contains Points or Linestrings
or Polygons, nothing changes.

1. any geometry has its MBR (minimum bounding rectangle) aka BBOX
(to prevent the Points from giving a degenerate rectangle without
dimensions a microscopic epsilon expansion is implicitly applied
on both axes)

2. the R*Tree that is the basis of the SpatialIndex is nothing more
than a hierarchical tree of rectangles (MBR)

3. the SpatialIndex logic queries the R*Tree and very quickly
identifies which MBRs intersect the geometry defined by
"search_frame" (in our case a circle centered on a point
X,Y with a radius R)

The only thing that changes when going from Points to Linestrings
or Polygons is that these geometries can have very bizarre shapes,
so simply evaluating their respective MBRs is often too crude
and potentially misleading.

In any case, the ST_Distance (or the ST_Intersects) then takes
care of refining the evaluation of the real spatial relationship.

In the case of Linestrings and Polygons it might be wise to widen
the search Radius a little, to prevent some geometry that is very
close but does not intersect the Reference Point's MBR from
escaping the search.
do some empirical testing to find the most appropriate calibration.

best regards,
Sandro