http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/96dd55ec/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJNodeConsolidator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJNodeConsolidator.java b/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJNodeConsolidator.java new file mode 100644 index 0000000..47d00dc --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJNodeConsolidator.java @@ -0,0 +1,628 @@ +package mvm.rya.indexing.pcj.matching; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.SortedSet; +import java.util.TreeSet; + +import org.openrdf.query.algebra.QueryModelNode; +import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.algebra.ValueExpr; + +import com.google.common.base.Preconditions; + +/** + * Given an order List view of an {@link OptionalJoinSegment} taken + * from a query and an OptionalJoinSegment representing a PCJ, + * this class attempts to consolidate the {@link QueryModelNode}s + * of the PCJ together within the query and order them in a way + * that is consistent with the PCJ. This is the key step in matching + * the PCJ to a subset of a query when LeftJoins are present. + * + */ +public class PCJNodeConsolidator { + + private TreeSet<PositionNode> leftJoinPosSet = new TreeSet<>( + new PositionComparator()); + private TreeSet<PositionNode> pcjPosSet = new TreeSet<>( + new PositionComparator()); + private TreeSet<PositionNode> lowerBoundSet = new TreeSet<>( + new PositionComparator()); // nonPcjNodes in query that + // pcjNodes cannot move past + private TreeSet<PositionNode> upperBoundSet = new TreeSet<>( + new PositionComparator());// nonPcjNodes in query that pcjNodes + // cannot move past + private int greatestLowerBound = -1; + private int leastUpperBound = Integer.MAX_VALUE; + + private List<QueryModelNode> queryNodes; + private List<QueryModelNode> pcjNodes; + private boolean consolidateCalled = false; + private boolean returnValConsolidate = false; + + public PCJNodeConsolidator(List<QueryModelNode> queryNodes, + List<QueryModelNode> pcjNodes) { + Preconditions.checkArgument(new HashSet<QueryModelNode>(queryNodes).containsAll(new HashSet<QueryModelNode>(pcjNodes))); + this.queryNodes = new ArrayList<>(queryNodes); + this.pcjNodes = new ArrayList<>(pcjNodes); + int i = 0; + for (QueryModelNode q : queryNodes) { + if (q instanceof FlattenedOptional) { + leftJoinPosSet.add(new PositionNode(q, i)); + } + if (pcjNodes.contains(q)) { + pcjPosSet.add(new PositionNode(q, i)); + } + i++; + } + } + + /** + * This method consolidates the PCJ nodes within the query. After this method is + * called, the PCJ nodes in the query will be completely consolidated if true is returned + * and will only be partially consolidated if false is return + * @return - true or false depending on whether nodes could be entirely consolidated + */ + public boolean consolidateNodes() { + if(consolidateCalled) { + return returnValConsolidate; + } + consolidateCalled = true; + returnValConsolidate = consolidate() && reOrderPcjNodes(); + return returnValConsolidate; + } + + /** + * + * @return List of the query's QueryModelNodes + */ + public List<QueryModelNode> getQueryNodes() { + return queryNodes; + } + + //assumes nodes are consolidated -- checks if they can be reordered to match pcj node list + private boolean reOrderPcjNodes() { + int pos = pcjPosSet.last().getPosition(); + for(int j = pcjNodes.size() - 1; j >= 0; j--) { + QueryModelNode node = pcjNodes.get(j); + int i = queryNodes.indexOf(node); + //use pcj node in queryNodes so FlattenedOptional boundVars + //are consistent with query + node = queryNodes.get(i); + if(!moveQueryNode(new PositionNode(node, i), pos)) { + return false; + } + pos--; + } + return true; + } + + private boolean consolidate() { + while (canConsolidate()) { + Move move = getNextMove(); + // if move is empty, then pcj nodes are + // consolidated + if (move.isEmpty) { + return true; + } + moveQueryNode(move.node, move.finalPos); + } + + return false; + } + + private boolean canConsolidate() { + if (greatestLowerBound < leastUpperBound) { + return true; + } + return adjustBounds(); + } + + // if l.u.b < g.l.b, attempt to push g.l.b up + // assume first pcj position node has position less + // than g.l.b. - this should be by design given that + // l.u.b <= g.l.b. and there has to be at least one pcj node + // positioned before l.u.b. + private boolean adjustBounds() { + + int finalPos = pcjPosSet.first().getPosition(); + PositionNode node = lowerBoundSet.last(); + + return moveQueryNode(node, finalPos); + } + + // assumes g.l.b <= l.u.b. + // iterates through pcj nodes in query from lowest position to + // highest looking for a difference in index position greater than + // one. Given the leftmost pair of nodes separated by two or more + // spaces, the leftmost node in the pair is moved so that its final + // position is one position to the left of the rightmost node. For + // example, given nodes at index 1 and index 3, the node at index 1 + // is advanced to index 2. This method returns the suggested Move, + // but does not actually perform the Move. + private Move getNextMove() { + + Iterator<PositionNode> posIterator = pcjPosSet.iterator(); + PositionNode current; + if (posIterator.hasNext()) { + current = posIterator.next(); + } else { + throw new IllegalStateException("PCJ has no nodes!"); + } + PositionNode next; + int pos1 = -1; + int pos2 = -1; + while (posIterator.hasNext()) { + next = posIterator.next(); + pos1 = current.getPosition(); + pos2 = next.getPosition(); + // move nodes are not adjacent + if (pos1 + 1 < pos2) { + if (leastUpperBound > pos2) { + return new Move(current, pos2 - 1); + } + // pos1 < leastUpperBound < pos2 b/c pos1 < leastUpperBound by + // design + else if(greatestLowerBound < pos1) { + return new Move(next, pos1 + 1); + } + //move current to node after greatestLowerBound + else { + return new Move(current, greatestLowerBound); + } + } + + current = next; + } + + return new Move(); + } + + private boolean moveQueryNode(PositionNode node, int position) { + + if (!canMoveNode(node, position)) { + if(upperBoundSet.size() > 0) { + leastUpperBound = upperBoundSet.first().getPosition(); + } + if(lowerBoundSet.size() > 0) { + greatestLowerBound = lowerBoundSet.last().getPosition(); + } + return false; + } + //update QueryModelNodes in leftJoin index so that FlattenedOptional + //var counts are correct + updateLeftJoinNodes(node, position); + //move node in queryNode list + updateNodeList(node, position, queryNodes); + //update bounds + updatePositionNodeSet(node, position, lowerBoundSet); + updatePositionNodeSet(node, position, upperBoundSet); + //update leastUppperBound and greatestLowerBound + if(upperBoundSet.size() > 0) { + leastUpperBound = upperBoundSet.first().getPosition(); + } + if(lowerBoundSet.size() > 0) { + greatestLowerBound = lowerBoundSet.last().getPosition(); + } + //update positions within leftJoin index + updatePositionNodeSet(node, position, leftJoinPosSet); + //no need to update entire set because pcj nodes are not moved + //past one another during consolidation + updatePositionNode(node, position, pcjPosSet); + + return true; + } + + private boolean canMoveNode(PositionNode node, int finalPos) { + PositionNode bound = getBounds(node, finalPos, queryNodes, leftJoinPosSet); + if (bound.isEmpty) { + return true; + } + addBound(bound, node, finalPos); + return false; + + } + + //adds bound to either lowerBoundSet or uppderBoundSet, depending on initial and + //final position of move + private void addBound(PositionNode bound, PositionNode node, int finalPos) { + int diff = finalPos - node.getPosition(); + + if(diff == 0) { + return; + } + + if (diff > 0) { + if (upperBoundSet.contains(bound)) { + return; + } else { + upperBoundSet.add(bound); + } + } else { + if (lowerBoundSet.contains(bound)) { + return; + } else { + lowerBoundSet.add(bound); + } + } + } + + + // updates nodes in given TreeSet between node.getPosition() and position + private void updatePositionNodeSet(PositionNode node, int position, + TreeSet<PositionNode> set) { + + if(set.size() == 0) { + return; + } + + int oldPos = node.getPosition(); + int diff = position - oldPos; + SortedSet<PositionNode> posNodes; + boolean containsNode = false; + + if (diff == 0) { + return; + } + + //remove node before decrementing or incrementing to prevent overwriting + if(set.contains(node)) { + containsNode = true; + set.remove(node); + } + + if (diff > 0) { + posNodes = set + .subSet(node, false, new PositionNode(position), true); + + List<PositionNode> pNodeList = new ArrayList<>(); + for(PositionNode pos: posNodes) { + pNodeList.add(pos); + } + // decrement posNodes + for (PositionNode pos : pNodeList) { + int p = pos.getPosition() - 1; + updatePositionNode(pos, p, set); + } + } else { + posNodes = set + .subSet(new PositionNode(position), true, node, false); + //create list to iterate in reverse order + List<PositionNode> pNodeList = new ArrayList<>(); + for(PositionNode pos: posNodes) { + pNodeList.add(pos); + } + //increment elements of TreeSet in reverse order so + //that no collisions occur - PositionNodes are incremented + //into slot created by removing node + for(int i = pNodeList.size() - 1; i >= 0; i--) { + PositionNode pNode = pNodeList.get(i); + int p = pNode.getPosition() + 1; + updatePositionNode(pNode, p, set); + } + } + + if(containsNode) { + node.setPosition(position); + set.add(node); + } + + } + + //updates the var counts in specified left join index + private void updateLeftJoinNodes(PositionNode node, int finalPos) { + if(node.getNode() instanceof ValueExpr) { + return; + } + + int diff = finalPos - node.getPosition(); + + if (diff == 0) { + return; + } + + if (node.isOptional) { + leftJoinPosSet.remove(node); + FlattenedOptional optional = (FlattenedOptional)node.getNode(); + if (diff < 0) { + for (int i = node.getPosition() - 1; i > finalPos - 1; i--) { + QueryModelNode tempNode = queryNodes.get(i); + if (tempNode instanceof ValueExpr) { + continue; + } + optional.addArg((TupleExpr) tempNode); + } + } else { + for (int i = node.getPosition() + 1; i < finalPos + 1; i++) { + QueryModelNode tempNode = queryNodes.get(i); + if (tempNode instanceof ValueExpr) { + continue; + } + optional.removeArg((TupleExpr) tempNode); + } + } + node.setNode(optional); + //FlattenedOptional equals does not take into account var counts + //The following three lines update the var count in the optional in list + int index = queryNodes.indexOf(optional); + queryNodes.remove(optional); + queryNodes.add(index, optional); + leftJoinPosSet.add(node); + + } else { + TupleExpr te = (TupleExpr) node.getNode(); + SortedSet<PositionNode> optionals; + if (diff < 0) { + optionals = leftJoinPosSet.subSet(new PositionNode(finalPos), true, node, false); + for (PositionNode pNode : optionals) { + FlattenedOptional optional = (FlattenedOptional) pNode + .getNode(); + optional.removeArg(te); + } + } else { + optionals = leftJoinPosSet.subSet(node, false, new PositionNode(finalPos), true); + for (PositionNode pNode : optionals) { + FlattenedOptional optional = (FlattenedOptional) pNode + .getNode(); + optional.addArg(te); + } + } + } + + } + + + + //works only if moving node to final position does not move it across + //another node in set + private void updatePositionNode(PositionNode node, int position, + TreeSet<PositionNode> set) { + set.remove(node); + node.setPosition(position); + set.add(node); + } + + // assumes input data fall within capacity of list + private void updateNodeList(PositionNode node, int finalPos, + List<QueryModelNode> list) { + int initialPos = node.getPosition(); + QueryModelNode qNode = list.remove(initialPos); + if (finalPos < list.size()) { + list.add(finalPos, qNode); + } else { + list.add(qNode); + } + } + + /** + * + * @param node + * @param finalPos + * @param list + * @param leftJoinNodes + * @return PositionNode - if node cannot be move to final position, this + * method returns a non-empty PositionNode representing a bound to the move. + * If it can, it returns an empty PositionNode. + */ + // determine if given node can be moved to finalPos + // assumes node.position and finalPos fall within index range of list + private PositionNode getBounds(PositionNode node, int finalPos, + List<QueryModelNode> list, TreeSet<PositionNode> leftJoinNodes) { + + //filters can be moved up and pushed down join segment + //without affecting bound and unbound variables of + //FlattenedOptionals -- Filters can be pushed down as + //far as possible because it is assumed that any variable + //that appears in a Filter also appears in a PCJ node + //if Filters can be grouped, then Filter variables will + //automatically be bound + if(node.getNode() instanceof ValueExpr) { + return new PositionNode(); + } + + int diff = finalPos - node.getPosition(); + + if (diff == 0) { + return new PositionNode(); + } + + if (node.isOptional) { + FlattenedOptional optional = ((FlattenedOptional)node.getNode()).clone(); + if (diff < 0) { + for (int i = node.getPosition() - 1; i > finalPos - 1; i--) { + QueryModelNode tempNode = list.get(i); + if (tempNode instanceof ValueExpr) { + continue; + } + + if (!optional.canAddTuple((TupleExpr) tempNode)) { + return new PositionNode(tempNode, i); + } + + if(tempNode instanceof FlattenedOptional) { + FlattenedOptional tempOptional = (FlattenedOptional) tempNode; + if(!tempOptional.canRemoveTuple(optional)) { + return new PositionNode(tempNode, i); + } + + } + optional.addArg((TupleExpr) tempNode); + } + } else { + for (int i = node.getPosition() + 1; i < finalPos + 1; i++) { // TODO + // check + // bounds + QueryModelNode tempNode = list.get(i); + if (tempNode instanceof ValueExpr) { + continue; + } + if (!optional.canRemoveTuple((TupleExpr) tempNode)) { + return new PositionNode(tempNode, i); + } + + if(tempNode instanceof FlattenedOptional) { + FlattenedOptional tempOptional = (FlattenedOptional) tempNode; + if(!tempOptional.canAddTuple(optional)) { + return new PositionNode(tempNode, i); + } + } + optional.removeArg((TupleExpr) tempNode); + } + } + + return new PositionNode(); + + } else { + TupleExpr te = (TupleExpr) node.getNode(); + SortedSet<PositionNode> leftJoins; + if (diff < 0) { + leftJoins = leftJoinNodes.subSet(new PositionNode(finalPos), true, node, false); + + for (PositionNode pNode : leftJoins) { + FlattenedOptional optional = (FlattenedOptional) pNode + .getNode(); + if (!optional.canRemoveTuple(te)) { + return new PositionNode(pNode); + } + } + } else { + + leftJoins = leftJoinNodes.subSet(node, false, new PositionNode(finalPos), true); + for (PositionNode pNode : leftJoins) { + FlattenedOptional optional = (FlattenedOptional) pNode + .getNode(); + if (!optional.canAddTuple(te)) { + return new PositionNode(pNode); + } + } + } + + return new PositionNode(); + + } + + } + + + static class Move { + + PositionNode node; + int finalPos; + boolean isEmpty = true; + + public Move(PositionNode node, int finalPos) { + this.node = node; + this.finalPos = finalPos; + this.isEmpty = false; + } + + public Move() { + } + + } + + static class PositionNode { + + private int position; + private QueryModelNode node; + private boolean isOptional = false; + boolean isEmpty = true; + + public PositionNode(QueryModelNode node, int position) { + this.node = node; + this.position = position; + this.isOptional = node instanceof FlattenedOptional; + isEmpty = false; + } + + public PositionNode(PositionNode node) { + this(node.node, node.position); + } + + public PositionNode(int position) { + this.position = position; + isEmpty = false; + } + + public PositionNode() { + + } + + /** + * @return the position + */ + public int getPosition() { + return position; + } + + /** + * @param position + * the position to set + */ + public void setPosition(int position) { + this.position = position; + } + + /** + * @return the node + */ + public QueryModelNode getNode() { + return node; + } + + public void setNode(QueryModelNode node) { + this.node = node; + } + + public boolean isOptional() { + return isOptional; + } + + @Override + public String toString() { + return "Node: " + node + " Position: " + position; + } + + } + + + class PositionComparator implements Comparator<PositionNode> { + + @Override + public int compare(PositionNode node1, PositionNode node2) { + + if (node1.position < node2.position) { + return -1; + } + if (node1.position > node2.position) { + return 1; + } + + return 0; + } + + } + +}
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/96dd55ec/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJOptimizer.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJOptimizer.java b/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJOptimizer.java new file mode 100644 index 0000000..a4ec2a0 --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJOptimizer.java @@ -0,0 +1,348 @@ +package mvm.rya.indexing.pcj.matching; + +/* + * 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.Set; + +import mvm.rya.api.RdfCloudTripleStoreConfiguration; +import mvm.rya.indexing.IndexPlanValidator.IndexPlanValidator; +import mvm.rya.indexing.IndexPlanValidator.IndexedExecutionPlanGenerator; +import mvm.rya.indexing.IndexPlanValidator.ThreshholdPlanSelector; +import mvm.rya.indexing.IndexPlanValidator.TupleReArranger; +import mvm.rya.indexing.IndexPlanValidator.ValidIndexCombinationGenerator; +import mvm.rya.indexing.accumulo.ConfigUtils; +import mvm.rya.indexing.external.tupleSet.AccumuloIndexSet; +import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; + +import org.apache.accumulo.core.client.AccumuloException; +import org.apache.accumulo.core.client.AccumuloSecurityException; +import org.apache.accumulo.core.client.Connector; +import org.apache.accumulo.core.client.TableNotFoundException; +import org.apache.hadoop.conf.Configurable; +import org.apache.hadoop.conf.Configuration; +import org.apache.log4j.Logger; +import org.apache.rya.indexing.pcj.storage.PcjException; +import org.apache.rya.indexing.pcj.storage.accumulo.PcjTables; +import org.openrdf.query.BindingSet; +import org.openrdf.query.Dataset; +import org.openrdf.query.MalformedQueryException; +import org.openrdf.query.QueryEvaluationException; +import org.openrdf.query.algebra.Filter; +import org.openrdf.query.algebra.Join; +import org.openrdf.query.algebra.LeftJoin; +import org.openrdf.query.algebra.Projection; +import org.openrdf.query.algebra.QueryModelNode; +import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.algebra.evaluation.QueryOptimizer; +import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; +import org.openrdf.sail.SailException; + +import com.google.common.collect.Lists; +import com.google.common.collect.Maps; + +/** + * {@link QueryOptimizer} which matches {@link TupleExpr}s associated with + * pre-computed queries to sub-queries of a given query. Each matched sub-query + * is replaced by an {@link ExternalTupleSet} node to delegate that portion of + * the query to the pre-computed query index. + * <p> + * + * A query is be broken up into {@link QuerySegment}s. Pre-computed query + * indices, or {@link ExternalTupleset} objects, are compared against the + * {@link QueryModelNode}s in each QuerySegment. If an ExternalTupleSets nodes + * match a subset of the given QuerySegments nodes, those nodes are replaced by + * the ExternalTupleSet in the QuerySegment. + * + */ +public class PCJOptimizer implements QueryOptimizer, Configurable { + + private static final Logger log = Logger.getLogger(PCJOptimizer.class); + private List<ExternalTupleSet> indexSet; + private Configuration conf; + private boolean init = false; + + public PCJOptimizer() { + } + + public PCJOptimizer(Configuration conf) { + this.conf = conf; + try { + indexSet = PCJOptimizerUtilities.getValidPCJs(getAccIndices(conf)); // TODO + // validate + // PCJs + // during + // table + // creation + } catch (MalformedQueryException | SailException + | QueryEvaluationException | TableNotFoundException + | AccumuloException | AccumuloSecurityException | PcjException e) { + e.printStackTrace(); + } + init = true; + } + + public PCJOptimizer(List<ExternalTupleSet> indices, boolean useOptimalPcj) { + this.indexSet = PCJOptimizerUtilities.getValidPCJs(indices); + conf = new Configuration(); + conf.setBoolean(ConfigUtils.USE_OPTIMAL_PCJ, useOptimalPcj); + } + + @Override + public void setConf(Configuration conf) { + this.conf = conf; + if (!init) { + try { + indexSet = PCJOptimizerUtilities + .getValidPCJs(getAccIndices(conf)); + } catch (MalformedQueryException | SailException + | QueryEvaluationException | TableNotFoundException + | AccumuloException | AccumuloSecurityException + | PcjException e) { + e.printStackTrace(); + } + init = true; + } + } + + @Override + public Configuration getConf() { + return conf; + } + + /** + * This method optimizes a specified query by matching subsets of it with + * PCJ queries. + * + * @param tupleExpr + * - the query to be optimized + */ + @Override + public void optimize(TupleExpr tupleExpr, Dataset dataset, + BindingSet bindings) { + + Projection projection = PCJOptimizerUtilities.getProjection(tupleExpr); + if (projection == null) { + log.debug("TupleExpr has no Projection. Invalid TupleExpr."); + return; + } + IndexedExecutionPlanGenerator iep = new IndexedExecutionPlanGenerator( + tupleExpr, indexSet); + List<ExternalTupleSet> pcjs = iep.getNormalizedIndices(); + // first standardize query by pulling all filters to top of query if + // they exist + // using TopOfQueryFilterRelocator + tupleExpr = TopOfQueryFilterRelocator.moveFiltersToTop(tupleExpr); + + if (ConfigUtils.getUseOptimalPCJ(conf) && pcjs.size() > 0) { + + // get potential relevant index combinations + ValidIndexCombinationGenerator vic = new ValidIndexCombinationGenerator( + tupleExpr); + Iterator<List<ExternalTupleSet>> iter = vic + .getValidIndexCombos(pcjs); + TupleExpr bestTup = null; + TupleExpr tempTup = null; + double tempCost = 0; + double minCost = Double.MAX_VALUE; + + while (iter.hasNext()) { + // apply join visitor to place external index nodes in query + TupleExpr clone = tupleExpr.clone(); + QuerySegmentPCJMatchVisitor.matchPCJs(clone, iter.next()); + + // get all valid execution plans for given external index + // combination by considering all + // permutations of nodes in TupleExpr + IndexPlanValidator ipv = new IndexPlanValidator(false); + Iterator<TupleExpr> validTups = ipv + .getValidTuples(TupleReArranger.getTupleReOrderings( + clone).iterator()); + + // set valid plan according to a specified cost threshold, where + // cost depends on specified weights + // for number of external index nodes, common variables among + // joins in execution plan, and number of + // external products in execution plan + ThreshholdPlanSelector tps = new ThreshholdPlanSelector( + tupleExpr); + tempTup = tps.getThreshholdQueryPlan(validTups, .4, .5, .2, .3); + + // choose best threshhold TupleExpr among all index node + // combinations + tempCost = tps.getCost(tempTup, .5, .2, .3); + if (tempCost < minCost) { + minCost = tempCost; + bestTup = tempTup; + } + } + if (bestTup != null) { + Projection bestTupProject = PCJOptimizerUtilities + .getProjection(bestTup); + projection.setArg(bestTupProject.getArg()); + } + return; + } else if (pcjs.size() > 0) { + QuerySegmentPCJMatchVisitor.matchPCJs(tupleExpr, pcjs); + } else { + return; + } + } + + /** + * This visitor navigates query until it reaches either a Join, Filter, or + * LeftJoin. Once it reaches this node, it gets the appropriate PCJMatcher + * from the {@link QuerySegmentPCJMatchVisitor} and uses this to match each + * of the PCJs to the {@link QuerySegment} starting with the Join, Filter, + * or LeftJoin. Once each PCJ has been compared for matching, the portion of + * the query starting with the Join, Filter, or LeftJoin is replaced by the + * {@link TupleExpr} returned by {@link PCJMatcher#getQuery()}. This visitor + * then visits each of the nodes returned by {@link PCJMatcher#getUnmatchedArgs()}. + * + */ + static class QuerySegmentPCJMatchVisitor extends + QueryModelVisitorBase<RuntimeException> { + + private static List<ExternalTupleSet> pcjs; + private static final QuerySegmentPCJMatchVisitor INSTANCE = new QuerySegmentPCJMatchVisitor(); + + private QuerySegmentPCJMatchVisitor() { + }; + + public static void matchPCJs(TupleExpr te, + List<ExternalTupleSet> indexSet) { + pcjs = indexSet; + te.visit(INSTANCE); + } + + @Override + public void meet(Join node) { + PCJMatcher matcher = PCJMatcherFactory.getPCJMatcher(node); + for (ExternalTupleSet pcj : pcjs) { + matcher.matchPCJ(pcj); + } + + node.replaceWith(matcher.getQuery()); + Set<TupleExpr> unmatched = matcher.getUnmatchedArgs(); + PCJOptimizerUtilities.relocateFilters(matcher.getFilters()); + + for (TupleExpr tupleExpr : unmatched) { + tupleExpr.visit(this); + } + } + + @Override + public void meet(LeftJoin node) { + PCJMatcher matcher = PCJMatcherFactory.getPCJMatcher(node); + for (ExternalTupleSet pcj : pcjs) { + matcher.matchPCJ(pcj); + } + + node.replaceWith(matcher.getQuery()); + Set<TupleExpr> unmatched = matcher.getUnmatchedArgs(); + PCJOptimizerUtilities.relocateFilters(matcher.getFilters()); + + for (TupleExpr tupleExpr : unmatched) { + tupleExpr.visit(this); + } + } + + @Override + public void meet(Filter node) { + PCJMatcher matcher = PCJMatcherFactory.getPCJMatcher(node); + for (ExternalTupleSet pcj : pcjs) { + matcher.matchPCJ(pcj); + } + + node.replaceWith(matcher.getQuery()); + Set<TupleExpr> unmatched = matcher.getUnmatchedArgs(); + PCJOptimizerUtilities.relocateFilters(matcher.getFilters()); + + for (TupleExpr tupleExpr : unmatched) { + tupleExpr.visit(this); + } + } + + } + + /** + * + * + * @param conf + * - client configuration + * + * @return - list of {@link ExternalTupleSet}s or PCJs that are either + * specified by user in Configuration or exist in system. + * + * @throws MalformedQueryException + * @throws SailException + * @throws QueryEvaluationException + * @throws TableNotFoundException + * @throws AccumuloException + * @throws AccumuloSecurityException + * @throws PcjException + */ + private static List<ExternalTupleSet> getAccIndices(Configuration conf) + throws MalformedQueryException, SailException, + QueryEvaluationException, TableNotFoundException, + AccumuloException, AccumuloSecurityException, PcjException { + + List<String> tables = null; + + if (conf instanceof RdfCloudTripleStoreConfiguration) { + tables = ((RdfCloudTripleStoreConfiguration) conf).getPcjTables(); + } + + String tablePrefix = conf + .get(RdfCloudTripleStoreConfiguration.CONF_TBL_PREFIX); + Connector c = ConfigUtils.getConnector(conf); + Map<String, String> indexTables = Maps.newLinkedHashMap(); + PcjTables pcj = new PcjTables(); + + if (tables != null && !tables.isEmpty()) { + for (final String table : tables) { + indexTables + .put(table, pcj.getPcjMetadata(c, table).getSparql()); + } + } else { + for (final String table : c.tableOperations().list()) { + if (table.startsWith(tablePrefix + "INDEX")) { + indexTables.put(table, pcj.getPcjMetadata(c, table) + .getSparql()); + } + } + + } + final List<ExternalTupleSet> index = Lists.newArrayList(); + + if (indexTables.isEmpty()) { + System.out.println("No Index found"); + } else { + for (final String table : indexTables.keySet()) { + final String indexSparqlString = indexTables.get(table); + index.add(new AccumuloIndexSet(indexSparqlString, c, table)); + } + } + return index; + } + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/96dd55ec/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJOptimizerUtilities.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJOptimizerUtilities.java b/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJOptimizerUtilities.java new file mode 100644 index 0000000..485e466 --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJOptimizerUtilities.java @@ -0,0 +1,346 @@ +package mvm.rya.indexing.pcj.matching; + +/* + * 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.Set; + +import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; +import mvm.rya.indexing.pcj.matching.QueryVariableNormalizer.VarCollector; + +import org.openrdf.query.algebra.Difference; +import org.openrdf.query.algebra.EmptySet; +import org.openrdf.query.algebra.Filter; +import org.openrdf.query.algebra.Intersection; +import org.openrdf.query.algebra.Join; +import org.openrdf.query.algebra.LeftJoin; +import org.openrdf.query.algebra.Projection; +import org.openrdf.query.algebra.QueryModelNode; +import org.openrdf.query.algebra.StatementPattern; +import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.algebra.UnaryTupleOperator; +import org.openrdf.query.algebra.Union; +import org.openrdf.query.algebra.Var; +import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; +import org.openrdf.query.algebra.helpers.VarNameCollector; + +import com.google.common.collect.Sets; + +public class PCJOptimizerUtilities { + + + /** + * This method determines whether an index node is valid. Criteria for a + * valid node are that is have two or more {@link StatementPattern} nodes or + * at least one {@link Filter} and one StatementPattern node. Additionally, + * the number of variables in the Filter cannot exceed the number of + * variables among all non-Filter nodes in the TupleExpr. Also, this method + * calls the {@link ValidQueryVisitor} to determine if the + * TupleExpr contains an invalid node type. + * + * @param node - node to be checked for validity + * @return - true if valid and false otherwise + */ + public static boolean isPCJValid(TupleExpr node) { + + final ValidQueryVisitor vqv = new ValidQueryVisitor(); + node.visit(vqv); + + if (vqv.isValid() && (vqv.getJoinCount() > 0 || vqv.getFilters().size() > 0 && vqv.getSPs().size() > 0)){ + if (vqv.getFilters().size() > 0) { + final Set<String> spVars = getVarNames(vqv.getSPs()); + final Set<String> fVarNames = getVarNames(vqv.getFilters()); + // check that all vars contained in filters also occur in SPs + return spVars.containsAll(fVarNames); + } else { + return true; + } + } else { + return false; + } + } + + + /** + * This method determines whether an index node is valid. Criteria for a + * valid node are that is have two or more {@link StatementPattern} nodes or + * at least one {@link Filter} and one StatementPattern node. Additionally, + * the number of variables in the Filter cannot exceed the number of + * variables among all non-Filter nodes in the TupleExpr. + * + * @param node - PCJ {@link ExternalTupleSet} index node to be checked for validity + * @return - true if valid and false otherwise + */ + public static boolean isPCJValid(ExternalTupleSet node) { + return isPCJValid(node.getTupleExpr()); + } + + public static List<ExternalTupleSet> getValidPCJs( + List<ExternalTupleSet> pcjs) { + + Iterator<ExternalTupleSet> iterator = pcjs.iterator(); + while (iterator.hasNext()) { + ExternalTupleSet pcj = iterator.next(); + if (!isPCJValid(pcj)) { + iterator.remove(); + } + } + return pcjs; + } + + + public static Projection getProjection(TupleExpr te) { + ProjectionVisitor visitor = new ProjectionVisitor(); + te.visit(visitor); + return visitor.node; + } + + static class ProjectionVisitor extends QueryModelVisitorBase<RuntimeException> { + + Projection node = null; + + @Override + public void meet(Projection node) { + this.node = node; + } + } + + + /** + * @param filters + * - filters to be pushed down into next {@link QuerySegment}, or + * as far down as binding variable names permit. + */ + public static void relocateFilters(Set<Filter> filters) { + for (Filter filter : filters) { + FilterRelocator.relocate(filter); + } + } + + private static Set<String> getVarNames(Collection<QueryModelNode> nodes) { + List<String> tempVars; + final Set<String> nodeVarNames = Sets.newHashSet(); + + for (final QueryModelNode s : nodes) { + tempVars = VarCollector.process(s); + for (final String t : tempVars) { + nodeVarNames.add(t); + } + } + return nodeVarNames; + } + + /** + * A visitor which checks a TupleExpr associated with an ExternalTupleSet to + * determine whether the TupleExpr contains an invalid node. + * + */ + private static class ValidQueryVisitor extends + QueryModelVisitorBase<RuntimeException> { + + private boolean isValid = true; + private Set<QueryModelNode> filterSet = Sets.newHashSet(); + private Set<QueryModelNode> spSet = Sets.newHashSet(); + private int joinCount = 0; + + public Set<QueryModelNode> getFilters() { + return filterSet; + } + + public Set<QueryModelNode> getSPs() { + return spSet; + } + + public boolean isValid() { + return isValid; + } + + public int getJoinCount() { + return joinCount; + } + + @Override + public void meet(Projection node) { + node.getArg().visit(this); + } + + @Override + public void meet(Filter node) { + filterSet.add(node.getCondition()); + node.getArg().visit(this); + } + + @Override + public void meet(StatementPattern node) { + spSet.add(node); + } + + @Override + public void meet(Join node) { + joinCount++; + super.meet(node); + } + + @Override + public void meet(LeftJoin node) { + joinCount++; + super.meet(node); + } + + @Override + public void meetNode(QueryModelNode node) { + if (!(node instanceof Join || node instanceof LeftJoin + || node instanceof StatementPattern || node instanceof Var + || node instanceof Union || node instanceof Filter || node instanceof Projection)) { + isValid = false; + return; + } + super.meetNode(node); + } + + } + + /** + * Relocates filters based on the binding variables contained in the + * {@link Filter}. If you don't specify the FilterRelocator to stop at the + * first {@link Join}, the relocator pushes the filter as far down the query + * plan as possible, checking if the nodes below contain its binding + * variables. If stopAtFirstJoin = true, the Filter is inserted at the first + * Join node encountered. The relocator tracks whether the node stays in the + * join segment or is inserted outside of the Join segment and returns true + * if the Filter stays in the segment and false otherwise. + * + */ + + protected static class FilterRelocator extends + QueryModelVisitorBase<RuntimeException> { + + protected Filter filter; + protected Set<String> filterVars; + + public FilterRelocator(Filter filter) { + this.filter = filter; + filterVars = VarNameCollector.process(filter.getCondition()); + } + + public static void relocate(Filter filter) { + final FilterRelocator fr = new FilterRelocator(filter); + filter.visit(fr); + } + + @Override + protected void meetNode(QueryModelNode node) { + // By default, do not traverse + assert node instanceof TupleExpr; + + if (node instanceof UnaryTupleOperator) { + if (((UnaryTupleOperator) node).getArg().getBindingNames() + .containsAll(filterVars)) { + ((UnaryTupleOperator) node).getArg().visit(this); + } + } + relocate(filter, (TupleExpr) node); + } + + @Override + public void meet(Join join) { + if (join.getRightArg().getBindingNames().containsAll(filterVars)) { + // All required vars are bound by the left expr + join.getRightArg().visit(this); + } else if (join.getLeftArg().getBindingNames() + .containsAll(filterVars)) { + // All required vars are bound by the right expr + join.getLeftArg().visit(this); + } else { + relocate(filter, join); + } + } + + @Override + public void meet(Filter node) { + node.getArg().visit(this); + } + + @Override + public void meet(LeftJoin leftJoin) { + if (leftJoin.getLeftArg().getBindingNames().containsAll(filterVars)) { + leftJoin.getLeftArg().visit(this); + } else { + relocate(filter, leftJoin.getLeftArg()); + } + } + + @Override + public void meet(Union union) { + if (Sets.intersection(union.getRightArg().getBindingNames(), filterVars).size() > 0) { + relocate(filter, union.getRightArg()); + } else if (Sets.intersection(union.getLeftArg().getBindingNames(), filterVars).size() > 0) { + Filter clone = new Filter(filter.getArg(), filter + .getCondition().clone()); + relocate(clone, union.getLeftArg()); + } + } + + @Override + public void meet(Difference node) { + if (Sets.intersection(node.getRightArg().getBindingNames(), filterVars).size() > 0) { + relocate(filter, node.getRightArg()); + } else if (Sets.intersection(node.getLeftArg().getBindingNames(), filterVars).size() > 0) { + Filter clone = new Filter(filter.getArg(), filter + .getCondition().clone()); + relocate(clone, node.getLeftArg()); + } + } + + @Override + public void meet(Intersection node) { + if (Sets.intersection(node.getRightArg().getBindingNames(), filterVars).size() > 0) { + relocate(filter, node.getRightArg()); + } else if (Sets.intersection(node.getLeftArg().getBindingNames(), filterVars).size() > 0) { + Filter clone = new Filter(filter.getArg(), filter + .getCondition().clone()); + relocate(clone, node.getLeftArg()); + } + } + + @Override + public void meet(EmptySet node) { + if (filter.getParentNode() != null) { + // Remove filter from its original location + filter.replaceWith(filter.getArg()); + } + } + + protected void relocate(Filter filter, TupleExpr newFilterArg) { + if (!filter.getArg().equals(newFilterArg)) { + if (filter.getParentNode() != null) { + // Remove filter from its original location + filter.replaceWith(filter.getArg()); + } + // Insert filter at the new location + newFilterArg.replaceWith(filter); + filter.setArg(newFilterArg); + } + } + } + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/96dd55ec/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/QueryNodesToTupleExpr.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/QueryNodesToTupleExpr.java b/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/QueryNodesToTupleExpr.java new file mode 100644 index 0000000..ee0a7b0 --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/QueryNodesToTupleExpr.java @@ -0,0 +1,194 @@ +package mvm.rya.indexing.pcj.matching; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.util.ArrayList; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +import org.openrdf.query.algebra.Filter; +import org.openrdf.query.algebra.Join; +import org.openrdf.query.algebra.LeftJoin; +import org.openrdf.query.algebra.QueryModelNode; +import org.openrdf.query.algebra.TupleExpr; + +import com.google.common.collect.Lists; + +/** + * This class converts a given collection of {@link QueryModelNode}s + * into a {@link TupleExpr}. The primary purpose of this class is + * to reconstruct a TupleExpr representation of a {@link QuerySegment} + * from its List view. + * + */ +public class QueryNodesToTupleExpr { + + private List<QueryModelNode> queryNodes; + private Set<Filter> filters; + + public QueryNodesToTupleExpr(List<QueryModelNode> queryNodes, Set<Filter> filters) { + this.queryNodes = queryNodes; + this.filters = filters; + } + + /** + * + * @return - a TupleExprAndNodes object that consists of the the + * TupleExpr representation of the List of QueryModelNodes and + * the nodes used to build the TupleExpr. + */ + public TupleExprAndNodes getTupleAndNodes() { + List<QueryModelNode> nodeCopy = new ArrayList<>(); + Set<Filter> setCopy = new HashSet<>(); + for(QueryModelNode q: queryNodes) { + nodeCopy.add(q.clone()); + } + for(Filter f: filters) { + setCopy.add(f.clone()); + } + TupleExpr te = buildQuery(nodeCopy, setCopy); + + return new TupleExprAndNodes(te, nodeCopy, setCopy); + } + + + private TupleExpr buildQuery(List<QueryModelNode> queryNodes, + Set<Filter> filters) { + List<Filter> chain = getFilterChain(filters); + return getNewJoin(queryNodes, chain); + } + + // chain filters together and return front and back of chain + private static List<Filter> getFilterChain(Set<Filter> filters) { + final List<Filter> filterTopBottom = Lists.newArrayList(); + Filter filterChainTop = null; + Filter filterChainBottom = null; + + for (final Filter filter : filters) { + if (filterChainTop == null) { + filterChainTop = filter; + filter.setParentNode(null); + } else if (filterChainBottom == null) { + filterChainBottom = filter; + filterChainTop.setArg(filterChainBottom); + } else { + filterChainBottom.setArg(filter); + filterChainBottom = filter; + } + } + if (filterChainTop != null) { + filterTopBottom.add(filterChainTop); + } + if (filterChainBottom != null) { + filterTopBottom.add(filterChainBottom); + } + return filterTopBottom; + } + + // build newJoin node given remaining joinArgs and chain of filters + private static TupleExpr getNewJoin(List<QueryModelNode> args, + List<Filter> filterChain) { + TupleExpr newJoin; + TupleExpr tempJoin; + final List<TupleExpr> joinArgs = Lists.newArrayList(); + for (QueryModelNode q : args) { + if (q instanceof TupleExpr) { + joinArgs.add(0, (TupleExpr) q); + } else { + throw new IllegalArgumentException("Invalid query node!"); + } + } + + if (joinArgs.size() > 1) { + TupleExpr left = joinArgs.remove(0); + TupleExpr right = joinArgs.remove(0); + tempJoin = getJoin(left, right); + for (int i = joinArgs.size() - 1; i >= 0; i--) { + tempJoin = getJoin(tempJoin, joinArgs.get(i)); + } + if (filterChain.size() == 0) { + newJoin = tempJoin; + } else if (filterChain.size() == 1) { + newJoin = filterChain.get(0); + ((Filter) newJoin).setArg(tempJoin); + } else { + newJoin = filterChain.get(0); + filterChain.get(1).setArg(tempJoin); + } + } else if (joinArgs.size() == 1) { + tempJoin = joinArgs.get(0); + if (filterChain.size() == 0) { + newJoin = tempJoin; + } else if (filterChain.size() == 1) { + newJoin = filterChain.get(0); + ((Filter) newJoin).setArg(tempJoin); + } else { + newJoin = filterChain.get(0); + filterChain.get(1).setArg(tempJoin); + } + } else { + throw new IllegalStateException("JoinArgs size cannot be zero."); + } + return newJoin; + } + + private static TupleExpr getJoin(TupleExpr oldJoin, TupleExpr newArg) { + if (newArg instanceof FlattenedOptional) { + return new LeftJoin(oldJoin, + ((FlattenedOptional) newArg).getRightArg()); + } else { + return new Join(oldJoin, newArg); + } + } + + public static class TupleExprAndNodes { + + private TupleExpr te; + private List<QueryModelNode> nodes; + private Set<Filter> filters; + + public TupleExprAndNodes(TupleExpr te, List<QueryModelNode> nodes, Set<Filter> filters) { + this.te = te; + this.nodes = nodes; + this.filters = filters; + } + + public TupleExpr getTupleExpr() { + return te; + } + + public List<QueryModelNode> getNodes() { + return nodes; + } + + public Set<Filter> getFilters() { + return filters; + } + + @Override + public String toString() { + return "Query: " + te + " Nodes: " + nodes; + } + + + } + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/96dd55ec/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/QuerySegment.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/QuerySegment.java b/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/QuerySegment.java new file mode 100644 index 0000000..2f7f499 --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/QuerySegment.java @@ -0,0 +1,83 @@ +package mvm.rya.indexing.pcj.matching; + +/* + * 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 java.util.Set; + +import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; +import mvm.rya.indexing.pcj.matching.QueryNodesToTupleExpr.TupleExprAndNodes; + +import org.openrdf.query.algebra.Filter; +import org.openrdf.query.algebra.QueryModelNode; + +/** + * A QuerySegment represents a subset of a query to be compared to PCJs for + * query matching. The QuerySegment is represented as a List, where the order of + * the nodes in the list is determined by a Visitor as it traverses the Segment + * from top down, visiting right children before left. + * + */ +public interface QuerySegment { + + /** + * + * @return - an unordered view of the {@link QueryModelNode}s in the segment + */ + public Set<QueryModelNode> getUnOrderedNodes(); + + /** + * + * @return - an ordered view of the {@link QueryModelNode}s in the segment. + */ + public List<QueryModelNode> getOrderedNodes(); + + public Set<Filter> getFilters(); + + /** + * + * @param segment + * - this method verifies whether the specified segment is + * contained in this segment + * @return - true if contained and false otherwise + */ + public boolean containsQuerySegment(QuerySegment segment); + + /** + * Sets List of {@link QueryModelNode}s representing this QuerySegment + * to specified list + + * @param nodes - nodes to set + */ + public void setNodes(List<QueryModelNode> nodes); + + /** + * + * @param nodeToReplace - QuerySegment representation of PCJ to match + * with subset of this QuerySegment + * @param PCJ - PCJ to replace matching QuerySegment nodes if match occurs + * @return - true if match occurs and false otherwise + */ + public boolean replaceWithPcj(QuerySegment nodeToReplace, + ExternalTupleSet PCJ); + + public TupleExprAndNodes getQuery(); + +}
