ExternalSortMerger Class Reference

ExternalSortMerger manages the process of merging stored runs. More...

#include <ExternalSortMerger.h>

Inheritance diagram for ExternalSortMerger:


Public Member Functions
	ExternalSortMerger (ExternalSortInfo &info)
virtual	~ExternalSortMerger ()
void	initRunAccess ()
	Initializes state used to access stored runs.
void	startMerge (std::vector< SharedSegStreamAllocation >::iterator pStoredRun, uint nRunsToMerge)
	Begins merge.
void	releaseResources ()
	Releases any resources acquired by this merger.
virtual ExternalSortFetchArray &	bindFetchArray ()
	Binds the fetch array which will be used implicitly by subsequent calls to fetch().
virtual ExternalSortRC	fetch (uint nTuplesRequested)
	Fetches tuples via the previously bound fetch array.
Private Member Functions
uint	heapParent (uint i)
uint	heapLeft (uint i)
uint	heapRight (uint i)
void	heapExchange (uint i, uint j)
void	heapify (uint i)
void	heapBuild ()
ExternalSortRC	checkFetch ()
ExternalSortMergeInfo &	getMergeHigh ()
Private Attributes
ExternalSortInfo &	sortInfo
	Global information.
boost::scoped_array< SharedExternalSortRunAccessor >	ppRunAccessors
	Array of accessors for runs to be merged.
boost::scoped_array< ExternalSortFetchArray * >	ppFetchArrays
	Array of fetch bindings corresponding to ppRunAccessors.
boost::scoped_array< uint >	pOrds
	Array of something-or-others corresponding to ppRunAccessors.
uint	nMergeMemPages
	Number of memory pages available for merging.
uint	nRuns
	Number of runs being merged.
boost::scoped_array< ExternalSortMergeInfo >	mergeInfo
	Array of info on runs being merged.
ExternalSortFetchArray	fetchArray
	Array used to return fetch results.
PBuffer	ppTupleBuffers [EXTSORT_FETCH_ARRAY_SIZE]
	Pointer array used to return fetch results.
TupleAccessor	tupleAccessor
TupleAccessor	tupleAccessor2
TupleProjectionAccessor	keyAccessor
TupleProjectionAccessor	keyAccessor2
TupleData	keyData
TupleData	keyData2

Detailed Description

ExternalSortMerger manages the process of merging stored runs.

Definition at line 63 of file ExternalSortMerger.h.

Constructor & Destructor Documentation

ExternalSortMerger::ExternalSortMerger ( ExternalSortInfo & info ) [explicit]

Definition at line 32 of file ExternalSortMerger.cpp.

References TupleProjectionAccessor::bind(), TupleData::compute(), TupleAccessor::compute(), fetchArray, keyAccessor, keyAccessor2, keyData, keyData2, ExternalSortInfo::keyDesc, ExternalSortInfo::keyProj, mergeInfo, nMergeMemPages, nRuns, ExternalSortInfo::nSortMemPages, pOrds, ppFetchArrays, ppRunAccessors, ppTupleBuffers, ExternalSortFetchArray::ppTupleBuffers, sortInfo, tupleAccessor, tupleAccessor2, and ExternalSortInfo::tupleDesc.

00033     : sortInfo(sortInfoIn)
00034 {
00035     nRuns = 0;
00036 
00037     tupleAccessor.compute(sortInfo.tupleDesc);
00038     tupleAccessor2.compute(sortInfo.tupleDesc);
00039 
00040     keyData.compute(sortInfo.keyDesc);
00041     keyData2 = keyData;
00042 
00043     keyAccessor.bind(tupleAccessor,sortInfo.keyProj);
00044     keyAccessor2.bind(tupleAccessor2,sortInfo.keyProj);
00045 
00046     nMergeMemPages = sortInfo.nSortMemPages + 1;
00047 
00048     ppRunAccessors.reset(new SharedExternalSortRunAccessor[nMergeMemPages]);
00049     ppFetchArrays.reset(new ExternalSortFetchArray *[nMergeMemPages]);
00050 
00051     pOrds.reset(new uint[nMergeMemPages]);
00052     memset(pOrds.get(),0,sizeof(uint) * nMergeMemPages);
00053 
00054     mergeInfo.reset(new ExternalSortMergeInfo[nMergeMemPages]);
00055 
00056     fetchArray.ppTupleBuffers = &(ppTupleBuffers[0]);
00057 }

ExternalSortMerger::~ExternalSortMerger ( ) [virtual]

Definition at line 59 of file ExternalSortMerger.cpp.

References releaseResources().

00060 {
00061     releaseResources();
00062 }

Member Function Documentation

uint ExternalSortMerger::heapParent ( uint i ) [inline, private]

Definition at line 110 of file ExternalSortMerger.cpp.

