com.bigdata.bop.join

Class JVMHashIndex

java.lang.Object

com.bigdata.bop.join.JVMHashIndex

public class JVMHashIndex
extends Object

A hash index for IBindingSets that supports duplicate solutions and hit counts. The hit counts are used to detect IBindingSets that do not join for OPTIONAL, MINUS, and related kinds of "negation" joins.

Note: The JVMDistinctBindingSetsOp does not use this class right now because it enjoys better concurrency than the JVMHashIndex. Also see JVMDistinctFilter, which is the backing implementation for the JVMDistinctBindingSetsOp.

Author:

Bryan Thompson

See Also:

JVMDistinctFilter

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	JVMHashIndex.Bucket A group of solutions having the same as-bound values for the join vars.
static class	JVMHashIndex.Key Wrapper for the keys in the hash table.
static class	JVMHashIndex.SolutionHit An solution and a hit counter as stored in the JVMHashIndex.

Constructor Summary

Constructors

Constructor and Description
JVMHashIndex(IVariable<?>[] keyVars, boolean indexSolutionsHavingUnboundJoinVars, Map<JVMHashIndex.Key,JVMHashIndex.Bucket> map)

Method Summary

Methods

Modifier and Type	Method and Description
JVMHashIndex.Key	add(IBindingSet bset) Add the solution to the index.
boolean	addDistinct(IBindingSet bset) Add the solution to the index iff the solution is not already present in the index.
int	bucketCount() The #of buckets in the hash index.
Iterator<JVMHashIndex.Bucket>	buckets() Visit all buckets in the hash index.
JVMHashIndex.Bucket	getBucket(IBindingSet left) Return the hash JVMHashIndex.Bucket into which the given solution is mapped.
JVMHashIndex.Bucket[]	toArray() Export the JVMHashIndex.Buckets as an array.

Methods inherited from class java.lang.Object

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

Constructor Detail

JVMHashIndex

public JVMHashIndex(IVariable<?>[] keyVars,
            boolean indexSolutionsHavingUnboundJoinVars,
            Map<JVMHashIndex.Key,JVMHashIndex.Bucket> map)

Parameters:

keyVars - The variables that are used to form the keys in the hash index (required, but may be empty). The order of the entries is used when forming the as-bound keys for the hash table. Duplicate elements and null elements are not permitted. If no join variables are specified, then the join will consider the N x M cross product, filtering for solutions which join. This is very expensive when compared to a hash join. Whenever possible you should identify one or more variables which must be bound for the join and specify those as the join variables.

indexSolutionsHavingUnboundJoinVars - When true, we allow solutions to be stored in the hash index that have unbound variables for the keyVars. When false, such solutions are dropped (they are not added to the index).

map - The backing map. A HashMap should be faster for insert and search. A LinkedHashMap should be faster for scans. Some join patterns do not require us to use scans, in which case HashMap is the clear winner. (For example, a non-optional hash join against an access path never uses the iterator over the hash index.)

Method Detail

add

public JVMHashIndex.Key add(IBindingSet bset)

Add the solution to the index.

Parameters:

bset - The IBindingSet.

Returns:

The JVMHashIndex.Key iff the solution was added to the index and null iff the solution was not added (because a JVMHashIndex.Key could not be formed for the solution given the specified keyVars).

addDistinct

public boolean addDistinct(IBindingSet bset)

Add the solution to the index iff the solution is not already present in the index.

Parameters:

bset - The solution.

Returns:

true iff the index was modified by this operation.

getBucket

public JVMHashIndex.Bucket getBucket(IBindingSet left)

Return the hash JVMHashIndex.Bucket into which the given solution is mapped.

Note: The caller must apply an appropriate join constraint in order to correctly reject solutions that (a) violate the join contract; and (b) that are present in the hash bucket due to a hash collection rather than because they have the same bindings for the join variables.

Parameters:

left - The probe.

Returns:

The hash JVMHashIndex.Bucket into which the given solution is mapped -or- null if there is no such hash bucket.

buckets

public Iterator<JVMHashIndex.Bucket> buckets()

Visit all buckets in the hash index.

bucketCount

public int bucketCount()

The #of buckets in the hash index. Each bucket has a distinct hash code. Hash collisions can cause solutions that are distinct in their keyVars to nevertheless be mapped into the same hash bucket.

Returns:

The #of buckets in the hash index.

toArray

public JVMHashIndex.Bucket[] toArray()

Export the JVMHashIndex.Buckets as an array.