More on the Multi-Level Grid

Hi Folks,

In my last indexing post, I filled in most of the details about our multi-level grid index.  Let me clean up a few lingering questions about our planar grid. We'll do this Q&A style:

Q:

What happens if I set the maximum number of cells-per-object so small that I cannot obtain a covering of my object?

A:

To make this concrete, let's take a look at one of the pictures from last time:

In this schematic, there are four top-level cells, and we can see that we need at least three cells to tile the object.  In this picture, we are using 13 cells, so we've set the maximum number of cells-per-object to at least that.  But what if we set it to two?

The answer is that in the case where the number of first-level cells needed to tile the object exceeds the max cells-per-object, we violate cells-per-object constraint.  This is really the only situation in which we'll do that, but it's necessary in order to ensure that we tile the object, and this is required in order to guarantee correct query results.

Keep in mind that in a real index, the number of top level cells is either 16, 64, or 256, and this will only happen if the max cells-per-object exceeds that value.

Q:

What if I have an object that falls outside, or partially outside the bounding box I have defined? Will I miss results?

A:

There is an implicit extra cell in the tessellation, what we call the root cell.  The root cell covers everything outside of the bounding box you've defined, and will be used to cover any object that touches it.  We can use this to guarantee correct results even if your object isn't well contained by your bounding box.  What will suffer is performance, and so it is still important to get the bounding box correct.

Q:

Are there times where you can answer the query using solely the index?

A:

Yes.  Consider a cell that is touched by one object, and completely covered by another.  We can tell that these two objects must intersect based solely on this fact: there is no need to actually run the intersection predicate.  We call this "intermediate filtering" (not the best name, but we needed something to call it) and we do implement it.  To do this, we store whether the object touches or covers the cell in the index row.

Q:

Which predicates are supported on an index?

A:

It depends on the type.  For geometry, we support STIntersects, STEquals, STOverlaps, STTouches, STWithin, STContains, STDistance, and STFilter.  On geography we only support STIntersects, STEquals, STDistance, and Filter.  We don't support the others simply because they don't exist on the type.

Q:

What is the difference between STIntersects and Filter?

A:

If there isn't an index, they do exactly the same thing.  This can happen on the client, or on the server if you haven't defined an index (or if the index isn't chosen for some reason).  When there is an index involved, Filter will not do any secondary filtering.  I.e., it is only guaranteed to return a superset of the results an STIntersects predicate will return: it may return extras.

This is useful for applications that are simply displaying results, are not sensitive to some extras, and want to avoid the cost of the secondary filter.  If you need precise results, use STIntersects.

If there are more questions, please ask, and I'll answer them here.  So far we've only talked about geometry, so next time I'll either fill in the gaps around geography or answer more questions.

Cheers,
-Isaac

Comments

• Anonymous
  June 16, 2008
  Hey - what happened to the QuadTree index? I turn my back for a few seconds and voila - a full blown spatial indexing system gets added!  Nice! Will the final version support commands for automating the indexing, like Oracle Spatial? (wash my mouth out)

• Anonymous
  June 17, 2008
  The comment has been removed

• Anonymous
  June 17, 2008
  With my dodgy eyesight, I'm sure it looked like an r-tree! :-)

• Anonymous
  August 08, 2008
  Nice series of articles. So, what differs with Geography... how does your grid lie on a round surface?

• Anonymous
  August 08, 2008
  Thanks for the poke---I conveniently forgot to complete this series, didn't I?  Expect something soon(ish). -Isaac