Executing st_within queries on subsets of a DB

[Stefano Polloni]

Hi there,

first-off I'd like to kindly thank Marc and Sandro for helping me getting more familiar with some basics of SQL and Spatialite yesterday. As I slowly build the foundations and walls of my house (referring to Sandro's analogy in my previous post), I have come across a specific example which I find puzzling, and I think it would be very pedagogical for me to figure out. I was hoping to get some help on this. My DB contains 3 tables:

1. a 'transactions' table with information on real-estate transactions, including the province in which they occur (~1.5M rows).
   
2. a 'plot' table with info on land plots, including their location which is a POINT geography column with Spatial Index (~4.5M rows).
   
3. a 'zones' table containing small disjoint polygons (also spatially indexed), and the province in which they lie (~1.2K rows/polygons).

All transactions describe the sale of a property, and each property lies on a land plot contained in my 'plot' table. I would like to obtain all transactions occurring inside the zones (polygons) for a specific province. I can run a query just fine for the entire DB, but subsetting on a province makes the query impossibly long if I invoke the spatial index.

A bit more details:

the following query successfully retrieves all transactions occurring inside the polygons for ALL provinces:

SELECT p.GEOMETRY, t.transaction_id
FROM plots AS p, zones AS z
JOIN transactions AS t ON p.property_id = t.property_id
WHERE p.ROWID IN (SELECT ROWID FROM SpatialIndex
        WHERE f_table_name='plots' AND search_frame=z.GEOMETRY)
AND st_within(p.GEOMETRY,z.GEOMETRY)

This takes ~60 seconds which I think is really reasonable given the size of my DB and that i'm executing the query on a not-too-recent macbook. Now things get tricky when I try to execute the same query but when retaining only the rows in a given province:

SELECT p.GEOMETRY, t.transaction_id
FROM plots AS p, zones AS z
JOIN transactions AS t ON p.property_id = t.property_id
WHERE p.ROWID IN (SELECT ROWID FROM SpatialIndex
        WHERE f_table_name='plots' AND search_frame=z.GEOMETRY)
AND st_within(p.GEOMETRY,z.GEOMETRY)
AND t.prov_code = 3

The above takes >500 seconds and I'm struggling to grasp why. Finally, I manage to get reasonable performance (30 seconds) with:

SELECT A.GEOMETRY, A.transaction_id
FROM ( SELECT p.GEOMETRY, t.transaction_id
       FROM plots AS p
       JOIN transactions AS t ON p.property_id = t.property_id
       WHERE t.prov_code = 3) AS A,
     ( SELECT * FROM zones
       WHERE prov_code = 3) AS B
WHERE st_within(A.GEOMETRY,B.GEOMETRY)

but as you notice this does not utilize the SpatialIndex at all. In fact province #3 is a small province and the same query will take much much longer for larger provinces. How can I both invoke the SpatialIndex and pick a province within one single efficient query?

Please note that the variables p.property_id, t.property_id, t.prov_code and z.prov_code all have regular SQL indices.

Many Thanks! 

Stefano

 

[mj10777]

It may be useful to read through the following sqlite3 pages:

1) https://sqlite.org/lang_explain.html

2) https://sqlite.org/eqp.html

3) https://sqlite.org/opcode.html

When adding 'EXPLAIN' (1) or 'EXPLAIN QUERY PLAN' (2) before the SELECT command, sqlite3 will list

- the instructions it would execute for this query

-- the second field shown in the results is 'opcode', which are explained in the 3rd link

On a developer machine only, it would wise to recompile sqlite3 with '-DSQLITE_ENABLE_EXPLAIN_COMMENTS'

./configure CFLAGS="-DSQLITE_ENABLE_EXPLAIN_COMMENTS"
sudo make install

then the last field 'comment' will show the values being used, which helps to make the 'gibberish' more understandable

- you will see the values being used

(Note for Sandro: spatialite_gui does not highlight 'EXPLAIN' and 'EXPLAIN QUERY PLAN' as keywords)

On Friday, 27 October 2017 01:55:27 UTC+2, Stefano Polloni wrote:

Hi there,

