ThinkGeo.com    |     Documentation    |     Premium Support

Indexing advice

#1

Could someone give me a little background on spatial indexing support please:


When using shapefiles, we`ve been creating spatial indexes on disk, and these give a noticeable performance increase when rendering.


As I understand it, this is because the indexing will allow the renderer to quickly cull the amount of shape information to be processed to what is required onscreen (similar to the concept of preprocessing bounding boxes?)..


Is this roughy right? Also, my understanding is that the shapefiles are fully loaded into memory straight away.. i.e. the spatial index is not used to index the shapefile binary, say when panning or zooming?


Does this mean indexing will have little or no impact at full extent?


Most importantly, is there anyway to get the advantages of spatial indexing if shapefiles have been moved into sql server 2008?


 



#2

Gordon, 
  
   There is all of mystery around spatial indexes so let try and de-mystify them for you.  This information is for shape file indexes but it in some ways broadly pertains to other system such as Oracle Spatial and SQL Server with spatial support.  You are pretty much right on all your points. 
  
   A spatial index hold the bounding box information for each shape along with the Id for that shape.  The main purpose of the index is to be able to quickly find what shapes are withing a given bounding box extent.  For example if you have road data and that contains 500,000 records for the state of Texas but you want to just display the roads of downtown Austin then the spatial index will help.  Without the index we would need to look at each of the 500,000 records and determine if that record was in the extent you want to draw.  The way the bounding boxes are stored in the index uses an R-Tree index which optimizes the locations of the bounding boxes in a hierarchy.  Similar to something like a binary tree.  If you have one million names in alphabetical order you can first jump to the middle of the list see if the name is before or after the name you are looking for then jump to the middle of the next half of the list.  In just a couple jumps you can find the one name in a million. 
  
   This approach is much faster than even storing all 500,000 bounding boxes in memory.  It also allows us not have have that additional memory overhead.  Spatial database such as Oracle spatial use the same kind of R-Tree, or something similar, to be able to quickly find a few records out of many.  Because it is optimized for finding a few records in many it has little or no effect if your extent covers the entire set of records, just like you mentioned in your e-mail.  It can even have a negative effect.  I believe we do an optimization check to see if the area you are requesting covers the full extent and if so we skip the index and just dump back everything. 
  
   The spatial index does not have anything to do with loading the shape file into memory.  In fact we do not load the shapes into memory except for the ones you need at any given extent while drawing.  After that we purge them from memory.  This is to conserve memory as many of the datasets out there can be gigs and gigs of data.  You might think that storing the recently used shapes in memory would be an advantage such as when you pan but we find it’s not the case and can even slow things down.  The reason is that in Windows there are many levels of caching already going on.  We have the disk cache which is holding lots of data, next there is the OS which is caching requested data and so on.  We find that once we have requested the data then it sits in these caches quite along time.  If you load a map and watch the hard drive light, the first time you see it glowing.  Then refresh a few times and even though we re-request the data there is hard drive activity. 
  
   To your question about SQL 2008, how do you mean moved?  We have run into people why physically move the files intoa blob into a database and then read them into a memeory stream at runtime.  Is this what you mean?  If so then we can still build indexes for them as well the strem them into Map Suite at runtime.   
  
   If you mean, and this is the more mainstream approach, you will extract the features and load them using the new SQL spatial functions into the database then the answer is yes.  We have a MsSql2008FeatureSource and Layer that will help you access the data.  Note that we have had a customer mention that our API doesn’t take advantage of the SQL spatial index.  Actually the reaosn is that you have to build it as an index and the use hints in the SQL to make it use them.  He forwared to us a great article and we are in the process of putting that in.  I would guess in two weeks or so we will have that in.  Our plan is to make that API really easy to use and allow you to with a quick line of code build the index and we will automatically use it to get you the best performance. 
  
 I hope this helps. 
  
 David

#3


 Thanks David, your reply was very helpful. 
  
 I’m a little surprised about the shapefile loading actually, but what you say makes sense regards caching and memory overhead. 
  
 We are investigating moving shapefiles into sql 2008 as geography types at the moment.  So it seems we would swap the cached disk read you describe, for a database trip in that case, even with the support for indexing. i.e. when using sql spatial indexing we will reduce the data fetch to just what is needed, but it is still remote rather than cached or held locally. (Of course, this is an architectural rather than a ThinkGeo issue).  
  
 I guess at that stage, once spatial indexing is optimised to return the correct region, it is a matter of tweaking the detail in the shapes themselves to be appropriate for the bandwidth available at a given zoom level.  Are there any diagnostic functions we could use to help with that? For instance, if we could see vertices drawn per refresh (or something), that could be used to tune the shapefiles and zoom levels to avoid spikes in bandwidth requirements (and hence slowdowns) maybe? 
  
 As luck would have it, I found the other thread you mention the moment I clicked send  … We’ll be watching developments with interest. 
  


#4

Gordon, 
  
   You are not alone in the quandary of moving to SQL from shape files.  We see it all the time with customers.  My opinion is that shape files are really fast and try to use them if you possibly can.  You just can’t beat local disk access.  The exception is with a fast network and a hulk of a SQL server.  In that case you could possibly transmit faster than a hard disk could read if SQL has a big cache and some raid 10 arrays.  
  
  I think for shape files they are easier to get right then SQL.  A newbie to SQL who doesn’t know how to tweak the server for fast access could make things quite slow where shape files are always fast with an index.  The other issue with SQL is that you are somewhat slowed down by single record access.  I mean with a shape file you can read random records one off and they all all as fast.  With SQL each single record request is a round trip.  The key with SQL is to try and batch things for one request with a big payload.  Depending on your application this might be slow. 
  
   Another option to think about if most of your data is base maps and static is to setup a WMS or osme sort of image server.  The server could have a big pipe to SQL and as it serves requests it could cache the drawn data in one spot.  This would help keep the requests down on the SQL server.  The bandwidth may or may not be higher depending on the complexity of the data and how many layers.  If you have lots of layers then the one image might be faster than all of the vector data. 
  
   You hit upon a key item for speed with is optimizing your data for the scale.  This is the single biggest thing you can do to keep bandwidth low and speed high.  I like to think the rendering time is really a factor of the amount of vector data.  If you have allot of vector data then the time will be slower.  To this end there are lots of things you can do for this.  If you need lightning fast maps you can try one or all of the following. 
  
 1.Simplify complex polygons relative to their zoom level and scale.  We don’t have a tool for this but many end user GIS packages do.  You can also contract a GIS company to do this.  It basically takes complex polygons and removes points while keeping their shape consistent.  Make a few of these for various zoom levels and since there are fewer points they will draw much faster.  This duplicates some data in your database but it is well worth it. 
 2.For high detail polygons such as state, county or block code boundaries cut them up into smaller polygons.  There are actually two steps to this.  First create a new line based files that is just the outlines of the polygons.  These you will use to draw the boundaries.  Next take the polygons and create a grid of x by x size depending on your scale and cut the polygons up into smaller ones.  
  You may be wondering why do this??  If you are zoomed into a county and want the polygon to draw with a background then even if you can’t see any of the sides we still need to fetch the entire polygon and draw it.  It takes time to fetch the polygon.  Then we have to draw it because we don’t know you will not see the side.  If you cut them based on a grid then we pull just a few probably square pieces and draw them.  This is really fast.  Of course since you cut them you cant outline these polygons but that is where the line based outlines come in  you cit those as well with the same grid and they draw as lines and the polygons go in as just fills.  You may be thinking we can just determine if we can see a side while we draw but the math is complex and slows down the more points you have.  After lots of testing we found it’s faster I in almost every case to just draw them and let GDI+ clip it. 
 You can do the cutting yourself or possibly professional services could help with a utility. 
 3.The other thing is to make sure that the desktop edition’s caching is turned on.  I think you need to check the Map1.Cache. Something and make sure to set the cache directory.  Do this for all the Overlays that you can safety cache.  The Overlays make it easier to segment your data into set of layers that can be cached and those that can’t as caching is by overlay. 
 4.Another idea is the one above where you setup a tile server of sorts and then you can create a special layer on the client that consumes those tiles over the network.  There again the Overlays and Layers can help you sort out what can be tiled and what cannot. 
  
  
 Unfortunately I don’t have any magic tools for you.  We have toyed around with writing them here but the 3.x releases have take center stage.  If these are key to you I would suggest maybe some professional service we offer to build something for your situation.  This is allot of information but that just a brain dump from me. 
  
 David