implement support for ORDER BY (MARMOTTA-496)
Project: http://git-wip-us.apache.org/repos/asf/marmotta/repo Commit: http://git-wip-us.apache.org/repos/asf/marmotta/commit/3753fe06 Tree: http://git-wip-us.apache.org/repos/asf/marmotta/tree/3753fe06 Diff: http://git-wip-us.apache.org/repos/asf/marmotta/diff/3753fe06 Branch: refs/heads/develop Commit: 3753fe06066135adc1e33ad2ef192800dc9907cb Parents: 0921aca Author: Sebastian Schaffert <[email protected]> Authored: Tue Sep 16 11:52:55 2014 +0200 Committer: Sebastian Schaffert <[email protected]> Committed: Tue Sep 16 11:52:55 2014 +0200 ---------------------------------------------------------------------- .../marmotta/kiwi/sparql/builder/OPTypes.java | 2 +- .../kiwi/sparql/builder/OrderFinder.java | 45 ++++++++++++++++ .../kiwi/sparql/builder/SQLBuilder.java | 41 ++++++++++++++- .../evaluation/KiWiEvaluationStrategyImpl.java | 55 +++++++++++++++++--- .../persistence/KiWiSparqlConnection.java | 2 +- .../sparql/sail/KiWiSparqlSailConnection.java | 2 +- .../kiwi/sparql/test/KiWiSparqlJoinTest.java | 7 +++ .../kiwi/sparql/test/KiWiSparqlUpdateTest.java | 8 +++ .../marmotta/kiwi/sparql/test/query24.sparql | 24 +++++++++ 9 files changed, 176 insertions(+), 10 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/marmotta/blob/3753fe06/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/OPTypes.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/OPTypes.java b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/OPTypes.java index 9f1d8a4..9139e79 100644 --- a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/OPTypes.java +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/OPTypes.java @@ -23,5 +23,5 @@ package org.apache.marmotta.kiwi.sparql.builder; * @author Sebastian Schaffert ([email protected]) */ public enum OPTypes { - STRING, DOUBLE, INT, DATE, BOOL, ANY + STRING, DOUBLE, INT, DATE, BOOL, VALUE, ANY } http://git-wip-us.apache.org/repos/asf/marmotta/blob/3753fe06/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 new file mode 100644 index 0000000..d74902f --- /dev/null +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/builder/OrderFinder.java @@ -0,0 +1,45 @@ +/* + * 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.Order; +import org.openrdf.query.algebra.OrderElem; +import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; + +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 OrderFinder extends QueryModelVisitorBase<RuntimeException> { + + List<OrderElem> elements = new ArrayList<>(); + + public OrderFinder(TupleExpr expr) { + expr.visit(this); + } + + @Override + public void meet(Order node) throws RuntimeException { + elements.addAll(node.getElements()); + } +} http://git-wip-us.apache.org/repos/asf/marmotta/blob/3753fe06/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 80704de..14a7c06 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 @@ -123,6 +123,7 @@ public class SQLBuilder { */ private long limit = -1; + private List<OrderElem> orderby; /** * A map for mapping the SPARQL variable names to internal names used for constructing SQL aliases. @@ -236,7 +237,7 @@ public class SQLBuilder { } private void prepareBuilder() throws UnsatisfiableQueryException { - Preconditions.checkArgument(query instanceof LeftJoin ||query instanceof Join || query instanceof Filter || query instanceof StatementPattern || query instanceof Distinct || query instanceof Slice || query instanceof Reduced); + Preconditions.checkArgument(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 @@ -251,6 +252,9 @@ public class SQLBuilder { // check if query is distinct distinct = new DistinctFinder(query).distinct; + // find the ordering + orderby = new OrderFinder(query).elements; + // find all variables occurring in the patterns and create a map to map them to // field names in the database query; each variable will have one or several field names, // one for each pattern it occurs in; field names are constructed automatically by a counter @@ -619,6 +623,21 @@ public class SQLBuilder { return whereClause.toString(); } + private String buildOrderClause() { + StringBuilder orderClause = new StringBuilder(); + if(orderby.size() > 0) { + orderClause.append("ORDER BY "); + for(Iterator<OrderElem> it = orderby.iterator(); it.hasNext(); ) { + orderClause.append(evaluateExpression(it.next().getExpr(), OPTypes.VALUE)); + if(it.hasNext()) { + orderClause.append(", "); + } + } + } + + return orderClause.toString(); + } + private String buildLimitClause() { // construct limit and offset @@ -752,6 +771,7 @@ public class SQLBuilder { case INT: return var + ".ivalue"; case DOUBLE: return var + ".dvalue"; case DATE: return var + ".tvalue"; + case VALUE: return var + ".svalue"; case ANY: return var + ".id"; } } @@ -763,6 +783,7 @@ public class SQLBuilder { } else { switch (optype) { case STRING: return "'" + val + "'"; + case VALUE: return "'" + val + "'"; case INT: return "" + Integer.parseInt(val); case DOUBLE: return "" + Double.parseDouble(val); case DATE: return "'" + sqlDateFormat.format(DateUtils.parseDate(val)) + "'"; @@ -822,6 +843,8 @@ public class SQLBuilder { return dialect.getFunction(XMLSchema.BOOLEAN, arg); case DATE: return dialect.getFunction(XMLSchema.DATETIME, arg); + case VALUE: + return arg; case ANY: return arg; default: @@ -839,6 +862,20 @@ public class SQLBuilder { private boolean hasNodeCondition(Var v, TupleExpr expr) { if(expr instanceof Filter) { return hasNodeCondition(v, ((UnaryTupleOperator) expr).getArg()) || hasNodeCondition(v, ((Filter) expr).getCondition()); + } else if(expr instanceof Order) { + for(OrderElem elem : ((Order) expr).getElements()) { + if(hasNodeCondition(v, elem.getExpr())) { + return true; + } + } + return hasNodeCondition(v,((Order) expr).getArg()); + } else if(expr instanceof Group) { + for(GroupElem elem : ((Group) expr).getGroupElements()) { + if(hasNodeCondition(v, elem.getOperator())) { + return true; + } + } + return hasNodeCondition(v,((Group) expr).getArg()); } else if(expr instanceof UnaryTupleOperator) { return hasNodeCondition(v, ((UnaryTupleOperator) expr).getArg()); } else if(expr instanceof BinaryTupleOperator) { @@ -978,6 +1015,7 @@ public class SQLBuilder { String selectClause = buildSelectClause(); String fromClause = buildFromClause(); String whereClause = buildWhereClause(); + String orderClause = buildOrderClause(); String limitClause = buildLimitClause(); @@ -986,6 +1024,7 @@ public class SQLBuilder { "SELECT " + selectClause + "\n " + "FROM " + fromClause + "\n " + "WHERE " + whereClause + "\n " + + orderClause + "\n " + limitClause; log.debug("original SPARQL syntax tree:\n {}", query); http://git-wip-us.apache.org/repos/asf/marmotta/blob/3753fe06/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 7d560c0..0538d4d 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 @@ -68,6 +68,35 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ } @Override + public CloseableIteration<BindingSet, QueryEvaluationException> 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<BindingSet, QueryEvaluationException>(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()); + } + } else { + return super.evaluate(order, bindings); + } + } + + + @Override public CloseableIteration<BindingSet, QueryEvaluationException> evaluate(LeftJoin join, BindingSet bindings) throws QueryEvaluationException { if(Thread.currentThread().isInterrupted()) { throw new QueryEvaluationException("SPARQL evaluation has already been cancelled"); @@ -77,7 +106,7 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ log.debug("applying KiWi LEFTJOIN optimizations on SPARQL query ..."); try { - return new ExceptionConvertingIteration<BindingSet, QueryEvaluationException>(connection.evaluateJoin(join, bindings, dataset)) { + return new ExceptionConvertingIteration<BindingSet, QueryEvaluationException>(connection.evaluateNative(join, bindings, dataset)) { @Override protected QueryEvaluationException convert(Exception e) { return new QueryEvaluationException(e); @@ -106,7 +135,7 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ log.debug("applying KiWi JOIN optimizations on SPARQL query ..."); try { - return new ExceptionConvertingIteration<BindingSet, QueryEvaluationException>(connection.evaluateJoin(join, bindings, dataset)) { + return new ExceptionConvertingIteration<BindingSet, QueryEvaluationException>(connection.evaluateNative(join, bindings, dataset)) { @Override protected QueryEvaluationException convert(Exception e) { return new QueryEvaluationException(e); @@ -130,7 +159,7 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ log.debug("applying KiWi FILTER optimizations on SPARQL query ..."); try { - return new ExceptionConvertingIteration<BindingSet, QueryEvaluationException>(connection.evaluateJoin(join, bindings, dataset)) { + return new ExceptionConvertingIteration<BindingSet, QueryEvaluationException>(connection.evaluateNative(join, bindings, dataset)) { @Override protected QueryEvaluationException convert(Exception e) { return new QueryEvaluationException(e); @@ -154,7 +183,7 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ log.debug("applying KiWi SLICE optimizations on SPARQL query ..."); try { - return new ExceptionConvertingIteration<BindingSet, QueryEvaluationException>(connection.evaluateJoin(slice, bindings, dataset)) { + return new ExceptionConvertingIteration<BindingSet, QueryEvaluationException>(connection.evaluateNative(slice, bindings, dataset)) { @Override protected QueryEvaluationException convert(Exception e) { return new QueryEvaluationException(e); @@ -178,7 +207,7 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ log.debug("applying KiWi REDUCED optimizations on SPARQL query ..."); try { - return new ExceptionConvertingIteration<BindingSet, QueryEvaluationException>(connection.evaluateJoin(reduced, bindings, dataset)) { + return new ExceptionConvertingIteration<BindingSet, QueryEvaluationException>(connection.evaluateNative(reduced, bindings, dataset)) { @Override protected QueryEvaluationException convert(Exception e) { return new QueryEvaluationException(e); @@ -202,7 +231,7 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ log.debug("applying KiWi DISTINCT optimizations on SPARQL query ..."); try { - return new ExceptionConvertingIteration<BindingSet, QueryEvaluationException>(connection.evaluateJoin(distinct, bindings, dataset)) { + return new ExceptionConvertingIteration<BindingSet, QueryEvaluationException>(connection.evaluateNative(distinct, bindings, dataset)) { @Override protected QueryEvaluationException convert(Exception e) { return new QueryEvaluationException(e); @@ -241,6 +270,20 @@ public class KiWiEvaluationStrategyImpl extends EvaluationStrategyImpl{ return isSupported(((Reduced) expr).getArg()); } else if(expr instanceof Distinct) { return isSupported(((Distinct) expr).getArg()); + } else if(expr instanceof Order) { + for(OrderElem elem : ((Order) expr).getElements()) { + if(!isSupported(elem.getExpr())) { + return false; + } + } + return isSupported(((Order) expr).getArg()); + } else if(expr instanceof Group) { + for(GroupElem elem : ((Group) expr).getGroupElements()) { + if(!isSupported(elem.getOperator())) { + return false; + } + } + return isSupported(((Group) expr).getArg()); } else { return false; } http://git-wip-us.apache.org/repos/asf/marmotta/blob/3753fe06/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 ac0cc6e..3c9d288 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 @@ -78,7 +78,7 @@ public class KiWiSparqlConnection { * @param dataset * @return */ - public CloseableIteration<BindingSet, SQLException> evaluateJoin(TupleExpr join, final BindingSet bindings, final Dataset dataset) throws SQLException, InterruptedException { + public CloseableIteration<BindingSet, SQLException> evaluateNative(TupleExpr join, final BindingSet bindings, final Dataset dataset) throws SQLException, InterruptedException { try { final SQLBuilder builder = new SQLBuilder(join, bindings, dataset, valueFactory, parent.getDialect()); http://git-wip-us.apache.org/repos/asf/marmotta/blob/3753fe06/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/sail/KiWiSparqlSailConnection.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/sail/KiWiSparqlSailConnection.java b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/sail/KiWiSparqlSailConnection.java index 662a8dc..b0954f0 100644 --- a/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/sail/KiWiSparqlSailConnection.java +++ b/libraries/kiwi/kiwi-sparql/src/main/java/org/apache/marmotta/kiwi/sparql/sail/KiWiSparqlSailConnection.java @@ -81,7 +81,7 @@ public class KiWiSparqlSailConnection extends NotifyingSailConnectionWrapper { new QueryJoinOptimizer(new KiWiEvaluationStatistics()).optimize(tupleExpr, dataset, bindings); new IterativeEvaluationOptimizer().optimize(tupleExpr, dataset, bindings); new FilterOptimizer().optimize(tupleExpr, dataset, bindings); - new OrderLimitOptimizer().optimize(tupleExpr, dataset, bindings); + //new OrderLimitOptimizer().optimize(tupleExpr, dataset, bindings); new DistinctLimitOptimizer().optimize(tupleExpr, dataset, bindings); log.debug("evaluating SPARQL query:\n {}", tupleExpr); http://git-wip-us.apache.org/repos/asf/marmotta/blob/3753fe06/libraries/kiwi/kiwi-sparql/src/test/java/org/apache/marmotta/kiwi/sparql/test/KiWiSparqlJoinTest.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/test/java/org/apache/marmotta/kiwi/sparql/test/KiWiSparqlJoinTest.java b/libraries/kiwi/kiwi-sparql/src/test/java/org/apache/marmotta/kiwi/sparql/test/KiWiSparqlJoinTest.java index b5a2028..8be3bac 100644 --- a/libraries/kiwi/kiwi-sparql/src/test/java/org/apache/marmotta/kiwi/sparql/test/KiWiSparqlJoinTest.java +++ b/libraries/kiwi/kiwi-sparql/src/test/java/org/apache/marmotta/kiwi/sparql/test/KiWiSparqlJoinTest.java @@ -264,6 +264,13 @@ public class KiWiSparqlJoinTest { testQuery("query21.sparql"); } + // order by + @Test + public void testQuery24() throws Exception { + testQuery("query24.sparql"); + } + + // INSERT/UPDATE @Test public void testUpdate01() throws Exception { http://git-wip-us.apache.org/repos/asf/marmotta/blob/3753fe06/libraries/kiwi/kiwi-sparql/src/test/java/org/apache/marmotta/kiwi/sparql/test/KiWiSparqlUpdateTest.java ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/test/java/org/apache/marmotta/kiwi/sparql/test/KiWiSparqlUpdateTest.java b/libraries/kiwi/kiwi-sparql/src/test/java/org/apache/marmotta/kiwi/sparql/test/KiWiSparqlUpdateTest.java index da7cd6b..6f49933 100644 --- a/libraries/kiwi/kiwi-sparql/src/test/java/org/apache/marmotta/kiwi/sparql/test/KiWiSparqlUpdateTest.java +++ b/libraries/kiwi/kiwi-sparql/src/test/java/org/apache/marmotta/kiwi/sparql/test/KiWiSparqlUpdateTest.java @@ -21,6 +21,7 @@ import org.apache.marmotta.kiwi.config.KiWiConfiguration; import org.apache.marmotta.kiwi.sail.KiWiStore; import org.apache.marmotta.kiwi.sparql.sail.KiWiSparqlSail; import org.apache.marmotta.kiwi.test.junit.KiWiDatabaseRunner; +import org.junit.Ignore; import org.junit.Test; import org.junit.runner.RunWith; import org.openrdf.model.vocabulary.FOAF; @@ -60,7 +61,14 @@ public class KiWiSparqlUpdateTest extends SPARQLUpdateTest { } + /** + * This bug is apparently an issue in Sesame and does not really concern our own SPARQL implementation. Not sure + * how to work around it. + * + * See https://openrdf.atlassian.net/browse/SES-2090 + */ @Test + @Ignore("ignored until fixed upstream") public void contextualInsertDeleteData() throws RepositoryException, MalformedQueryException, UpdateExecutionException { StringBuilder insert = new StringBuilder(); http://git-wip-us.apache.org/repos/asf/marmotta/blob/3753fe06/libraries/kiwi/kiwi-sparql/src/test/resources/org/apache/marmotta/kiwi/sparql/test/query24.sparql ---------------------------------------------------------------------- diff --git a/libraries/kiwi/kiwi-sparql/src/test/resources/org/apache/marmotta/kiwi/sparql/test/query24.sparql b/libraries/kiwi/kiwi-sparql/src/test/resources/org/apache/marmotta/kiwi/sparql/test/query24.sparql new file mode 100644 index 0000000..c562dac --- /dev/null +++ b/libraries/kiwi/kiwi-sparql/src/test/resources/org/apache/marmotta/kiwi/sparql/test/query24.sparql @@ -0,0 +1,24 @@ +# +# 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. +# +PREFIX foaf: <http://xmlns.com/foaf/0.1/> +PREFIX dc: <http://purl.org/dc/elements/1.1/> + +SELECT ?p1 ?fn ?age WHERE { + ?p1 foaf:name ?fn . + ?p1 foaf:age ?age +} ORDER BY DESC(?fn) ASC(xsd:integer(?age)) \ No newline at end of file
