com.bigdata.bop.join

Class PipelinedHashIndexAndSolutionSetJoinOp

java.lang.Object

com.bigdata.bop.CoreBaseBOp

com.bigdata.bop.BOpBase

com.bigdata.bop.PipelineOp

com.bigdata.bop.join.HashIndexOpBase

com.bigdata.bop.join.HashIndexOp

com.bigdata.bop.join.PipelinedHashIndexAndSolutionSetJoinOp

All Implemented Interfaces:

BOp, ISingleThreadedOp, IPropertySet, Serializable, Cloneable

public class PipelinedHashIndexAndSolutionSetJoinOp
extends HashIndexOp

Operator for pipelined hash index construction and subsequent join. Note that this operator needs not to be combined with a solution set hash join, but instead gets the subquery/subgroup passed as a parameter and thus can be considered as an "all-in-one" build-hash-index-and-join operation. The operator is designed for single-threaded use (as it is the case for the non-pipelined hash index & join operators). It's processing scheme is illustrated by an example in the following. Assume we have a query such as SELECT * WHERE { ?s ?o1 OPTIONAL { ?s ?o2 . ?s ?o3 . } } LIMIT 10 to be evaluated over the data set . . . . . . , where the OPTIONAL is considered as a complex group that is translated using a hash join pattern. The approach taken by this operator is that the OPTIONAL pattern is considered as subquery that is passed in to this operator via Annotations.SUBQUERY. The operator logically proceeds as follows: 1. Incoming are the bindings from outside, i.e. in our example the bindings for triple pattern "?s ?o1". Given the input data at hand, this means we have the following binding set { { ?s -> , ?o1 -> }, { ?s -> , ?o1 -> } { ?s -> , ?o1 -> } } coming in. For the sake of this example, assume the solutions are dropping in one after the after (chunk size=1) s.t. we have three iterations, but note that the implementation implements a generalized, vectored approach processing the input chunk by chunk.. 2. The join variable set is { ?s }. We compute the distinct projection over ?s on the incoming bindings: - In the 1st iteration, the distinct projection is { ?s -> }, - In the 2nd iteration, the distinct projection is { ?s -> }, - In the 3rd iteration, the distinct projection is { ?s -> } again. 3. For each of these distinct projections, we decide whether the subquery has been evaluated with the distinct projection as input before. If the subquery has already been evaluated, we take the fast path and proceed with step 5. If it has not yet been evaluated before, proceed to step 4 (namely its evaluation and buffering of the solution on the hash index). For our example this means: in the first iteration we proceed to step (4) with { ?s -> } as input; in the second iteration, we proceed to step (4) with { ?s -> } as input; in the third iteration, we can directly proceed to step (5): the distinct projection { ?s -> } has been encountered in iteration 1 already. 4. Evaluate the subquery for the incoming binding. The result is stored in a hash index (this hash index is used, in future, to decide whether the result has been already computed before for the distinct projection in step 3; note that, in addition to the hash index, we also record those distinct projections for which the subquery has been evaluated without producing a result, to avoid unnecessary re-computation). In the first iteration, we compute the subquery result { ?s -> , ?o2 -> , ?o3 -> } for the input binding { ?s -> }; in the second iteration, we compute { ?s -> } for the input binding { ?s -> } (i.e., OPTIONAL subquery that does not match, leaving the input unmodified); there is no third iteration step. 5. Join the original bindings (from which the distinct projection was obtained) against the hash index and output the results. The operator supports all kinds of joins (Normal, Exists, NotExists, etc.). We thus obtain the following matches with the hash index: - Iteration 1: { ?s -> , ?o1 -> } JOIN { ?s -> , ?o2 -> , ?o3 -> } - Iteration 2: { ?s -> , ?o1 -> } JOIN { ?s -> } - Iteration 3: { ?s -> , ?o1 -> } JOIN { ?s -> , ?o2 -> , ?o3 -> } This gives us the expected final result: { { ?s -> , ?o1 -> , ?o2 -> , ?o3 -> }, { ?s -> , ?o1 -> }, { ?s -> , ?o1 -> , ?o2 -> , ?o3 -> } } Note that this strategy is pipelined in the sense that all results from the left are emitted as soon as the subquery result for its distinct projection result has been calculated. # Further notes: 1.) Vectored processing: the implementation uses a vectored processing approach: instead of processing the mappings one by one, we collect unseen distinct projections and their associated incoming mappings in two buffers, namely the distinctProjectionBuffer and the incomingBindingssBuffer. Buffer size is controlled via annotations: incomingBindingssBufferThreshold and the Annotations.DISTINCT_PROJECTION_BUFFER_THRESHOLD. If, after processing a chunk, one of these thresholds is exceeded for the respective buffer (or, alternatively, if we're in the lastPass), the mappings in the distinctProjectionBuffer are provided as input to the subquery "in batch" (cf. step 4.)) and subsequently the bindings from the incomingBindingssBuffer are joined (and released). At that point, the buffers become empty again. Effectively, the thresholds allow to reserve some internal buffer space. For now, we go with default values, but we may want to expose these buffers via query hints or the like at some point. 2.) Alternative source: the strategy sketched above illustrates how the op works for subqueries. An alternative way of using the operator is by setting Annotations.BINDING_SETS_SOURCE *instead of* the subquery. This is used when computing a hash join with a VALUES clause; in that case, the binding sets provided by the VALUES clause are considered as "inner query"; as a notable difference, this set of values is static and does not need to be re-evaluated each time, it is submitted once to the hash index in the beginning and joined with every incoming binding. 3.) There exist two "implementations" of the operator, namely the JVMPipelinedHashJoinUtility and the HTreePipelinedHashJoinUtility. # Other remarks: There are some more technicalities like support for ASK_VAR (which is used by the FILTER (NOT) EXISTS translation scheme, which work in principle in the same way as they do for the standard hash join. Usage: the pipelined hash join operator is preferably used for queries containing LIMIT but *no* ORDER BY. It can also be globally enabled by system parameter QueryHints.PIPELINED_HASH_JOIN and via query hints. See AST2BOpUtility.usePipelinedHashJoin(com.bigdata.rdf.sparql.ast.eval.AST2BOpContext, com.bigdata.rdf.sparql.ast.QueryNodeBase) for the method implementing its selection strategy.