00111 {
00112     return (i >> 1);
00113 }

uint ExternalSortMerger::heapLeft ( uint i ) [inline, private]

Definition at line 115 of file ExternalSortMerger.cpp.

Referenced by heapify().

00116 {
00117     return (i << 1);
00118 }

uint ExternalSortMerger::heapRight ( uint i ) [inline, private]

Definition at line 120 of file ExternalSortMerger.cpp.

Referenced by heapify().

00121 {
00122     return (i << 1) + 1;
00123 }

void ExternalSortMerger::heapExchange	(	uint	i,
		uint	j
	)			`[inline, private]`

Definition at line 125 of file ExternalSortMerger.cpp.

References mergeInfo.

Referenced by checkFetch(), and heapify().

00126 {
00127     std::swap(mergeInfo[i],mergeInfo[j]);
00128 }

void ExternalSortMerger::heapify ( uint i ) [private]

Definition at line 135 of file ExternalSortMerger.cpp.

References ExternalSortInfo::compareKeys(), heapExchange(), heapLeft(), heapRight(), keyAccessor, keyAccessor2, keyData, keyData2, mergeInfo, nRuns, TupleAccessor::setCurrentTupleBuf(), sortInfo, tupleAccessor, tupleAccessor2, and TupleProjectionAccessor::unmarshal().

Referenced by fetch(), and heapBuild().

00136 {
00137     uint l, r, highest = i;
00138 
00139     l = heapLeft(i);
00140     r = heapRight(i);
00141 
00142     if (l <= nRuns) {
00143         tupleAccessor.setCurrentTupleBuf(mergeInfo[l].val);
00144         tupleAccessor2.setCurrentTupleBuf(mergeInfo[i].val);
00145         keyAccessor.unmarshal(keyData);
00146         keyAccessor2.unmarshal(keyData2);
00147         if (sortInfo.compareKeys(keyData,keyData2) < 0) {
00148             highest = l;
00149         }
00150     }
00151 
00152     if (r <= nRuns) {
00153         tupleAccessor.setCurrentTupleBuf(mergeInfo[r].val);
00154         tupleAccessor2.setCurrentTupleBuf(mergeInfo[highest].val);
00155         keyAccessor.unmarshal(keyData);
00156         keyAccessor2.unmarshal(keyData2);
00157         if (sortInfo.compareKeys(keyData,keyData2) < 0) {
00158             highest = r;
00159         }
00160     }
00161 
00162     if (highest != i) {
00163         heapExchange(highest,i);
00164         heapify(highest);
00165     }
00166 }

void ExternalSortMerger::heapBuild ( ) [private]

Definition at line 168 of file ExternalSortMerger.cpp.

References heapify(), and nRuns.

Referenced by startMerge().

00169 {
00170     for (uint i = (nRuns / 2); i > 0; i--) {
00171         heapify(i);
00172     }
00173 }

ExternalSortRC ExternalSortMerger::checkFetch ( ) [private]

Definition at line 175 of file ExternalSortMerger.cpp.

References EXTSORT_ENDOFDATA, EXTSORT_FETCH_ARRAY_SIZE, EXTSORT_SUCCESS, getMergeHigh(), heapExchange(), nRuns, pOrds, ppFetchArrays, ppRunAccessors, and ExternalSortMergeInfo::runOrd.

Referenced by fetch().

00176 {
00177     if (nRuns == 0) {
00178         return EXTSORT_ENDOFDATA;
00179     }
00180     if (pOrds[getMergeHigh().runOrd]
00181         >= ppFetchArrays[getMergeHigh().runOrd]->nTuples)
00182     {
00183         ExternalSortRC rc = ppRunAccessors[getMergeHigh().runOrd]->fetch(
00184             EXTSORT_FETCH_ARRAY_SIZE);
00185         if (rc != EXTSORT_SUCCESS) {
00186             assert(rc == EXTSORT_ENDOFDATA);
00187             heapExchange(1, nRuns);
00188             if (--nRuns == 0) {
00189                 return EXTSORT_ENDOFDATA;
00190             }
00191         } else {
00192             pOrds[getMergeHigh().runOrd] = 0;
00193         }
00194     }
00195 
00196     return EXTSORT_SUCCESS;
00197 }

ExternalSortMergeInfo & ExternalSortMerger::getMergeHigh ( ) [inline, private]

Definition at line 130 of file ExternalSortMerger.cpp.

References mergeInfo.

Referenced by checkFetch(), and fetch().

00131 {
00132     return mergeInfo[1];
00133 }

void ExternalSortMerger::initRunAccess ( )

Initializes state used to access stored runs.

Definition at line 64 of file ExternalSortMerger.cpp.

References nMergeMemPages, ppFetchArrays, ppRunAccessors, and sortInfo.

