You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@rya.apache.org by mi...@apache.org on 2016/10/15 20:06:47 UTC
[27/69] [abbrv] [partial] incubator-rya git commit: RYA-198 Renaming
Files
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);
- }
-
- }
-
-
-
-
-}