<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Generator" CONTENT="MS Exchange Server version 6.5.7652.24">
<TITLE>RE: [postgis-users] Large geometry issue</TITLE>
</HEAD>
<BODY>
<!-- Converted from text/plain format -->
<P><FONT SIZE=2>Paul --<BR>
<BR>
Thanks for the reference and the info ... I was pretty much afraid of that. Given the nature of the test for whether a polygon is within another one entirely, iterating through a few thousand tests will simply take time.<BR>
<BR>
I'll keep an eye on the list and we'll try the JTS stuff when it comes out -- we use JTS in our MiddleWare, but the postGIS side uses GEOS. So it's impossible for us to switch, or (I hope -- no commitment, you understand) pony up some geld.<BR>
<BR>
I'll think about maybe breaking up the sparse multis -- I have some leeway to preprocess data and if I get even a 25% gain things will be a bit easier ... currently numbers show that postGIS is way faster than The Other RDBMS for small polygons, much slower for big ones. Since the immediate testing is directed at a business case in which the large polygons aren't as much of an issue, we're ok for now. But I want to take aim at some internal applications that do use large polygons, eventually.<BR>
<BR>
Greg W.<BR>
<BR>
-----Original Message-----<BR>
From: postgis-users-bounces@postgis.refractions.net on behalf of Paul Ramsey<BR>
Sent: Thu 7/5/2007 9:24 AM<BR>
To: PostGIS Users Discussion<BR>
Subject: Re: [postgis-users] Large geometry issue<BR>
<BR>
The general shape of this problem is<BR>
<BR>
"large complex geometry potentially (based on index filter) contains a<BR>
large number of smaller geometries, figure out which ones are actually<BR>
contained"<BR>
<BR>
<A HREF="http://geotips.blogspot.com/2007/06/performance-and-contains.html">http://geotips.blogspot.com/2007/06/performance-and-contains.html</A><BR>
<BR>
There's no fast way to do this in PostGIS right now. Contains() will be<BR>
maximally fast for the many-points-in-polygon, but still hardly optimal,<BR>
since our naive p-i-p is still O(N).<BR>
<BR>
We are working on speeding this up for a client right now, and the<BR>
delivery will happen relatively soon, but the drawback is that it will<BR>
require using the JTS bindings instead of the GEOS ones, since the<BR>
solution required new JTS work that is not going to be in GEOS for some<BR>
time. The solution will build an internally-indexed version of the big<BR>
complex shape (the individual edges will have index entries) and then<BR>
keep that version around for re-use by each test of the<BR>
small-shape-vs-large-shape combinations.<BR>
<BR>
I would suggest waiting for that release to hit CVS, see if it does what<BR>
you want, then if you are averse to using the JTS bindings buck up for<BR>
the GEOS port.<BR>
<BR>
P.<BR>
<BR>
(It's a shame, but large sparse objects like multi-* don't use the<BR>
over-all feauture-based index well, because the bbox covers the whole<BR>
complex of sub-shapes. If lots of your objects are sparse multis,<BR>
breaking them into simple polygons with a key relationship will help<BR>
things quite a bit, by reducing improper index hits.)<BR>
<BR>
Burgholzer,Robert wrote:<BR>
> Gregory,<BR>
> I have been using within() to do the same, and have found many of the same performance issues. There are a couple of points that I think are useful:<BR>
><BR>
> 1) the "&&" queries are generally fast, especially when using a GIST index, because it is a very effective index - nothing comparable exists (to my knowledge) for distance and within().<BR>
> 2) In my investigations it seems that MULTIPOLYGONS may be the culprit in slowing things down. That is, it is not the complexity of the geometry per se, but rather, the number of isolated geometries within a given shape column, as indicated by the command "select my_id, numGeometries(the_geom) from my_table group by my_id;". I believe that if you are operating on shapes where the "numGeometries" command returns a value of 1, they will perform within() queries very quickly, however, when that number becomes considerably greater than 1, the queries bog down. This occurs often when you have shoreline type geometries that are non-continuous, or geometries that have a number of "holes" in them.<BR>
><BR>
> I think that if you can insure that your geometries are single continuous entities that you can improve performance. I have thought to also investigate the code that underlies the within() command, but have been unsuccessful in understanding the code. Some optimization here would be very worthwhile. If you were to be able to progress in this area, I would be interested in seeing what you can find, and perhaps contributing to the investigation.<BR>
><BR>
> I would be interested to know if anyone who knows more about this topic thinks my conclusions are correct.<BR>
><BR>
> Hope this is at least somewhat helpful,<BR>
> r.b.<BR>
><BR>
> -----Original Message-----<BR>
> From: postgis-users-bounces@postgis.refractions.net [<A HREF="mailto:postgis-users-bounces@postgis.refractions.net">mailto:postgis-users-bounces@postgis.refractions.net</A>] On Behalf Of Gregory Williamson<BR>
> Sent: Thursday, July 05, 2007 8:06 AM<BR>
> To: PostGIS Users Discussion; postgis-users@postgis.refractions.net<BR>
> Subject: RE: [postgis-users] Large geometry issue<BR>
><BR>
> FWIW, this is PostgreSQL 8.2.4, POSTGIS="1.2.1" GEOS="3.0.0rc4-CAPI-1.3.3" USE_STATS<BR>
> on a linux box with 8 gigs o' RAM ...<BR>
> GSW<BR>
><BR>
><BR>
> -----Original Message-----<BR>
> From: postgis-users-bounces@postgis.refractions.net on behalf of Gregory Williamson<BR>
> Sent: Thu 7/5/2007 3:09 AM<BR>
> To: postgis-users@postgis.refractions.net<BR>
> Subject: [postgis-users] Large geometry issue<BR>
><BR>
> Dear peoples,<BR>
><BR>
> I have a problem with a query that uses an absurdly large geometry (2530 in a single polygon). This is srid -1 (part of a large test of postgres vs some other database product). Everything has been vacuumed and analyzed.<BR>
><BR>
> The initial search to find candidates in a target table is quite fast:<BR>
> catest=# select count(*) from wtm_sub_cell w, order_line_item x WHERE x.bbox && w.geometry AND x.id_as_int = 114672;<BR>
> count<BR>
> -------<BR>
> 13168<BR>
> (1 row)<BR>
><BR>
> Time: 9.472 ms<BR>
><BR>
> Trying to get the list narrowed to geometries that are completely contained by the requested shape is slow:<BR>
> catest=# select count(*) from wtm_sub_cell w, order_line_item x WHERE x.bbox && w.geometry AND distance(x.geometry,w.geometry) = 0 and x.id_as_int = 114672;<BR>
> count<BR>
> -------<BR>
> 1112<BR>
> (1 row)<BR>
><BR>
> Time: 69277.780 ms<BR>
><BR>
> So I have two questions:<BR>
> a) anything better to use than "distance(x,y) = 0) ? I tried st_within -- it is about the same speed but returns no polys, which is strange to me, but I also haven't looked at these in detail yet. For example:<BR>
> catest=# select count(*) from wtm_sub_cell w, order_line_item x WHERE x.bbox && w.geometry AND st_within(x.geometry,w.geometry) and x.id_as_int = 114672;<BR>
> count<BR>
> -------<BR>
> 0<BR>
> (1 row)<BR>
><BR>
> Time: 1173.185 ms<BR>
> (same results with st_within(w.geometry,x.geometry):<BR>
> catest=# select count(*) from wtm_sub_cell w, order_line_item x WHERE x.bbox && w.geometry AND st_within(w.geometry,x.geometry) and x.id_as_int = 114672;<BR>
> count<BR>
> -------<BR>
> 0<BR>
> (1 row)<BR>
><BR>
><BR>
> b) anything I can do to speed things up ? I have tried boosting work mem to 16 megs (from 1) and it made no apparent difference.<BR>
><BR>
><BR>
><BR>
> I have a self contained test case that shows the same behavior -- the one large poly and all the candidates in another table. Apologies for the size; hopefully it's not been mangled in the transfers.<BR>
><BR>
> Explain analyze of the sample (the sequential is sensible since there is only one row in the table):<BR>
> catest=# explain analyze select count(*) from wsc_candidates w, oli_req x WHERE w.geometry && x.bbox AND distance(w.geometry,x.oli_req_geom) > 0 AND x.oli_req_id = 114672;<BR>
> QUERY PLAN <BR>
> -------------------------------------------------------------------------------------------------------------------------------------------------------<BR>
> Aggregate (cost=20.28..20.29 rows=1 width=0) (actual time=77232.858..77232.859 rows=1 loops=1)<BR>
> -> Nested Loop (cost=0.00..9.30 rows=4389 width=0) (actual time=6.389..77221.506 rows=12056 loops=1)<BR>
> Join Filter: (distance(w.geometry, x.oli_req_geom) > 0::double precision)<BR>
> -> Seq Scan on oli_req x (cost=0.00..1.01 rows=1 width=40602) (actual time=0.007..0.009 rows=1 loops=1)<BR>
> Filter: (oli_req_id = 114672)<BR>
> -> Index Scan using wsc_c_spatial_ndx on wsc_candidates w (cost=0.00..8.27 rows=1 width=109) (actual time=0.022..25.991 rows=13168 loops=1)<BR>
> Index Cond: (w.geometry && x.bbox)<BR>
> Filter: (w.geometry && x.bbox)<BR>
> Total runtime: 77232.901 ms<BR>
> (9 rows)<BR>
><BR>
> Time: 77233.773 ms<BR>
><BR>
><BR>
> And for the real thing:<BR>
> catest=# explain analyze select count(*) from wtm_sub_cell w, order_line_item x WHERE w.geometry && x.bbox AND distance(w.geometry,x.geometry) = 0 AND x.id_as_int = 114672;<BR>
> QUERY PLAN <BR>
> --------------------------------------------------------------------------------------------------------------------------------------------<BR>
> Aggregate (cost=141.83..141.84 rows=1 width=0) (actual time=77457.587..77457.588 rows=1 loops=1)<BR>
> -> Nested Loop (cost=5.99..141.83 rows=1 width=0) (actual time=15.682..77456.541 rows=1112 loops=1)<BR>
> Join Filter: (distance(w.geometry, x.geometry) = 0::double precision)<BR>
> -> Index Scan using oli_id_ndx on order_line_item x (cost=0.00..8.30 rows=1 width=383) (actual time=0.012..0.018 rows=1 loops=1)<BR>
> Index Cond: (id_as_int = 114672)<BR>
> -> Bitmap Heap Scan on wtm_sub_cell w (cost=5.99..132.97 rows=32 width=109) (actual time=2.988..21.796 rows=13168 loops=1)<BR>
> Filter: (w.geometry && x.bbox)<BR>
> -> Bitmap Index Scan on wsc_geom_idx1 (cost=0.00..5.98 rows=32 width=0) (actual time=2.828..2.828 rows=13168 loops=1)<BR>
> Index Cond: (w.geometry && x.bbox)<BR>
> Total runtime: 77457.633 ms<BR>
> (10 rows)<BR>
><BR>
> Time: 77458.458 ms<BR>
><BR>
><BR>
> The tables involved by size:<BR>
> catest=# select count(*) from wsc_candidates;<BR>
> count<BR>
> -------<BR>
> 13168<BR>
> (1 row)<BR>
><BR>
> Time: 2.586 ms<BR>
> catest=# select count(*) from oli_req;<BR>
> count<BR>
> -------<BR>
> 1<BR>
> (1 row)<BR>
><BR>
> Time: 0.193 ms<BR>
> catest=# select count(*) from wtm_sub_cell;<BR>
> count<BR>
> ---------<BR>
> 6399928<BR>
> (1 row)<BR>
><BR>
> Time: 1776.508 ms<BR>
> catest=# select count(*) from order_line_item;<BR>
> count<BR>
> --------<BR>
> 395921<BR>
> (1 row)<BR>
><BR>
> Time: 176.083 ms<BR>
><BR>
><BR>
> Many thanks for your time and bandwidth!<BR>
><BR>
> Greg Williamson<BR>
> Senior DBA<BR>
> GlobeXplorer LLC, a DigitalGlobe company<BR>
><BR>
> Confidentiality Notice: This e-mail message, including any attachments, is for the sole use of the intended recipient(s) and may contain confidential and privileged information and must be protected in accordance with those provisions. Any unauthorized review, use, disclosure or distribution is prohibited. If you are not the intended recipient, please contact the sender by reply e-mail and destroy all copies of the original message.<BR>
><BR>
> (My corporate masters made me say this.)<BR>
><BR>
> _______________________________________________<BR>
> postgis-users mailing list<BR>
> postgis-users@postgis.refractions.net<BR>
> <A HREF="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</A><BR>
<BR>
<BR>
--<BR>
<BR>
Paul Ramsey<BR>
Refractions Research<BR>
<A HREF="http://www.refractions.net">http://www.refractions.net</A><BR>
pramsey@refractions.net<BR>
Phone: 250-383-3022<BR>
Cell: 250-885-0632<BR>
_______________________________________________<BR>
postgis-users mailing list<BR>
postgis-users@postgis.refractions.net<BR>
<A HREF="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</A><BR>
<BR>
</FONT>
</P>
</BODY>
</HTML>