Return-Path: X-Original-To: apmail-marmotta-commits-archive@minotaur.apache.org Delivered-To: apmail-marmotta-commits-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 112D211C4C for ; Thu, 18 Sep 2014 15:16:49 +0000 (UTC) Received: (qmail 63903 invoked by uid 500); 18 Sep 2014 15:16:48 -0000 Delivered-To: apmail-marmotta-commits-archive@marmotta.apache.org Received: (qmail 63873 invoked by uid 500); 18 Sep 2014 15:16:48 -0000 Mailing-List: contact commits-help@marmotta.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@marmotta.apache.org Delivered-To: mailing list commits@marmotta.apache.org Received: (qmail 63864 invoked by uid 99); 18 Sep 2014 15:16:48 -0000 Received: from tyr.zones.apache.org (HELO tyr.zones.apache.org) (140.211.11.114) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 18 Sep 2014 15:16:48 +0000 Received: by tyr.zones.apache.org (Postfix, from userid 65534) id 6CBEFA1B1D3; Thu, 18 Sep 2014 15:16:48 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: sschaffert@apache.org To: commits@marmotta.apache.org Message-Id: <5fa635545be44117b3fe1b97244d46e6@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: git commit: improved support for subqueries (MARMOTTA-540) and UNION (MARMOTTA-538) Date: Thu, 18 Sep 2014 15:16:48 +0000 (UTC) Repository: marmotta Updated Branches: refs/heads/develop f1e457b77 -> ee1f7b8ec improved support for subqueries (MARMOTTA-540) and UNION (MARMOTTA-538) Project: http://git-wip-us.apache.org/repos/asf/marmotta/repo Commit: http://git-wip-us.apache.org/repos/asf/marmotta/commit/ee1f7b8e Tree: http://git-wip-us.apache.org/repos/asf/marmotta/tree/ee1f7b8e Diff: http://git-wip-us.apache.org/repos/asf/marmotta/diff/ee1f7b8e Branch: refs/heads/develop Commit: ee1f7b8ec0b548bb8f21ddfd8519de590a65a791 Parents: f1e457b Author: Sebastian Schaffert Authored: Thu Sep 18 17:17:05 2014 +0200 Committer: Sebastian Schaffert Committed: Thu Sep 18 17:17:05 2014 +0200 ---------------------------------------------------------------------- .../kiwi/sparql/builder/DistinctFinder.java | 14 +- .../kiwi/sparql/builder/LimitFinder.java | 14 ++ .../kiwi/sparql/builder/OrderFinder.java | 17 +- .../kiwi/sparql/builder/PatternCollector.java | 8 +- .../kiwi/sparql/builder/SQLBuilder.java | 33 ++- .../sparql/builder/SQLProjectionFinder.java | 21 +- .../kiwi/sparql/builder/SQLSubQuery.java | 15 +- .../marmotta/kiwi/sparql/builder/SQLUnion.java | 11 +- .../kiwi/sparql/builder/VariableFinder.java | 66 +++++ .../evaluation/KiWiEvaluationStrategyImpl.java | 251 +++++++------------ .../optimizer/DistinctLimitOptimizer.java | 28 ++- .../persistence/KiWiSparqlConnection.java | 9 +- 12 files changed, 286 insertions(+), 201 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/marmotta/blob/ee1f7b8e/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/DistinctFinder.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/DistinctFinder.java b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/DistinctFinder.java index 9a91c3f..efdf88a 100644 --- a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/DistinctFinder.java +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/DistinctFinder.java @@ -17,9 +17,7 @@ package org.apache.marmotta.kiwi.sparql.builder; -import org.openrdf.query.algebra.Distinct; -import org.openrdf.query.algebra.Reduced; -import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.algebra.*; import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; /** @@ -44,4 +42,14 @@ public class DistinctFinder extends QueryModelVisitorBase { public void meet(Reduced node) throws RuntimeException { distinct = true; } + + @Override + public void meet(Projection node) throws RuntimeException { + // stop at projection, subquery + } + + @Override + public void meet(Union node) throws RuntimeException { + // stop at projection, subquery + } } http://git-wip-us.apache.org/repos/asf/marmotta/blob/ee1f7b8e/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/LimitFinder.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/LimitFinder.java b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/LimitFinder.java index 0165b80..dfe6715 100644 --- a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/LimitFinder.java +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/LimitFinder.java @@ -17,8 +17,10 @@ package org.apache.marmotta.kiwi.sparql.builder; +import org.openrdf.query.algebra.Projection; import org.openrdf.query.algebra.Slice; import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.algebra.Union; import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; /** @@ -41,4 +43,16 @@ public class LimitFinder extends QueryModelVisitorBase { if(node.hasOffset()) offset = node.getOffset(); } + + + @Override + public void meet(Projection node) throws RuntimeException { + // stop at projection, subquery + } + + @Override + public void meet(Union node) throws RuntimeException { + // stop at projection, subquery + } + } http://git-wip-us.apache.org/repos/asf/marmotta/blob/ee1f7b8e/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/OrderFinder.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/OrderFinder.java b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/OrderFinder.java index d74902f..9e6cf34 100644 --- a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/OrderFinder.java +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/OrderFinder.java @@ -17,9 +17,7 @@ package org.apache.marmotta.kiwi.sparql.builder; -import org.openrdf.query.algebra.Order; -import org.openrdf.query.algebra.OrderElem; -import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.algebra.*; import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; import java.util.ArrayList; @@ -42,4 +40,17 @@ public class OrderFinder extends QueryModelVisitorBase { public void meet(Order node) throws RuntimeException { elements.addAll(node.getElements()); } + + + + @Override + public void meet(Projection node) throws RuntimeException { + // stop at projection, subquery + } + + @Override + public void meet(Union node) throws RuntimeException { + // stop at projection, subquery + } + } http://git-wip-us.apache.org/repos/asf/marmotta/blob/ee1f7b8e/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/PatternCollector.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/PatternCollector.java b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/PatternCollector.java index 1f44ca1..10fcb17 100644 --- a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/PatternCollector.java +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/PatternCollector.java @@ -24,6 +24,7 @@ import org.openrdf.query.algebra.*; import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; import java.util.LinkedList; +import java.util.Set; /** * Collect all statement patterns in a tuple expression. @@ -41,13 +42,14 @@ public class PatternCollector extends QueryModelVisitorBase { private Dataset dataset; private ValueConverter converter; private KiWiDialect dialect; + private Set projectedVars; - - public PatternCollector(TupleExpr expr, BindingSet bindings, Dataset dataset, ValueConverter converter, KiWiDialect dialect) { + public PatternCollector(TupleExpr expr, BindingSet bindings, Dataset dataset, ValueConverter converter, KiWiDialect dialect, Set projectedVars) { this.bindings = bindings; this.dataset = dataset; this.converter = converter; this.dialect = dialect; + this.projectedVars = projectedVars; parts.push(new SQLFragment()); expr.visit(this); @@ -90,6 +92,6 @@ public class PatternCollector extends QueryModelVisitorBase { public void meet(Projection node) throws RuntimeException { // subqueries are represented with a projection inside a JOIN; we don't continue collection - parts.getLast().getSubqueries().add(new SQLSubQuery("S" + (++counter), node, bindings, dataset, converter, dialect)); + parts.getLast().getSubqueries().add(new SQLSubQuery("S" + (++counter), node, bindings, dataset, converter, dialect, projectedVars)); } } http://git-wip-us.apache.org/repos/asf/marmotta/blob/ee1f7b8e/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLBuilder.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLBuilder.java b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLBuilder.java index c6f3eb4..982a5a9 100644 --- a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLBuilder.java +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLBuilder.java @@ -139,6 +139,9 @@ public class SQLBuilder { private Set groupLabels; + // list of SPARQL variable names that are actually contained in the projection + private Set projectedVars; + /** * Maintains a mapping between SPARQL variable names and internal variable descriptions. The internal description * contains information whether the variable needs to be projected, what SQL expressions represent this variable, @@ -173,13 +176,13 @@ public class SQLBuilder { * @param bindings * @param dataset */ - public SQLBuilder(TupleExpr query, BindingSet bindings, Dataset dataset, final KiWiValueFactory valueFactory, KiWiDialect dialect) throws UnsatisfiableQueryException { + public SQLBuilder(TupleExpr query, BindingSet bindings, Dataset dataset, final KiWiValueFactory valueFactory, KiWiDialect dialect, Set projectedVars) throws UnsatisfiableQueryException { this(query, bindings, dataset, new ValueConverter() { @Override public KiWiNode convert(Value value) { return valueFactory.convert(value); } - }, dialect); + }, dialect, projectedVars); } /** @@ -188,12 +191,13 @@ public class SQLBuilder { * @param bindings * @param dataset */ - public SQLBuilder(TupleExpr query, BindingSet bindings, Dataset dataset, ValueConverter converter, KiWiDialect dialect) throws UnsatisfiableQueryException { + public SQLBuilder(TupleExpr query, BindingSet bindings, Dataset dataset, ValueConverter converter, KiWiDialect dialect, Set projectedVars) throws UnsatisfiableQueryException { this.query = query; this.bindings = bindings; this.dataset = dataset; this.converter = converter; this.dialect = dialect; + this.projectedVars = projectedVars; prepareBuilder(); } @@ -203,12 +207,17 @@ public class SQLBuilder { return variables; } + + public Set getProjectedVars() { + return projectedVars; + } + private void prepareBuilder() throws UnsatisfiableQueryException { Preconditions.checkArgument(query instanceof Union || query instanceof Extension || query instanceof Order || query instanceof Group || query instanceof LeftJoin ||query instanceof Join || query instanceof Filter || query instanceof StatementPattern || query instanceof Distinct || query instanceof Slice || query instanceof Reduced); // collect all patterns in a list, using depth-first search over the join - PatternCollector pc = new PatternCollector(query, bindings, dataset, converter, dialect); + PatternCollector pc = new PatternCollector(query, bindings, dataset, converter, dialect, projectedVars); fragments = pc.parts; @@ -247,7 +256,7 @@ public class SQLBuilder { sv = new SQLVariable("V" + (++variableCount), v.getName()); // select those variables that are really projected and not only needed in a grouping construct - if(new SQLProjectionFinder(query,v.getName()).found) { + if(projectedVars.contains(sv.getSparqlName()) || new SQLProjectionFinder(query,v.getName()).found) { sv.setProjectionType(ProjectionType.NODE); } @@ -280,7 +289,7 @@ public class SQLBuilder { sv = new SQLVariable("V" + (++variableCount), sq_v.getSparqlName()); // select those variables that are really projected and not only needed in a grouping construct - if(new SQLProjectionFinder(query,sq_v.getSparqlName()).found) { + if(projectedVars.contains(sv.getSparqlName()) || new SQLProjectionFinder(query,sq_v.getSparqlName()).found) { sv.setProjectionType(sq_v.getProjectionType()); } @@ -316,7 +325,7 @@ public class SQLBuilder { sv = new SQLVariable("V" + (++variableCount), v.getName()); // select those variables that are really projected and not only needed in a grouping construct - if(new SQLProjectionFinder(query,v.getName()).found) { + if(projectedVars.contains(sv.getSparqlName()) || new SQLProjectionFinder(query,v.getName()).found) { sv.setProjectionType(getProjectionType(ext.getExpr())); } @@ -524,7 +533,7 @@ public class SQLBuilder { for(SQLVariable v : vars) { - if(v.getProjectionType() != ProjectionType.NONE) { + if(v.getProjectionType() != ProjectionType.NONE && (projectedVars.isEmpty() || projectedVars.contains(v.getSparqlName()))) { String projectedName = v.getName(); String fromName = v.getExpressions().get(0); @@ -962,6 +971,9 @@ public class SQLBuilder { /** * Check if a variable selecting a node actually has any attached condition; if not return false. This is used to * decide whether joining with the node itself is necessary. + * + * TODO: could be implemented as visitor instead + * * @param varName * @param expr * @return @@ -990,6 +1002,10 @@ public class SQLBuilder { } } return hasNodeCondition(varName,((Group) expr).getArg()); + } else if(expr instanceof Union) { + return false; // stop looking, this is a subquery + } else if(expr instanceof Projection) { + return false; // stop looking, this is a subquery } else if(expr instanceof UnaryTupleOperator) { return hasNodeCondition(varName, ((UnaryTupleOperator) expr).getArg()); } else if(expr instanceof BinaryTupleOperator) { @@ -1209,6 +1225,7 @@ public class SQLBuilder { log.debug("original SPARQL syntax tree:\n {}", query); log.debug("constructed SQL query string:\n {}",queryString); log.debug("SPARQL -> SQL node variable mappings:\n {}", variables); + log.debug("projected variables:\n {}", projectedVars); return queryString.toString(); } http://git-wip-us.apache.org/repos/asf/marmotta/blob/ee1f7b8e/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLProjectionFinder.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLProjectionFinder.java b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLProjectionFinder.java index f3c2d1b..cd47e50 100644 --- a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLProjectionFinder.java +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLProjectionFinder.java @@ -17,10 +17,7 @@ package org.apache.marmotta.kiwi.sparql.builder; -import org.openrdf.query.algebra.ExtensionElem; -import org.openrdf.query.algebra.Group; -import org.openrdf.query.algebra.TupleExpr; -import org.openrdf.query.algebra.Var; +import org.openrdf.query.algebra.*; import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; import org.slf4j.Logger; import org.slf4j.LoggerFactory; @@ -72,4 +69,20 @@ public class SQLProjectionFinder extends QueryModelVisitorBase found = true; } } + + + @Override + public void meet(Projection node) throws RuntimeException { + for(ProjectionElem elem : node.getProjectionElemList().getElements()) { + if(elem.getSourceName().equals(needle)) { + found = true; + } + } + // stop at projection, subquery + } + + @Override + public void meet(Union node) throws RuntimeException { + // stop at union, subquery + } } http://git-wip-us.apache.org/repos/asf/marmotta/blob/ee1f7b8e/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLSubQuery.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLSubQuery.java b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLSubQuery.java index 99da670..af8444c 100644 --- a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLSubQuery.java +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLSubQuery.java @@ -22,6 +22,7 @@ import org.apache.marmotta.kiwi.sparql.exception.UnsatisfiableQueryException; import org.openrdf.query.BindingSet; import org.openrdf.query.Dataset; import org.openrdf.query.algebra.Projection; +import org.openrdf.query.algebra.ProjectionElem; import java.util.HashSet; import java.util.Set; @@ -38,11 +39,19 @@ public class SQLSubQuery extends SQLAbstractSubquery { private Set variables = new HashSet<>(); - public SQLSubQuery(String alias, Projection query, BindingSet bindings, Dataset dataset, ValueConverter converter, KiWiDialect dialect) throws UnsatisfiableQueryException { + public SQLSubQuery(String alias, Projection query, BindingSet bindings, Dataset dataset, ValueConverter converter, KiWiDialect dialect, Set parentProjectedVars) throws UnsatisfiableQueryException { super(alias); + Set projectedVars = new HashSet<>(parentProjectedVars); + // count projected variables + for(ProjectionElem elem : query.getProjectionElemList().getElements()) { + projectedVars.add(elem.getSourceName()); + } + + + // we build a full subquery for each of the UNION's arguments - builder = new SQLBuilder(query.getArg(), bindings, dataset, converter, dialect); + builder = new SQLBuilder(query.getArg(), bindings, dataset, converter, dialect, projectedVars); for(SQLVariable svl : builder.getVariables().values()) { variables.add(svl); @@ -76,7 +85,7 @@ public class SQLSubQuery extends SQLAbstractSubquery { .append(alias); for(VariableMapping var : getJoinFields()) { - fromClause.append(" LEFT OUTER JOIN nodes AS "); // outer join because binding might be NULL + fromClause.append(" LEFT JOIN nodes AS "); // outer join because binding might be NULL fromClause.append(alias + "_" + var.getParentName()); fromClause.append(" ON " + alias + "." + var.getSubqueryName() + " = " + alias + "_" + var.getParentName() + ".id "); http://git-wip-us.apache.org/repos/asf/marmotta/blob/ee1f7b8e/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLUnion.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLUnion.java b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLUnion.java index dbc1fd8..6fd779a 100644 --- a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLUnion.java +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLUnion.java @@ -25,10 +25,7 @@ import org.openrdf.query.algebra.Union; import org.slf4j.Logger; import org.slf4j.LoggerFactory; -import java.util.HashMap; -import java.util.HashSet; -import java.util.Map; -import java.util.Set; +import java.util.*; /** * Represents a SPARQL UNION in SQL. Essentially, we translate a SPARQL UNION into a SQL subquery using UNION to @@ -53,8 +50,8 @@ public class SQLUnion extends SQLAbstractSubquery { super(alias); // we build a full subquery for each of the UNION's arguments - left = new SQLBuilder(query.getLeftArg(), bindings, dataset, converter, dialect); - right = new SQLBuilder(query.getRightArg(), bindings, dataset, converter, dialect); + left = new SQLBuilder(query.getLeftArg(), bindings, dataset, converter, dialect, Collections.EMPTY_SET); + right = new SQLBuilder(query.getRightArg(), bindings, dataset, converter, dialect, Collections.EMPTY_SET); // next we make sure that both subqueries share the same SQL variables so the SQL UNION succeeds by // adding NULL aliases for all variables present in one but not the other @@ -123,7 +120,7 @@ public class SQLUnion extends SQLAbstractSubquery { .append(alias); for(VariableMapping var : getJoinFields()) { - fromClause.append(" LEFT OUTER JOIN nodes AS "); // outer join because binding might be NULL + fromClause.append(" LEFT JOIN nodes AS "); // outer join because binding might be NULL fromClause.append(alias + "_" + var.getParentName()); fromClause.append(" ON " + alias + "." + var.getSubqueryName() + " = " + alias + "_" + var.getParentName() + ".id "); http://git-wip-us.apache.org/repos/asf/marmotta/blob/ee1f7b8e/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/VariableFinder.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/VariableFinder.java b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/VariableFinder.java new file mode 100644 index 0000000..ab3dbb9 --- /dev/null +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/VariableFinder.java @@ -0,0 +1,66 @@ +/* + * 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 org.apache.marmotta.kiwi.sparql.builder; + +import org.openrdf.query.algebra.*; +import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; + +import java.util.HashSet; +import java.util.Set; + +/** +* Find distinct/reduced in a tuple expression. +* +* @author Sebastian Schaffert (sschaffert@apache.org) +*/ +public class VariableFinder extends QueryModelVisitorBase { + + Set variableNames = new HashSet<>(); + + public VariableFinder(TupleExpr expr) { + expr.visit(this); + } + + + @Override + public void meet(Var node) throws RuntimeException { + variableNames.add(node.getName()); + } + + @Override + public void meet(ExtensionElem node) throws RuntimeException { + variableNames.add(node.getName()); + // don't recurse to the children, as this would project non-grouped elements + } + + @Override + public void meet(Group node) throws RuntimeException { + variableNames.addAll(node.getGroupBindingNames()); + // don't recurse to the children, as this would project non-grouped elements + } + + + @Override + public void meet(Projection node) throws RuntimeException { + for(ProjectionElem elem : node.getProjectionElemList().getElements()) { + variableNames.add(elem.getSourceName()); + } + // stop at projection, subquery + } + +} http://git-wip-us.apache.org/repos/asf/marmotta/blob/ee1f7b8e/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/evaluation/KiWiEvaluationStrategyImpl.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/evaluation/KiWiEvaluationStrategyImpl.java b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/evaluation/KiWiEvaluationStrategyImpl.java index 4259e49..487e851 100644 --- a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/evaluation/KiWiEvaluationStrategyImpl.java +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/evaluation/KiWiEvaluationStrategyImpl.java @@ -33,6 +33,8 @@ import org.slf4j.Logger; import org.slf4j.LoggerFactory; import java.sql.SQLException; +import java.util.HashSet; +import java.util.Set; /** * An implementation of the SPARQL query evaluation strategy with specific extensions and optimizations. The KiWi @@ -52,11 +54,54 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ private static Logger log = LoggerFactory.getLogger(KiWiEvaluationStrategyImpl.class); + // TODO: supported features should be checked based on this Set + private static Set supportedConstructs = new HashSet<>(); + static { + supportedConstructs.add(Join.class); + supportedConstructs.add(LeftJoin.class); + supportedConstructs.add(Filter.class); + supportedConstructs.add(Extension.class); + supportedConstructs.add(StatementPattern.class); + supportedConstructs.add(Slice.class); + supportedConstructs.add(Reduced.class); + supportedConstructs.add(Distinct.class); + supportedConstructs.add(Union.class); + supportedConstructs.add(Projection.class); // subquery only + supportedConstructs.add(Order.class); + supportedConstructs.add(Group.class); + + supportedConstructs.add(Coalesce.class); + supportedConstructs.add(Count.class); + supportedConstructs.add(Avg.class); + supportedConstructs.add(Min.class); + supportedConstructs.add(Max.class); + supportedConstructs.add(Sum.class); + supportedConstructs.add(Compare.class); + supportedConstructs.add(MathExpr.class); + supportedConstructs.add(And.class); + supportedConstructs.add(Or.class); + supportedConstructs.add(Not.class); + supportedConstructs.add(Var.class); + supportedConstructs.add(Str.class); + supportedConstructs.add(Label.class); + supportedConstructs.add(IsResource.class); + supportedConstructs.add(IsURI.class); + supportedConstructs.add(IsBNode.class); + supportedConstructs.add(IsLiteral.class); + supportedConstructs.add(Lang.class); + supportedConstructs.add(LangMatches.class); + supportedConstructs.add(Regex.class); + supportedConstructs.add(FunctionCall.class); // need to check for supported functions + } + + /** * The database connection offering specific SPARQL-SQL optimizations. */ private KiWiSparqlConnection connection; + private Set projectedVars = new HashSet<>(); + public KiWiEvaluationStrategyImpl(TripleSource tripleSource, KiWiSparqlConnection connection) { super(tripleSource); this.connection = connection; @@ -68,28 +113,22 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ } @Override - public CloseableIteration evaluate(Union union, BindingSet bindings) throws QueryEvaluationException { - if(Thread.currentThread().isInterrupted()) { - throw new QueryEvaluationException("SPARQL evaluation has already been cancelled"); + public CloseableIteration evaluate(Projection projection, BindingSet bindings) throws QueryEvaluationException { + // count projected variables + if(isSupported(projection.getArg())) { + for (ProjectionElem elem : projection.getProjectionElemList().getElements()) { + projectedVars.add(elem.getSourceName()); + } } + return super.evaluate(projection, bindings); + } + + + @Override + public CloseableIteration evaluate(Union union, BindingSet bindings) throws QueryEvaluationException { if(isSupported(union)) { - log.debug("applying KiWi UNION optimizations on SPARQL query ..."); - - try { - return new ExceptionConvertingIteration(connection.evaluateNative(union, bindings, dataset)) { - @Override - protected QueryEvaluationException convert(Exception e) { - return new QueryEvaluationException(e); - } - }; - } catch (SQLException e) { - throw new QueryEvaluationException(e.getMessage(),e); - } catch (IllegalArgumentException e) { - throw new QueryEvaluationException(e.getMessage(),e); - } catch (InterruptedException e) { - throw new QueryInterruptedException(e.getMessage()); - } + return evaluateNative(union, bindings); } else { return super.evaluate(union, bindings); } @@ -97,27 +136,8 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ @Override public CloseableIteration evaluate(Extension order, BindingSet bindings) throws QueryEvaluationException { - if(Thread.currentThread().isInterrupted()) { - throw new QueryEvaluationException("SPARQL evaluation has already been cancelled"); - } - if(isSupported(order)) { - log.debug("applying KiWi EXTENSION optimizations on SPARQL query ..."); - - try { - return new ExceptionConvertingIteration(connection.evaluateNative(order, bindings, dataset)) { - @Override - protected QueryEvaluationException convert(Exception e) { - return new QueryEvaluationException(e); - } - }; - } catch (SQLException e) { - throw new QueryEvaluationException(e.getMessage(),e); - } catch (IllegalArgumentException e) { - throw new QueryEvaluationException(e.getMessage(),e); - } catch (InterruptedException e) { - throw new QueryInterruptedException(e.getMessage()); - } + return evaluateNative(order, bindings); } else { return super.evaluate(order, bindings); } @@ -126,27 +146,8 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ @Override public CloseableIteration evaluate(Order order, BindingSet bindings) throws QueryEvaluationException { - if(Thread.currentThread().isInterrupted()) { - throw new QueryEvaluationException("SPARQL evaluation has already been cancelled"); - } - if(isSupported(order)) { - log.debug("applying KiWi ORDER optimizations on SPARQL query ..."); - - try { - return new ExceptionConvertingIteration(connection.evaluateNative(order, bindings, dataset)) { - @Override - protected QueryEvaluationException convert(Exception e) { - return new QueryEvaluationException(e); - } - }; - } catch (SQLException e) { - throw new QueryEvaluationException(e.getMessage(),e); - } catch (IllegalArgumentException e) { - throw new QueryEvaluationException(e.getMessage(),e); - } catch (InterruptedException e) { - throw new QueryInterruptedException(e.getMessage()); - } + return evaluateNative(order, bindings); } else { return super.evaluate(order, bindings); } @@ -155,27 +156,8 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ @Override public CloseableIteration evaluate(LeftJoin join, BindingSet bindings) throws QueryEvaluationException { - if(Thread.currentThread().isInterrupted()) { - throw new QueryEvaluationException("SPARQL evaluation has already been cancelled"); - } - if(isSupported(join)) { - log.debug("applying KiWi LEFTJOIN optimizations on SPARQL query ..."); - - try { - return new ExceptionConvertingIteration(connection.evaluateNative(join, bindings, dataset)) { - @Override - protected QueryEvaluationException convert(Exception e) { - return new QueryEvaluationException(e); - } - }; - } catch (SQLException e) { - throw new QueryEvaluationException(e.getMessage(),e); - } catch (IllegalArgumentException e) { - throw new QueryEvaluationException(e.getMessage(),e); - } catch (InterruptedException e) { - throw new QueryInterruptedException(e.getMessage()); - } + return evaluateNative(join, bindings); } else { return super.evaluate(join, bindings); } @@ -184,27 +166,8 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ @Override public CloseableIteration evaluate(Join join, BindingSet bindings) throws QueryEvaluationException { - if(Thread.currentThread().isInterrupted()) { - throw new QueryEvaluationException("SPARQL evaluation has already been cancelled"); - } - if(isSupported(join)) { - log.debug("applying KiWi JOIN optimizations on SPARQL query ..."); - - try { - return new ExceptionConvertingIteration(connection.evaluateNative(join, bindings, dataset)) { - @Override - protected QueryEvaluationException convert(Exception e) { - return new QueryEvaluationException(e); - } - }; - } catch (SQLException e) { - throw new QueryEvaluationException(e.getMessage(),e); - } catch (IllegalArgumentException e) { - throw new QueryEvaluationException(e.getMessage(),e); - } catch (InterruptedException e) { - throw new QueryInterruptedException(e.getMessage()); - } + return evaluateNative(join, bindings); } else { return super.evaluate(join, bindings); } @@ -213,22 +176,7 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ @Override public CloseableIteration evaluate(Filter join, BindingSet bindings) throws QueryEvaluationException { if(isSupported(join)) { - log.debug("applying KiWi FILTER optimizations on SPARQL query ..."); - - try { - return new ExceptionConvertingIteration(connection.evaluateNative(join, bindings, dataset)) { - @Override - protected QueryEvaluationException convert(Exception e) { - return new QueryEvaluationException(e); - } - }; - } catch (SQLException e) { - throw new QueryEvaluationException(e); - } catch (IllegalArgumentException e) { - throw new QueryEvaluationException(e); - } catch (InterruptedException e) { - throw new QueryInterruptedException(e); - } + return evaluateNative(join, bindings); } else { return super.evaluate(join, bindings); } @@ -237,22 +185,7 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ @Override public CloseableIteration evaluate(Slice slice, BindingSet bindings) throws QueryEvaluationException { if(isSupported(slice)) { - log.debug("applying KiWi SLICE optimizations on SPARQL query ..."); - - try { - return new ExceptionConvertingIteration(connection.evaluateNative(slice, bindings, dataset)) { - @Override - protected QueryEvaluationException convert(Exception e) { - return new QueryEvaluationException(e); - } - }; - } catch (SQLException e) { - throw new QueryEvaluationException(e); - } catch (IllegalArgumentException e) { - throw new QueryEvaluationException(e); - } catch (InterruptedException e) { - throw new QueryInterruptedException(e); - } + return evaluateNative(slice, bindings); } else { return super.evaluate(slice, bindings); } @@ -261,22 +194,7 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ @Override public CloseableIteration evaluate(Reduced reduced, BindingSet bindings) throws QueryEvaluationException { if(isSupported(reduced)) { - log.debug("applying KiWi REDUCED optimizations on SPARQL query ..."); - - try { - return new ExceptionConvertingIteration(connection.evaluateNative(reduced, bindings, dataset)) { - @Override - protected QueryEvaluationException convert(Exception e) { - return new QueryEvaluationException(e); - } - }; - } catch (SQLException e) { - throw new QueryEvaluationException(e); - } catch (IllegalArgumentException e) { - throw new QueryEvaluationException(e); - } catch (InterruptedException e) { - throw new QueryInterruptedException(e); - } + return evaluateNative(reduced, bindings); } else { return super.evaluate(reduced, bindings); } @@ -285,27 +203,32 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ @Override public CloseableIteration evaluate(Distinct distinct, BindingSet bindings) throws QueryEvaluationException { if(isSupported(distinct)) { - log.debug("applying KiWi DISTINCT optimizations on SPARQL query ..."); - - try { - return new ExceptionConvertingIteration(connection.evaluateNative(distinct, bindings, dataset)) { - @Override - protected QueryEvaluationException convert(Exception e) { - return new QueryEvaluationException(e); - } - }; - } catch (SQLException e) { - throw new QueryEvaluationException(e); - } catch (IllegalArgumentException e) { - throw new QueryEvaluationException(e); - } catch (InterruptedException e) { - throw new QueryInterruptedException(e); - } + return evaluateNative(distinct, bindings); } else { return super.evaluate(distinct, bindings); } } + public CloseableIteration evaluateNative(TupleExpr expr, BindingSet bindings) throws QueryEvaluationException { + log.debug("applying KiWi native optimizations on SPARQL query ..."); + + try { + return new ExceptionConvertingIteration(connection.evaluateNative(expr, bindings, dataset, projectedVars)) { + @Override + protected QueryEvaluationException convert(Exception e) { + return new QueryEvaluationException(e); + } + }; + } catch (SQLException e) { + throw new QueryEvaluationException(e); + } catch (IllegalArgumentException e) { + throw new QueryEvaluationException(e); + } catch (InterruptedException e) { + throw new QueryInterruptedException(e); + } + } + + /** * Test if a tuple expression is supported nby the optimized evaluation; in this case we can apply a specific optimization. @@ -316,7 +239,7 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ if(expr instanceof Join) { return isSupported(((Join) expr).getLeftArg()) && isSupported(((Join) expr).getRightArg()); } else if(expr instanceof LeftJoin) { - return isSupported(((LeftJoin) expr).getLeftArg()) && isSupported(((LeftJoin) expr).getRightArg()) && isSupported(((LeftJoin)expr).getCondition()); + return isSupported(((LeftJoin) expr).getLeftArg()) && isSupported(((LeftJoin) expr).getRightArg()) && isSupported(((LeftJoin)expr).getCondition()); } else if(expr instanceof Filter) { return isSupported(((Filter) expr).getArg()) && isSupported(((Filter) expr).getCondition()); } else if(expr instanceof Extension) { http://git-wip-us.apache.org/repos/asf/marmotta/blob/ee1f7b8e/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/optimizer/DistinctLimitOptimizer.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/optimizer/DistinctLimitOptimizer.java b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/optimizer/DistinctLimitOptimizer.java index f14bff4..ca64a6f 100644 --- a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/optimizer/DistinctLimitOptimizer.java +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/optimizer/DistinctLimitOptimizer.java @@ -37,13 +37,13 @@ public class DistinctLimitOptimizer implements QueryOptimizer { @Override public void optimize(TupleExpr tupleExpr, Dataset dataset, BindingSet bindings) { - if( new LimitPreconditions(tupleExpr).isAllowed() ) { + //if( new LimitPreconditions(tupleExpr).isAllowed() ) { log.debug("applying distinct/limit optimizations ..."); tupleExpr.visit(new LimitRelocator()); tupleExpr.visit(new DistinctRelocator()); tupleExpr.visit(new ReducedRelocator()); - } + //} } /** @@ -133,10 +133,18 @@ public class DistinctLimitOptimizer implements QueryOptimizer { private static boolean isSupported(TupleExpr expr) { if(expr instanceof Join) { return true; + } else if(expr instanceof LeftJoin) { + return true; } else if(expr instanceof Filter) { return true; } else if(expr instanceof StatementPattern) { return true; + } else if(expr instanceof Union) { + return true; + } else if(expr instanceof Order) { + return true; + } else if(expr instanceof Group) { + return true; } else { return false; } @@ -171,10 +179,18 @@ public class DistinctLimitOptimizer implements QueryOptimizer { private static boolean isSupported(TupleExpr expr) { if(expr instanceof Join) { return true; + } else if(expr instanceof LeftJoin) { + return true; } else if(expr instanceof Filter) { return true; } else if(expr instanceof StatementPattern) { return true; + } else if(expr instanceof Union) { + return true; + } else if(expr instanceof Order) { + return true; + } else if(expr instanceof Group) { + return true; } else if(expr instanceof Slice) { return true; } else { @@ -211,10 +227,18 @@ public class DistinctLimitOptimizer implements QueryOptimizer { private static boolean isSupported(TupleExpr expr) { if(expr instanceof Join) { return true; + } else if(expr instanceof LeftJoin) { + return true; } else if(expr instanceof Filter) { return true; } else if(expr instanceof StatementPattern) { return true; + } else if(expr instanceof Union) { + return true; + } else if(expr instanceof Order) { + return true; + } else if(expr instanceof Group) { + return true; } else if(expr instanceof Slice) { return true; } else if(expr instanceof Distinct) { http://git-wip-us.apache.org/repos/asf/marmotta/blob/ee1f7b8e/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/persistence/KiWiSparqlConnection.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/persistence/KiWiSparqlConnection.java b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/persistence/KiWiSparqlConnection.java index 0ad6a90..d242b3e 100644 --- a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/persistence/KiWiSparqlConnection.java +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/persistence/KiWiSparqlConnection.java @@ -47,6 +47,7 @@ import java.sql.ResultSet; import java.sql.SQLException; import java.util.ArrayList; import java.util.List; +import java.util.Set; import java.util.concurrent.*; /** @@ -82,10 +83,10 @@ public class KiWiSparqlConnection { * @param dataset * @return */ - public CloseableIteration evaluateNative(TupleExpr join, final BindingSet bindings, final Dataset dataset) throws SQLException, InterruptedException { + public CloseableIteration evaluateNative(TupleExpr join, final BindingSet bindings, final Dataset dataset, Set projectedVars) throws SQLException, InterruptedException { try { - final SQLBuilder builder = new SQLBuilder(join, bindings, dataset, valueFactory, parent.getDialect()); + final SQLBuilder builder = new SQLBuilder(join, bindings, dataset, valueFactory, parent.getDialect(), projectedVars); final PreparedStatement queryStatement = parent.getJDBCConnection().prepareStatement(builder.build()); if (parent.getDialect().isCursorSupported()) { @@ -123,7 +124,7 @@ public class KiWiSparqlConnection { long[] nodeIds = new long[vars.size()]; for(int i=0; i