http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/mvm/rya/indexing/FilterFunctionOptimizer.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/FilterFunctionOptimizer.java b/extras/indexing/src/main/java/mvm/rya/indexing/FilterFunctionOptimizer.java deleted file mode 100644 index d148b74..0000000 --- a/extras/indexing/src/main/java/mvm/rya/indexing/FilterFunctionOptimizer.java +++ /dev/null @@ -1,339 +0,0 @@ -package mvm.rya.indexing; - -/* - * 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.io.IOException; -import java.net.UnknownHostException; -import java.util.ArrayList; -import java.util.Collection; -import java.util.List; - -import org.apache.accumulo.core.client.AccumuloException; -import org.apache.accumulo.core.client.AccumuloSecurityException; -import org.apache.accumulo.core.client.TableExistsException; -import org.apache.accumulo.core.client.TableNotFoundException; -import org.apache.commons.lang.Validate; -import org.apache.hadoop.conf.Configurable; -import org.apache.hadoop.conf.Configuration; -import org.apache.log4j.Logger; -import org.openrdf.model.Resource; -import org.openrdf.model.URI; -import org.openrdf.model.Value; -import org.openrdf.model.ValueFactory; -import org.openrdf.model.impl.URIImpl; -import org.openrdf.model.impl.ValueFactoryImpl; -import org.openrdf.query.BindingSet; -import org.openrdf.query.Dataset; -import org.openrdf.query.algebra.And; -import org.openrdf.query.algebra.Filter; -import org.openrdf.query.algebra.FunctionCall; -import org.openrdf.query.algebra.Join; -import org.openrdf.query.algebra.LeftJoin; -import org.openrdf.query.algebra.QueryModelNode; -import org.openrdf.query.algebra.StatementPattern; -import org.openrdf.query.algebra.TupleExpr; -import org.openrdf.query.algebra.ValueConstant; -import org.openrdf.query.algebra.ValueExpr; -import org.openrdf.query.algebra.Var; -import org.openrdf.query.algebra.evaluation.QueryOptimizer; -import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; - -import com.google.common.collect.Lists; - -import mvm.rya.accumulo.AccumuloRdfConfiguration; -import mvm.rya.indexing.IndexingFunctionRegistry.FUNCTION_TYPE; -import mvm.rya.indexing.accumulo.ConfigUtils; -import mvm.rya.indexing.accumulo.freetext.AccumuloFreeTextIndexer; -import mvm.rya.indexing.accumulo.freetext.FreeTextTupleSet; -import mvm.rya.indexing.accumulo.temporal.AccumuloTemporalIndexer; -import mvm.rya.indexing.mongodb.freetext.MongoFreeTextIndexer; -import mvm.rya.indexing.mongodb.temporal.MongoTemporalIndexer; - -public class FilterFunctionOptimizer implements QueryOptimizer, Configurable { - private static final Logger LOG = Logger.getLogger(FilterFunctionOptimizer.class); - private final ValueFactory valueFactory = new ValueFactoryImpl(); - - private Configuration conf; - private FreeTextIndexer freeTextIndexer; - private TemporalIndexer temporalIndexer; - private boolean init = false; - - public FilterFunctionOptimizer() { - } - - public FilterFunctionOptimizer(final AccumuloRdfConfiguration conf) throws AccumuloException, AccumuloSecurityException, - TableNotFoundException, IOException, TableExistsException, NumberFormatException, UnknownHostException { - this.conf = conf; - init(); - } - - //setConf initializes FilterFunctionOptimizer so reflection can be used - //to create optimizer in RdfCloudTripleStoreConnection - @Override - public void setConf(final Configuration conf) { - this.conf = conf; - //reset the init. - init = false; - init(); - } - - private synchronized void init() { - if (!init) { - if (ConfigUtils.getUseMongo(conf)) { - freeTextIndexer = new MongoFreeTextIndexer(); - freeTextIndexer.setConf(conf); - temporalIndexer = new MongoTemporalIndexer(); - temporalIndexer.setConf(conf); - } else { - freeTextIndexer = new AccumuloFreeTextIndexer(); - freeTextIndexer.setConf(conf); - temporalIndexer = new AccumuloTemporalIndexer(); - temporalIndexer.setConf(conf); - } - init = true; - } - } - - @Override - public void optimize(final TupleExpr tupleExpr, final Dataset dataset, final BindingSet bindings) { - // find variables used in property and resource based searches: - final SearchVarVisitor searchVars = new SearchVarVisitor(); - tupleExpr.visit(searchVars); - // rewrites for property searches: - processPropertySearches(tupleExpr, searchVars.searchProperties); - - } - - - - private void processPropertySearches(final TupleExpr tupleExpr, final Collection<Var> searchProperties) { - final MatchStatementVisitor matchStatements = new MatchStatementVisitor(searchProperties); - tupleExpr.visit(matchStatements); - for (final StatementPattern matchStatement: matchStatements.matchStatements) { - final Var subject = matchStatement.getSubjectVar(); - if (subject.hasValue() && !(subject.getValue() instanceof Resource)) { - throw new IllegalArgumentException("Query error: Found " + subject.getValue() + ", expected an URI or BNode"); - } - Validate.isTrue(subject.hasValue() || subject.getName() != null); - Validate.isTrue(!matchStatement.getObjectVar().hasValue() && matchStatement.getObjectVar().getName() != null); - buildQuery(tupleExpr, matchStatement); - } - } - - private void buildQuery(final TupleExpr tupleExpr, final StatementPattern matchStatement) { - //If our IndexerExpr (to be) is the rhs-child of LeftJoin, we can safely make that a Join: - // the IndexerExpr will (currently) not return results that can deliver unbound variables. - //This optimization should probably be generalized into a LeftJoin -> Join optimizer under certain conditions. Until that - // has been done, this code path at least takes care of queries generated by OpenSahara SparqTool that filter on OPTIONAL - // projections. E.g. summary~'full text search' (summary is optional). See #379 - if (matchStatement.getParentNode() instanceof LeftJoin) { - final LeftJoin leftJoin = (LeftJoin)matchStatement.getParentNode(); - if (leftJoin.getRightArg() == matchStatement && leftJoin.getCondition() == null) { - matchStatement.getParentNode().replaceWith(new Join(leftJoin.getLeftArg(), leftJoin.getRightArg())); - } - } - final FilterFunction fVisitor = new FilterFunction(matchStatement.getObjectVar().getName()); - tupleExpr.visit(fVisitor); - final List<IndexingExpr> results = Lists.newArrayList(); - for(int i = 0; i < fVisitor.func.size(); i++){ - results.add(new IndexingExpr(fVisitor.func.get(i), matchStatement, fVisitor.args.get(i))); - } - removeMatchedPattern(tupleExpr, matchStatement, new IndexerExprReplacer(results)); - } - - //find vars contained in filters - private static class SearchVarVisitor extends QueryModelVisitorBase<RuntimeException> { - private final Collection<Var> searchProperties = new ArrayList<Var>(); - - @Override - public void meet(final FunctionCall fn) { - final URI fun = new URIImpl(fn.getURI()); - final Var result = IndexingFunctionRegistry.getResultVarFromFunctionCall(fun, fn.getArgs()); - if (result != null && !searchProperties.contains(result)) { - searchProperties.add(result); - } - } - } - - //find StatementPatterns containing filter variables - private static class MatchStatementVisitor extends QueryModelVisitorBase<RuntimeException> { - private final Collection<Var> propertyVars; - private final Collection<Var> usedVars = new ArrayList<Var>(); - private final List<StatementPattern> matchStatements = new ArrayList<StatementPattern>(); - - public MatchStatementVisitor(final Collection<Var> propertyVars) { - this.propertyVars = propertyVars; - } - - @Override public void meet(final StatementPattern statement) { - final Var object = statement.getObjectVar(); - if (propertyVars.contains(object)) { - if (usedVars.contains(object)) { - throw new IllegalArgumentException("Illegal search, variable is used multiple times as object: " + object.getName()); - } else { - usedVars.add(object); - matchStatements.add(statement); - } - } - } - } - - private abstract class AbstractEnhanceVisitor extends QueryModelVisitorBase<RuntimeException> { - final String matchVar; - List<URI> func = Lists.newArrayList(); - List<Value[]> args = Lists.newArrayList(); - - public AbstractEnhanceVisitor(final String matchVar) { - this.matchVar = matchVar; - } - - protected void addFilter(final URI uri, final Value[] values) { - func.add(uri); - args.add(values); - } - } - - //create indexing expression for each filter matching var in filter StatementPattern - //replace old filter condition with true condition - private class FilterFunction extends AbstractEnhanceVisitor { - public FilterFunction(final String matchVar) { - super(matchVar); - } - - @Override - public void meet(final FunctionCall call) { - final URI fnUri = valueFactory.createURI(call.getURI()); - final Var resultVar = IndexingFunctionRegistry.getResultVarFromFunctionCall(fnUri, call.getArgs()); - if (resultVar != null && resultVar.getName().equals(matchVar)) { - addFilter(valueFactory.createURI(call.getURI()), extractArguments(matchVar, call)); - if (call.getParentNode() instanceof Filter || call.getParentNode() instanceof And || call.getParentNode() instanceof LeftJoin) { - call.replaceWith(new ValueConstant(valueFactory.createLiteral(true))); - } else { - throw new IllegalArgumentException("Query error: Found " + call + " as part of an expression that is too complex"); - } - } - } - - private Value[] extractArguments(final String matchName, final FunctionCall call) { - final Value args[] = new Value[call.getArgs().size() - 1]; - int argI = 0; - for (int i = 0; i != call.getArgs().size(); ++i) { - final ValueExpr arg = call.getArgs().get(i); - if (argI == i && arg instanceof Var && matchName.equals(((Var)arg).getName())) { - continue; - } - if (arg instanceof ValueConstant) { - args[argI] = ((ValueConstant)arg).getValue(); - } else if (arg instanceof Var && ((Var)arg).hasValue()) { - args[argI] = ((Var)arg).getValue(); - } else { - throw new IllegalArgumentException("Query error: Found " + arg + ", expected a Literal, BNode or URI"); - } - ++argI; - } - return args; - } - - @Override - public void meet(final Filter filter) { - //First visit children, then condition (reverse of default): - filter.getArg().visit(this); - filter.getCondition().visit(this); - } - } - - private void removeMatchedPattern(final TupleExpr tupleExpr, final StatementPattern pattern, final TupleExprReplacer replacer) { - final List<TupleExpr> indexTuples = replacer.createReplacement(pattern); - if (indexTuples.size() > 1) { - final VarExchangeVisitor vev = new VarExchangeVisitor(pattern); - tupleExpr.visit(vev); - Join join = new Join(indexTuples.remove(0), indexTuples.remove(0)); - for (final TupleExpr geo : indexTuples) { - join = new Join(join, geo); - } - pattern.replaceWith(join); - } else if (indexTuples.size() == 1) { - pattern.replaceWith(indexTuples.get(0)); - pattern.setParentNode(null); - } else { - throw new IllegalStateException("Must have at least one replacement for matched StatementPattern."); - } - } - - private interface TupleExprReplacer { - List<TupleExpr> createReplacement(TupleExpr org); - } - - //replace each filter pertinent StatementPattern with corresponding index expr - private class IndexerExprReplacer implements TupleExprReplacer { - private final List<IndexingExpr> indxExpr; - private final FUNCTION_TYPE type; - - public IndexerExprReplacer(final List<IndexingExpr> indxExpr) { - this.indxExpr = indxExpr; - final URI func = indxExpr.get(0).getFunction(); - type = IndexingFunctionRegistry.getFunctionType(func); - } - - @Override - public List<TupleExpr> createReplacement(final TupleExpr org) { - final List<TupleExpr> indexTuples = Lists.newArrayList(); - switch (type) { - case FREETEXT: - for (final IndexingExpr indx : indxExpr) { - indexTuples.add(new FreeTextTupleSet(indx, freeTextIndexer)); - } - break; - case TEMPORAL: - for (final IndexingExpr indx : indxExpr) { - indexTuples.add(new TemporalTupleSet(indx, temporalIndexer)); - } - break; - default: - throw new IllegalArgumentException("Incorrect type!"); - } - return indexTuples; - } - } - - private static class VarExchangeVisitor extends QueryModelVisitorBase<RuntimeException> { - private final StatementPattern exchangeVar; - public VarExchangeVisitor(final StatementPattern sp) { - exchangeVar = sp; - } - - @Override - public void meet(final Join node) { - final QueryModelNode lNode = node.getLeftArg(); - if (lNode instanceof StatementPattern) { - exchangeVar.replaceWith(lNode); - node.setLeftArg(exchangeVar); - } else { - super.meet(node); - } - } - } - - @Override - public Configuration getConf() { - return conf; - } -}
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/mvm/rya/indexing/FreeTextIndexer.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/FreeTextIndexer.java b/extras/indexing/src/main/java/mvm/rya/indexing/FreeTextIndexer.java deleted file mode 100644 index f6fb2c7..0000000 --- a/extras/indexing/src/main/java/mvm/rya/indexing/FreeTextIndexer.java +++ /dev/null @@ -1,48 +0,0 @@ -package mvm.rya.indexing; - -import java.io.IOException; - -import org.openrdf.model.Statement; -import org.openrdf.query.QueryEvaluationException; - -/* - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - - - -import info.aduna.iteration.CloseableIteration; -import mvm.rya.api.persist.index.RyaSecondaryIndexer; - -/** - * A repository to store, index, and retrieve {@link Statement}s based on freetext features. - */ -public interface FreeTextIndexer extends RyaSecondaryIndexer { - - /** - * Query the Free Text Index with specific constraints. A <code>null</code> or empty parameters imply no constraint. - * - * @param query - * the query to perform - * @param contraints - * the constraints on the statements returned - * @return the set of statements that meet the query and other constraints. - * @throws IOException - */ - public abstract CloseableIteration<Statement, QueryEvaluationException> queryText(String query, StatementConstraints contraints) throws IOException; -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/mvm/rya/indexing/GeoConstants.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/GeoConstants.java b/extras/indexing/src/main/java/mvm/rya/indexing/GeoConstants.java deleted file mode 100644 index a692edd..0000000 --- a/extras/indexing/src/main/java/mvm/rya/indexing/GeoConstants.java +++ /dev/null @@ -1,46 +0,0 @@ -package mvm.rya.indexing; - -/* - * 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.model.URI; -import org.openrdf.model.impl.URIImpl; - -/** - * A set of URIs used in GeoSPARQL - */ -public class GeoConstants { - public static final String NS_GEO = "http://www.opengis.net/ont/geosparql#"; - public static final String NS_GEOF = "http://www.opengis.net/def/function/geosparql/"; - - public static final URI XMLSCHEMA_OGC_WKT = new URIImpl(NS_GEO + "wktLiteral"); - public static final URI GEO_AS_WKT = new URIImpl(NS_GEO + "asWKT"); - - public static final URI XMLSCHEMA_OGC_GML = new URIImpl(NS_GEO + "gmlLiteral"); - public static final URI GEO_AS_GML = new URIImpl(NS_GEO + "asGML"); - - public static final URI GEO_SF_EQUALS = new URIImpl(NS_GEOF + "sfEquals"); - public static final URI GEO_SF_DISJOINT = new URIImpl(NS_GEOF + "sfDisjoint"); - public static final URI GEO_SF_INTERSECTS = new URIImpl(NS_GEOF + "sfIntersects"); - public static final URI GEO_SF_TOUCHES = new URIImpl(NS_GEOF + "sfTouches"); - public static final URI GEO_SF_CROSSES = new URIImpl(NS_GEOF + "sfCrosses"); - public static final URI GEO_SF_WITHIN = new URIImpl(NS_GEOF + "sfWithin"); - public static final URI GEO_SF_CONTAINS = new URIImpl(NS_GEOF + "sfContains"); - public static final URI GEO_SF_OVERLAPS = new URIImpl(NS_GEOF + "sfOverlaps"); -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/ExternalIndexMatcher.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/ExternalIndexMatcher.java b/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/ExternalIndexMatcher.java deleted file mode 100644 index ee3d444..0000000 --- a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/ExternalIndexMatcher.java +++ /dev/null @@ -1,34 +0,0 @@ -package mvm.rya.indexing.IndexPlanValidator; - -/* - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - - -import java.util.Iterator; - -import org.openrdf.query.algebra.TupleExpr; - -public interface ExternalIndexMatcher { - - - public Iterator<TupleExpr> getIndexedTuples(); - - - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/GeneralizedExternalProcessor.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/GeneralizedExternalProcessor.java b/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/GeneralizedExternalProcessor.java deleted file mode 100644 index 08d52ed..0000000 --- a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/GeneralizedExternalProcessor.java +++ /dev/null @@ -1,726 +0,0 @@ -package mvm.rya.indexing.IndexPlanValidator; - -/* - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - - - - - -import java.util.Collection; -import java.util.HashSet; -import java.util.List; -import java.util.Set; - -import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; -import mvm.rya.indexing.pcj.matching.QueryVariableNormalizer.VarCollector; - -import org.openrdf.query.algebra.BindingSetAssignment; -import org.openrdf.query.algebra.Filter; -import org.openrdf.query.algebra.Join; -import org.openrdf.query.algebra.Projection; -import org.openrdf.query.algebra.QueryModelNode; -import org.openrdf.query.algebra.StatementPattern; -import org.openrdf.query.algebra.TupleExpr; -import org.openrdf.query.algebra.Var; -import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; -import org.openrdf.query.algebra.helpers.StatementPatternCollector; - -import com.google.common.collect.Lists; -import com.google.common.collect.Sets; - -/** - * Processes a {@link TupleExpr} and replaces sets of elements in the tree with {@link ExternalTupleSet} objects. - */ -public class GeneralizedExternalProcessor { - - - /** - * Iterates through list of normalized indexes and replaces all subtrees of query which match index with index. - * - * @param query - * @return TupleExpr - */ - public static TupleExpr process(TupleExpr query, List<ExternalTupleSet> indexSet) { - - boolean indexPlaced = false; - TupleExpr rtn = query.clone(); - QueryNodeCount qnc = new QueryNodeCount(); - rtn.visit(qnc); - - if(qnc.getNodeCount()/2 < indexSet.size()) { - return null; - } - - - //move BindingSetAssignment Nodes out of the way - organizeBSAs(rtn); - - - // test to see if query contains no other nodes - // than filter, join, projection, and statement pattern and - // test whether query contains duplicate StatementPatterns and filters - if (isTupleValid(rtn)) { - - for (ExternalTupleSet index : indexSet) { - - // test to see if index contains at least one StatementPattern, - // that StatementPatterns are unique, - // and that all variables found in filters occur in some - // StatementPattern - if (isTupleValid(index.getTupleExpr())) { - - ExternalTupleSet eTup = (ExternalTupleSet) index.clone(); - SPBubbleDownVisitor indexVistor = new SPBubbleDownVisitor(eTup); - rtn.visit(indexVistor); - FilterBubbleManager fbmv = new FilterBubbleManager(eTup); - rtn.visit(fbmv); - SubsetEqualsVisitor subIndexVis = new SubsetEqualsVisitor(eTup, rtn); - rtn.visit(subIndexVis); - indexPlaced = subIndexVis.indexPlaced(); - if(!indexPlaced) { - break; - } - - } - - } - if(indexPlaced) { - return rtn; - } else { - return null; - } - - } else { - throw new IllegalArgumentException("Invalid Query."); - } - } - - - - - - // determines whether query is valid, which requires that a - // query must contain a StatementPattern, not contain duplicate - // Statement Patterns or Filters, not be comprised of only Projection, - // Join, StatementPattern, and Filter nodes, and that any variable - // appearing in a Filter must appear in a StatementPattern. - private static boolean isTupleValid(QueryModelNode node) { - - ValidQueryVisitor vqv = new ValidQueryVisitor(); - node.visit(vqv); - - Set<String> spVars = getVarNames(getQNodes("sp", node)); - - if (vqv.isValid() && spVars.size() > 0) { - - FilterCollector fvis = new FilterCollector(); - node.visit(fvis); - List<QueryModelNode> fList = fvis.getFilters(); - return fList.size() == Sets.newHashSet(fList).size() && getVarNames(fList).size() <= spVars.size(); - - } else { - return false; - } - } - - private static Set<QueryModelNode> getQNodes(QueryModelNode queryNode) { - Set<QueryModelNode> rtns = new HashSet<QueryModelNode>(); - - StatementPatternCollector spc = new StatementPatternCollector(); - queryNode.visit(spc); - rtns.addAll(spc.getStatementPatterns()); - - FilterCollector fvis = new FilterCollector(); - queryNode.visit(fvis); - rtns.addAll(fvis.getFilters()); - - ExternalTupleCollector eVis = new ExternalTupleCollector(); - queryNode.visit(eVis); - rtns.addAll(eVis.getExtTup()); - - return rtns; - } - - private static Set<QueryModelNode> getQNodes(String node, QueryModelNode queryNode) { - - if (node.equals("sp")) { - Set<QueryModelNode> eSet = new HashSet<QueryModelNode>(); - StatementPatternCollector spc = new StatementPatternCollector(); - queryNode.visit(spc); - List<StatementPattern> spList = spc.getStatementPatterns(); - eSet.addAll(spList); - // returns empty set if list contains duplicate StatementPatterns - if (spList.size() > eSet.size()) { - return Sets.newHashSet(); - } else { - return eSet; - } - } else if (node.equals("filter")) { - - FilterCollector fvis = new FilterCollector(); - queryNode.visit(fvis); - - return Sets.newHashSet(fvis.getFilters()); - } else { - - throw new IllegalArgumentException("Invalid node type."); - } - } - - // moves StatementPatterns in query that also occur in index to bottom of - // query tree. - private static class SPBubbleDownVisitor extends QueryModelVisitorBase<RuntimeException> { - - private TupleExpr tuple; - private QueryModelNode indexQNode; - private Set<QueryModelNode> sSet = Sets.newHashSet(); - - public SPBubbleDownVisitor(ExternalTupleSet index) { - - this.tuple = index.getTupleExpr(); - indexQNode = ((Projection) tuple).getArg(); - sSet = getQNodes("sp", indexQNode); - - } - - @Override - public void meet(Projection node) { - // moves external tuples above statement patterns before attempting - // to bubble down index statement patterns found in query tree - - organizeExtTuples(node); - super.meet(node); - } - - @Override - public void meet(Join node) { - // if right node contained in index, move it to bottom of query tree - if (sSet.contains(node.getRightArg())) { - - Set<QueryModelNode> eSet = getQNodes("sp", node); - Set<QueryModelNode> compSet = Sets.difference(eSet, sSet); - - if (eSet.containsAll(sSet)) { - QNodeExchanger qne = new QNodeExchanger(node.getRightArg(), compSet); - node.visit(qne); - node.replaceChildNode(node.getRightArg(), qne.getReplaced()); - - super.meet(node); - } - return; - } - // if left node contained in index, move it to bottom of query tree - else if (sSet.contains(node.getLeftArg())) { - - Set<QueryModelNode> eSet = getQNodes("sp", node); - Set<QueryModelNode> compSet = Sets.difference(eSet, sSet); - - if (eSet.containsAll(sSet)) { - - QNodeExchanger qne = new QNodeExchanger(node.getLeftArg(), compSet); - node.visit(qne); - node.replaceChildNode(node.getLeftArg(), qne.getReplaced()); - - super.meet(node); - } - return; - - } else { - super.meet(node); - } - - } - - // moves all ExternalTupleSets in query tree above remaining - // StatementPatterns - private static void organizeExtTuples(QueryModelNode node) { - - ExternalTupleCollector eVis = new ExternalTupleCollector(); - node.visit(eVis); - - ExtTupleExchangeVisitor oev = new ExtTupleExchangeVisitor(eVis.getExtTup()); - node.visit(oev); - } - - } - - // given a replacement QueryModelNode and compSet, this visitor replaces the - // first - // element in the query tree that occurs in compSet with replacement and - // returns - // the element that was replaced. - private static class QNodeExchanger extends QueryModelVisitorBase<RuntimeException> { - - private QueryModelNode toBeReplaced; - private QueryModelNode replacement; - private Set<QueryModelNode> compSet; - - public QNodeExchanger(QueryModelNode replacement, Set<QueryModelNode> compSet) { - this.replacement = replacement; - this.toBeReplaced = replacement; - this.compSet = compSet; - } - - public QueryModelNode getReplaced() { - return toBeReplaced; - } - - @Override - public void meet(Join node) { - - if (compSet.contains(node.getRightArg())) { - this.toBeReplaced = node.getRightArg(); - node.replaceChildNode(node.getRightArg(), replacement); - return; - } else if (compSet.contains(node.getLeftArg())) { - this.toBeReplaced = node.getLeftArg(); - node.replaceChildNode(node.getLeftArg(), replacement); - return; - } else { - super.meet(node); - } - - } - - } - - // moves filter that occurs in both query and index down the query tree so - // that that it is positioned - // above statement patterns associated with index. Precondition for calling - // this method is that - // SPBubbleDownVisitor has been called to position index StatementPatterns - // within query tree. - //could lead to problems if filter optimizer called before external processor - private static class FilterBubbleDownVisitor extends QueryModelVisitorBase<RuntimeException> { - - private QueryModelNode filter; - private Set<QueryModelNode> compSet; - private boolean filterPlaced = false; - - public FilterBubbleDownVisitor(QueryModelNode filter, Set<QueryModelNode> compSet) { - this.filter = filter; - this.compSet = compSet; - - } - - public boolean filterPlaced() { - return filterPlaced; - } - - @Override - public void meet(Join node) { - - if (!compSet.contains(node.getRightArg())) { - // looks for placed to position filter node. if right node is - // contained in index - // and left node is statement pattern node contained in index or - // is a join, place - // filter above join. - if (node.getLeftArg() instanceof Join || !compSet.contains(node.getLeftArg())) { - - QueryModelNode pNode = node.getParentNode(); - ((Filter) filter).setArg(node); - pNode.replaceChildNode(node, filter); - filterPlaced = true; - - return; - } // otherwise place filter below join and above right arg - else { - ((Filter) filter).setArg(node.getRightArg()); - node.replaceChildNode(node.getRightArg(), filter); - filterPlaced = true; - return; - - } - } else if (node.getLeftArg() instanceof StatementPattern && !compSet.contains(node.getLeftArg())) { - - ((Filter) filter).setArg(node.getLeftArg()); - node.replaceChildNode(node.getLeftArg(), filter); - filterPlaced = true; - - return; - } else { - super.meet(node); - } - } - - } - - private static Set<String> getVarNames(Collection<QueryModelNode> nodes) { - - List<String> tempVars; - Set<String> nodeVarNames = Sets.newHashSet(); - - for (QueryModelNode s : nodes) { - tempVars = VarCollector.process(s); - for (String t : tempVars) { - nodeVarNames.add(t); - } - } - return nodeVarNames; - - } - - // visitor which determines whether or not to reposition a filter by calling - // FilterBubbleDownVisitor - private static class FilterBubbleManager extends QueryModelVisitorBase<RuntimeException> { - - private TupleExpr tuple; - private QueryModelNode indexQNode; - private Set<QueryModelNode> sSet = Sets.newHashSet(); - private Set<QueryModelNode> bubbledFilters = Sets.newHashSet(); - - public FilterBubbleManager(ExternalTupleSet index) { - this.tuple = index.getTupleExpr(); - indexQNode = ((Projection) tuple).getArg(); - sSet = getQNodes(indexQNode); - - } - - @Override - public void meet(Filter node) { - - Set<QueryModelNode> eSet = getQNodes(node); - Set<QueryModelNode> compSet = Sets.difference(eSet, sSet); - - // if index contains filter node and it hasn't already been moved, - // move it down - // query tree just above position of statement pattern nodes found - // in both query tree - // and index (assuming that SPBubbleDownVisitor has already been - // called) - if (sSet.contains(node.getCondition()) && !bubbledFilters.contains(node.getCondition())) { - FilterBubbleDownVisitor fbdv = new FilterBubbleDownVisitor(node.clone(), compSet); - node.visit(fbdv); - bubbledFilters.add(node.getCondition()); - // checks if filter correctly placed, and if it has been, - // removes old copy of filter - if (fbdv.filterPlaced()) { - - QueryModelNode pNode = node.getParentNode(); - TupleExpr cNode = node.getArg(); - pNode.replaceChildNode(node, cNode); - - - super.meetNode(pNode); - } - super.meet(node); - - } else { - super.meet(node); - } - } - } - - // iterates through the query tree and attempts to match subtrees with - // index. When a match is - // found, the subtree is replaced by an ExternalTupleSet formed from the - // index. Pre-condition for - // calling this method is that both SPBubbleDownVisitor and - // FilterBubbleManager have been called - // to position the StatementPatterns and Filters. - private static class SubsetEqualsVisitor extends QueryModelVisitorBase<RuntimeException> { - - private TupleExpr tuple; - private QueryModelNode indexQNode; - private ExternalTupleSet set; - private Set<QueryModelNode> sSet = Sets.newHashSet(); - private boolean indexPlaced = false; - - - public SubsetEqualsVisitor(ExternalTupleSet index, TupleExpr query) { - this.tuple = index.getTupleExpr(); - this.set = index; - indexQNode = ((Projection) tuple).getArg(); - sSet = getQNodes(indexQNode); - - } - - public boolean indexPlaced() { - return indexPlaced; - } - - - @Override - public void meet(Join node) { - - Set<QueryModelNode> eSet = getQNodes(node); - - if (eSet.containsAll(sSet) && !(node.getRightArg() instanceof BindingSetAssignment)) { - -// System.out.println("Eset is " + eSet + " and sSet is " + sSet); - - if (eSet.equals(sSet)) { - node.replaceWith(set); - indexPlaced = true; - return; - } else { - if (node.getLeftArg() instanceof StatementPattern && sSet.size() == 1) { - if(sSet.contains(node.getLeftArg())) { - node.setLeftArg(set); - indexPlaced = true; - } else if(sSet.contains(node.getRightArg())) { - node.setRightArg(set); - indexPlaced = true; - } else { - return; - } - } - else { - super.meet(node); - } - } - } else if (eSet.containsAll(sSet)) { - - super.meet(node); - - } else { - return; - } - - } - //to account for index consisting of only filter and BindingSetAssignment nodes - @Override - public void meet(Filter node) { - - Set<QueryModelNode> eSet = getQNodes(node); - - if (eSet.containsAll(sSet)) { - - if (eSet.equals(sSet)) { - node.replaceWith(set); - indexPlaced = true; - return; - } else { - node.getArg().visit(this); - } - } - } - - - @Override - public void meet(StatementPattern node) { - return; - } - } - - // visitor which determines whether a query is valid (i.e. it does not - // contain nodes other than - // Projection, Join, Filter, StatementPattern ) - private static class ValidQueryVisitor extends QueryModelVisitorBase<RuntimeException> { - - private boolean isValid = true; - - public boolean isValid() { - return isValid; - } - - @Override - public void meet(Projection node) { - node.getArg().visit(this); - } - - @Override - public void meet(Filter node) { - node.getArg().visit(this); - } - - - - - - @Override - public void meetNode(QueryModelNode node) { - - if (!(node instanceof Join || node instanceof StatementPattern || node instanceof BindingSetAssignment || node instanceof Var)) { - isValid = false; - return; - - } else{ - super.meetNode(node); - } - } - - } - - // repositions ExternalTuples above StatementPatterns within query tree - private static class ExtTupleExchangeVisitor extends QueryModelVisitorBase<RuntimeException> { - - private Set<QueryModelNode> extTuples; - - public ExtTupleExchangeVisitor(Set<QueryModelNode> extTuples) { - this.extTuples = extTuples; - } - - @Override - public void meet(Join queryNode) { - - // if query tree contains external tuples and they are not - // positioned above statement pattern node - // reposition - if (this.extTuples.size() > 0 && !(queryNode.getRightArg() instanceof ExternalTupleSet) - && !(queryNode.getRightArg() instanceof BindingSetAssignment)) { - - if (queryNode.getLeftArg() instanceof ExternalTupleSet) { - QueryModelNode temp = queryNode.getLeftArg(); - queryNode.setLeftArg(queryNode.getRightArg()); - queryNode.setRightArg((TupleExpr)temp); - } else { - - QNodeExchanger qnev = new QNodeExchanger(queryNode.getRightArg(), this.extTuples); - queryNode.visit(qnev); - queryNode.replaceChildNode(queryNode.getRightArg(), qnev.getReplaced()); - super.meet(queryNode); - } - } else { - super.meet(queryNode); - } - - } - - } - - private static class ExternalTupleCollector extends QueryModelVisitorBase<RuntimeException> { - - private Set<QueryModelNode> eSet = new HashSet<QueryModelNode>(); - - @Override - public void meetNode(QueryModelNode node) throws RuntimeException { - if (node instanceof ExternalTupleSet) { - eSet.add(node); - } - super.meetNode(node); - } - - public Set<QueryModelNode> getExtTup() { - return eSet; - } - - } - - private static class FilterCollector extends QueryModelVisitorBase<RuntimeException> { - - private List<QueryModelNode> filterList = Lists.newArrayList(); - - public List<QueryModelNode> getFilters() { - return filterList; - } - - @Override - public void meet(Filter node) { - filterList.add(node.getCondition()); - super.meet(node); - } - - } - - private static void organizeBSAs(QueryModelNode node) { - - BindingSetAssignmentCollector bsac = new BindingSetAssignmentCollector(); - node.visit(bsac); - - if (bsac.containsBSAs()) { - Set<QueryModelNode> bsaSet = bsac.getBindingSetAssignments(); - BindingSetAssignmentExchangeVisitor bsaev = new BindingSetAssignmentExchangeVisitor(bsaSet); - node.visit(bsaev); - } - } - - // repositions ExternalTuples above StatementPatterns within query tree - private static class BindingSetAssignmentExchangeVisitor extends QueryModelVisitorBase<RuntimeException> { - - private Set<QueryModelNode> bsas; - - public BindingSetAssignmentExchangeVisitor(Set<QueryModelNode> bsas) { - this.bsas = bsas; - } - - @Override - public void meet(Join queryNode) { - - // if query tree contains external tuples and they are not - // positioned above statement pattern node - // reposition - if (this.bsas.size() > 0 && !(queryNode.getRightArg() instanceof BindingSetAssignment)) { - QNodeExchanger qnev = new QNodeExchanger(queryNode.getRightArg(), bsas); - queryNode.visit(qnev); - queryNode.replaceChildNode(queryNode.getRightArg(), qnev.getReplaced()); - super.meet(queryNode); - } else { - super.meet(queryNode); - } - - } - - } - - - public static class BindingSetAssignmentCollector extends QueryModelVisitorBase<RuntimeException> { - - private Set<QueryModelNode> bindingSetList = Sets.newHashSet(); - - public Set<QueryModelNode> getBindingSetAssignments() { - return bindingSetList; - } - - public boolean containsBSAs() { - return bindingSetList.size() > 0; - } - - @Override - public void meet(BindingSetAssignment node) { - bindingSetList.add(node); - super.meet(node); - } - - } - - - - public static class QueryNodeCount extends QueryModelVisitorBase<RuntimeException> { - - private int nodeCount; - - public QueryNodeCount() { - nodeCount = 0; - } - - public int getNodeCount() { - return nodeCount; - } - - - @Override - public void meet(StatementPattern node) { - nodeCount += 1; - return; - } - - @Override - public void meet(Filter node) { - nodeCount += 1; - node.getArg().visit(this); - } - - } - - - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexListPruner.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexListPruner.java b/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexListPruner.java deleted file mode 100644 index 8fbcbe0..0000000 --- a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexListPruner.java +++ /dev/null @@ -1,31 +0,0 @@ -package mvm.rya.indexing.IndexPlanValidator; - -/* - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - - -import java.util.List; - -import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; - -public interface IndexListPruner { - - public List<ExternalTupleSet> getRelevantIndices(List<ExternalTupleSet> indexList); - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexPlanValidator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexPlanValidator.java b/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexPlanValidator.java deleted file mode 100644 index 74df958..0000000 --- a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexPlanValidator.java +++ /dev/null @@ -1,210 +0,0 @@ -package mvm.rya.indexing.IndexPlanValidator; - -/* - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - - -import java.util.Iterator; -import java.util.NoSuchElementException; -import java.util.Set; - -import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; - -import org.openrdf.query.algebra.BindingSetAssignment; -import org.openrdf.query.algebra.Filter; -import org.openrdf.query.algebra.Join; -import org.openrdf.query.algebra.Projection; -import org.openrdf.query.algebra.StatementPattern; -import org.openrdf.query.algebra.TupleExpr; -import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; - -import com.google.common.collect.Sets; - - - - -public class IndexPlanValidator implements TupleValidator { - - private boolean omitCrossProd = false; - - - public IndexPlanValidator(boolean omitCrossProd) { - this.omitCrossProd = omitCrossProd; - } - - public void setOmitCrossProd(boolean omitCrossProd) { - this.omitCrossProd = omitCrossProd; - } - - - @Override - public boolean isValid(TupleExpr te) { - - TupleValidateVisitor tv = new TupleValidateVisitor(); - te.visit(tv); - - return tv.isValid(); - } - - - - - public int getValidTupleSize(Iterator<TupleExpr> iter) { - - int size = 0; - - while(iter.hasNext()) { - if(isValid(iter.next())) { - size++; - } - } - - return size; - - } - - - - @Override - public Iterator<TupleExpr> getValidTuples(Iterator<TupleExpr> tupleIter) { - - final Iterator<TupleExpr> iter = tupleIter; - - return new Iterator<TupleExpr>() { - - private TupleExpr next = null; - private boolean hasNextCalled = false; - private boolean isEmpty = false; - - @Override - public boolean hasNext() { - - if (!hasNextCalled && !isEmpty) { - while (iter.hasNext()) { - TupleExpr temp = iter.next(); - if (isValid(temp)) { - next = temp; - hasNextCalled = true; - return true; - } - } - isEmpty = true; - return false; - } else if(isEmpty) { - return false; - }else { - return true; - } - } - - @Override - public TupleExpr next() { - - if (hasNextCalled) { - hasNextCalled = false; - return next; - } else if(isEmpty) { - throw new NoSuchElementException(); - }else { - if (this.hasNext()) { - hasNextCalled = false; - return next; - } else { - throw new NoSuchElementException(); - } - } - } - - @Override - public void remove() { - - throw new UnsupportedOperationException("Cannot delete from iterator!"); - - } - - }; - } - - private boolean isJoinValid(Join join) { - - Set<String> leftBindingNames = join.getLeftArg().getBindingNames(); - Set<String> rightBindingNames = join.getRightArg().getBindingNames(); - - - //System.out.println("Left binding names are " + leftBindingNames + " and right binding names are " + rightBindingNames); - - if (Sets.intersection(leftBindingNames, rightBindingNames).size() == 0) { - if (omitCrossProd) { - return false; - } else { - return true; - } - - } else { - if (join.getRightArg() instanceof ExternalTupleSet) { - - return ((ExternalTupleSet) join.getRightArg()).supportsBindingSet(leftBindingNames); - - } else { - return true; - } - } - - } - - public class TupleValidateVisitor extends QueryModelVisitorBase<RuntimeException> { - - private boolean isValid = true; - - public boolean isValid() { - return isValid; - } - - @Override - public void meet(Projection node) { - node.getArg().visit(this); - } - - @Override - public void meet(StatementPattern node) { - return; - } - - public void meet(BindingSetAssignment node) { - return; - } - - @Override - public void meet(Filter node) { - node.getArg().visit(this); - } - - @Override - public void meet(Join node) { - if (isJoinValid(node)) { - super.meet(node); - } else { - isValid = false; - return; - } - } - - } - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexTupleGenerator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexTupleGenerator.java b/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexTupleGenerator.java deleted file mode 100644 index 3586a5e..0000000 --- a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexTupleGenerator.java +++ /dev/null @@ -1,33 +0,0 @@ -package mvm.rya.indexing.IndexPlanValidator; - -/* - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - - -import java.util.Iterator; - -import org.openrdf.query.algebra.TupleExpr; - -public interface IndexTupleGenerator { - - - public Iterator<TupleExpr> getPlans(Iterator<TupleExpr> indexPlans); - - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexedExecutionPlanGenerator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexedExecutionPlanGenerator.java b/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexedExecutionPlanGenerator.java deleted file mode 100644 index 22b1e85..0000000 --- a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexedExecutionPlanGenerator.java +++ /dev/null @@ -1,127 +0,0 @@ -package mvm.rya.indexing.IndexPlanValidator; - -/* - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - - -import java.util.Iterator; -import java.util.List; -import java.util.NoSuchElementException; - -import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; -import mvm.rya.indexing.pcj.matching.QueryVariableNormalizer; - -import org.openrdf.query.algebra.Projection; -import org.openrdf.query.algebra.TupleExpr; - -import com.google.common.collect.Lists; - -public class IndexedExecutionPlanGenerator implements ExternalIndexMatcher { - - private final TupleExpr query; - private final List<ExternalTupleSet> normalizedIndexList; - - public IndexedExecutionPlanGenerator(TupleExpr query, List<ExternalTupleSet> indexList) { - this.query = query; - final VarConstantIndexListPruner vci = new VarConstantIndexListPruner(query); - normalizedIndexList = getNormalizedIndices(vci.getRelevantIndices(indexList)); - } - - public List<ExternalTupleSet> getNormalizedIndices() { - return normalizedIndexList; - } - - @Override - public Iterator<TupleExpr> getIndexedTuples() { - - final ValidIndexCombinationGenerator vic = new ValidIndexCombinationGenerator(query); - final Iterator<List<ExternalTupleSet>> iter = vic.getValidIndexCombos(normalizedIndexList); - return new Iterator<TupleExpr>() { - private TupleExpr next = null; - private boolean hasNextCalled = false; - private boolean isEmpty = false; - - @Override - public boolean hasNext() { - - if (!hasNextCalled && !isEmpty) { - while (iter.hasNext()) { - final TupleExpr temp = GeneralizedExternalProcessor.process(query, iter.next()); - if (temp != null) { - next = temp; - hasNextCalled = true; - return true; - } - } - isEmpty = true; - return false; - } else if(isEmpty) { - return false; - } else { - return true; - } - } - - @Override - public TupleExpr next() { - - if (hasNextCalled) { - hasNextCalled = false; - return next; - } else if(isEmpty) { - throw new NoSuchElementException(); - }else { - if (this.hasNext()) { - hasNextCalled = false; - return next; - } else { - throw new NoSuchElementException(); - } - } - } - - @Override - public void remove() { - throw new UnsupportedOperationException("Cannot delete from iterator!"); - } - }; - } - - private List<ExternalTupleSet> getNormalizedIndices(List<ExternalTupleSet> indexSet) { - - ExternalTupleSet tempIndex; - final List<ExternalTupleSet> normalizedIndexSet = Lists.newArrayList(); - - for (final ExternalTupleSet e : indexSet) { - List<TupleExpr> tupList = null; - try { - tupList = QueryVariableNormalizer.getNormalizedIndex(query, e.getTupleExpr()); - } catch (final Exception e1) { - e1.printStackTrace(); - } - - for (final TupleExpr te : tupList) { - tempIndex = (ExternalTupleSet) e.clone(); - tempIndex.setProjectionExpr((Projection) te); - normalizedIndexSet.add(tempIndex); - } - } - return normalizedIndexSet; - } -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexedQueryPlanSelector.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexedQueryPlanSelector.java b/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexedQueryPlanSelector.java deleted file mode 100644 index dbd1972..0000000 --- a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexedQueryPlanSelector.java +++ /dev/null @@ -1,32 +0,0 @@ -package mvm.rya.indexing.IndexPlanValidator; - -/* - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - - -import java.util.Iterator; - -import org.openrdf.query.algebra.TupleExpr; - -public interface IndexedQueryPlanSelector { - - public TupleExpr getThreshholdQueryPlan(Iterator<TupleExpr> tupleList, double threshhold, - double indexWeight, double commonVarWeight, double dirProdWeight); - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/ThreshholdPlanSelector.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/ThreshholdPlanSelector.java b/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/ThreshholdPlanSelector.java deleted file mode 100644 index a333dcb..0000000 --- a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/ThreshholdPlanSelector.java +++ /dev/null @@ -1,240 +0,0 @@ -package mvm.rya.indexing.IndexPlanValidator; - -/* - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - - -import java.util.Iterator; -import java.util.Set; - -import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; - -import org.openrdf.query.algebra.BindingSetAssignment; -import org.openrdf.query.algebra.Filter; -import org.openrdf.query.algebra.Join; -import org.openrdf.query.algebra.Projection; -import org.openrdf.query.algebra.QueryModelNode; -import org.openrdf.query.algebra.StatementPattern; -import org.openrdf.query.algebra.TupleExpr; -import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; - -import com.google.common.collect.Sets; - -public class ThreshholdPlanSelector implements IndexedQueryPlanSelector { - - private TupleExpr query; - private int queryNodeCount = 0; - - public ThreshholdPlanSelector(TupleExpr query) { - this.query = query; - QueryNodeCount qnc = new QueryNodeCount(); - query.visit(qnc); - - this.queryNodeCount = qnc.getNodeCount(); - - if(queryNodeCount == 0) { - throw new IllegalArgumentException("TupleExpr must contain at least one node!"); - } - } - - - - - @Override - public TupleExpr getThreshholdQueryPlan(Iterator<TupleExpr> tuples, double threshhold, double indexWeight, - double commonVarWeight, double extProdWeight) { - - if (threshhold < 0 || threshhold > 1) { - throw new IllegalArgumentException("Threshhold must be between 0 and 1!"); - } - double minCost = Double.MAX_VALUE; - TupleExpr minTup = null; - - double tempCost = 0; - TupleExpr tempTup = null; - - - - while (tuples.hasNext()) { - - tempTup = tuples.next(); - tempCost = getCost(tempTup, indexWeight, commonVarWeight, extProdWeight); - - if (tempCost < minCost) { - minCost = tempCost; - minTup = tempTup; - } - - if (minCost <= threshhold) { - return minTup; - } - - } - - return minTup; - } - - public double getCost(TupleExpr te, double indexWeight, double commonVarWeight, double dirProdWeight) { - - if (indexWeight + commonVarWeight + dirProdWeight != 1) { - throw new IllegalArgumentException("Weights must sum to 1!"); - } - - if(te == null) { - throw new IllegalArgumentException("TupleExpr cannot be null!"); - } - - QueryNodeCount qnc = new QueryNodeCount(); - te.visit(qnc); - - double nodeCount = qnc.getNodeCount(); - double commonJoinVars = qnc.getCommonJoinVarCount(); - double joinVars = qnc.getJoinVarCount(); - double joinCount = qnc.getJoinCount(); - double dirProdCount = qnc.getDirProdCount(); - double dirProductScale; - - if(queryNodeCount > nodeCount) { - dirProductScale = 1/((double)(queryNodeCount - nodeCount)); - } else { - dirProductScale = 1/((double)(queryNodeCount - nodeCount + 1)); - } - - double joinVarRatio; - double dirProductRatio; - - if(joinVars != 0) { - joinVarRatio = (joinVars - commonJoinVars) / joinVars; - } else { - joinVarRatio = 0; - } - - if(joinCount != 0) { - dirProductRatio = dirProdCount / joinCount; - } else { - dirProductRatio = 0; - } - - - double cost = indexWeight * (nodeCount / queryNodeCount) + commonVarWeight*joinVarRatio - + dirProdWeight *dirProductRatio*dirProductScale; - -// System.out.println("Tuple is " + te + " and cost is " + cost); -// System.out.println("Node count is " + nodeCount + " and query node count is " + queryNodeCount); -// System.out.println("Common join vars are " + commonJoinVars + " and join vars " + joinVars); -// System.out.println("Join count is " + joinCount + " and direct prod count is " + dirProdCount); - - return cost; - } - - public static class QueryNodeCount extends QueryModelVisitorBase<RuntimeException> { - - private int nodeCount = 0; - private int commonJoinVars = 0; - private int joinVars = 0; - private int joinCount = 0; - private int dirProdCount = 0; - - public int getCommonJoinVarCount() { - return commonJoinVars; - } - - public int getJoinVarCount() { - return joinVars; - } - - public int getNodeCount() { - return nodeCount; - } - - public int getJoinCount() { - return joinCount; - } - - public int getDirProdCount() { - return dirProdCount; - } - - public void meet(Projection node) { - node.getArg().visit(this); - } - - public void meetNode(QueryModelNode node) { - if (node instanceof ExternalTupleSet) { - nodeCount += 1; - return; - } - super.meetNode(node); - return; - } - - @Override - public void meet(StatementPattern node) { - nodeCount += 1; - return; - } - - @Override - public void meet(Filter node) { - nodeCount += 1; - node.getArg().visit(this); - } - - public void meet(BindingSetAssignment node) { - nodeCount += 1; - return; - } - - @Override - public void meet(Join node) { - - int tempCount = 0; - - Set<String> lNames = node.getLeftArg().getAssuredBindingNames(); - Set<String> rNames = node.getRightArg().getAssuredBindingNames(); - - for(String s: node.getLeftArg().getBindingNames()) { - if(s.startsWith("-const-")) { - lNames.remove(s); - } - } - - for(String s: node.getRightArg().getBindingNames()) { - if(s.startsWith("-const-")) { - rNames.remove(s); - } - } - - - joinVars += Math.min(lNames.size(), rNames.size()); - tempCount = Sets.intersection(lNames, rNames).size(); - if (tempCount == 0) { - dirProdCount += 1; - } else { - commonJoinVars += tempCount; - } - joinCount += 1; - - super.meet(node); - - } - - } - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/44a2dcf0/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/TupleExecutionPlanGenerator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/TupleExecutionPlanGenerator.java b/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/TupleExecutionPlanGenerator.java deleted file mode 100644 index 2776a9e..0000000 --- a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/TupleExecutionPlanGenerator.java +++ /dev/null @@ -1,215 +0,0 @@ -package mvm.rya.indexing.IndexPlanValidator; - -/* - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - - -import java.util.Collection; -import java.util.Iterator; -import java.util.List; -import java.util.NoSuchElementException; -import java.util.Set; - -import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; - -import org.openrdf.query.algebra.BindingSetAssignment; -import org.openrdf.query.algebra.Filter; -import org.openrdf.query.algebra.Join; -import org.openrdf.query.algebra.Projection; -import org.openrdf.query.algebra.QueryModelNode; -import org.openrdf.query.algebra.StatementPattern; -import org.openrdf.query.algebra.TupleExpr; -import org.openrdf.query.algebra.helpers.QueryModelVisitorBase; - -import com.beust.jcommander.internal.Lists; -import com.google.common.collect.Collections2; -import com.google.common.collect.Sets; - -public class TupleExecutionPlanGenerator implements IndexTupleGenerator { - - - - @Override - public Iterator<TupleExpr> getPlans(Iterator<TupleExpr> indexPlans) { - - final Iterator<TupleExpr> iter = indexPlans; - - return new Iterator<TupleExpr>() { - - private TupleExpr next = null; - private boolean hasNextCalled = false; - private boolean isEmpty = false; - Iterator<TupleExpr> tuples = null; - - @Override - public boolean hasNext() { - - if (!hasNextCalled && !isEmpty) { - if (tuples != null && tuples.hasNext()) { - next = tuples.next(); - hasNextCalled = true; - return true; - } else { - while (iter.hasNext()) { - tuples = getPlans(iter.next()).iterator(); - if (tuples == null) { - throw new IllegalStateException("Plans cannot be null!"); - } - next = tuples.next(); - hasNextCalled = true; - return true; - } - isEmpty = true; - return false; - } - } else if (isEmpty) { - return false; - } else { - return true; - } - } - - @Override - public TupleExpr next() { - - if (hasNextCalled) { - hasNextCalled = false; - return next; - } else if(isEmpty) { - throw new NoSuchElementException(); - }else { - if (this.hasNext()) { - hasNextCalled = false; - return next; - } else { - throw new NoSuchElementException(); - } - - } - - } - - @Override - public void remove() { - throw new UnsupportedOperationException("Cannot delete from iterator!"); - } - - }; - - } - - private List<TupleExpr> getPlans(TupleExpr te) { - - - NodeCollector nc = new NodeCollector(); - te.visit(nc); - - Set<QueryModelNode> nodeSet = nc.getNodeSet(); - List<Filter> filterList = nc.getFilterSet(); - Projection projection = nc.getProjection().clone(); - - List<TupleExpr> queryPlans = Lists.newArrayList(); - - Collection<List<QueryModelNode>> plans = Collections2.permutations(nodeSet); - - for (List<QueryModelNode> p : plans) { - if (p.size() == 0) { - throw new IllegalArgumentException("Tuple must contain at least one node!"); - } else if (p.size() == 1) { - queryPlans.add(te); - } else { - queryPlans.add(buildTuple(p, filterList, projection)); - } - } - - return queryPlans; - } - - private TupleExpr buildTuple(List<QueryModelNode> nodes, List<Filter> filters, Projection projection) { - - Projection proj = (Projection)projection.clone(); - Join join = null; - - join = new Join((TupleExpr) nodes.get(0).clone(), (TupleExpr) nodes.get(1).clone()); - - for (int i = 2; i < nodes.size(); i++) { - join = new Join(join, (TupleExpr) nodes.get(i).clone()); - } - - if (filters.size() == 0) { - proj.setArg(join); - return proj; - } else { - TupleExpr queryPlan = join; - for (Filter f : filters) { - Filter filt = (Filter) f.clone(); - filt.setArg(queryPlan); - queryPlan = filt; - } - proj.setArg(queryPlan); - return proj; - } - - } - - public static class NodeCollector extends QueryModelVisitorBase<RuntimeException> { - - private Set<QueryModelNode> nodeSet = Sets.newHashSet(); - private List<Filter> filterSet = Lists.newArrayList(); - private Projection projection; - - public Projection getProjection() { - return projection; - } - - public Set<QueryModelNode> getNodeSet() { - return nodeSet; - } - - public List<Filter> getFilterSet() { - return filterSet; - } - - @Override - public void meet(Projection node) { - projection = node; - node.getArg().visit(this); - } - - @Override - public void meetNode(QueryModelNode node) throws RuntimeException { - if (node instanceof ExternalTupleSet || node instanceof BindingSetAssignment - || node instanceof StatementPattern) { - nodeSet.add(node); - } - super.meetNode(node); - } - - @Override - public void meet(Filter node) { - filterSet.add(node); - node.getArg().visit(this); - } - - } - - - - -}