Author:

Michael Schmidt

See Also:

for implementation, Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	PipelinedHashIndexAndSolutionSetJoinOp.Annotations

Nested classes/interfaces inherited from class com.bigdata.bop.join.HashIndexOpBase

HashIndexOpBase.ChunkTaskBase

Field Summary

Fields inherited from class com.bigdata.bop.CoreBaseBOp

DEFAULT_INITIAL_CAPACITY

Fields inherited from interface com.bigdata.bop.BOp

NOANNS, NOARGS

Constructor Summary

Constructors

Constructor and Description
PipelinedHashIndexAndSolutionSetJoinOp(BOp[] args, Map<String,Object> annotations) Shallow copy constructor.
PipelinedHashIndexAndSolutionSetJoinOp(BOp[] args, NV... annotations)
PipelinedHashIndexAndSolutionSetJoinOp(PipelinedHashIndexAndSolutionSetJoinOp op) Deep copy constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected HashIndexOpBase.ChunkTaskBase	createChunkTask(BOpContext<IBindingSet> context)

Methods inherited from class com.bigdata.bop.join.HashIndexOpBase

eval, newStats

Methods inherited from class com.bigdata.bop.PipelineOp

assertAtOnceJavaHeapOp, assertMaxParallelOne, getChunkCapacity, getChunkOfChunksCapacity, getChunkTimeout, getMaxMemory, getMaxParallel, isAtOnceEvaluation, isBlockedEvaluation, isLastPassRequested, isPipelinedEvaluation, isReorderSolutions, isSharedState

Methods inherited from class com.bigdata.bop.BOpBase

__replaceArg, _clearProperty, _set, _setProperty, annotations, annotationsCopy, annotationsEqual, annotationsRef, argIterator, args, argsCopy, arity, clearAnnotations, clearProperty, deepCopy, deepCopy, get, getProperty, setArg, setProperty, setUnboundProperty, toArray, toArray

Methods inherited from class com.bigdata.bop.CoreBaseBOp

annotationsEqual, annotationsToString, annotationsToString, annotationValueToString, checkArgs, clone, equals, getEvaluationContext, getId, getProperty, getRequiredProperty, hashCode, indent, isController, mutation, shortenName, toShortString, toString, toString

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

PipelinedHashIndexAndSolutionSetJoinOp

public PipelinedHashIndexAndSolutionSetJoinOp(PipelinedHashIndexAndSolutionSetJoinOp op)

Deep copy constructor.

PipelinedHashIndexAndSolutionSetJoinOp

public PipelinedHashIndexAndSolutionSetJoinOp(BOp[] args,
                                      Map<String,Object> annotations)

Shallow copy constructor.

Parameters:

args -

annotations -

PipelinedHashIndexAndSolutionSetJoinOp

public PipelinedHashIndexAndSolutionSetJoinOp(BOp[] args,
                                      NV... annotations)

Method Detail

createChunkTask

protected HashIndexOpBase.ChunkTaskBase createChunkTask(BOpContext<IBindingSet> context)

Overrides:

createChunkTask in class HashIndexOp