[JENA-383] The query optimizer generates a suboptimal query plan in case of nested optionals followed by a filter

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: ARQ 2.9.4
• Fix Version/s: Jena 2.11.1
• Component/s: ARQ, Optimizer
• Labels: filter nested optimization optional
• Assignee: Andy Seaborne
• Reporter: Giovanni Mels
• Created: 21/Jan/13 11:00
• Updated: 24/Dec/13 17:21
• Resolved: 24/Dec/13 17:16

Description

The query optimizer generates a suboptimal query plan in case of nested optionals followed by a filter (?var = <uri>).

The problem is similar to the problem discussed here http://markmail.org/message/zy5qx47hxfo2vdlg, except we have nested optionals in our query (There are no scope problems, all optionals are translated to conditionals). It is only the filter that is translated differently:

arq-2.8.8

(extend ((?var <uri>))
(conditional
(conditional
(conditional
(conditional
(conditional
(conditional
(bgp
...

jena-arq-2.9.4

(filter (= ?var <uri>)
(conditional
(conditional
(conditional
(conditional
(conditional
(conditional
(bgp
...

Query times went from milliseconds to over 7 minutes because of this.

I reduced the query to this test case:

PREFIX ex: <http://example.org/test#>

SELECT * WHERE {

?var ex:p1 ?x.

OPTIONAL {
?x ex:p2 ?y.

OPTIONAL

{ ?y ex:p3 ?z }

}

FILTER (?var = ex:i)
}

(filter (= ?var <http://example.org/test#i>)
(conditional
(bgp (triple ?var <http://example.org/test#p1> ?x))
(conditional
(bgp (triple ?x <http://example.org/test#p2> ?y))
(bgp (triple ?y <http://example.org/test#p3> ?z)))))

The nested OPTIONAL seems to be the problem here, removing it gives

(assign ((?var <http://example.org/test#i>))
(conditional
(bgp (triple <http://example.org/test#i> <http://example.org/test#p1> ?x))
(bgp
(triple ?x <http://example.org/test#p2> ?y)
(triple ?y <http://example.org/test#p3> ?z)
)))

This might be related to JENA-294.

Issue Links

• relates to: JENA-294 TransformFilterEquality does not handle starting OPTIONAL well
• relates to: JENA-595 Improve filter placement optimization