Tag Archives: graphengine

Open Query @ MySQL Conf & Expo 2010

Walter and I are giving a tutorial on Monday morning, MySQL (and MariaDB) Dual Master Setups with MMM, I believe there are still some seats available – tutorials are a bit extra when you register for the conference, so you do need to sign up if you want to be there! It’s a hands-on tutorial/workshop, we’ll be setting up multiple clusters with dual master and the whole rest of the MMM fun, using VMs on your laptops and a separate wired network. Nothing beats messing with something live, breaking it, and seeing what happens!

Then on Tuesday afternoon (5:15pm, Ballroom F), Antony and I will do a session on the OQGRAPH engine: hierarchies/graphs inside the database made easy. If you’ve been struggling with trees in SQL, would really like to effectively use social networking in your applications, need to work with RDF datasets, or have been exploring neo4j but otherwise have everything in MySQL or MariaDB, this session is for you.

We (and a few others from OQ) will be around for the entire conference, the community dinner (Monday evening) and other social events, and are happy to answer any questions you might have. You’ll be able to easily recognise us in the crowds by our distinct friendly Open Query olive green shirts (green stands out because most companies mainly use blue/grey and orange/red).

Naturally we would love to do business with you (proactive support services, OQGRAPH development), but we don’t push ourselves on to unsuitable scenarios. In fact, we’re known to refer and even actively introduce clients to competent other vendors where appropriate. In any case, it’s our pleasure and privilege to meet you!

See you all in Santa Clara in a few days.

OQGRAPH update: speed, maze example, 5.0 packages

Antony has done a bit of magic, considerably speeding up inserts. Since the base implementation does not have persistence, insert speed is particularly important. Copying the 2×89,051 edges for the Tree-of-Life example is now near-instant.

The delete bug has been fixed.

There’s a new Maze example in the OQGRAPH trunk on Launchpad, first introduced in my MySQL University session. I created/inserted a maze of 1 million rooms (that comes to about 3 million edges), and OQGRAPH found the shortest path (122330 steps for this particular maze) in abound one second. That’s pretty good, I think!

Last but not least, the OurDelta builds of MySQL 5.0.87-d10 have been published (for all Debian, Ubuntu, CentOS/RHEL, generic) and the -Sail edition of the packages have OQGRAPH built-in. So if you use 5.0 or just want to play, it’s now very easy to get started!

Earlier in the week we received a message from an early OQGRAPH adopter, telling how he’s using it to manage paths in his IP network: calculations that would previously require many minutes are now completed in a fraction of a second and a single query. He admitted to be pretty much an all Oracle shop, with this OQGRAPH app being his first exploration of MySQL space. He loves OQGRAPH, and I suppose that by proxy implies he likes MySQL too ;-)

OQGRAPH engine on MySQL University – 5 Nov 2009 10:00 UTC

MySQL University logoOnly a few weeks after Walter’s session on Multi-Master Replication with MMM and thanks to the great gang at MySQL Docs (my colleagues from long ago!) I’ll be doing a MySQL University session in a few days, about the GRAPH computation engine. From talks/demos I’ve done about it so far, I’ve learnt that people love it but there are lots of interesting questions. After all, it’s a pretty new and in a way exotic thing.

MySQL University uses DimDim, an online presentation service. You’ll see slides, and hear my voice. You can also type questions in a live chat room. We actually even got desktop sharing working so a live demo is possible, we’ll see how that goes on the day (I’ll make sure to have static slides for the same also ;-)

For session details and the exact link to DimDim, see the MySQL uni page for the OQGRAPH session.

To attend, please calculate the starting time for your local timezone! It’ll be very early in the morning for US people, however for Europe it will be late morning, and Asia/Pacific will be evening. If you miss the live session, there’ll be a recording online soon afterwards and of course you can contact me for questions anyway. Still, it would be be cool if lots of people attended live, that’s always extra useful. Hope to meet you there!

Walking the Tree of Life in simple SQL

Antony and I are busy getting the Open Query GRAPH Engine code ready so you all can play with it, but we needed to test with a larger dataset to make sure all was fundamentally well with the system.

We have some intersting suitable dataset sources, but the first we tried in ernest because it was easy to get in (thanks to Roland Bouman for both the idea and providing xslt stylesheets to transform the set), was the Tree of Life which is a hierarchy of 89052 entries showing how biological species on earth are related to eachother.

GRAPH engine operates in a directed fashion, so I inserted the connections both ways resulting in 178102 entries. So, I inserted A->B as well as B->A for each connection. So we now have a real graph, not just a simple tree.

