[postgis-users] Fun with multikey GiST

[Andy Turk]

On Friday 21 June 2002 03:58 pm, you wrote:
> I am disappointed that the multikey GiST was not more effective. I would
> have hoped it would return results just as fast as pure geometric
> queries. One possibility for multidimensional searching is generalizing
> the RTree index we are using to operate in 3-space. That way one could
> index features pseudo geometrically, with the Z value standing in for
> some other parameter. A ways away though...

I suspect that the distribution of keys is more of an issue than the outright 
performance of multikey GiST.

The RTree over GiST index is pretty efficient over my data because there's 
relatively little overlap between the geometries and the "sizes" aren't 
skewed. In essence, while my data is made up of line segments, the bounding 
area of each segment is roughly the same size and only overlaps its immediate 
neighbors.

The string hashes are more random and the min-max bounds of a collection of 
hash values almost certainly overlap in ways that are inconvenient for the 
index.

When the index is being created, the algorithm (I think) looks at the leaf 
nodes thus far and then chooses one of the dimensions to make the split. The 
dimension with the greatest separation is used. I'm reaching here, but I 
think that the geometry dimension(s) separate nicely, while the hash 
dimension is a mess. This will probably force the index into less than 
optimal behavior.

One tool that would be really useful is to have an overall measure of the 
overlap within the index node hierarchy. If everything partitions out nicely 
with little overlap, then it'll be very efficient because most of the 
subnodes will be eliminated from the search. If there's a lot of overlap, 
then more subnodes will have to be searched and performance will suffer.

Anyway, I'll have to figure out how to speed this query up because I need to 
increase the data in the table by another order of magnitude for our software 
to be functional (woo hoo!).