Strabon
changeset 1167:bae12a2322e4 temporals
cloned behaviour of the SpatialJoinOptimizer to apply for the temporal case too, in order to avoid the production of cartesian products in temporal joins
| author | Konstantina Bereta <Konstantina.Bereta@di.uoa.gr> |
|---|---|
| date | Fri May 10 16:03:20 2013 +0300 (2013-05-10) |
| parents | 1d3afe469324 |
| children | c003d2c1a053 |
| files | evaluation/src/main/java/org/openrdf/query/algebra/evaluation/impl/TemporalJoinOptimizer.java generaldb/src/main/java/org/openrdf/sail/generaldb/optimizers/GeneralDBQueryOptimizer.java generaldb/src/main/java/org/openrdf/sail/generaldb/optimizers/GeneralDBSelectQueryOptimizer.java runtime/src/test/resources/temporal-periods.nq |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/evaluation/src/main/java/org/openrdf/query/algebra/evaluation/impl/TemporalJoinOptimizer.java Fri May 10 16:03:20 2013 +0300 1.3 @@ -0,0 +1,733 @@ 1.4 +/** 1.5 + * This Source Code Form is subject to the terms of the Mozilla Public 1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this 1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. 1.8 + * 1.9 + * Copyright (C) 2010, 2011, 2012, Pyravlos Team 1.10 + * 1.11 + * http://www.strabon.di.uoa.gr/ 1.12 + */ 1.13 +package org.openrdf.query.algebra.evaluation.impl; 1.14 + 1.15 +import java.util.ArrayList; 1.16 +import java.util.HashMap; 1.17 +import java.util.Iterator; 1.18 +import java.util.LinkedHashSet; 1.19 +import java.util.List; 1.20 +import java.util.Map; 1.21 +import java.util.Set; 1.22 + 1.23 +import org.openrdf.query.BindingSet; 1.24 +import org.openrdf.query.Dataset; 1.25 +import org.openrdf.query.algebra.Compare; 1.26 +import org.openrdf.query.algebra.Extension; 1.27 +import org.openrdf.query.algebra.Filter; 1.28 +import org.openrdf.query.algebra.FunctionCall; 1.29 +import org.openrdf.query.algebra.Join; 1.30 +import org.openrdf.query.algebra.LeftJoin; 1.31 +import org.openrdf.query.algebra.MathExpr; 1.32 +import org.openrdf.query.algebra.Or; 1.33 +import org.openrdf.query.algebra.QueryModelNode; 1.34 +import org.openrdf.query.algebra.StatementPattern; 1.35 +import org.openrdf.query.algebra.StatementPattern.Scope; 1.36 +import org.openrdf.query.algebra.TupleExpr; 1.37 +import org.openrdf.query.algebra.ValueExpr; 1.38 +import org.openrdf.query.algebra.Var; 1.39 +import org.openrdf.query.algebra.evaluation.function.Function; 1.40 +import org.openrdf.query.algebra.evaluation.function.FunctionRegistry; 1.41 +import org.openrdf.query.algebra.evaluation.function.temporal.stsparql.relation.TemporalRelationFunc; 1.42 +import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; 1.43 +import org.openrdf.query.algebra.helpers.StatementPatternCollector; 1.44 + 1.45 +/** 1.46 + * A query optimizer that re-orders nested Joins. 1.47 + * 1.48 + * @author Manos Karpathiotakis <mk@di.uoa.gr> 1.49 + */ 1.50 +public class TemporalJoinOptimizer 1.51 +//implements QueryOptimizer //Removed it consciously 1.52 +{ 1.53 + 1.54 + 1.55 + //private Set<String> existingVars = new TreeSet<String>(); 1.56 + /** 1.57 + * Applies generally applicable optimizations: path expressions are sorted 1.58 + * from more to less specific. 1.59 + * 1.60 + * @param tupleExpr 1.61 + */ 1.62 + public void optimize(TupleExpr tupleExpr, Dataset dataset, BindingSet bindings, List<TupleExpr> temporalJoins) { 1.63 + tupleExpr.visit(new JoinVisitor(temporalJoins)); 1.64 + } 1.65 + 1.66 + protected class JoinVisitor extends QueryModelVisitorBase<RuntimeException> { 1.67 + 1.68 + 1.69 + 1.70 + public JoinVisitor(List<TupleExpr> temporalJoins) { 1.71 + super(); 1.72 + this.temporalJoins = temporalJoins; 1.73 + } 1.74 + 1.75 + 1.76 + private List<TupleExpr> temporalJoins; 1.77 + //buffer with a var as a second argument 1.78 + private boolean problematicBuffer = false; 1.79 + 1.80 + //indicates whether a metric expression contains a temporal function call 1.81 + private boolean containsTemporal = false; 1.82 + private boolean optimizableMetricOrProperty = true; 1.83 + 1.84 + private int thematicJoinsSize = 0; 1.85 + 1.86 + 1.87 + Map<TupleExpr, List<Var>> temporalFilters = new HashMap<TupleExpr, List<Var>>(); 1.88 + 1.89 + @Override 1.90 + public void meet(Join node) { 1.91 + 1.92 + //XXX NOTE: NOT OPTIMIZING CONTENTS OF OPTIONAL CLAUSE!!! 1.93 + //Reason1: Errors occurred in the condition of the LeftJoin containing the optional subgraph 1.94 + 1.95 + //Not as successful as I hoped. Some OPTIONAL clauses may pass 1.96 + if(parentIsOptional(node)) 1.97 + { 1.98 + return; 1.99 + } 1.100 + // if(node.getParentNode() instanceof LeftJoin) 1.101 + // { 1.102 + // return; 1.103 + // } 1.104 + 1.105 + // Recursively get the join arguments 1.106 + List<TupleExpr> joinArgs = getJoinArgs(node, new ArrayList<TupleExpr>()); 1.107 + 1.108 + if(joinArgs == null) 1.109 + { 1.110 + //2nd mechanism to avoid OPTIONAL clauses from passing 1.111 + return; 1.112 + } 1.113 + 1.114 + 1.115 + Map<TupleExpr, List<Var>> varsMap = new /*Linked*/HashMap<TupleExpr, List<Var>>(); 1.116 + 1.117 + for (TupleExpr tupleExpr : joinArgs) { 1.118 + varsMap.put(tupleExpr, getStatementPatternVars(tupleExpr)); 1.119 + 1.120 + } 1.121 + 1.122 + //Now I have all the info I need. Just need to structure it efficiently 1.123 + int allNodes = varsMap.size() + temporalFilters.size(); 1.124 + thematicJoinsSize = varsMap.size(); 1.125 + //careful with positions on the diagonal! Do not utilize them! 1.126 + int joinsGraph[][] = new int[allNodes][allNodes]; 1.127 + 1.128 + //prints for debug 1.129 + // Set<TupleExpr> allExprs = varsMap.keySet(); 1.130 + // System.out.println(allExprs.toString()); 1.131 + // 1.132 + // Set<TupleExpr> allFilters = temporalFilters.keySet(); 1.133 + // System.out.println(allFilters.toString()); 1.134 + 1.135 + //Thematic part first 1.136 + int i = 0; 1.137 + 1.138 + for(List<Var> listHorizontal : varsMap.values()) 1.139 + { 1.140 + int j = 0; 1.141 + int k = 0; 1.142 + 1.143 + //Other thematics 1.144 + for(List<Var> listVertical : varsMap.values()) 1.145 + { 1.146 + if(i==j) 1.147 + { 1.148 + j++; 1.149 + continue; 1.150 + } 1.151 + 1.152 + 1.153 + joinsGraph[i][j] = sameVar(listHorizontal, listVertical); 1.154 + 1.155 + j++; 1.156 + } 1.157 + 1.158 + //Temporals 1.159 + for(List<Var> listVertical : temporalFilters.values()) 1.160 + { 1.161 + 1.162 + joinsGraph[i][k+varsMap.size()] = sameVar(listHorizontal, listVertical); 1.163 + 1.164 + k++; 1.165 + } 1.166 + 1.167 + i++; 1.168 + } 1.169 + 1.170 + //Now for the temporal horizontal nodes 1.171 + i = varsMap.size(); 1.172 + for(List<Var> listHorizontal : temporalFilters.values()) 1.173 + { 1.174 + int j = 0; 1.175 + int k = 0; 1.176 + 1.177 + //Other thematics 1.178 + for(List<Var> listVertical : varsMap.values()) 1.179 + { 1.180 + 1.181 + joinsGraph[i][j] = sameVar(listHorizontal, listVertical); 1.182 + 1.183 + j++; 1.184 + } 1.185 + 1.186 + //Temporals 1.187 + for(List<Var> listVertical : temporalFilters.values()) 1.188 + { 1.189 + if(i==k+varsMap.size()) 1.190 + { 1.191 + k++; 1.192 + continue; 1.193 + } 1.194 + 1.195 + joinsGraph[i][k+varsMap.size()] =sameVar(listHorizontal, listVertical); 1.196 + 1.197 + k++; 1.198 + } 1.199 + 1.200 + i++; 1.201 + } 1.202 + 1.203 + //Checking graph to be sure 1.204 + /* 1.205 + for(int a = 0; a < allNodes; a++) 1.206 + { 1.207 + for(int b = 0; b < allNodes; b++) 1.208 + { 1.209 + System.out.print(joinsGraph[a][b]+" "); 1.210 + 1.211 + } 1.212 + System.out.println(""); 1.213 + } 1.214 + */ 1.215 + 1.216 + //Time to construct ordered sequence of joins + filters 1.217 + List<TupleExpr> orderedJoinArgs = new ArrayList<TupleExpr>(allNodes); 1.218 + //maybe I won't need all the positions -> some temporal joins may not be utilized 1.219 + List<Integer> tempList = new ArrayList<Integer>(allNodes); 1.220 + List<Integer> pathList = new ArrayList<Integer>(); 1.221 + List<Integer> finalList = new ArrayList<Integer>(); 1.222 + Set<Var> varsTillNow = new LinkedHashSet<Var>(); 1.223 + for(int row = 0 ; row < allNodes ; row++) 1.224 + { 1.225 + tempList.add(row); 1.226 + createOrderedJoins(joinsGraph, row, row, 1, varsTillNow, tempList, pathList, finalList); 1.227 + pathList.clear(); 1.228 + if(finalList.size() == allNodes) 1.229 + { 1.230 + break; 1.231 + } 1.232 + 1.233 + } 1.234 + 1.235 + /* 1.236 + System.out.println("*--REWRITTEN TREE--**"); 1.237 + System.out.println(finalList.toString()); 1.238 + */ 1.239 + 1.240 + int varsMapSize = varsMap.size(); 1.241 + for(Integer position : finalList) 1.242 + { 1.243 + if(position<varsMapSize)//thematic! 1.244 + { 1.245 + int count = 0; 1.246 + Iterator it = varsMap.entrySet().iterator(); 1.247 + 1.248 + while (it.hasNext()) 1.249 + { 1.250 + { 1.251 + Map.Entry entry = (Map.Entry)it.next(); 1.252 + if(count == position) 1.253 + { 1.254 + orderedJoinArgs.add((TupleExpr) entry.getKey()); 1.255 + 1.256 + it.remove(); 1.257 + varsMapSize--; 1.258 + 1.259 + for(int fix = 0 ; fix < finalList.size(); fix++) 1.260 + { 1.261 + if(finalList.get(fix) > position) 1.262 + { 1.263 + int reduced = finalList.get(fix) - 1; 1.264 + finalList.set(fix, reduced); 1.265 + 1.266 + } 1.267 + } 1.268 + break; 1.269 + } 1.270 + count++; 1.271 + } 1.272 + } 1.273 + } 1.274 + else//temporal! 1.275 + { 1.276 + int count = 0; 1.277 + Iterator it = temporalFilters.entrySet().iterator(); 1.278 + while (it.hasNext()) 1.279 + { 1.280 + { 1.281 + Map.Entry entry = (Map.Entry)it.next(); 1.282 + if(count == position - varsMapSize) 1.283 + { 1.284 + //If I keep record of this entry, I can use the info later to avoid duplicate filters 1.285 + temporalJoins.add((TupleExpr) entry.getKey()); 1.286 + // 1.287 + orderedJoinArgs.add((TupleExpr) entry.getKey()); 1.288 + it.remove(); 1.289 + for(int fix = 0 ; fix < finalList.size(); fix++) 1.290 + { 1.291 + if(finalList.get(fix) > position) 1.292 + { 1.293 + int reduced = finalList.get(fix) - 1; 1.294 + finalList.set(fix, reduced); 1.295 + } 1.296 + } 1.297 + break; 1.298 + } 1.299 + count++; 1.300 + } 1.301 + } 1.302 + } 1.303 + 1.304 + } 1.305 + //Must take care of the remainders as well! 1.306 + Iterator it = varsMap.entrySet().iterator(); 1.307 + while (it.hasNext()) 1.308 + { 1.309 + Map.Entry entry = (Map.Entry)it.next(); 1.310 + orderedJoinArgs.add((TupleExpr) entry.getKey()); 1.311 + it.remove(); 1.312 + } 1.313 + 1.314 + TupleExpr replacement = orderedJoinArgs.get(0); 1.315 + for (int ii = 1; ii < orderedJoinArgs.size(); ii++) { 1.316 + replacement = new Join(replacement, orderedJoinArgs.get(ii)); 1.317 + } 1.318 + 1.319 + // Replace old join hierarchy 1.320 + node.replaceWith(replacement); 1.321 + 1.322 + } 1.323 + 1.324 + 1.325 + public boolean parentIsOptional(QueryModelNode node) 1.326 + { 1.327 + if(node.getParentNode() == null) 1.328 + { 1.329 + return false; 1.330 + } 1.331 + else if(node.getParentNode() instanceof LeftJoin) 1.332 + { 1.333 + return true; 1.334 + } 1.335 + else 1.336 + { 1.337 + return parentIsOptional(node.getParentNode()); 1.338 + } 1.339 + } 1.340 + 1.341 + /** 1.342 + * General Comment: If more than one function exists in the query and can be used to perform the join, no preference is shown 1.343 + * on which function will actually be used for this purpose. This could cause an issue if ST_Disjoint is the one finally used, 1.344 + * as the index won't be used for the evaluation in this case. Perhaps I should include some 'priority' 1.345 + */ 1.346 + @Override 1.347 + public void meet(Filter node) { 1.348 + 1.349 + /** 1.350 + * Filter node must not be in OPTIONAL clause! 1.351 + * After all, unneeded check. If an optional exists, the 'Filter' tuple expression 1.352 + * is removed and only the Function Calls remain 1.353 + */ 1.354 + if(!withinHaving(node)) 1.355 + { 1.356 + //if(!(node.getParentNode() instanceof LeftJoin)) 1.357 + //{ 1.358 + //XXX Ignore OR in Filters for now! (perhaps permanently) 1.359 + if(!(node.getCondition() instanceof Or)) 1.360 + { 1.361 + if(node.getCondition() instanceof FunctionCall) 1.362 + { 1.363 + //Only interested in temporal ones 1.364 + if(isRelevantTemporalFunc((FunctionCall) node.getCondition())) 1.365 + { 1.366 + //Have to retrieve all nested variables and other info 1.367 + 1.368 + //1.Retrieve varNames 1.369 + List<Var> varList = getFunctionCallVars((FunctionCall) node.getCondition()); 1.370 + 1.371 + //Cannot optimize buffer constructs when their 2nd argument is a 1.372 + //thematic var, because I can't manipulate the order of the 1.373 + //numeric_values table 1.374 + if(!problematicBuffer) 1.375 + { 1.376 + //XXX I cannot process cases involving more than 2 arguments in the temporal join! 1.377 + // They transcend the theta join level! 1.378 + // if(varList.size()<3) 1.379 + 1.380 + //if the arguments are not 2, I am essentially doing a selection! 1.381 + //No reason to push into optimizer then 1.382 + if(varList.size()==2) 1.383 + { 1.384 + //Add all important info about this temporal relationship to the appropriate structure 1.385 + //temporalFilters.add(new TemporalFilterInfo(varList, (FunctionCall) node.getCondition())); 1.386 + Filter toEnter = node.clone(); 1.387 + 1.388 + /** 1.389 + * VERY CAREFUL HERE! 1.390 + * Reason I did this: If not, I would carry a copy of the whole expression for 1.391 + * every extra filter of my query! 1.392 + * -DUMMY-!!! 1.393 + */ 1.394 + StatementPattern t = new StatementPattern(); 1.395 + t.setSubjectVar(new Var("-dummy-temporal")); 1.396 + t.setPredicateVar(new Var("-dummy-temporal")); 1.397 + t.setObjectVar(new Var("-dummy-temporal")); 1.398 + t.setScope(Scope.DEFAULT_CONTEXTS); 1.399 + toEnter.setArg(t); 1.400 + 1.401 + if(!temporalFilters.containsKey(toEnter)) 1.402 + { 1.403 + temporalFilters.put(toEnter,varList); 1.404 + } 1.405 + } 1.406 + problematicBuffer = false; 1.407 + } 1.408 + } 1.409 + } 1.410 + //Metrics 1.411 + //I have a similar problematic case with the one occurring in Buffer! 1.412 + //Cannot manipulate the join order when I am dealing with numerics! 1.413 + //Therefore, I cannot use a numeric field (a numeric var) to alter the join sequence 1.414 + else if(node.getCondition() instanceof Compare) 1.415 + { 1.416 + containsTemporal = false; 1.417 + List<Var> allVars = new ArrayList<Var>(getVarsInMetricOrProperty(node.getCondition())); 1.418 + if(containsTemporal&&optimizableMetricOrProperty) 1.419 + { 1.420 + //if the arguments are not 2, I am essentially doing a selection! 1.421 + //No reason to push into optimizer then 1.422 + if(allVars.size()==2) 1.423 + //if(allVars.size()<3) 1.424 + { 1.425 + //Add all important info about this temporal relationship to the appropriate structure 1.426 + //temporalFilters.add(new TemporalFilterInfo(varList, (FunctionCall) node.getCondition())); 1.427 + Filter toEnter = node.clone(); 1.428 + 1.429 + StatementPattern t = new StatementPattern(); 1.430 + t.setSubjectVar(new Var("-dummy-")); 1.431 + t.setPredicateVar(new Var("-dummy-")); 1.432 + t.setObjectVar(new Var("-dummy-")); 1.433 + t.setScope(Scope.DEFAULT_CONTEXTS); 1.434 + toEnter.setArg(t); 1.435 + 1.436 + if(!temporalFilters.containsKey(toEnter)) 1.437 + { 1.438 + temporalFilters.put(toEnter,allVars); 1.439 + } 1.440 + } 1.441 + containsTemporal = false; 1.442 + } 1.443 + optimizableMetricOrProperty = true; 1.444 + } 1.445 + 1.446 + } 1.447 + //} 1.448 + } 1.449 + 1.450 + //Last thing to do is ensuring the entire tree is traversed 1.451 + node.visitChildren(this); 1.452 + 1.453 + } 1.454 + 1.455 + 1.456 + /** 1.457 + * Helper Functions 1.458 + */ 1.459 + 1.460 + /** 1.461 + * Used to find out whether the Filter expr we are currently visiting is located inside 1.462 + * a HAVING clause. 1.463 + * 1.464 + * From what I have seen so far, it seems that if this is the case, its arg (or one of the following FILTER args in 1.465 + * the case of disjunction/conjunction) will be an Extension expr followed by a GROUP expr 1.466 + */ 1.467 + private boolean withinHaving(Filter expr) 1.468 + { 1.469 + if(expr.getArg() instanceof Extension) 1.470 + { 1.471 + return true; 1.472 + } 1.473 + else if(expr.getArg() instanceof Filter) 1.474 + { 1.475 + return withinHaving((Filter) expr.getArg()); 1.476 + } 1.477 + else 1.478 + { 1.479 + return false; 1.480 + } 1.481 + } 1.482 + 1.483 + private <L extends List<TupleExpr>> L getJoinArgs(TupleExpr tupleExpr, L joinArgs) { 1.484 + if (tupleExpr instanceof Join) { 1.485 + Join join = (Join)tupleExpr; 1.486 + if(getJoinArgs(join.getLeftArg(), joinArgs) == null) 1.487 + return null; 1.488 + if(getJoinArgs(join.getRightArg(), joinArgs) == null) 1.489 + return null; 1.490 + } 1.491 + else if(tupleExpr instanceof LeftJoin) 1.492 + { 1.493 + //Trying to avoid OPTIONAL clauses from passing 1.494 + return null; 1.495 + } 1.496 + else 1.497 + { 1.498 + joinArgs.add(tupleExpr); 1.499 + } 1.500 + 1.501 + return joinArgs; 1.502 + } 1.503 + 1.504 + private List<Var> getStatementPatternVars(TupleExpr tupleExpr) { 1.505 + List<StatementPattern> stPatterns = StatementPatternCollector.process(tupleExpr); 1.506 + List<Var> varList = new ArrayList<Var>(stPatterns.size() * 4); 1.507 + for (StatementPattern sp : stPatterns) { 1.508 + sp.getVars(varList); 1.509 + } 1.510 + return varList; 1.511 + } 1.512 + 1.513 + /** 1.514 + * temporalContent: Used to declare that this expression does include some temporal 1.515 + * content and an attempt should be made to use it in the joins' optimization process 1.516 + */ 1.517 + private Set<Var> getVarsInMetricOrProperty(ValueExpr expr) 1.518 + { 1.519 + Set<Var> allVars = new LinkedHashSet<Var>(); 1.520 + 1.521 + if(expr instanceof Compare) 1.522 + { 1.523 + allVars.addAll(getVarsInMetricOrProperty(((Compare) expr).getLeftArg())); 1.524 + allVars.addAll(getVarsInMetricOrProperty(((Compare) expr).getRightArg())); 1.525 + } 1.526 + else if(expr instanceof MathExpr) 1.527 + { 1.528 + allVars.addAll(getVarsInMetricOrProperty(((MathExpr) expr).getLeftArg())); 1.529 + allVars.addAll(getVarsInMetricOrProperty(((MathExpr) expr).getRightArg())); 1.530 + } 1.531 + else if(expr instanceof FunctionCall ) 1.532 + { 1.533 + if(isRelevantTemporalFunc((FunctionCall) expr)) 1.534 + { 1.535 + /** 1.536 + * There is a point in continuing the search recursively ONLY 1.537 + * if I reach this case. Otherwise, the function call 1.538 + * may not refer to a temporal function 1.539 + */ 1.540 + this.containsTemporal = true; 1.541 + allVars.addAll(getFunctionCallVars((FunctionCall) expr)); 1.542 + 1.543 + } 1.544 + } 1.545 + else if(expr instanceof Var) 1.546 + { 1.547 + if(!(expr.getParentNode() instanceof FunctionCall)) 1.548 + { 1.549 + //Cannot manipulate the join order when I am dealing with numerics! 1.550 + //Therefore, I cannot use a numeric field (a numeric var) to alter the join sequence 1.551 + this.optimizableMetricOrProperty = false; 1.552 + } 1.553 + if(!allVars.contains(expr)) 1.554 + { 1.555 + allVars.add((Var) expr); 1.556 + } 1.557 + } 1.558 + 1.559 + return allVars; 1.560 + } 1.561 + 1.562 + private boolean isRelevantTemporalFunc(FunctionCall functionCall) 1.563 + { 1.564 + Function function = FunctionRegistry.getInstance().get(functionCall.getURI()); 1.565 + if(function instanceof org.openrdf.query.algebra.evaluation.function.temporal.stsparql.construct.TemporalConstructFunc ) 1.566 + { 1.567 + //TODO may have to comment this part again 1.568 + //uncommented because I use this function in the case of metrics 1.569 + return true; 1.570 + } 1.571 + else if(function instanceof TemporalRelationFunc) 1.572 + { 1.573 + return true; 1.574 + } 1.575 + return false; 1.576 + } 1.577 + 1.578 + private List<Var> getFunctionCallVars(FunctionCall functionCall) { 1.579 + List<Var> varList = new ArrayList<Var>(); 1.580 + int argList = 0; 1.581 + for(ValueExpr expr : functionCall.getArgs()) 1.582 + { 1.583 + argList++; 1.584 + if(expr instanceof Var) 1.585 + { 1.586 + // if(!existingVars.contains(((Var) expr).getName())) 1.587 + // { 1.588 + // existingVars.add(((Var) expr).getName()); 1.589 + // } 1.590 + 1.591 + if(!varList.contains(expr)) 1.592 + { 1.593 + //Was using this code when I tried to incorporate the Buffer case buffer(?Temporal,?thematic) 1.594 + if(argList == 2 && functionCall.getURI().equals("http://strdf.di.uoa.gr/ontology#buffer")) 1.595 + { 1.596 + problematicBuffer = true; 1.597 + } 1.598 + varList.add((Var) expr); 1.599 + } 1.600 + 1.601 + } 1.602 + else if(expr instanceof FunctionCall) 1.603 + { 1.604 + varList.addAll(getFunctionCallVars((FunctionCall) expr)); 1.605 + } 1.606 + //TODO Should I add any additional cases? I don't think so 1.607 + else 1.608 + { 1.609 + continue; 1.610 + } 1.611 + } 1.612 + return varList; 1.613 + } 1.614 + 1.615 + /** 1.616 + * Both lists belong to either a thematic node (St.Pattern) or a temporal node (Filter) 1.617 + * Comparing the vars with each other to discover links of the query graph 1.618 + * @param list1 1.619 + * @param list2 1.620 + * @return 1.621 + */ 1.622 + private int sameVar(List<Var> list1, List<Var> list2) 1.623 + { 1.624 + for(Var var : list1) 1.625 + { 1.626 + if(list2.contains(var)) 1.627 + { 1.628 + return 1; 1.629 + } 1.630 + } 1.631 + 1.632 + return 0; 1.633 + } 1.634 + 1.635 + 1.636 + 1.637 + 1.638 + 1.639 + //Input: a single line of the table 1.640 + //NOTE: NO LOOPS! CAREFUL!! 1.641 + private boolean createOrderedJoins(int table[][], int lineToScan,int columnToSkip, 1.642 + int pathLen, Set<Var> varsTillNow, List<Integer> tempList, List<Integer> pathList, List<Integer> finalList) 1.643 + { 1.644 + boolean success = false; 1.645 + int dims = table.length; 1.646 + 1.647 + int j; 1.648 + 1.649 + //dims: all arguments 1.650 + for(j = 0; j < dims; j++) 1.651 + { 1.652 + if(j == columnToSkip) 1.653 + { 1.654 + continue; 1.655 + } 1.656 + 1.657 + //A connection exists! 1.658 + if(table[lineToScan][j]>0) 1.659 + { 1.660 + //Don't want my graph to have circles!!! 1.661 + if(!tempList.contains(j)&&!pathList.contains(j)) 1.662 + { 1.663 + if(j >= thematicJoinsSize) //aka if(temporalFilters.size() > 0) 1.664 + { 1.665 + List<Var> thisFilterVars = null; 1.666 + int count = 0; 1.667 + for(List<Var> vars : temporalFilters.values()) 1.668 + { 1.669 + if(count == j - thematicJoinsSize) 1.670 + { 1.671 + thisFilterVars = vars; 1.672 + break; 1.673 + } 1.674 + count++; 1.675 + } 1.676 + if(!varsTillNow.isEmpty()) 1.677 + { 1.678 + if(varsTillNow.containsAll(thisFilterVars)) 1.679 + { 1.680 + continue; 1.681 + } 1.682 + } 1.683 + 1.684 + //varsTillNow.add(thisFilterVars.get(1)); 1.685 + varsTillNow.addAll(thisFilterVars); 1.686 + 1.687 + } 1.688 + 1.689 + tempList.add((Integer)j); 1.690 + pathLen++; 1.691 + if(pathLen == dims) 1.692 + { 1.693 + //End of recursion 1.694 + pathList.addAll(tempList); 1.695 + tempList.clear(); 1.696 + finalList.clear(); 1.697 + finalList.addAll(pathList); 1.698 + 1.699 + return true; 1.700 + } 1.701 + 1.702 + //Recurse 1.703 + success = createOrderedJoins(table, j, lineToScan, pathLen, varsTillNow, tempList, pathList, finalList); 1.704 + 1.705 + //Success = true => recursion ended with pathLen = maxLen 1.706 + if(success) 1.707 + { 1.708 + return true; 1.709 + } 1.710 + else 1.711 + { 1.712 + //end of a path originating from this node was found -> find an additional path (if exists) 1.713 + continue; 1.714 + } 1.715 + } 1.716 + } 1.717 + } 1.718 + //To reach this place means the end of a path was found 1.719 + pathList.addAll(tempList); 1.720 + tempList.clear(); 1.721 + if(pathList.size() > finalList.size()) 1.722 + { 1.723 + finalList.clear(); 1.724 + finalList.addAll(pathList); 1.725 + if(finalList.size() == dims) 1.726 + { 1.727 + return true; 1.728 + } 1.729 + } 1.730 + return false; 1.731 + } 1.732 + 1.733 + } 1.734 + 1.735 + 1.736 +}
2.1 --- a/generaldb/src/main/java/org/openrdf/sail/generaldb/optimizers/GeneralDBQueryOptimizer.java Thu May 09 14:46:55 2013 +0300 2.2 +++ b/generaldb/src/main/java/org/openrdf/sail/generaldb/optimizers/GeneralDBQueryOptimizer.java Fri May 10 16:03:20 2013 +0300 2.3 @@ -19,6 +19,7 @@ 2.4 import org.openrdf.query.algebra.evaluation.impl.DisjunctiveConstraintOptimizer; 2.5 import org.openrdf.query.algebra.evaluation.impl.SameTermFilterOptimizer; 2.6 import org.openrdf.query.algebra.evaluation.impl.SpatialJoinOptimizer; 2.7 +import org.openrdf.query.algebra.evaluation.impl.TemporalJoinOptimizer; 2.8 import org.openrdf.query.algebra.evaluation.impl.stSPARQLConstantOptimizer; 2.9 import org.openrdf.sail.generaldb.GeneralDBValueFactory; 2.10 import org.openrdf.sail.generaldb.schema.BNodeTable; 2.11 @@ -47,6 +48,10 @@ 2.12 2.13 //Addition to locate duplicate filters caused by the SpatialJoinOptimizer 2.14 List<TupleExpr> spatialJoins = new ArrayList<TupleExpr>(); 2.15 + 2.16 + //same applies for temporal joins 2.17 + List<TupleExpr> temporalJoins = new ArrayList<TupleExpr>(); 2.18 + 2.19 // 2.20 2.21 public void setSelectQueryOptimizerFactory(GeneralDBSelectQueryOptimizerFactory factory) { 2.22 @@ -112,13 +117,16 @@ 2.23 new SameTermFilterOptimizer().optimize(expr, dataset, bindings); 2.24 2.25 //XXX 2.26 - //new SpatialJoinOptimizer().optimize(expr, dataset, bindings,spatialJoins); 2.27 + new SpatialJoinOptimizer().optimize(expr, dataset, bindings,spatialJoins); 2.28 + 2.29 + new TemporalJoinOptimizer().optimize(expr, dataset, bindings, temporalJoins); 2.30 } 2.31 2.32 protected void rdbmsOptimizations(TupleExpr expr, Dataset dataset, BindingSet bindings) { 2.33 new GeneralDBValueIdLookupOptimizer(vf).optimize(expr, dataset, bindings); 2.34 - factory.createRdbmsFilterOptimizer().optimize(expr, dataset, bindings,spatialJoins); 2.35 + factory.createRdbmsFilterOptimizer().optimize(expr, dataset, bindings,spatialJoins, temporalJoins); 2.36 this.spatialJoins.clear(); 2.37 + this.temporalJoins.clear(); 2.38 new GeneralDBVarColumnLookupOptimizer().optimize(expr, dataset, bindings); 2.39 GeneralDBValueJoinOptimizer valueJoins = new GeneralDBValueJoinOptimizer(); 2.40 valueJoins.setBnodeTable(bnodes);
3.1 --- a/generaldb/src/main/java/org/openrdf/sail/generaldb/optimizers/GeneralDBSelectQueryOptimizer.java Thu May 09 14:46:55 2013 +0300 3.2 +++ b/generaldb/src/main/java/org/openrdf/sail/generaldb/optimizers/GeneralDBSelectQueryOptimizer.java Fri May 10 16:03:20 2013 +0300 3.3 @@ -9,12 +9,15 @@ 3.4 import static org.openrdf.sail.generaldb.algebra.GeneralDBColumnVar.createObj; 3.5 import static org.openrdf.sail.generaldb.algebra.GeneralDBColumnVar.createPred; 3.6 import static org.openrdf.sail.generaldb.algebra.GeneralDBColumnVar.createSpatialColumn; 3.7 +import static org.openrdf.sail.generaldb.algebra.GeneralDBColumnVar.createTemporalColumn; 3.8 import static org.openrdf.sail.generaldb.algebra.GeneralDBColumnVar.createSubj; 3.9 import static org.openrdf.sail.generaldb.algebra.base.GeneralDBExprSupport.coalesce; 3.10 import static org.openrdf.sail.generaldb.algebra.base.GeneralDBExprSupport.eq; 3.11 import static org.openrdf.sail.generaldb.algebra.base.GeneralDBExprSupport.isNull; 3.12 import static org.openrdf.sail.generaldb.algebra.base.GeneralDBExprSupport.or; 3.13 3.14 +import info.aduna.lang.service.ServiceRegistry; 3.15 + 3.16 import java.sql.SQLException; 3.17 import java.util.ArrayList; 3.18 import java.util.HashMap; 3.19 @@ -157,6 +160,8 @@ 3.20 private GeneralDBColumnVar previousTemporalArg = null; 3.21 private GeneralDBColumnVar previousTemporalAlias; 3.22 3.23 + private List<Var> existingTemporalJoins = new ArrayList<Var>(); 3.24 + 3.25 3.26 /** 3.27 * 3.28 @@ -178,6 +183,8 @@ 3.29 3.30 private IdSequence ids; 3.31 3.32 + private List<TupleExpr> temporalJoins; 3.33 + 3.34 public void setSqlExprFactory(GeneralDBSqlExprFactory sql) { 3.35 this.sql = sql; 3.36 } 3.37 @@ -194,10 +201,11 @@ 3.38 this.ids = ids; 3.39 } 3.40 3.41 - public void optimize(TupleExpr tupleExpr, Dataset dataset, BindingSet bindings, List<TupleExpr> spatialJoins) { 3.42 + public void optimize(TupleExpr tupleExpr, Dataset dataset, BindingSet bindings, List<TupleExpr> spatialJoins, List<TupleExpr> temporalJoins) { 3.43 this.dataset = dataset; 3.44 this.bindings = bindings; 3.45 this.spatialJoins = spatialJoins; 3.46 + this.temporalJoins = temporalJoins; 3.47 tupleExpr.visit(this); 3.48 } 3.49 3.50 @@ -593,6 +601,28 @@ 3.51 break; 3.52 // } 3.53 } 3.54 + else if(var.getName().equals(previousAlias.getName())) 3.55 + { 3.56 + existingSpatialJoins.add(var); 3.57 + queries[count] = new GeneralDBSelectQuery(); 3.58 + Value objValue = getVarValue(var,bindings); 3.59 + 3.60 + //any changes in these two lines could cause problems 3.61 + GeneralDBColumnVar colVar = createSpatialColumn("l_"+var.getName(), var, objValue); 3.62 + GeneralDBJoinItem from = new GeneralDBJoinItem("l_"+var.getName(), "geo_values"); 3.63 + 3.64 + queries[count].setFrom(from); 3.65 + 3.66 + //assuming that only one var will reach this case 3.67 + from.addFilter(new GeneralDBSqlEq(new GeneralDBIdColumn(colVar), new GeneralDBIdColumn(previousAlias))); 3.68 + 3.69 + //Copying functionality from meet(StatementPattern) 3.70 + GeneralDBSelectProjection proj = new GeneralDBSelectProjection(); 3.71 + proj.setVar(colVar); 3.72 + proj.setId(new GeneralDBRefIdColumn(var)); 3.73 + break; 3.74 + // } 3.75 + } 3.76 count++; 3.77 } 3.78 mark = (count+1)%2; 3.79 @@ -726,6 +756,140 @@ 3.80 //node.replaceWith(queries[j]); 3.81 3.82 } 3.83 + else if(st.getSubjectVar().getName().equals("-dummy-temporal")) 3.84 + { 3.85 + 3.86 + //Spatial join 3.87 + 3.88 + // List<Var> allVars = retrieveVars(node.getCondition()); 3.89 + List<Var> allVars = new ArrayList<Var>(retrieveVars(node.getCondition())); 3.90 + GeneralDBSelectQuery queries[] = new GeneralDBSelectQuery[allVars.size()]; 3.91 + 3.92 + int count = 0; 3.93 + 3.94 + //will probably be TWO contents at most in all cases concerning spatial filters here - have to make sure of that 3.95 + //Don't know which one of the spatial variables is bound with the upper join! Therefore, I altered the code to check 3.96 + //for the possibility any of them is the one. 3.97 + int mark = 0; 3.98 + //FIXME remove the list after consulting Kostis for certainty, and replace with table[2] 3.99 + if(allVars.size()>1) 3.100 + { 3.101 + for(Var var : allVars) 3.102 + { 3.103 + if(var.getName().equals(previousTemporalAlias.getName())) 3.104 + { 3.105 + 3.106 + // if(var.getName().endsWith("?-buffer-")) 3.107 + // { 3.108 + // bufferCase = true; 3.109 + // fixVarName(var); 3.110 + // 3.111 + // existingSpatialJoins.add(var); 3.112 + // queries[count] = new GeneralDBSelectQuery(); 3.113 + // Value objValue = getVarValue(var,bindings); 3.114 + // 3.115 + // GeneralDBColumnVar colVar = createObj("l_"+var.getName(), var, objValue); 3.116 + 3.117 + 3.118 + // } 3.119 + // else //DEFAULT CASE. The only case differentiating from this one is buffer(?spatialVar,?thematicVar) 3.120 + // { 3.121 + 3.122 + existingTemporalJoins.add(var); 3.123 + queries[count] = new GeneralDBSelectQuery(); 3.124 + Value objValue = getVarValue(var,bindings); 3.125 + 3.126 + //any changes in these two lines could cause problems 3.127 + GeneralDBColumnVar colVar = createSpatialColumn("l_"+var.getName(), var, objValue); 3.128 + GeneralDBJoinItem from = new GeneralDBJoinItem("l_"+var.getName(), "period_values"); 3.129 + 3.130 + queries[count].setFrom(from); 3.131 + 3.132 + //assuming that only one var will reach this case 3.133 + from.addFilter(new GeneralDBSqlEq(new GeneralDBIdColumn(colVar), new GeneralDBIdColumn(previousTemporalAlias))); 3.134 + 3.135 + //Copying functionality from meet(StatementPattern) 3.136 + GeneralDBSelectProjection proj = new GeneralDBSelectProjection(); 3.137 + proj.setVar(colVar); 3.138 + proj.setId(new GeneralDBRefIdColumn(var)); 3.139 + break; 3.140 + // } 3.141 + } 3.142 + else if(var.getName().equals(previousTemporalAlias.getName())) 3.143 + { 3.144 + existingTemporalJoins.add(var); 3.145 + queries[count] = new GeneralDBSelectQuery(); 3.146 + Value objValue = getVarValue(var,bindings); 3.147 + 3.148 + //any changes in these two lines could cause problems 3.149 + GeneralDBColumnVar colVar = createTemporalColumn("l_"+var.getName(), var, objValue); 3.150 + GeneralDBJoinItem from = new GeneralDBJoinItem("l_"+var.getName(), "period_values"); 3.151 + 3.152 + queries[count].setFrom(from); 3.153 + 3.154 + //assuming that only one var will reach this case 3.155 + from.addFilter(new GeneralDBSqlEq(new GeneralDBIdColumn(colVar), new GeneralDBIdColumn(previousTemporalAlias))); 3.156 + 3.157 + //Copying functionality from meet(StatementPattern) 3.158 + GeneralDBSelectProjection proj = new GeneralDBSelectProjection(); 3.159 + proj.setVar(colVar); 3.160 + proj.setId(new GeneralDBRefIdColumn(var)); 3.161 + break; 3.162 + // } 3.163 + } 3.164 + count++; 3.165 + } 3.166 + mark = (count+1)%2; 3.167 + } 3.168 + //The second var of the spatial join -> must incorporate the spatial filter here 3.169 + 3.170 + 3.171 + Var var = allVars.get(mark); 3.172 + existingTemporalJoins.add(var); 3.173 + queries[mark] = new GeneralDBSelectQuery(); 3.174 + Value objValue = getVarValue(var,bindings); 3.175 + 3.176 + //any changes in these two lines could cause problems 3.177 + GeneralDBColumnVar colVar = createTemporalColumn("l_"+var.getName(), var, objValue); 3.178 + GeneralDBJoinItem from = new GeneralDBJoinItem("l_"+var.getName(), "period_values"); 3.179 + queries[mark].setFrom(from); 3.180 + 3.181 + previousTemporalArg = colVar; 3.182 + 3.183 + 3.184 + super.meet(node); 3.185 + 3.186 + 3.187 + //Incorporating temporal filter 3.188 + ValueExpr condition = null; 3.189 + for (ValueExpr expr : flatten(node.getCondition())) 3.190 + { 3.191 + try 3.192 + { 3.193 + GeneralDBSqlExpr sqlFilter = sql.createBooleanExpr(expr); 3.194 + 3.195 + queries[mark].addFilter(sqlFilter); 3.196 + } 3.197 + catch (UnsupportedRdbmsOperatorException e) 3.198 + { 3.199 + if (condition == null) 3.200 + { 3.201 + condition = expr; 3.202 + } 3.203 + else 3.204 + { 3.205 + condition = new And(condition, expr); 3.206 + } 3.207 + } 3.208 + } 3.209 + 3.210 + queries[count].setParentNode(node.getParentNode()); 3.211 + 3.212 + node.replaceWith(queries[mark]); 3.213 + 3.214 + 3.215 + 3.216 + } 3.217 else 3.218 { 3.219 super.meet(node); 3.220 @@ -800,6 +964,15 @@ 3.221 break; 3.222 } 3.223 } 3.224 + for(TupleExpr sfilter : this.temporalJoins) 3.225 + { 3.226 + ValueExpr tmpExpr = ((Filter)sfilter).getCondition(); 3.227 + if(tmpExpr.equals(dupFunctionCall)) 3.228 + { 3.229 + dup = true; 3.230 + break; 3.231 + } 3.232 + } 3.233 3.234 super.meet(node); 3.235 if (node.getArg() instanceof GeneralDBSelectQuery) { 3.236 @@ -1676,7 +1849,7 @@ 3.237 { 3.238 //if(!((FunctionCall)expr).getURI().equals("http://strdf.di.uoa.gr/ontology#buffer") || argNo!=2 ) 3.239 //{ 3.240 - if(!existingSpatialJoins.contains(arg)) 3.241 + if(!existingSpatialJoins.contains(arg) && !existingTemporalJoins.contains(arg)) 3.242 { 3.243 //XXX note: this may cause error if the user intends to 3.244 //perform an operation such as ?GEO1 ~ ?GEO1. 3.245 @@ -1700,7 +1873,7 @@ 3.246 } 3.247 else if(expr instanceof Var) 3.248 { 3.249 - if(!existingSpatialJoins.contains(expr)) 3.250 + if(!existingSpatialJoins.contains(expr) && !existingTemporalJoins.contains(expr)) 3.251 { 3.252 //Want to find the UNIQUE names! 3.253 //if(!vars.contains(expr))
4.1 --- a/runtime/src/test/resources/temporal-periods.nq Thu May 09 14:46:55 2013 +0300 4.2 +++ b/runtime/src/test/resources/temporal-periods.nq Fri May 10 16:03:20 2013 +0300 4.3 @@ -5,7 +5,7 @@ 4.4 <http://example.org/item2> <http://example.org/value> "20"^^<http://www.w3.org/2001/XMLSchema#int> "[2012-11-19T12:41:00,2012-11-19T13:41:00]"^^<http://strdf.di.uoa.gr/ontology#period>. 4.5 <http://example.org/item1> <http://teleios.di.uoa.gr/ontologies/noaOntology.owl#hasGeometry> "POINT(1 0)"^^<http://strdf.di.uoa.gr/ontology#WKT> "[2012-11-19T12:41:00+02,2012-11-19T13:41:00]"^^<http://strdf.di.uoa.gr/ontology#period>. 4.6 <http://example.org/item2> <http://teleios.di.uoa.gr/ontologies/noaOntology.owl#hasGeometry> "POINT(2 0)"^^<http://strdf.di.uoa.gr/ontology#WKT> "[2012-11-19T12:41:00+02,2012-11-19T13:41:00]"^^<http://strdf.di.uoa.gr/ontology#period>. 4.7 -<http://example.org/item3> <http://teleios.di.uoa.gr/ontologies/noaOntology.owl#hasGeometry> "POINT(3 0)"^^<http://strdf.di.uoa.gr/ontology#WKT> "[2012-11-19t12:41:00+02,2012-11-19T13:41:00]"^^<http://strdf.di.uoa.gr/ontology#period>. 4.8 +<http://example.org/item3> <http://teleios.di.uoa.gr/ontologies/noaOntology.owl#hasGeometry> "POINT(3 0)"^^<http://strdf.di.uoa.gr/ontology#WKT> "[2012-11-19T12:41:00+02,2012-11-19T13:41:00]"^^<http://strdf.di.uoa.gr/ontology#period>. 4.9 <http://example.org/item1> <http://example.org/value> "10"^^<http://www.w3.org/2001/XMLSchema#int> "[2012-11-19T10:41:00,2012-11-19T11:41:00]"^^<http://strdf.di.uoa.gr/ontology#period>. 4.10 <http://example.org/item2> <http://example.org/value> "20"^^<http://www.w3.org/2001/XMLSchema#int> "[2012-11-19T10:41:00,2012-11-19T15:41:00]"^^<http://strdf.di.uoa.gr/ontology#period>. 4.11 <http://example.org/item4> <http://example.org/value> "20"^^<http://www.w3.org/2001/XMLSchema#int> "2012-01-19T10:41:00"^^<http://www.w3.org/2001/XMLSchema#dateTime> .