Do large vertex counts cause performance issues?

I have a table of several thousand tuples - each tuple has a geometry column. The problem is, these geometries have a large vertex count. The max vertex count is 400, while the average is 200. Obviously "large" is somewhat ambiguous. I "think" that's large, but maybe it's not. For some of these large geometries, I'm considering applying a smoothing algorithm to trim some of the points, IF a performance benefit can be gained.

I'm wondering how these high-vertex polygons affect performance? There is a GIS index on the geometry column. I would think performing an ST_Intersects or other similar functions that are exact would be MUCH slower, whereas a bounding box check, such as the && operator, would be negligibly slower.

In addition, would Postgres store these high-vertex polygons different? I have a basic understanding of the TOAST tables used for "extended" data - I wonder if Postgres would be utilizing this for the large polygons?

As for indexing, there probably isn't much gain, because the index already uses the bounding box for lookup, so whether you have 400 or 5 vertex points, your BB is going to be (roughly) the same, and the lookup will be roughly the same.

Any other considerations?

• Basic geometry operations, such as intersection, point-in-polygon, etc., typically scale logarithmically with geometry size, provided precomputation (such as contained in "index" files in certain GISes) occurs. If this is the case in PostGIS, then modest reductions in vertex count--even removing 90% of them--ought to have little real effect on CPU cycles. Data throughput for a few thousand records shouldn't be an issue, either. Obviously this is just speculation, but it suggests some simple scaling tests would resolve the question. – whuber May 31 '12 at 16:01
• Interesting point - thanks. So here's a more direct question that I hinted at in the O.P. - How does PostGIS/Postgres store the geometry types? TOAST tables are used for variable length data, so I would THINK they're also used for geometry types. Higher vertex counts could mean more TOAST table look ups. – Jmoney38 May 31 '12 at 16:27

Yes, the geometry type is a varying length data type even if it is just a point.

If you will get a performance issue depends on how fast you need things to happen and what you want to do.

A few thousand geometries is not very much, and 400 vertex-points is not very much either.

But simplifying the geometries might be a good idea to get better performance.

As whuber has commented some calculations will increase their query-time logarithmically with geometry size.

But not all functions you might expect will behave like that. First, the index will as discussed before reduce this effect where possible. The selectivity of the index depends of how big the bounding boxes are comapred to the whole data set.

Many functions also have algorithms that makes them more effective. Point in polygon for instance uses a technique of preparing the polygon and reusing that information. That is why PostGIS can solve this

Another function that might be thought of as increasing querytime logarithmically with size is distance calculations, but that is not true if the bounding boxes doesn't intersect, why that is you can see here

So, the only way to know if the number of vertexes is a problem is to test and get experience from different functions in different situations.

HTH

Nicklas

Good stuff, Nicklas - thank you. I also did some rudimentary testing and found that geometries are in fact stored in the TOAST tables, when the vertex count is "large." (relative to my application's usage) I'll post the analysis below:

Shared buffer cache initially:

# SELECT c.relname, count(*) AS buffers
FROM pg_buffercache b INNER JOIN pg_class c
ON b.relfilenode = c.relfilenode AND
b.reldatabase IN (0, (SELECT oid FROM pg_database
WHERE datname = current_database())) where c.relname like 'pg_toast%' or c.relname = 'my_test'
GROUP BY c.relname
ORDER BY 2 DESC;

relname         | buffers
------------------------+---------
pg_toast_2604080       |   35832
pg_toast_2604080_index |    1848
pg_toast_2619          |      28
pg_toast_2618          |       5
pg_toast_1255          |       4
pg_toast_2619_index    |       2
pg_toast_2618_index    |       2

Create my test tables:

# create table my_test(id integer, the_geom geometry, txt text);
# create index my_test_idx on my_test using gist (the_geom);

Shared buffer cache:
(no entry for my_test toast table yet)

relname         | buffers
------------------------+---------
pg_toast_2604080       |   35832
pg_toast_2604080_index |    1848
pg_toast_2619          |      28
pg_toast_2618          |       5
pg_toast_1255          |       4
pg_toast_2619_index    |       2
pg_toast_2618_index    |       2

OID for my_test table is 3301975.

Insert a large (300+ vertex) polygon entry to my_test table:

# insert into my_test values (1, st_geomfromtext('large polygon))'), 'This is a test');

Shared buffer cache:
(Now contains a TOAST entry for my_test)

relname         | buffers
------------------------+---------
pg_toast_2604080       |   35832
pg_toast_2604080_index |    1848
pg_toast_2619          |      28
pg_toast_2618          |       5
pg_toast_1255          |       4
pg_toast_2619_index    |       2
pg_toast_2618_index    |       2
pg_toast_3301975_index |       2
pg_toast_3301975       |       1
my_test                |       1

Now lets add a small geometry - hopefully it's not added to the TOAST table:

# insert into my_test values (1, st_geomfromtext('POLYGON((-114.0 32.0,-115.0 32.0,-115.0 33.,-115.0 33.,-114.0 32.0))'), 'This is a small test');

relname         | buffers
------------------------+---------
pg_toast_2604080       |   35832
pg_toast_2604080_index |    1848
pg_toast_2619          |      28
pg_toast_2618          |       5
pg_toast_1255          |       4
pg_toast_2619_index    |       2
pg_toast_2618_index    |       2
pg_toast_3301975_index |       2
pg_toast_3301975       |       1
my_test                |       1

Good! No TOAST was added for the small geometry

• And just to finalize, I'd like to avoid storage in the TOAST tables, if FEASIBLE. At this point, I need to research the storage size of geometries - i.e. At what size does a geometry cross the 2 KB page size? That's when it's being stored in TOAST. Thus, would it be feasible to try to smooth my polygons to shrink them below the 2 KB limit? Don't need answers at this point, just posting my thought process... :-) – Jmoney38 May 31 '12 at 20:07
• Interesting, I haven't thought about this. It would be interesting to compare the performance between tables with many small geometries compared to a few large. With constant total number of vertex-points it should be possible to see the penalty of reading toast-table. – Nicklas Avén May 31 '12 at 20:14