[postgis-devel] estimating quality of spatial indexes

[Sandro Santilli]

On Tue, Mar 03, 2015 at 11:04:25AM +0100, Rémi Cura wrote:
> A while ago I would really have appreciated an easy way to visualize index.

I'm looking at it now. An N-dimensional index. Projecting level-1 nodes
on the XY, XZ and XM planes (ST_SwapOrdinates!).

Done by implementing text output for BOX2DF and GIDX, and then
convert that output to WKT using replace.

Will commit shortly, meanwhile get Gevel installed :)
git://sigaev.ru/gevel

--strk;

> 2015-03-03 9:58 GMT+01:00 Sandro Santilli <strk at keybit.net>:
> 
> > On Mon, Mar 02, 2015 at 10:57:29AM -0800, Paul Ramsey wrote:
> > > Yes, I think the n-d index is still ang-tan.
> > > Oleg and Teodor's site had some code for visualizing r-tree boxes that
> > > could maybe be used to get a feel? Doing higher dimensions is going to
> > > be difficut, I would imagine.
> >
> > I got Oleg and Teodor's "Gevel" in place, great tool!
> > Now the problem is that we hide so much our index types under the carpet
> > that converting index keys to geometries is not easy.
> >
> > Not only BOX2DF type lacks a cast to GEOMETRY but does not even implement
> > text output, so there's basically no way to get it printed.
> > Hadn't tried yet, but I guess the same holds for GIDX.
> >
> > Do you guys have an problem with me implementing the casts ?
> >
> > --strk;
> >
> > > On Mon, Mar 2, 2015 at 10:54 AM, Sandro Santilli <strk at keybit.net>
> > wrote:
> > > > I'm running performance tests with n-dimensional data and
> > > > found cases in which fetching 5 points out of ~35 million
> > > > can take 20K reads _or_ 2K reads depending on whether the
> > > > Z/M selectivity is higher or the 2d selectivity is.
> > > >
> > > > In other words, if the query box is large but "low" it takes
> > > > 10 times more seeking than if it is narrow but tall.
> > > >
> > > > I guess this has to do with the way splits were choosen and of
> > > > course to the distribution of the data. To know more about the
> > > > case I'd like to be able to "see" the index volumes in some way.
> > > >
> > > > Do you have ideas about how to visualize contents of the index ?
> > > > I remember someone did it a long time ago.
> > > >
> > > > Another though is that the 2d index was changed 2 years ago
> > > > to use Korotkov ( double-sorting ) approach for splitting, whereas the
> > > > nd seems to be still using Ang-Tan one, is that correct ?
> > > >
> > > > REF: http://en.wikipedia.org/wiki/R-tree
> > > >      http://trac.osgeo.org/postgis/ticket/1895
> > > >
> > > > --strk;