Monday, 27 September 2010

Some MySQL projects I think are cool - OpenQuery Graph Engine (OQG)

This project was announced a year or so ago by Antony Curtis who used to work for MySQL AB. Having met Antony a few times I was intrigued to see what he was up to. The quote on the OpenQuery website describes it well :
The Open Query GRAPH engine (OQGRAPH) is a computation engine allowing hierarchies and more complex graph structures to be handled in a relational fashion. In a nutshell, tree structures and friend-of-a-friend style searches can now be done using standard SQL syntax, and results joined onto other tables.

That sounds cool, and it's the first time I've heard of a MySQL 'Computation engine' plugin. Delving further into the manual gives some insight, and there's some unexpected twists there :
  • OQG is a storage engine, but data stored is not persistent w.r.t. server crashes.
  • All tables have the same schema, storing details of graph 'edges'.
  • The fixed schema has a magic column called 'latch'
  • Depending on the constant value of latch used in a SELECT statement on the table, the engine will return different 'pseudo results'.
The last fact is the coolest one. As far as I understand it :
  • SELECT where latch = NULL AND ... allows queries on the graph as though it were a list of edges (as the data was entered).
  • SELECT where latch = 0 [AND ...] allows queries on the graph as though it were a list of nodes.
  • SELECT where latch = 1 [AND ...] allows Dijkstra's shortest path algorithm to be applied to the graph
  • SELECT where latch = 2 [AND ...] allows a breadth-first search to be applied to the graph
This is a superb hack! I imagine the OQG engine internally has an in-memory graph structure which is maintained as edges are added via the INSERT Api. The SELECT Api then gives access to different views of the underlying graph and even allows complex parameterised functions to be applied to the graph, giving results as a set of rows which can be decoded into the required result. It's not pretty, but it's an extremely pragmatic approach to embedding graph access and operations within a database.

It's also undeniable that the use of magic numbers and the 'latch' column adds a certain arcane wackiness that charms this reader. It's definitely a MySQL-style solution, continuing the tradition of MyISAM, Blackhole, Federated etc where good-enough gets to market before best, and 20% of the implementation effort delivers 80% of the functionality.

Once again I'd be interested to hear about how this is actually being used, and what sort of difference it is making.

Each of these three cool projects enable new solutions individually and expand the dimensions of what is possible using MySQL. In combination they open up a vast expanse of potential. One of the best things about them is that they all happened outside the confines of MySQL / Sun / Oracle. Hopefully they will get the success they deserve so that we can have more cool new projects in future.

No comments: