Class MergeSort
- java.lang.Object
-
- org.apache.derby.impl.store.access.sort.MergeSort
-
- All Implemented Interfaces:
Sort
- Direct Known Subclasses:
UniqueWithDuplicateNullsMergeSort
class MergeSort extends java.lang.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 java.util.Vector<java.lang.Long>
mergeRuns
A vector of merge runs, produced by the MergeInserter.(package private) static java.util.Properties
properties
Properties for mergeSortprivate 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 int
STATE_CLOSED
private static int
STATE_DONE_INSERTING
private static int
STATE_DONE_SCANNING
private static int
STATE_INITIALIZED
private static int
STATE_INSERTING
private static int
STATE_SCANNING
protected DataValueDescriptor[]
template
The template as passed in on create.
-
Constructor Summary
Constructors Constructor Description MergeSort()
-
Method Summary
All Methods Instance Methods Concrete Methods 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'tnull
.(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, java.util.Vector<java.lang.Long> mergeRuns)
An inserter is closing.(package private) void
doneScanning(Scan scan, SortBuffer sortBuffer)
(package private) void
doneScanning(Scan scan, SortBuffer sortBuffer, java.util.Vector<java.lang.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.
-
-
-
Field Detail
-
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 java.util.Vector<java.lang.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 java.util.Properties properties
Properties for mergeSort
-
-
Method Detail
-
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 interfaceSort
- Throws:
StandardException
- Standard exception policy.- See Also:
Sort.open(org.apache.derby.iapi.store.access.conglomerate.TransactionManager)
-
openSortScan
public ScanManager openSortScan(TransactionManager tran, boolean hold) throws StandardException
Open a scan controller.- Specified by:
openSortScan
in interfaceSort
- Throws:
StandardException
- Standard exception policy.- See Also:
Sort.openSortScan(org.apache.derby.iapi.store.access.conglomerate.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 interfaceSort
- Throws:
StandardException
- Standard exception policy.- See Also:
Sort.openSortRowSource(org.apache.derby.iapi.store.access.conglomerate.TransactionManager)
-
drop
public void drop(TransactionController tran) throws StandardException
Drop the sort.- Specified by:
drop
in interfaceSort
- Throws:
StandardException
- See Also:
Sort.drop(org.apache.derby.iapi.store.access.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'tnull
.Intended to be called as part of a sanity check. All columns are orderable, since
DataValueDescriptor
extendsOrderable
.- 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, java.util.Vector<java.lang.Long> mergeRuns)
An inserter is closing.
-
doneScanning
void doneScanning(Scan scan, SortBuffer sortBuffer)
-
doneScanning
void doneScanning(Scan scan, SortBuffer sortBuffer, java.util.Vector<java.lang.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
-
-