Code:
/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / Core / System / Linq / Parallel / QueryOperators / Binary / HashJoinQueryOperatorEnumerator.cs / 1305376 / HashJoinQueryOperatorEnumerator.cs
// ==++==
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
// ==--==
// =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
//
// HashJoinQueryOperatorEnumerator.cs
//
// [....]
//
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
using System.Collections.Generic;
using System.Diagnostics.Contracts;
using System.Threading;
namespace System.Linq.Parallel
{
///
/// This enumerator implements the hash-join algorithm as noted earlier.
///
/// Assumptions:
/// This enumerator type won't work properly at all if the analysis engine didn't
/// ensure a proper hash-partition. We expect inner and outer elements with equal
/// keys are ALWAYS in the same partition. If they aren't (e.g. if the analysis is
/// busted) we'll silently drop items on the floor. :(
///
///
/// This is the enumerator class for two operators:
/// - Join
/// - GroupJoin
///
///
: QueryOperatorEnumerator
{
private readonly QueryOperatorEnumerator, TLeftKey> m_leftSource; // Left (outer) data source. For probing.
private readonly QueryOperatorEnumerator, int> m_rightSource; // Right (inner) data source. For building.
private readonly Func m_singleResultSelector; // Single result selector.
private readonly Func, TOutput> m_groupResultSelector; // Group result selector.
private readonly IEqualityComparer m_keyComparer; // An optional key comparison object.
private readonly CancellationToken m_cancellationToken;
private Mutables m_mutables;
private class Mutables
{
internal TLeftInput m_currentLeft; // The current matching left element.
internal TLeftKey m_currentLeftKey; // The current index of the matching left element.
internal HashLookup>> m_rightHashLookup; // The hash lookup.
internal ListChunk m_currentRightMatches; // Current right matches (if any).
internal int m_currentRightMatchesIndex; // Current index in the set of right matches.
internal int m_outputLoopCount;
}
//----------------------------------------------------------------------------------------
// Instantiates a new hash-join enumerator.
//
internal HashJoinQueryOperatorEnumerator(
QueryOperatorEnumerator, TLeftKey> leftSource,
QueryOperatorEnumerator, int> rightSource,
Func singleResultSelector,
Func, TOutput> groupResultSelector,
IEqualityComparer keyComparer,
CancellationToken cancellationToken)
{
Contract.Assert(leftSource != null);
Contract.Assert(rightSource != null);
Contract.Assert(singleResultSelector != null || groupResultSelector != null);
m_leftSource = leftSource;
m_rightSource = rightSource;
m_singleResultSelector = singleResultSelector;
m_groupResultSelector = groupResultSelector;
m_keyComparer = keyComparer;
m_cancellationToken = cancellationToken;
}
//---------------------------------------------------------------------------------------
// MoveNext implements all the hash-join logic noted earlier. When it is called first, it
// will execute the entire inner query tree, and build a hash-table lookup. This is the
// Building phase. Then for the first call and all subsequent calls to MoveNext, we will
// incrementally perform the Probing phase. We'll keep getting elements from the outer
// data source, looking into the hash-table we built, and enumerating the full results.
//
// This routine supports both inner and outer (group) joins. An outer join will yield a
// (possibly empty) list of matching elements from the inner instead of one-at-a-time,
// as we do for inner joins.
//
internal override bool MoveNext(ref TOutput currentElement, ref TLeftKey currentKey)
{
Contract.Assert(m_singleResultSelector != null || m_groupResultSelector != null, "expected a compiled result selector");
Contract.Assert(m_leftSource != null);
Contract.Assert(m_rightSource != null);
// BUILD phase: If we haven't built the hash-table yet, create that first.
Mutables mutables = m_mutables;
if (mutables == null)
{
mutables = m_mutables = new Mutables();
#if DEBUG
int hashLookupCount = 0;
int hashKeyCollisions = 0;
#endif
mutables.m_rightHashLookup = new HashLookup>>(m_keyComparer);
Pair rightPair = default(Pair);
int rightKeyUnused = default(int);
int i = 0;
while (m_rightSource.MoveNext(ref rightPair, ref rightKeyUnused))
{
if ((i++ & CancellationState.POLL_INTERVAL) == 0)
CancellationState.ThrowIfCanceled(m_cancellationToken);
TRightInput rightElement = rightPair.First;
THashKey rightHashKey = rightPair.Second;
// We ignore null keys.
if (rightHashKey != null)
{
#if DEBUG
hashLookupCount++;
#endif
// See if we've already stored an element under the current key. If not, we
// lazily allocate a pair to hold the elements mapping to the same key.
const int INITIAL_CHUNK_SIZE = 2;
Pair> currentValue = default(Pair>);
if (!mutables.m_rightHashLookup.TryGetValue(rightHashKey, ref currentValue))
{
currentValue = new Pair>(rightElement, null);
if (m_groupResultSelector != null)
{
// For group joins, we also add the element to the list. This makes
// it easier later to yield the list as-is.
currentValue.Second = new ListChunk(INITIAL_CHUNK_SIZE);
currentValue.Second.Add(rightElement);
}
mutables.m_rightHashLookup.Add(rightHashKey, currentValue);
}
else
{
if (currentValue.Second == null)
{
// Lazily allocate a list to hold all but the 1st value. We need to
// re-store this element because the pair is a value type.
currentValue.Second = new ListChunk(INITIAL_CHUNK_SIZE);
mutables.m_rightHashLookup[rightHashKey] = currentValue;
}
currentValue.Second.Add(rightElement);
#if DEBUG
hashKeyCollisions++;
#endif
}
}
}
#if DEBUG
TraceHelpers.TraceInfo("ParallelJoinQueryOperator::MoveNext - built hash table [count = {0}, collisions = {1}]",
hashLookupCount, hashKeyCollisions);
#endif
}
// PROBE phase: So long as the source has a next element, return the match.
ListChunk currentRightChunk = mutables.m_currentRightMatches;
if (currentRightChunk != null && mutables.m_currentRightMatchesIndex == currentRightChunk.Count)
{
currentRightChunk = mutables.m_currentRightMatches = currentRightChunk.Next;
mutables.m_currentRightMatchesIndex = 0;
}
if (mutables.m_currentRightMatches == null)
{
// We have to look up the next list of matches in the hash-table.
Pair leftPair = default(Pair);
TLeftKey leftKey = default(TLeftKey);
while (m_leftSource.MoveNext(ref leftPair, ref leftKey))
{
if ((mutables.m_outputLoopCount++ & CancellationState.POLL_INTERVAL) == 0)
CancellationState.ThrowIfCanceled(m_cancellationToken);
// Find the match in the hash table.
Pair> matchValue = default(Pair>);
TLeftInput leftElement = leftPair.First;
THashKey leftHashKey = leftPair.Second;
// Ignore null keys.
if (leftHashKey != null)
{
if (mutables.m_rightHashLookup.TryGetValue(leftHashKey, ref matchValue))
{
// We found a new match. For inner joins, we remember the list in case
// there are multiple value under this same key -- the next iteration will pick
// them up. For outer joins, we will use the list momentarily.
if (m_singleResultSelector != null)
{
mutables.m_currentRightMatches = matchValue.Second;
Contract.Assert(mutables.m_currentRightMatches == null || mutables.m_currentRightMatches.Count > 0,
"we were expecting that the list would be either null or empty");
mutables.m_currentRightMatchesIndex = 0;
// Yield the value.
currentElement = m_singleResultSelector(leftElement, matchValue.First);
currentKey = leftKey;
// If there is a list of matches, remember the left values for next time.
if (matchValue.Second != null)
{
mutables.m_currentLeft = leftElement;
mutables.m_currentLeftKey = leftKey;
}
return true;
}
}
}
// For outer joins, we always yield a result.
if (m_groupResultSelector != null)
{
// Grab the matches, or create an empty list if there are none.
IEnumerable matches = matchValue.Second;
if (matches == null)
{
matches = ParallelEnumerable.Empty();
}
// Generate the current value.
currentElement = m_groupResultSelector(leftElement, matches);
currentKey = leftKey;
return true;
}
}
// If we've reached the end of the data source, we're done.
return false;
}
// Produce the next element and increment our index within the matches.
Contract.Assert(m_singleResultSelector != null);
Contract.Assert(mutables.m_currentRightMatches != null);
Contract.Assert(0 <= mutables.m_currentRightMatchesIndex && mutables.m_currentRightMatchesIndex < mutables.m_currentRightMatches.Count);
currentElement = m_singleResultSelector(
mutables.m_currentLeft, mutables.m_currentRightMatches.m_chunk[mutables.m_currentRightMatchesIndex]);
currentKey = mutables.m_currentLeftKey;
mutables.m_currentRightMatchesIndex++;
return true;
}
protected override void Dispose(bool disposing)
{
Contract.Assert(m_leftSource != null && m_rightSource != null);
m_leftSource.Dispose();
m_rightSource.Dispose();
}
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// ==++==
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
// ==--==
// =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
//
// HashJoinQueryOperatorEnumerator.cs
//
// [....]
//
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
using System.Collections.Generic;
using System.Diagnostics.Contracts;
using System.Threading;
namespace System.Linq.Parallel
{
///
/// This enumerator implements the hash-join algorithm as noted earlier.
///
/// Assumptions:
/// This enumerator type won't work properly at all if the analysis engine didn't
/// ensure a proper hash-partition. We expect inner and outer elements with equal
/// keys are ALWAYS in the same partition. If they aren't (e.g. if the analysis is
/// busted) we'll silently drop items on the floor. :(
///
///
/// This is the enumerator class for two operators:
/// - Join
/// - GroupJoin
///
///
: QueryOperatorEnumerator
{
private readonly QueryOperatorEnumerator, TLeftKey> m_leftSource; // Left (outer) data source. For probing.
private readonly QueryOperatorEnumerator, int> m_rightSource; // Right (inner) data source. For building.
private readonly Func m_singleResultSelector; // Single result selector.
private readonly Func, TOutput> m_groupResultSelector; // Group result selector.
private readonly IEqualityComparer m_keyComparer; // An optional key comparison object.
private readonly CancellationToken m_cancellationToken;
private Mutables m_mutables;
private class Mutables
{
internal TLeftInput m_currentLeft; // The current matching left element.
internal TLeftKey m_currentLeftKey; // The current index of the matching left element.
internal HashLookup>> m_rightHashLookup; // The hash lookup.
internal ListChunk m_currentRightMatches; // Current right matches (if any).
internal int m_currentRightMatchesIndex; // Current index in the set of right matches.
internal int m_outputLoopCount;
}
//----------------------------------------------------------------------------------------
// Instantiates a new hash-join enumerator.
//
internal HashJoinQueryOperatorEnumerator(
QueryOperatorEnumerator, TLeftKey> leftSource,
QueryOperatorEnumerator, int> rightSource,
Func singleResultSelector,
Func, TOutput> groupResultSelector,
IEqualityComparer keyComparer,
CancellationToken cancellationToken)
{
Contract.Assert(leftSource != null);
Contract.Assert(rightSource != null);
Contract.Assert(singleResultSelector != null || groupResultSelector != null);
m_leftSource = leftSource;
m_rightSource = rightSource;
m_singleResultSelector = singleResultSelector;
m_groupResultSelector = groupResultSelector;
m_keyComparer = keyComparer;
m_cancellationToken = cancellationToken;
}
//---------------------------------------------------------------------------------------
// MoveNext implements all the hash-join logic noted earlier. When it is called first, it
// will execute the entire inner query tree, and build a hash-table lookup. This is the
// Building phase. Then for the first call and all subsequent calls to MoveNext, we will
// incrementally perform the Probing phase. We'll keep getting elements from the outer
// data source, looking into the hash-table we built, and enumerating the full results.
//
// This routine supports both inner and outer (group) joins. An outer join will yield a
// (possibly empty) list of matching elements from the inner instead of one-at-a-time,
// as we do for inner joins.
//
internal override bool MoveNext(ref TOutput currentElement, ref TLeftKey currentKey)
{
Contract.Assert(m_singleResultSelector != null || m_groupResultSelector != null, "expected a compiled result selector");
Contract.Assert(m_leftSource != null);
Contract.Assert(m_rightSource != null);
// BUILD phase: If we haven't built the hash-table yet, create that first.
Mutables mutables = m_mutables;
if (mutables == null)
{
mutables = m_mutables = new Mutables();
#if DEBUG
int hashLookupCount = 0;
int hashKeyCollisions = 0;
#endif
mutables.m_rightHashLookup = new HashLookup>>(m_keyComparer);
Pair rightPair = default(Pair);
int rightKeyUnused = default(int);
int i = 0;
while (m_rightSource.MoveNext(ref rightPair, ref rightKeyUnused))
{
if ((i++ & CancellationState.POLL_INTERVAL) == 0)
CancellationState.ThrowIfCanceled(m_cancellationToken);
TRightInput rightElement = rightPair.First;
THashKey rightHashKey = rightPair.Second;
// We ignore null keys.
if (rightHashKey != null)
{
#if DEBUG
hashLookupCount++;
#endif
// See if we've already stored an element under the current key. If not, we
// lazily allocate a pair to hold the elements mapping to the same key.
const int INITIAL_CHUNK_SIZE = 2;
Pair> currentValue = default(Pair>);
if (!mutables.m_rightHashLookup.TryGetValue(rightHashKey, ref currentValue))
{
currentValue = new Pair>(rightElement, null);
if (m_groupResultSelector != null)
{
// For group joins, we also add the element to the list. This makes
// it easier later to yield the list as-is.
currentValue.Second = new ListChunk(INITIAL_CHUNK_SIZE);
currentValue.Second.Add(rightElement);
}
mutables.m_rightHashLookup.Add(rightHashKey, currentValue);
}
else
{
if (currentValue.Second == null)
{
// Lazily allocate a list to hold all but the 1st value. We need to
// re-store this element because the pair is a value type.
currentValue.Second = new ListChunk(INITIAL_CHUNK_SIZE);
mutables.m_rightHashLookup[rightHashKey] = currentValue;
}
currentValue.Second.Add(rightElement);
#if DEBUG
hashKeyCollisions++;
#endif
}
}
}
#if DEBUG
TraceHelpers.TraceInfo("ParallelJoinQueryOperator::MoveNext - built hash table [count = {0}, collisions = {1}]",
hashLookupCount, hashKeyCollisions);
#endif
}
// PROBE phase: So long as the source has a next element, return the match.
ListChunk currentRightChunk = mutables.m_currentRightMatches;
if (currentRightChunk != null && mutables.m_currentRightMatchesIndex == currentRightChunk.Count)
{
currentRightChunk = mutables.m_currentRightMatches = currentRightChunk.Next;
mutables.m_currentRightMatchesIndex = 0;
}
if (mutables.m_currentRightMatches == null)
{
// We have to look up the next list of matches in the hash-table.
Pair leftPair = default(Pair);
TLeftKey leftKey = default(TLeftKey);
while (m_leftSource.MoveNext(ref leftPair, ref leftKey))
{
if ((mutables.m_outputLoopCount++ & CancellationState.POLL_INTERVAL) == 0)
CancellationState.ThrowIfCanceled(m_cancellationToken);
// Find the match in the hash table.
Pair> matchValue = default(Pair>);
TLeftInput leftElement = leftPair.First;
THashKey leftHashKey = leftPair.Second;
// Ignore null keys.
if (leftHashKey != null)
{
if (mutables.m_rightHashLookup.TryGetValue(leftHashKey, ref matchValue))
{
// We found a new match. For inner joins, we remember the list in case
// there are multiple value under this same key -- the next iteration will pick
// them up. For outer joins, we will use the list momentarily.
if (m_singleResultSelector != null)
{
mutables.m_currentRightMatches = matchValue.Second;
Contract.Assert(mutables.m_currentRightMatches == null || mutables.m_currentRightMatches.Count > 0,
"we were expecting that the list would be either null or empty");
mutables.m_currentRightMatchesIndex = 0;
// Yield the value.
currentElement = m_singleResultSelector(leftElement, matchValue.First);
currentKey = leftKey;
// If there is a list of matches, remember the left values for next time.
if (matchValue.Second != null)
{
mutables.m_currentLeft = leftElement;
mutables.m_currentLeftKey = leftKey;
}
return true;
}
}
}
// For outer joins, we always yield a result.
if (m_groupResultSelector != null)
{
// Grab the matches, or create an empty list if there are none.
IEnumerable matches = matchValue.Second;
if (matches == null)
{
matches = ParallelEnumerable.Empty();
}
// Generate the current value.
currentElement = m_groupResultSelector(leftElement, matches);
currentKey = leftKey;
return true;
}
}
// If we've reached the end of the data source, we're done.
return false;
}
// Produce the next element and increment our index within the matches.
Contract.Assert(m_singleResultSelector != null);
Contract.Assert(mutables.m_currentRightMatches != null);
Contract.Assert(0 <= mutables.m_currentRightMatchesIndex && mutables.m_currentRightMatchesIndex < mutables.m_currentRightMatches.Count);
currentElement = m_singleResultSelector(
mutables.m_currentLeft, mutables.m_currentRightMatches.m_chunk[mutables.m_currentRightMatchesIndex]);
currentKey = mutables.m_currentLeftKey;
mutables.m_currentRightMatchesIndex++;
return true;
}
protected override void Dispose(bool disposing)
{
Contract.Assert(m_leftSource != null && m_rightSource != null);
m_leftSource.Dispose();
m_rightSource.Dispose();
}
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- Mutex.cs
- ExpressionDumper.cs
- WindowPattern.cs
- DataControlLinkButton.cs
- GrammarBuilderBase.cs
- DocumentViewerAutomationPeer.cs
- EntityProxyFactory.cs
- ColumnMapCopier.cs
- SafeCoTaskMem.cs
- XmlQueryType.cs
- EventInfo.cs
- Codec.cs
- WebPartTransformer.cs
- EUCJPEncoding.cs
- DynamicPropertyReader.cs
- Config.cs
- SourceLineInfo.cs
- Comparer.cs
- ResourcePool.cs
- Misc.cs
- CustomValidator.cs
- SplashScreenNativeMethods.cs
- LinearGradientBrush.cs
- CodeTypeDelegate.cs
- ParserOptions.cs
- StatusBarPanelClickEvent.cs
- BaseComponentEditor.cs
- MessageQueueAccessControlEntry.cs
- objectresult_tresulttype.cs
- TableParagraph.cs
- SupportsEventValidationAttribute.cs
- ViewGenerator.cs
- TextSelectionProcessor.cs
- NotCondition.cs
- CodeSnippetStatement.cs
- CodeTypeDelegate.cs
- EventSourceCreationData.cs
- ApplicationSecurityInfo.cs
- SchemaObjectWriter.cs
- Propagator.JoinPropagator.SubstitutingCloneVisitor.cs
- DeviceFiltersSection.cs
- SimplePropertyEntry.cs
- StructuredTypeEmitter.cs
- GlyphRunDrawing.cs
- GridItemPatternIdentifiers.cs
- SQLDecimal.cs
- CodeCatchClauseCollection.cs
- ThrowHelper.cs
- storepermissionattribute.cs
- ProfileGroupSettings.cs
- TemplateAction.cs
- propertytag.cs
- BrowserCapabilitiesFactoryBase.cs
- DateTimeConstantAttribute.cs
- InstanceNormalEvent.cs
- SiteIdentityPermission.cs
- CannotUnloadAppDomainException.cs
- XPathNodeIterator.cs
- SoapHeaderException.cs
- Quad.cs
- SQLInt32Storage.cs
- DataStreamFromComStream.cs
- TPLETWProvider.cs
- PerfService.cs
- RowToFieldTransformer.cs
- RawStylusSystemGestureInputReport.cs
- SequenceDesignerAccessibleObject.cs
- GAC.cs
- LinkDescriptor.cs
- PointLight.cs
- ImageClickEventArgs.cs
- ToolbarAUtomationPeer.cs
- WindowsGraphicsWrapper.cs
- SkewTransform.cs
- IList.cs
- ColorConvertedBitmap.cs
- DataServiceQueryProvider.cs
- FamilyMap.cs
- _NestedMultipleAsyncResult.cs
- ObjectQueryExecutionPlan.cs
- CodeArrayIndexerExpression.cs
- DescendentsWalker.cs
- ADMembershipUser.cs
- SoundPlayerAction.cs
- LinkedList.cs
- ToolboxBitmapAttribute.cs
- AddInController.cs
- HierarchicalDataBoundControlAdapter.cs
- ListView.cs
- LogRecordSequence.cs
- SByte.cs
- WebConfigurationManager.cs
- dataprotectionpermissionattribute.cs
- MetadataCacheItem.cs
- QilPatternVisitor.cs
- DropSource.cs
- TextRangeAdaptor.cs
- newinstructionaction.cs
- SafeLibraryHandle.cs
- DataKeyPropertyAttribute.cs