first-off I'd like to kindly thank Marc and Sandro for helping me getting more familiar with some basics of SQL and Spatialite yesterday. As I slowly build the foundations and walls of my house (referring to Sandro's analogy in my previous post), I have come across a specific example which I find puzzling, and I think it would be very pedagogical for me to figure out. I was hoping to get some help on this. My DB contains 3 tables:

1. a 'transactions' table with information on real-estate transactions, including the province in which they occur (~1.5M rows).
   
2. a 'plot' table with info on land plots, including their location which is a POINT geography column with Spatial Index (~4.5M rows).
   
3. a 'zones' table containing small disjoint polygons (also spatially indexed), and the province in which they lie (~1.2K rows/polygons).

All transactions describe the sale of a property, and each property lies on a land plot contained in my 'plot' table. I would like to obtain all transactions occurring inside the zones (polygons) for a specific province. I can run a query just fine for the entire DB, but subsetting on a province makes the query impossibly long if I invoke the spatial index.

A bit more details:

the following query successfully retrieves all transactions occurring inside the polygons for ALL provinces:

SELECT p.GEOMETRY, t.transaction_id
FROM plots AS p, zones AS z
JOIN transactions AS t ON p.property_id = t.property_id
WHERE p.ROWID IN (SELECT ROWID FROM SpatialIndex
        WHERE f_table_name='plots' AND search_frame=z.GEOMETRY)
AND st_within(p.GEOMETRY,z.GEOMETRY)

This takes ~60 seconds which I think is really reasonable given the size of my DB and that i'm executing the query on a not-too-recent macbook. Now things get tricky when I try to execute the same query but when retaining only the rows in a given province:

SELECT p.GEOMETRY, t.transaction_id
FROM plots AS p, zones AS z
JOIN transactions AS t ON p.property_id = t.property_id
WHERE p.ROWID IN (SELECT ROWID FROM SpatialIndex
        WHERE f_table_name='plots' AND search_frame=z.GEOMETRY)
AND st_within(p.GEOMETRY,z.GEOMETRY)
AND t.prov_code = 3

The above takes >500 seconds and I'm struggling to grasp why.

what is the time result if 't.prov_code = 3' is placed before the SpatialIndex portion of WHERE

- thus filtering out all the other provinces before the SpatialIndex and ST_WITHIN portions?

Mark

[Jukka Rahkonen]

Hi

Read
https://groups.google.com/forum/#!topic/spatialite-users/u8uo6IWg-vE

and try with the unary "+"

SELECT p.GEOMETRY, t.transaction_id
FROM plots AS p, zones AS z
JOIN transactions AS t ON p.property_id = t.property_id
WHERE p.ROWID IN (SELECT ROWID FROM SpatialIndex
WHERE f_table_name='plots' AND search_frame=z.GEOMETRY)
AND st_within(p.GEOMETRY,z.GEOMETRY)

AND +t.prov_code = 3;

It could also be worth trying CROSS JOIN as in
https://www.mail-archive.com/sqlite...@mailinglists.sqlite.org/msg103804.html.
Even Rouault also suggests in
http://erouault.blogspot.fi/2017/03/dealing-with-huge-vector-geopackage.html
that reading rtree with JOIN is better than with the subquery "WHERE
p.ROWID in ...).

-Jukka Rahkonen-

Stefano Polloni kirjoitti 2017-10-27 02:55:
> Hi there,
>
> first-off I'd like to kindly thank Marc and Sandro for helping me
> getting more familiar with some basics of SQL and Spatialite
> yesterday. As I slowly build the foundations and walls of my house
> (referring to Sandro's analogy in my previous post), I have come
> across a specific example which I find puzzling, and I think it would
> be very pedagogical for me to figure out. I was hoping to get some
> help on this. My DB contains 3 tables:
>

> * a 'transactions' table with information on real-estate

> transactions, including the province in which they occur (~1.5M rows).
>

> * a 'plot' table with info on land plots, including their location

> which is a POINT geography column with Spatial Index (~4.5M rows).

> * a 'zones' table containing small disjoint polygons (also spatially

> indexed), and the province in which they lie (~1.2K rows/polygons).
>
> All transactions describe the sale of a property, and each property
> lies on a land plot contained in my 'plot' table. I would like to
> obtain all transactions occurring inside the zones (polygons) for a
> specific province. I can run a query just fine for the entire DB, but
> subsetting on a province makes the query impossibly long if I invoke
> the spatial index.
>

> A BIT MORE DETAILS:

> --
> You received this message because you are subscribed to the Google
> Groups "SpatiaLite Users" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to spatialite-use...@googlegroups.com.
> To post to this group, send email to
> spatiali...@googlegroups.com.
> Visit this group at https://groups.google.com/group/spatialite-users.
> For more options, visit https://groups.google.com/d/optout.

[mj10777]

On Friday, 27 October 2017 01:55:27 UTC+2, Stefano Polloni wrote:

Hi there,

first-off I'd like to kindly thank Marc and Sandro for helping me getting more familiar with some basics of SQL and Spatialite yesterday. As I slowly build the foundations and walls of my house (referring to Sandro's analogy in my previous post), I have come across a specific example which I find puzzling, and I think it would be very pedagogical for me to figure out. I was hoping to get some help on this. My DB contains 3 tables:

