[andy_ppp]

How many joins did it have (sounds very joinery :-D)/or how deep was your graph? Presumably it was doing full table scans for everything - sounds very interesting anyway.

[atemerev]

About 1.5 million nodes (not that big), most of queries followed 3-4 edges.

Joins are good. :)