5

Update 2 (below) suggests 14% of the table geometries are stored out-of-line with the rest of the table records. This may be a useful clue.

The Problem:

We've got a table with appx 170,000 WGS84 polygons, a GIST geometry index, and we're wanting to get a selection set ordered by descending feature area values. Since this data was "born" in ArcSDE, it has a shape_area field.

Querying with ORDER BY shape_area DESC and LIMIT 2000 predicates, the intersection--using &&--took appx 25000 milliseconds (25 sec) to finish.

So ..perhaps Clustering by descending polygon area?

Looking for more speed, I tried clustering the table by a shape_area index like this:

CREATE INDEX shape_area_idx 
  ON layer_wgs84 
  USING btree 
  (shape_area DESC NULLS LAST)
  WITH (FILLFACTOR=100) ;

ALTER TABLE layer_wgs84 CLUSTER ON shape_area_idx ;

cluster layer_wgs84 ;

-- then I dropped and recreated the geometry index

VACUUM ANALYZE layer_wgs84 ;

Afterward I could run the intersection without the expensive ORDER BY clause, but it still took over 3000 ms (3 sec) to complete.

..FWIW I've also tried using a WITH Query (a.k.a. Common Table Expression), to ensure the BBox intersection is processed first. But this doesn't really help at low zoom if the BBox covers the whole 170,000-feature table. Even with the LIMIT, it still takes 3-4 seconds.

I'd like to get this down to about 500 ms.

[ACTUAL QUESTION]

Strategically, is there a better approach I may not be aware of to perform a spatial intersection ordered by their shape area descending?

[UPDATE 1]

When I omit the geometry from the query, it becomes stupid-fast. 50ms! So I'm thinking my query is as good as it's going to get, and the bottle-neck must be the instance hitting disk to fetch the geometry objects.

[UPDATE 2]

Because pulling the geometries was killing the return speed, I started wondering if the geometry objects were stored inline or out-of-line with the rest of the record fields, and consequently, whether I might consider storing all the geometries in a different field as VARCHAR(N) or TEXT in an effort to force them inline and avoid any expensive disk hits. Googling that question led me to this SO thread (how to check the storage mode for each table column) and the docs page discussing TOAST(The Oversized-Attribute Storage Technique).

So I checked this table (on my dev system) and the geometry column is setup for "MAIN", which means:

MAIN allows compression but not out-of-line storage. (Actually, out-of-line storage will still be performed for such columns, but only as a last resort when there is no other way to make the row small enough to fit on a page.)

And this passage suggests the implication for geometry values under default conditions:

The TOAST code is triggered only when a row value to be stored in a table is wider than TOAST_TUPLE_THRESHOLD bytes (normally 2 kB). The TOAST code will compress and/or move field values out-of-line until the row value is shorter than TOAST_TUPLE_TARGET bytes (also normally 2 kB) or no more gains can be had.

Sooooooo then I wondered.. What percent of our table is stored out-of-line??

ANSWER: appx 14% (Including a military base parcel that probably gets pulled by a shocking number of queries.) For the curious, here's I polled the DB to learn this..

with 
  total as (
    select count(*) from parcels_cama_wgs84 as count),
  out_of_line as (
    select count(*) from parcels_cama_wgs84 as count 
    where ST_mem_size(the_geom)*0.001 > 2)

select 
  total.count, 
  out_of_line.count, 
  (out_of_line.count::DECIMAL/total.count::DECIMAL)::DECIMAL as perc 
from total, out_of_line;

| total  | outofline | percent     
| 164861 | 23193     | 0.14068

Which led me to ask.. What if I modify the query to return ONLY the UNtoasted geometries??

To do this I modified the WHERE clause of my inner select (see query below) to include this..

AND ST_mem_size(the_geom)*0.001 < 2 -- only geoms less than 2kb

After that my test-case query went from 1400 ms to 850 ms..

However. While this is an interesting discovery it doesn't lend any solution, plus it's not an option for us to omit all > 2kb polygons from these layer queries. So while this does tell me something, I'm still looking for the Aha!-moment..

I can force the geometries inline by changing the column storage mode to PLAIN, which I'll try and remark on..


[Obligatory Query and Explain Plan | tl;dr;]

This is my current query and its explain plan. However I want to stress I'm really just asking if there is an alternative approach/tactic I should be considering.

SELECT 
  l.gid, 
  st_astext(l.the_geom) AS geom,
  l.tms AS tms, 
  l.shape_area_int
