Class MergeSort

java.lang.Object

org.apache.derby.impl.store.access.sort.MergeSort

All Implemented Interfaces:

Sort

Direct Known Subclasses:

UniqueWithDuplicateNullsMergeSort

class MergeSort
extends Object
implements Sort

A sort implementation which does the sort in-memory if it can, but which can do an external merge sort so that it can sort an arbitrary number of rows.

Field Summary

Fields

Modifier and Type	Field	Description
protected boolean	alreadyInOrder	Whether the rows are expected to be in order on insert, as passed in on create.
protected ColumnOrdering[]	columnOrdering	The column ordering as passed in on create.
protected boolean[]	columnOrderingAscendingMap	A lookup table to speed up lookup of Ascending state of a column,
protected int[]	columnOrderingMap	A lookup table to speed up lookup of a column associated with the i'th column to compare.
protected boolean[]	columnOrderingNullsLowMap	A lookup table to speed up lookup of nulls-low ordering of a column,
private MergeInserter	inserter	The inserter that's being used to insert rows into the sort.
private Vector<Long>	mergeRuns	A vector of merge runs, produced by the MergeInserter.
(package private) static Properties	properties	Properties for mergeSort
private Scan	scan	The scan that's being used to return rows from the sort.
private SortBuffer	sortBuffer	An ordered set of the leftover rows that didn't go in the last merge run (might be all the rows if there are no merge runs).
(package private) int	sortBufferMax	The maximum number of entries a sort buffer can hold.
(package private) int	sortBufferMin	The minimum number of entries a sort buffer can hold.
(package private) SortObserver	sortObserver	The sort observer.
private int	state	Maintains the current state of the sort as defined in the preceding values.
private static final int	STATE_CLOSED
private static final int	STATE_DONE_INSERTING
private static final int	STATE_DONE_SCANNING
private static final int	STATE_INITIALIZED
private static final int	STATE_INSERTING
private static final int	STATE_SCANNING
protected DataValueDescriptor[]	template	The template as passed in on create.

Constructor Summary

Constructors

Constructor	Description
MergeSort()

Method Summary

Modifier and Type	Method	Description
private boolean	checkColumnOrdering(DataValueDescriptor[] template, ColumnOrdering[] columnOrdering)	Check the column ordering against the template, making sure that each column is present in the template, is not mentioned more than once, and that the columns isn't null.
(package private) void	checkColumnTypes(DataValueDescriptor[] row)	Check that the columns in the row agree with the columns in the template, both in number and in type.
protected int	compare(DataValueDescriptor[] r1, DataValueDescriptor[] r2)
(package private) long	createMergeRun(TransactionManager tran, SortBuffer sortBuffer)	Remove all the rows from the sort buffer and store them in a temporary conglomerate.
(package private) void	doneInserting(MergeInserter inserter, SortBuffer sortBuffer, Vector<Long> mergeRuns)	An inserter is closing.
(package private) void	doneScanning(Scan scan, SortBuffer sortBuffer)
(package private) void	doneScanning(Scan scan, SortBuffer sortBuffer, Vector<Long> mergeRuns)
void	drop(TransactionController tran)	Drop the sort.
(package private) void	dropMergeRuns(TransactionManager tran)	Get rid of the merge runs, if there are any.
void	initialize(DataValueDescriptor[] template, ColumnOrdering[] columnOrdering, SortObserver sortObserver, boolean alreadyInOrder, long estimatedRows, int sortBufferMax)	Go from the CLOSED to the INITIALIZED state.
private void	multiStageMerge(TransactionManager tran)
SortController	open(TransactionManager tran)	Open a sort controller.
ScanControllerRowSource	openSortRowSource(TransactionManager tran)	Open a row source to get rows out of the sorter.
ScanManager	openSortScan(TransactionManager tran, boolean hold)	Open a scan controller.

Methods inherited from class Object

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

Field Details

STATE_CLOSED

private static final int STATE_CLOSED

See Also:

• Constant Field Values

STATE_INITIALIZED

private static final int STATE_INITIALIZED

See Also:

• Constant Field Values

STATE_INSERTING

private static final int STATE_INSERTING

See Also:

• Constant Field Values

STATE_DONE_INSERTING

private static final int STATE_DONE_INSERTING

See Also:

• Constant Field Values

STATE_SCANNING

private static final int STATE_SCANNING

See Also:

• Constant Field Values

STATE_DONE_SCANNING

private static final int STATE_DONE_SCANNING

See Also:

• Constant Field Values

state

private int state

Maintains the current state of the sort as defined in the preceding values. Sorts start off and end up closed.

template

protected DataValueDescriptor[] template

The template as passed in on create. Valid when the state is INITIALIZED through SCANNING, null otherwise.

columnOrdering

protected ColumnOrdering[] columnOrdering

