rya-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From miha...@apache.org
Subject [08/69] [abbrv] [partial] incubator-rya git commit: RYA-198 Renaming Files
Date Sat, 15 Oct 2016 20:06:28 GMT
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);
+		}
+
+	}
+}


Mime
View raw message