[JENA-709] Index join strategy may need to be more conservative when some sequence elements are potentially expensive

• Type: Brainstorming
• Status: Closed
• Priority: Minor
• Resolution: Not A Problem
• Affects Version/s: Jena 2.11.1
• Fix Version/s: Jena 2.11.2
• Component/s: ARQ, Optimizer
• Assignee: Unassigned
• Reporter: Rob Vesse
• Created: 04/Jun/14 09:04
• Updated: 10/Jun/14 12:51
• Resolved: 04/Jun/14 14:57

Description

As noted in a discussion of a poorly performing query on a mailing list thread (http://s.apache.org/cAn) there are cases where the introduction of sequence can actually make the query slower when some elements in the sequence are expensive to calculate e.g. sub-queries

The example query given is:

SELECT DISTINCT ?O ?T  ?E
WHERE
{  
  ?E a x:E. 
  {
    SELECT ?O ?T 
    WHERE 
    {
      ?O :oE ?E ;
            :oT ?T .
    } 
    ORDER BY DESC(?T)
    LIMIT 3
  }
}

Which produces the following algebra:

(distinct
 (project (?O ?T ?E)
  (sequence
   (bgp (triple ?E rdf:type x:E))
   (project (?O ?T)
    (top (3 (desc ?T))
     (bgp
      (triple ?O :oE ?/E)
      (triple ?O :oT ?T)
     ))))))

Because there are no common variables due to scoping the substitution of the bindings from the first sequence element into the sub-query has no effect so the expensive sub-query (note the top operator) gets executed in full for every single LHS solution

It is unclear from the discussion thread so far if this is just a badly written query and we don't have an example dataset that demonstrates the performance problems but just looking at the algebra it seems like we would be better avoiding use of sequence in favour of a plain join in a case like this

Issue Links

• is duplicated by: JENA-711 LIMIT on inner query incorrectly applied to outer query
• is related to: JENA-633 optimizer sequences instead of joins / subqueries with limits project more results than they should