com.bigdata.bop.joinGraph

Class TestPartitionedJoinGroup_canJoinUsingConstraints

java.lang.Object

junit.framework.Assert

junit.framework.TestCase

junit.framework.TestCase2

com.bigdata.bop.joinGraph.TestPartitionedJoinGroup_canJoinUsingConstraints

All Implemented Interfaces:

junit.framework.Test

public class TestPartitionedJoinGroup_canJoinUsingConstraints
extends TestCase2

This test suite is built around around BSBM Q5. Each test has an existing join path and a new vertex to be added to the join path. The question is whether or not the vertex can join with the join path using one or more shared variable(s). This tests a method used to incrementally grow a join path when it is dynamically decided that an IPredicate may be added to the join path based on shared variables. Static analysis easily reports those joins which are allowed based on the variables directly given with two IPredicates. The purpose of this test suite is to explore when joins (based on shared variables) become permissible through IConstraints as the variable(s) used within those constraints become bound.

Note: To avoid a dependency on the RDF model layer, this just uses String constants for URIs and Literals.

Analysis of BSBM Q5

The following predicates all join on product:

• p0
• p2
• p4
• p5

The predicates (p3 and p5) do not directly join with any of the other predicates (they do not directly share any variables). In general, a join without shared variables means the cross product of the sources will be materialized and such joins should be run last.

However, in this case there are two SPARQL FILTERs (c1 and c2) which (a) use those variables (origProperty1 and origProperty2); and (b) can constrain the query. This means that running the predicates without shared variables and applying the constraints before the tail of the plan can in fact lead to a more efficient join path.

This set of unit tests explores various join paths and verifies that the canJoin() and canJoinUsingConstraints() methods correctly recognize edges by which a join path can be extended corresponding to both static and dynamic analysis of the query.

Version:

$Id: TestBOpUtility_canJoinUsingConstraints.java 4211 2011-02-20 21:20:44Z thompsonbry $

Author:

Bryan Thompson

See Also:

PartitionedJoinGroup.canJoin(IPredicate, IPredicate), PartitionedJoinGroup.canJoinUsingConstraints(IPredicate[], IPredicate, IConstraint[]), JGraph

Nested Class Summary

Nested classes/interfaces inherited from class junit.framework.TestCase2

TestCase2.MyProperties, TestCase2.RandomType

Field Summary

Fields inherited from class junit.framework.TestCase2

_randomType, log

Constructor Summary

Constructors

Constructor and Description
TestPartitionedJoinGroup_canJoinUsingConstraints()
TestPartitionedJoinGroup_canJoinUsingConstraints(String name)

Method Summary

Methods

Modifier and Type	Method and Description
void	test_attachConstraints_BSBM_Q5_path01() path = [1, 2, 4, 6, 0, 3, 5]
void	test_attachConstraints_BSBM_Q5_path02() [5, 3, 1, 0, 2, 4, 6].
void	test_attachConstraints_BSBM_Q5_path03() [3, 4, 5, 6, 1, 2, 0] (key-range constraint variant).
void	test_attachConstraints_BSBM_Q5_path04() [5 6 0 2 1 4 3].
void	test_canJoinUsingConstraints_1step_productVar() Unit test for one-step joins based on the product variable.
void	test_canJoinUsingConstraints_illegalArgument() Unit tests to verify that arguments are validated.
void	test_canJoinUsingConstraints_multiStep_productVar() Unit test for multi-step join paths based on the product variable.
void	test_canJoinUsingConstraints_p3_p4() Unit test examines the predicates without shared variables and verifies (a) that joins are not permitted when the constraints are not considered; and (b) that joins are permitted when the constraints are considered.
void	test_canJoinUsingConstraints_p5_p6() Unit test examines the predicates without shared variables and verifies (a) that joins are not permitted when the constraints are not considered; and (b) that joins are permitted when the constraints are considered.

Methods inherited from class junit.framework.TestCase2

assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEqualsWithinUlps, assertSameArray, assertSameArray, assertSameBigDecimal, assertSameBigDecimal, assertSameBigInteger, assertSameBigInteger, assertSameIterator, assertSameIterator, assertSameIteratorAnyOrder, assertSameIteratorAnyOrder, assertSameValue, assertSameValue, assertZeroUlps, assertZeroUlps, fail, getInnerCause, getNormalInt, getProjectBuildPath, getProperties, getRandomObject, getRandomObject, getRandomOrder, getRandomString, getTestInputStream, getTestResource, getTestResource, getUlps, getUlps, isDEBUG, isDEBUG, isINFO, isINFO, isInnerCause, logProperties