00065 {
00066     for (uint i = 1; i < nMergeMemPages; i++) {
00067         ppRunAccessors[i].reset(new ExternalSortRunAccessor(sortInfo));
00068         ppRunAccessors[i]->initRead();
00069         ppFetchArrays[i] = &(ppRunAccessors[i]->bindFetchArray());
00070     }
00071 }

void ExternalSortMerger::startMerge	(	std::vector< SharedSegStreamAllocation >::iterator	pStoredRun,
		uint	nRunsToMerge
	)

Begins merge.

Parameters:

	pStoredRun	iterator to first run to merge
	nRunsToMerge	number of runs to merge

Definition at line 81 of file ExternalSortMerger.cpp.

References EXTSORT_FETCH_ARRAY_SIZE, fetchArray, heapBuild(), mergeInfo, nMergeMemPages, nRuns, ExternalSortFetchArray::nTuples, pOrds, ppFetchArrays, and ppRunAccessors.

00084 {
00085     assert (nRunsToMerge < nMergeMemPages);
00086 
00087     nRuns = nRunsToMerge;
00088 
00089     for (uint i = 1; i < nMergeMemPages; i++) {
00090         ppRunAccessors[i]->resetRead();
00091         pOrds[i] = 0;
00092     }
00093 
00094     for (uint i = 1; i <= nRuns; i++) {
00095         ppRunAccessors[i]->startRead(pStoredRun[i - 1]);
00096         ppRunAccessors[i]->fetch(EXTSORT_FETCH_ARRAY_SIZE);
00097         mergeInfo[i].val = ppFetchArrays[i]->ppTupleBuffers[0];
00098         mergeInfo[i].runOrd = i;
00099     }
00100     fetchArray.nTuples = 0;
00101 
00102     heapBuild();
00103 }

void ExternalSortMerger::releaseResources ( )

Releases any resources acquired by this merger.

Definition at line 73 of file ExternalSortMerger.cpp.

References mergeInfo, pOrds, ppFetchArrays, and ppRunAccessors.

Referenced by ~ExternalSortMerger().

00074 {
00075     ppRunAccessors.reset();
00076     ppFetchArrays.reset();
00077     pOrds.reset();
00078     mergeInfo.reset();
00079 }

ExternalSortFetchArray & ExternalSortMerger::bindFetchArray ( ) [virtual]

Binds the fetch array which will be used implicitly by subsequent calls to fetch().

Returns:: bound fetch array

Implements ExternalSortSubStream.

Definition at line 105 of file ExternalSortMerger.cpp.

References fetchArray.

00106 {
00107     return fetchArray;
00108 }

ExternalSortRC ExternalSortMerger::fetch ( uint nTuplesRequested ) [virtual]

Fetches tuples via the previously bound fetch array.

Parameters:

nTuplesRequested

maximum number of tuples to be returned from fetch (actual count may be less at callee's discretion; this does not indicate end of stream)

Returns:: result of fetch (either EXTSORT_ENDOFDATA or EXTSORT_SUCCESS)

Implements ExternalSortSubStream.

Definition at line 199 of file ExternalSortMerger.cpp.

References ExecStream::checkAbort(), checkFetch(), EXTSORT_FETCH_ARRAY_SIZE, EXTSORT_SUCCESS, fetchArray, getMergeHigh(), heapify(), ExternalSortFetchArray::nTuples, pOrds, ppFetchArrays, ExternalSortFetchArray::ppTupleBuffers, ExternalSortMergeInfo::runOrd, sortInfo, ExternalSortInfo::stream, and ExternalSortMergeInfo::val.

00200 {
00201     sortInfo.stream.checkAbort();
00202 
00203     if (nTuplesRequested > EXTSORT_FETCH_ARRAY_SIZE) {
00204         nTuplesRequested = EXTSORT_FETCH_ARRAY_SIZE;
00205     }
00206 
00207     ExternalSortRC rc = checkFetch();
00208     if (rc != EXTSORT_SUCCESS) {
00209         // error handling will be done by checkFetch here
00210         return rc;
00211     }
00212 
00213     fetchArray.nTuples = 0;
00214     do {
00215         getMergeHigh().val =
00216             ppFetchArrays[getMergeHigh().runOrd]->ppTupleBuffers[
00217                 pOrds[getMergeHigh().runOrd]];
00218 
00219         heapify(1);
00220 
00221         fetchArray.ppTupleBuffers[fetchArray.nTuples] = getMergeHigh().val;
00222         fetchArray.nTuples++;
00223         nTuplesRequested--;
00224 
00225         pOrds[getMergeHigh().runOrd]++;
00226     } while (nTuplesRequested
00227               && (pOrds[getMergeHigh().runOrd]
00228                   < ppFetchArrays[getMergeHigh().runOrd]->nTuples));
00229 
00230     return EXTSORT_SUCCESS;
00231 }