Performance issue with ST_Intersects(geometry,geometry)

[nicklas]

When answering  this question I found to my surprise that in this case ST_DWithin was quite a lot faster than ST_Intersects when doing point in polygon test.

ST_DWithin was actually about 3 times faster.

What I think I have found is that in some situations the ST_Intersects function doesn't get the geometries in the expected order. That means that the prepared polygon gets wasted and the preparation needs to be redone next time the same polygon appears.

That is the only explanation I can find from the testing I did, that in those situations the preparation of the polygons gets really expensive.

It seems like a working index on the geometries guarantees the geometries to arrive as wanted. But without the index the &&-operator seems to mess up the order. But I haven't relly seem the pattern how index and && operator affects the order.

[strk]

Doesn't order depend on the planner ? Or are you talking about parameters order ?

[nicklas]

You are right strk, it might be something we cannot control.

But there is some strange things happening here, which I don't really understand.

I will try to add a test case showing the effect.

The question is if can detect if there is no working index and in case of that I think we shouldn't use prepared geometries in those cases.

I will try to make the ticket more complete.

[strk]

When switching to the "global cache" I think I noticed a different strategy within the two different caching strategies (rtree and prepared). One of them only built the cache/prepared after hitting the same polygon twice (never the first time). It should be checked for that policy to be consistent. In other words: check if the slower code path is always building the cache or only after seeing it twice.

[nicklas]

Ok, I don't know enough about those caching mechanisms, but I will try to investigate.

In this case it is the PostGIS internal rtree(?) algorithm for point in polygon tests.

[nicklas]

a two tables dump

[nicklas]

Ok, I have an example showing this issue

In the attached dump there is two tables. One with the two largest polygons from the question in gis.stackexchange linked to above. The two polygons have between 7000 and 9000 vertex-points each.

The other table is a point table with 100000 points spread over the box from ST_Extent of the two polygons.

There is no indexes on the polygons.

So ther is two polygons with gid = 1 and gid = 2.

Running :

SELECT count(*)
FROM polygons  , points 
WHERE ST_Intersects(points.geom , polygons.geom) and polygons.gid in (1);

takes about 1600 ms.

The same with gid=2 takes about the same.

So to run the same with both polygons could be expected to take about 3-4000 ms, But

SELECT count(*)
FROM polygons  , points 
WHERE ST_Intersects(points.geom , polygons.geom) and polygons.gid in (1,2);

uses about 18000 ms.

If I put a gist-index on the points table the issue disappears. Then the single polygon queries takes about 1200 ms each and the query with both polygons uses about 2400ms.

[pramsey]

Interesting, perhaps the "only cache on second occurence" code will reduce this. It's a corner case, IMO, since most times we'll have an index in place to drive this stuff, hopefully.

[nicklas]

"only cache on second occurence" will probably reduce the impact, but then prepared geometries are not used.

I agree that it is a corner case.

But what is important is if it can happen also with indexes.

I have not tried and not looked at the code, but in the polygon-polygon case, do we have the "only cache on second occurence" in place? If not, what decides which of the polygons to be prepared? Can we in that case be sure that the index and the "prepared geometry" code agrees about which of them is in the "inner" and "outer" iteration. If not we might get the same problem also with indexes.

In the polygon-point case I guess that it s always the polygon that searches for points in the index, is that correct, and not vice verse.

[pramsey]

Is the problem still there? Strk committed a patch during the sprint that might have been causing inadvertent cache misses.

[nicklas]

Yes, the trunk of today does still have the same problem.

Sorry for the delay in answer.

[strk]

I can't reproduce with your dump. It takes 6650.959 ms to run with no condition, 3251.666 ms with gid=1 and 3418.510 ms with gid=2.

This is POSTGIS="2.1.0SVN r9902" GEOS="3.4.0dev-CAPI-1.8.0 r3670" on PostgreSQL 8.4.10 on x86_64-pc-linux-gnu, compiled by GCC gcc-4.4.real (Ubuntu 4.4.3-4ubuntu5) 4.4.3, 64-bit

[nicklas]

That was interesting. I still have the issue with the trunk from yesterday.

That could indicate that there is a difference in handling between POstgreSQL 8.4 and PostgreSQL 9.1.3 that I am running. I will install PostgreSQL 8.4 and test.