1. a 'transactions' table with information on real-estate transactions, including the province in which they occur (~1.5M rows).
   
2. a 'plot' table with info on land plots, including their location which is a POINT geography column with Spatial Index (~4.5M rows).
   
3. a 'zones' table containing small disjoint polygons (also spatially indexed), and the province in which they lie (~1.2K rows/polygons).

All transactions describe the sale of a property, and each property lies on a land plot contained in my 'plot' table. I would like to obtain all transactions occurring inside the zones (polygons) for a specific province. I can run a query just fine for the entire DB, but subsetting on a province makes the query impossibly long if I invoke the spatial index.

A bit more details:

the following query successfully retrieves all transactions occurring inside the polygons for ALL provinces:

SELECT p.GEOMETRY, t.transaction_id
FROM plots AS p, zones AS z
JOIN transactions AS t ON p.property_id = t.property_id
WHERE p.ROWID IN (SELECT ROWID FROM SpatialIndex
        WHERE f_table_name='plots' AND search_frame=z.GEOMETRY)
AND st_within(p.GEOMETRY,z.GEOMETRY)

This takes ~60 seconds which I think is really reasonable given the size of my DB and that i'm executing the query on a not-too-recent macbook. Now things get tricky when I try to execute the same query but when retaining only the rows in a given province:

SELECT p.GEOMETRY, t.transaction_id
FROM plots AS p, zones AS z
JOIN transactions AS t ON p.property_id = t.property_id
WHERE p.ROWID IN (SELECT ROWID FROM SpatialIndex
        WHERE f_table_name='plots' AND search_frame=z.GEOMETRY)
AND st_within(p.GEOMETRY,z.GEOMETRY)
AND t.prov_code = 3

The above takes >500 seconds and I'm struggling to grasp why. Finally, I manage to get reasonable performance (30 seconds) with:

Here I think you will get the same timing result for the above query if you move t.prov_code = 3  to the first condition of WHERE.

I have experimented with the EXPLAIN function based on the query of yesterday, adding

((point_z=33.620000) AND (point_z>2.77 ))

- once before and once after the SpatialIndex query

The results of both EXPLAIN results were placed in 2 text files and using the diff command:

diff explain.before.txt explain.after.txt

shows this:

'<' =before

'>'=after

21,29c21,29

< 20 Column 0 3 9 0 00 r[9]=berlin_dhhn92_2007.point_z

< 21 RealAffinity 9 0 0 00

< 22 Ne 10 33 9 (BINARY) 55 if r[9]!=r[10] goto 33

< 23 Le 12 33 9 (BINARY) 55 if r[9]<=r[12] goto 33

< 24 Column 0 4 13 NULL 00 r[13]=berlin_dhhn92_2007.utm_point

< 25 Function0 2 13 11 ST_ClosestPoint(2) 02 r[11]=func(r[13..14])

< 26 IsNull 11 33 0 00 if r[11]==NULL goto 33

< 27 Column 0 4 11 NULL 00 r[11]=berlin_dhhn92_2007.utm_point

< 28 Function0 0 11 16 ST_Z(1) 01 r[16]=func(r[11])

---

> 20 Column 0 4 10 NULL 00 r[10]=berlin_dhhn92_2007.utm_point

> 21 Function0 2 10 9 ST_ClosestPoint(2) 02 r[9]=func(r[10..11])

