Filter optimisation doesn't respect scope changes

[frensjan]

Current Behavior

While investigating the support for LATERAL, I believe I have found an issue with how filter optimisation incorrectly handles scope changes.

The following query:

PREFIX : <http://example/>
SELECT ?s ?o WHERE {
    VALUES ?s { :S }
    {
        { VALUES ?o { :O } }
        { FILTER(BOUND(?s) && !BOUND(?o)) }
    }
}

Has this as unoptimised query plan:

Projection
╠══ ProjectionElemList
║     ProjectionElem "s"
║     ProjectionElem "o"
╚══ Join
   ├── BindingSetAssignment ([[s=http://example/S]]) [left]
   └── Join (new scope) [right]
      ╠══ BindingSetAssignment ([[o=http://example/O]]) (new scope) [left]
      ╚══ Filter (new scope) [right]
         ├── And
         │  ╠══ Bound
         │  ║     Var (name=s)
         │  ╚══ Not
         │        Bound
         │           Var (name=o)
         └── SingletonSet

However, the optimised query plan is:

Join (JoinIterator)
╠══ BindingSetAssignment ([[s=http://example/S]]) (costEstimate=1, resultSizeEstimate=1) [left]
╚══ Join (JoinIterator) [right]
   ├── BindingSetAssignment ([[o=http://example/O]]) (new scope) (costEstimate=1, resultSizeEstimate=1) [left]
   └── Filter [right]
      ╠══ And
      ║  ├── Bound
      ║  │     Var (name=s)
      ║  └── Not
      ║        Bound
      ║           Var (name=o)
      ╚══ SingletonSet

Note that the Filter [right] is no longer marked as a new scope.

Expected Behavior

Optimisation may split, move and merge filters, but only within the same scope (group graph pattern).

Version

develop

Are you interested in contributing a solution yourself?

Perhaps?

Anything else?

Irrelevance without LATERAL

Note that this issue is largely irrelevant without notion of LATERAL join as the evaluation of { FILTER(BOUND(?s) && !BOUND(?o)) } (with the bottom-up evaluation semantics of SPARQL) can never yield a result as s will never be bound. The work for #4769 by @hmottestad and @JervenBolleman fixes this issue for the situation without LATERAL join. I do think this will hinder the implementation of LATERAL though.

Variable scopes are difficult

I'm wondering whether having the VariableScopeChange with it's boolean state at the QueryModelNode level is easy enough to work with when it comes to creating optimisation rules. Could perhaps having an explicit node in the algebra make this area less error prone?

E.g., the solution for #4769 at least in part was to 'fix' the scope of bindings for Filter. However, I think scoping could be tackled more generically, also 'freeing' implementations such as FilterIterator from such details.

Details of the query plan optimisation

For reference, these are intermediary query plans:

Intermediary query plans

The first relevant optimisation is performed by ConjunctiveConstraintSplitterOptimizer:

QueryRoot
   Join
      BindingSetAssignment ([[s=http://example/S]])
      Join
         BindingSetAssignment ([[o=http://example/O]]) (new scope)
         Filter (new scope)
            Bound
               Var (name=s)
            Filter
               Not
                  Bound
                     Var (name=o)
               SingletonSet

Then the FilterOrganizer in the FilterOptimizer relocates the two nested Filter as deep as possible; but reverses their nesting! The FilterMerger then merges the conditions of the two Filters into the a new Filter, ignoring the isVariableScopeChange state.

QueryRoot
   Join
      BindingSetAssignment ([[s=http://example/S]])
      Join
         BindingSetAssignment ([[o=http://example/O]]) (new scope)
         Filter
            Not
               Bound
                  Var (name=o)
            Filter (new scope)
               Bound
                  Var (name=s)
               SingletonSet