http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/c12f58f4/extras/indexing/src/test/java/mvm/rya/indexing/IndexPlanValidator/ThreshholdPlanSelectorTest.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/test/java/mvm/rya/indexing/IndexPlanValidator/ThreshholdPlanSelectorTest.java b/extras/indexing/src/test/java/mvm/rya/indexing/IndexPlanValidator/ThreshholdPlanSelectorTest.java index f8da365..3bc895e 100644 --- a/extras/indexing/src/test/java/mvm/rya/indexing/IndexPlanValidator/ThreshholdPlanSelectorTest.java +++ b/extras/indexing/src/test/java/mvm/rya/indexing/IndexPlanValidator/ThreshholdPlanSelectorTest.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,19 +19,16 @@ package mvm.rya.indexing.IndexPlanValidator; * under the License. */ - import java.util.ArrayList; import java.util.Iterator; import java.util.List; -import java.util.Set; -import junit.framework.Assert; -import mvm.rya.indexing.external.ExternalProcessor; +import mvm.rya.indexing.external.PrecompJoinOptimizer; import mvm.rya.indexing.external.tupleSet.ExternalTupleSet; import mvm.rya.indexing.external.tupleSet.SimpleExternalTupleSet; +import org.junit.Assert; import org.junit.Test; -import org.openrdf.query.algebra.Filter; import org.openrdf.query.algebra.Projection; import org.openrdf.query.algebra.QueryModelNode; import org.openrdf.query.algebra.StatementPattern; @@ -42,797 +39,675 @@ import org.openrdf.query.parser.ParsedQuery; import org.openrdf.query.parser.sparql.SPARQLParser; import com.beust.jcommander.internal.Lists; -import com.google.common.collect.Sets; public class ThreshholdPlanSelectorTest { - private String q7 = ""// - + "SELECT ?s ?t ?u " // - + "{" // - + " ?s a ?t ."// - + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// - + " ?u <uri:talksTo> ?s . "// - + "}";// - - private String q8 = ""// - + "SELECT ?e ?l ?c " // - + "{" // - + " ?e a ?l ."// - + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// - + " ?c <uri:talksTo> ?e . "// - + "}";// - - private String q9 = ""// - + "SELECT ?f ?m ?d " // - + "{" // - + " ?f a ?m ."// - + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + " ?d <uri:talksTo> ?f . "// - + "}";// - - - - - private String q15 = ""// - + "SELECT ?f ?m ?d ?e ?l ?c " // - + "{" // - + " ?f a ?m ."// - + " ?e a ?l ."// - + " ?d <uri:talksTo> ?f . "// - + " ?c <uri:talksTo> ?e . "// - + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// - + "}";// - - private String q16 = ""// - + "SELECT ?f ?m ?d ?e ?l " // - + "{" // - + " ?d <uri:talksTo> ?f . "// - + " ?d <uri:talksTo> ?e . "// - + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + "}";// - - private String q17 = ""// - + "SELECT ?chicken ?dog ?cat " // - + "{" // - + " ?chicken <uri:talksTo> ?dog . "// - + " ?cat <http://www.w3.org/2000/01/rdf-schema#label> ?chicken ."// - + "}";// - - private String q18 = ""// - + "SELECT ?dog ?chicken " // - + "{" // - + " ?chicken <uri:talksTo> ?dog . "// - + "}";// - - private String q19 = ""// - + "SELECT ?cat ?chicken " // - + "{" // - + " ?cat <http://www.w3.org/2000/01/rdf-schema#label> ?chicken ."// - + "}";// - - - private String q20 = ""// - + "SELECT ?f ?m ?d ?e ?l ?c " // - + "{" // - + " ?f a ?m ."// - + " ?e a ?l ."// - + " ?d <uri:talksTo> ?f . "// - + " ?c <uri:talksTo> ?e . "// - + " ?m <uri:talksTo> ?e . "// - + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// - + "}";// - - - - private String q21 = ""// - + "SELECT ?u ?s ?t " // - + "{" // - + " ?s a ?t ."// - + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// - + " ?u <uri:talksTo> ?s . "// - + "}";// - - - - @Test - public void testSingleIndex() throws Exception { - - SPARQLParser parser = new SPARQLParser(); - - - ParsedQuery pq1 = parser.parseQuery(q15, null); - ParsedQuery pq2 = parser.parseQuery(q7, null); - ParsedQuery pq3 = parser.parseQuery(q8, null); - ParsedQuery pq4 = parser.parseQuery(q9, null); - //ParsedQuery pq3 = parser.parseQuery(q12, null); - - SimpleExternalTupleSet extTup1 = new SimpleExternalTupleSet((Projection) pq2.getTupleExpr()); - SimpleExternalTupleSet extTup2 = new SimpleExternalTupleSet((Projection) pq3.getTupleExpr()); - SimpleExternalTupleSet extTup3 = new SimpleExternalTupleSet((Projection) pq4.getTupleExpr()); - - List<ExternalTupleSet> list = new ArrayList<ExternalTupleSet>(); - - list.add(extTup1); - - List<QueryModelNode> optTupNodes = Lists.newArrayList(); - optTupNodes.add(extTup2); - optTupNodes.add(extTup3); - - IndexedExecutionPlanGenerator iep = new IndexedExecutionPlanGenerator(pq1.getTupleExpr(), list); - - Iterator<TupleExpr> plans = (new TupleExecutionPlanGenerator()).getPlans(iep.getIndexedTuples()); - - IndexPlanValidator ipv = new IndexPlanValidator(false); - - Iterator<TupleExpr> validPlans = ipv.getValidTuples(plans); - - ThreshholdPlanSelector tps = new ThreshholdPlanSelector(pq1.getTupleExpr()); - - TupleExpr optimalTup = tps.getThreshholdQueryPlan(validPlans, .1, 1, 0, 0); - - NodeCollector nc = new NodeCollector(); - optimalTup.visit(nc); - - List<QueryModelNode> qNodes = nc.getNodes(); - - - Assert.assertEquals(qNodes.size(), optTupNodes.size()); - for(QueryModelNode node: qNodes) { - Assert.assertTrue(optTupNodes.contains(node)); - } - - - } - - - - - - @Test - public void testSingleIndex2() throws Exception { - - String q1 = ""// - + "SELECT ?f ?m ?d ?e ?l ?c " // - + "{" // - + " ?f a ?m ."// - + " ?c a ?l ."// - + " ?d <uri:talksTo> ?f . "// - + " ?e <uri:talksTo> ?c . "// - + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?e ."// - + " ?m <uri:talksTo> ?e . "// - + "}";// - - String q2 = ""// - + "SELECT ?u ?s ?t " // - + "{" // - + " ?s a ?t ."// - + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// - + " ?u <uri:talksTo> ?s . "// - + "}";// - - String q3 = ""// - + "SELECT ?e ?c ?l " // - + "{" // - + " ?c a ?l ."// - + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?e ."// - + " ?e <uri:talksTo> ?c . "// - + "}";// - - String q4 = ""// - + "SELECT ?d ?f ?m " // - + "{" // - + " ?f a ?m ."// - + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + " ?d <uri:talksTo> ?f . "// - + "}";// - - SPARQLParser parser = new SPARQLParser(); - - ParsedQuery pq1 = parser.parseQuery(q1, null); - ParsedQuery pq2 = parser.parseQuery(q2, null); - ParsedQuery pq3 = parser.parseQuery(q3, null); - ParsedQuery pq4 = parser.parseQuery(q4, null); - - SimpleExternalTupleSet extTup1 = new SimpleExternalTupleSet((Projection) pq2.getTupleExpr()); - SimpleExternalTupleSet extTup2 = new SimpleExternalTupleSet((Projection) pq3.getTupleExpr()); - SimpleExternalTupleSet extTup3 = new SimpleExternalTupleSet((Projection) pq4.getTupleExpr()); - - List<ExternalTupleSet> list = new ArrayList<ExternalTupleSet>(); - - list.add(extTup1); - - List<StatementPattern> spList = StatementPatternCollector.process(pq1.getTupleExpr()); - List<QueryModelNode> optTupNodes = Lists.newArrayList(); - optTupNodes.add(extTup3); - optTupNodes.add(spList.get(6)); - optTupNodes.add(extTup2); - - IndexedExecutionPlanGenerator iep = new IndexedExecutionPlanGenerator(pq1.getTupleExpr(), list); - - Iterator<TupleExpr> plans = (new TupleExecutionPlanGenerator()).getPlans(iep.getIndexedTuples()); - - //System.out.println("Size is " + plans.size()); - // System.out.println("Plans are " + plans); - - IndexPlanValidator ipv = new IndexPlanValidator(true); - Iterator<TupleExpr> validPlans = ipv.getValidTuples(plans); - - //System.out.println("Valid plan size is " + validPlans.size()); - // System.out.println("Valid plans are " + validPlans); - - ThreshholdPlanSelector tps = new ThreshholdPlanSelector(pq1.getTupleExpr()); - - TupleExpr optimalTup = tps.getThreshholdQueryPlan(validPlans, .4, .7, .1, .2); - - NodeCollector nc = new NodeCollector(); - optimalTup.visit(nc); - - //System.out.println("Optimal plan is " + optimalTup); - - List<QueryModelNode> qNodes = nc.getNodes(); - //System.out.println("Returned list is " + qNodes + " and comp list is " + optTupNodes); - - Assert.assertTrue(qNodes.equals(optTupNodes)); - - } - - - - - - - - - @Test - public void testTwoIndex() throws Exception { - - String q1 = ""// - + "SELECT ?f ?m ?d ?h ?i " // - + "{" // - + " ?f a ?m ."// - + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + " ?d <uri:talksTo> ?f . "// - + " ?d <uri:hangOutWith> ?f ." // - + " ?f <uri:hangOutWith> ?h ." // - + " ?f <uri:associatesWith> ?i ." // - + " ?i <uri:associatesWith> ?h ." // - + "}";// - - 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 ?m ?f ?d " // - + "{" // - + " ?f a ?m ."// - + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + " ?d <uri:talksTo> ?f . "// - + "}";// - - - String q6 = ""// - + "SELECT ?d ?f ?h " // - + "{" // - + " ?d <uri:hangOutWith> ?f ." // - + " ?f <uri:hangOutWith> ?h ." // - + "}";// - - String q7 = ""// - + "SELECT ?f ?i ?h " // - + "{" // - + " ?f <uri:associatesWith> ?i ." // - + " ?i <uri:associatesWith> ?h ." // - + "}";// - - - - - - - SPARQLParser parser = new SPARQLParser(); - - ParsedQuery pq1 = parser.parseQuery(q1, null); - ParsedQuery pq2 = parser.parseQuery(q2, null); - ParsedQuery pq3 = parser.parseQuery(q3, null); - ParsedQuery pq4 = parser.parseQuery(q4, null); - ParsedQuery pq5 = parser.parseQuery(q5, null); - ParsedQuery pq6 = parser.parseQuery(q6, null); - ParsedQuery pq7 = parser.parseQuery(q7, null); - - SimpleExternalTupleSet extTup1 = new SimpleExternalTupleSet((Projection) pq2.getTupleExpr()); - SimpleExternalTupleSet extTup2 = new SimpleExternalTupleSet((Projection) pq3.getTupleExpr()); - SimpleExternalTupleSet extTup3 = new SimpleExternalTupleSet((Projection) pq4.getTupleExpr()); - SimpleExternalTupleSet extTup4 = new SimpleExternalTupleSet((Projection) pq5.getTupleExpr()); - SimpleExternalTupleSet extTup5 = new SimpleExternalTupleSet((Projection) pq6.getTupleExpr()); - SimpleExternalTupleSet extTup6 = new SimpleExternalTupleSet((Projection) pq7.getTupleExpr()); - - - - - List<ExternalTupleSet> list = new ArrayList<ExternalTupleSet>(); - - list.add(extTup2); - list.add(extTup1); - list.add(extTup3); - - List<QueryModelNode> optTupNodes = Lists.newArrayList(); - optTupNodes.add(extTup4); - optTupNodes.add(extTup6); - optTupNodes.add(extTup5); - - IndexedExecutionPlanGenerator iep = new IndexedExecutionPlanGenerator(pq1.getTupleExpr(), list); - - Iterator<TupleExpr> plans = (new TupleExecutionPlanGenerator()).getPlans(iep.getIndexedTuples()); - IndexPlanValidator ipv = new IndexPlanValidator(true); - Iterator<TupleExpr> validPlans = ipv.getValidTuples(plans); - - ThreshholdPlanSelector tps = new ThreshholdPlanSelector(pq1.getTupleExpr()); - TupleExpr optimalTup = tps.getThreshholdQueryPlan(validPlans, .2, .6, .4, 0); - - NodeCollector nc = new NodeCollector(); - optimalTup.visit(nc); - - List<QueryModelNode> qNodes = nc.getNodes(); - - Assert.assertTrue(qNodes.equals(optTupNodes)); - - } - - - - - @Test - public void largeQueryFourtyIndexTest() { - - - String q1 = ""// - + "SELECT ?f ?m ?d ?e ?l ?c ?n ?o ?p ?a ?h ?r " // - + "{" // - + " ?f a ?m ."// - + " ?e a ?l ."// - + " ?n a ?o ."// - + " ?a a ?h ."// - + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// - + " ?o <http://www.w3.org/2000/01/rdf-schema#label> ?p ."// - + " ?h <http://www.w3.org/2000/01/rdf-schema#label> ?r ."// - + " ?d <uri:talksTo> ?f . "// - + " ?c <uri:talksTo> ?e . "// - + " ?p <uri:talksTo> ?n . "// - + " ?r <uri:talksTo> ?a . "// - + "}";// - - - String q2 = ""// - + "SELECT ?s ?t ?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 ?d ?f ?g " // - + "{" // - + " ?s a ?t ."// - + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// - + " ?u <uri:talksTo> ?s . "// - + " ?d a ?f ."// - + " ?f <http://www.w3.org/2000/01/rdf-schema#label> ?g ."// - + " ?g <uri:talksTo> ?d . "// - + "}";// - - - - String q4 = ""// - + "SELECT ?s ?t ?u ?d ?f ?g ?a ?b ?c" // - + "{" // - + " ?s a ?t ."// - + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// - + " ?u <uri:talksTo> ?s . "// - + " ?d a ?f ."// - + " ?f <http://www.w3.org/2000/01/rdf-schema#label> ?g ."// - + " ?g <uri:talksTo> ?d . "// - + " ?a a ?b ."// - + " ?b <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// - + " ?c <uri:talksTo> ?a . "// - + "}";// - - - String q5 = ""// - + "SELECT ?f ?m ?d ?a ?h ?r " // - + "{" // - + " ?f a ?m ."// - + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + " ?d <uri:talksTo> ?f . "// - + " ?a a ?h ."// - + " ?h <http://www.w3.org/2000/01/rdf-schema#label> ?r ."// - + " ?r <uri:talksTo> ?a . "// - + "}";// - - String q6 = ""// - + "SELECT ?e ?l ?c " // - + "{" // - + " ?e a ?l ."// - + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// - + " ?c <uri:talksTo> ?e . "// - + "}";// - - String q7 = ""// - + "SELECT ?n ?o ?p " // - + "{" // - + " ?n a ?o ."// - + " ?o <http://www.w3.org/2000/01/rdf-schema#label> ?p ."// - + " ?p <uri:talksTo> ?n . "// - + "}";// - - - - - - 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; - - - 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); - - } catch (Exception e) { - e.printStackTrace(); - } - - SimpleExternalTupleSet extTup1 = new SimpleExternalTupleSet((Projection) pq2.getTupleExpr()); - SimpleExternalTupleSet extTup2 = new SimpleExternalTupleSet((Projection) pq3.getTupleExpr()); - SimpleExternalTupleSet extTup3 = new SimpleExternalTupleSet((Projection) pq4.getTupleExpr()); - - SimpleExternalTupleSet extTup4 = new SimpleExternalTupleSet((Projection) pq5.getTupleExpr()); - SimpleExternalTupleSet extTup5 = new SimpleExternalTupleSet((Projection) pq6.getTupleExpr()); - SimpleExternalTupleSet extTup6 = new SimpleExternalTupleSet((Projection) pq7.getTupleExpr()); - - List<ExternalTupleSet> list = new ArrayList<ExternalTupleSet>(); - - list.add(extTup2); - list.add(extTup1); - list.add(extTup3); - - List<ExternalTupleSet> list2 = new ArrayList<ExternalTupleSet>(); - - list2.add(extTup4); - list2.add(extTup5); - list2.add(extTup6); - - IndexedExecutionPlanGenerator iep = new IndexedExecutionPlanGenerator(pq1.getTupleExpr(), list); - - Iterator<TupleExpr> plans = (new TupleExecutionPlanGenerator()).getPlans(iep.getIndexedTuples()); - IndexPlanValidator ipv = new IndexPlanValidator(false); - Iterator<TupleExpr> validPlans = ipv.getValidTuples(plans); - - ThreshholdPlanSelector tps = new ThreshholdPlanSelector(pq1.getTupleExpr()); - TupleExpr optimalTup = tps.getThreshholdQueryPlan(validPlans, .4, .8, .1, .1); - - NodeCollector nc = new NodeCollector(); - optimalTup.visit(nc); - - - - } - - - - - - - - - @Test - public void twoIndexFilterTest() { - - - String q1 = ""// - + "SELECT ?f ?m ?d ?e ?l ?c " // - + "{" // - + " Filter(?f > \"5\")." // - + " Filter(?e > \"5\")." // - + " ?f a ?m ."// - + " ?e a ?l ."// - + " ?d <uri:talksTo> ?f . "// - + " ?c <uri:talksTo> ?e . "// - + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// - + "}";// - - - String q2 = ""// - + "SELECT ?s ?t ?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 " // - + "{" // - + " Filter(?s > \"5\") ."// - + " ?s a ?t ."// - + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// - + " ?u <uri:talksTo> ?s . "// - + "}";// - - - - String q4 = ""// - + "SELECT ?f ?m ?d " // - + "{" // - + " Filter(?f > \"5\") ."// - + " ?f a ?m ."// - + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + " ?d <uri:talksTo> ?f . "// - + "}";// - - - String q5 = ""// - + "SELECT ?e ?l ?c " // - + "{" // - + " Filter(?e > \"5\") ."// - + " ?e a ?l ."// - + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// - + " ?c <uri:talksTo> ?e . "// - + "}";// - - - - - SPARQLParser parser = new SPARQLParser(); - - ParsedQuery pq1 = null; - ParsedQuery pq2 = null; - ParsedQuery pq3 = null; - ParsedQuery pq4 = null; - ParsedQuery pq5 = 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); - - - } catch (Exception e) { - e.printStackTrace(); - } - - SimpleExternalTupleSet extTup1 = new SimpleExternalTupleSet((Projection) pq2.getTupleExpr()); - SimpleExternalTupleSet extTup2 = new SimpleExternalTupleSet((Projection) pq3.getTupleExpr()); - SimpleExternalTupleSet extTup3 = new SimpleExternalTupleSet((Projection) pq4.getTupleExpr()); - SimpleExternalTupleSet extTup4 = new SimpleExternalTupleSet((Projection) pq5.getTupleExpr()); - - List<ExternalTupleSet> list = new ArrayList<ExternalTupleSet>(); - - list.add(extTup2); - list.add(extTup1); - - List<ExternalTupleSet> list2 = new ArrayList<ExternalTupleSet>(); - - list2.add(extTup3); - list2.add(extTup4); - - IndexedExecutionPlanGenerator iep = new IndexedExecutionPlanGenerator(pq1.getTupleExpr(), list); - - Iterator<TupleExpr> plans = (new TupleExecutionPlanGenerator()).getPlans(iep.getIndexedTuples()); - IndexPlanValidator ipv = new IndexPlanValidator(false); - Iterator<TupleExpr> validPlans = ipv.getValidTuples(plans); - - ThreshholdPlanSelector tps = new ThreshholdPlanSelector(pq1.getTupleExpr()); - TupleExpr optimalTup = tps.getThreshholdQueryPlan(validPlans, .4, .8, .1, .1); - - NodeCollector nc = new NodeCollector(); - optimalTup.visit(nc); - - Assert.assertEquals(nc.getNodes().size(), list2.size()); - - for(QueryModelNode e: nc.getNodes()) { - Assert.assertTrue(list2.contains((ExternalTupleSet)e)); - } - - - - } - - - - - - - - - - @Test - public void testCost1() throws Exception { - - String q1 = ""// - + "SELECT ?f ?m ?d ?h ?i " // - + "{" // - + " ?f a ?m ."// - + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + " ?d <uri:talksTo> ?f . "// - + " ?d <uri:hangOutWith> ?f ." // - + " ?f <uri:hangOutWith> ?h ." // - + " ?f <uri:associatesWith> ?i ." // - + " ?i <uri:associatesWith> ?h ." // - + "}";// - - - SPARQLParser parser = new SPARQLParser(); - - ParsedQuery pq1 = parser.parseQuery(q1, null); - - ThreshholdPlanSelector tps = new ThreshholdPlanSelector(pq1.getTupleExpr()); - double cost = tps.getCost(pq1.getTupleExpr(), .6, .4, 0); - Assert.assertEquals(.7,cost); - - } - - - - - @Test - public void testCost2() throws Exception { - - String q1 = ""// - + "SELECT ?f ?m ?d ?e ?l ?c " // - + "{" // - + " ?f a ?m ."// - + " ?e a ?l ."// - + " ?d <uri:talksTo> ?f . "// - + " ?c <uri:talksTo> ?e . "// - + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// - + "}";// - - - SPARQLParser parser = new SPARQLParser(); - - ParsedQuery pq1 = parser.parseQuery(q1, null); - - ThreshholdPlanSelector tps = new ThreshholdPlanSelector(pq1.getTupleExpr()); - double cost = tps.getCost(pq1.getTupleExpr(), .4, .3, .3); - Assert.assertEquals(.58,cost, .000000001); - - } - - - - - - @Test - public void testCost3() throws Exception { - - String q1 = ""// - + "SELECT ?f ?m ?d ?e ?l ?c " // - + "{" // - + " Filter(?f > \"5\")." // - + " Filter(?e > \"6\")." // - + " ?f a ?m ."// - + " ?e a ?l ."// - + " ?d <uri:talksTo> ?f . "// - + " ?c <uri:talksTo> ?e . "// - + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// - + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// - + "}";// - - - String q2 = ""// - + "SELECT ?s ?t ?u " // - + "{" // - + " ?s a ?t ."// - + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// - + " ?u <uri:talksTo> ?s . "// - + "}";// - - - SPARQLParser parser = new SPARQLParser(); - - ParsedQuery pq1 = parser.parseQuery(q1, null); - ParsedQuery pq2 = parser.parseQuery(q2, null); - - SimpleExternalTupleSet sep = new SimpleExternalTupleSet((Projection) pq2.getTupleExpr()); - List<ExternalTupleSet> eList = Lists.newArrayList(); - - eList.add(sep); - ExternalProcessor ep = new ExternalProcessor(eList); - - TupleExpr te = pq1.getTupleExpr(); - te = ep.process(te); - - - - ThreshholdPlanSelector tps = new ThreshholdPlanSelector(pq1.getTupleExpr()); - double cost = tps.getCost(te, .4, .3, .3); - Assert.assertEquals(.575,cost); - - - } - - - - - - - - - - public static class NodeCollector extends QueryModelVisitorBase<RuntimeException> { - - List<QueryModelNode> qNodes = Lists.newArrayList(); - - - public List<QueryModelNode> getNodes() { - return qNodes; - } - - - - @Override - public void meetNode(QueryModelNode node) { - if(node instanceof StatementPattern || node instanceof ExternalTupleSet) { - qNodes.add(node); - } - super.meetNode(node); - - } - - - } - - - - + private String q7 = ""// + + "SELECT ?s ?t ?u " // + + "{" // + + " ?s a ?t ."// + + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + + " ?u <uri:talksTo> ?s . "// + + "}";// + + private String q8 = ""// + + "SELECT ?e ?l ?c " // + + "{" // + + " ?e a ?l ."// + + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// + + " ?c <uri:talksTo> ?e . "// + + "}";// + + private String q9 = ""// + + "SELECT ?f ?m ?d " // + + "{" // + + " ?f a ?m ."// + + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// + + " ?d <uri:talksTo> ?f . "// + + "}";// + + private String q15 = ""// + + "SELECT ?f ?m ?d ?e ?l ?c " // + + "{" // + + " ?f a ?m ."// + + " ?e a ?l ."// + + " ?d <uri:talksTo> ?f . "// + + " ?c <uri:talksTo> ?e . "// + + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// + + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// + + "}";// + + @Test + public void testSingleIndex() throws Exception { + + SPARQLParser parser = new SPARQLParser(); + + ParsedQuery pq1 = parser.parseQuery(q15, null); + ParsedQuery pq2 = parser.parseQuery(q7, null); + ParsedQuery pq3 = parser.parseQuery(q8, null); + ParsedQuery pq4 = parser.parseQuery(q9, null); + + SimpleExternalTupleSet extTup1 = new SimpleExternalTupleSet( + (Projection) pq2.getTupleExpr()); + SimpleExternalTupleSet extTup2 = new SimpleExternalTupleSet( + (Projection) pq3.getTupleExpr()); + SimpleExternalTupleSet extTup3 = new SimpleExternalTupleSet( + (Projection) pq4.getTupleExpr()); + + List<ExternalTupleSet> list = new ArrayList<ExternalTupleSet>(); + + list.add(extTup1); + + List<QueryModelNode> optTupNodes = Lists.newArrayList(); + optTupNodes.add(extTup2); + optTupNodes.add(extTup3); + + IndexedExecutionPlanGenerator iep = new IndexedExecutionPlanGenerator( + pq1.getTupleExpr(), list); + + Iterator<TupleExpr> plans = new TupleExecutionPlanGenerator() + .getPlans(iep.getIndexedTuples()); + + IndexPlanValidator ipv = new IndexPlanValidator(false); + + Iterator<TupleExpr> validPlans = ipv.getValidTuples(plans); + + ThreshholdPlanSelector tps = new ThreshholdPlanSelector( + pq1.getTupleExpr()); + + TupleExpr optimalTup = tps.getThreshholdQueryPlan(validPlans, .1, 1, 0, + 0); + + NodeCollector nc = new NodeCollector(); + optimalTup.visit(nc); + + List<QueryModelNode> qNodes = nc.getNodes(); + + Assert.assertEquals(qNodes.size(), optTupNodes.size()); + for (QueryModelNode node : qNodes) { + Assert.assertTrue(optTupNodes.contains(node)); + } + + } + + @Test + public void testSingleIndex2() throws Exception { + + String q1 = ""// + + "SELECT ?f ?m ?d ?e ?l ?c " // + + "{" // + + " ?f a ?m ."// + + " ?c a ?l ."// + + " ?d <uri:talksTo> ?f . "// + + " ?e <uri:talksTo> ?c . "// + + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// + + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?e ."// + + " ?m <uri:talksTo> ?e . "// + + "}";// + + String q2 = ""// + + "SELECT ?u ?s ?t " // + + "{" // + + " ?s a ?t ."// + + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + + " ?u <uri:talksTo> ?s . "// + + "}";// + + String q3 = ""// + + "SELECT ?e ?c ?l " // + + "{" // + + " ?c a ?l ."// + + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?e ."// + + " ?e <uri:talksTo> ?c . "// + + "}";// + + String q4 = ""// + + "SELECT ?d ?f ?m " // + + "{" // + + " ?f a ?m ."// + + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// + + " ?d <uri:talksTo> ?f . "// + + "}";// + + SPARQLParser parser = new SPARQLParser(); + + ParsedQuery pq1 = parser.parseQuery(q1, null); + ParsedQuery pq2 = parser.parseQuery(q2, null); + ParsedQuery pq3 = parser.parseQuery(q3, null); + ParsedQuery pq4 = parser.parseQuery(q4, null); + + SimpleExternalTupleSet extTup1 = new SimpleExternalTupleSet( + (Projection) pq2.getTupleExpr()); + SimpleExternalTupleSet extTup2 = new SimpleExternalTupleSet( + (Projection) pq3.getTupleExpr()); + SimpleExternalTupleSet extTup3 = new SimpleExternalTupleSet( + (Projection) pq4.getTupleExpr()); + + List<ExternalTupleSet> list = new ArrayList<ExternalTupleSet>(); + + list.add(extTup1); + + List<StatementPattern> spList = StatementPatternCollector.process(pq1 + .getTupleExpr()); + List<QueryModelNode> optTupNodes = Lists.newArrayList(); + optTupNodes.add(extTup3); + optTupNodes.add(spList.get(6)); + optTupNodes.add(extTup2); + + IndexedExecutionPlanGenerator iep = new IndexedExecutionPlanGenerator( + pq1.getTupleExpr(), list); + + Iterator<TupleExpr> plans = new TupleExecutionPlanGenerator() + .getPlans(iep.getIndexedTuples()); + + IndexPlanValidator ipv = new IndexPlanValidator(true); + Iterator<TupleExpr> validPlans = ipv.getValidTuples(plans); + + ThreshholdPlanSelector tps = new ThreshholdPlanSelector( + pq1.getTupleExpr()); + + TupleExpr optimalTup = tps.getThreshholdQueryPlan(validPlans, .4, .7, + .1, .2); + + NodeCollector nc = new NodeCollector(); + optimalTup.visit(nc); + + List<QueryModelNode> qNodes = nc.getNodes(); + + Assert.assertTrue(qNodes.equals(optTupNodes)); + + } + + @Test + public void testTwoIndex() throws Exception { + + String q1 = ""// + + "SELECT ?f ?m ?d ?h ?i " // + + "{" // + + " ?f a ?m ."// + + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// + + " ?d <uri:talksTo> ?f . "// + + " ?d <uri:hangOutWith> ?f ." // + + " ?f <uri:hangOutWith> ?h ." // + + " ?f <uri:associatesWith> ?i ." // + + " ?i <uri:associatesWith> ?h ." // + + "}";// + + 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 ?m ?f ?d " // + + "{" // + + " ?f a ?m ."// + + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// + + " ?d <uri:talksTo> ?f . "// + + "}";// + + String q6 = ""// + + "SELECT ?d ?f ?h " // + + "{" // + + " ?d <uri:hangOutWith> ?f ." // + + " ?f <uri:hangOutWith> ?h ." // + + "}";// + + String q7 = ""// + + "SELECT ?f ?i ?h " // + + "{" // + + " ?f <uri:associatesWith> ?i ." // + + " ?i <uri:associatesWith> ?h ." // + + "}";// + + SPARQLParser parser = new SPARQLParser(); + + ParsedQuery pq1 = parser.parseQuery(q1, null); + ParsedQuery pq2 = parser.parseQuery(q2, null); + ParsedQuery pq3 = parser.parseQuery(q3, null); + ParsedQuery pq4 = parser.parseQuery(q4, null); + ParsedQuery pq5 = parser.parseQuery(q5, null); + ParsedQuery pq6 = parser.parseQuery(q6, null); + ParsedQuery pq7 = parser.parseQuery(q7, null); + + SimpleExternalTupleSet extTup1 = new SimpleExternalTupleSet( + (Projection) pq2.getTupleExpr()); + SimpleExternalTupleSet extTup2 = new SimpleExternalTupleSet( + (Projection) pq3.getTupleExpr()); + SimpleExternalTupleSet extTup3 = new SimpleExternalTupleSet( + (Projection) pq4.getTupleExpr()); + SimpleExternalTupleSet extTup4 = new SimpleExternalTupleSet( + (Projection) pq5.getTupleExpr()); + SimpleExternalTupleSet extTup5 = new SimpleExternalTupleSet( + (Projection) pq6.getTupleExpr()); + SimpleExternalTupleSet extTup6 = new SimpleExternalTupleSet( + (Projection) pq7.getTupleExpr()); + + List<ExternalTupleSet> list = new ArrayList<ExternalTupleSet>(); + + list.add(extTup2); + list.add(extTup1); + list.add(extTup3); + + List<QueryModelNode> optTupNodes = Lists.newArrayList(); + optTupNodes.add(extTup4); + optTupNodes.add(extTup6); + optTupNodes.add(extTup5); + + IndexedExecutionPlanGenerator iep = new IndexedExecutionPlanGenerator( + pq1.getTupleExpr(), list); + + Iterator<TupleExpr> plans = new TupleExecutionPlanGenerator() + .getPlans(iep.getIndexedTuples()); + IndexPlanValidator ipv = new IndexPlanValidator(true); + Iterator<TupleExpr> validPlans = ipv.getValidTuples(plans); + + ThreshholdPlanSelector tps = new ThreshholdPlanSelector( + pq1.getTupleExpr()); + TupleExpr optimalTup = tps.getThreshholdQueryPlan(validPlans, .2, .6, + .4, 0); + + NodeCollector nc = new NodeCollector(); + optimalTup.visit(nc); + + List<QueryModelNode> qNodes = nc.getNodes(); + + Assert.assertTrue(qNodes.equals(optTupNodes)); + + } + + @Test + public void largeQueryFourtyIndexTest() { + + String q1 = ""// + + "SELECT ?f ?m ?d ?e ?l ?c ?n ?o ?p ?a ?h ?r " // + + "{" // + + " ?f a ?m ."// + + " ?e a ?l ."// + + " ?n a ?o ."// + + " ?a a ?h ."// + + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// + + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// + + " ?o <http://www.w3.org/2000/01/rdf-schema#label> ?p ."// + + " ?h <http://www.w3.org/2000/01/rdf-schema#label> ?r ."// + + " ?d <uri:talksTo> ?f . "// + + " ?c <uri:talksTo> ?e . "// + + " ?p <uri:talksTo> ?n . "// + + " ?r <uri:talksTo> ?a . "// + + "}";// + + String q2 = ""// + + "SELECT ?s ?t ?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 ?d ?f ?g " // + + "{" // + + " ?s a ?t ."// + + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + + " ?u <uri:talksTo> ?s . "// + + " ?d a ?f ."// + + " ?f <http://www.w3.org/2000/01/rdf-schema#label> ?g ."// + + " ?g <uri:talksTo> ?d . "// + + "}";// + + String q4 = ""// + + "SELECT ?s ?t ?u ?d ?f ?g ?a ?b ?c" // + + "{" // + + " ?s a ?t ."// + + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + + " ?u <uri:talksTo> ?s . "// + + " ?d a ?f ."// + + " ?f <http://www.w3.org/2000/01/rdf-schema#label> ?g ."// + + " ?g <uri:talksTo> ?d . "// + + " ?a a ?b ."// + + " ?b <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// + + " ?c <uri:talksTo> ?a . "// + + "}";// + + String q5 = ""// + + "SELECT ?f ?m ?d ?a ?h ?r " // + + "{" // + + " ?f a ?m ."// + + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// + + " ?d <uri:talksTo> ?f . "// + + " ?a a ?h ."// + + " ?h <http://www.w3.org/2000/01/rdf-schema#label> ?r ."// + + " ?r <uri:talksTo> ?a . "// + + "}";// + + String q6 = ""// + + "SELECT ?e ?l ?c " // + + "{" // + + " ?e a ?l ."// + + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// + + " ?c <uri:talksTo> ?e . "// + + "}";// + + String q7 = ""// + + "SELECT ?n ?o ?p " // + + "{" // + + " ?n a ?o ."// + + " ?o <http://www.w3.org/2000/01/rdf-schema#label> ?p ."// + + " ?p <uri:talksTo> ?n . "// + + "}";// + + 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; + + 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); + + } catch (Exception e) { + e.printStackTrace(); + } + + SimpleExternalTupleSet extTup1 = new SimpleExternalTupleSet( + (Projection) pq2.getTupleExpr()); + SimpleExternalTupleSet extTup2 = new SimpleExternalTupleSet( + (Projection) pq3.getTupleExpr()); + SimpleExternalTupleSet extTup3 = new SimpleExternalTupleSet( + (Projection) pq4.getTupleExpr()); + + SimpleExternalTupleSet extTup4 = new SimpleExternalTupleSet( + (Projection) pq5.getTupleExpr()); + SimpleExternalTupleSet extTup5 = new SimpleExternalTupleSet( + (Projection) pq6.getTupleExpr()); + SimpleExternalTupleSet extTup6 = new SimpleExternalTupleSet( + (Projection) pq7.getTupleExpr()); + + List<ExternalTupleSet> list = new ArrayList<ExternalTupleSet>(); + + list.add(extTup2); + list.add(extTup1); + list.add(extTup3); + + List<ExternalTupleSet> list2 = new ArrayList<ExternalTupleSet>(); + + list2.add(extTup4); + list2.add(extTup5); + list2.add(extTup6); + + IndexedExecutionPlanGenerator iep = new IndexedExecutionPlanGenerator( + pq1.getTupleExpr(), list); + + Iterator<TupleExpr> plans = new TupleExecutionPlanGenerator() + .getPlans(iep.getIndexedTuples()); + IndexPlanValidator ipv = new IndexPlanValidator(false); + Iterator<TupleExpr> validPlans = ipv.getValidTuples(plans); + + ThreshholdPlanSelector tps = new ThreshholdPlanSelector( + pq1.getTupleExpr()); + TupleExpr optimalTup = tps.getThreshholdQueryPlan(validPlans, .4, .8, + .1, .1); + + NodeCollector nc = new NodeCollector(); + optimalTup.visit(nc); + + } + + @Test + public void twoIndexFilterTest() { + + String q1 = ""// + + "SELECT ?f ?m ?d ?e ?l ?c " // + + "{" // + + " Filter(?f > \"5\")." // + + " Filter(?e > \"5\")." // + + " ?f a ?m ."// + + " ?e a ?l ."// + + " ?d <uri:talksTo> ?f . "// + + " ?c <uri:talksTo> ?e . "// + + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// + + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// + + "}";// + + String q2 = ""// + + "SELECT ?s ?t ?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 " // + + "{" // + + " Filter(?s > \"5\") ."// + + " ?s a ?t ."// + + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + + " ?u <uri:talksTo> ?s . "// + + "}";// + + String q4 = ""// + + "SELECT ?f ?m ?d " // + + "{" // + + " Filter(?f > \"5\") ."// + + " ?f a ?m ."// + + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// + + " ?d <uri:talksTo> ?f . "// + + "}";// + + String q5 = ""// + + "SELECT ?e ?l ?c " // + + "{" // + + " Filter(?e > \"5\") ."// + + " ?e a ?l ."// + + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// + + " ?c <uri:talksTo> ?e . "// + + "}";// + + SPARQLParser parser = new SPARQLParser(); + + ParsedQuery pq1 = null; + ParsedQuery pq2 = null; + ParsedQuery pq3 = null; + ParsedQuery pq4 = null; + ParsedQuery pq5 = 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); + + } catch (Exception e) { + e.printStackTrace(); + } + + SimpleExternalTupleSet extTup1 = new SimpleExternalTupleSet( + (Projection) pq2.getTupleExpr()); + SimpleExternalTupleSet extTup2 = new SimpleExternalTupleSet( + (Projection) pq3.getTupleExpr()); + SimpleExternalTupleSet extTup3 = new SimpleExternalTupleSet( + (Projection) pq4.getTupleExpr()); + SimpleExternalTupleSet extTup4 = new SimpleExternalTupleSet( + (Projection) pq5.getTupleExpr()); + + List<ExternalTupleSet> list = new ArrayList<ExternalTupleSet>(); + + list.add(extTup2); + list.add(extTup1); + + List<ExternalTupleSet> list2 = new ArrayList<ExternalTupleSet>(); + + list2.add(extTup3); + list2.add(extTup4); + + IndexedExecutionPlanGenerator iep = new IndexedExecutionPlanGenerator( + pq1.getTupleExpr(), list); + + Iterator<TupleExpr> plans = new TupleExecutionPlanGenerator() + .getPlans(iep.getIndexedTuples()); + IndexPlanValidator ipv = new IndexPlanValidator(false); + Iterator<TupleExpr> validPlans = ipv.getValidTuples(plans); + + ThreshholdPlanSelector tps = new ThreshholdPlanSelector( + pq1.getTupleExpr()); + TupleExpr optimalTup = tps.getThreshholdQueryPlan(validPlans, .4, .8, + .1, .1); + + NodeCollector nc = new NodeCollector(); + optimalTup.visit(nc); + + Assert.assertEquals(nc.getNodes().size(), list2.size()); + + for (QueryModelNode e : nc.getNodes()) { + Assert.assertTrue(list2.contains(e)); + } + + } + + @Test + public void testCost1() throws Exception { + + String q1 = ""// + + "SELECT ?f ?m ?d ?h ?i " // + + "{" // + + " ?f a ?m ."// + + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// + + " ?d <uri:talksTo> ?f . "// + + " ?d <uri:hangOutWith> ?f ." // + + " ?f <uri:hangOutWith> ?h ." // + + " ?f <uri:associatesWith> ?i ." // + + " ?i <uri:associatesWith> ?h ." // + + "}";// + + SPARQLParser parser = new SPARQLParser(); + + ParsedQuery pq1 = parser.parseQuery(q1, null); + + ThreshholdPlanSelector tps = new ThreshholdPlanSelector( + pq1.getTupleExpr()); + double cost = tps.getCost(pq1.getTupleExpr(), .6, .4, 0); + Assert.assertEquals(.7, cost, .01); + + } + + @Test + public void testCost2() throws Exception { + + String q1 = ""// + + "SELECT ?f ?m ?d ?e ?l ?c " // + + "{" // + + " ?f a ?m ."// + + " ?e a ?l ."// + + " ?d <uri:talksTo> ?f . "// + + " ?c <uri:talksTo> ?e . "// + + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// + + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// + + "}";// + + SPARQLParser parser = new SPARQLParser(); + + ParsedQuery pq1 = parser.parseQuery(q1, null); + + ThreshholdPlanSelector tps = new ThreshholdPlanSelector( + pq1.getTupleExpr()); + double cost = tps.getCost(pq1.getTupleExpr(), .4, .3, .3); + Assert.assertEquals(.58, cost, .000000001); + + } + + @Test + public void testCost3() throws Exception { + + String q1 = ""// + + "SELECT ?f ?m ?d ?e ?l ?c " // + + "{" // + + " Filter(?f > \"5\")." // + + " Filter(?e > \"6\")." // + + " ?f a ?m ."// + + " ?e a ?l ."// + + " ?d <uri:talksTo> ?f . "// + + " ?c <uri:talksTo> ?e . "// + + " ?m <http://www.w3.org/2000/01/rdf-schema#label> ?d ."// + + " ?l <http://www.w3.org/2000/01/rdf-schema#label> ?c ."// + + "}";// + + String q2 = ""// + + "SELECT ?s ?t ?u " // + + "{" // + + " ?s a ?t ."// + + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + + " ?u <uri:talksTo> ?s . "// + + "}";// + + SPARQLParser parser = new SPARQLParser(); + + ParsedQuery pq1 = parser.parseQuery(q1, null); + ParsedQuery pq2 = parser.parseQuery(q2, null); + + SimpleExternalTupleSet sep = new SimpleExternalTupleSet( + (Projection) pq2.getTupleExpr()); + List<ExternalTupleSet> eList = Lists.newArrayList(); + eList.add(sep); + + final TupleExpr te = pq1.getTupleExpr().clone(); + final PrecompJoinOptimizer pcj = new PrecompJoinOptimizer(eList, false); + pcj.optimize(te, null, null); + + ThreshholdPlanSelector tps = new ThreshholdPlanSelector( + pq1.getTupleExpr()); + double cost = tps.getCost(te, .4, .3, .3); + Assert.assertEquals(.575, cost, .0001); + + } + + public static class NodeCollector extends + QueryModelVisitorBase<RuntimeException> { + + List<QueryModelNode> qNodes = Lists.newArrayList(); + + public List<QueryModelNode> getNodes() { + return qNodes; + } + + @Override + public void meetNode(QueryModelNode node) { + if (node instanceof StatementPattern + || node instanceof ExternalTupleSet) { + qNodes.add(node); + } + super.meetNode(node); + + } + } }
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/c12f58f4/extras/indexing/src/test/java/mvm/rya/indexing/IndexPlanValidator/TupleExecutionPlanGeneratorTest.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/test/java/mvm/rya/indexing/IndexPlanValidator/TupleExecutionPlanGeneratorTest.java b/extras/indexing/src/test/java/mvm/rya/indexing/IndexPlanValidator/TupleExecutionPlanGeneratorTest.java index ffb7b2d..f0be8cb 100644 --- a/extras/indexing/src/test/java/mvm/rya/indexing/IndexPlanValidator/TupleExecutionPlanGeneratorTest.java +++ b/extras/indexing/src/test/java/mvm/rya/indexing/IndexPlanValidator/TupleExecutionPlanGeneratorTest.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 @@ -20,14 +20,12 @@ package mvm.rya.indexing.IndexPlanValidator; */ -import static org.junit.Assert.*; import java.util.Iterator; import java.util.List; import java.util.Set; -import junit.framework.Assert; - +import org.junit.Assert; import org.junit.Test; import org.openrdf.query.MalformedQueryException; import org.openrdf.query.algebra.TupleExpr; @@ -39,8 +37,8 @@ import com.beust.jcommander.internal.Sets; public class TupleExecutionPlanGeneratorTest { - - + + private String q1 = ""// + "SELECT ?s ?t ?u " // + "{" // @@ -48,8 +46,8 @@ public class TupleExecutionPlanGeneratorTest { + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + " ?u <uri:talksTo> ?s . "// + "}";// - - + + private String q2 = ""// + "SELECT ?s ?t ?u " // + "{" // @@ -57,8 +55,8 @@ public class TupleExecutionPlanGeneratorTest { + " ?s a ?t ."// + " ?u <uri:talksTo> ?s . "// + "}";// - - + + private String q3 = ""// + "SELECT ?s ?t ?u " // + "{" // @@ -66,8 +64,8 @@ public class TupleExecutionPlanGeneratorTest { + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + " ?s a ?t ."// + "}";// - - + + private String q4 = ""// + "SELECT ?s ?t ?u " // + "{" // @@ -75,8 +73,8 @@ public class TupleExecutionPlanGeneratorTest { + " ?u <uri:talksTo> ?s . "// + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + "}";// - - + + private String q5 = ""// + "SELECT ?s ?t ?u " // + "{" // @@ -84,8 +82,8 @@ public class TupleExecutionPlanGeneratorTest { + " ?u <uri:talksTo> ?s . "// + " ?s a ?t ."// + "}";// - - + + private String q6 = ""// + "SELECT ?s ?t ?u " // + "{" // @@ -93,30 +91,30 @@ public class TupleExecutionPlanGeneratorTest { + " ?s a ?t ."// + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + "}";// - - - - + + + + private String q7 = ""// + "SELECT ?s ?t ?u " // + "{" // + " ?s a ?t ."// + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + "}";// - - + + private String q8 = ""// + "SELECT ?s ?t ?u " // + "{" // + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + " ?s a ?t ."// + "}";// - - - - - - + + + + + + private String q9 = ""// + "SELECT ?s ?t ?u " // + "{" // @@ -126,8 +124,8 @@ public class TupleExecutionPlanGeneratorTest { + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + " ?u <uri:talksTo> ?s . "// + "}";// - - + + private String q10 = ""// + "SELECT ?s ?t ?u " // + "{" // @@ -137,8 +135,8 @@ public class TupleExecutionPlanGeneratorTest { + " ?s a ?t ."// + " ?u <uri:talksTo> ?s . "// + "}";// - - + + private String q11 = ""// + "SELECT ?s ?t ?u " // + "{" // @@ -148,8 +146,8 @@ public class TupleExecutionPlanGeneratorTest { + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + " ?s a ?t ."// + "}";// - - + + private String q12 = ""// + "SELECT ?s ?t ?u " // + "{" // @@ -159,8 +157,8 @@ public class TupleExecutionPlanGeneratorTest { + " ?u <uri:talksTo> ?s . "// + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + "}";// - - + + private String q13 = ""// + "SELECT ?s ?t ?u " // + "{" // @@ -170,8 +168,8 @@ public class TupleExecutionPlanGeneratorTest { + " ?u <uri:talksTo> ?s . "// + " ?s a ?t ."// + "}";// - - + + private String q14 = ""// + "SELECT ?s ?t ?u " // + "{" // @@ -181,8 +179,8 @@ public class TupleExecutionPlanGeneratorTest { + " ?s a ?t ."// + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + "}";// - - + + private String q15 = ""// + "SELECT ?s ?t ?u " // + "{" // @@ -192,10 +190,10 @@ public class TupleExecutionPlanGeneratorTest { + " ?t <http://www.w3.org/2000/01/rdf-schema#label> ?u ."// + " ?u <uri:talksTo> ?s . "// + "}";// - - - - + + + + @Test public void testTwoNodeOrder() { @@ -217,11 +215,11 @@ public class TupleExecutionPlanGeneratorTest { TupleExecutionPlanGenerator tep = new TupleExecutionPlanGenerator(); Iterator<TupleExpr> processedTups = tep.getPlans(tupSet.iterator()); - + List<TupleExpr> processedTupList = Lists.newArrayList(); - + int size = 0; - + while(processedTups.hasNext()) { Assert.assertTrue(processedTups.hasNext()); processedTupList.add(processedTups.next()); @@ -234,11 +232,11 @@ public class TupleExecutionPlanGeneratorTest { Assert.assertTrue(processedTupList.get(1).equals(pq1.getTupleExpr())); } - - - - - + + + + + @Test public void testThreeNodeOrder() { @@ -270,9 +268,9 @@ public class TupleExecutionPlanGeneratorTest { Iterator<TupleExpr> processedTups= tep.getPlans(tupSet.iterator()); List<TupleExpr> processedTupList = Lists.newArrayList(); - + int size = 0; - + while(processedTups.hasNext()) { Assert.assertTrue(processedTups.hasNext()); processedTupList.add(processedTups.next()); @@ -290,8 +288,8 @@ public class TupleExecutionPlanGeneratorTest { Assert.assertTrue(processedTupList.get(3).equals(pq6.getTupleExpr())); } - - + + @Test public void testThreeNodeOrderFilter() { @@ -318,7 +316,7 @@ public class TupleExecutionPlanGeneratorTest { // TODO Auto-generated catch block e.printStackTrace(); } - + System.out.println(pq1.getTupleExpr()); Set<TupleExpr> tupSet = Sets.newHashSet(); @@ -328,11 +326,11 @@ public class TupleExecutionPlanGeneratorTest { Iterator<TupleExpr> processedTups= tep.getPlans(tupSet.iterator()); List<TupleExpr> processedTupList = Lists.newArrayList(); - + int size = 0; - + while(processedTups.hasNext()) { - + Assert.assertTrue(processedTups.hasNext()); TupleExpr te = processedTups.next(); processedTupList.add(te); @@ -351,14 +349,14 @@ public class TupleExecutionPlanGeneratorTest { Assert.assertTrue(processedTupList.get(3).equals(pq6.getTupleExpr())); } - - - - - - - - - + + + + + + + + + } http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/c12f58f4/extras/indexing/src/test/java/mvm/rya/indexing/IndexPlanValidator/TupleReArrangerTest.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/test/java/mvm/rya/indexing/IndexPlanValidator/TupleReArrangerTest.java b/extras/indexing/src/test/java/mvm/rya/indexing/IndexPlanValidator/TupleReArrangerTest.java index 96466cb..aaa4819 100644 --- a/extras/indexing/src/test/java/mvm/rya/indexing/IndexPlanValidator/TupleReArrangerTest.java +++ b/extras/indexing/src/test/java/mvm/rya/indexing/IndexPlanValidator/TupleReArrangerTest.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,8 +22,7 @@ package mvm.rya.indexing.IndexPlanValidator; import java.util.List; -import junit.framework.Assert; - +import org.junit.Assert; import org.junit.Test; import org.openrdf.query.MalformedQueryException; import org.openrdf.query.algebra.TupleExpr; @@ -35,27 +34,27 @@ public class TupleReArrangerTest { @Test public void tupleReArrangeTest1() throws MalformedQueryException { - + String queryString = ""// + "SELECT ?a ?b ?c ?d ?e" // + "{" // + "{ ?a a ?b . ?a <http://www.w3.org/2000/01/rdf-schema#label> ?c }"// + " UNION { ?a <uri:talksTo> ?d . ?a <http://www.w3.org/2000/01/rdf-schema#label> ?e }"// + "}";// - + SPARQLParser sp = new SPARQLParser(); ParsedQuery pq = sp.parseQuery(queryString, null); List<TupleExpr> tuples = TupleReArranger.getTupleReOrderings(pq.getTupleExpr()); - + Assert.assertEquals(4, tuples.size()); - + } - - - + + + @Test public void tupleReArrangeTest2() throws MalformedQueryException { - + String queryString = ""// + "SELECT ?a ?b ?c ?d ?e ?x ?y" // + "{" // @@ -64,23 +63,23 @@ public class TupleReArrangerTest { + "{ ?a a ?b . ?a <http://www.w3.org/2000/01/rdf-schema#label> ?c }"// + " UNION { ?a <uri:talksTo> ?d . ?a <http://www.w3.org/2000/01/rdf-schema#label> ?e }"// + "}";// - + SPARQLParser sp = new SPARQLParser(); ParsedQuery pq = sp.parseQuery(queryString, null); List<TupleExpr> tuples = TupleReArranger.getTupleReOrderings(pq.getTupleExpr()); - - + + Assert.assertEquals(24, tuples.size()); - + } - - - - - + + + + + @Test public void tupleReArrangeTest3() throws MalformedQueryException { - + String queryString = ""// + "SELECT ?a ?b ?c ?d ?e ?x ?y" // + "{" // @@ -91,24 +90,24 @@ public class TupleReArrangerTest { + "{ ?a a ?b . ?a <http://www.w3.org/2000/01/rdf-schema#label> ?c }"// + " UNION { ?a <uri:talksTo> ?d . ?a <http://www.w3.org/2000/01/rdf-schema#label> ?e }"// + "}";// - + SPARQLParser sp = new SPARQLParser(); ParsedQuery pq = sp.parseQuery(queryString, null); List<TupleExpr> tuples = TupleReArranger.getTupleReOrderings(pq.getTupleExpr()); - + Assert.assertEquals(24, tuples.size()); - + } - - - - - - - + + + + + + + @Test public void tupleReArrangeTest4() throws MalformedQueryException { - + String queryString = ""// + "SELECT ?a ?b ?c ?d ?e ?x ?y" // + "{" // @@ -120,22 +119,22 @@ public class TupleReArrangerTest { + "{ ?a a ?b . ?a <http://www.w3.org/2000/01/rdf-schema#label> ?c }"// + " UNION { ?a <uri:talksTo> ?d . ?a <http://www.w3.org/2000/01/rdf-schema#label> ?e }"// + "}";// - + SPARQLParser sp = new SPARQLParser(); ParsedQuery pq = sp.parseQuery(queryString, null); TupleExpr te = pq.getTupleExpr(); - (new FilterOptimizer()).optimize(te, null, null); + new FilterOptimizer().optimize(te, null, null); System.out.println(te); List<TupleExpr> tuples = TupleReArranger.getTupleReOrderings(te); System.out.println(tuples); - + Assert.assertEquals(24, tuples.size()); - + } - - - - - + + + + + }
