Update queries performance problem with MINUS operators

[AlyHdr]

When executing long update queries that contains MINUS operator a performance issue is noticed, where such queries perform so poorly compared to running the same queries without the MINUS.

Here's one of the queries being executed (truncated with the MINUS part longer):

DELETE {
  ?s ?p ?o .
}
 WHERE {
  VALUES ?entity {
     <https://linkedopendata.eu/entity/Q2605861> <https://linkedopendata.eu/entity/Q2549773> <https://linkedopendata.eu/entity/Q136> <https://linkedopendata.eu/entity/Q2616388> <https://linkedopendata.eu/entity/Q2651539> <https://linkedopendata.eu/entity/Q2557122> <https://linkedopendata.eu/entity/Q2738805> <https://linkedopendata.eu/entity/Q2603812> <https://linkedopendata.eu/entity/Q2584> <https://linkedopendata.eu/entity/Q8988> <https://linkedopendata.eu/entity/Q2650084> <https://linkedopendata.eu/entity/Q2570> <https://linkedopendata.eu/entity/Q2563291> <https://linkedopendata.eu/entity/Q2573576> <https://linkedopendata.eu/entity/Q240339> <https://linkedopendata.eu/entity/Q4551> <https://linkedopendata.eu/entity/Q236714> <https://linkedopendata.eu/entity/Q2643393> <https://linkedopendata.eu/entity/Q6193> <https://linkedopendata.eu/entity/Q2643177> <https://linkedopendata.eu/entity/Q2576426> <https://linkedopendata.eu/entity/Q2502380> <https://linkedopendata.eu/entity/Q16> <https://linkedopendata.eu/entity/Q1048> <https://linkedopendata.eu/entity/Q4557> <https://linkedopendata.eu/entity/Q5866> <https://linkedopendata.eu/entity/Q2650897>
  
  }
    ?s <http://schema.org/about> ?entity .
  ?s ?p ?o    .
  MINUS {
    VALUES ( ?s ?p ?o ) {
      ( <https://ro.wikipedia.org/wiki/New_York_(ora%C8%99)> <http://schema.org/name> "New York (ora?)"@ro )
( <https://lv.wikipedia.org/wiki/Futbols> <http://schema.org/about> <https://linkedopendata.eu/entity/Q8988> )
( <https://hu.wikipedia.org/wiki/Andrzej_Duda> <http://schema.org/isPartOf> <https://hu.wikipedia.org/> )
( <https://hu.wikipedia.org/wiki/Hiiumaa_(megye)> <http://schema.org/isPartOf> <https://hu.wikipedia.org/> )
( <https://pl.wikipedia.org/wiki/Austro-W%C4%99gry> <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://schema.org/Article> )
( <https://sk.wikipedia.org/wiki/Vladimir_Vladimirovi%C4%8D_Putin> <http://schema.org/name> "Vladimir Vladimirovi? Putin"@sk )
.
.
.
.
.
    }
  }
}

It could be that this operator to exclude the triples is not well optimized, by looking at the iterator SPARQLMinusIteration https://github.com/eclipse/rdf4j/blob/e3548a79f754361695283acf9fe752b37071c186/core/queryalgebra/evaluation/src/main/java/org/eclipse/rdf4j/query/algebra/evaluation/iterator/SPARQLMinusIteration.java#L81

It appears that for every given binding set there is a loop which in theory could be a quadratic complexity, and this could be optimised by using a hashset to store all the triples to be excluded and for every given binding set we can check if it has to be excluded in constant time and not linear.

[abrokenjester]

It appears that for every given binding set there is a loop which in theory could be a quadratic complexity and this could be optimised by using a hashset to store all the triples to be excluded and for every given binding set we can check if it has to be excluded in constant time and not linear.

I am a little confused about what you're proposing. The bindingsets to be excluded are internally cached (that's the excludeSet field), which seems to be precisely the solution to the perceived performance issue you're proposing.

[abrokenjester]

Instead one would like to check if it is compatible by checking that the object is a key of the set excludeSet.

That would only work if we could guarantee that the incoming bindingsets are typically equal to the bindingsets in the exclude set, but this is not something that is generally true: the left-hand side of the minus may be binding many more (or fewer) variables than are bound in the exclude set, so an equality check would fail.

[hmottestad]

There are probably a few things that could be optimise for common cases.

If we assume that the binding names in the exclude set are typically homogeneous, then we could build an excludeSetBindingNames set so we can optimise !sharedBindingNames.isEmpty(), but we would still have to double check unless all the binding sets in the excluded set use the exact same binding names.

I also think that Set<String> makeSet(Set<String> set) could either be removed or optimised to check if the set is already some form of hash set.

QueryResults.bindingSetsCompatible(excluded, object) creates its own shared binding names set, since we already have one we could probably reuse that in some way.

As for a general optimisation. What we are looking for is a binding set in the exclude set, where for every matching binding name the values have to be the same. So if we could look up bindings in the exclude set based on a binding name + value, then we would have fewer binding sets to compare.

Maybe we could make Map<String, Map<Value, BindingSet>> bindingNameToValueToBindingSet so we can loop through binding names in the object (the accept method argument), for each binding name look up the binding sets that have the same value, then calculate the intersection and see if we have any matching binding sets.

For this last optimisation here I'm not sure how it handles shared or not shared binding names, or possible null values.

[D063520]

Hi,

thank you @jeenbroekstra and @hmottestad. I was not aware of the full SPARQL syntax here, I though that the variable names in the left and right part of the MINUS need to correspond.

Maybe some comments regarding the points raised by @hmottestad:

QueryResults.bindingSetsCompatible(excluded, object) creates its own shared binding names set, since we already have one we could probably reuse that in some way.

I agree, we also noticed this.

Maybe we could make Map<String, Map<Value, BindingSet>> bindingNameToValueToBindingSet so we can loop through binding names in the object (the accept method argument), for each binding name look up the binding sets that have the same value, then calculate the intersection and see if we have any matching binding sets.

I'm not sure if I correctly understand it, but maybe I have a counter example

select * where {
  values( ?s) {
    ( <https://linkedopendata.eu/entity/S1>  )
    ( <https://linkedopendata.eu/entity/S2>  )
   }  
  MINUS {
    VALUES (?s ?p){
        ( <https://linkedopendata.eu/entity/S1> <https://linkedopendata.eu/entity/P4>)
        ( <https://linkedopendata.eu/entity/S3> <https://linkedopendata.eu/entity/P4>)
    }
    }
  }

The question is how to make the lookup? The excluded set has to be prepared for fast lookups.

We thought a while over it and we come up with this. It is based on the following assumption.
ASSUMPTION: both the left and right hand are homogenous (i.e. the variables stay the same for the left as well as for the right part (the list can be different for the left and the right part)). (My guess is that in real world 90% of the queries are like this)

1. we check that the excludedSet is homogenous, if not we use the current strategy
2. we make the intersection between the variables in the first object and the excludedSet, which we call sharedBindingNames
3. We prepare the excludedSet for fast access on the sharedBindingNames variables
4. when the next object arrives we check that the intersection between the variables and the excludedSet is the sharedBindingNames. If not we fall back on the current strategy. (This case means that the left hand of the MINUS is not homogeneus)

This would make the MINUS for homogenous variables considerably faster and there should be a reasonable overhead when this is not the case. What do you think?

We will share some metrics showing how we run in this issue ....

[AlyHdr]

Here are some metrics where we compare the performance against blazegraph which succeeds to run those complex queries in a much shorter amount of time. There is around 35 million triples in the store and if you want I could provide the queries, I didn't want to paste them here because they are extremely long.

P.S: both stores were running on a PC with 16GB of RAM.

	rdf4j - native	blazegraph - wikibase
query 1 (bigger)	5m 3.55s	6.20s
query 2	1m 0.96s	5.43s

[abrokenjester]

I like the idea (mind you I've only thought about it for a few minutes, but it makes sense to me).

Would you both be interested in doing a proof of concept and if all looks well, perhaps even post a PR with an improvement?