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

[pramsey]

In 9.2 on my computer the tests show no order dependence,

postgis21=# SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
postgis21-# WHERE ST_Intersects(t1.geom, t2.geom);
 count 
-------
  5131
(1 row)

Time: 6817.429 ms

postgis21=# SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
postgis21-# WHERE ST_Intersects(t2.geom, t1.geom);
 count 
-------
  5131
(1 row)

Time: 6818.568 ms

[pramsey]

Also on 9.1 on my computer, the tests show no order dependence.

pramsey=# SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
          WHERE ST_Intersects(t1.geom, t2.geom);
 count 
-------
  5131
(1 row)

Time: 7639.911 ms
pramsey=# SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
          WHERE ST_Intersects(t2.geom, t1.geom);
 count 
-------
  5131
(1 row)

PostgreSQL 9.1.9, PostGIS 2.0svn

[robe]

On my 2.1.0beta3 install there is a difference but not that noticable

Here is run on my windows 2008 R2 64-bit vm - PostgreSQL 9.2.4, compiled by Visual C++ build 1600, 64-bit POSTGIS="2.1.0beta3dev r11482" GEOS="3.4.0dev-CAPI-1.8.0 r0" PROJ="Rel. 4.8.0, 6 March 2012" GDAL="GDAL 1.10.0, released 2013/04/24" LIBXML="2.7.8" LIBJSON="UNKNOWN" RASTER

-- 6126 ms, 5971 ms, 5921 ms
SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
WHERE ST_Intersects(t1.geom, t2.geom);

-- count: 5131

-- 6040 ms, 5912 ms, 5902 ms
SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
 WHERE ST_Intersects(t2.geom, t1.geom);

-- count: 5131

-- ST_DWithin - 4991 ms, 4971 ms
SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
WHERE ST_DWithin(t1.geom, t2.geom,0);

-- count: 5131

But yah ST_DWithin is noticeably faster

[robe]

I've reopened this because ST_DWithin seems clearly faster than ST_Intersects even after I have put in an index on the geometries. But I suspect it's something we shouldn't try to fix in a micro so pushing to 2.2.0

After adding an index on geom and analyze on table here is what I get:

-- count: 5131
-- times 5753 ms, 5792 ms
SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
WHERE ST_Intersects(t1.geom, t2.geom);


-- count: 5131
-- times 5931 ms, 5962 ms, 6072 ms
SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
 WHERE ST_Intersects(t2.geom, t1.geom);

-- count: 5131
-- times 4181 ms, 4164 ms
SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
WHERE ST_DWithin(t1.geom, t2.geom,0);

I'm even more bothered that the intersects time has gotten worse after putting in the index while ST_DWithin has got much better and now the disparity is even more striking.

Might be something else going on here with 2.1 like something funky with new stats feature.

I'm going to upgrade to latest 2.1 branch to see if issue goes away.

[strk]

hint2: count(gid) to take off the cost of checking all attributes for being null. hint3: play with order by as that seems to be the only difference between the two calls to ST_Intersects, right ? (since the input table contains the same data)

[robe]

Just for good measure did reverse test on ST_Dwithin:

-- count 5131
-- 4151 ms,  4161 ms
SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
WHERE ST_DWithin(t2.geom, t1.geom,0);

-- explain analyze --
Aggregate  (cost=2522.66..2522.67 rows=1 width=0) (actual time=4191.691..4191.692 rows=1 loops=1)
  ->  Nested Loop  (cost=0.00..2522.66 rows=1 width=0) (actual time=0.142..4178.498 rows=5131 loops=1)
        ->  Seq Scan on intersects_order t1  (cost=0.00..565.23 rows=623 width=7166) (actual time=0.015..2.579 rows=623 loops=1)
        ->  Index Scan using idx_i_o_geom on intersects_order t2  (cost=0.00..3.13 rows=1 width=7166) (actual time=0.745..6.631 rows=8 loops=623)
              Index Cond: (geom && st_expand(t1.geom, 0::double precision))
              Filter: ((t1.geom && st_expand(geom, 0::double precision)) AND _st_dwithin(geom, t1.geom, 0::double precision))
              Rows Removed by Filter: 1
Total runtime: 4191.816 ms



--
-- count 5131
-- 6061 ms, 5935 ms, 6021 ms
SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
 WHERE ST_Intersects(t2.geom, t1.geom);

--explain analyze
Aggregate  (cost=2531.78..2531.79 rows=1 width=0) (actual time=6080.601..6080.603 rows=1 loops=1)
  ->  Nested Loop  (cost=0.00..2517.99 rows=5517 width=0) (actual time=11.907..6070.443 rows=5131 loops=1)
        ->  Seq Scan on intersects_order t1  (cost=0.00..565.23 rows=623 width=7166) (actual time=0.015..2.721 rows=623 loops=1)
        ->  Index Scan using idx_i_o_geom on intersects_order t2  (cost=0.00..3.12 rows=1 width=7166) (actual time=6.540..9.670 rows=8 loops=623)
              Index Cond: (geom && t1.geom)
              Filter: _st_intersects(geom, t1.geom)
              Rows Removed by Filter: 1
