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

java.lang.Object
  extended byorg.apache.derby.impl.store.access.sort.MergeSort
All Implemented Interfaces:
Sort

public final 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
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  MergeInserter inserter
          The inserter that's being used to insert rows into the sort.
protected  java.util.Vector mergeRuns
          A vector of merge runs, produced by the MergeInserter.
(package private) static java.util.Properties properties
          Properties for mergeSort
protected  Scan scan
          The scan that's being used to return rows from the sort.
protected  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).
protected  int sortBufferMax
          The maximum number of entries a sort buffer can hold.
protected  int sortBufferMin
          The minimum number of entries a sort buffer can hold.
protected  SortObserver sortObserver
          The sort observer.
protected  int state
          Maintains the current state of the sort as defined in the preceding values.
(package private) static int STATE_CLOSED
           
(package private) static int STATE_DONE_INSERTING
           
(package private) static int STATE_DONE_SCANNING
           
(package private) static int STATE_INITIALIZED
           
(package private) static int STATE_INSERTING
           
(package private) static int STATE_SCANNING
           
protected  DataValueDescriptor[] template
          The template as passed in on create.
 
Constructor Summary
MergeSort()
           
 
Method Summary
protected  boolean checkColumnOrdering(DataValueDescriptor[] template, ColumnOrdering[] columnOrdering)
          Check the column ordering against the template, making sure that each column is present in the template, implements Orderable, and is not mentioned more than once.
(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.
(package private)  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 mergeRuns)
          An inserter is closing.
(package private)  void doneScanning(Scan scan, SortBuffer sortBuffer)
           
(package private)  void doneScanning(Scan scan, SortBuffer sortBuffer, java.util.Vector 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.
 ScanController 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

static final int STATE_CLOSED
See Also:
Constant Field Values

STATE_INITIALIZED

static final int STATE_INITIALIZED
See Also:
Constant Field Values

STATE_INSERTING

static final int STATE_INSERTING
See Also:
Constant Field Values

STATE_DONE_INSERTING

static final int STATE_DONE_INSERTING
See Also:
Constant Field Values

STATE_SCANNING

static final int STATE_SCANNING
See Also:
Constant Field Values

STATE_DONE_SCANNING

static final int STATE_DONE_SCANNING
See Also:
Constant Field Values

state

protected 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,


sortObserver

protected 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

protected 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

protected 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

protected java.util.Vector 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

protected 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

protected int sortBufferMax
The maximum number of entries a sort buffer can hold.


sortBufferMin

protected int sortBufferMin
The minimum number of entries a sort buffer can hold.


properties

static java.util.Properties properties
Properties for mergeSort

Constructor Detail

MergeSort

public 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 ScanController 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

protected boolean checkColumnOrdering(DataValueDescriptor[] template,
                                      ColumnOrdering[] columnOrdering)
Check the column ordering against the template, making sure that each column is present in the template, implements Orderable, and is not mentioned more than once. Intended to be called as part of a sanity check.


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

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 mergeRuns)
An inserter is closing.


doneScanning

void doneScanning(Scan scan,
                  SortBuffer sortBuffer)

doneScanning

void doneScanning(Scan scan,
                  SortBuffer sortBuffer,
                  java.util.Vector 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

Built on Mon 2007-06-04 09:58:47+0400, from revision ???

Apache Derby V10.1 Engine Documentation - Copyright © 1997,2005 The Apache Software Foundation or its licensors, as applicable.