http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/GeneralizedExternalProcessor.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/GeneralizedExternalProcessor.java b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/GeneralizedExternalProcessor.java new file mode 100644 index 0000000..08d52ed --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/GeneralizedExternalProcessor.java @@ -0,0 +1,726 @@ +package mvm.rya.indexing.IndexPlanValidator; + +/* + * 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.Collection; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; +import mvm.rya.indexing.pcj.matching.QueryVariableNormalizer.VarCollector; + +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.Lists; +import com.google.common.collect.Sets; + +/** + * Processes a {@link TupleExpr} and replaces sets of elements in the tree with {@link ExternalTupleSet} objects. + */ +public class GeneralizedExternalProcessor { + + + /** + * Iterates through list of normalized indexes and replaces all subtrees of query which match index with index. + * + * @param query + * @return TupleExpr + */ + public static TupleExpr process(TupleExpr query, List<ExternalTupleSet> indexSet) { + + boolean indexPlaced = false; + TupleExpr rtn = query.clone(); + QueryNodeCount qnc = new QueryNodeCount(); + rtn.visit(qnc); + + if(qnc.getNodeCount()/2 < indexSet.size()) { + return null; + } + + + //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())) { + + ExternalTupleSet eTup = (ExternalTupleSet) index.clone(); + SPBubbleDownVisitor indexVistor = new SPBubbleDownVisitor(eTup); + rtn.visit(indexVistor); + FilterBubbleManager fbmv = new FilterBubbleManager(eTup); + rtn.visit(fbmv); + SubsetEqualsVisitor subIndexVis = new SubsetEqualsVisitor(eTup, rtn); + rtn.visit(subIndexVis); + indexPlaced = subIndexVis.indexPlaced(); + if(!indexPlaced) { + break; + } + + } + + } + if(indexPlaced) { + return rtn; + } else { + return null; + } + + } else { + throw new IllegalArgumentException("Invalid Query."); + } + } + + + + + + // 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); + + } + + @Override + 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); + } + + @Override + 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; + } + + @Override + 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. + //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; + } + + @Override + 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); + + } + + @Override + 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(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(); + private boolean indexPlaced = false; + + + public SubsetEqualsVisitor(ExternalTupleSet index, TupleExpr query) { + this.tuple = index.getTupleExpr(); + this.set = index; + indexQNode = ((Projection) tuple).getArg(); + sSet = getQNodes(indexQNode); + + } + + public boolean indexPlaced() { + return indexPlaced; + } + + + @Override + 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); + indexPlaced = true; + return; + } else { + if (node.getLeftArg() instanceof StatementPattern && sSet.size() == 1) { + if(sSet.contains(node.getLeftArg())) { + node.setLeftArg(set); + indexPlaced = true; + } else if(sSet.contains(node.getRightArg())) { + node.setRightArg(set); + indexPlaced = true; + } else { + return; + } + } + else { + super.meet(node); + } + } + } else if (eSet.containsAll(sSet)) { + + super.meet(node); + + } else { + return; + } + + } + //to account for index consisting of only filter and BindingSetAssignment nodes + @Override + public void meet(Filter node) { + + Set<QueryModelNode> eSet = getQNodes(node); + + if (eSet.containsAll(sSet)) { + + if (eSet.equals(sSet)) { + node.replaceWith(set); + indexPlaced = true; + return; + } else { + node.getArg().visit(this); + } + } + } + + + @Override + public void meet(StatementPattern node) { + return; + } + } + + // 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; + } + + @Override + public void meet(Projection node) { + node.getArg().visit(this); + } + + @Override + public void meet(Filter node) { + node.getArg().visit(this); + } + + + + + + @Override + 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; + } + + @Override + 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)) { + + if (queryNode.getLeftArg() instanceof ExternalTupleSet) { + QueryModelNode temp = queryNode.getLeftArg(); + queryNode.setLeftArg(queryNode.getRightArg()); + queryNode.setRightArg((TupleExpr)temp); + } else { + + QNodeExchanger qnev = new QNodeExchanger(queryNode.getRightArg(), this.extTuples); + queryNode.visit(qnev); + queryNode.replaceChildNode(queryNode.getRightArg(), 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; + } + + @Override + 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(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); + } + + } + + + + public static class QueryNodeCount extends QueryModelVisitorBase<RuntimeException> { + + private int nodeCount; + + public QueryNodeCount() { + nodeCount = 0; + } + + public int getNodeCount() { + return nodeCount; + } + + + @Override + public void meet(StatementPattern node) { + nodeCount += 1; + return; + } + + @Override + public void meet(Filter node) { + nodeCount += 1; + node.getArg().visit(this); + } + + } + + + +}
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexListPruner.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexListPruner.java b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexListPruner.java new file mode 100644 index 0000000..8fbcbe0 --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexListPruner.java @@ -0,0 +1,31 @@ +package mvm.rya.indexing.IndexPlanValidator; + +/* + * 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.ExternalTupleSet; + +public interface IndexListPruner { + + public List<ExternalTupleSet> getRelevantIndices(List<ExternalTupleSet> indexList); + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexPlanValidator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexPlanValidator.java b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexPlanValidator.java new file mode 100644 index 0000000..74df958 --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexPlanValidator.java @@ -0,0 +1,210 @@ +package mvm.rya.indexing.IndexPlanValidator; + +/* + * 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.Iterator; +import java.util.NoSuchElementException; +import java.util.Set; + +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.StatementPattern; +import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; + +import com.google.common.collect.Sets; + + + + +public class IndexPlanValidator implements TupleValidator { + + private boolean omitCrossProd = false; + + + public IndexPlanValidator(boolean omitCrossProd) { + this.omitCrossProd = omitCrossProd; + } + + public void setOmitCrossProd(boolean omitCrossProd) { + this.omitCrossProd = omitCrossProd; + } + + + @Override + public boolean isValid(TupleExpr te) { + + TupleValidateVisitor tv = new TupleValidateVisitor(); + te.visit(tv); + + return tv.isValid(); + } + + + + + public int getValidTupleSize(Iterator<TupleExpr> iter) { + + int size = 0; + + while(iter.hasNext()) { + if(isValid(iter.next())) { + size++; + } + } + + return size; + + } + + + + @Override + public Iterator<TupleExpr> getValidTuples(Iterator<TupleExpr> tupleIter) { + + final Iterator<TupleExpr> iter = tupleIter; + + return new Iterator<TupleExpr>() { + + private TupleExpr next = null; + private boolean hasNextCalled = false; + private boolean isEmpty = false; + + @Override + public boolean hasNext() { + + if (!hasNextCalled && !isEmpty) { + while (iter.hasNext()) { + TupleExpr temp = iter.next(); + if (isValid(temp)) { + next = temp; + hasNextCalled = true; + return true; + } + } + isEmpty = true; + return false; + } else if(isEmpty) { + return false; + }else { + return true; + } + } + + @Override + public TupleExpr next() { + + if (hasNextCalled) { + hasNextCalled = false; + return next; + } else if(isEmpty) { + throw new NoSuchElementException(); + }else { + if (this.hasNext()) { + hasNextCalled = false; + return next; + } else { + throw new NoSuchElementException(); + } + } + } + + @Override + public void remove() { + + throw new UnsupportedOperationException("Cannot delete from iterator!"); + + } + + }; + } + + private boolean isJoinValid(Join join) { + + Set<String> leftBindingNames = join.getLeftArg().getBindingNames(); + Set<String> rightBindingNames = join.getRightArg().getBindingNames(); + + + //System.out.println("Left binding names are " + leftBindingNames + " and right binding names are " + rightBindingNames); + + if (Sets.intersection(leftBindingNames, rightBindingNames).size() == 0) { + if (omitCrossProd) { + return false; + } else { + return true; + } + + } else { + if (join.getRightArg() instanceof ExternalTupleSet) { + + return ((ExternalTupleSet) join.getRightArg()).supportsBindingSet(leftBindingNames); + + } else { + return true; + } + } + + } + + public class TupleValidateVisitor extends QueryModelVisitorBase<RuntimeException> { + + private boolean isValid = true; + + public boolean isValid() { + return isValid; + } + + @Override + public void meet(Projection node) { + node.getArg().visit(this); + } + + @Override + public void meet(StatementPattern node) { + return; + } + + public void meet(BindingSetAssignment node) { + return; + } + + @Override + public void meet(Filter node) { + node.getArg().visit(this); + } + + @Override + public void meet(Join node) { + if (isJoinValid(node)) { + super.meet(node); + } else { + isValid = false; + return; + } + } + + } + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexTupleGenerator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexTupleGenerator.java b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexTupleGenerator.java new file mode 100644 index 0000000..3586a5e --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexTupleGenerator.java @@ -0,0 +1,33 @@ +package mvm.rya.indexing.IndexPlanValidator; + +/* + * 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.Iterator; + +import org.openrdf.query.algebra.TupleExpr; + +public interface IndexTupleGenerator { + + + public Iterator<TupleExpr> getPlans(Iterator<TupleExpr> indexPlans); + + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexedExecutionPlanGenerator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexedExecutionPlanGenerator.java b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexedExecutionPlanGenerator.java new file mode 100644 index 0000000..22b1e85 --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexedExecutionPlanGenerator.java @@ -0,0 +1,127 @@ +package mvm.rya.indexing.IndexPlanValidator; + +/* + * 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.Iterator; +import java.util.List; +import java.util.NoSuchElementException; + +import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; +import mvm.rya.indexing.pcj.matching.QueryVariableNormalizer; + +import org.openrdf.query.algebra.Projection; +import org.openrdf.query.algebra.TupleExpr; + +import com.google.common.collect.Lists; + +public class IndexedExecutionPlanGenerator implements ExternalIndexMatcher { + + private final TupleExpr query; + private final List<ExternalTupleSet> normalizedIndexList; + + public IndexedExecutionPlanGenerator(TupleExpr query, List<ExternalTupleSet> indexList) { + this.query = query; + final VarConstantIndexListPruner vci = new VarConstantIndexListPruner(query); + normalizedIndexList = getNormalizedIndices(vci.getRelevantIndices(indexList)); + } + + public List<ExternalTupleSet> getNormalizedIndices() { + return normalizedIndexList; + } + + @Override + public Iterator<TupleExpr> getIndexedTuples() { + + final ValidIndexCombinationGenerator vic = new ValidIndexCombinationGenerator(query); + final Iterator<List<ExternalTupleSet>> iter = vic.getValidIndexCombos(normalizedIndexList); + return new Iterator<TupleExpr>() { + private TupleExpr next = null; + private boolean hasNextCalled = false; + private boolean isEmpty = false; + + @Override + public boolean hasNext() { + + if (!hasNextCalled && !isEmpty) { + while (iter.hasNext()) { + final TupleExpr temp = GeneralizedExternalProcessor.process(query, iter.next()); + if (temp != null) { + next = temp; + hasNextCalled = true; + return true; + } + } + isEmpty = true; + return false; + } else if(isEmpty) { + return false; + } else { + return true; + } + } + + @Override + public TupleExpr next() { + + if (hasNextCalled) { + hasNextCalled = false; + return next; + } else if(isEmpty) { + throw new NoSuchElementException(); + }else { + if (this.hasNext()) { + hasNextCalled = false; + return next; + } else { + throw new NoSuchElementException(); + } + } + } + + @Override + public void remove() { + throw new UnsupportedOperationException("Cannot delete from iterator!"); + } + }; + } + + private List<ExternalTupleSet> getNormalizedIndices(List<ExternalTupleSet> indexSet) { + + ExternalTupleSet tempIndex; + final List<ExternalTupleSet> normalizedIndexSet = Lists.newArrayList(); + + for (final ExternalTupleSet e : indexSet) { + List<TupleExpr> tupList = null; + try { + tupList = QueryVariableNormalizer.getNormalizedIndex(query, e.getTupleExpr()); + } catch (final Exception e1) { + e1.printStackTrace(); + } + + for (final TupleExpr te : tupList) { + tempIndex = (ExternalTupleSet) e.clone(); + tempIndex.setProjectionExpr((Projection) te); + normalizedIndexSet.add(tempIndex); + } + } + return normalizedIndexSet; + } +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexedQueryPlanSelector.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexedQueryPlanSelector.java b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexedQueryPlanSelector.java new file mode 100644 index 0000000..dbd1972 --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/IndexedQueryPlanSelector.java @@ -0,0 +1,32 @@ +package mvm.rya.indexing.IndexPlanValidator; + +/* + * 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.Iterator; + +import org.openrdf.query.algebra.TupleExpr; + +public interface IndexedQueryPlanSelector { + + public TupleExpr getThreshholdQueryPlan(Iterator<TupleExpr> tupleList, double threshhold, + double indexWeight, double commonVarWeight, double dirProdWeight); + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/ThreshholdPlanSelector.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/ThreshholdPlanSelector.java b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/ThreshholdPlanSelector.java new file mode 100644 index 0000000..a333dcb --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/ThreshholdPlanSelector.java @@ -0,0 +1,240 @@ +package mvm.rya.indexing.IndexPlanValidator; + +/* + * 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.Iterator; +import java.util.Set; + +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.helpers.QueryModelVisitorBase; + +import com.google.common.collect.Sets; + +public class ThreshholdPlanSelector implements IndexedQueryPlanSelector { + + private TupleExpr query; + private int queryNodeCount = 0; + + public ThreshholdPlanSelector(TupleExpr query) { + this.query = query; + QueryNodeCount qnc = new QueryNodeCount(); + query.visit(qnc); + + this.queryNodeCount = qnc.getNodeCount(); + + if(queryNodeCount == 0) { + throw new IllegalArgumentException("TupleExpr must contain at least one node!"); + } + } + + + + + @Override + public TupleExpr getThreshholdQueryPlan(Iterator<TupleExpr> tuples, double threshhold, double indexWeight, + double commonVarWeight, double extProdWeight) { + + if (threshhold < 0 || threshhold > 1) { + throw new IllegalArgumentException("Threshhold must be between 0 and 1!"); + } + double minCost = Double.MAX_VALUE; + TupleExpr minTup = null; + + double tempCost = 0; + TupleExpr tempTup = null; + + + + while (tuples.hasNext()) { + + tempTup = tuples.next(); + tempCost = getCost(tempTup, indexWeight, commonVarWeight, extProdWeight); + + if (tempCost < minCost) { + minCost = tempCost; + minTup = tempTup; + } + + if (minCost <= threshhold) { + return minTup; + } + + } + + return minTup; + } + + public double getCost(TupleExpr te, double indexWeight, double commonVarWeight, double dirProdWeight) { + + if (indexWeight + commonVarWeight + dirProdWeight != 1) { + throw new IllegalArgumentException("Weights must sum to 1!"); + } + + if(te == null) { + throw new IllegalArgumentException("TupleExpr cannot be null!"); + } + + QueryNodeCount qnc = new QueryNodeCount(); + te.visit(qnc); + + double nodeCount = qnc.getNodeCount(); + double commonJoinVars = qnc.getCommonJoinVarCount(); + double joinVars = qnc.getJoinVarCount(); + double joinCount = qnc.getJoinCount(); + double dirProdCount = qnc.getDirProdCount(); + double dirProductScale; + + if(queryNodeCount > nodeCount) { + dirProductScale = 1/((double)(queryNodeCount - nodeCount)); + } else { + dirProductScale = 1/((double)(queryNodeCount - nodeCount + 1)); + } + + double joinVarRatio; + double dirProductRatio; + + if(joinVars != 0) { + joinVarRatio = (joinVars - commonJoinVars) / joinVars; + } else { + joinVarRatio = 0; + } + + if(joinCount != 0) { + dirProductRatio = dirProdCount / joinCount; + } else { + dirProductRatio = 0; + } + + + double cost = indexWeight * (nodeCount / queryNodeCount) + commonVarWeight*joinVarRatio + + dirProdWeight *dirProductRatio*dirProductScale; + +// System.out.println("Tuple is " + te + " and cost is " + cost); +// System.out.println("Node count is " + nodeCount + " and query node count is " + queryNodeCount); +// System.out.println("Common join vars are " + commonJoinVars + " and join vars " + joinVars); +// System.out.println("Join count is " + joinCount + " and direct prod count is " + dirProdCount); + + return cost; + } + + public static class QueryNodeCount extends QueryModelVisitorBase<RuntimeException> { + + private int nodeCount = 0; + private int commonJoinVars = 0; + private int joinVars = 0; + private int joinCount = 0; + private int dirProdCount = 0; + + public int getCommonJoinVarCount() { + return commonJoinVars; + } + + public int getJoinVarCount() { + return joinVars; + } + + public int getNodeCount() { + return nodeCount; + } + + public int getJoinCount() { + return joinCount; + } + + public int getDirProdCount() { + return dirProdCount; + } + + public void meet(Projection node) { + node.getArg().visit(this); + } + + public void meetNode(QueryModelNode node) { + if (node instanceof ExternalTupleSet) { + nodeCount += 1; + return; + } + super.meetNode(node); + return; + } + + @Override + public void meet(StatementPattern node) { + nodeCount += 1; + return; + } + + @Override + public void meet(Filter node) { + nodeCount += 1; + node.getArg().visit(this); + } + + public void meet(BindingSetAssignment node) { + nodeCount += 1; + return; + } + + @Override + public void meet(Join node) { + + int tempCount = 0; + + Set<String> lNames = node.getLeftArg().getAssuredBindingNames(); + Set<String> rNames = node.getRightArg().getAssuredBindingNames(); + + for(String s: node.getLeftArg().getBindingNames()) { + if(s.startsWith("-const-")) { + lNames.remove(s); + } + } + + for(String s: node.getRightArg().getBindingNames()) { + if(s.startsWith("-const-")) { + rNames.remove(s); + } + } + + + joinVars += Math.min(lNames.size(), rNames.size()); + tempCount = Sets.intersection(lNames, rNames).size(); + if (tempCount == 0) { + dirProdCount += 1; + } else { + commonJoinVars += tempCount; + } + joinCount += 1; + + super.meet(node); + + } + + } + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/TupleExecutionPlanGenerator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/TupleExecutionPlanGenerator.java b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/TupleExecutionPlanGenerator.java new file mode 100644 index 0000000..2776a9e --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/TupleExecutionPlanGenerator.java @@ -0,0 +1,215 @@ +package mvm.rya.indexing.IndexPlanValidator; + +/* + * 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.Collection; +import java.util.Iterator; +import java.util.List; +import java.util.NoSuchElementException; +import java.util.Set; + +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.helpers.QueryModelVisitorBase; + +import com.beust.jcommander.internal.Lists; +import com.google.common.collect.Collections2; +import com.google.common.collect.Sets; + +public class TupleExecutionPlanGenerator implements IndexTupleGenerator { + + + + @Override + public Iterator<TupleExpr> getPlans(Iterator<TupleExpr> indexPlans) { + + final Iterator<TupleExpr> iter = indexPlans; + + return new Iterator<TupleExpr>() { + + private TupleExpr next = null; + private boolean hasNextCalled = false; + private boolean isEmpty = false; + Iterator<TupleExpr> tuples = null; + + @Override + public boolean hasNext() { + + if (!hasNextCalled && !isEmpty) { + if (tuples != null && tuples.hasNext()) { + next = tuples.next(); + hasNextCalled = true; + return true; + } else { + while (iter.hasNext()) { + tuples = getPlans(iter.next()).iterator(); + if (tuples == null) { + throw new IllegalStateException("Plans cannot be null!"); + } + next = tuples.next(); + hasNextCalled = true; + return true; + } + isEmpty = true; + return false; + } + } else if (isEmpty) { + return false; + } else { + return true; + } + } + + @Override + public TupleExpr next() { + + if (hasNextCalled) { + hasNextCalled = false; + return next; + } else if(isEmpty) { + throw new NoSuchElementException(); + }else { + if (this.hasNext()) { + hasNextCalled = false; + return next; + } else { + throw new NoSuchElementException(); + } + + } + + } + + @Override + public void remove() { + throw new UnsupportedOperationException("Cannot delete from iterator!"); + } + + }; + + } + + private List<TupleExpr> getPlans(TupleExpr te) { + + + NodeCollector nc = new NodeCollector(); + te.visit(nc); + + Set<QueryModelNode> nodeSet = nc.getNodeSet(); + List<Filter> filterList = nc.getFilterSet(); + Projection projection = nc.getProjection().clone(); + + List<TupleExpr> queryPlans = Lists.newArrayList(); + + Collection<List<QueryModelNode>> plans = Collections2.permutations(nodeSet); + + for (List<QueryModelNode> p : plans) { + if (p.size() == 0) { + throw new IllegalArgumentException("Tuple must contain at least one node!"); + } else if (p.size() == 1) { + queryPlans.add(te); + } else { + queryPlans.add(buildTuple(p, filterList, projection)); + } + } + + return queryPlans; + } + + private TupleExpr buildTuple(List<QueryModelNode> nodes, List<Filter> filters, Projection projection) { + + Projection proj = (Projection)projection.clone(); + Join join = null; + + join = new Join((TupleExpr) nodes.get(0).clone(), (TupleExpr) nodes.get(1).clone()); + + for (int i = 2; i < nodes.size(); i++) { + join = new Join(join, (TupleExpr) nodes.get(i).clone()); + } + + if (filters.size() == 0) { + proj.setArg(join); + return proj; + } else { + TupleExpr queryPlan = join; + for (Filter f : filters) { + Filter filt = (Filter) f.clone(); + filt.setArg(queryPlan); + queryPlan = filt; + } + proj.setArg(queryPlan); + return proj; + } + + } + + public static class NodeCollector extends QueryModelVisitorBase<RuntimeException> { + + private Set<QueryModelNode> nodeSet = Sets.newHashSet(); + private List<Filter> filterSet = Lists.newArrayList(); + private Projection projection; + + public Projection getProjection() { + return projection; + } + + public Set<QueryModelNode> getNodeSet() { + return nodeSet; + } + + public List<Filter> getFilterSet() { + return filterSet; + } + + @Override + public void meet(Projection node) { + projection = node; + node.getArg().visit(this); + } + + @Override + public void meetNode(QueryModelNode node) throws RuntimeException { + if (node instanceof ExternalTupleSet || node instanceof BindingSetAssignment + || node instanceof StatementPattern) { + nodeSet.add(node); + } + super.meetNode(node); + } + + @Override + public void meet(Filter node) { + filterSet.add(node); + node.getArg().visit(this); + } + + } + + + + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/TupleReArranger.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/TupleReArranger.java b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/TupleReArranger.java new file mode 100644 index 0000000..089ef5d --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/TupleReArranger.java @@ -0,0 +1,348 @@ +package mvm.rya.indexing.IndexPlanValidator; + +/* + * 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.Iterator; +import java.util.List; +import java.util.Map; +import java.util.NoSuchElementException; + +import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; +import mvm.rya.rdftriplestore.inference.DoNotExpandSP; +import mvm.rya.rdftriplestore.utils.FixedStatementPattern; + +import org.openrdf.query.algebra.Filter; +import org.openrdf.query.algebra.Join; +import org.openrdf.query.algebra.StatementPattern; +import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; + +import com.beust.jcommander.internal.Lists; +import com.google.common.collect.Collections2; +import com.google.common.collect.Maps; + + +//A given TupleExpr can be broken up into "join segments", which are sections of the TupleExpr where nodes can +//be freely exchanged. This class creates a list of permuted TupleExpr from a specified TupleExpr by permuting the nodes +//in each join segment. +public class TupleReArranger { + + private static Map<Join, List<List<TupleExpr>>> joinArgs; + private static Map<Join, List<Filter>> filterArgs; + + + public static Iterator<TupleExpr> getPlans(Iterator<TupleExpr> indexPlans) { + + final Iterator<TupleExpr> iter = indexPlans; + + return new Iterator<TupleExpr>() { + + private TupleExpr next = null; + private boolean hasNextCalled = false; + private boolean isEmpty = false; + Iterator<TupleExpr> tuples = null; + + @Override + public boolean hasNext() { + + if (!hasNextCalled && !isEmpty) { + if (tuples != null && tuples.hasNext()) { + next = tuples.next(); + hasNextCalled = true; + return true; + } else { + while (iter.hasNext()) { + tuples = getTupleReOrderings(iter.next()).iterator(); + if (tuples == null) { + throw new IllegalStateException("Plans cannot be null!"); + } + next = tuples.next(); + hasNextCalled = true; + return true; + } + isEmpty = true; + return false; + } + } else if (isEmpty) { + return false; + } else { + return true; + } + } + + @Override + public TupleExpr next() { + + if (hasNextCalled) { + hasNextCalled = false; + return next; + } else if (isEmpty) { + throw new NoSuchElementException(); + } else { + if (this.hasNext()) { + hasNextCalled = false; + return next; + } else { + throw new NoSuchElementException(); + } + } + } + + @Override + public void remove() { + throw new UnsupportedOperationException("Cannot delete from iterator!"); + } + }; + } + + + //Give a TupleExpr, return list of join segment permuted TupleExpr + public static List<TupleExpr> getTupleReOrderings(TupleExpr te) { + + joinArgs = Maps.newHashMap(); + filterArgs = Maps.newHashMap(); + + NodeCollector nc = new NodeCollector(); + te.visit(nc); + joinArgs = nc.getPerms(); + List<Join> joins = Lists.newArrayList(joinArgs.keySet()); + + return getPlans(getReOrderings(joins), te); + + } + + + //iterates through the reOrder maps, and for each reOrder map builds a new, reordered tupleExpr + private static List<TupleExpr> getPlans(List<Map<Join, List<TupleExpr>>> reOrderings, TupleExpr te) { + + List<TupleExpr> queryPlans = Lists.newArrayList(); + PermInserter pm = new PermInserter(); + + for (Map<Join, List<TupleExpr>> order : reOrderings) { + TupleExpr clone = te.clone(); + pm.setReOrderMap(order); + clone.visit(pm); + queryPlans.add(clone); + } + + return queryPlans; + } + + + + //recursive method which produces a list of maps. Each map associates a join with + //a list of the non-join arguments below it contained in same join segment. The list + //represents an ordering of the + //non-join arguments and creating a TupleExpr from this map yields a new TupleExpr + //whose non-join arguments are permuted + private static List<Map<Join, List<TupleExpr>>> getReOrderings(List<Join> joins) { + Map<Join, List<TupleExpr>> reOrder = Maps.newHashMap(); + List<Map<Join, List<TupleExpr>>> reOrderings = Lists.newArrayList(); + getReOrderings(joins, reOrder, reOrderings); + return reOrderings; + + } + + private static void getReOrderings(List<Join> joins, Map<Join, List<TupleExpr>> reOrder, + List<Map<Join, List<TupleExpr>>> reOrderings) { + + if (joins.isEmpty()) { + reOrderings.add(reOrder); + return; + } + + List<Join> joinsCopy = Lists.newArrayList(joins); + Join join = joinsCopy.remove(0); + List<List<TupleExpr>> joinArgPerms = joinArgs.get(join); + for (List<TupleExpr> tupList : joinArgPerms) { + Map<Join, List<TupleExpr>> newReOrder = Maps.newHashMap(reOrder); + newReOrder.put(join, tupList); + getReOrderings(joinsCopy, newReOrder, reOrderings); + } + + return; + + } + + + //creates a map which associates each first join of a TupleExpr join segment with all permutations of + //the non-join nodes after it. More specifically, each join is associated with a list of TupleExpr + //lists, where each list represents an ordering of the non-join nodes following the associated join + private static class NodeCollector extends QueryModelVisitorBase<RuntimeException> { + + private static List<Filter> filterList; + + public Map<Join, List<List<TupleExpr>>> getPerms() { + return joinArgs; + } + + @Override + public void meet(Join node) { + + filterList = Lists.newArrayList(); + + List<TupleExpr> args = Lists.newArrayList(); + args = getJoinArgs(node, args); + List<List<TupleExpr>> argPerms = Lists.newArrayList(Collections2.permutations(args)); + joinArgs.put(node, argPerms); + filterArgs.put(node, filterList); + + for (TupleExpr te : args) { + if (!(te instanceof StatementPattern) && !(te instanceof ExternalTupleSet)) { + te.visit(this); + } + } + + } + + + //get all non-join nodes below tupleExpr in same join segment + private static List<TupleExpr> getJoinArgs(TupleExpr tupleExpr, List<TupleExpr> joinArgs) { + if (tupleExpr instanceof Join) { + if (!(((Join) tupleExpr).getLeftArg() instanceof FixedStatementPattern) + && !(((Join) tupleExpr).getRightArg() instanceof DoNotExpandSP)) { + Join join = (Join) tupleExpr; + getJoinArgs(join.getLeftArg(), joinArgs); + getJoinArgs(join.getRightArg(), joinArgs); + } // assumes all filter occur above first join of segment -- + // this should be the state + // after PrecompJoinOptimizer is called + } else if (tupleExpr instanceof Filter) { + filterList.add((Filter) tupleExpr); + getJoinArgs(((Filter) tupleExpr).getArg(), joinArgs); + } else { + joinArgs.add(tupleExpr); + } + + return joinArgs; + } + + } + + + + //for a given reOrder map, searches through TupleExpr and places each reordered collection + //of nodes at appropriate join + private static class PermInserter extends QueryModelVisitorBase<RuntimeException> { + + private Map<Join, List<TupleExpr>> reOrderMap = Maps.newHashMap(); + + public void setReOrderMap(Map<Join, List<TupleExpr>> reOrderMap) { + this.reOrderMap = reOrderMap; + } + + @Override + public void meet(Join node) { + + List<TupleExpr> reOrder = reOrderMap.get(node); + if (reOrder != null) { + List<Filter> filterList = Lists.newArrayList(filterArgs.get(node)); + node.replaceWith(getNewJoin(reOrder, getFilterChain(filterList))); + + for (TupleExpr te : reOrder) { + if (!(te instanceof StatementPattern) && !(te instanceof ExternalTupleSet)) { + te.visit(this); + } + } + } + super.meet(node); + } + } + + + // chain filters together and return front and back of chain + private static 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.clone(); + } else if (filterChainBottom == null) { + filterChainBottom = filter.clone(); + filterChainTop.setArg(filterChainBottom); + } else { + Filter newFilter = filter.clone(); + filterChainBottom.setArg(newFilter); + filterChainBottom = newFilter; + } + } + 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 static 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).clone(); + TupleExpr tempJoin; + TupleExpr temp = filterChain.get(0); + + if (joinArgs.size() > 1) { + tempJoin = new Join(joinArgs.remove(0).clone(), joinArgs.remove(0).clone()); + for (TupleExpr te : joinArgs) { + tempJoin = new Join(tempJoin, te.clone()); + } + } else { + tempJoin = joinArgs.remove(0).clone(); + } + + 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.remove(0).clone(), joinArgs.remove(0).clone()); + + for (TupleExpr te : joinArgs) { + newJoin = new Join(newJoin, te.clone()); + } + } + } else if (joinArgs.size() == 1) { + if (filterChain.size() > 0) { + newJoin = filterChain.get(0); + if (filterChain.size() == 1) { + ((Filter) newJoin).setArg(joinArgs.get(0).clone()); + } else { + ((Filter) filterChain.get(1)).setArg(joinArgs.get(0).clone()); + } + } else { + newJoin = joinArgs.get(0).clone(); + } + } else { + throw new IllegalStateException("JoinArgs size cannot be zero."); + } + return newJoin; + } + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/TupleValidator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/TupleValidator.java b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/TupleValidator.java new file mode 100644 index 0000000..4960d78 --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/TupleValidator.java @@ -0,0 +1,34 @@ +package mvm.rya.indexing.IndexPlanValidator; + +/* + * 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.Iterator; + +import org.openrdf.query.algebra.TupleExpr; + +public interface TupleValidator { + + public boolean isValid(TupleExpr te); + + public Iterator<TupleExpr> getValidTuples(Iterator<TupleExpr> tupleList); + + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/ValidIndexCombinationGenerator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/ValidIndexCombinationGenerator.java b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/ValidIndexCombinationGenerator.java new file mode 100644 index 0000000..483457f --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/IndexPlanValidator/ValidIndexCombinationGenerator.java @@ -0,0 +1,461 @@ +package mvm.rya.indexing.IndexPlanValidator; + +/* + * 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.Collections; +import java.util.Iterator; +import java.util.List; +import java.util.NoSuchElementException; +import java.util.Set; + +import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; + +import org.openrdf.query.algebra.Filter; +import org.openrdf.query.algebra.QueryModelNode; +import org.openrdf.query.algebra.StatementPattern; +import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; + +import com.google.common.base.Joiner; +import com.google.common.collect.Lists; +import com.google.common.collect.Sets; + +public class ValidIndexCombinationGenerator { + + private TupleExpr query; + private Set<String> invalidCombos = Sets.newTreeSet(); + private Set<QueryModelNode> spFilterSet; + + public ValidIndexCombinationGenerator(TupleExpr query) { + this.query = query; + SpFilterCollector sfc = new SpFilterCollector(); + query.visit(sfc); + spFilterSet = sfc.getSpFilterSet(); + } + + public Iterator<List<ExternalTupleSet>> getValidIndexCombos( + List<ExternalTupleSet> indexSet) { + + Collections.shuffle(indexSet); + final List<ExternalTupleSet> list = indexSet; + final Iterator<List<Integer>> iter = getValidCombos(list); + + return new Iterator<List<ExternalTupleSet>>() { + + private List<ExternalTupleSet> next = null; + private List<Integer> nextCombo = null; + private boolean hasNextCalled = false; + private boolean isEmpty = false; + + @Override + public boolean hasNext() { + + if (!hasNextCalled && !isEmpty) { + if (!iter.hasNext()) { + isEmpty = true; + return false; + } else { + nextCombo = iter.next(); + List<ExternalTupleSet> indexCombo = Lists + .newArrayList(); + for (Integer i : nextCombo) { + indexCombo.add(list.get(i)); + } + next = indexCombo; + hasNextCalled = true; + return true; + + } + + } else if (isEmpty) { + return false; + } else { + return true; + } + } + + @Override + public List<ExternalTupleSet> next() { + + if (hasNextCalled) { + hasNextCalled = false; + return next; + } else if (isEmpty) { + throw new NoSuchElementException(); + } else { + if (this.hasNext()) { + hasNextCalled = false; + return next; + } else { + throw new NoSuchElementException(); + } + } + } + + @Override + public void remove() { + + throw new UnsupportedOperationException( + "Cannot delete from iterator!"); + + } + + }; + + } + + private Iterator<List<Integer>> getValidCombos( + List<ExternalTupleSet> indexList) { + + final List<ExternalTupleSet> list = indexList; + final int indexSize = list.size(); + final Iterator<List<Integer>> iter = getCombos(indexSize); + + return new Iterator<List<Integer>>() { + + private List<Integer> next = null; + private boolean hasNextCalled = false; + private boolean isEmpty = false; + + @Override + public boolean hasNext() { + if (!hasNextCalled && !isEmpty) { + + while (iter.hasNext()) { + List<Integer> tempNext = iter.next(); + if (isValid(tempNext, list)) { + next = tempNext; + hasNextCalled = true; + return true; + } + + } + + isEmpty = true; + return false; + + } else if (isEmpty) { + return false; + } else { + return true; + } + } + + @Override + public List<Integer> next() { + + if (hasNextCalled) { + hasNextCalled = false; + return next; + } else if (isEmpty) { + throw new NoSuchElementException(); + } else { + if (this.hasNext()) { + hasNextCalled = false; + return next; + } else { + throw new NoSuchElementException(); + } + + } + + } + + @Override + public void remove() { + + throw new UnsupportedOperationException( + "Cannot delete from iterator!"); + + } + + }; + } + + private Iterator<List<Integer>> getCombos(int indexListSize) { + + final int indexSize = indexListSize; + final int maxSubListSize = spFilterSet.size() / 2; + + return new Iterator<List<Integer>>() { + + private List<Integer> next = null; + private boolean hasNextCalled = false; + private boolean isEmpty = false; + private int subListSize = Math.min(maxSubListSize, indexSize) + 1; + Iterator<List<Integer>> subList = null; + + @Override + public boolean hasNext() { + + if (!hasNextCalled && !isEmpty) { + if (subList != null && subList.hasNext()) { + next = subList.next(); + hasNextCalled = true; + return true; + } else { + subListSize--; + if (subListSize == 0) { + isEmpty = true; + return false; + } + subList = getCombos(subListSize, indexSize); + if (subList == null) { + throw new IllegalStateException( + "Combos cannot be null!"); + } + next = subList.next(); + hasNextCalled = true; + return true; + + } + } else if (isEmpty) { + return false; + } else { + return true; + } + } + + @Override + public List<Integer> next() { + + if (hasNextCalled) { + hasNextCalled = false; + return next; + } else if (isEmpty) { + throw new NoSuchElementException(); + } else { + if (this.hasNext()) { + hasNextCalled = false; + return next; + } else { + throw new NoSuchElementException(); + } + + } + + } + + @Override + public void remove() { + throw new UnsupportedOperationException( + "Cannot delete from iterator!"); + } + + }; + + } + + private Iterator<List<Integer>> getCombos(int subListSize, int indexListSize) { + + if (subListSize > indexListSize) { + throw new IllegalArgumentException( + "Sublist size must be less than or equal to list size!"); + } + + final int subSize = subListSize; + final int indexSize = indexListSize; + + return new Iterator<List<Integer>>() { + + private List<Integer> next = null; + private List<Integer> tempList = Lists.newArrayList(); + private boolean calledHasNext = false; + private boolean isEmpty = false; + + @Override + public boolean hasNext() { + + if (!calledHasNext && !isEmpty) { + if (next == null) { + for (int i = 0; i < subSize; i++) { + tempList.add(i); + } + next = tempList; + calledHasNext = true; + return true; + } else { + next = getNext(next, indexSize - 1); + if (next == null) { + isEmpty = true; + return false; + } else { + calledHasNext = true; + return true; + } + + } + } else if (isEmpty) { + return false; + } else { + return true; + } + + } + + @Override + public List<Integer> next() { + + if (calledHasNext) { + calledHasNext = false; + return next; + } else if (isEmpty) { + throw new NoSuchElementException(); + } else { + if (this.hasNext()) { + calledHasNext = false; + return next; + } else { + throw new NoSuchElementException(); + } + } + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + + } + + }; + } + + private List<Integer> getNext(List<Integer> prev, int maxInt) { + + List<Integer> returnList = Lists.newArrayList(); + int size = prev.size(); + int incrementPos = -1; + int incrementVal = 0; + + for (int i = 0; i < size; i++) { + if (prev.get(size - (i + 1)) != maxInt - i) { + incrementPos = size - (i + 1); + break; + } + } + + if (incrementPos == -1) { + return null; + } else { + + incrementVal = prev.get(incrementPos); + for (int i = 0; i < incrementPos; i++) { + returnList.add(prev.get(i)); + } + + for (int j = incrementPos; j < size; j++) { + returnList.add(++incrementVal); + } + + return returnList; + } + } + + private boolean isValid(List<Integer> combo, + List<ExternalTupleSet> indexList) { + + String s1 = Joiner.on("\u0000").join(combo).trim(); + + if (invalidCombos.contains(s1)) { + return false; + } else { + int valid = indicesDisjoint(combo, indexList); + + if (valid >= 0) { + String s2 = ""; + for (int i = 0; i < valid + 1; i++) { + if (s2.length() == 0) { + s2 = s2 + combo.get(i); + } else { + s2 = s2 + "\u0000" + combo.get(i); + } + } + invalidCombos.add(s2); + + for (int i = valid + 1; i < combo.size(); i++) { + s2 = s2 + "\u0000" + combo.get(i); + invalidCombos.add(s2); + } + + return false; + } else { + return true; + } + } + + } + + private int indicesDisjoint(List<Integer> combo, + List<ExternalTupleSet> indexList) { + + Set<QueryModelNode> indexNodes = Sets.newHashSet(); + Set<QueryModelNode> tempNodes; + TupleExpr temp; + + int j = 0; + for (Integer i : combo) { + temp = indexList.get(i).getTupleExpr(); + SpFilterCollector spf = new SpFilterCollector(); + temp.visit(spf); + tempNodes = spf.getSpFilterSet(); + if (Sets.intersection(indexNodes, tempNodes).size() == 0) { + indexNodes = Sets.union(indexNodes, tempNodes); + if (indexNodes.size() > spFilterSet.size()) { + return j; + } + } else { + return j; + } + j++; + } + + return -1; + } + + private static class SpFilterCollector extends + QueryModelVisitorBase<RuntimeException> { + + private Set<QueryModelNode> spFilterSet = Sets.newHashSet(); + + public int getNodeNumber() { + return spFilterSet.size(); + } + + public Set<QueryModelNode> getSpFilterSet() { + return spFilterSet; + } + + @Override + public void meet(StatementPattern node) { + + spFilterSet.add(node); + return; + + } + + @Override + public void meet(Filter node) { + + spFilterSet.add(node.getCondition()); + node.getArg().visit(this); + } + + } +}
