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 2014/04/21 18:06:12 UTC
svn commit: r1588912 - in
/jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena: query/ARQ.java
sparql/algebra/optimize/Optimize.java
sparql/algebra/optimize/TransformFilterPlacementConservative.java
Author: andy
Date: Mon Apr 21 16:06:12 2014
New Revision: 1588912
URL: http://svn.apache.org/r1588912
Log:
JENA-681 : Put back the original filter placement code as TransformFilterPlacementConservative.
Alternative filter placement transformation.
Not used by default.
Added:
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterPlacementConservative.java (with props)
Modified:
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/query/ARQ.java
jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/Optimize.java
Modified: jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/query/ARQ.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/query/ARQ.java?rev=1588912&r1=1588911&r2=1588912&view=diff
==============================================================================
--- jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/query/ARQ.java (original)
+++ jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/query/ARQ.java Mon Apr 21 16:06:12 2014
@@ -285,6 +285,15 @@ public class ARQ
* Default is "true" - filter placement is pushed into BGPs.
*/
public static final Symbol optFilterPlacementBGP = ARQConstants.allocSymbol("optFilterPlacementBGP") ;
+
+ /**
+ * Context key controlling whether the main query engine moves filters to the "best" place using
+ * the more limited and conservative strategy which does not place as many filters
+ * Must be explicitly set "true" to operate.
+ * Filter placement, via {@linkplain #optFilterPlacement} must also be active (which it is by default).
+ * @see #optFilterPlacement
+ */
+ public static final Symbol optFilterPlacementConservative = ARQConstants.allocSymbol("optFilterPlacementConservative") ;
/**
* Context key controlling whether an ORDER BY-LIMIT query is done avoiding total sort using an heap.
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=1588912&r1=1588911&r2=1588912&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 Apr 21 16:06:12 2014
@@ -211,11 +211,15 @@ public class Optimize implements Rewrite
// of a filter in a (sequence) from each half of a (join). This is harmless,
// because filters are generally cheap, but it looks a bit bad.
if ( context.isTrueOrUndef(ARQ.optFilterPlacement) ) {
- // Whether to push into BGPs
- boolean b = context.isTrueOrUndef(ARQ.optFilterPlacementBGP) ;
- op = apply("Filter Placement", new TransformFilterPlacement(b), op) ;
+ if ( context.isTrue(ARQ.optFilterPlacementConservative))
+ op = apply("Filter Placement (conservative)", new TransformFilterPlacementConservative(), op) ;
+ else {
+ // Whether to push into BGPs
+ boolean b = context.isTrueOrUndef(ARQ.optFilterPlacementBGP) ;
+ op = apply("Filter Placement", new TransformFilterPlacement(b), op) ;
+ }
}
-
+
// Replace suitable FILTER(?x = TERM) with (assign) and write the TERm for ?x in the pattern.
// Apply (possible a second time) after FILTER placement as it can create new possibilities.
// See JENA-616.
Added: jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterPlacementConservative.java
URL: http://svn.apache.org/viewvc/jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterPlacementConservative.java?rev=1588912&view=auto
==============================================================================
--- jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterPlacementConservative.java (added)
+++ jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterPlacementConservative.java Mon Apr 21 16:06:12 2014
@@ -0,0 +1,306 @@
+/*
+ * 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.
+ */
+
+/* Contains code submitted in email to jena-user@incubator.apache.org
+ * so software grant and relicensed under the Apache Software License.
+ * transformFilterConditional
+ */
+
+package com.hp.hpl.jena.sparql.algebra.optimize;
+
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Set;
+
+import com.hp.hpl.jena.graph.Node;
+import com.hp.hpl.jena.graph.Triple;
+import com.hp.hpl.jena.query.ARQ;
+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.OpBGP;
+import com.hp.hpl.jena.sparql.algebra.op.OpConditional;
+import com.hp.hpl.jena.sparql.algebra.op.OpFilter;
+import com.hp.hpl.jena.sparql.algebra.op.OpQuadPattern;
+import com.hp.hpl.jena.sparql.algebra.op.OpSequence;
+import com.hp.hpl.jena.sparql.algebra.op.OpTable;
+import com.hp.hpl.jena.sparql.core.BasicPattern;
+import com.hp.hpl.jena.sparql.core.Var;
+import com.hp.hpl.jena.sparql.expr.Expr;
+import com.hp.hpl.jena.sparql.expr.ExprList;
+import com.hp.hpl.jena.sparql.util.VarUtils;
+
+/**
+ * Rewrite an algebra expression to put filters as close to their bound
+ * variables in a BGP. Works on (filter (BGP ...) )
+ * <p>
+ * This is a conservative and relatively limited optimization and has been
+ * superseded in the default optimizer by the {@link TransformFilterPlacement}
+ * as of the 2.11.x releases. This original version of TransformFilterPlacement
+ * only operates on filters over BGPs, quad blocks, sequences and conditions
+ * (a form of LeftJoin with no scope issues) of the same.
+ * However in some cases it may be desirable to have
+ * the more limited and conservative behaviour so this is preserved in the code
+ * for those who want to use this.
+ * </p>
+ * <p>
+ * The context flag {@link ARQ#optFilterPlacementConservative} may be set to
+ * have the default optimizer use this in place of the newer and more aggressive
+ * {@link TransformFilterPlacement}
+ * </p>
+ */
+
+public class TransformFilterPlacementConservative extends TransformCopy {
+
+ public TransformFilterPlacementConservative( ) {}
+
+ // Original helper statics.
+ // Removed because this is not the best TransformFilterPlacement to use.
+// public static Op transform(ExprList exprs, BasicPattern bgp) {
+// if (!doFilterPlacement)
+// return OpFilter.filter(exprs, new OpBGP(bgp));
+// // Mutated
+// ExprList exprs2 = ExprList.copy(exprs);
+// Op op = transformFilterBGP(exprs2, new HashSet<Var>(), bgp);
+// // Remaining filters? e.g. ones mentioning var s not used anywhere.
+// op = buildFilter(exprs2, op);
+// return op;
+// }
+//
+// public static Op transform(ExprList exprs, Node graphNode, BasicPattern bgp) {
+// if (!doFilterPlacement)
+// return OpFilter.filter(exprs, new OpQuadPattern(graphNode, bgp));
+// // Mutated
+// ExprList exprs2 = ExprList.copy(exprs);
+// Op op = transformFilterQuadPattern(exprs2, new HashSet<Var>(), graphNode, bgp);
+// op = buildFilter(exprs2, op);
+// return op;
+// }
+
+ @Override
+ public Op transform(OpFilter opFilter, Op x) {
+ // Destructive use of exprs - copy it.
+ ExprList exprs = ExprList.copy(opFilter.getExprs());
+ Set<Var> varsScope = new HashSet<Var>();
+
+ Op op = transform(exprs, varsScope, x);
+ if (op == x)
+ // Didn't do anything.
+ return super.transform(opFilter, x);
+
+ // Remaining exprs
+ op = buildFilter(exprs, op);
+ return op;
+ }
+
+ private static Op transform(ExprList exprs, Set<Var> varsScope, Op x) {
+ // OpAssign/OpExtend could be done if the assignment and exprs are
+ // independent.
+ // Dispatch by visitor??
+ if (x instanceof OpBGP)
+ return transformFilterBGP(exprs, varsScope, (OpBGP) x);
+
+ if (x instanceof OpSequence)
+ return transformFilterSequence(exprs, varsScope, (OpSequence) x);
+
+ if (x instanceof OpQuadPattern)
+ return transformFilterQuadPattern(exprs, varsScope, (OpQuadPattern) x);
+
+ if (x instanceof OpSequence)
+ return transformFilterSequence(exprs, varsScope, (OpSequence) x);
+
+ if (x instanceof OpConditional)
+ return transformFilterConditional(exprs, varsScope, (OpConditional) x);
+
+ // Not special - advance the variable scope tracking.
+ OpVars.visibleVars(x, varsScope);
+ return x;
+ }
+
+ // == The transformFilter* modify the exprs and patternVarsScope arguments
+
+ private static Op transformFilterBGP(ExprList exprs, Set<Var> patternVarsScope, OpBGP x) {
+ return transformFilterBGP(exprs, patternVarsScope, x.getPattern());
+ }
+
+ // Mutates exprs
+ private static Op transformFilterBGP(ExprList exprs, Set<Var> patternVarsScope, BasicPattern pattern) {
+ // Any filters that depend on no variables.
+ Op op = insertAnyFilter(exprs, patternVarsScope, null);
+
+ for (Triple triple : pattern) {
+ OpBGP opBGP = getBGP(op);
+ if (opBGP == null) {
+ // Last thing was not a BGP (so it likely to be a filter)
+ // Need to pass the results from that into the next triple.
+ // Which is a join and sequence is a special case of join
+ // which always evaluates by passing results of the early
+ // part into the next element of the sequence.
+
+ opBGP = new OpBGP();
+ op = OpSequence.create(op, opBGP);
+ }
+
+ opBGP.getPattern().add(triple);
+ // Update variables in scope.
+ VarUtils.addVarsFromTriple(patternVarsScope, triple);
+
+ // Attempt to place any filters
+ op = insertAnyFilter(exprs, patternVarsScope, op);
+ }
+ // Leave any remaining filter expressions - don't wrap up any as
+ // something else may take them.
+ return op;
+ }
+
+ /** Find the current OpBGP, or return null. */
+ private static OpBGP getBGP(Op op) {
+ if (op instanceof OpBGP)
+ return (OpBGP) op;
+
+ if (op instanceof OpSequence) {
+ // Is last in OpSequence an BGP?
+ OpSequence opSeq = (OpSequence) op;
+ List<Op> x = opSeq.getElements();
+ if (x.size() > 0) {
+ Op opTop = x.get(x.size() - 1);
+ if (opTop instanceof OpBGP)
+ return (OpBGP) opTop;
+ // Drop through
+ }
+ }
+ // Can't find.
+ return null;
+ }
+
+ private static Op transformFilterQuadPattern(ExprList exprs, Set<Var> patternVarsScope, OpQuadPattern pattern) {
+ return transformFilterQuadPattern(exprs, patternVarsScope, pattern.getGraphNode(), pattern.getBasicPattern());
+ }
+
+ private static Op transformFilterQuadPattern(ExprList exprs, Set<Var> patternVarsScope, Node graphNode, BasicPattern pattern) {
+ // Any filters that depend on no variables.
+ Op op = insertAnyFilter(exprs, patternVarsScope, null);
+ if (Var.isVar(graphNode)) {
+ // Add in the graph node of the quad block.
+ // It's picked up after the first triple is processed.
+ VarUtils.addVar(patternVarsScope, Var.alloc(graphNode));
+ }
+
+ for (Triple triple : pattern) {
+ OpQuadPattern opQuad = getQuads(op);
+ if (opQuad == null) {
+ opQuad = new OpQuadPattern(graphNode, new BasicPattern());
+ op = OpSequence.create(op, opQuad);
+ }
+
+ opQuad.getBasicPattern().add(triple);
+ // Update variables in scope.
+ VarUtils.addVarsFromTriple(patternVarsScope, triple);
+
+ // Attempt to place any filters
+ op = insertAnyFilter(exprs, patternVarsScope, op);
+ }
+
+ return op;
+ }
+
+ /** Find the current OpQuadPattern, or return null. */
+ private static OpQuadPattern getQuads(Op op) {
+ if (op instanceof OpQuadPattern)
+ return (OpQuadPattern) op;
+
+ if (op instanceof OpSequence) {
+ // Is last in OpSequence an BGP?
+ OpSequence opSeq = (OpSequence) op;
+ List<Op> x = opSeq.getElements();
+ if (x.size() > 0) {
+ Op opTop = x.get(x.size() - 1);
+ if (opTop instanceof OpQuadPattern)
+ return (OpQuadPattern) opTop;
+ // Drop through
+ }
+ }
+ // Can't find.
+ return null;
+ }
+
+ private static Op transformFilterSequence(ExprList exprs, Set<Var> varScope, OpSequence opSequence) {
+ List<Op> ops = opSequence.getElements();
+
+ // Any filters that depend on no variables.
+ Op op = insertAnyFilter(exprs, varScope, null);
+
+ for (Iterator<Op> iter = ops.iterator(); iter.hasNext();) {
+ Op seqElt = iter.next();
+ // Process the sequence element. This may insert filters (sequence
+ // or BGP)
+ seqElt = transform(exprs, varScope, seqElt);
+ // Merge into sequence.
+ op = OpSequence.create(op, seqElt);
+ // Place any filters now ready.
+ op = insertAnyFilter(exprs, varScope, op);
+ }
+ return op;
+ }
+
+ // Modularize.
+ 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;
+ }
+
+ // ---- Utilities
+
+ /** For any expression now in scope, wrap the op with a filter */
+ private static Op insertAnyFilter(ExprList exprs, Set<Var> patternVarsScope, Op op) {
+ for (Iterator<Expr> iter = exprs.iterator(); iter.hasNext();) {
+ Expr expr = iter.next();
+ // Cache
+ Set<Var> exprVars = expr.getVarsMentioned();
+ if (patternVarsScope.containsAll(exprVars)) {
+ if (op == null)
+ op = OpTable.unit();
+ op = OpFilter.filter(expr, op);
+ iter.remove();
+ }
+ }
+ return op;
+ }
+
+ /** Place expressions around an Op */
+ private static Op buildFilter(ExprList exprs, Op op) {
+ if (exprs.isEmpty())
+ return op;
+
+ for (Iterator<Expr> iter = exprs.iterator(); iter.hasNext();) {
+ Expr expr = iter.next();
+ if (op == null)
+ op = OpTable.unit();
+ op = OpFilter.filter(expr, op);
+ iter.remove();
+ }
+ return op;
+ }
+}
Propchange: jena/trunk/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformFilterPlacementConservative.java
------------------------------------------------------------------------------
svn:mime-type = text/plain