I couldn't find a way to comment on Benjamins post, so I've stuck it here:

What indexing are you using? My tagtriples store schema is basically a table with 4 ids which joins to an (ID,String) table. When it used to be an RDF store this held both literals and URIs.

I found the key to getting good performance with this arrangement was ensuring that the mysql query engine had enough optimised btree indexes to make a good guess at query execution order. I eventually went for 6 compound indexes on the triples table (ignore the seperate graphs table - I ditched this soon after).

Hope this helps (and sorry if I'm mis-assuming something or have mis-understood the problem)