Repository: marmotta Updated Branches: refs/heads/develop 0c899417a -> 4e63ca961
first native implementation of GROUP BY (MARMOTTA-495) Project: http://git-wip-us.apache.org/repos/asf/marmotta/repo Commit: http://git-wip-us.apache.org/repos/asf/marmotta/commit/4e63ca96 Tree: http://git-wip-us.apache.org/repos/asf/marmotta/tree/4e63ca96 Diff: http://git-wip-us.apache.org/repos/asf/marmotta/diff/4e63ca96 Branch: refs/heads/develop Commit: 4e63ca961f4687ce14e6242667ce140f23a522e8 Parents: 0c89941 Author: Sebastian Schaffert <[email protected]> Authored: Tue Sep 16 18:27:29 2014 +0200 Committer: Sebastian Schaffert <[email protected]> Committed: Tue Sep 16 18:27:29 2014 +0200 ---------------------------------------------------------------------- .../kiwi/sparql/builder/GroupFinder.java | 50 ++++++++ .../kiwi/sparql/builder/SQLBuilder.java | 115 ++++++++++++++++--- .../sparql/builder/SQLProjectionFinder.java | 75 ++++++++++++ .../evaluation/KiWiEvaluationStrategyImpl.java | 12 ++ .../marmotta/kiwi/persistence/KiWiDialect.java | 9 ++ .../persistence/pgsql/PostgreSQLDialect.java | 10 ++ 6 files changed, 258 insertions(+), 13 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/marmotta/blob/4e63ca96/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/GroupFinder.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/GroupFinder.java b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/GroupFinder.java new file mode 100644 index 0000000..515cf7d --- /dev/null +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/GroupFinder.java @@ -0,0 +1,50 @@ +/* + * 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.Group; +import org.openrdf.query.algebra.GroupElem; +import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; + +import java.util.ArrayList; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +/** +* Find the offset and limit values in a tuple expression +* +* @author Sebastian Schaffert ([email protected]) +*/ +public class GroupFinder extends QueryModelVisitorBase<RuntimeException> { + + Set<String> bindings = new HashSet<>(); + List<GroupElem> elements = new ArrayList<>(); + + public GroupFinder(TupleExpr expr) { + expr.visit(this); + } + + @Override + public void meet(Group node) throws RuntimeException { + bindings.addAll(node.getGroupBindingNames()); + elements.addAll(node.getGroupElements()); + super.meet(node); + } +} http://git-wip-us.apache.org/repos/asf/marmotta/blob/4e63ca96/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 cdee921..942c0f5 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 @@ -163,6 +163,9 @@ public class SQLBuilder { private List<OrderElem> orderby; private List<ExtensionElem> extensions; + private List<GroupElem> groupExpressions; + private Set<String> groupLabels; + /** * A map for mapping the SPARQL variable names to internal names used for constructing SQL aliases. * Will look like { ?x -> "V1", ?y -> "V2", ... } @@ -186,6 +189,7 @@ public class SQLBuilder { private Map<Var, ProjectionType> variableTypes = new HashMap<>(); + private Set<Var> projectedVariables = new HashSet<>(); /** * The triple patterns collected from the query. @@ -264,7 +268,7 @@ public class SQLBuilder { * @return */ public Set<Var> getProjectedVariables() { - return queryVariableIds.keySet(); + return projectedVariables; } /** @@ -306,6 +310,11 @@ public class SQLBuilder { // find the ordering orderby = new OrderFinder(query).elements; + // find the grouping + GroupFinder gf = new GroupFinder(query); + groupExpressions = gf.elements; + groupLabels = gf.bindings; + // find extensions (BIND) extensions = new ExtensionFinder(query).elements; @@ -326,6 +335,11 @@ public class SQLBuilder { variableTypes.put(v, ProjectionType.NODE); queryVariables.put(v.getName(), new LinkedList<String>()); queryVariableIds.put(v, new LinkedList<String>()); + + // select those variables that are really projected and not only needed in a grouping construct + if(new SQLProjectionFinder(query,v).found) { + projectedVariables.add(v); + } } String pName = p.getName(); String vName = variableNames.get(v); @@ -344,6 +358,8 @@ public class SQLBuilder { } } + + // add all extensions to the variable list so they are properly considered in projections and clauses for(ExtensionElem ext : extensions) { Var v = new Var(ext.getName()); @@ -354,6 +370,11 @@ public class SQLBuilder { variableTypes.put(v, getProjectionType(ext.getExpr())); queryVariables.put(v.getName(), new LinkedList<String>()); queryVariableIds.put(v, new LinkedList<String>()); + + // select those variables that are really projected and not only needed in a grouping construct + if(new SQLProjectionFinder(query,v).found) { + projectedVariables.add(v); + } } if (hasNodeCondition(v, query)) { queryVariables.get(v.getName()).add(evaluateExpression(ext.getExpr(), OPTypes.ANY)); @@ -515,23 +536,25 @@ public class SQLBuilder { private String buildSelectClause() { + List<String> projections = new ArrayList<>(); + for(Iterator<Var> it = queryVariableIds.keySet().iterator(); it.hasNext(); ) { + Var v = it.next(); + if(projectedVariables.contains(v)) { + String projectedName = variableNames.get(v); + String fromName = queryVariableIds.get(v).get(0); + + projections.add(fromName + " AS " + projectedName); + + } + } + StringBuilder selectClause = new StringBuilder(); if(distinct) { selectClause.append("DISTINCT "); } - for(Iterator<Var> it = queryVariableIds.keySet().iterator(); it.hasNext(); ) { - Var v = it.next(); - String projectedName = variableNames.get(v); - String fromName = queryVariableIds.get(v).get(0); - selectClause.append(fromName); - selectClause.append(" as "); - selectClause.append(projectedName); - if(it.hasNext()) { - selectClause.append(", "); - } - } + selectClause.append(CollectionUtils.fold(projections,", ")); return selectClause.toString(); } @@ -712,11 +735,40 @@ public class SQLBuilder { orderClause.append(", "); } } + orderClause.append(" \n"); } return orderClause.toString(); } + private String buildGroupClause() { + StringBuilder groupClause = new StringBuilder(); + if(groupLabels.size() > 0) { + groupClause.append("GROUP BY "); + for(Iterator<String> it = groupLabels.iterator(); it.hasNext(); ) { + Var v = new Var(it.next()); + + + if(queryVariableIds.get(v) != null) { + Iterator<String> lit = queryVariableIds.get(v).iterator(); + while (lit.hasNext()) { + groupClause.append(lit.next()); + if(lit.hasNext()) { + groupClause.append(", "); + } + } + } + + if(it.hasNext()) { + groupClause.append(", "); + } + } + groupClause.append(" \n"); + } + + return groupClause.toString(); + } + private String buildLimitClause() { // construct limit and offset @@ -879,6 +931,41 @@ public class SQLBuilder { return evaluateExpression(valueExpr, optype); } },", ") + ")"; + } else if(expr instanceof Count) { + StringBuilder countExp = new StringBuilder(); + countExp.append("COUNT("); + + if(((Count) expr).isDistinct()) { + countExp.append("DISTINCT "); + } + + if(((Count) expr).getArg() == null) { + // this is a weird special case where we need to expand to all variables selected in the query wrapped + // by the group; we cannot simply use "*" because the concept of variables is a different one in SQL, + // so instead we construct an ARRAY of the bindings of all variables + + List<String> countVariables = new ArrayList<>(); + for(Map.Entry<Var,List<String>> v : queryVariableIds.entrySet()) { + if(!projectedVariables.contains(v.getKey())) { + countVariables.add(v.getValue().get(0)); + } + } + countExp.append("ARRAY["); + countExp.append(CollectionUtils.fold(countVariables,",")); + countExp.append("]"); + + } else { + countExp.append(evaluateExpression(((Count) expr).getArg(), OPTypes.ANY)); + } + countExp.append(")"); + + return countExp.toString(); + } else if(expr instanceof Avg) { + return "AVG(" + evaluateExpression(((Avg) expr).getArg(), OPTypes.DOUBLE) + ")"; + } else if(expr instanceof Min) { + return "MIN(" + evaluateExpression(((Min) expr).getArg(), OPTypes.DOUBLE) + ")"; + } else if(expr instanceof Max) { + return "MAX(" + evaluateExpression(((Max) expr).getArg(), OPTypes.DOUBLE) + ")"; } else if(expr instanceof FunctionCall) { FunctionCall fc = (FunctionCall)expr; @@ -1164,6 +1251,7 @@ public class SQLBuilder { String fromClause = buildFromClause(); String whereClause = buildWhereClause(); String orderClause = buildOrderClause(); + String groupClause = buildGroupClause(); String limitClause = buildLimitClause(); @@ -1172,7 +1260,8 @@ public class SQLBuilder { "SELECT " + selectClause + "\n " + "FROM " + fromClause + "\n " + "WHERE " + whereClause + "\n " + - orderClause + "\n " + + groupClause + + orderClause + limitClause; log.debug("original SPARQL syntax tree:\n {}", query); http://git-wip-us.apache.org/repos/asf/marmotta/blob/4e63ca96/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 new file mode 100644 index 0000000..46bece0 --- /dev/null +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/SQLProjectionFinder.java @@ -0,0 +1,75 @@ +/* + * 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.ExtensionElem; +import org.openrdf.query.algebra.Group; +import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.algebra.Var; +import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +import java.util.ArrayList; +import java.util.List; + +/** +* Find the offset and limit values in a tuple expression +* +* @author Sebastian Schaffert ([email protected]) +*/ +public class SQLProjectionFinder extends QueryModelVisitorBase<RuntimeException> { + + private static Logger log = LoggerFactory.getLogger(SQLProjectionFinder.class); + + List<ExtensionElem> elements = new ArrayList<>(); + + Var needle; + + boolean found = false; + + public SQLProjectionFinder(TupleExpr expr, Var needle) { + this.needle = needle; + expr.visit(this); + } + + @Override + public void meet(ExtensionElem node) throws RuntimeException { + if(node.getName().equals(needle.getName())) { + found = true; + } + // don't recurse to the children, as this would project non-grouped elements + } + + @Override + public void meet(Group node) throws RuntimeException { + for(String g : node.getGroupBindingNames()) { + if(g.equals(needle.getName())) { + found = true; + } + } + // don't recurse to the children, as this would project non-grouped elements + } + + @Override + public void meet(Var node) throws RuntimeException { + if(node.equals(needle)) { + found = true; + } + } +} http://git-wip-us.apache.org/repos/asf/marmotta/blob/4e63ca96/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 201cccb..cb2f23d 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 @@ -342,6 +342,18 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ } } return true; + } else if(expr instanceof Count) { + if(((Count) expr).getArg() == null) { + return connection.getDialect().isArraySupported(); + } else { + return isSupported(((Count) expr).getArg()); + } + } else if(expr instanceof Avg) { + return isSupported(((Avg) expr).getArg()); + } else if(expr instanceof Min) { + return isSupported(((Min) expr).getArg()); + } else if(expr instanceof Max) { + return isSupported(((Max) expr).getArg()); } else if(expr instanceof Compare) { return isSupported(((Compare) expr).getLeftArg()) && isSupported(((Compare) expr).getRightArg()); } else if(expr instanceof MathExpr) { http://git-wip-us.apache.org/repos/asf/marmotta/blob/4e63ca96/libraries/kiwi/kiwi-triplestore/src/main/java/org/apache/marmotta/kiwi/persistence/KiWiDialect.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-triplestore/src/main/java/org/apache/marmotta/kiwi/persistence/KiWiDialect.java b/libraries/kiwi/kiwi-triplestore/src/main/java/org/apache/marmotta/kiwi/persistence/KiWiDialect.java index 3dc2270..c8ede67 100644 --- a/libraries/kiwi/kiwi-triplestore/src/main/java/org/apache/marmotta/kiwi/persistence/KiWiDialect.java +++ b/libraries/kiwi/kiwi-triplestore/src/main/java/org/apache/marmotta/kiwi/persistence/KiWiDialect.java @@ -83,6 +83,15 @@ public abstract class KiWiDialect { */ public abstract boolean isBatchSupported(); + + /** + * Return true in case the database supports creating arrays with ARRAY[...] + * @return + */ + public boolean isArraySupported() { + return false; + } + /** * Return the contents of the SQL create script used for initialising an empty database * @return http://git-wip-us.apache.org/repos/asf/marmotta/blob/4e63ca96/libraries/kiwi/kiwi-triplestore/src/main/java/org/apache/marmotta/kiwi/persistence/pgsql/PostgreSQLDialect.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-triplestore/src/main/java/org/apache/marmotta/kiwi/persistence/pgsql/PostgreSQLDialect.java b/libraries/kiwi/kiwi-triplestore/src/main/java/org/apache/marmotta/kiwi/persistence/pgsql/PostgreSQLDialect.java index 63a4db7..b7d1fea 100644 --- a/libraries/kiwi/kiwi-triplestore/src/main/java/org/apache/marmotta/kiwi/persistence/pgsql/PostgreSQLDialect.java +++ b/libraries/kiwi/kiwi-triplestore/src/main/java/org/apache/marmotta/kiwi/persistence/pgsql/PostgreSQLDialect.java @@ -163,6 +163,16 @@ public class PostgreSQLDialect extends KiWiDialect { /** + * Return true in case the database supports creating arrays with ARRAY[...] + * + * @return + */ + @Override + public boolean isArraySupported() { + return true; + } + + /** * Return an SQL string for evaluating the function with the given URI on the arguments. All arguments are already * properly substituted SQL expressions (e.g. field names or constants). * <p/>
