Query Planner Prematurely Does not See into Optional Joins.

[joka921]

• The Query Planner currently does not see into OPTIONAL clauses.
• OPTIONAL clauses are optimized separately from regular triples in the same GraphPattern
• most notably this discards the information which Sorting of the Optional clause and the rest of the Graph Pattern are beneficial for further processing.
• Consider the following simple example taken from QueryPlannerTest.cpp:

SELECT ?a ?b "WHERE {
   ?a <rel1> ?b . 
   OPTIONAL { ?a <rel2> ?c }
} ORDER BY ?b")

The Optimizer currently has not way to know, that reading both <rel1> and <rel2> from the PSO permutation is beneficial since it saves us a sort later on.

This could be fixed by two ways:

• Integrating the Triples in the OPTIONAL clause into the optimization of the ordinary triples. (In our previous example, the ?a <rel2> ?c could be optimized like a regular join which does never filter elements on the join column). PRO: Yields the optimal result, CON: increases the optimization effort.

• Make the GraphPattern in and outside of the OPTIONAL aware of which sorting is required to join them afterwards.

  • PRO: simpler and more similar to the current code
  • CON: It is not clear what to do, if there are multiple ways to join the different patterns together:

SELECT ?a ?b ?c ?d "WHERE {
   ?a <rel1> ?b . 
   OPTIONAL { ?a <rel2> ?c } .
   OPTIONAL { ?d <rel3> ?a} .

} ORDER BY ?b")