Total runtime: 6080.893 ms

[robe]

later versions of PostgreSQL have gotten much smarter about count(*) versus say count(t1.gid). I tried switching to just t1.gid and the timings are still the same.

[robe]

It could be maybe just because ST_DWithin doesn't have to do that geos serialization step that its outperforming by saving that step, but then I would expect ST_Intersects to gain by using prepared geometry.

The polygons aren't that big:

SELECT Max(ST_NPoints(geom)), AVG(ST_NPoints(geom))
frOM intersects_order;

Max   Avg
582   416.5136436597110754

[robe]

Huh — I upgraded to latest 2.1 branch and things got worse for ST_Intersects even after I revacuum analyze the table (though not that noticeably worse so could be just the server warming up since I had to restart the service to upgrade). I have to fix the fact that 3.4.0 r is not coming thru on my 64-bit. I suspect geos_revision or something is being clubbered in my geos. This version of geos is still built with my configure. I haven't tried my 9.3 which is built with cmake geos.

POSTGIS="2.1.0rc1dev r11637" GEOS="3.4.0dev-CAPI-1.8.0 r0" PROJ="Rel. 4.8.0, 6 March 2012" GDAL="GDAL 1.10.0, released 2013/04/24" LIBXML="2.7.8" LIBJSON="UNKNOWN" RASTER PostgreSQL 9.2.4, compiled by Visual C++ build 1600, 64-bit

-- count: 5131
-- times 5985 ms, 6008 ms, 5955 ms
SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
WHERE ST_Intersects(t1.geom, t2.geom);


-- count: 5131
-- times 6142 ms, 6112 ms, 6181 ms
SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
 WHERE ST_Intersects(t2.geom, t1.geom);

-- count: 5131
-- times 4234 ms, 4181 ms, 4211 ms
SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
WHERE ST_DWithin(t1.geom, t2.geom,0);

-- count: 5131
-- times 4211 ms, 4222 ms, 4210 ms
SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
WHERE ST_DWithin(t2.geom, t1.geom,0);

[robe]

disregard my comment about indexes. Stupid user error - turns out I was testing with indexed geometries all along because nicklas had indexes on his intersects_order table. The without index as expected is much worse. 21,425ms. So my harp about difference in speed after I added an index is bogus.

We still have the issue that ST_Intersects seems much slower than ST_DWithin with an index for this sample set of data. However if you take the index off the geom, ST_Intersects then defeats ST_DWithin. So it seems ST_Intersects is not benefiting from the index as much as ST_DWithin is perhaps because prepared geometry is not helpful here and ST_DWithin doesn't have the overhead of preparing.

-- without geom index
-- 16392 ms, 16312 ms
SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
WHERE ST_Intersects(t1.geom, t2.geom);

-- 16401 ms, 16392 ms
SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
WHERE ST_Intersects(t2.geom, t1.geom);

-- 18794 ms, 18913 ms
SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
WHERE ST_DWithin(t1.geom, t2.geom,0);

-- 18433 ms, 18494 ms
SELECT COUNT(*) FROM intersects_order t1, intersects_order t2 
WHERE ST_DWithin(t2.geom, t1.geom,0);

[strk]

I believe this ticket is about a speed regression in ST_Intersects since prepared geometries were added. Correct me if I'm wrong. It got so crowded that I'm not sure it's useful in its current incarnation.

[pramsey]

Yes, this ticket is a mess, and I'm closing it out. Please do not re-open, open a new clean one with a clean example and reproduction case. I still see *no* effect in the intersects_order tests. I also see the opposite effect in the point-in-poly tests, st_intersects is much faster, as expected.

perf=# \d points
                          Table "public.points"
 Column |   Type   |                      Modifiers                       
--------+----------+------------------------------------------------------
 geom   | geometry | 
 gid    | integer  | not null default nextval('points_gid_seq'::regclass)
Indexes:
    "points_pkey" PRIMARY KEY, btree (gid)
    "points_gix" gist (geom)

perf=# select p.gid, count(*) from polygons p join points t on st_intersects(p.geom, t.geom) group by p.gid;
 gid | count 
-----+-------
   1 |  4870
   2 |  6393
(2 rows)

Time: 1286.141 ms

perf=# select p.gid, count(*) from polygons p join points t on st_dwithin(p.geom, t.geom, 0) group by p.gid;
 gid | count 
-----+-------
   1 |  4870
   2 |  6393
(2 rows)

Time: 11054.843 ms