RYA-151 Implemented a PCJOptimizer benchmark tool.
Project: http://git-wip-us.apache.org/repos/asf/incubator-rya/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-rya/commit/3e17a258 Tree: http://git-wip-us.apache.org/repos/asf/incubator-rya/tree/3e17a258 Diff: http://git-wip-us.apache.org/repos/asf/incubator-rya/diff/3e17a258 Branch: refs/heads/master Commit: 3e17a2582a9ad50c2126c038f38389bf7a83c6aa Parents: e77e839 Author: Kevin Chilton <[email protected]> Authored: Fri Sep 2 16:30:00 2016 -0400 Committer: pujav65 <[email protected]> Committed: Tue Sep 27 11:05:07 2016 -0400 ---------------------------------------------------------------------- .../java/mvm/rya/api/client/BatchUpdatePCJ.java | 18 + .../api/client/PCJDoesNotExistException.java | 18 + .../client/accumulo/AccumuloBatchUpdatePCJ.java | 18 + .../tupleSet/SimpleExternalTupleSet.java | 73 +--- .../rya/indexing/pcj/matching/PCJOptimizer.java | 6 +- .../accumulo/AccumuloBatchUpdatePCJIT.java | 18 + .../tupleSet/SimpleExternalTupleSetTest.java | 173 ++++++++ .../benchmark/query/PCJOptimizerBenchmark.java | 421 +++++++++++++++++++ 8 files changed, 691 insertions(+), 54 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/3e17a258/common/rya.api/src/main/java/mvm/rya/api/client/BatchUpdatePCJ.java ---------------------------------------------------------------------- diff --git a/common/rya.api/src/main/java/mvm/rya/api/client/BatchUpdatePCJ.java b/common/rya.api/src/main/java/mvm/rya/api/client/BatchUpdatePCJ.java index 20d90e0..d6f3454 100644 --- a/common/rya.api/src/main/java/mvm/rya/api/client/BatchUpdatePCJ.java +++ b/common/rya.api/src/main/java/mvm/rya/api/client/BatchUpdatePCJ.java @@ -1,3 +1,21 @@ +/* + * 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. + */ package mvm.rya.api.client; import javax.annotation.ParametersAreNonnullByDefault; http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/3e17a258/common/rya.api/src/main/java/mvm/rya/api/client/PCJDoesNotExistException.java ---------------------------------------------------------------------- diff --git a/common/rya.api/src/main/java/mvm/rya/api/client/PCJDoesNotExistException.java b/common/rya.api/src/main/java/mvm/rya/api/client/PCJDoesNotExistException.java index 63efe0c..89f095f 100644 --- a/common/rya.api/src/main/java/mvm/rya/api/client/PCJDoesNotExistException.java +++ b/common/rya.api/src/main/java/mvm/rya/api/client/PCJDoesNotExistException.java @@ -1,3 +1,21 @@ +/* + * 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. + */ package mvm.rya.api.client; import javax.annotation.ParametersAreNonnullByDefault; http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/3e17a258/extras/indexing/src/main/java/mvm/rya/api/client/accumulo/AccumuloBatchUpdatePCJ.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/api/client/accumulo/AccumuloBatchUpdatePCJ.java b/extras/indexing/src/main/java/mvm/rya/api/client/accumulo/AccumuloBatchUpdatePCJ.java index ee773b0..53f29f4 100644 --- a/extras/indexing/src/main/java/mvm/rya/api/client/accumulo/AccumuloBatchUpdatePCJ.java +++ b/extras/indexing/src/main/java/mvm/rya/api/client/accumulo/AccumuloBatchUpdatePCJ.java @@ -1,3 +1,21 @@ +/* + * 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. + */ package mvm.rya.api.client.accumulo; import static java.util.Objects.requireNonNull; http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/3e17a258/extras/indexing/src/main/java/mvm/rya/indexing/external/tupleSet/SimpleExternalTupleSet.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/external/tupleSet/SimpleExternalTupleSet.java b/extras/indexing/src/main/java/mvm/rya/indexing/external/tupleSet/SimpleExternalTupleSet.java index 2c5ef44..ccdb7a8 100644 --- a/extras/indexing/src/main/java/mvm/rya/indexing/external/tupleSet/SimpleExternalTupleSet.java +++ b/extras/indexing/src/main/java/mvm/rya/indexing/external/tupleSet/SimpleExternalTupleSet.java @@ -1,5 +1,3 @@ -package mvm.rya.indexing.external.tupleSet; - /* * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file @@ -18,13 +16,10 @@ package mvm.rya.indexing.external.tupleSet; * specific language governing permissions and limitations * under the License. */ +package mvm.rya.indexing.external.tupleSet; -import info.aduna.iteration.CloseableIteration; - -import java.util.HashMap; -import java.util.HashSet; -import java.util.Map; -import java.util.Set; +import java.util.ArrayList; +import java.util.List; import org.openrdf.query.BindingSet; import org.openrdf.query.QueryEvaluationException; @@ -32,51 +27,46 @@ import org.openrdf.query.algebra.Projection; import org.openrdf.query.algebra.QueryModelVisitor; import com.google.common.base.Joiner; -import com.google.common.collect.Sets; + +import info.aduna.iteration.CloseableIteration; /** * This a testing class to create mock pre-computed join nodes in order to * test the {@link PrecompJoinOptimizer} for query planning. - * */ - public class SimpleExternalTupleSet extends ExternalTupleSet { - public SimpleExternalTupleSet(Projection tuple) { + /** + * Constructs an instance of {@link SimpleExternalTupleSet}. + * + * @param tuple - An expression that represents the PCJ. (not null) + */ + public SimpleExternalTupleSet(final Projection tuple) { this.setProjectionExpr(tuple); setSupportedVarOrders(); } private void setSupportedVarOrders() { + final List<String> varOrders = new ArrayList<>(); - final Set<String> varSet = Sets.newHashSet(); - final Map<String, Set<String>> supportedVarOrders = new HashMap<>(); - String t = ""; - - for (final String s : this.getTupleExpr().getAssuredBindingNames()) { - if (t.length() == 0) { - t = s; - } else { - t = t + VAR_ORDER_DELIM + s; - } + String varOrder = ""; + for(final String var : this.getTupleExpr().getAssuredBindingNames()) { + varOrder = varOrder.isEmpty() ? var : varOrder + VAR_ORDER_DELIM + var; + varOrders.add( varOrder ); + } - varSet.add(s); - supportedVarOrders.put(t, new HashSet<String>(varSet)); - - } - this.setSupportedVariableOrderMap(supportedVarOrders); + this.setSupportedVariableOrderMap(varOrders); } @Override - public <X extends Exception> void visit(QueryModelVisitor<X> visitor) + public <X extends Exception> void visit(final QueryModelVisitor<X> visitor) throws X { visitor.meetOther(this); } @Override - public CloseableIteration<BindingSet, QueryEvaluationException> evaluate( - BindingSet bindings) throws QueryEvaluationException { - // TODO Auto-generated method stub + public CloseableIteration<BindingSet, QueryEvaluationException> evaluate( final BindingSet bindings) throws QueryEvaluationException { + // Intentionally does nothing. return null; } @@ -88,23 +78,4 @@ public class SimpleExternalTupleSet extends ExternalTupleSet { .getElements()).replaceAll("\\s+", " "); } - - @Override - public boolean equals(Object other) { - - if (!(other instanceof SimpleExternalTupleSet)) { - return false; - } else { - - final SimpleExternalTupleSet arg = (SimpleExternalTupleSet) other; - if (this.getTupleExpr().equals(arg.getTupleExpr())) { - return true; - } else { - return false; - } - - } - - } - -} +} \ No newline at end of file http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/3e17a258/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJOptimizer.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJOptimizer.java b/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJOptimizer.java index 046bd53..8ce89bf 100644 --- a/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJOptimizer.java +++ b/extras/indexing/src/main/java/mvm/rya/indexing/pcj/matching/PCJOptimizer.java @@ -83,8 +83,8 @@ import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; * */ public class PCJOptimizer implements QueryOptimizer, Configurable { - private static final Logger log = Logger.getLogger(PCJOptimizer.class); + private List<ExternalTupleSet> indexSet; private Configuration conf; private boolean init = false; @@ -104,7 +104,7 @@ public class PCJOptimizer implements QueryOptimizer, Configurable { } catch (MalformedQueryException | SailException | QueryEvaluationException | TableNotFoundException | AccumuloException | AccumuloSecurityException | PcjException e) { - e.printStackTrace(); + log.error(e.getMessage(), e); } init = true; } @@ -352,7 +352,7 @@ public class PCJOptimizer implements QueryOptimizer, Configurable { //use table name sparql map (indexTables) to create {@link AccumuloIndexSet} final List<ExternalTupleSet> index = Lists.newArrayList(); if (indexTables.isEmpty()) { - System.out.println("No Index found"); + log.info("No Index found"); } else { for (final String table : indexTables.keySet()) { final String indexSparqlString = indexTables.get(table); http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/3e17a258/extras/indexing/src/test/java/mvm/rya/api/client/accumulo/AccumuloBatchUpdatePCJIT.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/test/java/mvm/rya/api/client/accumulo/AccumuloBatchUpdatePCJIT.java b/extras/indexing/src/test/java/mvm/rya/api/client/accumulo/AccumuloBatchUpdatePCJIT.java index f23f1c4..1f98f88 100644 --- a/extras/indexing/src/test/java/mvm/rya/api/client/accumulo/AccumuloBatchUpdatePCJIT.java +++ b/extras/indexing/src/test/java/mvm/rya/api/client/accumulo/AccumuloBatchUpdatePCJIT.java @@ -1,3 +1,21 @@ +/* + * 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. + */ package mvm.rya.api.client.accumulo; import static org.junit.Assert.assertEquals; http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/3e17a258/extras/indexing/src/test/java/mvm/rya/indexing/external/tupleSet/SimpleExternalTupleSetTest.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/test/java/mvm/rya/indexing/external/tupleSet/SimpleExternalTupleSetTest.java b/extras/indexing/src/test/java/mvm/rya/indexing/external/tupleSet/SimpleExternalTupleSetTest.java new file mode 100644 index 0000000..6354490 --- /dev/null +++ b/extras/indexing/src/test/java/mvm/rya/indexing/external/tupleSet/SimpleExternalTupleSetTest.java @@ -0,0 +1,173 @@ +/* + * 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. + */ +package mvm.rya.indexing.external.tupleSet; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertNotEquals; + +import java.util.HashMap; +import java.util.HashSet; +import java.util.Map; +import java.util.Set; + +import org.junit.Test; +import org.openrdf.query.MalformedQueryException; +import org.openrdf.query.algebra.Projection; +import org.openrdf.query.parser.ParsedQuery; +import org.openrdf.query.parser.sparql.SPARQLParser; + +/** + * Tests {@link SimpleExternalTupleSet}. + */ +public class SimpleExternalTupleSetTest { + + @Test + public void equals_equals() throws MalformedQueryException { + // The common PCJ expression. + final String sparql = + "SELECT ?f ?m ?d { " + + "?f <urn:talksTo> ?m . " + + "?m <uri:associatesWith> ?d . " + + "}"; + + final ParsedQuery query = new SPARQLParser().parseQuery(sparql, null); + final Projection pcjExpression = (Projection) query.getTupleExpr(); + + // Create two SimpleExternalTupleSet pbjects using the same expression. + final SimpleExternalTupleSet testSet = new SimpleExternalTupleSet(pcjExpression); + final SimpleExternalTupleSet identicalTestSet = new SimpleExternalTupleSet(pcjExpression); + + // Show that they are equal. + assertEquals(testSet, identicalTestSet); + } + + @Test + public void equals_notEquals() throws MalformedQueryException { + // Create the first SimpleExternalTupleSet object. + final String sparql1 = + "SELECT ?f ?m ?d { " + + "?f <urn:talksTo> ?m . " + + "?m <uri:associatesWith> ?d . " + + "}"; + + final ParsedQuery query1 = new SPARQLParser().parseQuery(sparql1, null); + final Projection pcjExpression1 = (Projection) query1.getTupleExpr(); + final SimpleExternalTupleSet set1 = new SimpleExternalTupleSet(pcjExpression1); + + // Create another one using a different expression. + final String sparql2 = + "SELECT ?f ?m ?d { " + + "?f <urn:talksTo> ?m . " + + "?m <uri:friendsWith> ?d . " + + "}"; + + final ParsedQuery query2 = new SPARQLParser().parseQuery(sparql2, null); + final Projection pcjExpression2 = (Projection) query2.getTupleExpr(); + final SimpleExternalTupleSet set2 = new SimpleExternalTupleSet(pcjExpression2); + + // Show they are not equal. + assertNotEquals(set1, set2); + } + + @Test + public void hashCode_same() throws MalformedQueryException { + // The common PCJ expression. + final String sparql = + "SELECT ?f ?m ?d { " + + "?f <urn:talksTo> ?m . " + + "?m <uri:associatesWith> ?d . " + + "}"; + + final ParsedQuery query = new SPARQLParser().parseQuery(sparql, null); + final Projection pcjExpression = (Projection) query.getTupleExpr(); + + // Create two SimpleExternalTupleSet pbjects using the same expression. + final SimpleExternalTupleSet testSet = new SimpleExternalTupleSet(pcjExpression); + final SimpleExternalTupleSet identicalTestSet = new SimpleExternalTupleSet(pcjExpression); + + // Show that they are equal. + assertEquals(testSet.hashCode(), identicalTestSet.hashCode()); + } + + public void hashCode_notSame() throws MalformedQueryException { + // Create the first SimpleExternalTupleSet object. + final String sparql1 = + "SELECT ?f ?m ?d { " + + "?f <urn:talksTo> ?m . " + + "?m <uri:associatesWith> ?d . " + + "}"; + + final ParsedQuery query1 = new SPARQLParser().parseQuery(sparql1, null); + final Projection pcjExpression1 = (Projection) query1.getTupleExpr(); + final SimpleExternalTupleSet set1 = new SimpleExternalTupleSet(pcjExpression1); + + // Create another one using a different expression. + final String sparql2 = + "SELECT ?f ?m ?d { " + + "?f <urn:talksTo> ?m . " + + "?m <uri:friendsWith> ?d . " + + "}"; + + final ParsedQuery query2 = new SPARQLParser().parseQuery(sparql2, null); + final Projection pcjExpression2 = (Projection) query2.getTupleExpr(); + final SimpleExternalTupleSet set2 = new SimpleExternalTupleSet(pcjExpression2); + + // Show they are not equal. + assertNotEquals(set1.hashCode(), set2.hashCode()); + } + + @Test + public void getSupportedVariableOrderMap() throws MalformedQueryException { + // Create the PCJ expression. + final String sparql = + "SELECT ?f ?m ?d { " + + "?f <urn:talksTo> ?m . " + + "?m <uri:associatesWith> ?d . " + + "}"; + + final ParsedQuery query = new SPARQLParser().parseQuery(sparql, null); + final Projection pcjExpression = (Projection) query.getTupleExpr(); + + // Create the object that is being tested. + final SimpleExternalTupleSet testSet = new SimpleExternalTupleSet(pcjExpression); + + // Verify the correct Supported Variable Order Map is created. + final Map<String, Set<String>> expected = new HashMap<>(); + + String varOrder = "f"; + Set<String> vars = new HashSet<>(); + vars.add("f"); + expected.put(varOrder, vars); + + varOrder = "f;m"; + vars = new HashSet<>(); + vars.add("f"); + vars.add("m"); + expected.put(varOrder, vars); + + varOrder = "f;m;d"; + vars = new HashSet<>(); + vars.add("f"); + vars.add("m"); + vars.add("d"); + expected.put(varOrder, vars); + + assertEquals(expected, testSet.getSupportedVariableOrderMap()); + } +} \ No newline at end of file http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/3e17a258/extras/rya.benchmark/src/main/java/org/apache/rya/benchmark/query/PCJOptimizerBenchmark.java ---------------------------------------------------------------------- diff --git a/extras/rya.benchmark/src/main/java/org/apache/rya/benchmark/query/PCJOptimizerBenchmark.java b/extras/rya.benchmark/src/main/java/org/apache/rya/benchmark/query/PCJOptimizerBenchmark.java new file mode 100644 index 0000000..ff6285b --- /dev/null +++ b/extras/rya.benchmark/src/main/java/org/apache/rya/benchmark/query/PCJOptimizerBenchmark.java @@ -0,0 +1,421 @@ +/** + * 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. + */ +package org.apache.rya.benchmark.query; + +import static com.google.common.base.Preconditions.checkArgument; +import static java.util.Objects.requireNonNull; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Objects; +import java.util.Queue; + +import javax.annotation.ParametersAreNonnullByDefault; + +import org.openjdk.jmh.annotations.Benchmark; +import org.openjdk.jmh.annotations.Param; +import org.openjdk.jmh.annotations.Scope; +import org.openjdk.jmh.annotations.Setup; +import org.openjdk.jmh.annotations.State; +import org.openjdk.jmh.runner.Runner; +import org.openjdk.jmh.runner.RunnerException; +import org.openjdk.jmh.runner.options.CommandLineOptionException; +import org.openjdk.jmh.runner.options.CommandLineOptions; +import org.openjdk.jmh.runner.options.OptionsBuilder; +import org.openrdf.query.MalformedQueryException; +import org.openrdf.query.algebra.Projection; +import org.openrdf.query.algebra.TupleExpr; +import org.openrdf.query.parser.sparql.SPARQLParser; + +import com.google.common.base.Joiner; +import com.google.common.collect.Lists; + +import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; +import mvm.rya.indexing.external.tupleSet.SimpleExternalTupleSet; +import mvm.rya.indexing.pcj.matching.PCJOptimizer; + +/** + * A benchmark that may be used to evaluate the performance of {@link PCJOptimizer}. + * It pivots over three dimensions: + * <ul> + * <li>How many Statement Patterns the optimized query has.</li> + * <li>How many PCJ indices the optimizer has available to it.</li> + * <li>How many Statement Patterns each PCJ has.</li> + * </ul> + * To execute this benchmark, build the project by executing: + * <pre> + * mvn clean install + * </pre> + * Transport the "target/benchmarking.jar" file to the system that will execute + * the benchmark, write the configuration file, and then execute: + * <pre> + * java -cp benchmarks.jar org.apache.rya.benchmark.query.PCJOptimizerBenchmark + * </pre> + */ +@State(Scope.Thread) +@ParametersAreNonnullByDefault +public class PCJOptimizerBenchmark { + + /** + * Variables that may be used when building SPARQL queries. + */ + private static final List<String> variables = Lists.newArrayList("?a","?b", + "?c","?d","?e","?f","?g","?h","?i","?j","?k","?l","?m","?n","?o", + "?p","?q","?r","?s","?t","?u","?v","?w","?x","?y","?z"); + + // Parameters that effect which PCJs are used by the benchmark. + @Param({"0", "1", "2", "3", "4", "5", "6"}) + public int numPCJs; + + @Param({"2", "3", "4", "5", "6"}) + public int pcjSPCount; + + // Parameters that effect the Query that is being optimized by the benchmark. + @Param({"1", "2", "3", "4", "5", "6"}) + public int querySPCount; + + // Cached benchmark data that is generated during the setup phase. + private final Map<BenchmarkParams, BenchmarkValues> chainedBenchmarkValues = new HashMap<>(); + private final Map<BenchmarkParams, BenchmarkValues> unchainedBenchmarkValues = new HashMap<>(); + + @Setup + public void buildBenchmarkValues() throws MalformedQueryException { + for(int numPCJs = 0; numPCJs <= 6; numPCJs++) { + for(int pcjSPCount = 2; pcjSPCount <= 6; pcjSPCount++) { + for(int querySPCount = 1; querySPCount <= 6; querySPCount++) { + final BenchmarkParams benchmarkParams = new BenchmarkParams(numPCJs, pcjSPCount, querySPCount); + + final BenchmarkValues chainedValues = new BenchmarkValues( + makeChainedQuery(benchmarkParams), + makeChainedPCJOptimizer(benchmarkParams)); + this.chainedBenchmarkValues.put(benchmarkParams, chainedValues); + + final BenchmarkValues unchainedValues = new BenchmarkValues( + makeUnchainedQuery(benchmarkParams), + makeUnchainedPCJOptimizer(benchmarkParams)); + this.unchainedBenchmarkValues.put(benchmarkParams, unchainedValues); + } + } + } + } + + @Benchmark + public void optimizeQuery_unchained() throws MalformedQueryException { + // Fetch the pieces that benchmark uses. + final BenchmarkValues values = unchainedBenchmarkValues.get( new BenchmarkParams(numPCJs, pcjSPCount, querySPCount) ); + final PCJOptimizer pcjOptimizer = values.getPCJOptimizer(); + final TupleExpr query = values.getQuery(); + + // Perform the optimization. + pcjOptimizer.optimize(query, null, null); + } + + @Benchmark + public void optimizeQuery_chained() throws MalformedQueryException { + // Fetch the pieces that benchmark uses. + final BenchmarkValues values = chainedBenchmarkValues.get( new BenchmarkParams(numPCJs, pcjSPCount, querySPCount) ); + final PCJOptimizer pcjOptimizer = values.getPCJOptimizer(); + final TupleExpr query = values.getQuery(); + + // Perform the optimization. + pcjOptimizer.optimize(query, null, null); + } + + private static TupleExpr makeUnchainedQuery(final BenchmarkParams params) throws MalformedQueryException { + final Queue<String> varQueue= Lists.newLinkedList(variables); + final SPARQLParser parser = new SPARQLParser(); + + final List<String> queryVars = new ArrayList<>(); + + // The first statement pattern has two variables. + queryVars.add( varQueue.remove() ); + queryVars.add( varQueue.remove() ); + + // The each extra statement pattern joins with the previous one, so only need one more variable each. + for(int i = 1; i < params.getQuerySPCount(); i++) { + queryVars.add( varQueue.remove() ); + queryVars.add( varQueue.remove() ); + } + + final String sparql = buildUnchainedSPARQL(queryVars); + return parser.parseQuery(sparql, null).getTupleExpr(); + } + + private static TupleExpr makeChainedQuery(final BenchmarkParams params) throws MalformedQueryException { + final Queue<String> varQueue= Lists.newLinkedList(variables); + final SPARQLParser parser = new SPARQLParser(); + + final List<String> queryVars = new ArrayList<>(); + + // The first statement pattern has two variables. + queryVars.add( varQueue.remove() ); + queryVars.add( varQueue.remove() ); + + // The each extra statement pattern joins with the previous one, so only need one more variable each. + for(int i = 1; i < params.getQuerySPCount(); i++) { + queryVars.add( varQueue.remove() ); + } + + final String sparql = buildChainedSPARQL(queryVars); + return parser.parseQuery(sparql, null).getTupleExpr(); + } + + private static PCJOptimizer makeUnchainedPCJOptimizer(final BenchmarkParams params) throws MalformedQueryException { + final Queue<String> varQueue= Lists.newLinkedList(variables); + final SPARQLParser parser = new SPARQLParser(); + + final List<ExternalTupleSet> indices = new ArrayList<>(); + + // Create the first PCJ. + final List<String> pcjVars = new ArrayList<>(); + pcjVars.add( varQueue.remove() ); + pcjVars.add( varQueue.remove() ); + + for(int spI = 1; spI < params.getPCJSPCount(); spI++) { + pcjVars.add( varQueue.remove() ); + pcjVars.add( varQueue.remove() ); + } + + String pcjSparql = buildUnchainedSPARQL(pcjVars); + Projection projection = (Projection) parser.parseQuery(pcjSparql, null).getTupleExpr(); + indices.add( new SimpleExternalTupleSet(projection) ); + + // Add the rest of the PCJs. + for(int pcjI = 1; pcjI < params.getNumPCJS(); pcjI++) { + // Remove the previous PCJs first variable. + pcjVars.remove(0); + pcjVars.remove(0); + + // And add a new one to the end of it. + pcjVars.add( varQueue.remove() ); + pcjVars.add( varQueue.remove() ); + + // Build the index. + pcjSparql = buildUnchainedSPARQL(pcjVars); + projection = (Projection) parser.parseQuery(pcjSparql, null).getTupleExpr(); + indices.add( new SimpleExternalTupleSet(projection) ); + } + + // Create the optimizer. + return new PCJOptimizer(indices, false); + } + + private static PCJOptimizer makeChainedPCJOptimizer(final BenchmarkParams params) throws MalformedQueryException { + final Queue<String> varQueue= Lists.newLinkedList(variables); + final SPARQLParser parser = new SPARQLParser(); + + final List<ExternalTupleSet> indices = new ArrayList<>(); + + // Create the first PCJ. + final List<String> pcjVars = new ArrayList<>(); + pcjVars.add( varQueue.remove() ); + pcjVars.add( varQueue.remove() ); + + for(int spI = 1; spI < params.getPCJSPCount(); spI++) { + pcjVars.add( varQueue.remove() ); + } + + String pcjSparql = buildChainedSPARQL(pcjVars); + Projection projection = (Projection) parser.parseQuery(pcjSparql, null).getTupleExpr(); + indices.add( new SimpleExternalTupleSet(projection) ); + + // Add the rest of the PCJs. + for(int pcjI = 1; pcjI < params.getNumPCJS(); pcjI++) { + // Remove the previous PCJs first variable. + pcjVars.remove(0); + + // And add a new one to the end of it. + pcjVars.add( varQueue.remove() ); + + // Build the index. + pcjSparql = buildChainedSPARQL(pcjVars); + projection = (Projection) parser.parseQuery(pcjSparql, null).getTupleExpr(); + indices.add( new SimpleExternalTupleSet(projection) ); + } + + // Create the optimizer. + return new PCJOptimizer(indices, false); + } + + private static String buildUnchainedSPARQL(final List<String> vars) { + checkArgument(vars.size() % 2 == 0); + + final Queue<String> varQueue= Lists.newLinkedList(vars); + final List<String> statementPatterns = new ArrayList<>(); + + // Create the first SP. + String var1 = varQueue.remove(); + String var2 = varQueue.remove(); + statementPatterns.add( var1 + " <urn:predicate> " + var2); + + // Need two more variables for every following statement pattern. + while(!varQueue.isEmpty()) { + var1 = varQueue.remove(); + var2 = varQueue.remove(); + statementPatterns.add( var1 + " <urn:predicate> " + var2); + } + + return "select " + Joiner.on(" ").join(vars) + " where { " + + Joiner.on(" . ").join(statementPatterns) + + " . }" ; + } + + private static String buildChainedSPARQL(final List<String> vars) { + final Queue<String> varQueue= Lists.newLinkedList(vars); + final List<String> statementPatterns = new ArrayList<>(); + + // Create the first SP. + final String var1 = varQueue.remove(); + final String var2 = varQueue.remove(); + statementPatterns.add( var1 + " <urn:predicate> " + var2); + + // Chain the rest of the SPs off of each other. + String lastVar = var2; + + while(!varQueue.isEmpty()) { + final String var = varQueue.remove(); + statementPatterns.add( lastVar + " <urn:predicate> " + var); + lastVar = var; + } + + // Build the SPARQL query from the pieces. + return "select " + Joiner.on(" ").join(vars) + " where { " + + Joiner.on(" . ").join(statementPatterns) + + " . }" ; + } + + /** + * The parameter values used by the benchmark. Used to lookup a benchmark' {@link BenchmarkValues}. + */ + @ParametersAreNonnullByDefault + public static class BenchmarkParams { + private final int numPCJs; + private final int pcjSPCount; + private final int querySPCount; + + /** + * Constructs an instance of {@link BenchmarkParams}. + * + * @param numPCJs - The number of PCJs that will be available to the {@link PCJOptimizer}. (not null) + * @param pcjSPCount - The number of Statement Patterns that are in each PCJs. (not null) + * @param querySPCount - The number of Statement Patterns that are in the query that will be optimized. (not null) + */ + public BenchmarkParams(final int numPCJs, final int pcjSPCount, final int querySPCount){ + this.numPCJs = numPCJs; + this.pcjSPCount = pcjSPCount; + this.querySPCount = querySPCount; + } + + /** + * @return The number of PCJs that will be available to the {@link PCJOptimizer}. + */ + public int getNumPCJS() { + return numPCJs; + } + + /** + * @return The number of Statement Patterns that are in each PCJs. + */ + public int getPCJSPCount() { + return pcjSPCount; + } + + /** + * @return The number of Statement Patterns that are in the query that will be optimized. + */ + public int getQuerySPCount() { + return querySPCount; + } + + @Override + public int hashCode() { + return Objects.hash(numPCJs, pcjSPCount, querySPCount); + } + + @Override + public boolean equals(final Object other) { + if(this == other) { + return true; + } + if(other instanceof BenchmarkParams) { + final BenchmarkParams key = (BenchmarkParams) other; + return numPCJs == key.numPCJs && + pcjSPCount == key.pcjSPCount && + querySPCount == key.querySPCount; + } + return false; + } + } + + /** + * Holds onto the SPARQL query that will be optimized as well as the optimizers + * that will be used to optimize the query. + */ + @ParametersAreNonnullByDefault + public static class BenchmarkValues { + private final TupleExpr query; + private final PCJOptimizer optimizer; + + /** + * Constructs an isntance of {@link BenchmarkValues}. + * + * @param query - The SPARQL query to optimize. + * @param optimizer - The optimizer used to optimize the query. + */ + public BenchmarkValues(final TupleExpr query, final PCJOptimizer optimizer) { + this.query = requireNonNull(query); + this.optimizer = requireNonNull(optimizer); + } + + /** + * @return The SPARQL query to optimize. + */ + public TupleExpr getQuery() { + return query; + } + + /** + * @return The optimizer used to optimize the query. + */ + public PCJOptimizer getPCJOptimizer() { + return optimizer; + } + } + + /** + * Runs the PCJOptimizer benchmarks. + * </p> + * Example command line: + * <pre> + * java -cp benchmarks.jar org.apache.rya.benchmark.query.PCJOptimizerBenchmark + * </pre> + * + * @param args - The command line arguments that will be fed into the benchmark. + * @throws Exception The benchmark could not be run. + */ + public static void main(final String[] args) throws RunnerException, MalformedQueryException, CommandLineOptionException { + final OptionsBuilder opts = new OptionsBuilder(); + opts.parent( new CommandLineOptions(args) ); + opts.include(PCJOptimizerBenchmark.class.getSimpleName()); + + new Runner(opts.build()).run(); + } +} \ No newline at end of file
