Zsort ?

[Attila Csipa]

On Thursday 17 May 2007 17:01, Stephen Woodbridge wrote:
> So in the small result set, these could be sorted on the fly, but it
> would get a little convoluted to have an attribute index in combination
> with the spatial index. That would probably require having a spatial
> index for each attribute index to preserve the order of that index,
> which seems a little much.

Maybe I'm not correct, but as I outlined in the previous mail we could get 
away with just one index per attribute + the spatial index. The index is 
roughly a B+ tree, sorted by a given attribute (or even attribute 
combinations). When we do the pass thorugh the spatial index, we have the IDs 
of the items we need to draw. Using a hash these can be looked up quickly. 
Now, we do a simple pass through our B+ tree, and discard every value that is 
not in our hash, and remembering each one that is there. The result is a 
subset of the attribute index which contains only the shape IDs that need to 
be drawn _in the proper order_, no additional sorting or manipulation is 
needed. This should not be a major performance issue unless the B+ tree or 
the spatial hash have an excessively large number of nodes, in which case the 
bottleneck would be probably reading all those shapes and attributes, and not 
the extra tree/hash operations that need to be done to get the sort order 
right.