The column ordering as passed in on create. Valid when the state is INITIALIZED through SCANNING, null otherwise. May be null if there is no column ordering - this means that all rows are considered to be duplicates, and the sort will only emit a single row.

columnOrderingMap

protected int[] columnOrderingMap

A lookup table to speed up lookup of a column associated with the i'th column to compare. To find the column id to compare as the i'th column look in columnOrderingMap[i].

columnOrderingAscendingMap

protected boolean[] columnOrderingAscendingMap

A lookup table to speed up lookup of Ascending state of a column,

columnOrderingNullsLowMap

protected boolean[] columnOrderingNullsLowMap

A lookup table to speed up lookup of nulls-low ordering of a column,

sortObserver

SortObserver sortObserver

The sort observer. May be null. Used as a callback.

alreadyInOrder

protected boolean alreadyInOrder

Whether the rows are expected to be in order on insert, as passed in on create.

inserter

private MergeInserter inserter

The inserter that's being used to insert rows into the sort. This field is only valid when the state is INSERTING.

scan

private Scan scan

The scan that's being used to return rows from the sort. This field is only valid when the state is SCANNING.

mergeRuns

private Vector<Long> mergeRuns

A vector of merge runs, produced by the MergeInserter. Might be null if no merge runs were produced. It is a vector of container ids.

sortBuffer

private SortBuffer sortBuffer

An ordered set of the leftover rows that didn't go in the last merge run (might be all the rows if there are no merge runs).

sortBufferMax

int sortBufferMax

The maximum number of entries a sort buffer can hold.

sortBufferMin

int sortBufferMin

The minimum number of entries a sort buffer can hold.

properties

static Properties properties

Properties for mergeSort

Constructor Details

MergeSort

MergeSort()

Method Details

open

public SortController open(TransactionManager tran)
                    throws StandardException

Open a sort controller.

This implementation only supports a single sort controller per sort.

Specified by:

open in interface Sort

Throws:

StandardException - Standard exception policy.

See Also:

• Sort.open(TransactionManager)

openSortScan

public ScanManager openSortScan(TransactionManager tran,
 boolean hold)
                         throws StandardException

Open a scan controller.

Specified by:

openSortScan in interface Sort

Throws:

StandardException - Standard exception policy.

See Also:

• Sort.openSortScan(TransactionManager, boolean)

openSortRowSource

public ScanControllerRowSource openSortRowSource(TransactionManager tran)
                                          throws StandardException

Open a row source to get rows out of the sorter.

Specified by:

openSortRowSource in interface Sort

Throws:

StandardException - Standard exception policy.

See Also:

• Sort.openSortRowSource(TransactionManager)

drop

public void drop(TransactionController tran)
          throws StandardException

Drop the sort.

Specified by:

drop in interface Sort

Throws:

StandardException

See Also:

• Sort.drop(TransactionController)

checkColumnOrdering

private boolean checkColumnOrdering(DataValueDescriptor[] template,
 ColumnOrdering[] columnOrdering)

Check the column ordering against the template, making sure that each column is present in the template, is not mentioned more than once, and that the columns isn't null.

Intended to be called as part of a sanity check. All columns are orderable, since DataValueDescriptor extends Orderable.

Returns:

true if the ordering is valid, false if not.

checkColumnTypes

void checkColumnTypes(DataValueDescriptor[] row)
               throws StandardException

Check that the columns in the row agree with the columns in the template, both in number and in type.

XXX (nat) Currently checks that the classes implementing each column are the same -- is this right?

Throws:

StandardException

compare

protected int compare(DataValueDescriptor[] r1,
 DataValueDescriptor[] r2)
               throws StandardException

Throws:

StandardException

initialize

public void initialize(DataValueDescriptor[] template,
 ColumnOrdering[] columnOrdering,
 SortObserver sortObserver,
 boolean alreadyInOrder,
 long estimatedRows,
 int sortBufferMax)
                throws StandardException

Go from the CLOSED to the INITIALIZED state.

Throws:

StandardException

doneInserting

void doneInserting(MergeInserter inserter,
 SortBuffer sortBuffer,
 Vector<Long> mergeRuns)

An inserter is closing.

doneScanning

void doneScanning(Scan scan,
 SortBuffer sortBuffer)

doneScanning

void doneScanning(Scan scan,
 SortBuffer sortBuffer,
 Vector<Long> mergeRuns)

dropMergeRuns

void dropMergeRuns(TransactionManager tran)

Get rid of the merge runs, if there are any. Must not cause any errors because it's called during error processing.

multiStageMerge

private void multiStageMerge(TransactionManager tran)
                      throws StandardException

Throws:

StandardException

createMergeRun

long createMergeRun(TransactionManager tran,
 SortBuffer sortBuffer)
             throws StandardException

Remove all the rows from the sort buffer and store them in a temporary conglomerate. The temporary conglomerate is a "merge run". Returns the container id of the merge run.

Throws:

StandardException