Improving the Feature Join experience

So what was this screenshot all about?

Time for an explanation. This screenshot was the result of an experimental mg-desktop addition to make feature joins perform much faster (around 100 times faster as evidenced by the screenshot), by taking advantage of new FDO Join APIs that were recently introduced with the 3.6 release. Why does the FDO Join APIs perform so much faster? Time for a little backstory...

Why Feature Joins suck (performance wise)

Feature Joins are performed by the GWS Query Engine component of MapGuide. From a high-level overview, this component takes two input iterators (with interfaces similar to a FDO/MG Feature Reader), and depending on the capabilities of the left and right sides of the join a "merged" feature reader is returned that will loop the two iterators in the following fashion:

• Nested Loops (both sides do not support ordering)
• Nested block join and sorted block (left side supports ordering, right side doesn't)
• Sort-Merge (both sides support ordering)
• Batch Sorted Block (left side does not support ordering, right side does)

Now these join algorithms themselves are also sensitive to the data you're working with. For example, any sorted block algorithm is going to perform bad on datasets with high-spread of join key values (low-spread of join keys means lots of sorted duplicate joins values which can be skipped). Sort merge has issues regarding case-sensitivity of key values (though this may be a bug in the implementation). Nested Loops is obviously terrible if both sides are large (as is the case of a SDF to SDF join as per the above screenshot)

MapGuide in its current form is not aware of join factors which impact performance:

• The size of both sides of the join (Nested loops is obviously bad, but the inability to determine size means this can't be avoided if this is the designated algorithm)
• The spread of join key values (Sorted blocks work best on lookup-value type spreads not foreign-key type spreads)

It is all of the above factors which make having good performing feature joins a difficult proposition. ^

The FDO Join API (or: Let the data store figure it out)

So it's clear that MapGuide does a terrible and/or erratic job as a query optimizer, so assuming we want respectable performance of joined data, you would've probably avoided Feature Joins altogether and have the bits you want to join in question residing in the same centralised RDBMS, do the joins at the database level and wrap the result in a database view.

This approach is a good solution in terms of performance because figuring out the best way to join data is now a data store responsibility, and you can apply a whole assortment of indexes and other DBMS performance improvements that MapGuide is not aware of. From MapGuide's perspective all it sees is a table/view and it just queries that. But this approach presents its own problems:

• The need for metadata hacks for views to be properly recognised as a feature class (eg. SDO_GEOM_METADATA in Oracle)
• The type of view affecting selectability (eg. SQL Server, which requires schema overrides to work around)

With the introduction of FDO Join APIs, it allows us to do these type of joins in an ad-hoc fashion without needing to wrap our joined data into database views. Joining data with the FDO Join APIs is basically the equivalent of doing a SQL SELECT query with JOIN clauses. In other words, the FDO Join APIs lets you delegate join optimization to the data store and let it figure out the best performing way to do it.

Taking advantage of FDO Joins in MapGuide (with RFC123)

So as already explained, work on bringing support for this into MapGuide started with mg-desktop. Being essentially a self-contained version of MapGuide meant that mg-desktop was a nice sandbox for playing and experimenting with new features. So once support was built into mg-desktop, bringing it over to MapGuide proper was quite an easy affair.

So how does mg-desktop and MapGuide take advantage of FDO Joins?

We use the existing Extended Feature Class mechanism to construct an equivalent FDO Join select query, applying the proper property/class aliasing to ensure that the reader that is returned presents the same property list as a default feature join query.

When querying an Extended Feature Class, MapGuide does several checks to see if the FDO Join optimization path can be taken. These checks include:

• Does the underlying FDO provider for the Feature Source support FDO Joins? (obvious one!)
• Does the primary and joined feature classes of this Extended Feature Class originate from the same feature source? (this is important, because FDO Joins work within the context of the same connection, thus the classes we are joining must come from the same source)
• A whole bunch of other minor conditions which your Extended Feature Class will most likely satisfy (detailed in the RFC)

If the Extended Feature Class being queried passes the above checks, MapGuide takes the FDO Join path, which as seen from the screenshot above, can be up to 100 times faster than the regular Feature Join approach.

Additionally, Extended Feature Classes also double up as the metadata. You don't need to do SDO_GEOM_METADATA hacks or FDO Schema Overrides for these classes to be recognised. Because MapGuide already understands these elements out of the box!

Also, in case you're wondering, the performance numbers in MapGuide are even better than mg-desktop (up to 1s faster than the numbers in the above screenshot) due to connection pooling and object caching mechanisms present in the MapGuide Server code.

Conditions Apply

Now as you can see, only certain Extended Feature Classes can take advantage of this optimization. The other limitation is FDO provider support. As of writing this post, the following providers implement the FDO Join APIs:

• SQL Server
• SQLite

Given the high usage of these providers (you are using SQLite for all your spatial data aren't you?), there is a good chance of this optimization path being used.

The beauty of FDO is that as soon as an FDO provider implements the FDO Join APIs (like King.Oracle wink, wink, nudge, nudge), such configured Extended Feature Classes in MapGuide can automatically take advantage of this optimization path.

So there you have it. 100x faster feature joins if your data ticks all the boxes.

^ There is a 5th type of join algorithm that is (suprisingly) not implemented by the GWS Query Engine: Hash Joins. Though probably the most memory intensive join algorithm (due to needing to store one side of the join in a hash-table), this should always perform better than the default nested loops. Anyway, it's 2011. Memory is cheap! Having this join type implemented should improve the Feature Join user story even further. Guess that's another item on the TODO list.

Announcing: A fixed installer for MapGuide Maestro 4.0 RC1

Oops!

It turns out that as far back as the first beta release of Maestro 3.0, that the window installers I've been making did not include the XML schema files required for validating XML content.

So I've posted an updated 4.0 RC1 installer with the missing XML schema files. Note that this is only applicable if you've been downloading the windows installer package. If you have been using the zip packages, the XML schema files have always been in there, so everything's ok on that front.

To make sure that the XML schema files are properly set up, go to Tools - Options and check that the XML schema path is configured to point to the Schemas directory under your MapGuide Maestro installation directory

Or, you can click Reset and Maestro will reset all preferences to default values and auto-discover all the required paths.

Update: OSGeo is back in order. So the fixed 4.0 RC1 installer is available for download from here

Announcing: MapGuide Maestro 4.0 RC1

Here's another RC coming your way.

This release re-introduces the Package Editor feature, which has been missing since Maestro 2.1 and includes a big bucket of fixes and small improvements since beta 2.

One particular improvement which I'm proud of finally implementing can be summarised with this screenshot:

Yep, I finally figured out how do do it!

Download (back at OSGeo)

Announcing: FDO Toolbox 1.0 RC1

About time I started to get this thing to the 1.0 final release.

New Features

• Now using FDO 3.6.0 final release.
• Data Preview now supports the new FDO Join APIs
• You can now dump the contents of a Feature Class in the Object Explorer to SDF/SQLite via the context menu.

Also included is plenty of bug fixes and small improvments

Come and get it

Report Issues/Enhancements

A screenshot to tide you over

Stay tuned for more information :)

Announcing: MapGuide Maestro 4.0 beta 2

I am happy to announce the 2nd beta of MapGuide Maestro 4.0

The major new feature of this release is non-transactional package loading, which greatly improves the reliability of loading very large package files, at the small cost of losing the repository ACID-ity of the official approach. Should you encounter any failed operations during the package loading, Maestro will give you the ability to retry these failed operations until all failed operations are accounted for, or you choose to abort yourself.

Also included in this release is:

• Fixes for defects brought on by the new multi-site support
• Editor support for FDO expressions in color editor properties
• Updated to the latest mg-desktop binaries for Local Connection mode

Once again, this beta is available in the fat NSIS installer or the lean zip package (which excludes local connection mode). Users of non-windows operating systems will have to download the zip package.

Download (temporarily hosted on the mg-desktop site)

Introducing non-transactional package loading

The next beta of MapGuide Maestro 4.0 will feature a new way of loading packages which I call "non-transactional" package loading.

Normally the package loading process in Maestro is as follows.

1. Select the package file
2. Maestro invokes APPLYRESOURCEPACKAGE on the MapGuide Server and uploads the package file
3. Twiddle your thumbs, because there is no way to know how long this operation will take
4. The operation being transactional means that the operation will wholly suceeed or wholly fail.

Loading a package several hundred MBs in size only to be told that the entire operation failed at the end is needless to say, a very frustrating experience.

Non-transactional package takes a different approach. It eschews using the APPLYRESOURCEPACKAGE API (the cause of the thumb twiddling and waiting because there is no way to track progress) for an approach that allows progress to be measured. At the heart of a MapGuide Package is the resource package manifest, which is simply a list of resource service operations to execute on the MapGuide Server, which are generally a mixture of:

• SETRESOURCE
• SETRESOURCEDATA
• DELETERESOURCE

The existing approach executes all these operations on the server-side under one big transaction, the new approach executes all these operations one at a time from the client side and because we know how many operations need to be executed, we can measure the entire progress of the package loading operation.

Now when you load a package, you will be asked to choose the method of uploading:

Choosing the Transactional method will load the package in the existing fashion. Choosing the other option will use the non-transactional method and because this approach is measurable, we get a nice meaningful progress dialog to relay the upload progress.

So in what cases would you use non-transactional package loading over the default transactional one? Here's a few I've thought of:

• The package file is several hundred MBs in size
• The package file contains hundreds of resources to be loaded
• The package file is not loadable via the transactional method, which is generally the result of any of the above items.

Finally, because it's non-transactional if one operation fails it will keep continuing with the upload of the others, failed operations are logged. As a result, the upload can partially succeed and fail. Should the operation partially fail, it is planned to re-use the list of failed operations to allow you to re-run the package upload, but to skip all the successful operations, thus turning a partially failed upload to a fully successful one.


I've received some test packages which completely failed to load under the official package loading methods. These packages loaded without issues in the non-transactional mode. So no matter low large or small your data packages are, Maestro can upload it for you. One way or another.