This summary of several ideas that have been floating around the commiity for a while. If I touch on your favorate idea and mange to totally mess up the explaination please jump in and fix and comment.

  • Throughput, Number of bits/features/transactions per unit of time
  • Performance Time, per bit/feature/transaction (inverse of throughput)
  • Latency, Wait time for a response
  • Capacity, Number of entities the system can support in a given configuration at a fixed level of performance
  • Scalability, Ability to increase capacity by adding hardware
  • Reliability, Length of time the system can run without failing
  • Response Time, Total perceived time it takes to process a request
Subjective Performance

Response Time is arguably the most important measure with respect to rendering.

DJB: but Response Time is difficult to define. Udig probably wants to put the first feature on the screen quickly. Geoserver WMS wants to get the image to the user as quickly as possible.

Response time is a subjective quality - and subjective experience is hackable:

Objective Performace

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:

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

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:

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).

Note: the short circuit idea would need to reverse reproject a pixel(at each corner) back to the world co ordinates.

Feature Cache

The idea of cacheing Feature information is currently in vogue:

The various implementations have different tradeoffs:

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

Raster Cache

The focus here is on minimizing the number of requests, and optimizing pan and zoom opperations.

  1. Request feature information for the current screen
    1. Render on to the current raster
    2. Render on to the zoomed-out raster (the content will only over the center of the zoomed-out raster)
    3. Render on to the zoomed-in raster (only content from the center of the current raster will be used)
  2. Request information for "tiles" surrounding the current raster
    1. Render this information to the surround raster
    2. Render this information to the zoomed-out raster - the content will now completely render the zoomed out raster

Origionally I thought we could favour what requests are need based on the current mode (pan or zoom) but it seems that the same requests need to be made regardless.

Note: This idea makes more sense with the fixed stepping size usually associated with zoom-in and zoom-out. BBox based zoom is unlikely to be helped by these ideas.

Note: Some features (like polygons) are almost scale in-dependent and requesting a larger zoomed-in raster (and then rescaling it) may work. Line work however does not respond well to scaling, although the idea may warrent attention to provide a form of immidaiate feed back.

Note: For features that are simply styled (say all to the same color), one could get away with storing 2 bit depth rasters and applying the color at rendering time using the graphics2d.drawImage (or equiv JAI opperations).

Postgis Hack

There are many simple hacks we can do when asking for spatial data from postgis.

But now for something completly different. In working with an OpenGL based renderer years ago one thing we ended updoing was defining wrapper functions that simplified the data sent depending on the current zoom level.

These ideas are mostly applicable to line work, but the ideas are sound. Consider a function that provides a real world "length" assocaited with a the diagonal of a screen pixel.

The easiest implementaiton is to walk along the line, or linear ring, and sample about the distance every pixel occrurs. For many real world features this is sufficient. The resulting geometry is only good for display but the reduction in size is worthwhile.

Another idea would be to provide a modificaiton of wkb that worked with shorts rather than doubles. I know this sounds like a bad idea, but spatial data is often very location dependent (especially with respect to a single geometry). By providing the geometry as a series of short values we can relize a hudge reduction in data size. The short values would need to be considered as a scaled value with in the bounds provided by the geometry's bounding box, or offsets from the first point.

If we cast our mind back to the earlier Feature Caching converstation, the above reduced Geometry starts to look similar to the Graphic construct from GO-1 or the point lists from the j2d renderer.

If we also included the projected bounding box of the screen we could ask the database to perform cliping for us. I kind of doubt the database woudl be kind enough to let us hack the internal quad trees (so we could pull of a index based rendering short circuit). So cutting down the size of the transmitted geometry is probably the best we could do.

Summary

All these optimizations have there place, and none of them are ready to be applied. We will need to come up with some hard numbers to see which, if any of these ideas are worth implementing.

Even then there will be run time tradeoffs.