Generally speaking, the FILTER NOT EXISTS query is quite challenging, it requires the evaluation of a composed graph pattern for each of the outer solutions. What’s missing here for the query to run efficiently is a distinct projection on the variables that are bound outside and projected in the FILTER NOT EXISTS clause, to eliminate redundant computations. This is inline with other issues we’re currently working on; we will address these issues as part of ticket http://trac.bigdata.com/ticket/1140 in the near future.

For the meantime, here’s a proposal for rewriting the query into (as we understand) an equivalent one that should run in the subseconds range (note that the query slightly differs from your query, e.g. does not contain the filters — we’ve got a different data set running here at the moment). The key idea is to use GROUP BY and HAVING COUNT = 1 to identify statements that are referenced only once, it should be straightforward to apply to the original query:

SELECT ?s ?p ?o
WITH {
  SELECT ?ref
  WHERE {
    <http://www.wikidata.org/entity/Q30> ?statementPred ?statement .
    ?statement <http://www.w3.org/ns/prov#wasDerivedFrom> ?ref . 
  }
  GROUP BY ?ref
  HAVING (COUNT(?statement)=1)
} AS %unreferenced
WHERE {
  INCLUDE %unreferenced
  ?ref ?expandedValuePred ?s .
  ?s ?p ?o .
}

The query uses the (non-standard) SPARQL extensions “WITH”, which allows enforcing the order in which subqueries are evaluated. Once we’ve tackled the optimization, you may switch back to the original query and execute that one more efficiently.

So we actually moved to a different model of updating, now the query we use to filter out the unused entries is:

DELETE { ?s ?p ?o } WHERE {
  VALUES ?s { %values% }
  # Since values are shared we can only clear the values on them when they are no longer used
  # anywhere else.
  FILTER NOT EXISTS { ?someEntity ?someStatementPred ?s .  }
  ?s ?p ?o .
}

(with %values% being replaced by the list of actual IRIs) and it seems to perform OK so far.
We still use this construct though:

DELETE {
  ?s ?p ?o .
}
WHERE {
 <http://www.wikidata.org/entity/Q30> ?statementPred ?s .
  FILTER( STRSTARTS(STR(?s), ""http://www.wikidata.org/entity/statement/") ) .
  ?s ?p ?o .
  FILTER NOT EXISTS {
    VALUES ( ?s ?p ?o ) {
      %valueStatements%
    }
  }
}

Where %valueStatements% is a set of new triples to be introduced later with INSERT, so if old & new data have same triples they won't be deleted and then inserted back.

We'll keep an eye on it and see if we have any more trouble.

This part could be expensive. Instead of having a prefix scan, it is
scanning all statements, materializing the Object position from the
dictionary, and then checking the string representation of that URI for a
match.

http://www.wikidata.org/entity/Q30 ?statementPred ?s .
FILTER( STRSTARTS(STR(?s), ""http://www.wikidata.org/entity/statement/") ) .

We should try to make this a prefix scan on the inline IV range for
http://www.wikidata.org/entity/statement/. This will require being smarter
about pushing down filters.

I have copied Michael who has been looking at how to improve our FILTER
handling.

Thanks,
Bryan

Bryan Thompson
Chief Scientist & Founder
SYSTAP, LLC
4501 Tower Road
Greensboro, NC 27410
bryan@systap.com
http://blazegraph.com
http://blog.bigdata.com http://bigdata.com
http://mapgraph.io

Blazegraph™ http://www.blazegraph.com/ is our ultra high-performance
graph database that supports both RDF/SPARQL and Tinkerpop/Blueprints
APIs. MapGraph™ http://www.systap.com/mapgraph is our disruptive new
technology to use GPUs to accelerate data-parallel graph analytics.

CONFIDENTIALITY NOTICE: This email and its contents and attachments are
for the sole use of the intended recipient(s) and are confidential or
proprietary to SYSTAP. Any unauthorized review, use, disclosure,
dissemination or copying of this email or its contents or attachments is
prohibited. If you have received this communication in error, please notify
the sender by reply email and permanently delete all copies of the email
and its contents and attachments.

Yes, the idea behind this query is to do prefix scan/filter on the IRIs. If there's some syntax we'd be better using to achieve the same we could change this query. In general, the amount of predicates from Q30 shouldn't be _that_ high (no more that hundreds) so it may not be that big of a deal right now.

Ok. At that number this will not matter. But it is not being as efficient
as you would hope. Something to work on.

Bryan

OK, added this as a comment to http://trac.bigdata.com/ticket/1083, which deals with the issue of filter pushing.