FROM ( 
  SELECT * FROM  
    parcels_cama_wgs84  
  WHERE 
    the_geom && ST_Envelope(ST_GeogFromText('SRID=4326;POLYGON((-81.08030319213867 34.060588119230346, -81.08030319213867 34.09318398156763, -81.02404117584229 34.09318398156763, -81.02404117584229 34.060588119230346, -81.08030319213867 34.060588119230346))')::geometry) 
) AS l 
ORDER BY shape_area_int DESC 
LIMIT 2000;

Explain Plan:

"Limit  (cost=9970.86..9975.86 rows=2000 width=1155) (actual time=484.172..489.691 rows=2000 loops=1)"
"  ->  Sort  (cost=9970.86..9977.31 rows=2580 width=1155) (actual time=484.169..489.564 rows=2000 loops=1)"
"        Sort Key: parcels_cama_wgs84.shape_area_int"
"        Sort Method: external merge  Disk: 6640kB"
"        ->  Bitmap Heap Scan on parcels_cama_wgs84  (cost=136.32..8519.16 rows=2580 width=1155) (actual time=2.357..463.939 rows=2569 loops=1)"
"              Recheck Cond: (the_geom && '0103000020E61000000100000005000000000000B0234554C06C4FFB59C1074140000000B0234554C009ACE473ED0B4140000000E4894154C009ACE473ED0B4140000000E4894154C06C4FFB59C1074140000000B0234554C06C4FFB59C1074140'::geometry)"
"              ->  Bitmap Index Scan on parcels_cama_wgs84_the_geom_geom_idx  (cost=0.00..135.67 rows=2580 width=0) (actual time=2.066..2.066 rows=2569 loops=1)"
"                    Index Cond: (the_geom && '0103000020E61000000100000005000000000000B0234554C06C4FFB59C1074140000000B0234554C009ACE473ED0B4140000000E4894154C009ACE473ED0B4140000000E4894154C06C4FFB59C1074140000000B0234554C06C4FFB59C1074140'::geometry)"
"Total runtime: 491.461 ms"
  • Have you tried ordering by ST_Area(geom) those geometries that pass the ST_Intersects test? – John Powell Apr 8 '15 at 22:03
  • 1
    Please take a look at: wiki.postgresql.org/wiki/Slow_Query_Questions . Especially the part about explain should be useful. – Jakub Kania Apr 9 '15 at 9:04
  • @JakubKania gotcha--it's a good link. But I'm more interested in a different approach altogether rather than improving my existing query. fwiw I'll append the question with my current query and the explain plan ...however I think that's just going to make it super noisy. – elrobis Apr 9 '15 at 14:12
  • @elrobis It's not about the noise, it's about understanding what is really happening. You should increase WORK_MEM, probably adjust the shared buffers too. – Jakub Kania Apr 9 '15 at 15:48
  • 2
    May be it is difficult to create an index on datasets, where object density is clumped or patchy in space. In this cases a fractal indexing strategies like Q-Tree are more efficent. But I cannot find any indexing schema in postgis for that approach. – huckfinn Apr 10 '15 at 7:10
1

is the area field a float? you may want to try creating the area index (clustered or non) on an integer field (if your use case can accept the generalization).

  • Perceptive. And it is. Interesting idea I'll try it. – elrobis Apr 8 '15 at 21:32
  • 1
    Based on your idea I re-clustered the table on the GIST/geom index, added an index as CEIL(shape_area) DESC, and ran it with the bbox/intersection in a nested select ..it did better at 2300 ms (saving 700ms). I'm still hoping there's a clever way to get it down to a 500ms query. – elrobis Apr 8 '15 at 21:55
1

I suspect that geometries such as your military area that is large and irregular and thus having a large bbox overlapping with many others forces the refine (cf., filter-refine) step in the search for exact match too many times slowing the result. The speed is not only affected by the size, but also the complexity of the geometry. So maybe trying a generalization on your geometries would help? There is no need to do the query discussed on full detail geometries in most cases I would think. The area values will not be affected, as they are not computed on the actual geometries, but stored. To make sure the topology of the polygons is correct, you could use Postgis's Topology preserving simplification (http://strk.keybit.net/blog/tag/postgis/) although I have to warn that his can lead to incorrect results in some cases (it can introduce spurious intersections thus introducing a relationship between two previously disjoint geometries in some marginal non-convex geom cases, such as deep inlets with a protruding peninsula coming into it - tested on Sydney harbour some time ago).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.