[postgis-devel] GeomUnion Performance Info

[strk at refractions.net]

On Wed, Jun 22, 2005 at 12:35:17PM +0100, Mark Cave-Ayland wrote:
> Hi Bill/strk,
> 
> > -----Original Message-----
> > From: postgis-devel-bounces at postgis.refractions.net 
> > [mailto:postgis-devel-bounces at postgis.refractions.net] On 
> > Behalf Of strk at refractions.net
> > Sent: 22 June 2005 10:36
> > To: PostGIS Development Discussion
> > Subject: Re: [postgis-devel] GeomUnion Performance Info
> 
> (cut)
> 
> > Index is not required, the ORDER BY will use operators 
> > defined by the btree operator class.
> 
> Correct. I'm not exactly sure what the ordering is for Btree indices. I
> thought that it was the area of the bounding box of the geometry, but
> looking at PostGIS 1.0.1 source it appears the ordering criteria is based
> upon the outermost edge of each geom. Can anyone clarify this criterion as
> there are no comments in the code as to how this works?

Basically btree index has NO 'planned' use so far.
We have just seen analyze will use it but we never exploited
actual efficiency of that analisys return (talking about
pre-800 of course)

I defined an operator class for btree when I realized pg800
(or previous?) required it for ORDER BY, DISTINCT and GROUP BY
operations.

Current implementation is comparison of (in that order):
xmin, ymin, xmax, ymax.

This brings to btree ordere geometries being close
(at least in bbox terms), so it probably reduces
the occurrences of disjoint bboxes in GeomUnion operations
(can be checked uncommenting a comment in the GEOS shortcircuit
block).

Since we DO have shortcircuits now, we need inspect other aspect
impacting performance, and see how GiST vs. btree compare in
this sense. Btree indexing strategy can of course be modified
since I don't think anyone is using it, but I maybe different
operation would benefit from different indexes, so this might
be a short-sigthed approach compared to definition of different
indexes for different-kind operations (cluster on this, cluster
on that... more an interesting research topic then an actual
development plan)

...
> > > BTW: I tried to create a btree index on my parcels, but got this:
> > > 
> > > gis=# create index parcel_shape_btree ON parcels (parcel_shape);
> > > ERROR:  index row requires 8452 bytes, maximum size is 8191
> > > 
> > > go figure.
> > 
> > Ach! I think we should visually see that btree order!
> 
> Hmmm, perhaps the btree index is trying to stuff the whole geometry into the
> index key instead of just the bounding box? I'm not sure if there is
> anything we can do about this...

We can probably force use of bbox as key as it is done for GiST, but
that would probably require a dump/reload again so I'd think twice
before doing that. Let's first see if we have a practical use for btree
first.

> Curiosity got the better of me and so I decided to have a quick look at the
> source to see how the GiST is traversed during an index scan.

.. welcome aboard ;)

--strk;