http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/JoinSegment.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/JoinSegment.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/JoinSegment.java deleted file mode 100644 index ca012a9..0000000 --- a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/JoinSegment.java +++ /dev/null @@ -1,130 +0,0 @@ -package org.apache.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 org.apache.rya.indexing.external.tupleSet.ExternalTupleSet; -import org.apache.rya.rdftriplestore.inference.DoNotExpandSP; -import org.apache.rya.rdftriplestore.utils.FixedStatementPattern; - -import org.openrdf.query.algebra.Filter; -import org.openrdf.query.algebra.Join; -import org.openrdf.query.algebra.QueryModelNode; -import org.openrdf.query.algebra.TupleExpr; -import org.openrdf.query.algebra.ValueExpr; - -import com.google.common.base.Preconditions; -import com.google.common.collect.Sets; - -/** - * This class represents a portion of a {@link TupleExpr} query that PCJ queries - * are compared to. A JoinSegment is comprised of a collection of - * {@link QueryModelNode}s that are connected by {@link Join}s. In the case, the - * QueryModelNodes can commute within the JoinSegment, which makes JoinSegments - * a natural way to partition a query for PCJ matching. A query is decomposed - * into JoinSegments and PCJ queries can easily be compared to the {@link QueryModelNode}s - * contained in the segment using set operations. - * - */ -public class JoinSegment extends AbstractQuerySegment { - - public JoinSegment(Join join) { - Preconditions.checkNotNull(join); - createJoinSegment(join); - } - - public JoinSegment(Filter filter) { - Preconditions.checkNotNull(filter); - createJoinSegment(filter); - } - - private void createJoinSegment(TupleExpr te) { - orderedNodes = getJoinArgs(te, orderedNodes); - unorderedNodes = Sets.newHashSet(orderedNodes); - } - - /** - * This method matches the ordered nodes returned by - * {@link JoinSegment#getOrderedNodes()} for nodeToReplace with a subset of - * the ordered nodes for this JoinSegment. The order of the nodes for - * nodeToReplace must match the order of the nodes as a subset of - * orderedNodes - * - * @param nodeToReplace - * - nodes to be replaced by pcj - * @param pcj - * - pcj node that will replace specified query nodes - */ - @Override - public boolean replaceWithPcj(QuerySegment nodeToReplace, - ExternalTupleSet pcj) { - Preconditions.checkNotNull(nodeToReplace != null); - Preconditions.checkNotNull(pcj); - if (!containsQuerySegment(nodeToReplace)) { - return false; - } - Set<QueryModelNode> nodeSet = nodeToReplace.getUnOrderedNodes(); - orderedNodes.removeAll(nodeSet); - orderedNodes.add(pcj); - unorderedNodes.removeAll(nodeSet); - unorderedNodes.add(pcj); - for (QueryModelNode q : nodeSet) { - if (q instanceof ValueExpr) { - conditionMap.remove(q); - } - } - return true; - } - - /** - * - * @param tupleExpr - * - the query object that will be traversed by this method - * @param joinArgs - * - all nodes connected by Joins and Filters - * @return - List containing all nodes connected by Joins, LeftJoins, and - * Filters. This List contains the - * @param ValueExpr - * in place of the Filter - */ - private List<QueryModelNode> getJoinArgs(TupleExpr tupleExpr, - List<QueryModelNode> joinArgs) { - - if (tupleExpr instanceof Join) { - if (!(((Join) tupleExpr).getLeftArg() instanceof FixedStatementPattern) - && !(((Join) tupleExpr).getRightArg() instanceof DoNotExpandSP)) { - Join join = (Join) tupleExpr; - getJoinArgs(join.getRightArg(), joinArgs); - getJoinArgs(join.getLeftArg(), joinArgs); - } - } else if (tupleExpr instanceof Filter) { - Filter filter = (Filter) tupleExpr; - joinArgs.add(filter.getCondition()); - conditionMap.put(filter.getCondition(), filter); - getJoinArgs(filter.getArg(), joinArgs); - } else { - joinArgs.add(tupleExpr); - } - return joinArgs; - } - -}
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/JoinSegmentPCJMatcher.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/JoinSegmentPCJMatcher.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/JoinSegmentPCJMatcher.java deleted file mode 100644 index a318d30..0000000 --- a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/JoinSegmentPCJMatcher.java +++ /dev/null @@ -1,106 +0,0 @@ -package org.apache.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 org.apache.rya.indexing.external.tupleSet.ExternalTupleSet; - -import org.openrdf.query.algebra.Filter; -import org.openrdf.query.algebra.Join; -import org.openrdf.query.algebra.QueryModelNode; -import org.openrdf.query.algebra.TupleExpr; -import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; - -/** - * This class is responsible for matching PCJ nodes with subsets of the - * {@link QueryModelNode}s found in {@link JoinSegment}s. Each PCJ is reduced to - * a bag of QueryModelNodes and set operations can be used to determine if the - * PCJ is a subset of the JoinSegment. If it is a subset, the PCJ node replaces - * the QueryModelNodes in the JoinSegment. - * - */ - -public class JoinSegmentPCJMatcher extends AbstractPCJMatcher { - - public JoinSegmentPCJMatcher(Join join) { - segment = new JoinSegment(join); - segmentNodeList = new ArrayList<>(segment.getOrderedNodes()); - pcjToSegment = new PCJToJoinSegment(); - } - - public JoinSegmentPCJMatcher(Filter filter) { - segment = new JoinSegment(filter); - segmentNodeList = new ArrayList<>(segment.getOrderedNodes()); - pcjToSegment = new PCJToJoinSegment(); - } - - /** - * @param pcjNodes - * - {@link QueryModelNode}s to be replaced - * @param pcj - * - the PCJ node to be compared to pcjNodes - */ - @Override - public boolean matchPCJ(QuerySegment pcjNodes, ExternalTupleSet pcj) { - - if(PCJOptimizerUtilities.pcjContainsLeftJoins(pcj)) { - return false; - } - - boolean nodesReplaced = segment.replaceWithPcj(pcjNodes, pcj); - if (nodesReplaced) { - tupleAndNodesUpToDate = false; - segmentNodeList = segment.getOrderedNodes(); - } - - return nodesReplaced; - } - - /** - * This class extracts the {@link JoinSegment} from the {@link TupleExpr} of - * specified PCJ. - * - */ - static class PCJToJoinSegment extends - QueryModelVisitorBase<RuntimeException> implements PCJToSegment { - - private JoinSegment segment; - - @Override - public QuerySegment getSegment(ExternalTupleSet pcj) { - segment = null; - pcj.getTupleExpr().visit(this); - return segment; - } - - @Override - public void meet(Join join) { - segment = new JoinSegment(join); - } - - @Override - public void meet(Filter filter) { - segment = new JoinSegment(filter); - } - - } - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/OptionalJoinSegment.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/OptionalJoinSegment.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/OptionalJoinSegment.java deleted file mode 100644 index 0e4ff2f..0000000 --- a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/OptionalJoinSegment.java +++ /dev/null @@ -1,146 +0,0 @@ -package org.apache.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 org.apache.rya.indexing.external.tupleSet.ExternalTupleSet; -import org.apache.rya.rdftriplestore.inference.DoNotExpandSP; -import org.apache.rya.rdftriplestore.utils.FixedStatementPattern; - -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 org.openrdf.query.algebra.ValueExpr; - -import com.google.common.base.Preconditions; -import com.google.common.collect.Sets; - -/** - * An OptionalJoinSegment represents the portion of a {@link TupleExpr} that is - * connected by Filters, LeftJoins, and Joins. All nodes in the portion of the - * TupleExpr that are connected via these node types are gathered into an - * ordered and an unordered list that can easily be compared with - * {@link ExternalTupleSet} nodes for sub-query matching to use with Precomputed - * Joins. - * - */ -public class OptionalJoinSegment extends AbstractQuerySegment { - - public OptionalJoinSegment(Join join) { - Preconditions.checkNotNull(join); - createJoinSegment(join); - } - - public OptionalJoinSegment(LeftJoin join) { - Preconditions.checkNotNull(join); - createJoinSegment(join); - } - - public OptionalJoinSegment(Filter filter) { - Preconditions.checkNotNull(filter); - createJoinSegment(filter); - } - - private void createJoinSegment(TupleExpr te) { - orderedNodes = getJoinArgs(te, orderedNodes); - unorderedNodes = Sets.newHashSet(orderedNodes); - } - - /** - * This method matches the ordered nodes returned by - * {@link JoinSegment #getOrderedNodes()} for nodeToReplace with a subset of - * the ordered nodes for this JoinSegment. The order of the nodes for - * nodeToReplace must match the order of the nodes as a subset of - * orderedNodes - * - * @param nodeToReplace - * - nodes to be replaced by pcj - * @param pcj - * - pcj node that will replace specified query nodes - */ - @Override - public boolean replaceWithPcj(QuerySegment nodeToReplace, - ExternalTupleSet pcj) { - Preconditions.checkNotNull(nodeToReplace != null); - Preconditions.checkNotNull(pcj); - if (!containsQuerySegment(nodeToReplace)) { - return false; - } - List<QueryModelNode> nodeList = nodeToReplace.getOrderedNodes(); - int begin = orderedNodes.indexOf(nodeList.get(0)); - // TODO this assumes no duplicate nodes - if (begin < 0 - || begin + nodeList.size() > orderedNodes.size() - || !nodeList.equals(orderedNodes.subList(begin, begin - + nodeList.size()))) { - return false; - } - orderedNodes.removeAll(nodeList); - orderedNodes.add(begin, pcj); - unorderedNodes.removeAll(nodeList); - unorderedNodes.add(pcj); - for (QueryModelNode q : nodeList) { - if (q instanceof ValueExpr) { - conditionMap.remove(q); - } - } - return true; - } - - /** - * - * @param tupleExpr - * - the query object that will be traversed by this method - * @param joinArgs - * - all nodes connected by Joins, LeftJoins, and Filters - * @return - List containing all nodes connected by Joins, LeftJoins, and - * Filters. This List contains the {@link ValueExpr} in place of the - * Filter and a {@link FlattenedOptional} in place of the LeftJoin - * for ease of comparison with PCJ nodes. - */ - private List<QueryModelNode> getJoinArgs(TupleExpr tupleExpr, - List<QueryModelNode> joinArgs) { - - if (tupleExpr instanceof Join) { - if (!(((Join) tupleExpr).getLeftArg() instanceof FixedStatementPattern) - && !(((Join) tupleExpr).getRightArg() instanceof DoNotExpandSP)) { - Join join = (Join) tupleExpr; - getJoinArgs(join.getRightArg(), joinArgs); - getJoinArgs(join.getLeftArg(), joinArgs); - } - } else if (tupleExpr instanceof LeftJoin) { - LeftJoin lj = (LeftJoin) tupleExpr; - joinArgs.add(new FlattenedOptional(lj)); - getJoinArgs(lj.getLeftArg(), joinArgs); - } else if (tupleExpr instanceof Filter) { - Filter filter = (Filter) tupleExpr; - joinArgs.add(filter.getCondition()); - conditionMap.put(filter.getCondition(), filter); - getJoinArgs(filter.getArg(), joinArgs); - } else { - joinArgs.add(tupleExpr); - } - return joinArgs; - } - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/OptionalJoinSegmentPCJMatcher.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/OptionalJoinSegmentPCJMatcher.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/OptionalJoinSegmentPCJMatcher.java deleted file mode 100644 index 1141cbf..0000000 --- a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/OptionalJoinSegmentPCJMatcher.java +++ /dev/null @@ -1,142 +0,0 @@ -package org.apache.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.List; - -import org.apache.rya.indexing.external.tupleSet.ExternalTupleSet; - -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.helpers.QueryModelVisitorBase; - -/** - * This class matches PCJ queries to sub-queries of a given - * {@link OptionalJoinSegment}. A match will occur when the - * {@link QueryModelNode}s of the PCJ can be grouped together - * in the OptionalJoinSegment and ordered to match the PCJ query. - * - */ - -public class OptionalJoinSegmentPCJMatcher extends AbstractPCJMatcher { - - public OptionalJoinSegmentPCJMatcher(Join join) { - segment = new OptionalJoinSegment(join); - segmentNodeList = new ArrayList<>(segment.getOrderedNodes()); - pcjToSegment = new PCJToOptionalJoinSegment(); - } - - public OptionalJoinSegmentPCJMatcher(LeftJoin join) { - segment = new OptionalJoinSegment(join); - segmentNodeList = new ArrayList<>(segment.getOrderedNodes()); - pcjToSegment = new PCJToOptionalJoinSegment(); - } - - public OptionalJoinSegmentPCJMatcher(Filter filter) { - segment = new OptionalJoinSegment(filter); - segmentNodeList = new ArrayList<>(segment.getOrderedNodes()); - pcjToSegment = new PCJToOptionalJoinSegment(); - } - - /** - * @param pcjNodes - {@link QuerySegment} to be replaced by PCJ - * @param pcj - PCJ to replace matchin QuerySegment - */ - @Override - public boolean matchPCJ(QuerySegment pcjNodes, ExternalTupleSet pcj) { - - if(!segment.containsQuerySegment(pcjNodes)) { - return false; - } - List<QueryModelNode> consolidatedNodes = groupNodesToMatchPCJ(getOrderedNodes(), pcjNodes.getOrderedNodes()); - if(consolidatedNodes.size() == 0) { - return false; - } - - //set segment nodes to the consolidated nodes to match pcj - segment.setNodes(consolidatedNodes); - boolean nodesReplaced = segment.replaceWithPcj(pcjNodes, pcj); - - //if pcj nodes replaced queryNodes, update segmentNodeList - //otherwise restore segment nodes back to original pre-consolidated state - if(nodesReplaced) { - segmentNodeList = segment.getOrderedNodes(); - tupleAndNodesUpToDate = false; - } else { - segment.setNodes(segmentNodeList); - } - - return nodesReplaced; - } - - /** - * - * @param queryNodes - query nodes to be compared to pcj for matching - * @param pcjNodes - pcj nodes to match to query - * @return - query nodes with pcj nodes grouped together (if possible), otherwise return - * an empty list. - */ - private List<QueryModelNode> groupNodesToMatchPCJ(List<QueryModelNode> queryNodes, List<QueryModelNode> pcjNodes) { - PCJNodeConsolidator pnc = new PCJNodeConsolidator(queryNodes, pcjNodes); - boolean canConsolidate = pnc.consolidateNodes(); - if(canConsolidate) { - return pnc.getQueryNodes(); - } - return new ArrayList<QueryModelNode>(); - } - - - /** - * This class extracts the {@link OptionalJoinSegment} of PCJ query. - * - */ - static class PCJToOptionalJoinSegment extends QueryModelVisitorBase<RuntimeException> implements PCJToSegment { - - private OptionalJoinSegment segment; - - @Override - public QuerySegment getSegment(ExternalTupleSet pcj) { - segment = null; - pcj.getTupleExpr().visit(this); - return segment; - } - - @Override - public void meet(Join join) { - segment = new OptionalJoinSegment(join); - } - - @Override - public void meet(Filter filter) { - segment = new OptionalJoinSegment(filter); - } - - @Override - public void meet(LeftJoin node) { - segment = new OptionalJoinSegment(node); - } - - } - - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJExternalSetMatcherFactory.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJExternalSetMatcherFactory.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJExternalSetMatcherFactory.java new file mode 100644 index 0000000..e9bfbbe --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJExternalSetMatcherFactory.java @@ -0,0 +1,45 @@ +package org.apache.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 org.apache.rya.indexing.external.matching.AbstractExternalSetMatcherFactory; +import org.apache.rya.indexing.external.matching.ExternalSetMatcher; +import org.apache.rya.indexing.external.matching.JoinSegment; +import org.apache.rya.indexing.external.matching.JoinSegmentMatcher; +import org.apache.rya.indexing.external.matching.OptionalJoinSegment; +import org.apache.rya.indexing.external.matching.OptionalJoinSegmentMatcher; +import org.apache.rya.indexing.external.tupleSet.ExternalTupleSet; + +/** + * Factory used to build {@link ExternalSetMatcher}s for the {@link PCJOptimizer}. + * + */ +public class PCJExternalSetMatcherFactory extends AbstractExternalSetMatcherFactory<ExternalTupleSet> { + + @Override + protected ExternalSetMatcher<ExternalTupleSet> getJoinSegmentMatcher(JoinSegment<ExternalTupleSet> segment) { + return new JoinSegmentMatcher<ExternalTupleSet>(segment, new PCJToSegmentConverter()); + } + + @Override + protected ExternalSetMatcher<ExternalTupleSet> getOptionalJoinSegmentMatcher(OptionalJoinSegment<ExternalTupleSet> segment) { + return new OptionalJoinSegmentMatcher<ExternalTupleSet>(segment, new PCJToSegmentConverter()); + } + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJMatcher.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJMatcher.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJMatcher.java deleted file mode 100644 index b0e6cfb..0000000 --- a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJMatcher.java +++ /dev/null @@ -1,76 +0,0 @@ -package org.apache.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 org.apache.rya.indexing.external.tupleSet.ExternalTupleSet; - -import org.openrdf.query.algebra.Filter; -import org.openrdf.query.algebra.QueryModelNode; -import org.openrdf.query.algebra.TupleExpr; - -/** - * This interface provides a framework for matching PCJ {@link ExternalTupleSet}s - * to subsets of a given {@link QuerySegment}. - * - */ -public interface PCJMatcher { - - /** - * - * @param pcjNodes - QuerySegment representation of PCJ to be used for matching - * @param pcj - {@link ExternalTupleSet} used to replace matching PCJ nodes when match occurs - * @return - true is match and replace occurs and false otherwise - */ - public boolean matchPCJ(QuerySegment pcjNodes, ExternalTupleSet pcj); - - /** - * - * @param pcj - {@link ExternalTupleSet} used to replace matching PCJ nodes when match occurs - * @return - true is match and replace occurs and false otherwise - */ - public boolean matchPCJ(ExternalTupleSet pcj); - - /** - * @return - TupleExpr constructed from {@link QuerySegment} with matched nodes - */ - public TupleExpr getQuery(); - - /** - * - * @return - all {@link TupleExpr} that haven't been matched to a PCJ - */ - public Set<TupleExpr> getUnmatchedArgs(); - - /** - * - * @return - provided ordered view of QuerySegment nodes - */ - public List<QueryModelNode> getOrderedNodes(); - - /** - * - * @return - Set of {@link Filter}s of given QuerySegment - */ - public Set<Filter> getFilters(); - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJMatcherFactory.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJMatcherFactory.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJMatcherFactory.java deleted file mode 100644 index 99fa801..0000000 --- a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJMatcherFactory.java +++ /dev/null @@ -1,73 +0,0 @@ -package org.apache.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 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.TupleExpr; - -/** - * This class takes in a given {@link Join}, {@Filter}, or {@link LeftJoin} - * and provides the appropriate {@link PCJMatcher} to match PCJs to the - * given query. - * - */ - -public class PCJMatcherFactory { - - public static PCJMatcher getPCJMatcher(Join join) { - if (segmentContainsLeftJoins(join)) { - return new OptionalJoinSegmentPCJMatcher(join); - } else { - return new JoinSegmentPCJMatcher(join); - } - } - - public static PCJMatcher getPCJMatcher(LeftJoin join) { - return new OptionalJoinSegmentPCJMatcher(join); - } - - public static PCJMatcher getPCJMatcher(Filter filter) { - if (segmentContainsLeftJoins(filter)) { - return new OptionalJoinSegmentPCJMatcher(filter); - } else { - return new JoinSegmentPCJMatcher(filter); - } - } - - private static boolean segmentContainsLeftJoins(TupleExpr tupleExpr) { - - if (tupleExpr instanceof Projection) { - return segmentContainsLeftJoins(((Projection) tupleExpr).getArg()); - } else if (tupleExpr instanceof Join) { - Join join = (Join) tupleExpr; - return segmentContainsLeftJoins(join.getRightArg()) - || segmentContainsLeftJoins(join.getLeftArg()); - } else if (tupleExpr instanceof LeftJoin) { - return true; - } else if (tupleExpr instanceof Filter) { - return segmentContainsLeftJoins(((Filter) tupleExpr).getArg()); - } else { - return false; - } - } -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJNodeConsolidator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJNodeConsolidator.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJNodeConsolidator.java deleted file mode 100644 index 85678e4..0000000 --- a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJNodeConsolidator.java +++ /dev/null @@ -1,628 +0,0 @@ -package org.apache.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/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJOptimizer.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJOptimizer.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJOptimizer.java index da034e7..75b48b4 100644 --- a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJOptimizer.java +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJOptimizer.java @@ -1,5 +1,4 @@ package org.apache.rya.indexing.pcj.matching; - /* * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file @@ -19,54 +18,29 @@ package org.apache.rya.indexing.pcj.matching; * under the License. */ -import static java.util.Objects.requireNonNull; +import static com.google.common.base.Preconditions.checkNotNull; -import java.util.Iterator; import java.util.List; -import java.util.Map; -import java.util.Set; -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.PrecomputedJoinStorage; -import org.apache.rya.indexing.pcj.storage.accumulo.AccumuloPcjStorage; -import org.apache.rya.indexing.pcj.storage.accumulo.PcjTableNameFactory; -import org.apache.rya.indexing.pcj.storage.accumulo.PcjTables; +import org.apache.rya.indexing.accumulo.ConfigUtils; +import org.apache.rya.indexing.external.matching.AbstractExternalSetOptimizer; +import org.apache.rya.indexing.external.matching.BasicRater; +import org.apache.rya.indexing.external.matching.ExternalSetMatcher; +import org.apache.rya.indexing.external.matching.ExternalSetProvider; +import org.apache.rya.indexing.external.matching.QueryNodeListRater; +import org.apache.rya.indexing.external.matching.QuerySegment; +import org.apache.rya.indexing.external.matching.TopOfQueryFilterRelocator; +import org.apache.rya.indexing.external.tupleSet.ExternalTupleSet; 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; +import com.google.common.base.Optional;; -import org.apache.rya.accumulo.instance.AccumuloRyaInstanceDetailsRepository; -import org.apache.rya.api.RdfCloudTripleStoreConfiguration; -import org.apache.rya.api.instance.RyaDetailsRepository; -import org.apache.rya.api.instance.RyaDetailsRepository.RyaDetailsRepositoryException; -import org.apache.rya.indexing.IndexPlanValidator.IndexPlanValidator; -import org.apache.rya.indexing.IndexPlanValidator.IndexedExecutionPlanGenerator; -import org.apache.rya.indexing.IndexPlanValidator.ThreshholdPlanSelector; -import org.apache.rya.indexing.IndexPlanValidator.TupleReArranger; -import org.apache.rya.indexing.IndexPlanValidator.ValidIndexCombinationGenerator; -import org.apache.rya.indexing.accumulo.ConfigUtils; -import org.apache.rya.indexing.external.tupleSet.AccumuloIndexSet; -import org.apache.rya.indexing.external.tupleSet.ExternalTupleSet; /** * {@link QueryOptimizer} which matches {@link TupleExpr}s associated with @@ -82,49 +56,43 @@ import org.apache.rya.indexing.external.tupleSet.ExternalTupleSet; * the ExternalTupleSet in the QuerySegment. * */ -public class PCJOptimizer implements QueryOptimizer, Configurable { - private static final Logger log = Logger.getLogger(PCJOptimizer.class); - - private List<ExternalTupleSet> indexSet; +public class PCJOptimizer extends AbstractExternalSetOptimizer<ExternalTupleSet>implements Configurable { + private static final PCJExternalSetMatcherFactory factory = new PCJExternalSetMatcherFactory(); + private AccumuloIndexSetProvider provider; private Configuration conf; private boolean init = false; - public PCJOptimizer() { - } + public PCJOptimizer() {} public PCJOptimizer(final 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) { - log.error(e.getMessage(), e); - } - init = true; + setConf(conf); } + /** + * This constructor is designed to be used for testing. A more typical use + * pattern is for a user to specify Accumulo connection details in a Configuration + * file so that PCJs can be retrieved by an AccumuloIndexSetProvider. + * + * @param indices - user specified PCJs to match to query + * @param useOptimalPcj - optimize PCJ combos for matching + */ public PCJOptimizer(final List<ExternalTupleSet> indices, final boolean useOptimalPcj) { - this.indexSet = PCJOptimizerUtilities.getValidPCJs(indices); + checkNotNull(indices); conf = new Configuration(); - conf.setBoolean(ConfigUtils.USE_OPTIMAL_PCJ, useOptimalPcj); + this.useOptimal = useOptimalPcj; + provider = new AccumuloIndexSetProvider(conf, indices); + init = true; } @Override - public void setConf(final Configuration conf) { - this.conf = conf; + public final void setConf(final Configuration conf) { + checkNotNull(conf); if (!init) { try { - indexSet = PCJOptimizerUtilities.getValidPCJs(getAccIndices(conf)); - } catch (MalformedQueryException | SailException - | QueryEvaluationException | TableNotFoundException - | AccumuloException | AccumuloSecurityException - | PcjException e) { + this.conf = conf; + this.useOptimal = ConfigUtils.getUseOptimalPCJ(conf); + provider = new AccumuloIndexSetProvider(conf); + } catch (Exception e) { throw new Error(e); } init = true; @@ -140,235 +108,40 @@ public class PCJOptimizer implements QueryOptimizer, Configurable { * This method optimizes a specified query by matching subsets of it with * PCJ queries. * - * @param tupleExpr - * - the query to be optimized + * @param tupleExpr - the query to be optimized + * @param dataset - this value is ignored + * @param bindings - this value is ignored */ @Override - public void optimize(TupleExpr tupleExpr, final Dataset dataset, - final BindingSet bindings) { - - final Projection projection = PCJOptimizerUtilities.getProjection(tupleExpr); - if (projection == null) { - log.debug("TupleExpr has no Projection. Invalid TupleExpr."); - return; - } - final IndexedExecutionPlanGenerator iep = new IndexedExecutionPlanGenerator( - tupleExpr, indexSet); - final List<ExternalTupleSet> pcjs = iep.getNormalizedIndices(); + public void optimize(TupleExpr tupleExpr, final Dataset dataset, final BindingSet bindings) { + checkNotNull(tupleExpr); // first standardize query by pulling all filters to top of query if - // they exist - // using TopOfQueryFilterRelocator + // they exist using TopOfQueryFilterRelocator tupleExpr = TopOfQueryFilterRelocator.moveFiltersToTop(tupleExpr); - - if (ConfigUtils.getUseOptimalPCJ(conf) && pcjs.size() > 0) { - - // get potential relevant index combinations - final ValidIndexCombinationGenerator vic = new ValidIndexCombinationGenerator( - tupleExpr); - final 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 - final 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 - final IndexPlanValidator ipv = new IndexPlanValidator(false); - final 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 - final 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) { - final Projection bestTupProject = PCJOptimizerUtilities - .getProjection(bestTup); - projection.setArg(bestTupProject.getArg()); + try { + if (provider.size() > 0) { + super.optimize(tupleExpr, null, null); + } else { + return; } - return; - } else if (pcjs.size() > 0) { - QuerySegmentPCJMatchVisitor.matchPCJs(tupleExpr, pcjs); - } else { - return; + } catch (Exception e) { + throw new RuntimeException("Could not populate Accumulo Index Cache."); } } - /** - * 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(final TupleExpr te, - final List<ExternalTupleSet> indexSet) { - pcjs = indexSet; - te.visit(INSTANCE); - } - - @Override - public void meet(final Join node) { - final PCJMatcher matcher = PCJMatcherFactory.getPCJMatcher(node); - for (final ExternalTupleSet pcj : pcjs) { - matcher.matchPCJ(pcj); - } - - node.replaceWith(matcher.getQuery()); - final Set<TupleExpr> unmatched = matcher.getUnmatchedArgs(); - PCJOptimizerUtilities.relocateFilters(matcher.getFilters()); - - for (final TupleExpr tupleExpr : unmatched) { - tupleExpr.visit(this); - } - } - - @Override - public void meet(final LeftJoin node) { - final PCJMatcher matcher = PCJMatcherFactory.getPCJMatcher(node); - for (final ExternalTupleSet pcj : pcjs) { - matcher.matchPCJ(pcj); - } - - node.replaceWith(matcher.getQuery()); - final Set<TupleExpr> unmatched = matcher.getUnmatchedArgs(); - PCJOptimizerUtilities.relocateFilters(matcher.getFilters()); - - for (final TupleExpr tupleExpr : unmatched) { - tupleExpr.visit(this); - } - } - - @Override - public void meet(final Filter node) { - final PCJMatcher matcher = PCJMatcherFactory.getPCJMatcher(node); - for (final ExternalTupleSet pcj : pcjs) { - matcher.matchPCJ(pcj); - } - - node.replaceWith(matcher.getQuery()); - final Set<TupleExpr> unmatched = matcher.getUnmatchedArgs(); - PCJOptimizerUtilities.relocateFilters(matcher.getFilters()); - - for (final TupleExpr tupleExpr : unmatched) { - tupleExpr.visit(this); - } - } + @Override + protected ExternalSetMatcher<ExternalTupleSet> getMatcher(QuerySegment<ExternalTupleSet> segment) { + return factory.getMatcher(segment); } - /** - * - * - * @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(final Configuration conf) - throws MalformedQueryException, SailException, - QueryEvaluationException, TableNotFoundException, - AccumuloException, AccumuloSecurityException, PcjException { - - requireNonNull(conf); - final String tablePrefix = requireNonNull(conf.get(RdfCloudTripleStoreConfiguration.CONF_TBL_PREFIX)); - final Connector conn = requireNonNull(ConfigUtils.getConnector(conf)); - List<String> tables = null; - - if (conf instanceof RdfCloudTripleStoreConfiguration) { - tables = ((RdfCloudTripleStoreConfiguration) conf).getPcjTables(); - } - // this maps associates pcj table name with pcj sparql query - final Map<String, String> indexTables = Maps.newLinkedHashMap(); - final PrecomputedJoinStorage storage = new AccumuloPcjStorage(conn, tablePrefix); - final PcjTableNameFactory pcjFactory = new PcjTableNameFactory(); - - final boolean tablesProvided = tables != null && !tables.isEmpty(); - - if (tablesProvided) { - //if tables provided, associate table name with sparql - for (final String table : tables) { - indexTables.put(table, storage.getPcjMetadata(pcjFactory.getPcjId(table)).getSparql()); - } - } else if(hasRyaDetails(tablePrefix, conn)) { - // If this is a newer install of Rya, and it has PCJ Details, then use those. - final List<String> ids = storage.listPcjs(); - for(final String id: ids) { - indexTables.put(pcjFactory.makeTableName(tablePrefix, id), storage.getPcjMetadata(id).getSparql()); - } - } else { - // Otherwise figure it out by scanning tables. - final PcjTables pcjTables = new PcjTables(); - for(final String table : conn.tableOperations().list()) { - if(table.startsWith(tablePrefix + "INDEX")) { - indexTables.put(table, pcjTables.getPcjMetadata(conn, table).getSparql()); - } - } - } - - //use table name sparql map (indexTables) to create {@link AccumuloIndexSet} - final List<ExternalTupleSet> index = Lists.newArrayList(); - if (indexTables.isEmpty()) { - log.info("No Index found"); - } else { - for (final String table : indexTables.keySet()) { - final String indexSparqlString = indexTables.get(table); - index.add(new AccumuloIndexSet(indexSparqlString, conf, table)); - } - } - return index; + @Override + protected ExternalSetProvider<ExternalTupleSet> getProvider() { + return provider; } - private static boolean hasRyaDetails(final String ryaInstanceName, final Connector conn) { - final RyaDetailsRepository detailsRepo = new AccumuloRyaInstanceDetailsRepository(conn, ryaInstanceName); - try { - detailsRepo.getRyaInstanceDetails(); - return true; - } catch(final RyaDetailsRepositoryException e) { - return false; - } + @Override + protected Optional<QueryNodeListRater> getNodeListRater(QuerySegment<ExternalTupleSet> segment) { + return Optional.of(new BasicRater(segment.getOrderedNodes())); } } http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJOptimizerUtilities.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJOptimizerUtilities.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJOptimizerUtilities.java index 19b608f..909d932 100644 --- a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJOptimizerUtilities.java +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJOptimizerUtilities.java @@ -24,6 +24,7 @@ import java.util.Iterator; import java.util.List; import java.util.Set; +import org.apache.rya.indexing.external.matching.QuerySegment; import org.apache.rya.indexing.external.tupleSet.ExternalTupleSet; import org.apache.rya.indexing.pcj.matching.QueryVariableNormalizer.VarCollector; @@ -345,9 +346,9 @@ public class PCJOptimizerUtilities { - public static boolean pcjContainsLeftJoins(ExternalTupleSet pcj) { + public static boolean tupleContainsLeftJoins(TupleExpr node) { LeftJoinVisitor lj = new LeftJoinVisitor(); - pcj.getTupleExpr().visit(lj); + node.visit(lj); return lj.containsLeftJoin; } http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJToSegmentConverter.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJToSegmentConverter.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJToSegmentConverter.java new file mode 100644 index 0000000..61d6204 --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/PCJToSegmentConverter.java @@ -0,0 +1,117 @@ +package org.apache.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 org.apache.rya.indexing.external.matching.ExternalSetConverter; +import org.apache.rya.indexing.external.matching.JoinSegment; +import org.apache.rya.indexing.external.matching.OptionalJoinSegment; +import org.apache.rya.indexing.external.matching.QuerySegment; +import org.apache.rya.indexing.external.tupleSet.ExternalTupleSet; +import org.openrdf.query.algebra.Filter; +import org.openrdf.query.algebra.Join; +import org.openrdf.query.algebra.LeftJoin; +import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; + +import com.google.common.base.Preconditions; + +/** + * Implementation of {@link ExternalSetConverter} to convert {@link ExternalTupleSet}s + * to {@link QuerySegment}s. + * + */ +public class PCJToSegmentConverter implements ExternalSetConverter<ExternalTupleSet> { + + private static final PCJToOptionalJoinSegment optional = new PCJToOptionalJoinSegment(); + private static final PCJToJoinSegment join = new PCJToJoinSegment(); + + + @Override + public QuerySegment<ExternalTupleSet> setToSegment(ExternalTupleSet set) { + Preconditions.checkNotNull(set); + if (PCJOptimizerUtilities.tupleContainsLeftJoins(set.getTupleExpr())) { + return optional.getSegment(set); + } else { + return join.getSegment(set); + } + } + + /** + * This class extracts the {@link JoinSegment} from the {@link TupleExpr} of + * specified PCJ. + * + */ + static class PCJToJoinSegment extends QueryModelVisitorBase<RuntimeException> { + + private JoinSegment<ExternalTupleSet> segment; + + private PCJToJoinSegment(){}; + + public QuerySegment<ExternalTupleSet> getSegment(ExternalTupleSet pcj) { + segment = null; + pcj.getTupleExpr().visit(this); + return segment; + } + + @Override + public void meet(final Join join) { + segment = new JoinSegment<ExternalTupleSet>(join); + } + + @Override + public void meet(final Filter filter) { + segment = new JoinSegment<ExternalTupleSet>(filter); + } + + } + + /** + * This class extracts the {@link OptionalJoinSegment} of PCJ query. + * + */ + static class PCJToOptionalJoinSegment extends QueryModelVisitorBase<RuntimeException> { + + private OptionalJoinSegment<ExternalTupleSet> segment; + + private PCJToOptionalJoinSegment(){}; + + public QuerySegment<ExternalTupleSet> getSegment(ExternalTupleSet pcj) { + segment = null; + pcj.getTupleExpr().visit(this); + return segment; + } + + @Override + public void meet(final Join join) { + segment = new OptionalJoinSegment<ExternalTupleSet>(join); + } + + @Override + public void meet(final Filter filter) { + segment = new OptionalJoinSegment<ExternalTupleSet>(filter); + } + + @Override + public void meet(final LeftJoin node) { + segment = new OptionalJoinSegment<ExternalTupleSet>(node); + } + + } + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/QueryNodesToTupleExpr.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/QueryNodesToTupleExpr.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/QueryNodesToTupleExpr.java deleted file mode 100644 index b316095..0000000 --- a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/QueryNodesToTupleExpr.java +++ /dev/null @@ -1,194 +0,0 @@ -package org.apache.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/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/QuerySegment.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/QuerySegment.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/QuerySegment.java deleted file mode 100644 index 0b74fa3..0000000 --- a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/QuerySegment.java +++ /dev/null @@ -1,83 +0,0 @@ -package org.apache.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 org.apache.rya.indexing.external.tupleSet.ExternalTupleSet; -import org.apache.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(); - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/TopOfQueryFilterRelocator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/TopOfQueryFilterRelocator.java b/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/TopOfQueryFilterRelocator.java deleted file mode 100644 index ba6a6d3..0000000 --- a/extras/indexing/src/main/java/org/apache/rya/indexing/pcj/matching/TopOfQueryFilterRelocator.java +++ /dev/null @@ -1,97 +0,0 @@ -package org.apache.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.Projection; -import org.openrdf.query.algebra.TupleExpr; -import org.openrdf.query.algebra.ValueExpr; -import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; - -/** - * Class consisting of a single utility method for relocating filters. - * - */ -public class TopOfQueryFilterRelocator { - - - /** - * - * This method moves the Filters of a specified {@link TupleExpr} - * to the top of the TupleExpr. - * - * @param query - query whose filters will be relocated - * @return - TupleExpr with filters relocated to top - */ - public static TupleExpr moveFiltersToTop(TupleExpr query) { - - ProjectionAndFilterGatherer fg = new ProjectionAndFilterGatherer(); - query.visit(fg); - List<ValueExpr> filterCond = new ArrayList<>(fg.filterCond); - Projection projection = fg.projection; - - if(filterCond.size() == 0) { - return query; - } - - Filter first = new Filter(); - first.setCondition(filterCond.remove(0)); - Filter current = first; - for(ValueExpr cond: filterCond) { - Filter filter = new Filter(null, cond); - current.setArg(filter); - current = filter; - } - - TupleExpr te = projection.getArg(); - projection.setArg(first); - current.setArg(te); - - return query; - - } - - - static class ProjectionAndFilterGatherer extends QueryModelVisitorBase<RuntimeException> { - - Set<ValueExpr> filterCond = new HashSet<>(); - Projection projection; - - - @Override - public void meet(Projection node) { - this.projection = node; - node.getArg().visit(this); - } - - @Override - public void meet(Filter node) { - filterCond.add(node.getCondition()); - node.replaceWith(node.getArg()); - } - - } - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/11349b11/extras/indexing/src/main/java/org/apache/rya/indexing/statement/metadata/matching/MetadataNodeToSegmentConverter.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/org/apache/rya/indexing/statement/metadata/matching/MetadataNodeToSegmentConverter.java b/extras/indexing/src/main/java/org/apache/rya/indexing/statement/metadata/matching/MetadataNodeToSegmentConverter.java new file mode 100644 index 0000000..82d45c9 --- /dev/null +++ b/extras/indexing/src/main/java/org/apache/rya/indexing/statement/metadata/matching/MetadataNodeToSegmentConverter.java @@ -0,0 +1,44 @@ +package org.apache.rya.indexing.statement.metadata.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.HashMap; +import java.util.List; +import java.util.Set; + +import org.apache.rya.indexing.external.matching.ExternalSetConverter; +import org.apache.rya.indexing.external.matching.JoinSegment; +import org.apache.rya.indexing.external.matching.QuerySegment; +import org.openrdf.query.algebra.Filter; +import org.openrdf.query.algebra.QueryModelNode; +import org.openrdf.query.algebra.ValueExpr; + +import com.beust.jcommander.internal.Lists; +import com.google.common.collect.Sets; + +public class MetadataNodeToSegmentConverter implements ExternalSetConverter<StatementMetadataNode<?>> { + + @Override + public QuerySegment<StatementMetadataNode<?>> setToSegment(StatementMetadataNode<?> set) { + Set<QueryModelNode> patterns = Sets.newHashSet(set.getReifiedStatementPatterns()); + List<QueryModelNode> patternList = Lists.newArrayList(patterns); + return new JoinSegment<StatementMetadataNode<?>>(patterns, patternList, new HashMap<ValueExpr, Filter>()); + + } + +}
