Versions Compared

Old Version 9

changes.mady.by.user Adrian Custer

Saved on

compared with

New Version Current

changes.mady.by.user Adrian Custer

Saved on

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
Comment: Migrated to Confluence 4.0

...

  • Do Something quickly, by responding at all the percieved processing time is reduced.
  • Adjust percieved response time by rendering longer lines first.
    order by length(the_geom) DESC
    User's "feel" that the render is basically done, and largely ignore it filling in a bunch of "small" stuff near the end
  • Many fast, studies show that a a progress that has many small steps each of which has a fast progress bar, appears to go faster then providing one process bar that slowly works though each of the steps. I seem to recall people percived the difference to be as high as 30%.
Objective Performace
  • Capacticty, the big convern is not making use of a system that limitis the number of features that can be rendered to the size of memory
  • Latency, we would like a minimal wait for response to start being displayed on screen. This is mostly bound by the turnaround time of the DataStore prociding the features
  • Throughput (or Performance Time) indicates the efficiency of of drawing process, although factors such as the speed in parsing GML data make actually provide the bottleneck
  • Scalability (throwing hardware at the problem) is desirable but not the end all and be all of solutions. Using an OpenGL based renderer is wonderful for rendering graphical content, but you may force your users into the purchase of a new video card.

Index

The use of an index (specifically a spatial index) is an optmization we can do that will actually help. That said it may not allways help. For our shapefile datastore, for small shapefiels, the entire file is likely to be memory mapped (and an index is likely to get in the way).

...

There are three index techniques that I have heard of:

  • STR-Tree - JTS implementation. Need to provide all the features before use, get a nice balanced tree. Seems to be the best when you can use it. So fastest for use, poor choice in the face of edits.
  • R-Tree (Region Tree) - I think Shapefile Index Support was going this way.
  • Quad-Tree - subdivide and conqure, my impression was that this one wanted to know the total bbox first (something we can get from a shapefile), and then splits into 4 (ish) boxes when the content grows too big for one node in the tree.

The abilities I am looking for out of the index system are the following:

  • spatial query the usual point of a spatial index
  • ability to short circuit the rendering process based on index information.

The short circuit idea is my own (well thanks to David Blasby too) and I am not sure how sane it is. If the features in a index node are all less then one pixel at the current resolution then:

  • one feature needs to be displayed for line data like roads
  • no feature needs to be displayed for polygon information like lakes
Panel
Index Best Case Senario

My best case senario for indexing is the following:

  • Quad Tree implemented for Shapefile, so each node has a distinct spatial location
  • Ability to perform a spatial query for the area on the screen.
  • Ability to "recognize" when a the bounding box for a node is less than a pixel in size. If so renderer can request one (and only one) feature, for rendering as a single pixel. Feature returned shoudl be reproducable (something like the first feature) across runs.
  • Ability for the index to be memory mapped into memory. I wolud prefer not taking on the added complexity of a index that is cached into memory manually.
  • based on mapserver .qnx files? There is C source code to port, and a working executable to generate the correct index files.
  • The volume of feature data required should remain fairly constant at various levels of zoom. As we zoom in the spatial query provides us with less features. As we zoom out the short-circuit reduices the number of features we need to renderer.

Note: that these index requirements, and the joining requirements start to make this whole thing look like a limitied spatial database. Admittedly it can talk to more data sources (but we should look into working with others on these isses).

...

The idea of cacheing Feature information is currently in vogue:

  • j2d renderer (Martin) makes use of a cache information derived from a feature (point lists?), and enough information to style and pain them.
  • lite renderer - currently does not cache
  • lite_renderer2 - but Andrea has been asking martin a lot of questions so I kind of expect lite renderer 2 to go in this direction
  • GO-1 - makes use of a FeatureCanvas as a bridge between Features and Graphic (where graphic has the geometry and style information)

The various implementations have different tradeoffs:

  • most use float rather than double (for space saving)
  • some do great reprojection (turning straight lines) into curves based on pixel size

Well as you can see above nobody actually caches features they all cache a simplified geometry, paint and style information.

...

Even then there will be run time tradeoffs.

  • almost any of these schemes will get in the way (slowdown and complicate) a memory mapped shapefile
  • caching Features may be applicable for a data size of 1000 features, caching Graphic (simplified Geometry + styling) may be applicable to to 10,000. Using a index with the short-circuit may be worthwhile over 10, 0000. Caching Rasters may be worth while for a WMS.