Now I have used: "POSTGIS="2.1.0SVN r9904" GEOS="3.4.0dev-CAPI-1.8.0 r3673" PROJ="Rel. 4.8.0, 20 February 2012" GDAL="GDAL 1.9.0, released 2011/12/29" LIBXML="2.8.0" LIBJSON="UNKNOWN" RASTER" on: "PostgreSQL 9.1.3 on x86_64-unknown-linux-gnu, compiled by gcc-4.4.real (Debian 4.4.5-8) 4.4.5, 64-bit"

[nicklas]

There seems to be a difference in PostgreSQL 8.4 and 9.1.

With 8.4 I get the same result as Sandro, with everything else unchanged.

So, should we just leave this as unsolvable?

Could anyone say something about the risk that this is happening also with the index in place? I would guess that it not will happen with point against polygon, but maybe with polygons against polygons. Then it could be a risk that PostGIS is preparing the wrong one of the incoming polygons.

I think I have a big polygon data set someone nearby to test.

[strk]

Should be reported on pgsql-hackers (or -bugs).

Can you show the EXPLAIN output on 9.1.3 ?

[nicklas]

EXPLAIN 
SELECT count(*)
FROM polygons  , points 
WHERE ST_Intersects(points.geom , polygons.geom);

9.1:

Aggregate  (cost=54835.03..54835.04 rows=1 width=0)
   ->  Nested Loop  (cost=0.00..54835.03 rows=1 width=0)
         Join Filter: ((points.geom && polygons.geom) AND _st_intersects(points.geom, polygons.geom))
         ->  Seq Scan on points  (cost=0.00..1834.00 rows=100000 width=128)
         ->  Materialize  (cost=0.00..1.03 rows=2 width=32)
               ->  Seq Scan on polygons  (cost=0.00..1.02 rows=2 width=32)
(6 rows)

8.4:

 Aggregate  (cost=56169.02..56169.03 rows=1 width=0)
   ->  Nested Loop  (cost=0.00..56169.02 rows=1 width=0)
         Join Filter: ((points.geom && polygons.geom) AND _st_intersects(points.geom, polygons.geom))
         ->  Seq Scan on polygons  (cost=0.00..1.02 rows=2 width=32)
         ->  Seq Scan on points  (cost=0.00..1834.00 rows=100000 width=128)
(5 rows)

As I understand it in 8.4 the sequantal scan takes one polygon at a time and iterate all points. But in 9.1 it takes one point at a time iterating all polygons which makes preparing the polygon just slowing things down.

But from PostgreSQL perspective there is no right and wrong I guess? Or can we manipulate this behavior?

Is this something like the same issue that causes us to expand both first and second geoemetry in the sql-definition of ST_DWithin. If I remember right Regina said something like that.

[strk]

We could surely use second geometry but our second geometry will only be the same polygon every count(polygons) calls...

I don't know how the planner picks which scan to perform first. Try with the same number of records for each table ?

[nicklas]

This is getting worse. From PostGIS perspective we have a quite serious regression from 8.4 to 9.1.

In the dumpfile called intersects_order.dump is a table with polygons. It is the data set that Sandro used in #1841

Here I am using a gist index so this is not a corner case but the real thing.

In 8.4 those two queries takes about 2400 ms each:

SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
WHERE ST_Intersects(t1.geom, t2.geom);

SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
WHERE ST_Intersects(t2.geom, t1.geom);

(notice the changed order in ST_Intersects)

In 9.1 the first query uses about 5500 ms and the second uses about 9800 ms.

So there must be at least two things going on here. 9.1 gets affected by the order, 8.4 don't in this case. And even the fast order in 9.1 takes twice as long time as 8.3.

I have put the explain results in the file intersects_order.sql. What is interesting there is that the plan is identical no matter of the order in ST_Intersects (compared to the case discussed above without index when the plan changes with different order), but is quite different in 8.4 and 9.1.

All this have to do with the caching and preparing mechanisms I guess, but I cannot figure out what is happening.

From my understanding there is three possible scenaros in PostGIS

1) nothing gets cached or prepared at all because the "only on second appearance"-rule 2) wrong geometry gets prepared so we just get the job of preparing and no gain 3) the right geometry gets prepared and cached, we all get happy

But what is happening above in 8.4, 9.1 with "right order" and 9.1 with "wrong order"?

[nicklas]

explain results

[strk]

doesn't sound something that will be fixed in 2.0.1 -- not even sure we can call this a bug. if you want to debug caches being used you can enable debugging in postgis_config.h

[robe]

pramsey is this issue affected by any of the changes you are doing to selectivity or should we punt this one?

[robe]

move back if you feel this is easily solvable