incubator-jena-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Rob Battle <>
Subject TransformFilterPlacement optimization
Date Wed, 26 Jan 2011 19:36:26 GMT

I have been looking at the com.hp.hpl.jena.sparql.algebra.Optimize class in order to add some
specific optimizations for BBN's Parliament [1] triple store.  I noticed that the Filter Placement
algorithm executed by the TransformFilterPlacement class does not take into account conditionals.

For instance, suppose you have the following query:
SELECT ?s ?name
  ?s :age ?age .
      ?s :name ?name .
   FILTER (?age < 20) .

Couldn't this be optimized to move the filter above the optional block?  Currently, the TransformFilterPlacement
class examines a filter's sub operation and checks to see if it is either an OpBGP, OpSequence,
or OpQuadPattern.

It seems like this could be extended to also look at the OpConditional.  For instance, the
following method will move the filter into the left side of the conditional if it applies.

   private static Op transformFilterConditional(ExprList exprs, Set<Var> varScope, OpConditional
opConditional) {
      // Any filters that depend on no variables. 
      Op op = insertAnyFilter(exprs, varScope, null) ;
      Op left = opConditional.getLeft();
      left = transform(exprs, varScope, left);
      Op right = opConditional.getRight();
      op = new OpConditional(left, right);
      op = insertAnyFilter(exprs, varScope, op);
      return op;

For the above query, the original TransformFilterPlacement class generates the following algebra

(project (?s ?name)
  (filter (< ?age 20)
      (bgp (triple ?s <> ?age))
      (bgp (triple ?s <> ?name)))))

while the modified code generates the following:

(project (?s ?name)
    (filter (< ?age 20)
      (bgp (triple ?s <> ?age)))
    (bgp (triple ?s <> ?name))))

Unless I'm mistaken, this will cause the filter to be applied before the optional is considered.
 Is there something I'm missing where this optimization is invalid?


View raw message