MergeSort (Apache Derby V10.14 Internals)

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 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 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()

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'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, 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.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- 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
- Constructor Detail
  - MergeSort
```
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 interface Sort
    
    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 interface Sort
    
    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 interface Sort
    
    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 interface Sort
    
    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'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,
                   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

Class MergeSort

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

STATE_CLOSED

STATE_INITIALIZED

STATE_INSERTING

STATE_DONE_INSERTING

STATE_SCANNING

STATE_DONE_SCANNING

state

template

columnOrdering

columnOrderingMap

columnOrderingAscendingMap

columnOrderingNullsLowMap

sortObserver

alreadyInOrder

inserter

scan

mergeRuns

sortBuffer

sortBufferMax

sortBufferMin

properties

Constructor Detail

MergeSort

Method Detail

open

openSortScan

openSortRowSource

drop

checkColumnOrdering

checkColumnTypes

compare

initialize

doneInserting

doneScanning

doneScanning

dropMergeRuns

multiStageMerge

createMergeRun