Earlier quoted context omitted.
SPARQL is PSPACE-complete. Worst case complexity and "fast in practice" aren't really the same thing at all. I suspect average case complexity for SPARQL is much better, which is backed up by several reasonably peformant implementations.
What are these reasonably performant implementations? Have you tried them with a billion edges? Also, if your data store is "fast in practice" but has worst cases that are PSPACE-complete, how do you prevent worst-case queries from DOSing it?
Well, I'm a vendor in the space so I like my implementation: http://stardog.com/ -- and yes we've "tried it" with 10s of billions of edges.
Worst cases are prevented from DOSing by having query management features like auto-killing queries that run too long, etc.