Just like with my previous post, we have a separate table that contains the name of the species. For query simplicity, I looked up the id the start/end name separately. By the way, latch=1 indicates we use Dijkstra’s shortest-path algorithm for our search.

# with all that explained, let’s find ourselves in the tree of life!
SELECT GROUP_CONCAT(name ORDER BY seq SEPARATOR ‘ -> ‘) AS path FROM tol_graph JOIN tol ON (linkid=id) WHERE latch=1 AND origid=1 AND destid=16421 \G
*************************** 1. row ***************************
path: Life on Earth -> Eukaryotes -> Unikonts -> Opisthokonts -> Animals -> Bilateria -> Deuterostomia -> Chordata -> Craniata -> Vertebrata -> Gnathostomata -> Teleostomi -> Osteichthyes -> Sarcopterygii -> Terrestrial Vertebrates -> Tetrapoda -> Reptiliomorpha -> Amniota -> Synapsida -> Eupelycosauria -> Sphenacodontia -> Sphenacodontoidea -> Therapsida -> Theriodontia -> Cynodontia -> Mammalia -> Eutheria -> Primates -> Catarrhini -> Hominidae -> Homo -> Homo sapiens
1 row in set (0.13 sec)

# how are we related to the family of plants containing the banana
SELECT GROUP_CONCAT(name ORDER BY seq SEPARATOR ‘ -> ‘) AS path FROM tol_graph JOIN tol ON (linkid=id) WHERE latch=1 AND origid=16421 AND destid=21506 \G
*************************** 1. row ***************************
path: Homo sapiens -> Homo -> Hominidae -> Catarrhini -> Primates -> Eutheria -> Mammalia -> Cynodontia -> Theriodontia -> Therapsida -> Sphenacodontoidea -> Sphenacodontia -> Eupelycosauria -> Synapsida -> Amniota -> Reptiliomorpha -> Tetrapoda -> Terrestrial Vertebrates -> Sarcopterygii -> Osteichthyes -> Teleostomi -> Gnathostomata -> Vertebrata -> Craniata -> Chordata -> Deuterostomia -> Bilateria -> Animals -> Opisthokonts -> Unikonts -> Eukaryotes -> Archaeplastida (Plantae) -> Green plants -> Streptophyta -> Embryophytes -> Spermatopsida -> Angiosperms -> Monocotyledons -> Zingiberanae -> Musaceae
1 row in set (0.06 sec)

Obviously, this search needs to find its way up the tree then find the appropriate other branch.

# finally, our connection retro-viruses
SELECT GROUP_CONCAT(name ORDER BY seq SEPARATOR ‘ -> ‘) AS path FROM tol_graph JOIN tol ON (linkid=id) WHERE latch=1 AND origid=16421 AND destid=57380 \G
*************************** 1. row ***************************
path: Homo sapiens -> Homo -> Hominidae -> Catarrhini -> Primates -> Eutheria -> Mammalia -> Cynodontia -> Theriodontia -> Therapsida -> Sphenacodontoidea -> Sphenacodontia -> Eupelycosauria -> Synapsida -> Amniota -> Reptiliomorpha -> Tetrapoda -> Terrestrial Vertebrates -> Sarcopterygii -> Osteichthyes -> Teleostomi -> Gnathostomata -> Vertebrata -> Craniata -> Chordata -> Deuterostomia -> Bilateria -> Animals -> Opisthokonts -> Unikonts -> Eukaryotes -> Life on Earth -> Viruses -> DNA-RNA Reverse Transcribing Viruses -> Retroviridae
1 row in set (0.06 sec)

As you can see this one has to walk all the way back to “life on earth”, we’re really not related at all.

I left in the lines that show the amount of time taken. In earlier queries it took a few seconds, and I thought that was just some slowness in the graph engine, until I found out that the join was un-indexed so MySQL was table-scanning the tol table for each item found. Quickly corrected, the numbers are as you see.

I was still curious though, and since the SELECT returns a single item (a string in this case) it was really easy to use the BENCHMARK(N,func) function. That standard MySQL function runs func N times. Simple.

# so, we do
SELECT benchmark(1000000,(SELECT GROUP_CONCAT(name ORDER BY seq SEPARATOR ‘ -> ‘) AS path FROM tol_tree JOIN tol ON (linkid=id) WHERE latch=1 AND origid=16421 AND destid=57380));

1 row in set (1.86 sec)

As it turns out, we were really just measuring latency before, as this shows we can do a million of these path searches through a graph in less than 2 seconds. To me, that’s not just “not bad” (the usual opinion a Dutch person would express ;-) but freaking awesome. And that is just what I wanted to tell.