> 22 IsNull 9 33 0 00 if r[9]==NULL goto 33

> 23 Column 0 3 9 0 00 r[9]=berlin_dhhn92_2007.point_z

> 24 RealAffinity 9 0 0 00

> 25 Ne 12 33 9 (BINARY) 55 if r[9]!=r[12] goto 33

> 26 Le 14 33 9 (BINARY) 55 if r[9]<=r[14] goto 33

> 27 Column 0 4 13 NULL 00 r[13]=berlin_dhhn92_2007.utm_point

> 28 Function0 0 13 16 ST_Z(1) 01 r[16]=func(r[13])

51,58c51,58

< 50 Real 0 10 0 33.62 00 r[10]=33.62

< 51 Real 0 12 0 2.77 00 r[12]=2.77

< 52 Real 0 30 0 24700.552 00 r[30]=24700.552

< 53 Real 0 31 0 20674.744 00 r[31]=20674.744

< 54 Integer 3068 32 0 00 r[32]=3068

< 55 Function0 7 30 28 MakePoint(3) 03 r[28]=func(r[30..32])

< 56 Integer 25833 29 0 00 r[29]=25833

< 57 Function0 3 28 14 ST_Transform(2) 02 r[14]=func(r[28..29])

---

> 50 Real 0 30 0 24700.552 00 r[30]=24700.552

> 51 Real 0 31 0 20674.744 00 r[31]=20674.744

> 52 Integer 3068 32 0 00 r[32]=3068

> 53 Function0 7 30 28 MakePoint(3) 03 r[28]=func(r[30..32])

> 54 Integer 25833 29 0 00 r[29]=25833

> 55 Function0 3 28 11 ST_Transform(2) 02 r[11]=func(r[28..29])

> 56 Real 0 12 0 33.62 00 r[12]=33.62

> 57 Real 0 14 0 2.77 00 r[14]=2.77

Sqlite3 will attempt (I believe with 'prepare') to optimize a query.

But there are certain 'logical' conditions that cannot be 'guessed' beforehand

- which of the 2 WHERE conditions excludes the most results and use that first

-- on such conditions it will assume you know what you are doing and leave as it is

Conclusion: 

Inside the WHERE statement

- first exclude everything where it is clear that it is not needed

--> in your case: all provinces != 3

- then the other conditions that will be performed on all provinces == 3

Mark

[mj10777]

On Friday, 27 October 2017 08:49:29 UTC+2, Jukka Rahkonen wrote:

Hi

Read
https://groups.google.com/forum/#!topic/spatialite-users/u8uo6IWg-vE

and try with the unary "+"

This will not help, since EXPLAIN shows that this is none after the SpatilIndex condition.

Goal is not to perform WHERE conditions on records, where it clear from the beginning, that they are not needed.

The EXPLAIN text shows (with 'if r[9]!=r[12] goto 33') that it will skip the next WHERE conditions and preside to the next record.

Mark

SELECT p.GEOMETRY, t.transaction_id
FROM plots AS p, zones AS z
JOIN transactions AS t ON p.property_id = t.property_id
WHERE p.ROWID IN (SELECT ROWID FROM SpatialIndex
         WHERE f_table_name='plots' AND search_frame=z.GEOMETRY)
AND st_within(p.GEOMETRY,z.GEOMETRY)
AND +t.prov_code = 3;

It could also be worth trying CROSS JOIN as in

https://www.mail-archive.com/sqlite-users@mailinglists.sqlite.org/msg103804.html.

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

On Thu, 26 Oct 2017 16:55:26 -0700 (PDT), Stefano Polloni wrote:
> SELECT p.GEOMETRY, t.transaction_id
> FROM plots AS p, zones AS z
> JOIN transactions AS t ON p.property_id = t.property_id
> WHERE p.ROWID IN (SELECT ROWID FROM SpatialIndex
>         WHERE f_table_name='plots' AND search_frame=z.GEOMETRY)
> AND st_within(p.GEOMETRY,z.GEOMETRY)
> AND t.prov_code = 3
>
> The above takes >500 seconds and I'm struggling to grasp why.
>

Hi Stefano,

there is a specific key-point in the Spatial Index (aka Virtual
RTree) implementation worth to be explained in more detail.

