MS RFC 52: One-pass query processing
======================================================================

:Date: 2009/03/08
:Authors: Steve Lime
:Contact: sdlime at comcast.net
:Last Edited: 2009/06/03
:Status: Adopted
:Version: MapServer 6.0

Overview
------------------------------------------------------------------------------
This RFC proposes change(s) to the current of query (by point, by box, by shape, 
etc...) processing in MapServer.

Presently MapServer supports a very flexible query mechanism that utilizes two
passes through the data. This works by caching a list of feature IDs (pass one)
and then a second pass through the features for presentation: templated output, 
drawing, or retrieval via MapScript. The obvious problem is the performance hit 
incurred from the second pass. The real pain is that the msLayerGetShape() function, 
as implemented, provides random access to the data which can be very expensive for
certain drivers.

Technical Solution
------------------------------------------------------------------------------
There are a number of potential solutions:

1. One could cache the returned shapes in memory. While this wouldn't result in 
a true single-pass, you wouldn't have to go back to the original driver twice. 
However, it could lead to large memory consumption with even moderately-sized 
datasets. Multiple clients accessing services at the same time would only 
compound the problems. Some testing has confirmed this method to be no faster
and probably even a bit slower than option 3 below.

2. Another solution would be fold much of the query pre-  and post-processing 
code into the msLayerWhichShapes() and msLayerNextShapes() functions so that
the access paradigm used in drawing layers could be used. Subsequent research
has let us to conclude that a true single pass is not possible in some cases.
For example, GML requires a result set envelope be written out before writing
individual features. There's no way to get that initial envelope without a 
pass through the features.

3. A final solution would be to change how the msLayerGetShape() function 
behaves. We prepose changing the behavior of that function to provide random
access to a result set (as defined by msLayerWhichShapes()) rather than the 
entire data set. This removes most of the overhead currently incurred by 
referencing the results already returned by the data driver in the initial 
query. For implementation purposes we would retain the current msLayerGetShape() 
implementations to support easy random access and create a new function 
called msLayerResultsGetShape(). 

msLayerGetShape() would *only* be used via MapScript to preserve true random 
access functionality. Note that drawing uses msLayerNextShape() and does not
rely on index values.

Under this last solution data drivers would need to do two things:

  * update the population of the shapeObj index property (long int) with a value 
    that will allow msLayerResultsGetShape() to randomly access a result

  * creation of the driver-specific version of msLayerResultsGetShape() to 
    retrieve a shape from the results created in msLayerWhichShapes()

  * the default implementation of msLayerResultsGetShape() would simply wrap
    msLayerGetShape() since most drivers would not have to implement the newer
    function (e.g. OGR or shapefiles)

The query functions would need to:

  * not close the layer when finished with a query (we assume that users will 
    want to do something with the results)

  * allow msLayerWhichItems() to retrieve ALL items so that the retrieved
    shapes are presentation-ready (draw, template, or ...)

The presentation functions:

  * refrain from calling msLayerOpen(), msLayerWhichItems(), msLayerWhichShapes()
    since that has already been done in the query functions

MapScript layerObj wrappers:

  * add resultsGetShape() method

This solution has been piloted in the single-pass sandbox with very promising
results. In some cases queries run orders of magnitude faster. One positive side
effect is that primary keys need not be used to retrieve features from the result
set. It is the drivers responsibility to provide data to uniquely identify a 
row in the result set.

Backwards Compatibility Issues
------------------------------------------------------------------------------
This solution will most likely require changes to MapScript applications that 
process query results depending on types of data being processed. Those hitting
shapefiles for example will still function "as is" since there that driver will
still be using msLayerGetShape(). Any script hitting a RDBMS data source will
have to swith to using resultsGetShape() instead of getFeature()/getShape().

One casualty would be the query save/read functions. Since the processing of 
a set of results would be specific to dataset result handle it won't be 
possible to get back to a result once a layer is ultimately closed. A proposed
solution to this problem is presented next.

Query File Support
------------------------------------------------------------------------------
Query files have provided a means of saving the results of a query operation for
use in subsequent map production. The series of indexes gathered during a query
are written to disk and read later to be used to access the data a feature at a 
time. With the proposed changes this simply won't work with RDBMS data sources.
It becomes necessary to instead recreate the result set but re-executing the 
query. Problem is, there's no easy way to serialize query parameters.

I propose creating a new object, a queryObj, to store the various parameters
associated with MapServer queries. It might look something like:

.. code-block:: python

   typedef struct {
      int type; /\* By rect, point, shape, attribute, etc... Types match the query functions. \*/
      int qlayer; /\* used by all functions \*/
  
      rectObj *rect; /\* used by msQueryByRect() \*/
  
      char *qitem; /* used by msQueryByAttribute() \*/
      char *qstring; /\* used by msQueryByAttribute() \*/
  
      ...and so on...
   } queryObj;

A single queryObj would hang off a mapObj and the mapObj would be the sole parameter 
passed to the various query methods. MapServer C code, primarily the CGI and OGC
interfaces would simply populate the appropriate queryObj members and call the correct
query function.

MapScript would be unchanged. The wrappers for the various query functions need only
use the user supplied parameters to populate the queryObj and then call the query
function. The queryObj would be immutable.

By storing all the information in a single store it should be easily serialized to
disk. When read, the reconsituted queryObj could then be used to re-execute the
appropriate query. The msSaveQuery() and msLoadQuery() function signatures would
remain "as is" although the internals would change.

Files Impacted
------------------------------------------------------------------------------
* driver files: implement msXXXLayerResultsGetShape() function to shape fetching 
  code if necessary

* maptemplate.c: don't open/close a layer when presenting results

* mapgml.c: don't open/close a layer when presenting results

* mapdraw.c: don't open/close a layer etc... IF if drawing a query map

* maplayer.c: refactor msLayerWhichItems(), add msLayerResultsGetShape() to the
  layer plugin API

* mapquery.c: re-work msSaveQuery() and msLoadQuery(), change query functions
  to take a lone mapObj as input, add msInitQuery() and msFreeQuery() functions

* mapserv.c: populate map->query before calling query functions

* mapwxs.c (various): populate map->query before calling query functions

* mapfile.c: leverage msInitQuery() and msFreeQuery() functions

* mapserver.h: define queryObj, add to mapObj

* mapscript (various): update map/layer query methods to populate a queryObj

* others? (mapcopy.c for one)

Although a number of files are impacted the changes in general are relatively simple.

Unknowns
--------------------------------------------------------------------------------
To date only shapefiles, PostGIS and Oracle drivers have been tested with this new
scheme, all with positive results. Even shapefiles showed a performance improvement
simply due to incurring the overhead of opening files just once. It's not clear how
OGR, SDE and raster queries will be impacted. I hope the owners of those drivers can
comment further.

MapServer has supported a rather obscure query method called queryByIndex() as basically
a wrapper to msLayerGetShape(). This change may render that method obsolete but more
checking need be done.

Voting History
--------------------------------------------------------------------------------

+1 from SteveL, DanielM, HowardB, PerryN, TamasS
