The SPARQL query that is created by the search function generates very slow queries. That is because the queries don't restrict the results to one graph, which can get extremely slow in some circumstances. See bug 219687 for an discussion about this (although that report is about Akonadi::ContactSearchJob being slow)
Hej Thomas, is this still valid? Ciao, Tobias
No idea. Probably those are still missing, but I haven't looked into that part a long time.