1. an R*Tree Spatial Index isn't really an Index; it's just
an independent Virtual Table, and the main core of SQLite
is completely unaware that a logical relations exists between
the main table being indexed and the companion R*Tree table.
2. this explains why you necessarily have to explicitly query
the R*Tree Spatial Index in your SQL query (usually by
defining an Inner SubQuery).

This specific architecture could easily lead to unexpected
results when the Query Planner/Optimizer compiles your SQL
query into a sequence of pseudo-code operations (SQLite is
internally implemented as kind-of an interpreted language
based on its own pseudo-codes).

As a general design principle, when a WHERE clauses defines
more than a single condition the Query Planner/Optimizer
will always attempt to choose the (apparently) most efficient
data access strategy.
This usually means that any comparison supported by an
appropriate Index will always assume an higher priority;
but an R*Tree Spatial Index isn't an Index, it really is
a Virtual Table, and consequently the Planner/Optimizer
will easily assign a very negligible priority to any
comparison based on a Spatial Index.
The net result will be that any WHERE clause defining
both a Spatial Index sub-query and other "ordinary"
comparisons will end up in "shadowing" the Spatial
Index, and will then probably be executed in a very
inefficient way (i.e. it will not really take any
profit from the supporting Spatial Index).

Possible solutions and workarounds:

A. in case of doubt always check EXPLAIN (as suggested
by Mark).
B. try using the "Unary +" syntax so opportunely instruct
the Planner/Optimizer to _NOT_ use some Indexes (as
suggested by Jukka).
NOTE: this method has its hidden pitfalls, please read:

http://sqlite.1065341.n5.nabble.com/Unary-isn-t-disabling-use-of-index-td95582.html
C. split your query in two distinct steps:
- first check the Spatial Index alone, and store this
preliminary resultset into a Temporary Table.
- and finally query the above Temporary Table so to
check any other comparison based on "ordinary"
(non-Geometry) data.

bye Sandro

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

On Fri, 27 Oct 2017 10:16:20 +0200, a.fu...@lqt.it wrote:
> C. split your query in two distinct steps:
> - first check the Spatial Index alone, and store this
> preliminary resultset into a Temporary Table.
> - and finally query the above Temporary Table so to
> check any other comparison based on "ordinary"
> (non-Geometry) data.
>

Addendum: avoiding to execute overly complex SQL queries
and splitting them into several simpler queries extensively
using Temporary Tables for storing partial resultsets
usually is a very powerful technique leading to spectacular
optimizations (literally: from deadly slow to speed of light).

Rationale: simple queries are easily predictable, so the
Query Planner will precisely understand your intentions
then choosing an highly optimized data access strategy.
Complex queries could be more easily misunderstood, and
the Query Planner could then choose a very inefficient
and penalizing data access strategy.

bye Sandro

[Stefano Polloni]

I am once again impressed by the quick and helpful responses I am receiving in this group -- thank you all. Using EXPLAIN QUERY PLAN as proposed by Mark, I confirm that adding AND t.prov_code = 3 significantly alters the data access strategy:

without subsetting: 

0|0|1|SCAN TABLE zones AS z
0|1|0|SEARCH TABLE plots AS p USING INTEGER PRIMARY KEY (rowid=?)
0|0|0|EXECUTE CORRELATED LIST SUBQUERY 1
1|0|0|SCAN TABLE SpatialIndex VIRTUAL TABLE INDEX 2:
0|2|2|SEARCH TABLE transactions AS t USING AUTOMATIC COVERING INDEX (property_id=?)

with subsetting (t.prov_code = 3)

0|0|2|SEARCH TABLE transactions AS t USING INDEX prov_ind (prov_code=?)
0|1|0|SEARCH TABLE plots AS p USING INDEX property_ind_plot (property_id=?)
0|2|1|SCAN TABLE zones AS z
0|0|0|EXECUTE CORRELATED LIST SUBQUERY 1
1|0|0|SCAN TABLE SpatialIndex VIRTUAL TABLE INDEX 2:

I believe this is exactly what Sandro mentions about assigning very negligible priority to any conditions based on a SpatialIndex, since t.prov_code here is a regular SQLite index in the DB. I am now clear on why this query takes so much time.

