[postgis-devel] Postgis topology creation - O(n-squared)? - creates problems with large datasets.

Sandro Santilli strk at keybit.net
Mon Jan 13 14:00:21 PST 2014


On Mon, Jan 13, 2014 at 10:14:43PM +0100, Sandro Santilli wrote:
> On Mon, Jan 13, 2014 at 10:11:48PM +0100, Sandro Santilli wrote:
> 
> > These are the function that are run for insertion of a _single_ polygon when
> > the topology already contains 165000 faces.
> > 
> > -- Ordered by "self_time":
> > strk=# select * from pg_stat_user_functions order by self_time desc;
> > 
> >  funcid | schemaname |        funcname         | calls  | total_time | self_time
> > --------+------------+-------------------------+--------+------------+-----------
> >   62973 | topology   | _st_addfacesplit        |      2 |    424.356 |    192.07
> >   52356 | public     | st_lineinterpolatepoint | 165013 |    136.911 |   136.911
> >   52097 | public     | geometry_overlaps       | 165015 |     92.684 |    92.684
> >   54503 | topology   | st_addedgemodface       |      1 |    438.418 |    13.539
> >   54508 | topology   | st_addisonode           |      1 |       7.39 |     7.359
> >   54491 | topology   | getringedges            |      2 |      2.552 |     2.552
> >   54533 | topology   | topogeo_addlinestring   |      1 |    450.942 |     2.385
> >   54534 | topology   | topogeo_addpoint        |      2 |      9.287 |     1.837
> > 
> > Interesting enough, "geometry_overlaps" and "st_lineinterpolatepoint" are called
> > once for each and every already-loaded geometry, which suggests there's indeed a
> > problem with index usage. The "geometry_overlaps" function is the one that
> > implements operator&&, supposedly an index user!
> 
> Another interesting information is that the _second_time_ you pass the same
> input to TopoGeo_addPolygon, "geometry_overlaps" gets called 9 times only,
> which is more like the expected number out of an index filter...

I've found the culprit!
It's a query in topology._ST_AddFaceSplit that fails to make use of the index
by checking for overlap between a literal and a function over the indexed
geometry, in this form:

 WHERE ST_Contains('...'::geometry, ST_LineInterpolatePoint(geom, 0.2));

For the index to be effective the query should first check overlap with whole
geometry and then containment.

Ticketed here: http://trac.osgeo.org/postgis/ticket/2610

--strk;

 ()  ASCII ribbon campaign        - against html e-mail
 /\  http://www.asciiribbon.org   - against proprietary attachments



More information about the postgis-devel mailing list