You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jena.apache.org by an...@apache.org on 2012/08/20 15:54:52 UTC
svn commit: r1375022 - in /jena/trunk/jena-arq/src:
main/java/com/hp/hpl/jena/sparql/algebra/op/
main/java/com/hp/hpl/jena/sparql/algebra/optimize/
main/java/com/hp/hpl/jena/sparql/algebra/table/
main/java/com/hp/hpl/jena/sparql/sse/writers/ test/java/...
Author: andy
Date: Mon Aug 20 13:54:51 2012
New Revision: 1375022
URL: http://svn.apache.org/viewvc?rev=1375022&view=rev
Log:
Restructure TransformFilterEquality (prep for JENA-294; no changes)
Add case of deducing empty results.
Added:
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterEquality.java
Modified:
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/op/OpTable.java
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/Optimize.java
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/table/TableEmpty.java
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/sse/writers/WriterOp.java
jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/TestFilterTransform.java
Modified: jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/op/OpTable.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/op/OpTable.java?rev=1375022&r1=1375021&r2=1375022&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/op/OpTable.java (original)
+++ jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/op/OpTable.java Mon Aug 20 13:54:51 2012
@@ -46,7 +46,6 @@ public class OpTable extends Op0
public boolean isJoinIdentity()
{ return TableUnit.isTableUnit(table) ; }
- // One row of no bindings.
public Table getTable()
{ return table ; }
Modified: jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/Optimize.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/Optimize.java?rev=1375022&r1=1375021&r2=1375022&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/Optimize.java (original)
+++ jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/Optimize.java Mon Aug 20 13:54:51 2012
@@ -174,8 +174,8 @@ public class Optimize implements Rewrite
if ( context.isTrueOrUndef(ARQ.optFilterEquality) )
{
- boolean termStrings = context.isDefined(ARQ.optTermStrings) ;
- op = apply("Filter Equality", new TransformFilterEquality(!termStrings), op) ;
+ //boolean termStrings = context.isDefined(ARQ.optTermStrings) ;
+ op = apply("Filter Equality", new TransformFilterEquality(), op) ;
}
if ( context.isTrueOrUndef(ARQ.optFilterDisjunction) )
Added: jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterEquality.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterEquality.java?rev=1375022&view=auto
==============================================================================
--- jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterEquality.java (added)
+++ jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterEquality.java Mon Aug 20 13:54:51 2012
@@ -0,0 +1,275 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.hp.hpl.jena.sparql.algebra.optimize;
+
+import java.util.ArrayList ;
+import java.util.Collection ;
+import java.util.List ;
+import java.util.Set ;
+
+import org.openjena.atlas.lib.Pair ;
+
+import com.hp.hpl.jena.query.ARQ ;
+import com.hp.hpl.jena.sparql.ARQNotImplemented ;
+import com.hp.hpl.jena.sparql.algebra.Op ;
+import com.hp.hpl.jena.sparql.algebra.OpVars ;
+import com.hp.hpl.jena.sparql.algebra.TransformCopy ;
+import com.hp.hpl.jena.sparql.algebra.op.* ;
+import com.hp.hpl.jena.sparql.core.Substitute ;
+import com.hp.hpl.jena.sparql.core.Var ;
+import com.hp.hpl.jena.sparql.expr.* ;
+
+public class TransformFilterEquality extends TransformCopy
+{
+ public TransformFilterEquality()
+ { }
+
+ @Override
+ public Op transform(OpFilter opFilter, Op subOp)
+ {
+ Op op = apply(opFilter.getExprs(), subOp) ;
+ if ( op == null )
+ return super.transform(opFilter, subOp) ;
+ return op ;
+ }
+
+ private static Op apply(ExprList exprs, Op subOp)
+ {
+ // ---- Find and extract any equality filters.
+ Pair<List<Pair<Var, NodeValue>>, ExprList> p = preprocessFilterEquality(exprs) ;
+ if ( p == null || p.getLeft().size() == 0 )
+ return null ;
+
+ List<Pair<Var, NodeValue>> equalities = p.getLeft() ;
+ Collection<Var> varsMentioned = varsMentionedInEqualityFilters(equalities) ;
+ ExprList remaining = p.getRight() ;
+
+ // ---- Check if the subOp is the right shape to transform.
+
+
+ Op op = subOp ;
+
+ // Special case : deduce that the filter will always "eval unbound"
+ // hence elimate all rows. Return the empty table.
+
+ if ( testSpecialCaseUnused(subOp, equalities, remaining))
+ {
+ return OpTable.empty() ;
+ }
+
+
+ // Special case: the deep left op of a OpConditional/OpLeftJoin is unit table.
+ // Given the there is an equality filter, if the right does not match,
+ // the empty row will be rejected by the filter.
+ // So the bottom is in fact a normal join;
+ // and a form like "(join unit P)" is equal to P.
+ if ( testSpecialCase1(subOp, equalities, remaining))
+ op = processSpecialCase1(op, equalities) ;
+
+ // ---- Transform
+
+ if ( ! safeToTransform(varsMentioned, op) )
+ return null ;
+ for ( Pair<Var, NodeValue> equalityTest : equalities )
+ op = processFilterWorker(op, equalityTest.getLeft(), equalityTest.getRight()) ;
+
+ // ---- Place any filter expressions around the processed sub op.
+ if ( remaining.size() > 0 )
+ op = OpFilter.filter(remaining, op) ;
+ return op ;
+ }
+
+ // --- find and extract
+ private static Pair<List<Pair<Var, NodeValue>>, ExprList> preprocessFilterEquality(ExprList exprs)
+ {
+ List<Pair<Var, NodeValue>> exprsFilterEquality = new ArrayList<Pair<Var, NodeValue>>() ;
+ ExprList exprsOther = new ExprList() ;
+ for ( Expr e : exprs.getList() )
+ {
+ Pair<Var, NodeValue> p = preprocess(e) ;
+ if ( p != null )
+ exprsFilterEquality.add(p) ;
+ else
+ exprsOther.add(e) ;
+ }
+ if ( exprsFilterEquality.size() == 0 )
+ return null ;
+ return Pair.create(exprsFilterEquality, exprsOther) ;
+ }
+
+ private static Pair<Var, NodeValue> preprocess(Expr e)
+ {
+ if ( !(e instanceof E_Equals) && !(e instanceof E_SameTerm) )
+ return null ;
+
+ ExprFunction2 eq = (ExprFunction2)e ;
+ Expr left = eq.getArg1() ;
+ Expr right = eq.getArg2() ;
+
+ Var var = null ;
+ NodeValue constant = null ;
+
+ if ( left.isVariable() && right.isConstant() )
+ {
+ var = left.asVar() ;
+ constant = right.getConstant() ;
+ }
+ else if ( right.isVariable() && left.isConstant() )
+ {
+ var = right.asVar() ;
+ constant = left.getConstant() ;
+ }
+
+ if ( var == null || constant == null )
+ return null ;
+
+ // Corner case: sameTerm is false for string/plain literal,
+ // but true in the graph for graph matching.
+ if (e instanceof E_SameTerm)
+ {
+ if ( ! ARQ.isStrictMode() && constant.isString() )
+ return null ;
+ }
+
+ // Final check for "=" where a FILTER = can do value matching when the graph does not.
+ if ( e instanceof E_Equals )
+ {
+ // Value based?
+ if ( ! ARQ.isStrictMode() && constant.isLiteral() )
+ return null ;
+ }
+
+ return Pair.create(var, constant) ;
+ }
+
+ private static Collection<Var> varsMentionedInEqualityFilters(List<Pair<Var, NodeValue>> equalities)
+ {
+ List<Var> vars = new ArrayList<Var>() ;
+ for ( Pair<Var, NodeValue> p : equalities )
+ vars.add(p.getLeft()) ;
+ return vars ;
+ }
+
+ private static boolean safeToTransform(Collection<Var> varsEquality, Op op)
+ {
+ if ( op instanceof OpBGP || op instanceof OpQuadPattern )
+ return true ;
+
+ // This will be applied also in sub-calls of the Transform but queries
+ // are very rarely so deep that it matters.
+ if ( op instanceof OpSequence )
+ {
+ OpN opN = (OpN)op ;
+ for ( Op subOp : opN.getElements() )
+ {
+ if ( ! safeToTransform(varsEquality, subOp) )
+ return false ;
+ }
+ return true ;
+ }
+
+ if ( op instanceof OpJoin || op instanceof OpUnion)
+ {
+ Op2 op2 = (Op2)op ;
+ return safeToTransform(varsEquality, op2.getLeft()) && safeToTransform(varsEquality, op2.getRight()) ;
+ }
+
+ // Not safe unless filter variables are mentioned on the LHS.
+ if ( op instanceof OpConditional || op instanceof OpLeftJoin )
+ {
+ Op2 opleftjoin = (Op2)op ;
+
+ if ( ! safeToTransform(varsEquality, opleftjoin.getLeft()) ||
+ ! safeToTransform(varsEquality, opleftjoin.getRight()) )
+ return false ;
+
+ // Not only must the left and right be safe to transform,
+ // but the equality variable must be known to be always set.
+
+ // If the varsLeft are disjoint from assigned vars,
+ // we may be able to push assign down right
+ // (this generalises the unit table case specialcase1)
+ // Needs more investigation.
+
+ Op opLeft = opleftjoin.getLeft() ;
+ Set<Var> varsLeft = OpVars.patternVars(opLeft) ;
+ if ( varsLeft.containsAll(varsEquality) )
+ return true ;
+ return false ;
+ }
+
+ if ( op instanceof OpGraph )
+ {
+ OpGraph opg = (OpGraph)op ;
+ return safeToTransform(varsEquality, opg.getSubOp()) ;
+ }
+
+ return false ;
+ }
+
+ // -- A special case
+ // If a sequence of OPTIONALS, and nothing prior to the first, we end up with
+ // a unit table on the left sid of a next of LeftJoin/conditionals.
+
+ private static boolean testSpecialCaseUnused(Op op, List<Pair<Var, NodeValue>> equalities, ExprList remaining)
+ {
+ // If the op does not contain the var at all, for some equality
+ // then the filter expression wil/ be "eval unbound" i.e. false.
+ // We can return empty table.
+ Set<Var> patternVars = OpVars.patternVars(op) ;
+ for ( Pair<Var, NodeValue> p : equalities )
+ {
+ if ( ! patternVars.contains(p.getLeft()))
+ return true ;
+ }
+ return false ;
+ }
+
+ private static boolean testSpecialCase1(Op op, List<Pair<Var, NodeValue>> equalities , ExprList remaining )
+ {
+ return false ;
+ }
+
+ private static Op processSpecialCase1(Op op, List<Pair<Var, NodeValue>> equalities)
+ {
+ throw new ARQNotImplemented() ;
+ }
+
+ // ---- Transformation
+
+ private static Op processFilterWorker(Op op, Var var, NodeValue constant)
+ {
+ return subst(op, var, constant) ;
+ }
+
+ private static Op subst(Op subOp , Var var, NodeValue nv)
+ {
+ Op op = Substitute.substitute(subOp, var, nv.asNode()) ;
+ return OpAssign.assign(op, var, nv) ;
+ }
+
+ // Helper for TransformFilterDisjunction.
+
+ /** Apply the FilterEquality transform or return null if no change */
+
+ static Op processFilter(Expr e, Op subOp)
+ {
+ return apply(new ExprList(e), subOp) ;
+ }
+}
Modified: jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/table/TableEmpty.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/table/TableEmpty.java?rev=1375022&r1=1375021&r2=1375022&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/table/TableEmpty.java (original)
+++ jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/table/TableEmpty.java Mon Aug 20 13:54:51 2012
@@ -71,5 +71,4 @@ public class TableEmpty extends TableBas
public int size() { return 0 ; }
@Override
public boolean isEmpty() { return true ; }
-
}
Modified: jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/sse/writers/WriterOp.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/sse/writers/WriterOp.java?rev=1375022&r1=1375021&r2=1375022&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/sse/writers/WriterOp.java (original)
+++ jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/sse/writers/WriterOp.java Mon Aug 20 13:54:51 2012
@@ -34,15 +34,9 @@ import com.hp.hpl.jena.sparql.algebra.Op
import com.hp.hpl.jena.sparql.algebra.OpVisitor ;
import com.hp.hpl.jena.sparql.algebra.op.* ;
import com.hp.hpl.jena.sparql.algebra.table.TableUnit ;
-import com.hp.hpl.jena.sparql.core.BasicPattern ;
-import com.hp.hpl.jena.sparql.core.Prologue ;
-import com.hp.hpl.jena.sparql.core.Quad ;
-import com.hp.hpl.jena.sparql.core.QuadPattern ;
-import com.hp.hpl.jena.sparql.core.TriplePath ;
-import com.hp.hpl.jena.sparql.core.Var ;
-import com.hp.hpl.jena.sparql.core.VarExprList ;
-import com.hp.hpl.jena.sparql.expr.ExprAggregator ;
+import com.hp.hpl.jena.sparql.core.* ;
import com.hp.hpl.jena.sparql.expr.Expr ;
+import com.hp.hpl.jena.sparql.expr.ExprAggregator ;
import com.hp.hpl.jena.sparql.expr.ExprList ;
import com.hp.hpl.jena.sparql.pfunction.PropFuncArg ;
import com.hp.hpl.jena.sparql.serializer.SerializationContext ;
@@ -365,6 +359,14 @@ public class WriterOp
return ;
}
+ if ( opTable.getTable().isEmpty() )
+ {
+ start(opTable, NoNL) ;
+ out.print("empty") ;
+ finish(opTable) ;
+ return ;
+ }
+
start(opTable, NoNL) ;
WriterNode.outputVars(out, opTable.getTable().getVars(), sContext) ;
out.println() ;
Modified: jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/TestFilterTransform.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/TestFilterTransform.java?rev=1375022&r1=1375021&r2=1375022&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/TestFilterTransform.java (original)
+++ jena/trunk/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/TestFilterTransform.java Mon Aug 20 13:54:51 2012
@@ -38,7 +38,7 @@ public class TestFilterTransform
return new JUnit4TestAdapter(TestFilterTransform.class) ;
}
- private Transform t_equality = new TransformFilterEquality(false) ;
+ private Transform t_equality = new TransformFilterEquality() ;
private Transform t_disjunction = new TransformFilterDisjunction() ;
private Transform t_placement = new TransformFilterPlacement() ;
private Transform t_expandOneOf = new TransformExpandOneOf() ;
@@ -71,17 +71,18 @@ public class TestFilterTransform
// Unused
test("(filter (= ?UNUSED <x>) (bgp ( ?s ?p ?x)) )",
t_equality,
- (String[])null) ;
+ "(table empty)") ;
}
@Test public void equality05()
{
- // Can't optimize if filter does not only cover vars in LHS
- test("(filter (= ?UNUSED <x>) (conditional (bgp ( ?s ?p ?x)) (bgp ( ?s ?p ?x))))",
+ // Can't optimize if filter does not cover vars in LHS
+ test("(filter (= ?x2 <x>) (conditional (bgp ( ?s1 ?p1 ?x1)) (bgp ( ?s2 ?p2 ?x2))))",
t_equality,
- "(filter (= ?UNUSED <x>) (conditional (bgp ( ?s ?p ?x)) (bgp ( ?s ?p ?x))))") ;
+ "(filter (= ?x2 <x>) (conditional (bgp ( ?s1 ?p1 ?x1)) (bgp ( ?s2 ?p2 ?x2))))") ;
}
+
@Test public void equality06()
{
test("(filter (= ?x <x>) (conditional (bgp ( ?s ?p ?x)) (bgp ( ?s ?p ?x))))",
@@ -105,10 +106,10 @@ public class TestFilterTransform
@Test public void equality09()
{
- // Can't optimize if filter does not only cover vars in LHS
- test("(filter (= ?UNUSED <x>) (leftjoin (bgp ( ?s ?p ?x)) (bgp ( ?s ?p ?x))))",
+ // Can't optimize if filter does not cover vars in LHS
+ test("(filter (= ?x2 <x>) (leftjoin (bgp ( ?s1 ?p1 ?x1)) (bgp ( ?s2 ?p2 ?x2))))",
t_equality,
- "(filter (= ?UNUSED <x>) (leftjoin (bgp ( ?s ?p ?x)) (bgp ( ?s ?p ?x))))") ;
+ "(filter (= ?x2 <x>) (leftjoin (bgp ( ?s1 ?p1 ?x1)) (bgp ( ?s2 ?p2 ?x2))))") ;
}
@Test public void equality10()