http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/5a03ef61/extras/indexing/src/main/java/mvm/rya/indexing/external/ExternalProcessor.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/external/ExternalProcessor.java b/extras/indexing/src/main/java/mvm/rya/indexing/external/ExternalProcessor.java deleted file mode 100644 index 2c6d924..0000000 --- a/extras/indexing/src/main/java/mvm/rya/indexing/external/ExternalProcessor.java +++ /dev/null @@ -1,726 +0,0 @@ -package mvm.rya.indexing.external; - -/* - * 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. - */ - - - -import java.util.ArrayList; -import java.util.Collection; -import java.util.HashSet; -import java.util.List; -import java.util.Map; -import java.util.Set; - -import mvm.rya.indexing.external.QueryVariableNormalizer.VarCollector; -import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; - -import org.openrdf.query.algebra.BindingSetAssignment; -import org.openrdf.query.algebra.Filter; -import org.openrdf.query.algebra.Join; -import org.openrdf.query.algebra.Projection; -import org.openrdf.query.algebra.QueryModelNode; -import org.openrdf.query.algebra.StatementPattern; -import org.openrdf.query.algebra.TupleExpr; -import org.openrdf.query.algebra.Var; -import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; -import org.openrdf.query.algebra.helpers.StatementPatternCollector; - -import com.google.common.collect.BiMap; -import com.google.common.collect.HashBiMap; -import com.google.common.collect.Lists; -import com.google.common.collect.Maps; -import com.google.common.collect.Sets; - -/** - * Processes a {@link TupleExpr} and replaces sets of elements in the tree with {@link ExternalTupleSet} objects. - */ -public class ExternalProcessor { - - private List<ExternalTupleSet> indexSet; - - public ExternalProcessor(List<ExternalTupleSet> indexSet) { - this.indexSet = indexSet; - } - - /** - * Iterates through list of indexes and replaces all subtrees of query which match index with external tuple object built from index. - * - * @param query - * @return TupleExpr - */ - public TupleExpr process(TupleExpr query) { - TupleExpr rtn = query.clone(); - - - //move BindingSetAssignment Nodes out of the way - organizeBSAs(rtn); - - - // test to see if query contains no other nodes - // than filter, join, projection, and statement pattern and - // test whether query contains duplicate StatementPatterns and filters - if (isTupleValid(rtn)) { - - for (ExternalTupleSet index : indexSet) { - - // test to see if index contains at least one StatementPattern, - // that StatementPatterns are unique, - // and that all variables found in filters occur in some - // StatementPattern - if (isTupleValid(index.getTupleExpr())) { - - List<TupleExpr> normalize = getMatches(rtn, index.getTupleExpr()); - - for (TupleExpr tup : normalize) { - ExternalTupleSet eTup = (ExternalTupleSet) index.clone(); - setTableMap(tup, eTup); - setSupportedVarOrderMap(eTup); - eTup.setProjectionExpr((Projection) tup); - SPBubbleDownVisitor indexVistor = new SPBubbleDownVisitor(eTup); - rtn.visit(indexVistor); - FilterBubbleManager fbmv = new FilterBubbleManager(eTup); - rtn.visit(fbmv); - SubsetEqualsVisitor subIndexVis = new SubsetEqualsVisitor(eTup); - rtn.visit(subIndexVis); - - } - } - - } - - return rtn; - } else { - throw new IllegalArgumentException("Invalid Query."); - } - } - - - private void setTableMap(TupleExpr tupleMatch, ExternalTupleSet index) { - - List<String> replacementVars = Lists.newArrayList(tupleMatch.getBindingNames()); - List<String> tableVars = Lists.newArrayList(index.getTupleExpr().getBindingNames()); - - Map<String,String> tableMap = Maps.newHashMap(); - - for(int i = 0; i < tableVars.size(); i++) { - tableMap.put(replacementVars.get(i), tableVars.get(i)); - } - index.setTableVarMap(tableMap); - - - } - - private void setSupportedVarOrderMap(ExternalTupleSet index) { - - Map<String, Set<String>> supportedVarOrders = Maps.newHashMap(); - BiMap<String, String> biMap = HashBiMap.create(index.getTableVarMap()).inverse(); - Map<String, Set<String>> oldSupportedVarOrders = index.getSupportedVariableOrderMap(); - - Set<String> temp = null; - Set<String> keys = oldSupportedVarOrders.keySet(); - - for (String s : keys) { - temp = oldSupportedVarOrders.get(s); - Set<String> newSet = Sets.newHashSet(); - - for (String t : temp) { - newSet.add(biMap.get(t)); - } - - String[] tempStrings = s.split("\u0000"); - String v = ""; - for(String u: tempStrings) { - if(v.length() == 0){ - v = v + biMap.get(u); - } else { - v = v + "\u0000" + biMap.get(u); - } - } - - supportedVarOrders.put(v, newSet); - - } - - index.setSupportedVariableOrderMap(supportedVarOrders); - - } - - - - private List<TupleExpr> getMatches(TupleExpr query, TupleExpr tuple) { - - try { - List<TupleExpr> list = QueryVariableNormalizer.getNormalizedIndex(query, tuple); - // System.out.println("Match list is " + list); - return list; - } catch (Exception e) { - System.out.println(e); - } - - return new ArrayList<TupleExpr>(); - - } - - // determines whether query is valid, which requires that a - // query must contain a StatementPattern, not contain duplicate - // Statement Patterns or Filters, not be comprised of only Projection, - // Join, StatementPattern, and Filter nodes, and that any variable - // appearing in a Filter must appear in a StatementPattern. - private static boolean isTupleValid(QueryModelNode node) { - - ValidQueryVisitor vqv = new ValidQueryVisitor(); - node.visit(vqv); - - Set<String> spVars = getVarNames(getQNodes("sp", node)); - - if (vqv.isValid() && (spVars.size() > 0)) { - - FilterCollector fvis = new FilterCollector(); - node.visit(fvis); - List<QueryModelNode> fList = fvis.getFilters(); - return (fList.size() == Sets.newHashSet(fList).size() && getVarNames(fList).size() <= spVars.size()); - - } else { - return false; - } - } - - private static Set<QueryModelNode> getQNodes(QueryModelNode queryNode) { - Set<QueryModelNode> rtns = new HashSet<QueryModelNode>(); - - StatementPatternCollector spc = new StatementPatternCollector(); - queryNode.visit(spc); - rtns.addAll(spc.getStatementPatterns()); - - FilterCollector fvis = new FilterCollector(); - queryNode.visit(fvis); - rtns.addAll(fvis.getFilters()); - - ExternalTupleCollector eVis = new ExternalTupleCollector(); - queryNode.visit(eVis); - rtns.addAll(eVis.getExtTup()); - - return rtns; - } - - private static Set<QueryModelNode> getQNodes(String node, QueryModelNode queryNode) { - - if (node.equals("sp")) { - Set<QueryModelNode> eSet = new HashSet<QueryModelNode>(); - StatementPatternCollector spc = new StatementPatternCollector(); - queryNode.visit(spc); - List<StatementPattern> spList = spc.getStatementPatterns(); - eSet.addAll(spList); - // returns empty set if list contains duplicate StatementPatterns - if (spList.size() > eSet.size()) { - return Sets.newHashSet(); - } else { - return eSet; - } - } else if (node.equals("filter")) { - - FilterCollector fvis = new FilterCollector(); - queryNode.visit(fvis); - - return Sets.newHashSet(fvis.getFilters()); - } else { - - throw new IllegalArgumentException("Invalid node type."); - } - } - - // moves StatementPatterns in query that also occur in index to bottom of - // query tree. - private static class SPBubbleDownVisitor extends QueryModelVisitorBase<RuntimeException> { - - private TupleExpr tuple; - private QueryModelNode indexQNode; - private Set<QueryModelNode> sSet = Sets.newHashSet(); - - public SPBubbleDownVisitor(ExternalTupleSet index) { - - this.tuple = index.getTupleExpr(); - indexQNode = ((Projection) tuple).getArg(); - sSet = getQNodes("sp", indexQNode); - - } - - public void meet(Projection node) { - // moves external tuples above statement patterns before attempting - // to bubble down index statement patterns found in query tree - - organizeExtTuples(node); - - super.meet(node); - } - - public void meet(Join node) { - // if right node contained in index, move it to bottom of query tree - if (sSet.contains(node.getRightArg())) { - - Set<QueryModelNode> eSet = getQNodes("sp", node); - Set<QueryModelNode> compSet = Sets.difference(eSet, sSet); - - if (eSet.containsAll(sSet)) { - - QNodeExchanger qne = new QNodeExchanger(node.getRightArg(), compSet); - node.visit(qne); - node.replaceChildNode(node.getRightArg(), qne.getReplaced()); - - super.meet(node); - } - return; - } - // if left node contained in index, move it to bottom of query tree - else if (sSet.contains(node.getLeftArg())) { - - Set<QueryModelNode> eSet = getQNodes("sp", node); - Set<QueryModelNode> compSet = Sets.difference(eSet, sSet); - - if (eSet.containsAll(sSet)) { - - QNodeExchanger qne = new QNodeExchanger(node.getLeftArg(), compSet); - node.visit(qne); - node.replaceChildNode(node.getLeftArg(), qne.getReplaced()); - - super.meet(node); - } - return; - - } else { - super.meet(node); - } - - } - - // moves all ExternalTupleSets in query tree above remaining - // StatementPatterns - private static void organizeExtTuples(QueryModelNode node) { - - ExternalTupleCollector eVis = new ExternalTupleCollector(); - node.visit(eVis); - - ExtTupleExchangeVisitor oev = new ExtTupleExchangeVisitor(eVis.getExtTup()); - node.visit(oev); - } - - } - - // given a replacement QueryModelNode and compSet, this visitor replaces the - // first - // element in the query tree that occurs in compSet with replacement and - // returns - // the element that was replaced. - private static class QNodeExchanger extends QueryModelVisitorBase<RuntimeException> { - - private QueryModelNode toBeReplaced; - private QueryModelNode replacement; - private Set<QueryModelNode> compSet; - - public QNodeExchanger(QueryModelNode replacement, Set<QueryModelNode> compSet) { - this.replacement = replacement; - this.toBeReplaced = replacement; - this.compSet = compSet; - } - - public QueryModelNode getReplaced() { - return toBeReplaced; - } - - public void meet(Join node) { - - if (compSet.contains(node.getRightArg())) { - this.toBeReplaced = node.getRightArg(); - node.replaceChildNode(node.getRightArg(), replacement); - return; - } else if (compSet.contains(node.getLeftArg())) { - this.toBeReplaced = node.getLeftArg(); - node.replaceChildNode(node.getLeftArg(), replacement); - return; - } else { - super.meet(node); - } - - } - - } - - // moves filter that occurs in both query and index down the query tree so - // that that it is positioned - // above statement patterns associated with index. Precondition for calling - // this method is that - // SPBubbleDownVisitor has been called to position index StatementPatterns - // within query tree. - //TODO this visitor assumes that all filters are positioned at top of query tree - //could lead to problems if filter optimizer called before external processor - private static class FilterBubbleDownVisitor extends QueryModelVisitorBase<RuntimeException> { - - private QueryModelNode filter; - private Set<QueryModelNode> compSet; - private boolean filterPlaced = false; - - public FilterBubbleDownVisitor(QueryModelNode filter, Set<QueryModelNode> compSet) { - this.filter = filter; - this.compSet = compSet; - - } - - public boolean filterPlaced() { - return filterPlaced; - } - - public void meet(Join node) { - - if (!compSet.contains(node.getRightArg())) { - // looks for placed to position filter node. if right node is - // contained in index - // and left node is statement pattern node contained in index or - // is a join, place - // filter above join. - if (node.getLeftArg() instanceof Join || !(compSet.contains(node.getLeftArg()))) { - - QueryModelNode pNode = node.getParentNode(); - ((Filter) filter).setArg(node); - pNode.replaceChildNode(node, filter); - filterPlaced = true; - - return; - } // otherwise place filter below join and above right arg - else { - ((Filter) filter).setArg(node.getRightArg()); - node.replaceChildNode(node.getRightArg(), filter); - filterPlaced = true; - return; - - } - } else if ((node.getLeftArg() instanceof StatementPattern) && !compSet.contains(node.getLeftArg())) { - - ((Filter) filter).setArg(node.getLeftArg()); - node.replaceChildNode(node.getLeftArg(), filter); - filterPlaced = true; - - return; - } else { - super.meet(node); - } - } - - } - - private static Set<String> getVarNames(Collection<QueryModelNode> nodes) { - - List<String> tempVars; - Set<String> nodeVarNames = Sets.newHashSet(); - - for (QueryModelNode s : nodes) { - tempVars = VarCollector.process(s); - for (String t : tempVars) - nodeVarNames.add(t); - } - return nodeVarNames; - - } - - // visitor which determines whether or not to reposition a filter by calling - // FilterBubbleDownVisitor - private static class FilterBubbleManager extends QueryModelVisitorBase<RuntimeException> { - - private TupleExpr tuple; - private QueryModelNode indexQNode; - private Set<QueryModelNode> sSet = Sets.newHashSet(); - private Set<QueryModelNode> bubbledFilters = Sets.newHashSet(); - - public FilterBubbleManager(ExternalTupleSet index) { - this.tuple = index.getTupleExpr(); - indexQNode = ((Projection) tuple).getArg(); - sSet = getQNodes(indexQNode); - - } - - public void meet(Filter node) { - - Set<QueryModelNode> eSet = getQNodes(node); - Set<QueryModelNode> compSet = Sets.difference(eSet, sSet); - - // if index contains filter node and it hasn't already been moved, - // move it down - // query tree just above position of statement pattern nodes found - // in both query tree - // and index (assuming that SPBubbleDownVisitor has already been - // called) - if (sSet.contains(node.getCondition()) && !bubbledFilters.contains(node.getCondition())) { - FilterBubbleDownVisitor fbdv = new FilterBubbleDownVisitor((Filter) node.clone(), compSet); - node.visit(fbdv); - bubbledFilters.add(node.getCondition()); - // checks if filter correctly placed, and if it has been, - // removes old copy of filter - if (fbdv.filterPlaced()) { - - QueryModelNode pNode = node.getParentNode(); - TupleExpr cNode = node.getArg(); - pNode.replaceChildNode(node, cNode); - - - super.meetNode(pNode); - } - super.meet(node); - - } else { - super.meet(node); - } - } - } - - // iterates through the query tree and attempts to match subtrees with - // index. When a match is - // found, the subtree is replaced by an ExternalTupleSet formed from the - // index. Pre-condition for - // calling this method is that both SPBubbleDownVisitor and - // FilterBubbleManager have been called - // to position the StatementPatterns and Filters. - private static class SubsetEqualsVisitor extends QueryModelVisitorBase<RuntimeException> { - - private TupleExpr tuple; - private QueryModelNode indexQNode; - private ExternalTupleSet set; - private Set<QueryModelNode> sSet = Sets.newHashSet(); - - public SubsetEqualsVisitor(ExternalTupleSet index) { - this.tuple = index.getTupleExpr(); - this.set = index; - indexQNode = ((Projection) tuple).getArg(); - sSet = getQNodes(indexQNode); - - } - - public void meet(Join node) { - - Set<QueryModelNode> eSet = getQNodes(node); - - if (eSet.containsAll(sSet) && !(node.getRightArg() instanceof BindingSetAssignment)) { - -// System.out.println("Eset is " + eSet + " and sSet is " + sSet); - - if (eSet.equals(sSet)) { - node.replaceWith(set); - return; - } else { - if (node.getLeftArg() instanceof StatementPattern && sSet.size() == 1) { - if(sSet.contains(node.getLeftArg())) { - node.setLeftArg(set); - } else if(sSet.contains(node.getRightArg())) { - node.setRightArg(set); - } else { - return; - } - } - else { - super.meet(node); - } - } - } else if (eSet.containsAll(sSet)) { - - super.meet(node); - - } - - } - //TODO might need to include BindingSetAssignment Condition here - //to account for index consisting of only filter and BindingSetAssignment nodes - public void meet(Filter node) { - - Set<QueryModelNode> eSet = getQNodes(node); - - if (eSet.containsAll(sSet)) { - - if (eSet.equals(sSet)) { - node.replaceWith(set); - return; - } else { - super.meet(node); - } - } - } - } - - // visitor which determines whether a query is valid (i.e. it does not - // contain nodes other than - // Projection, Join, Filter, StatementPattern ) - private static class ValidQueryVisitor extends QueryModelVisitorBase<RuntimeException> { - - private boolean isValid = true; - - public boolean isValid() { - return isValid; - } - - public void meet(Projection node) { - node.getArg().visit(this); - } - - public void meet(Filter node) { - node.getArg().visit(this); - } - - - - - - public void meetNode(QueryModelNode node) { - - if (!((node instanceof Join) || (node instanceof StatementPattern) || (node instanceof BindingSetAssignment) || (node instanceof Var))) { - isValid = false; - return; - - } else{ - super.meetNode(node); - } - } - - } - - // repositions ExternalTuples above StatementPatterns within query tree - private static class ExtTupleExchangeVisitor extends QueryModelVisitorBase<RuntimeException> { - - private Set<QueryModelNode> extTuples; - - public ExtTupleExchangeVisitor(Set<QueryModelNode> extTuples) { - this.extTuples = extTuples; - } - - public void meet(Join queryNode) { - - // if query tree contains external tuples and they are not - // positioned above statement pattern node - // reposition - if (this.extTuples.size() > 0 && !(queryNode.getRightArg() instanceof ExternalTupleSet) - && !(queryNode.getRightArg() instanceof BindingSetAssignment)) { - QNodeExchanger qnev = new QNodeExchanger((QueryModelNode) queryNode.getRightArg(), this.extTuples); - queryNode.visit(qnev); - queryNode.setRightArg((TupleExpr)qnev.getReplaced()); - super.meet(queryNode); - } else { - super.meet(queryNode); - } - - } - - } - - private static class ExternalTupleCollector extends QueryModelVisitorBase<RuntimeException> { - - private Set<QueryModelNode> eSet = new HashSet<QueryModelNode>(); - - @Override - public void meetNode(QueryModelNode node) throws RuntimeException { - if (node instanceof ExternalTupleSet) { - eSet.add(node); - } - super.meetNode(node); - } - - public Set<QueryModelNode> getExtTup() { - return eSet; - } - - } - - private static class FilterCollector extends QueryModelVisitorBase<RuntimeException> { - - private List<QueryModelNode> filterList = Lists.newArrayList(); - - public List<QueryModelNode> getFilters() { - return filterList; - } - - @Override - public void meet(Filter node) { - filterList.add(node.getCondition()); - super.meet(node); - } - - } - - private static void organizeBSAs(QueryModelNode node) { - - BindingSetAssignmentCollector bsac = new BindingSetAssignmentCollector(); - node.visit(bsac); - - if (bsac.containsBSAs()) { - Set<QueryModelNode> bsaSet = bsac.getBindingSetAssignments(); - BindingSetAssignmentExchangeVisitor bsaev = new BindingSetAssignmentExchangeVisitor(bsaSet); - node.visit(bsaev); - } - } - - // repositions ExternalTuples above StatementPatterns within query tree - private static class BindingSetAssignmentExchangeVisitor extends QueryModelVisitorBase<RuntimeException> { - - private Set<QueryModelNode> bsas; - - public BindingSetAssignmentExchangeVisitor(Set<QueryModelNode> bsas) { - this.bsas = bsas; - } - - public void meet(Join queryNode) { - - // if query tree contains external tuples and they are not - // positioned above statement pattern node - // reposition - if (this.bsas.size() > 0 && !(queryNode.getRightArg() instanceof BindingSetAssignment)) { - QNodeExchanger qnev = new QNodeExchanger((QueryModelNode) queryNode.getRightArg(), bsas); - queryNode.visit(qnev); - queryNode.replaceChildNode(queryNode.getRightArg(), qnev.getReplaced()); - super.meet(queryNode); - } else { - super.meet(queryNode); - } - - } - - } - - - public static class BindingSetAssignmentCollector extends QueryModelVisitorBase<RuntimeException> { - - private Set<QueryModelNode> bindingSetList = Sets.newHashSet(); - - public Set<QueryModelNode> getBindingSetAssignments() { - return bindingSetList; - } - - public boolean containsBSAs() { - return (bindingSetList.size() > 0); - } - - @Override - public void meet(BindingSetAssignment node) { - bindingSetList.add(node); - super.meet(node); - } - - } - - // TODO insert BindingSetAssignments at bottom of query tree --this approach assumes - // BindingSetAssignments always removed during creation of ExternalTupleSets within - // query. There may be cases where this precondition does not hold (all BindingSetAssignments - // not removed). For now assuming it always holds. - -}
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/5a03ef61/extras/indexing/src/main/java/mvm/rya/indexing/external/ExternalSail.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/external/ExternalSail.java b/extras/indexing/src/main/java/mvm/rya/indexing/external/ExternalSail.java deleted file mode 100644 index 772ffa4..0000000 --- a/extras/indexing/src/main/java/mvm/rya/indexing/external/ExternalSail.java +++ /dev/null @@ -1,86 +0,0 @@ -package mvm.rya.indexing.external; - -/* - * 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. - */ - - - -import info.aduna.iteration.CloseableIteration; - -import org.openrdf.model.ValueFactory; -import org.openrdf.query.BindingSet; -import org.openrdf.query.Dataset; -import org.openrdf.query.QueryEvaluationException; -import org.openrdf.query.algebra.Projection; -import org.openrdf.query.algebra.QueryRoot; -import org.openrdf.query.algebra.TupleExpr; -import org.openrdf.sail.Sail; -import org.openrdf.sail.SailConnection; -import org.openrdf.sail.SailException; -import org.openrdf.sail.helpers.SailBase; -import org.openrdf.sail.helpers.SailConnectionWrapper; - -public class ExternalSail extends SailBase { - private final Sail s; - private final ExternalProcessor processor; - - public ExternalSail(Sail s, ExternalProcessor processor) { - this.s = s; - this.processor = processor; - } - - @Override - protected SailConnection getConnectionInternal() throws SailException { - return new ProcessingSailConnection(); - } - - @Override - public boolean isWritable() throws SailException { - return s.isWritable(); - } - - @Override - public ValueFactory getValueFactory() { - return s.getValueFactory(); - } - - @Override - protected void shutDownInternal() throws SailException { - s.shutDown(); - } - - private class ProcessingSailConnection extends SailConnectionWrapper { - - public ProcessingSailConnection() throws SailException { - super(s.getConnection()); - } - - @Override - public CloseableIteration<? extends BindingSet, QueryEvaluationException> evaluate(TupleExpr tupleExpr, Dataset dataset, - BindingSet bindings, boolean includeInferred) throws SailException { - if ((tupleExpr instanceof Projection) || (tupleExpr instanceof QueryRoot)) { - TupleExpr processedExpression = processor.process(tupleExpr); - return super.evaluate(processedExpression, dataset, bindings, includeInferred); - } else { - return super.evaluate(tupleExpr, dataset, bindings, includeInferred); - } - - } - } -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/5a03ef61/extras/indexing/src/main/java/mvm/rya/indexing/external/ExternalSailExample.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/external/ExternalSailExample.java b/extras/indexing/src/main/java/mvm/rya/indexing/external/ExternalSailExample.java deleted file mode 100644 index 082dd99..0000000 --- a/extras/indexing/src/main/java/mvm/rya/indexing/external/ExternalSailExample.java +++ /dev/null @@ -1,124 +0,0 @@ -package mvm.rya.indexing.external; - -/* - * 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. - */ - - - -import java.util.List; - -import mvm.rya.indexing.external.tupleSet.AccumuloIndexSet; -import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; - -import org.apache.accumulo.core.client.Connector; -import org.apache.accumulo.core.client.mock.MockInstance; -import org.openrdf.model.URI; -import org.openrdf.model.impl.LiteralImpl; -import org.openrdf.model.impl.URIImpl; -import org.openrdf.model.vocabulary.RDF; -import org.openrdf.model.vocabulary.RDFS; -import org.openrdf.query.QueryLanguage; -import org.openrdf.query.algebra.helpers.QueryModelTreePrinter; -import org.openrdf.query.parser.ParsedQuery; -import org.openrdf.query.parser.sparql.SPARQLParser; -import org.openrdf.query.resultio.sparqlxml.SPARQLResultsXMLWriter; -import org.openrdf.repository.sail.SailRepository; -import org.openrdf.repository.sail.SailRepositoryConnection; -import org.openrdf.sail.Sail; -import org.openrdf.sail.memory.MemoryStore; - -import com.google.common.collect.Lists; - -public class ExternalSailExample { - - public static void main(String[] args) throws Exception { - - Sail s = new MemoryStore(); - SailRepository repo = new SailRepository(s); - repo.initialize(); - SailRepositoryConnection conn = repo.getConnection(); - - URI sub = new URIImpl("uri:entity"); - URI subclass = new URIImpl("uri:class"); - URI obj = new URIImpl("uri:obj"); - URI talksTo = new URIImpl("uri:talksTo"); - - conn.add(sub, RDF.TYPE, subclass); - conn.add(sub, RDFS.LABEL, new LiteralImpl("label")); - conn.add(sub, talksTo, obj); - - URI sub2 = new URIImpl("uri:entity2"); - URI subclass2 = new URIImpl("uri:class2"); - URI obj2 = new URIImpl("uri:obj2"); - - conn.add(sub2, RDF.TYPE, subclass2); - conn.add(sub2, RDFS.LABEL, new LiteralImpl("label2")); - conn.add(sub2, talksTo, obj2); - - // TODO Auto-generated method stub - String indexSparqlString = ""// - + "SELECT ?e ?l ?c " // - + "{" // - + " ?e a ?c . "// - + " ?e <http://www.w3.org/2000/01/rdf-schema#label> ?l "// - + "}";// - - conn.prepareTupleQuery(QueryLanguage.SPARQL, indexSparqlString).evaluate(new SPARQLResultsXMLWriter(System.out)); - - SPARQLParser sp = new SPARQLParser(); - ParsedQuery pq = sp.parseQuery(indexSparqlString, null); - System.out.println(pq); - - List<ExternalTupleSet> index = Lists.newArrayList(); - - Connector accCon = new MockInstance().getConnector("root", "".getBytes()); - String tablename = "table"; - accCon.tableOperations().create(tablename); - index.add(new AccumuloIndexSet(indexSparqlString, conn, accCon, tablename)); - - String queryString = ""// - + "SELECT ?e ?c ?l ?o " // - + "{" // - + " ?e a ?c . "// - + " ?e <http://www.w3.org/2000/01/rdf-schema#label> ?l . "// - + " ?e <uri:talksTo> ?o . "// - + "}";// - - conn.prepareTupleQuery(QueryLanguage.SPARQL, queryString).evaluate(new SPARQLResultsXMLWriter(System.out)); - - pq = sp.parseQuery(queryString, null); - QueryModelTreePrinter mp = new QueryModelTreePrinter(); - pq.getTupleExpr().visit(mp); - System.out.println(mp.getTreeString()); - System.out.println(pq.getTupleExpr()); - - System.out.println("++++++++++++"); - ExternalProcessor processor = new ExternalProcessor(index); - System.out.println(processor.process(pq.getTupleExpr())); - - System.out.println("----------------"); - Sail processingSail = new ExternalSail(s, processor); - SailRepository smartSailRepo = new SailRepository(processingSail); - smartSailRepo.initialize(); - - smartSailRepo.getConnection().prepareTupleQuery(QueryLanguage.SPARQL, queryString).evaluate(new SPARQLResultsXMLWriter(System.out)); - - } - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/5a03ef61/extras/indexing/src/main/java/mvm/rya/indexing/external/PrecompJoinOptimizer.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/external/PrecompJoinOptimizer.java b/extras/indexing/src/main/java/mvm/rya/indexing/external/PrecompJoinOptimizer.java deleted file mode 100644 index 65a775f..0000000 --- a/extras/indexing/src/main/java/mvm/rya/indexing/external/PrecompJoinOptimizer.java +++ /dev/null @@ -1,773 +0,0 @@ -package mvm.rya.indexing.external; - -/* - * 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. - */ - - -import java.util.ArrayList; -import java.util.Collection; -import java.util.Iterator; -import java.util.List; -import java.util.Map; -import java.util.Map.Entry; -import java.util.Set; - -import mvm.rya.api.RdfCloudTripleStoreConfiguration; -import mvm.rya.indexing.IndexPlanValidator.IndexPlanValidator; -import mvm.rya.indexing.IndexPlanValidator.IndexedExecutionPlanGenerator; -import mvm.rya.indexing.IndexPlanValidator.ThreshholdPlanSelector; -import mvm.rya.indexing.IndexPlanValidator.TupleReArranger; -import mvm.rya.indexing.IndexPlanValidator.ValidIndexCombinationGenerator; -import mvm.rya.indexing.accumulo.ConfigUtils; -import mvm.rya.indexing.external.QueryVariableNormalizer.VarCollector; -import mvm.rya.indexing.external.tupleSet.AccumuloIndexSet; -import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; -import mvm.rya.rdftriplestore.inference.DoNotExpandSP; -import mvm.rya.rdftriplestore.utils.FixedStatementPattern; - -import org.apache.accumulo.core.client.AccumuloException; -import org.apache.accumulo.core.client.AccumuloSecurityException; -import org.apache.accumulo.core.client.Connector; -import org.apache.accumulo.core.client.Scanner; -import org.apache.accumulo.core.client.TableNotFoundException; -import org.apache.accumulo.core.data.Key; -import org.apache.accumulo.core.data.Range; -import org.apache.accumulo.core.data.Value; -import org.apache.accumulo.core.security.Authorizations; -import org.apache.hadoop.conf.Configurable; -import org.apache.hadoop.conf.Configuration; -import org.apache.hadoop.io.Text; -import org.openrdf.query.BindingSet; -import org.openrdf.query.Dataset; -import org.openrdf.query.MalformedQueryException; -import org.openrdf.query.QueryEvaluationException; -import org.openrdf.query.algebra.BindingSetAssignment; -import org.openrdf.query.algebra.Difference; -import org.openrdf.query.algebra.Distinct; -import org.openrdf.query.algebra.EmptySet; -import org.openrdf.query.algebra.Extension; -import org.openrdf.query.algebra.Filter; -import org.openrdf.query.algebra.Intersection; -import org.openrdf.query.algebra.Join; -import org.openrdf.query.algebra.LeftJoin; -import org.openrdf.query.algebra.Order; -import org.openrdf.query.algebra.Projection; -import org.openrdf.query.algebra.QueryModelNode; -import org.openrdf.query.algebra.QueryRoot; -import org.openrdf.query.algebra.Reduced; -import org.openrdf.query.algebra.StatementPattern; -import org.openrdf.query.algebra.TupleExpr; -import org.openrdf.query.algebra.UnaryTupleOperator; -import org.openrdf.query.algebra.Union; -import org.openrdf.query.algebra.ValueExpr; -import org.openrdf.query.algebra.Var; -import org.openrdf.query.algebra.evaluation.QueryOptimizer; -import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; -import org.openrdf.query.algebra.helpers.VarNameCollector; -import org.openrdf.sail.SailException; - -import com.google.common.collect.Lists; -import com.google.common.collect.Maps; -import com.google.common.collect.Sets; - -//optimizer which matches TupleExpressions associated with pre-computed queries -//to sub-queries of a given query. Each matched sub-query is replaced by an indexing node -//to delegate that portion of the query to the pre-computed query index -public class PrecompJoinOptimizer implements QueryOptimizer, Configurable { - - private List<ExternalTupleSet> indexSet; - private Configuration conf; - private boolean init = false; - - public PrecompJoinOptimizer() { - } - - public PrecompJoinOptimizer(Configuration conf) { - this.conf = conf; - try { - indexSet = getAccIndices(conf); - init = true; - } catch (MalformedQueryException e) { - e.printStackTrace(); - } catch (SailException e) { - e.printStackTrace(); - } catch (QueryEvaluationException e) { - e.printStackTrace(); - } catch (TableNotFoundException e) { - e.printStackTrace(); - } catch (AccumuloException e) { - e.printStackTrace(); - } catch (AccumuloSecurityException e) { - e.printStackTrace(); - } - } - - public PrecompJoinOptimizer(List<ExternalTupleSet> indices, boolean useOptimalPcj) { - this.indexSet = indices; - conf = new Configuration(); - conf.setBoolean(ConfigUtils.USE_OPTIMAL_PCJ, useOptimalPcj); - } - - public void setConf(Configuration conf) { - this.conf = conf; - if (!init) { - try { - indexSet = getAccIndices(conf); - init = true; - } catch (MalformedQueryException e) { - e.printStackTrace(); - } catch (SailException e) { - e.printStackTrace(); - } catch (QueryEvaluationException e) { - e.printStackTrace(); - } catch (TableNotFoundException e) { - e.printStackTrace(); - } catch (AccumuloException e) { - e.printStackTrace(); - } catch (AccumuloSecurityException e) { - e.printStackTrace(); - } - } - } - - @Override - public Configuration getConf() { - return conf; - } - - - @Override - public void optimize(TupleExpr tupleExpr, Dataset dataset, BindingSet bindings) { - - IndexedExecutionPlanGenerator iep = new IndexedExecutionPlanGenerator(tupleExpr, indexSet); - JoinVisitor jv = new JoinVisitor(); - - if (ConfigUtils.getUseOptimalPCJ(conf) && indexSet.size() > 0) { - - //get potential relevant index combinations - ValidIndexCombinationGenerator vic = new ValidIndexCombinationGenerator(tupleExpr); - Iterator<List<ExternalTupleSet>> iter = vic.getValidIndexCombos(iep.getNormalizedIndices()); - TupleExpr bestTup = null; - TupleExpr tempTup = null; - double tempCost = 0; - double minCost = Double.MAX_VALUE; - - while (iter.hasNext()) { - //apply join visitor to place external index nodes in query - TupleExpr clone = tupleExpr.clone(); - jv.setExternalTupList(iter.next()); - jv.setSegmentFilters(new ArrayList<Filter>()); - clone.visit(jv); - - //get all valid execution plans for given external index combination by considering all - //permutations of nodes in TupleExpr - IndexPlanValidator ipv = new IndexPlanValidator(false); - Iterator<TupleExpr> validTups = ipv.getValidTuples(TupleReArranger.getTupleReOrderings(clone).iterator()); - - //set valid plan according to a specified cost threshold, where cost depends on specified weights - //for number of external index nodes, common variables among joins in execution plan, and number of - //external products in execution plan - ThreshholdPlanSelector tps = new ThreshholdPlanSelector(tupleExpr); - tempTup = tps.getThreshholdQueryPlan(validTups, .4, .5, .2, .3); - - //choose best threshhold TupleExpr among all index node combinations - tempCost = tps.getCost(tempTup, .5, .2, .3); - if(tempCost < minCost ) { - minCost = tempCost; - bestTup = tempTup; - } - } - if (bestTup != null) { - ((UnaryTupleOperator) tupleExpr).setArg(((UnaryTupleOperator) bestTup).getArg()); - } - return; - } else { - if (indexSet.size() > 0) { - jv.setExternalTupList(iep.getNormalizedIndices()); - tupleExpr.visit(jv); - } - return; - } - } - - protected class JoinVisitor extends QueryModelVisitorBase<RuntimeException> { - - private List<ExternalTupleSet> tupList; - private List<Filter> segmentFilters = Lists.newArrayList(); - - public void setExternalTupList(List<ExternalTupleSet> tupList) { - this.tupList = tupList; - } - - public void setSegmentFilters(List<Filter> segmentFilters) { - this.segmentFilters = segmentFilters; - } - - @Override - public void meet(Join node) { - - //get all filters with bindings in this segment - updateFilters(segmentFilters, true); - - try { - if (node.getLeftArg() instanceof FixedStatementPattern && node.getRightArg() instanceof DoNotExpandSP) { - return; - } - - //get nodes in this join segment - TupleExpr newJoin = null; - List<QueryModelNode> args = getJoinArgs(node, new ArrayList<QueryModelNode>(), false); - List<TupleExpr> joinArgs = Lists.newArrayList(); - - for (QueryModelNode qNode : args) { - assert (qNode instanceof TupleExpr); - joinArgs.add((TupleExpr) qNode); - } - - //insert all matching ExternalTupleSets in tupList into this segment - joinArgs = matchExternalTupleSets(joinArgs, tupList); - - //push down any filters that have bindings in lower segments - //and update the filters in this segment - updateFilters(segmentFilters, false); - - //form join from matching ExternalTupleSets, remaining nodes, and filters - //that can't be pushed down any further - newJoin = getNewJoin(joinArgs, getFilterChain(segmentFilters)); - - // Replace old join hierarchy - node.replaceWith(newJoin); - - //visit remaining nodes to match ExternalTupleSets with nodes further down - for (TupleExpr te : joinArgs) { - if (!(te instanceof StatementPattern) && !(te instanceof ExternalTupleSet)) { - segmentFilters = Lists.newArrayList(); - te.visit(this); - } - } - - } catch (Exception e) { - e.printStackTrace(); - } - } - - - @Override - public void meet(Filter node) { - segmentFilters.add(node); - node.getArg().visit(this); - } - - //chain filters together and return front and back of chain - private List<TupleExpr> getFilterChain(List<Filter> filters) { - List<TupleExpr> filterTopBottom = Lists.newArrayList(); - Filter filterChainTop = null; - Filter filterChainBottom = null; - - for (Filter filter: filters) { - if (filterChainTop == null) { - filterChainTop = filter; - } else if (filterChainBottom == null) { - filterChainBottom = filter; - filterChainTop.setArg(filterChainBottom); - } else { - filterChainBottom.setArg(filter); - filterChainBottom = filter; - } - } - if(filterChainTop != null) { - filterTopBottom.add(filterChainTop); - } - if(filterChainBottom != null) { - filterTopBottom.add(filterChainBottom); - } - return filterTopBottom; - } - - //build newJoin node given remaining joinArgs and chain of filters - private TupleExpr getNewJoin(List<TupleExpr> args, List<TupleExpr> filterChain) { - TupleExpr newJoin; - List<TupleExpr> joinArgs = Lists.newArrayList(args); - - if (joinArgs.size() > 1) { - if (filterChain.size() > 0) { - TupleExpr finalJoinArg = joinArgs.remove(0); - TupleExpr tempJoin; - TupleExpr temp = filterChain.get(0); - - if (joinArgs.size() > 1) { - tempJoin = new Join(joinArgs.remove(0), joinArgs.remove(0)); - for (TupleExpr te : joinArgs) { - tempJoin = new Join(tempJoin, te); - } - } else { - tempJoin = joinArgs.remove(0); - } - - if (filterChain.size() == 1) { - ((Filter) temp).setArg(tempJoin); - } else { - ((Filter) filterChain.get(1)).setArg(tempJoin); - } - newJoin = new Join(temp, finalJoinArg); - } else { - newJoin = new Join(joinArgs.get(0), joinArgs.get(1)); - joinArgs.remove(0); - joinArgs.remove(0); - - for (TupleExpr te : joinArgs) { - newJoin = new Join(newJoin, te); - } - } - } else if (joinArgs.size() == 1) { - if (filterChain.size() > 0) { - newJoin = filterChain.get(0); - if (filterChain.size() == 1) { - ((Filter) newJoin).setArg(joinArgs.get(0)); - } else { - ((Filter) filterChain.get(1)).setArg(joinArgs.get(0)); - } - } else { - newJoin = joinArgs.get(0); - } - } else { - throw new IllegalStateException("JoinArgs size cannot be zero."); - } - return newJoin; - } - - - private List<TupleExpr> matchExternalTupleSets(List<TupleExpr> joinArgs, List<ExternalTupleSet> tupList) { - - Set<QueryModelNode> argSet = Sets.newHashSet(); - argSet.addAll(joinArgs); - - if(argSet.size() < joinArgs.size()) { - throw new IllegalArgumentException("Query has duplicate nodes in segment!"); - } - - Set<QueryModelNode> firstJoinFilterCond = Sets.newHashSet(); - - for(Filter filter: segmentFilters) { - firstJoinFilterCond.add(filter.getCondition()); - } - - argSet.addAll(firstJoinFilterCond); - - //see if ExternalTupleSet nodes are a subset of joinArgs, and if so, replacing matching nodes - //with ExternalTupleSet - for (ExternalTupleSet tup : tupList) { - TupleExpr tupleArg = tup.getTupleExpr(); - if (isTupleValid(tupleArg)) { - List<QueryModelNode> tupJoinArgs = getJoinArgs(tupleArg, - new ArrayList<QueryModelNode>(), true); - Set<QueryModelNode> tupJoinArgSet = Sets.newHashSet(tupJoinArgs); - if(tupJoinArgSet.size() < tupJoinArgs.size()) { - throw new IllegalArgumentException("ExternalTuple contains duplicate nodes!"); - } - if (argSet.containsAll(tupJoinArgSet)) { - argSet = Sets.newHashSet(Sets.difference(argSet, tupJoinArgSet)); - argSet.add((ExternalTupleSet) tup.clone()); - } - } - } - - //update segment filters by removing those use in ExternalTupleSet - Iterator<Filter> iter = segmentFilters.iterator(); - - while(iter.hasNext()) { - Filter filt = iter.next(); - if(!argSet.contains(filt.getCondition())) { - filt.replaceWith(filt.getArg()); - iter.remove(); - } - } - - //update joinArgs - joinArgs = Lists.newArrayList(); - for(QueryModelNode node: argSet) { - if(!(node instanceof ValueExpr)) { - joinArgs.add((TupleExpr)node); - } - } - - return joinArgs; - } - - - private void updateFilters(List<Filter> filters, boolean firstJoin) { - - Iterator<Filter> iter = segmentFilters.iterator(); - - while (iter.hasNext()) { - if (!FilterRelocator.relocate(iter.next(), firstJoin)) { - iter.remove(); - } - } - } - - protected List<QueryModelNode> getJoinArgs(TupleExpr tupleExpr, List<QueryModelNode> joinArgs, boolean getFilters) { - if (tupleExpr instanceof Join) { - if (!(((Join) tupleExpr).getLeftArg() instanceof FixedStatementPattern) - && !(((Join) tupleExpr).getRightArg() instanceof DoNotExpandSP)) { - Join join = (Join) tupleExpr; - getJoinArgs(join.getLeftArg(), joinArgs, getFilters); - getJoinArgs(join.getRightArg(), joinArgs, getFilters); - } - } else if(tupleExpr instanceof Filter) { - if (getFilters) { - joinArgs.add(((Filter) tupleExpr).getCondition()); - } - getJoinArgs(((Filter)tupleExpr).getArg(), joinArgs, getFilters); - } else if(tupleExpr instanceof Projection) { - getJoinArgs(((Projection)tupleExpr).getArg(), joinArgs, getFilters); - } else { - joinArgs.add(tupleExpr); - } - - return joinArgs; - } - } - - protected static class FilterRelocator extends QueryModelVisitorBase<RuntimeException> { - - - protected final Filter filter; - - protected final Set<String> filterVars; - private boolean stopAtFirstJoin = false; - private boolean isFirstJoinFilter = false; - private boolean inSegment = true; - - - public FilterRelocator(Filter filter) { - this.filter = filter; - filterVars = VarNameCollector.process(filter.getCondition()); - } - - public FilterRelocator(Filter filter, boolean stopAtFirstJoin) { - this.filter = filter; - filterVars = VarNameCollector.process(filter.getCondition()); - this.stopAtFirstJoin = stopAtFirstJoin; - } - - public static boolean relocate(Filter filter) { - FilterRelocator fr = new FilterRelocator(filter); - filter.visit(fr); - return fr.inSegment; - } - - public static boolean relocate(Filter filter, boolean stopAtFirstJoin) { - if (stopAtFirstJoin) { - FilterRelocator fr = new FilterRelocator(filter, stopAtFirstJoin); - filter.visit(fr); - return fr.isFirstJoinFilter; - } else { - FilterRelocator fr = new FilterRelocator(filter); - filter.visit(fr); - return fr.inSegment; - } - } - - - @Override - protected void meetNode(QueryModelNode node) { - // By default, do not traverse - assert node instanceof TupleExpr; - - if(node instanceof UnaryTupleOperator) { - if (((UnaryTupleOperator)node).getArg().getBindingNames().containsAll(filterVars)) { - if (stopAtFirstJoin) { - ((UnaryTupleOperator) node).getArg().visit(this); - } else { - inSegment = false; - relocate(filter, ((UnaryTupleOperator) node).getArg()); - } - } - } - - relocate(filter, (TupleExpr) node); - } - - - @Override - public void meet(Join join) { - - if (stopAtFirstJoin) { - isFirstJoinFilter = true; - relocate(filter, join); - } else { - - if (join.getLeftArg().getBindingNames().containsAll(filterVars)) { - // All required vars are bound by the left expr - join.getLeftArg().visit(this); - } else if (join.getRightArg().getBindingNames().containsAll(filterVars)) { - // All required vars are bound by the right expr - join.getRightArg().visit(this); - } else { - relocate(filter, join); - } - } - } - - @Override - public void meet(LeftJoin leftJoin) { - - if (leftJoin.getLeftArg().getBindingNames().containsAll(filterVars)) { - inSegment = false; - if (stopAtFirstJoin) { - leftJoin.getLeftArg().visit(this); - } else { - relocate(filter, leftJoin.getLeftArg()); - } - } - else { - relocate(filter, leftJoin); - } - } - - @Override - public void meet(Union union) { - Filter clone = new Filter(); - clone.setCondition(filter.getCondition().clone()); - - relocate(filter, union.getLeftArg()); - relocate(clone, union.getRightArg()); - - inSegment = false; - - } - - @Override - public void meet(Difference node) { - Filter clone = new Filter(); - clone.setCondition(filter.getCondition().clone()); - - relocate(filter, node.getLeftArg()); - relocate(clone, node.getRightArg()); - - inSegment = false; - - } - - @Override - public void meet(Intersection node) { - Filter clone = new Filter(); - clone.setCondition(filter.getCondition().clone()); - - relocate(filter, node.getLeftArg()); - relocate(clone, node.getRightArg()); - - inSegment = false; - - } - - @Override - public void meet(Extension node) { - if (node.getArg().getBindingNames().containsAll(filterVars)) { - if (stopAtFirstJoin) { - node.getArg().visit(this); - } else { - relocate(filter, node.getArg()); - inSegment = false; - } - } - else { - relocate(filter, node); - } - } - - @Override - public void meet(EmptySet node) { - if (filter.getParentNode() != null) { - // Remove filter from its original location - filter.replaceWith(filter.getArg()); - } - } - - @Override - public void meet(Filter filter) { - // Filters are commutative - filter.getArg().visit(this); - } - - @Override - public void meet(Distinct node) { - node.getArg().visit(this); - } - - @Override - public void meet(Order node) { - node.getArg().visit(this); - } - - @Override - public void meet(QueryRoot node) { - node.getArg().visit(this); - } - - @Override - public void meet(Reduced node) { - node.getArg().visit(this); - } - - protected void relocate(Filter filter, TupleExpr newFilterArg) { - if (filter.getArg() != newFilterArg) { - if (filter.getParentNode() != null) { - // Remove filter from its original location - filter.replaceWith(filter.getArg()); - } - - // Insert filter at the new location - newFilterArg.replaceWith(filter); - filter.setArg(newFilterArg); - } - } - } - - - private static boolean isTupleValid(QueryModelNode node) { - - ValidQueryVisitor vqv = new ValidQueryVisitor(); - node.visit(vqv); - - if (vqv.isValid() && vqv.getSPs().size() > 1) { - if(vqv.getFilters().size() > 0) { - Set<String> spVars = getVarNames(vqv.getSPs()); - Set<String> fVarNames = getVarNames(vqv.getFilters()); - //check that all vars contained in filters also occur in SPs - return Sets.intersection(fVarNames,spVars).equals(fVarNames); - } else { - return true; - } - } else { - return false; - } - } - - - private static Set<String> getVarNames(Collection<QueryModelNode> nodes) { - - List<String> tempVars; - Set<String> nodeVarNames = Sets.newHashSet(); - - for (QueryModelNode s : nodes) { - tempVars = VarCollector.process(s); - for (String t : tempVars) - nodeVarNames.add(t); - } - return nodeVarNames; - } - - - private static class ValidQueryVisitor extends QueryModelVisitorBase<RuntimeException> { - - private boolean isValid = true; - private Set<QueryModelNode> filterSet = Sets.newHashSet(); - private Set<QueryModelNode> spSet = Sets.newHashSet(); - - public Set<QueryModelNode> getFilters() { - return filterSet; - } - - public Set<QueryModelNode> getSPs() { - return spSet; - } - - public boolean isValid() { - return isValid; - } - - public void meet(Projection node) { - node.getArg().visit(this); - } - - @Override - public void meet(Filter node) { - filterSet.add(node.getCondition()); - node.getArg().visit(this); - } - - @Override - public void meet(StatementPattern node) { - spSet.add(node); - } - - public void meetNode(QueryModelNode node) { - - if (!((node instanceof Join) || (node instanceof StatementPattern) || (node instanceof BindingSetAssignment) || - (node instanceof Var) || (node instanceof Union) || (node instanceof LeftJoin))) { - isValid = false; - return; - - } else{ - super.meetNode(node); - } - } - - } - - - private static List<ExternalTupleSet> getAccIndices(Configuration conf) throws MalformedQueryException, - SailException, QueryEvaluationException, TableNotFoundException, AccumuloException, - AccumuloSecurityException { - - List<String> tables = null; - - if (conf instanceof RdfCloudTripleStoreConfiguration) { - tables = ((RdfCloudTripleStoreConfiguration) conf).getPcjTables(); - } - - String tablePrefix = conf.get(RdfCloudTripleStoreConfiguration.CONF_TBL_PREFIX); - Connector c = ConfigUtils.getConnector(conf); - Map<String, String> indexTables = Maps.newLinkedHashMap(); - - if (tables != null && !tables.isEmpty()) { - for (String table : tables) { - Scanner s = c.createScanner(table, new Authorizations()); - s.setRange(Range.exact(new Text("~SPARQL"))); - for (Entry<Key, Value> e : s) { - indexTables.put(table, e.getValue().toString()); - } - } - } else { - for (String table : c.tableOperations().list()) { - if (table.startsWith(tablePrefix + "INDEX")) { - Scanner s = c.createScanner(table, new Authorizations()); - s.setRange(Range.exact(new Text("~SPARQL"))); - for (Entry<Key, Value> e : s) { - indexTables.put(table, e.getValue().toString()); - } - } - } - - } - List<ExternalTupleSet> index = Lists.newArrayList(); - - if (indexTables.isEmpty()) { - System.out.println("No Index found"); - } else { - for (String table : indexTables.keySet()) { - String indexSparqlString = indexTables.get(table); - index.add(new AccumuloIndexSet(indexSparqlString, c, table)); - } - } - return index; - } -}
