RYA-32 Improve how metadata and values are written to Accumulo PCJ tables
Project: http://git-wip-us.apache.org/repos/asf/incubator-rya/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-rya/commit/c12f58f4 Tree: http://git-wip-us.apache.org/repos/asf/incubator-rya/tree/c12f58f4 Diff: http://git-wip-us.apache.org/repos/asf/incubator-rya/diff/c12f58f4 Branch: refs/heads/develop Commit: c12f58f46be0aed3c88eff7504d4bfd4e4f295e9 Parents: 4b7bd4f Author: Caleb Meier <[email protected]> Authored: Fri Jan 29 11:40:59 2016 -0500 Committer: Caleb Meier <[email protected]> Committed: Fri Jan 29 11:40:59 2016 -0500 ---------------------------------------------------------------------- extras/indexing/pom.xml | 7 + .../accumulo/precompQuery/AccumuloPcjQuery.java | 352 ++ .../AccumuloPrecompQueryIndexer.java | 326 -- .../GeneralizedExternalProcessor.java | 156 +- .../IndexPlanValidator/IndexListPruner.java | 12 +- .../IndexedExecutionPlanGenerator.java | 109 +- .../ValidIndexCombinationGenerator.java | 1054 ++--- .../VarConstantIndexListPruner.java | 61 +- .../main/java/mvm/rya/indexing/PcjQuery.java | 40 + .../mvm/rya/indexing/PrecompQueryIndexer.java | 63 - .../accumulo/entity/EntityOptimizer.java | 48 +- .../accumulo/entity/EntityTupleSet.java | 73 +- .../rya/indexing/accumulo/entity/StarQuery.java | 342 +- .../rya/indexing/accumulo/geo/GeoTupleSet.java | 53 +- .../indexing/external/ExternalIndexMain.java | 219 - .../indexing/external/ExternalProcessor.java | 726 --- .../mvm/rya/indexing/external/ExternalSail.java | 86 - .../indexing/external/ExternalSailExample.java | 124 - .../indexing/external/PrecompJoinOptimizer.java | 1474 +++--- .../external/tupleSet/AccumuloIndexSet.java | 775 ++-- .../tupleSet/AccumuloPcjSerializer.java | 103 + .../external/tupleSet/ExternalTupleSet.java | 241 +- .../indexing/external/tupleSet/PcjTables.java | 800 ++++ .../tupleSet/SimpleExternalTupleSet.java | 118 +- .../GeneralizedExternalProcessorTest.java | 418 +- .../IndexPlanValidatorTest.java | 1856 +++----- .../IndexedExecutionPlanGeneratorTest.java | 717 ++- .../ThreshholdPlanSelectorTest.java | 1465 +++--- .../TupleExecutionPlanGeneratorTest.java | 138 +- .../IndexPlanValidator/TupleReArrangerTest.java | 83 +- .../ValidIndexCombinationGeneratorTest.java | 1083 ++--- .../VarConstantIndexListPrunerTest.java | 547 ++- .../external/AccumuloConstantIndexSetTest.java | 831 ---- .../AccumuloConstantPcjIntegrationTest.java | 410 ++ .../indexing/external/AccumuloIndexSetTest.java | 4330 ------------------ .../external/AccumuloIndexSetTest2.java | 803 ---- .../external/AccumuloPcjIntegrationTest.java | 1426 ++++++ .../external/PcjIntegrationTestingUtil.java | 385 ++ .../PrecompJoinOptimizerIntegrationTest.java | 939 ++-- .../external/PrecompJoinOptimizerTest.java | 361 +- .../external/PrecompJoinOptimizerTest2.java | 1130 +++++ .../PrecompJoinOptimizerVarToConstTest.java | 430 ++ .../external/tupleSet/AccumuloIndexSetTest.java | 678 +++ .../tupleSet/AccumuloPcjSerialzerTest.java | 114 + .../tupleSet/ExternalProcessorTest.java | 1654 ------- .../tupleSet/PcjTablesIntegrationTests.java | 413 ++ .../external/tupleSet/PcjTablesTests.java | 65 + .../tupleSet/VarConstExternalProcessorTest.java | 490 -- .../src/main/java/RyaDirectExample.java | 1521 +++--- 49 files changed, 12568 insertions(+), 17081 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/c12f58f4/extras/indexing/pom.xml ---------------------------------------------------------------------- diff --git a/extras/indexing/pom.xml b/extras/indexing/pom.xml index f484916..3bfa0ce 100644 --- a/extras/indexing/pom.xml +++ b/extras/indexing/pom.xml @@ -81,6 +81,13 @@ under the License. <artifactId>junit</artifactId> <scope>test</scope> </dependency> + + <dependency> + <groupId>org.apache.accumulo</groupId> + <artifactId>accumulo-minicluster</artifactId> + <version>${accumulo.version}</version> + <scope>test</scope> + </dependency> </dependencies> <build> <plugins> http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/c12f58f4/extras/indexing/src/main/java/mvm/rya/accumulo/precompQuery/AccumuloPcjQuery.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/accumulo/precompQuery/AccumuloPcjQuery.java b/extras/indexing/src/main/java/mvm/rya/accumulo/precompQuery/AccumuloPcjQuery.java new file mode 100644 index 0000000..08c0f78 --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/accumulo/precompQuery/AccumuloPcjQuery.java @@ -0,0 +1,352 @@ +package mvm.rya.accumulo.precompQuery; + +/* + * 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 info.aduna.iteration.Iteration; + +import java.util.Collection; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; +import java.util.NoSuchElementException; +import java.util.Set; + +import mvm.rya.api.resolver.RyaTypeResolverException; +import mvm.rya.indexing.PcjQuery; +import mvm.rya.indexing.external.tupleSet.AccumuloIndexSet; +import mvm.rya.indexing.external.tupleSet.AccumuloPcjSerializer; +import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; + +import org.apache.accumulo.core.client.BatchScanner; +import org.apache.accumulo.core.client.Connector; +import org.apache.accumulo.core.client.TableNotFoundException; +import org.apache.accumulo.core.data.Key; +import org.apache.accumulo.core.data.Range; +import org.apache.accumulo.core.data.Value; +import org.apache.accumulo.core.security.Authorizations; +import org.apache.hadoop.io.Text; +import org.openrdf.query.BindingSet; +import org.openrdf.query.QueryEvaluationException; +import org.openrdf.query.algebra.evaluation.QueryBindingSet; + +import com.google.common.collect.HashMultimap; +import com.google.common.collect.Lists; +import com.google.common.collect.Sets; + +/** + * This class encapsulates how pre-computed join tables are used during query + * evaluation. The method + * {@link AccumuloPcjQuery#queryPrecompJoin(List, String, Map, Map, Collection) + * is used by {@link AccumuloIndexSet#evaluate(BindingSet)} to evaluate the + * {@link AccumuloIndexSet#getTupleExpr()} associated with the Accumulo + * pre-computed join table. Given the {@link BindingSet} constraints, it uses + * the variables common to the BindingSet constraints and the pre-computed join + * table TupleExpr to build a {@Range} prefix to scan the pre-computed + * join table to obtain results for the constrained sub-query. + * + */ +public class AccumuloPcjQuery implements PcjQuery { + private final Connector accCon; + private final String tableName; + + public AccumuloPcjQuery(Connector accCon, String tableName) { + this.accCon = accCon; + this.tableName = tableName; + } + + /** + * @param commonVars - variables common to bsConstraints and table in terms of query variables + * @param localityGroup - the column family to scan in terms of table variables + * @param valMap - Literal type associated with constant constraints + * @param varMap - map query variables to pre-computed join table variables + * @param bsConstraints - binding set constraints + * @return {@link Iteration} over result BindingSets + */ + @Override + public CloseableIteration<BindingSet, QueryEvaluationException> queryPrecompJoin( + List<String> commonVars, String localityGroup, + Map<String, org.openrdf.model.Value> valMap, + Map<String, String> varMap, Collection<BindingSet> bsConstraints) + throws QueryEvaluationException, TableNotFoundException { + + final Iterator<Entry<Key, Value>> accIter; + final Map<String, org.openrdf.model.Value> constValMap = valMap; + final HashMultimap<Range, BindingSet> map = HashMultimap.create(); + + final List<BindingSet> extProdList = Lists.newArrayList(); + final List<String> prefixVars = commonVars; + final BatchScanner bs = accCon.createBatchScanner(tableName, + new Authorizations(), 10); + final Set<Range> ranges = Sets.newHashSet(); + final Map<String, String> tableVarMap = varMap; + final boolean bsContainsPrefixVar = bindingsContainsPrefixVar( + bsConstraints, prefixVars); + + bs.fetchColumnFamily(new Text(localityGroup)); + // process bindingSet and constant constraints + for (final BindingSet bSet : bsConstraints) { + // bindings sets and PCJ have common vars + if (bsContainsPrefixVar) { + byte[] rangePrefix = null; + final QueryBindingSet rangeBs = new QueryBindingSet(); + for (final String var : prefixVars) { + if (var.startsWith(ExternalTupleSet.CONST_PREFIX)) { + rangeBs.addBinding(var, constValMap.get(var)); + } else { + rangeBs.addBinding(var, bSet.getBinding(var).getValue()); + } + } + try { + rangePrefix = AccumuloPcjSerializer.serialize(rangeBs, + commonVars.toArray(new String[commonVars.size()])); + } catch (final RyaTypeResolverException e) { + e.printStackTrace(); + } + final Range r = Range.prefix(new Text(rangePrefix)); + map.put(r, bSet); + ranges.add(r); + // non-empty binding sets and no common vars with no constant + // constraints + } else if (bSet.size() > 0 && prefixVars.size() == 0) { + extProdList.add(bSet); + } + } + + // constant constraints and no bindingSet constraints + // add range of entire table if no constant constraints and + // bsConstraints consists of single, empty set (occurs when AIS is + // first node evaluated in query) + if (ranges.isEmpty()) { + // constant constraints + if (prefixVars.size() > 0) { + byte[] rangePrefix = null; + final QueryBindingSet rangeBs = new QueryBindingSet(); + for (final String var : prefixVars) { + if (var.startsWith(ExternalTupleSet.CONST_PREFIX)) { + rangeBs.addBinding(var, constValMap.get(var)); + } + } + try { + rangePrefix = AccumuloPcjSerializer.serialize(rangeBs, + commonVars.toArray(new String[commonVars.size()])); + } catch (final RyaTypeResolverException e) { + e.printStackTrace(); + } + final Range r = Range.prefix(new Text(rangePrefix)); + ranges.add(r); + } + // no constant or bindingSet constraints + else { + ranges.add(new Range("", true, "~", false)); + } + } + + if (ranges.size() == 0) { + accIter = null; + } else { + bs.setRanges(ranges); + accIter = bs.iterator(); + } + return new CloseableIteration<BindingSet, QueryEvaluationException>() { + @Override + public void remove() throws QueryEvaluationException { + throw new UnsupportedOperationException(); + } + + private Iterator<BindingSet> inputSet = null; + private QueryBindingSet currentSolutionBs = null; + private boolean hasNextCalled = false; + private boolean isEmpty = false; + + @Override + public BindingSet next() throws QueryEvaluationException { + final QueryBindingSet bs = new QueryBindingSet(); + if (hasNextCalled) { + hasNextCalled = false; + if (inputSet != null) { + bs.addAll(inputSet.next()); + } + bs.addAll(currentSolutionBs); + } else if (isEmpty) { + throw new NoSuchElementException(); + } else { + if (this.hasNext()) { + hasNextCalled = false; + if (inputSet != null) { + bs.addAll(inputSet.next()); + } + bs.addAll(currentSolutionBs); + } else { + throw new NoSuchElementException(); + } + } + return bs; + } + + @Override + public boolean hasNext() throws QueryEvaluationException { + if (accIter == null) { + isEmpty = true; + return false; + } + if (!hasNextCalled && !isEmpty) { + while (accIter.hasNext() || inputSet != null + && inputSet.hasNext()) { + if (inputSet != null && inputSet.hasNext()) { + hasNextCalled = true; + return true; + } + final Key k = accIter.next().getKey(); + // get bindings from scan without values associated with + // constant constraints + BindingSet bs; + try { + bs = getBindingSetWithoutConstants(k, tableVarMap); + } catch (final RyaTypeResolverException e) { + throw new QueryEvaluationException(e); + } + currentSolutionBs = new QueryBindingSet(); + currentSolutionBs.addAll(bs); + + // check to see if additional bindingSet constraints + // exist in map + if (map.size() > 0) { + // get prefix range to retrieve remainder of + // bindingSet from map + byte[] rangePrefix; + try { + rangePrefix = getPrefixByte(bs, constValMap, + prefixVars); + } catch (final RyaTypeResolverException e) { + throw new QueryEvaluationException(e); + } + final Range r = Range.prefix(new Text(rangePrefix)); + inputSet = map.get(r).iterator(); + if (!inputSet.hasNext()) { + continue; + } else { + hasNextCalled = true; + return true; + } + // check to see if binding set constraints exist, + // but no common vars + } else if (extProdList.size() > 0) { + inputSet = extProdList.iterator(); + hasNextCalled = true; + return true; + } + // no bindingsSet constraints--only constant constraints + // or none + else { + hasNextCalled = true; + return true; + } + } + isEmpty = true; + return false; + } else if (isEmpty) { + return false; + } else { + return true; + } + } + + @Override + public void close() throws QueryEvaluationException { + bs.close(); + } + }; + } + + /** + * + * @param bindingSets - binding set constraints + * @param prefixVars - common prefix variables to table and any constant constraints + * @return true if there are variables common to binding sets and table and false + * if prefixVars only consists of constant constraints + */ + private boolean bindingsContainsPrefixVar( + Collection<BindingSet> bindingSets, List<String> prefixVars) { + final Iterator<BindingSet> iter = bindingSets.iterator(); + if (iter.hasNext()) { + final BindingSet tempBindingSet = iter.next(); + final Set<String> bindings = tempBindingSet.getBindingNames(); + for (final String var : prefixVars) { + if (bindings.contains(var)) { + return true; + } + } + } + return false; + } + + /** + * + * @param bs - binding set from which byte is extracted + * @param valMap - map which associated Value type to constant constraint + * @param prefixVars - prefix of variables common to binding sets and table and constant constraints + * @return - bytes associated with values in bs that are associated with prefixVars + * @throws RyaTypeResolverException + */ + private static byte[] getPrefixByte(BindingSet bs, + Map<String, org.openrdf.model.Value> valMap, List<String> prefixVars) + throws RyaTypeResolverException { + final QueryBindingSet bSet = new QueryBindingSet(); + for (final String var : prefixVars) { + if (var.startsWith(ExternalTupleSet.CONST_PREFIX)) { + bSet.addBinding(var, valMap.get(var)); + } else if (bs.getBindingNames().size() > 0 + && bs.getBinding(var) != null) { + bSet.addBinding(var, bs.getBinding(var).getValue()); + } + } + return AccumuloPcjSerializer.serialize(bSet, + prefixVars.toArray(new String[prefixVars.size()])); + } + + /** + * + * @param key - Accumulo key obtained from scan + * @param tableVarMap - map that associated query variables and table variables + * @return - BindingSet without values associated with constant constraints + * @throws RyaTypeResolverException + */ + private static BindingSet getBindingSetWithoutConstants(Key key, + Map<String, String> tableVarMap) throws RyaTypeResolverException { + final byte[] row = key.getRow().getBytes(); + final String[] varOrder = key.getColumnFamily().toString() + .split(ExternalTupleSet.VAR_ORDER_DELIM); + final QueryBindingSet temp = new QueryBindingSet( + AccumuloPcjSerializer.deSerialize(row, varOrder)); + final QueryBindingSet bs = new QueryBindingSet(); + for (final String var : temp.getBindingNames()) { + if (!tableVarMap.get(var).startsWith(ExternalTupleSet.CONST_PREFIX)) { + bs.addBinding(tableVarMap.get(var), temp.getValue(var)); + } + } + return bs; + } + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/c12f58f4/extras/indexing/src/main/java/mvm/rya/accumulo/precompQuery/AccumuloPrecompQueryIndexer.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/accumulo/precompQuery/AccumuloPrecompQueryIndexer.java b/extras/indexing/src/main/java/mvm/rya/accumulo/precompQuery/AccumuloPrecompQueryIndexer.java deleted file mode 100644 index 86cb73e..0000000 --- a/extras/indexing/src/main/java/mvm/rya/accumulo/precompQuery/AccumuloPrecompQueryIndexer.java +++ /dev/null @@ -1,326 +0,0 @@ -package mvm.rya.accumulo.precompQuery; - -/* - * 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 java.io.IOException; -import java.util.Collection; -import java.util.Iterator; -import java.util.List; -import java.util.Map; -import java.util.NoSuchElementException; -import java.util.Map.Entry; -import java.util.Set; - -import org.apache.accumulo.core.client.BatchScanner; -import org.apache.accumulo.core.client.Connector; -import org.apache.accumulo.core.client.TableNotFoundException; -import org.apache.accumulo.core.data.Key; -import org.apache.accumulo.core.data.Range; -import org.apache.accumulo.core.data.Value; -import org.apache.accumulo.core.security.Authorizations; -import org.apache.hadoop.io.Text; -import org.openrdf.query.Binding; -import org.openrdf.query.BindingSet; -import org.openrdf.query.QueryEvaluationException; -import org.openrdf.query.algebra.evaluation.QueryBindingSet; - -import com.google.common.collect.HashMultimap; -import com.google.common.collect.Lists; -import com.google.common.collect.Sets; - -import mvm.rya.indexing.PrecompQueryIndexer; -import mvm.rya.indexing.external.tupleSet.AccumuloIndexSet.AccValueFactory; - -public class AccumuloPrecompQueryIndexer implements PrecompQueryIndexer { - - - private Connector accCon; - private String tableName; - private Map<String, AccValueFactory> bindings; - - - - public AccumuloPrecompQueryIndexer(Connector accCon, String tableName) { - this.accCon = accCon; - this.tableName = tableName; - } - - - @Override - public void storeBindingSet(BindingSet bs) throws IOException { - // TODO Auto-generated method stub - - } - - @Override - public void storeBindingSets(Collection<BindingSet> bindingSets) throws IOException, IllegalArgumentException { - // TODO Auto-generated method stub - - } - - @Override - public CloseableIteration<BindingSet, QueryEvaluationException> queryPrecompJoin(List<String> varOrder, - String localityGroup, Map<String, AccValueFactory> bindings, Map<String, org.openrdf.model.Value> valMap, Collection<BindingSet> bsConstraints) - throws QueryEvaluationException, TableNotFoundException { - - - final int prefixLength = Integer.parseInt(varOrder.remove(varOrder.size()-1)); - final Iterator<Entry<Key,Value>> accIter; - final HashMultimap<Range,BindingSet> map = HashMultimap.create(); - final List<BindingSet> extProdList = Lists.newArrayList(); - final Map<String, AccValueFactory> bindingMap = bindings; - final List<String> order = varOrder; - final BatchScanner bs = accCon.createBatchScanner(tableName, new Authorizations(), 10); - final Set<Range> ranges = Sets.newHashSet(); - - - - bs.fetchColumnFamily(new Text(localityGroup)); - - //process bindingSet and constant constraints - for (BindingSet bSet : bsConstraints) { - StringBuffer rangePrefix = new StringBuffer(); - int i = 0; - - for (String b : order) { - - if (i >= prefixLength) { - break; - } - - if (b.startsWith("-const-")) { - String val = bindings.get(b).create(valMap.get(b)); - rangePrefix.append(val); - rangePrefix.append("\u0000"); - } else { - - Binding v = bSet.getBinding(b); - if (v == null) { - throw new IllegalStateException("Binding set can't have null value!"); - } - String val = bindings.get(b).create(bSet.getValue(b)); - rangePrefix.append(val); - rangePrefix.append("\u0000"); - - } - - i++; - - } - if (rangePrefix.length() > 0) { - String prefixWithOutNull = rangePrefix.deleteCharAt(rangePrefix.length() - 1).toString(); - String prefixWithNull = prefixWithOutNull + "\u0001"; - Range r = new Range(new Key(prefixWithOutNull), true, new Key(prefixWithNull), false); - map.put(r, bSet); - ranges.add(r); - } else if (bSet.size() > 0) { - extProdList.add(bSet); - } - } - - //constant constraints and no bindingSet constraints - //add range of entire table if no constant constraints and - //bsConstraints consists of single, empty set (occurs when AIS is - //first node evaluated in query) - if (ranges.isEmpty() && bsConstraints.size() > 0) { - - if (prefixLength > 0) { - StringBuffer rangePrefix = new StringBuffer(); - - int i = 0; - for (String b : order) { - if (i >= prefixLength) { - break; - } - if (b.startsWith("-const-")) { - String val = bindings.get(b).create(valMap.get(b)); - rangePrefix.append(val); - rangePrefix.append("\u0000"); - } - i++; - } - - String prefixWithOutNull = rangePrefix.deleteCharAt(rangePrefix.length() - 1).toString(); - String prefixWithNull = prefixWithOutNull + "\u0001"; - Range r = new Range(new Key(prefixWithOutNull), true, new Key(prefixWithNull), false); - ranges.add(r); - - } else { // no constant or bindingSet constraints - ranges.add(new Range("", true, "~", false)); - } - } - - if (ranges.size() == 0) { - accIter = null; - } else { - bs.setRanges(ranges); - accIter = bs.iterator(); - } - - - return new CloseableIteration<BindingSet, QueryEvaluationException>() { - - @Override - public void remove() throws QueryEvaluationException { - throw new UnsupportedOperationException(); - } - - private Iterator<BindingSet> inputSet = null; - private QueryBindingSet currentSolutionBs = null; - private boolean hasNextCalled = false; - private boolean isEmpty = false; - - - - @Override - public BindingSet next() throws QueryEvaluationException { - QueryBindingSet bs = new QueryBindingSet(); - - if (hasNextCalled) { - hasNextCalled = false; - if (inputSet != null) { - bs.addAll(inputSet.next()); - } - bs.addAll(currentSolutionBs); - } else if (isEmpty) { - throw new NoSuchElementException(); - } else { - if (this.hasNext()) { - hasNextCalled = false; - if (inputSet != null) { - bs.addAll(inputSet.next()); - } - bs.addAll(currentSolutionBs); - } else { - throw new NoSuchElementException(); - } - } - - return bs; - } - - @Override - public boolean hasNext() throws QueryEvaluationException { - - if(accIter == null ) { - isEmpty = true; - return false; - } - - if (!hasNextCalled && !isEmpty) { - while (accIter.hasNext() || (inputSet != null && inputSet.hasNext())) { - - if(inputSet != null && inputSet.hasNext()) { - hasNextCalled = true; - return true; - } - - - Key k = accIter.next().getKey(); - final String[] s = k.getRow().toString().split("\u0000"); - - StringBuilder rangePrefix = new StringBuilder(); - // TODO Assuming that order specifies order of variables - // commmon to - // bindingSet passed in and variables in index table - // --size is equal to - - for (int i = 0; i < prefixLength; i++) { - rangePrefix.append(s[i]); - rangePrefix.append("\u0000"); - } - - // TODO I need to remember what the type was! - currentSolutionBs = new QueryBindingSet(); - int i = 0; - for (String b : order) { - if (b.startsWith("-const")) { - i++; - } else { - final String v = s[i]; - currentSolutionBs.addBinding(b, bindingMap.get(b).create(v)); - i++; - } - - } - //check to see if bindingSet constraints exist - if (map.size() > 0) { - String prefixWithOutNull = rangePrefix.deleteCharAt(rangePrefix.length() - 1).toString(); - String prefixWithNull = prefixWithOutNull + "\u0001"; - Range r = new Range(new Key(prefixWithOutNull), true, new Key(prefixWithNull), false); - inputSet = map.get(r).iterator(); - if (!inputSet.hasNext()) { - continue; - } else { - hasNextCalled = true; - return true; - } // check to see if binding set constraints exist, but no common vars - } else if (extProdList.size() > 0) { - inputSet = extProdList.iterator(); - hasNextCalled = true; - return true; - }else { //no bindingsSet constraints--only constant constraints or none - hasNextCalled = true; - return true; - } - } - - isEmpty = true; - return false; - - } else if (isEmpty) { - return false; - } else { - return true; - } - - } - - @Override - public void close() throws QueryEvaluationException { - bs.close(); - } - - }; - } - - - - @Override - public void flush() throws IOException { - // TODO Auto-generated method stub - - } - - @Override - public void close() throws IOException { - // TODO Auto-generated method stub - - } - - - - - - -} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/c12f58f4/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 index 27a0d15..58e84d9 100644 --- a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/GeneralizedExternalProcessor.java +++ b/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/GeneralizedExternalProcessor.java @@ -8,9 +8,9 @@ package mvm.rya.indexing.IndexPlanValidator; * 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 @@ -53,29 +53,26 @@ 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(); - - - //TODO optimization: turn on when testing done 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 @@ -105,26 +102,18 @@ public class GeneralizedExternalProcessor { } if(indexPlaced) { -// if(indexSet.size() == 3) { -// System.out.println("IndexSet is " + indexSet); -// System.out.println("Tuple is " + rtn); -// } return rtn; } else { -// if(indexSet.size() == 3) { -// System.out.println("IndexSet is " + indexSet); -// } -// return null; } - + } else { throw new IllegalArgumentException("Invalid Query."); } } - - - + + + // determines whether query is valid, which requires that a @@ -139,12 +128,12 @@ public class GeneralizedExternalProcessor { Set<String> spVars = getVarNames(getQNodes("sp", node)); - if (vqv.isValid() && (spVars.size() > 0)) { + 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()); + return fList.size() == Sets.newHashSet(fList).size() && getVarNames(fList).size() <= spVars.size(); } else { return false; @@ -211,16 +200,17 @@ public class GeneralizedExternalProcessor { } - public void meet(Projection node) { + @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); } - public void meet(Join 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())) { @@ -228,7 +218,6 @@ public class GeneralizedExternalProcessor { 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()); @@ -293,7 +282,8 @@ public class GeneralizedExternalProcessor { return toBeReplaced; } - public void meet(Join node) { + @Override + public void meet(Join node) { if (compSet.contains(node.getRightArg())) { this.toBeReplaced = node.getRightArg(); @@ -317,7 +307,6 @@ public class GeneralizedExternalProcessor { // this method is that // SPBubbleDownVisitor has been called to position index StatementPatterns // within query tree. - //TODO this visitor assumes that all filters are positioned at top of query tree //could lead to problems if filter optimizer called before external processor private static class FilterBubbleDownVisitor extends QueryModelVisitorBase<RuntimeException> { @@ -335,7 +324,8 @@ public class GeneralizedExternalProcessor { return filterPlaced; } - public void meet(Join node) { + @Override + public void meet(Join node) { if (!compSet.contains(node.getRightArg())) { // looks for placed to position filter node. if right node is @@ -343,13 +333,13 @@ public class GeneralizedExternalProcessor { // 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()))) { - + 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 { @@ -359,12 +349,12 @@ public class GeneralizedExternalProcessor { return; } - } else if ((node.getLeftArg() instanceof StatementPattern) && !compSet.contains(node.getLeftArg())) { - + } 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); @@ -380,8 +370,9 @@ public class GeneralizedExternalProcessor { for (QueryModelNode s : nodes) { tempVars = VarCollector.process(s); - for (String t : tempVars) - nodeVarNames.add(t); + for (String t : tempVars) { + nodeVarNames.add(t); + } } return nodeVarNames; @@ -403,7 +394,8 @@ public class GeneralizedExternalProcessor { } - public void meet(Filter node) { + @Override + public void meet(Filter node) { Set<QueryModelNode> eSet = getQNodes(node); Set<QueryModelNode> compSet = Sets.difference(eSet, sSet); @@ -415,7 +407,7 @@ public class GeneralizedExternalProcessor { // and index (assuming that SPBubbleDownVisitor has already been // called) if (sSet.contains(node.getCondition()) && !bubbledFilters.contains(node.getCondition())) { - FilterBubbleDownVisitor fbdv = new FilterBubbleDownVisitor((Filter) node.clone(), compSet); + FilterBubbleDownVisitor fbdv = new FilterBubbleDownVisitor(node.clone(), compSet); node.visit(fbdv); bubbledFilters.add(node.getCondition()); // checks if filter correctly placed, and if it has been, @@ -425,7 +417,7 @@ public class GeneralizedExternalProcessor { QueryModelNode pNode = node.getParentNode(); TupleExpr cNode = node.getArg(); pNode.replaceChildNode(node, cNode); - + super.meetNode(pNode); } @@ -446,37 +438,35 @@ public class GeneralizedExternalProcessor { // to position the StatementPatterns and Filters. private static class SubsetEqualsVisitor extends QueryModelVisitorBase<RuntimeException> { - private TupleExpr query; private TupleExpr tuple; private QueryModelNode indexQNode; private ExternalTupleSet set; private Set<QueryModelNode> sSet = Sets.newHashSet(); - private TupleExpr temp; private boolean indexPlaced = false; - + public SubsetEqualsVisitor(ExternalTupleSet index, TupleExpr query) { - this.query = query; this.tuple = index.getTupleExpr(); this.set = index; indexQNode = ((Projection) tuple).getArg(); sSet = getQNodes(indexQNode); } - + public boolean indexPlaced() { return indexPlaced; } - - public void meet(Join node) { + + @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; @@ -506,9 +496,9 @@ public class GeneralizedExternalProcessor { } } - //TODO might need to include BindingSetAssignment Condition here //to account for index consisting of only filter and BindingSetAssignment nodes - public void meet(Filter node) { + @Override + public void meet(Filter node) { Set<QueryModelNode> eSet = getQNodes(node); @@ -523,9 +513,10 @@ public class GeneralizedExternalProcessor { } } } - - - public void meet(StatementPattern node) { + + + @Override + public void meet(StatementPattern node) { return; } } @@ -541,24 +532,27 @@ public class GeneralizedExternalProcessor { return isValid; } - public void meet(Projection node) { + @Override + public void meet(Projection node) { node.getArg().visit(this); } - public void meet(Filter node) { + @Override + public void meet(Filter node) { node.getArg().visit(this); } - - - - - - public void meetNode(QueryModelNode node) { - if (!((node instanceof Join) || (node instanceof StatementPattern) || (node instanceof BindingSetAssignment) || (node instanceof Var))) { + + + + + @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); } @@ -575,21 +569,22 @@ public class GeneralizedExternalProcessor { this.extTuples = extTuples; } - public void meet(Join queryNode) { + @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((QueryModelNode) queryNode.getRightArg(), this.extTuples); + QNodeExchanger qnev = new QNodeExchanger(queryNode.getRightArg(), this.extTuples); queryNode.visit(qnev); queryNode.replaceChildNode(queryNode.getRightArg(), qnev.getReplaced()); super.meet(queryNode); @@ -657,13 +652,14 @@ public class GeneralizedExternalProcessor { this.bsas = bsas; } - public void meet(Join queryNode) { + @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((QueryModelNode) queryNode.getRightArg(), bsas); + QNodeExchanger qnev = new QNodeExchanger(queryNode.getRightArg(), bsas); queryNode.visit(qnev); queryNode.replaceChildNode(queryNode.getRightArg(), qnev.getReplaced()); super.meet(queryNode); @@ -674,8 +670,8 @@ public class GeneralizedExternalProcessor { } } - - + + public static class BindingSetAssignmentCollector extends QueryModelVisitorBase<RuntimeException> { private Set<QueryModelNode> bindingSetList = Sets.newHashSet(); @@ -685,7 +681,7 @@ public class GeneralizedExternalProcessor { } public boolean containsBSAs() { - return (bindingSetList.size() > 0); + return bindingSetList.size() > 0; } @Override @@ -695,9 +691,9 @@ public class GeneralizedExternalProcessor { } } - - - + + + public static class QueryNodeCount extends QueryModelVisitorBase<RuntimeException> { private int nodeCount; @@ -725,6 +721,6 @@ public class GeneralizedExternalProcessor { } - - + + } http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/c12f58f4/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 index fa1dc13..8fbcbe0 100644 --- a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexListPruner.java +++ b/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexListPruner.java @@ -8,9 +8,9 @@ package mvm.rya.indexing.IndexPlanValidator; * 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 @@ -22,14 +22,10 @@ package mvm.rya.indexing.IndexPlanValidator; import java.util.List; - - -import java.util.Set; - import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; public interface IndexListPruner { - public Set<ExternalTupleSet> getRelevantIndices(List<ExternalTupleSet> indexList); - + public List<ExternalTupleSet> getRelevantIndices(List<ExternalTupleSet> indexList); + } http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/c12f58f4/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 index acf3f6a..a0fca34 100644 --- a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexedExecutionPlanGenerator.java +++ b/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/IndexedExecutionPlanGenerator.java @@ -8,9 +8,9 @@ package mvm.rya.indexing.IndexPlanValidator; * 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 @@ -22,9 +22,7 @@ package mvm.rya.indexing.IndexPlanValidator; import java.util.Iterator; import java.util.List; -import java.util.Map; import java.util.NoSuchElementException; -import java.util.Set; import mvm.rya.indexing.external.QueryVariableNormalizer; import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; @@ -32,38 +30,29 @@ import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; import org.openrdf.query.algebra.Projection; import org.openrdf.query.algebra.TupleExpr; -import com.google.common.collect.BiMap; -import com.google.common.collect.HashBiMap; import com.google.common.collect.Lists; -import com.google.common.collect.Maps; -import com.google.common.collect.Sets; public class IndexedExecutionPlanGenerator implements ExternalIndexMatcher { private final TupleExpr query; - private List<ExternalTupleSet> normalizedIndexList; - + private final List<ExternalTupleSet> normalizedIndexList; + public IndexedExecutionPlanGenerator(TupleExpr query, List<ExternalTupleSet> indexList) { this.query = query; - VarConstantIndexListPruner vci = new VarConstantIndexListPruner(query); + final VarConstantIndexListPruner vci = new VarConstantIndexListPruner(query); normalizedIndexList = getNormalizedIndices(vci.getRelevantIndices(indexList)); } - + public List<ExternalTupleSet> getNormalizedIndices() { return normalizedIndexList; } - - - - + @Override public Iterator<TupleExpr> getIndexedTuples() { - - ValidIndexCombinationGenerator vic = new ValidIndexCombinationGenerator(query); - final Iterator<List<ExternalTupleSet>> iter = vic.getValidIndexCombos(normalizedIndexList); + 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; @@ -73,7 +62,7 @@ public class IndexedExecutionPlanGenerator implements ExternalIndexMatcher { if (!hasNextCalled && !isEmpty) { while (iter.hasNext()) { - TupleExpr temp = GeneralizedExternalProcessor.process(query, iter.next()); + final TupleExpr temp = GeneralizedExternalProcessor.process(query, iter.next()); if (temp != null) { next = temp; hasNextCalled = true; @@ -104,104 +93,36 @@ public class IndexedExecutionPlanGenerator implements ExternalIndexMatcher { } else { throw new NoSuchElementException(); } - } - } @Override public void remove() { - throw new UnsupportedOperationException("Cannot delete from iterator!"); - } - }; } - - private List<ExternalTupleSet> getNormalizedIndices(Set<ExternalTupleSet> indexSet) { + private List<ExternalTupleSet> getNormalizedIndices(List<ExternalTupleSet> indexSet) { ExternalTupleSet tempIndex; - List<ExternalTupleSet> normalizedIndexSet = Lists.newArrayList(); - - for (ExternalTupleSet e : indexSet) { + final List<ExternalTupleSet> normalizedIndexSet = Lists.newArrayList(); + for (final ExternalTupleSet e : indexSet) { List<TupleExpr> tupList = null; try { tupList = QueryVariableNormalizer.getNormalizedIndex(query, e.getTupleExpr()); - } catch (Exception e1) { + } catch (final Exception e1) { // TODO Auto-generated catch block e1.printStackTrace(); } - for (TupleExpr te : tupList) { - + for (final TupleExpr te : tupList) { tempIndex = (ExternalTupleSet) e.clone(); - setTableMap(te, tempIndex); - setSupportedVarOrderMap(tempIndex); tempIndex.setProjectionExpr((Projection) te); normalizedIndexSet.add(tempIndex); - } - } - return normalizedIndexSet; } - - private void setTableMap(TupleExpr tupleMatch, ExternalTupleSet index) { - - List<String> replacementVars = Lists.newArrayList(tupleMatch.getBindingNames()); - List<String> tableVars = Lists.newArrayList(index.getTupleExpr().getBindingNames()); - - Map<String, String> tableMap = Maps.newHashMap(); - - for (int i = 0; i < tableVars.size(); i++) { - tableMap.put(replacementVars.get(i), tableVars.get(i)); - } - // System.out.println("Table map is " + tableMap); - index.setTableVarMap(tableMap); - - } - - - private void setSupportedVarOrderMap(ExternalTupleSet index) { - - Map<String, Set<String>> supportedVarOrders = Maps.newHashMap(); - BiMap<String, String> biMap = HashBiMap.create(index.getTableVarMap()).inverse(); - Map<String, Set<String>> oldSupportedVarOrders = index.getSupportedVariableOrderMap(); - - Set<String> temp = null; - Set<String> keys = oldSupportedVarOrders.keySet(); - - for (String s : keys) { - temp = oldSupportedVarOrders.get(s); - Set<String> newSet = Sets.newHashSet(); - - for (String t : temp) { - newSet.add(biMap.get(t)); - } - - String[] tempStrings = s.split("\u0000"); - String v = ""; - for(String u: tempStrings) { - if(v.length() == 0){ - v = v + biMap.get(u); - } else { - v = v + "\u0000" + biMap.get(u); - } - } - - supportedVarOrders.put(v, newSet); - - } - - index.setSupportedVariableOrderMap(supportedVarOrders); - - } - - - - } http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/c12f58f4/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/ValidIndexCombinationGenerator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/ValidIndexCombinationGenerator.java b/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/ValidIndexCombinationGenerator.java index b3c3fcd..483457f 100644 --- a/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/ValidIndexCombinationGenerator.java +++ b/extras/indexing/src/main/java/mvm/rya/indexing/IndexPlanValidator/ValidIndexCombinationGenerator.java @@ -8,9 +8,9 @@ package mvm.rya.indexing.IndexPlanValidator; * 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 @@ -19,7 +19,6 @@ package mvm.rya.indexing.IndexPlanValidator; * under the License. */ - import java.util.Collections; import java.util.Iterator; import java.util.List; @@ -27,645 +26,436 @@ import java.util.NoSuchElementException; import java.util.Set; import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; -import mvm.rya.indexing.external.tupleSet.SimpleExternalTupleSet; -import org.openrdf.query.MalformedQueryException; import org.openrdf.query.algebra.Filter; -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 org.openrdf.query.parser.ParsedQuery; -import org.openrdf.query.parser.sparql.SPARQLParser; import com.google.common.base.Joiner; import com.google.common.collect.Lists; import com.google.common.collect.Sets; public class ValidIndexCombinationGenerator { - - - private TupleExpr query; - private Set<String> invalidCombos = Sets.newTreeSet(); - private Set<QueryModelNode> spFilterSet; - - - public ValidIndexCombinationGenerator(TupleExpr query) { - this.query = query; - SpFilterCollector sfc = new SpFilterCollector(); - query.visit(sfc); - spFilterSet = sfc.getSpFilterSet(); - } - - - - - public Iterator<List<ExternalTupleSet>> getValidIndexCombos(List<ExternalTupleSet> indexSet) { - - Collections.shuffle(indexSet); - final List<ExternalTupleSet> list = indexSet; - final Iterator<List<Integer>> iter = getValidCombos(list); - - return new Iterator<List<ExternalTupleSet>>() { - - private List<ExternalTupleSet> next = null; - private List<Integer> nextCombo = null; - private boolean hasNextCalled = false; - private boolean isEmpty = false; - - @Override - public boolean hasNext() { - - if (!hasNextCalled && !isEmpty) { - if (!iter.hasNext()) { - isEmpty = true; - return false; - } else { - nextCombo = iter.next(); - List<ExternalTupleSet> indexCombo = Lists.newArrayList(); - for (Integer i : nextCombo) { - indexCombo.add(list.get(i)); - } - next = indexCombo; - hasNextCalled = true; - return true; - - } - - } else if (isEmpty) { - return false; - } else { - return true; - } - } - - @Override - public List<ExternalTupleSet> next() { - - if (hasNextCalled) { - hasNextCalled = false; - return next; - } else if(isEmpty) { - throw new NoSuchElementException(); - }else { - if (this.hasNext()) { - hasNextCalled = false; - return next; - } else { - throw new NoSuchElementException(); - } - } - } - - @Override - public void remove() { - - throw new UnsupportedOperationException("Cannot delete from iterator!"); - - } - - }; - - } - - - - private Iterator<List<Integer>> getValidCombos(List<ExternalTupleSet> indexList) { - - - final List<ExternalTupleSet> list = indexList; - final int indexSize = list.size(); - final Iterator<List<Integer>> iter = getCombos(indexSize); - - - return new Iterator<List<Integer>>() { - - private List<Integer> next = null; - private boolean hasNextCalled = false; - private boolean isEmpty = false; - - @Override - public boolean hasNext() { - if (!hasNextCalled && !isEmpty) { - - while (iter.hasNext()) { - List<Integer> tempNext = iter.next(); - if (isValid(tempNext, list)) { - next = tempNext; - hasNextCalled = true; - return true; - } - - } - - isEmpty = true; - return false; - - } else if (isEmpty) { - return false; - } else { - return true; - } - } - - @Override - public List<Integer> next() { - - if (hasNextCalled) { - hasNextCalled = false; - return next; - } else if (isEmpty) { - throw new NoSuchElementException(); - } else { - if (this.hasNext()) { - hasNextCalled = false; - return next; - } else { - throw new NoSuchElementException(); - } - - } - - } - - @Override - public void remove() { - - throw new UnsupportedOperationException("Cannot delete from iterator!"); - - } - - }; - } - - - - - - - private Iterator<List<Integer>> getCombos(int indexListSize) { - - final int indexSize = indexListSize; - final int maxSubListSize = spFilterSet.size() / 2; - - return new Iterator<List<Integer>>() { - - private List<Integer> next = null; - private boolean hasNextCalled = false; - private boolean isEmpty = false; - private int subListSize = Math.min(maxSubListSize, indexSize) + 1; - Iterator<List<Integer>> subList = null; - - @Override - public boolean hasNext() { - - if (!hasNextCalled && !isEmpty) { - if (subList != null && subList.hasNext()) { - next = subList.next(); - hasNextCalled = true; - return true; - } else { - subListSize--; - if (subListSize == 0) { - isEmpty = true; - return false; - } - subList = getCombos(subListSize, indexSize); - if (subList == null) { - throw new IllegalStateException("Combos cannot be null!"); - } - next = subList.next(); - hasNextCalled = true; - return true; - - } - } else if (isEmpty) { - return false; - } else { - return true; - } - } - - @Override - public List<Integer> next() { - - if (hasNextCalled) { - hasNextCalled = false; - return next; - } else if (isEmpty) { - throw new NoSuchElementException(); - } else { - if (this.hasNext()) { - hasNextCalled = false; - return next; - } else { - throw new NoSuchElementException(); - } - - } - - } - - @Override - public void remove() { - throw new UnsupportedOperationException("Cannot delete from iterator!"); - } - - }; - - } - - - - private Iterator<List<Integer>> getCombos(int subListSize, int indexListSize) { - - if(subListSize > indexListSize) { - throw new IllegalArgumentException("Sublist size must be less than or equal to list size!"); - } - - final int subSize = subListSize; - final int indexSize = indexListSize; - - return new Iterator<List<Integer>>() { - - private List<Integer> next = null; - private List<Integer> tempList = Lists.newArrayList(); - private boolean calledHasNext = false; - private boolean isEmpty = false; - - @Override - public boolean hasNext() { - - if (!calledHasNext && !isEmpty) { - if (next == null) { - for (int i = 0; i < subSize; i++) { - tempList.add(i); - } - next = tempList; - calledHasNext = true; - return true; - } else { - next = getNext(next, indexSize - 1); - if (next == null) { - isEmpty = true; - return false; - } else { - calledHasNext = true; - return true; - } - - } - } else if(isEmpty) { - return false; - } else { - return true; - } - - } - - @Override - public List<Integer> next() { - - if (calledHasNext) { - calledHasNext = false; - return next; - } else if (isEmpty) { - throw new NoSuchElementException(); - } else { - if (this.hasNext()) { - calledHasNext = false; - return next; - } else { - throw new NoSuchElementException(); - } - } - } - @Override - public void remove() { - throw new UnsupportedOperationException(); - - } - - - - }; - } - - - - - - - private List<Integer> getNext(List<Integer> prev, int maxInt) { - - List<Integer> returnList = Lists.newArrayList(); - int size = prev.size(); - int incrementPos = -1; - int incrementVal = 0; - - for(int i = 0; i < size; i++) { - if(prev.get(size-(i+1)) != maxInt - i) { - incrementPos = size - (i+1); - break; - } - } - - if (incrementPos == -1) { - return null; - } else { - - incrementVal = prev.get(incrementPos); - for (int i = 0; i < incrementPos; i++) { - returnList.add(prev.get(i)); - } - - for (int j = incrementPos; j < size; j++) { - returnList.add(++incrementVal); - } - - return returnList; - } - } - - - - - private boolean isValid(List<Integer> combo, List<ExternalTupleSet> indexList) { - - String s1 = Joiner.on("\u0000").join(combo).trim(); - - if(invalidCombos.contains(s1)) { - return false; - } else { - int valid = indicesDisjoint(combo, indexList); - - if (valid >= 0) { - String s2 = ""; - for (int i = 0; i < valid + 1; i++) { - if (s2.length() == 0) { - s2 = s2 + combo.get(i); - } else { - s2 = s2 + "\u0000" + combo.get(i); - } - } - invalidCombos.add(s2); - - for (int i = valid + 1; i < combo.size(); i++) { - s2 = s2 + "\u0000" + combo.get(i); - invalidCombos.add(s2); - } - - return false; - } else { - return true; - } - } - - - } - - - - private int indicesDisjoint(List<Integer> combo, List<ExternalTupleSet> indexList) { - - Set<QueryModelNode> indexNodes = Sets.newHashSet(); - Set<QueryModelNode> tempNodes; - TupleExpr temp; - - - int j = 0; - for(Integer i: combo) { - temp = indexList.get(i).getTupleExpr(); - SpFilterCollector spf = new SpFilterCollector(); - temp.visit(spf); - tempNodes = spf.getSpFilterSet(); - if(Sets.intersection(indexNodes, tempNodes).size() == 0) { - indexNodes = Sets.union(indexNodes, tempNodes); - if(indexNodes.size() > spFilterSet.size()) { - return j; - } - } else { - return j; - } - j++; - } - - return -1; - } - - - - - public static void main(String[] args) { - - - String q1 = ""// - + "SELECT ?f ?m ?d " // - + "{" // - + " ?f a ?m ."// - + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + " ?d <uri:talksTo> ?f . "// - + " ?f <uri:hangOutWith> ?m ." // - + " ?m <uri:hangOutWith> ?d ." // - + " ?f <uri:associatesWith> ?m ." // - + " ?m <uri:associatesWith> ?d ." // - + "}";// - - - String q2 = ""// - + "SELECT ?t ?s ?u " // - + "{" // - + " ?s a ?t ."// - + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// - + " ?u <uri:talksTo> ?s . "// - + "}";// - - - String q3 = ""// - + "SELECT ?s ?t ?u " // - + "{" // - + " ?s <uri:hangOutWith> ?t ." // - + " ?t <uri:hangOutWith> ?u ." // - + "}";// - - String q4 = ""// - + "SELECT ?s ?t ?u " // - + "{" // - + " ?s <uri:associatesWith> ?t ." // - + " ?t <uri:associatesWith> ?u ." // - + "}";// - - - String q5 = ""// - + "SELECT ?t ?s ?u " // - + "{" // - + " ?s a ?t ."// - + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// - + " ?u <uri:talksTo> ?s . "// - + " ?s <uri:hangOutWith> ?t ." // - + " ?t <uri:hangOutWith> ?u ." // - + "}";// - - String q6 = ""// - + "SELECT ?s ?t ?u " // - + "{" // - + " ?s <uri:associatesWith> ?t ." // - + " ?t <uri:associatesWith> ?u ." // - + " ?s <uri:hangOutWith> ?t ." // - + " ?t <uri:hangOutWith> ?u ." // - + "}";// - - - String q7 = ""// - + "SELECT ?s ?t ?u " // - + "{" // - + " ?s <uri:associatesWith> ?t ." // - + " ?t <uri:associatesWith> ?u ." // - + " ?t <uri:hangOutWith> ?u ." // - + "}";// - - - - String q8 = ""// - + "SELECT ?t ?s ?u " // - + "{" // - + " ?s a ?t ."// - + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// - + " ?u <uri:talksTo> ?s . "// - + " ?s <uri:associatesWith> ?t ." // - + "}";// - - - String q9 = ""// - + "SELECT ?t ?s ?u " // - + "{" // - + " ?s a ?t ."// - + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// - + "}";// - - - - - - - - - - SPARQLParser parser = new SPARQLParser(); - ParsedQuery pq1 = null; - ParsedQuery pq2 = null; - ParsedQuery pq3 = null; - ParsedQuery pq4 = null; - ParsedQuery pq5 = null; - ParsedQuery pq6 = null; - ParsedQuery pq7 = null; - ParsedQuery pq8 = null; - ParsedQuery pq9 = null; - - SimpleExternalTupleSet extTup1 = null; - SimpleExternalTupleSet extTup2 = null; - SimpleExternalTupleSet extTup3 = null; - SimpleExternalTupleSet extTup4 = null; - SimpleExternalTupleSet extTup5 = null; - SimpleExternalTupleSet extTup6 = null; - SimpleExternalTupleSet extTup7 = null; - SimpleExternalTupleSet extTup8 = null; - - - - - - try { - pq1 = parser.parseQuery(q1, null); - pq2 = parser.parseQuery(q2, null); - pq3 = parser.parseQuery(q3, null); - pq4 = parser.parseQuery(q4, null); - pq5 = parser.parseQuery(q5, null); - pq6 = parser.parseQuery(q6, null); - pq7 = parser.parseQuery(q7, null); - pq8 = parser.parseQuery(q8, null); - pq9 = parser.parseQuery(q9, null); - - - extTup1 = new SimpleExternalTupleSet((Projection) pq2.getTupleExpr()); - extTup2 = new SimpleExternalTupleSet((Projection) pq3.getTupleExpr()); - extTup3 = new SimpleExternalTupleSet((Projection) pq4.getTupleExpr()); - extTup4 = new SimpleExternalTupleSet((Projection) pq5.getTupleExpr()); - extTup5 = new SimpleExternalTupleSet((Projection) pq6.getTupleExpr()); - extTup6 = new SimpleExternalTupleSet((Projection) pq7.getTupleExpr()); - extTup7 = new SimpleExternalTupleSet((Projection) pq8.getTupleExpr()); - extTup8 = new SimpleExternalTupleSet((Projection) pq9.getTupleExpr()); - - - } catch (MalformedQueryException e) { - // TODO Auto-generated catch block - e.printStackTrace(); - } - - List<ExternalTupleSet> indexList = Lists.newArrayList(); - indexList.add(extTup1); - indexList.add(extTup2); - indexList.add(extTup3); - indexList.add(extTup4); - indexList.add(extTup5); - indexList.add(extTup6); - indexList.add(extTup7); - indexList.add(extTup8); - - - ValidIndexCombinationGenerator vic = new ValidIndexCombinationGenerator(pq1.getTupleExpr()); - Iterator<List<ExternalTupleSet>> combos = vic.getValidIndexCombos(indexList); - int size = 0; - while(combos.hasNext()) { - combos.hasNext(); - size++; - List<ExternalTupleSet> eSet = combos.next(); - System.out.println("********************************************"); - for(ExternalTupleSet e: eSet) { - System.out.println(e.getTupleExpr()); - } - System.out.println("********************************************"); - } - - System.out.println("size is " + size + " has next " + combos.hasNext()); - } - - - - - - private static class SpFilterCollector extends QueryModelVisitorBase<RuntimeException> { - - private Set<QueryModelNode> spFilterSet = Sets.newHashSet(); - - - public int getNodeNumber() { - return spFilterSet.size(); - } - - - public Set<QueryModelNode> getSpFilterSet() { - return spFilterSet; - } - - - @Override - public void meet(StatementPattern node) { - - spFilterSet.add(node); - return; - - } - - - @Override - public void meet(Filter node) { - - spFilterSet.add(node.getCondition()); - node.getArg().visit(this); - } - - - } + + private TupleExpr query; + private Set<String> invalidCombos = Sets.newTreeSet(); + private Set<QueryModelNode> spFilterSet; + + public ValidIndexCombinationGenerator(TupleExpr query) { + this.query = query; + SpFilterCollector sfc = new SpFilterCollector(); + query.visit(sfc); + spFilterSet = sfc.getSpFilterSet(); + } + + public Iterator<List<ExternalTupleSet>> getValidIndexCombos( + List<ExternalTupleSet> indexSet) { + + Collections.shuffle(indexSet); + final List<ExternalTupleSet> list = indexSet; + final Iterator<List<Integer>> iter = getValidCombos(list); + + return new Iterator<List<ExternalTupleSet>>() { + + private List<ExternalTupleSet> next = null; + private List<Integer> nextCombo = null; + private boolean hasNextCalled = false; + private boolean isEmpty = false; + + @Override + public boolean hasNext() { + + if (!hasNextCalled && !isEmpty) { + if (!iter.hasNext()) { + isEmpty = true; + return false; + } else { + nextCombo = iter.next(); + List<ExternalTupleSet> indexCombo = Lists + .newArrayList(); + for (Integer i : nextCombo) { + indexCombo.add(list.get(i)); + } + next = indexCombo; + hasNextCalled = true; + return true; + + } + + } else if (isEmpty) { + return false; + } else { + return true; + } + } + + @Override + public List<ExternalTupleSet> next() { + + if (hasNextCalled) { + hasNextCalled = false; + return next; + } else if (isEmpty) { + throw new NoSuchElementException(); + } else { + if (this.hasNext()) { + hasNextCalled = false; + return next; + } else { + throw new NoSuchElementException(); + } + } + } + + @Override + public void remove() { + + throw new UnsupportedOperationException( + "Cannot delete from iterator!"); + + } + + }; + + } + + private Iterator<List<Integer>> getValidCombos( + List<ExternalTupleSet> indexList) { + + final List<ExternalTupleSet> list = indexList; + final int indexSize = list.size(); + final Iterator<List<Integer>> iter = getCombos(indexSize); + + return new Iterator<List<Integer>>() { + + private List<Integer> next = null; + private boolean hasNextCalled = false; + private boolean isEmpty = false; + + @Override + public boolean hasNext() { + if (!hasNextCalled && !isEmpty) { + + while (iter.hasNext()) { + List<Integer> tempNext = iter.next(); + if (isValid(tempNext, list)) { + next = tempNext; + hasNextCalled = true; + return true; + } + + } + + isEmpty = true; + return false; + + } else if (isEmpty) { + return false; + } else { + return true; + } + } + + @Override + public List<Integer> next() { + + if (hasNextCalled) { + hasNextCalled = false; + return next; + } else if (isEmpty) { + throw new NoSuchElementException(); + } else { + if (this.hasNext()) { + hasNextCalled = false; + return next; + } else { + throw new NoSuchElementException(); + } + + } + + } + + @Override + public void remove() { + + throw new UnsupportedOperationException( + "Cannot delete from iterator!"); + + } + + }; + } + + private Iterator<List<Integer>> getCombos(int indexListSize) { + + final int indexSize = indexListSize; + final int maxSubListSize = spFilterSet.size() / 2; + + return new Iterator<List<Integer>>() { + + private List<Integer> next = null; + private boolean hasNextCalled = false; + private boolean isEmpty = false; + private int subListSize = Math.min(maxSubListSize, indexSize) + 1; + Iterator<List<Integer>> subList = null; + + @Override + public boolean hasNext() { + + if (!hasNextCalled && !isEmpty) { + if (subList != null && subList.hasNext()) { + next = subList.next(); + hasNextCalled = true; + return true; + } else { + subListSize--; + if (subListSize == 0) { + isEmpty = true; + return false; + } + subList = getCombos(subListSize, indexSize); + if (subList == null) { + throw new IllegalStateException( + "Combos cannot be null!"); + } + next = subList.next(); + hasNextCalled = true; + return true; + + } + } else if (isEmpty) { + return false; + } else { + return true; + } + } + + @Override + public List<Integer> next() { + + if (hasNextCalled) { + hasNextCalled = false; + return next; + } else if (isEmpty) { + throw new NoSuchElementException(); + } else { + if (this.hasNext()) { + hasNextCalled = false; + return next; + } else { + throw new NoSuchElementException(); + } + + } + + } + + @Override + public void remove() { + throw new UnsupportedOperationException( + "Cannot delete from iterator!"); + } + + }; + + } + + private Iterator<List<Integer>> getCombos(int subListSize, int indexListSize) { + + if (subListSize > indexListSize) { + throw new IllegalArgumentException( + "Sublist size must be less than or equal to list size!"); + } + + final int subSize = subListSize; + final int indexSize = indexListSize; + + return new Iterator<List<Integer>>() { + + private List<Integer> next = null; + private List<Integer> tempList = Lists.newArrayList(); + private boolean calledHasNext = false; + private boolean isEmpty = false; + + @Override + public boolean hasNext() { + + if (!calledHasNext && !isEmpty) { + if (next == null) { + for (int i = 0; i < subSize; i++) { + tempList.add(i); + } + next = tempList; + calledHasNext = true; + return true; + } else { + next = getNext(next, indexSize - 1); + if (next == null) { + isEmpty = true; + return false; + } else { + calledHasNext = true; + return true; + } + + } + } else if (isEmpty) { + return false; + } else { + return true; + } + + } + + @Override + public List<Integer> next() { + + if (calledHasNext) { + calledHasNext = false; + return next; + } else if (isEmpty) { + throw new NoSuchElementException(); + } else { + if (this.hasNext()) { + calledHasNext = false; + return next; + } else { + throw new NoSuchElementException(); + } + } + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + + } + + }; + } + + private List<Integer> getNext(List<Integer> prev, int maxInt) { + + List<Integer> returnList = Lists.newArrayList(); + int size = prev.size(); + int incrementPos = -1; + int incrementVal = 0; + + for (int i = 0; i < size; i++) { + if (prev.get(size - (i + 1)) != maxInt - i) { + incrementPos = size - (i + 1); + break; + } + } + + if (incrementPos == -1) { + return null; + } else { + + incrementVal = prev.get(incrementPos); + for (int i = 0; i < incrementPos; i++) { + returnList.add(prev.get(i)); + } + + for (int j = incrementPos; j < size; j++) { + returnList.add(++incrementVal); + } + + return returnList; + } + } + + private boolean isValid(List<Integer> combo, + List<ExternalTupleSet> indexList) { + + String s1 = Joiner.on("\u0000").join(combo).trim(); + + if (invalidCombos.contains(s1)) { + return false; + } else { + int valid = indicesDisjoint(combo, indexList); + + if (valid >= 0) { + String s2 = ""; + for (int i = 0; i < valid + 1; i++) { + if (s2.length() == 0) { + s2 = s2 + combo.get(i); + } else { + s2 = s2 + "\u0000" + combo.get(i); + } + } + invalidCombos.add(s2); + + for (int i = valid + 1; i < combo.size(); i++) { + s2 = s2 + "\u0000" + combo.get(i); + invalidCombos.add(s2); + } + + return false; + } else { + return true; + } + } + + } + + private int indicesDisjoint(List<Integer> combo, + List<ExternalTupleSet> indexList) { + + Set<QueryModelNode> indexNodes = Sets.newHashSet(); + Set<QueryModelNode> tempNodes; + TupleExpr temp; + + int j = 0; + for (Integer i : combo) { + temp = indexList.get(i).getTupleExpr(); + SpFilterCollector spf = new SpFilterCollector(); + temp.visit(spf); + tempNodes = spf.getSpFilterSet(); + if (Sets.intersection(indexNodes, tempNodes).size() == 0) { + indexNodes = Sets.union(indexNodes, tempNodes); + if (indexNodes.size() > spFilterSet.size()) { + return j; + } + } else { + return j; + } + j++; + } + + return -1; + } + + private static class SpFilterCollector extends + QueryModelVisitorBase<RuntimeException> { + + private Set<QueryModelNode> spFilterSet = Sets.newHashSet(); + + public int getNodeNumber() { + return spFilterSet.size(); + } + + public Set<QueryModelNode> getSpFilterSet() { + return spFilterSet; + } + + @Override + public void meet(StatementPattern node) { + + spFilterSet.add(node); + return; + + } + + @Override + public void meet(Filter node) { + + spFilterSet.add(node.getCondition()); + node.getArg().visit(this); + } + + } }