Moving forward, I have tried both (1) placing the 't.prov_code = 3' condition before the spatial portion of the query and (2) using the "Unary +" syntax. (1) yields the exact same query plan as above and hence its performance remains poor (>500 seconds). When doing (2), i.e. 'AND +t.prov_code = 3', the query plan revokes to the initial plan (without subsetting), but curiously the query returns empty after about a minute of processing. I'm not sure why that is....

Finally, I have tried Sandro's recommendation of splitting my query into simpler ones. The 3 queries I use sequentially are:

first, 

CREATE TEMPORARY TABLE trans_3 AS
SELECT p.GEOMETRY, t.trans_id
FROM plots AS p
JOIN transactions AS t on p.property_id = t.property_id
WHERE t.prov_code = 3;

then,

CREATE TEMPORARY TABLE zone_3 AS
SELECT * FROM zones
WHERE prov_code = 3;

and last:

SELECT t.GEOMETRY, t.trans_id
FROM trans_3 AS t, zone_3 AS z
WHERE t.ROWID IN (
   SELECT ROWID
   FROM SpatialIndex
   WHERE f_table_name='trans_3'
   AND search_frame=z.GEOMETRY)
AND st_within(t.GEOMETRY,z.GEOMETRY);

This is indeed near light-speed fast, but the query returned is again empty, just like when using the unary +. I'm confused why this would be the case, and I am 100% sure that there are transactions occurring on plots that live inside the zones  in province 3.

[Stefano Polloni]

Addendum:

In the sequential approach, replacing the third query by the following:

SELECT t.GEOMETRY, t.trans_id
FROM trans_3 AS t,

zone_3 AS z
WHERE st_within(t.GEOMETRY,z.GEOMETRY);

will return the expected rows, although the query is sloooow for large provinces.

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

Hi Stefano,

there is an obvious mistake in your queries:

1. "trans_3" is created as a temporary table
CREATE TEMPORARY TABLE trans_3 AS ....

2. then you attempt to execute an inner subquery on the Spatial
Index supporting "trans_3":
... FROM SpatialIndex WHERE f_table_name='trans_3'

3. but no such Spatial Index do really exists.

Note: querying the SpatialIndex obviously requires that the
table identified by "WHERE f_table_name = 'xxxx'" really
matches a companion Spatial Index.
if not, any sub-query targeting a non-existing Spatial
Index will simply return a NULL, thus inexorably leading
to an empty resultset.

Spatial Indices are never created "auto-magically"; you
absolutely need to explicitly call CreateSpatialIndex()
in order to effectively create an R*Tree supporting a
Spatial Table.

Note #2: temporary tables can _NEVER_ support a Spatial
Index; only Spatial Tables properly registered into the
metadata tables via AddGeometryColumn() or
RecoverGeometryColumn() can do.

short conclusion; you simply have to rewrite in a better
form the first and the last of your three queries, as e.g.:

CREATE TEMPORARY TABLE trans_3 AS

SELECT p.ROWID AS prowid, p.GEOMETRY, t.trans_id

FROM plots AS p
JOIN transactions AS t on p.property_id = t.property_id
WHERE t.prov_code = 3;

(you must carefully preserve into the temp-table a reference
to the the original ROWID-values coming from "plots")

SELECT t.GEOMETRY, t.trans_id
FROM trans_3 AS t, zone_3 AS z

WHERE t.prowid IN (
SELECT ROWID
FROM SpatialIndex
WHERE f_table_name='plots'
AND search_frame=z.GEOMETRY)
AND st_within(t.GEOMETRY,z.GEOMETRY);

(now you can safely continue to query the Spatial Index
supporting "plots" because the returned ROWIDs will
precisely match "t.prowid")

Bye Sandro

[Stefano Polloni]

Sandro, 

Grazie mille. I suspected that spatial indices were not "auto-magically" created, but when trying to create one after the first query, the CreateSpatialIndex() error reported that 'either "trans_3"."GEOMETRY" isn't a Geometry column or a SpatialIndex is already defined'. I assumed that the latter was true, but now I understand that temporary tables simply don't support spatial indices. 

Thanks for fixing my queries! Perhaps interestingly, invoking the spatial index seems to not improve performance in this case. 

Best,

Stefano