Methods inherited from class junit.framework.TestCase

assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertFalse, assertFalse, assertNotNull, assertNotNull, assertNotSame, assertNotSame, assertNull, assertNull, assertSame, assertSame, assertTrue, assertTrue, countTestCases, createResult, fail, fail, failNotEquals, failNotSame, failSame, format, getName, run, run, runBare, runTest, setName, setUp, tearDown, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

TestPartitionedJoinGroup_canJoinUsingConstraints

public TestPartitionedJoinGroup_canJoinUsingConstraints()

TestPartitionedJoinGroup_canJoinUsingConstraints

public TestPartitionedJoinGroup_canJoinUsingConstraints(String name)

Parameters:

name -

Method Detail

test_canJoinUsingConstraints_illegalArgument

public void test_canJoinUsingConstraints_illegalArgument()

Unit tests to verify that arguments are validated.

See Also:

PartitionedJoinGroup.canJoinUsingConstraints(IPredicate[], IPredicate, IConstraint[])

test_canJoinUsingConstraints_1step_productVar

public void test_canJoinUsingConstraints_1step_productVar()

Unit test for one-step joins based on the product variable.

test_canJoinUsingConstraints_multiStep_productVar

public void test_canJoinUsingConstraints_multiStep_productVar()

Unit test for multi-step join paths based on the product variable.

test_canJoinUsingConstraints_p3_p4

public void test_canJoinUsingConstraints_p3_p4()

Unit test examines the predicates without shared variables and verifies (a) that joins are not permitted when the constraints are not considered; and (b) that joins are permitted when the constraints are considered.

This test is identical to test_canJoinUsingConstraints_p5_p6()() except that it considers the (p3 x p4) join via the c1 constraint instead.

test_canJoinUsingConstraints_p5_p6

public void test_canJoinUsingConstraints_p5_p6()

Unit test examines the predicates without shared variables and verifies (a) that joins are not permitted when the constraints are not considered; and (b) that joins are permitted when the constraints are considered.

This test is identical to test_canJoinUsingConstraints_p3_p4() except that it considers the (p5 x p6) join via the c2 constraint instead.

test_attachConstraints_BSBM_Q5_path01

public void test_attachConstraints_BSBM_Q5_path01()

path = [1, 2, 4, 6, 0, 3, 5]

test_attachConstraints_BSBM_Q5_path02

public void test_attachConstraints_BSBM_Q5_path02()

[5, 3, 1, 0, 2, 4, 6].

test_attachConstraints_BSBM_Q5_path03

public void test_attachConstraints_BSBM_Q5_path03()

[3, 4, 5, 6, 1, 2, 0] (key-range constraint variant).

test_attachConstraints_BSBM_Q5_path04

public void test_attachConstraints_BSBM_Q5_path04()

[5 6 0 2 1 4 3]. FIXME The above join path produces a false ZERO result for the query and all of the join path segments below produce a false exact ZERO (0E) cardinality estimate. Figure out why. The final path chosen could have been any of the one step extensions of a path with a false 0E cardinality estimate.

 INFO : 3529      main com.bigdata.bop.joinGraph.rto.JGraph.expand(JGraph.java:1116): 
 ** round=4: paths{in=14,considered=26,out=6}
 path    srcCard  *          f (      in  sumRgCt tplsRead      out    limit  adjCard) =    estRead    estCard  : sumEstRead sumEstCard sumEstCost  joinPath
    0          0E *       0.00 (       0        0        0        0      200        0) =          0          0E :          1          0          0  [ 5  6  0  2  1  4 ]
    1          0E *       0.00 (       0        0        0        0      200        0) =          0          0E :          1          0          0  [ 5  6  0  2  4  3 ]
    2          0E *       0.00 (       0        0        0        0      200        0) =          0          0E :          1          0          0  [ 5  6  0  4  1  3 ]
    3          0E *       0.00 (       0        0        0        0      200        0) =          0          0E :          1          0          0  [ 5  6  2  1  4  3 ]
    4        208  *       1.00 (      26       26       26       26      400       26) =         26        208  :      16576       1447       1447  [ 5  3  1  2  4  0 ]
    5          0E *       0.00 (       0        0        0        0      200        0) =          0          0E :          2          1          1  [ 5  3  6  0  1  2 ]