[JENA-779] Filter placement should be able to break up extend

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: Jena 2.12.0
• Fix Version/s: Jena 2.12.1
• Component/s: ARQ, Optimizer
• Assignee: Andy Seaborne
• Reporter: Rob Vesse
• Created: 09/Sep/14 09:04
• Updated: 07/Jul/15 12:54
• Resolved: 12/Sep/14 16:48

Description

The following query demonstrates a query plan seen internally which is considered sub-optimal.

Consider the following query:

SELECT DISTINCT ?domainName
{
  { ?uri ?p ?o }
  UNION
  {
    ?sub ?p ?uri
    FILTER(isIRI(?uri))
  }
  BIND(str(?uri) as ?s)
  FILTER(STRSTARTS(?s, "http://"))
  BIND(IRI(CONCAT("http://", STRBEFORE(SUBSTR(?s,8), "/"))) AS ?domainName)
}

Which ARQ optimises as follows:

(distinct
  (project (?domainName)
    (filter (strstarts ?s "http://")
      (extend ((?s (str ?uri)) (?domainName (iri (concat "http://" (strbefore (substr ?s 8) "/")))))
        (union
          (bgp (triple ?uri ?p ?o))
          (filter (isIRI ?uri)
            (bgp (triple ?sub ?p ?uri))))))))

Which makes the query engine do a lot of work because it computes the both the BIND expressions for lots of possible solutions that will then be rejected when for many of them it would only be necessary to compute the first simple BIND function.

It would be better if the query was planned as follows:

(distinct
  (project (?domainName)
    (extend (?domainName (iri (concat "http://" (strbefore (substr ?s 8) "/"))))
      (filter (strstarts ?s "http://")
        (extend (?s (str ?uri))
          (union
            (bgp (triple ?uri ?p ?o))
            (filter (isIRI ?uri)
              (bgp (triple ?sub ?p ?uri)))))))))

Essentially when we try to push a filter through an extend if we determine that we cannot push it through the extend we should see if we can split the extend instead thus resulting in a partial pushing.

Note that a user can re-write the original query to yield this plan if they make the second BIND a project expression like so:

SELECT DISTINCT (IRI(CONCAT("http://", STRBEFORE(SUBSTR(?s,8), "/"))) AS ?domainName)
{
  { ?uri ?p ?o }
  UNION
  {
    ?sub ?p ?uri
    FILTER(isIRI(?uri))
  }
  BIND(str(?uri) as ?s)
  FILTER(STRSTARTS(?s, "http://"))
}

Issue Links

• relates to: JENA-780 Single use extend expressions could be substituted directly for their later usage
• relates to: JENA-783 qparse detects inconsistency on multiple BIND separated by {}