Top Fields Constructors Methods
org.apache.derby.impl.store.access.sort

public Class ExternalSortFactory

extends Object
implements SortFactory, ModuleControl, ModuleSupportable, SortCostController
Class Inheritance
All Implemented Interfaces
org.apache.derby.iapi.store.access.SortCostController, org.apache.derby.iapi.services.monitor.ModuleSupportable, org.apache.derby.iapi.services.monitor.ModuleControl, org.apache.derby.iapi.store.access.conglomerate.SortFactory, org.apache.derby.iapi.store.access.conglomerate.MethodFactory
Known Direct Subclasses
org.apache.derby.impl.store.access.sort.UniqueWithDuplicateNullsExternalSortFactory
Imports
java.util.Properties, org.apache.derby.iapi.services.monitor.ModuleControl, .ModuleFactory, .ModuleSupportable, .Monitor, org.apache.derby.iapi.services.property.PropertyUtil, org.apache.derby.shared.common.sanity.SanityManager, org.apache.derby.shared.common.error.StandardException, org.apache.derby.iapi.store.access.conglomerate.Sort, .SortFactory, .MethodFactory, org.apache.derby.iapi.store.access.SortObserver, .SortCostController, .ColumnOrdering, .TransactionController, org.apache.derby.iapi.types.DataValueDescriptor, org.apache.derby.iapi.services.uuid.UUIDFactory, org.apache.derby.catalog.UUID

Field Summary

Modifier and TypeField and Description
protected static final int
protected static final int
private static final int
private int
private UUID
private static final String
private static final String
private static final int
private static final int
private int
private boolean

Constructor Summary

AccessConstructor and Description
public

Method Summary

Modifier and TypeMethod and Description
public void
boot(boolean
True if the database should be created
create
,
Properties
Configuration properties
startParams
)

Implements org.apache.derby.iapi.services.monitor.ModuleControl.boot.

Boot this module with the given properties.

public boolean
canSupport(Properties startParams)

Implements org.apache.derby.iapi.services.monitor.ModuleSupportable.canSupport.

See if this implementation can support any attributes that are listed in properties.

public void
public Sort
createSort(TransactionController tran, int segment, Properties implParameters, DataValueDescriptor[] template, ColumnOrdering[] columnOrdering, SortObserver sortObserver, boolean alreadyInOrder, long estimatedRows, int estimatedRowSize)

Implements org.apache.derby.iapi.store.access.conglomerate.SortFactory.createSort.

Create a sort.

public Properties
defaultProperties()

Implements org.apache.derby.iapi.store.access.conglomerate.MethodFactory.defaultProperties.

There are no default properties for the external sort..

protected MergeSort

Returns:

MergeSort implementation
getMergeSort
()

Returns merge sort implementation.

private static ModuleFactory
getMonitor()

Must be private so that user code can't call this entry point.

public double

Returns:

The identifier to be used to open the conglomerate later.
getSortCost
(DataValueDescriptor[]
A row which is prototypical for the sort. All rows inserted into the sort controller must have exactly the same number of columns as the template row. Every column in an inserted row must have the same type as the corresponding column in the template.
template
,
ColumnOrdering[]
An array which specifies which columns participate in ordering - see interface ColumnOrdering for details. The column referenced in the 0th columnOrdering object is compared first, then the 1st, etc.
columnOrdering
,
boolean
Indicates that the rows inserted into the sort controller will already be in order. This is used to perform aggregation only.
alreadyInOrder
,
long
The number of rows that the caller estimates will be inserted into the sort. This number must be >= 0.
estimatedInputRows
,
long
The number of rows that the caller estimates will be exported by the sorter. For instance if the sort is doing duplicate elimination and all rows are expected to be duplicates then the estimatedExportRows would be 1. If no duplicate eliminate is to be done then estimatedExportRows would be the same as estimatedInputRows. This number must be >= 0.
estimatedExportRows
,
int
The estimated average row size of the rows being sorted. This is the client portion of the rowsize, it should not attempt to calculate Store's overhead. -1 indicates that the caller has no idea (and the sorter will use 100 bytes in that case. Used by the sort to make good choices about in-memory vs. external sorting, and to size merge runs. The client is not expected to estimate the per column/ per row overhead of raw store, just to make a guess about the storage associated with each row (ie. reasonable estimates for some implementations would be 4 for int, 8 for long, 102 for char(100), 202 for varchar(200), a number out of hat for user types, ...).
estimatedRowSize
)

Implements org.apache.derby.iapi.store.access.SortCostController.getSortCost.

Short one line description of routine.

public SortCostController

Returns:

The open SortCostController.
openSortCostController
()

Implements org.apache.derby.iapi.store.access.conglomerate.SortFactory.openSortCostController.

Return an open SortCostController.

public UUID
primaryFormat()

Implements org.apache.derby.iapi.store.access.conglomerate.MethodFactory.primaryFormat.

Return the primary format that this access method supports.

public String
primaryImplementationType()

Implements org.apache.derby.iapi.store.access.conglomerate.MethodFactory.primaryImplementationType.

Return the primary implementation type for this access method.

public void
public boolean
supportsFormat(UUID formatid)

Implements org.apache.derby.iapi.store.access.conglomerate.MethodFactory.supportsFormat.

Return whether this access method supports the format supplied in the argument.

public boolean
supportsImplementation(String implementationId)

Implements org.apache.derby.iapi.store.access.conglomerate.MethodFactory.supportsImplementation.

Return whether this access method implements the implementation type given in the argument string.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

DEFAULT_MAX_MERGE_RUNback to summary
protected static final int DEFAULT_MAX_MERGE_RUN
DEFAULT_MEM_USEback to summary
protected static final int DEFAULT_MEM_USE
DEFAULT_SORTBUFFERMAXback to summary
private static final int DEFAULT_SORTBUFFERMAX
defaultSortBufferMaxback to summary
private int defaultSortBufferMax
formatUUIDback to summary
private UUID formatUUID
FORMATUUIDSTRINGback to summary
private static final String FORMATUUIDSTRING
IMPLEMENTATIONIDback to summary
private static final String IMPLEMENTATIONID
MINIMUM_SORTBUFFERMAXback to summary
private static final int MINIMUM_SORTBUFFERMAX
SORT_ROW_OVERHEADback to summary
private static final int SORT_ROW_OVERHEAD
sortBufferMaxback to summary
private int sortBufferMax
userSpecifiedback to summary
private boolean userSpecified

Constructor Detail

ExternalSortFactoryback to summary
public ExternalSortFactory()

Method Detail

bootback to summary
public void boot(boolean create, Properties startParams) throws StandardException

Implements org.apache.derby.iapi.services.monitor.ModuleControl.boot.

Doc from org.apache.derby.iapi.services.monitor.ModuleControl.boot.

Boot this module with the given properties. Creates a module instance that can be found using the findModule() methods of Monitor. The module can only be found using one of these findModule() methods once this method has returned.

An implementation's boot method can throw StandardException. If it is thrown the module is not registered by the monitor and therefore cannot be found through a findModule(). In this case the module's stop() method is not called, thus throwing this exception must free up any resources.

When create is true the contents of the properties object will be written to the service.properties of the persistent service. Thus any code that requires an entry in service.properties must explicitly place the value in this properties set using the put method.
Typically the properties object contains one or more default properties sets, which are not written out to service.properties. These default sets are how callers modify the create process. In a JDBC connection database create the first set of defaults is a properties object that contains the attributes that were set on the jdbc:derby: URL. This attributes properties set has the second default properties set as its default. This set (which could be null) contains the properties that the user set on their DriverManager.getConnection() call, and are thus not owned by Derby code, and thus must not be modified by Derby code.

When create is false the properties object contains all the properties set in the service.properties file plus a limited number of attributes from the JDBC URL attributes or connection properties set. This avoids properties set by the user compromising the boot process. An example of a property passed in from the JDBC world is the bootPassword for encrypted databases.

Code should not hold onto the passed in properties reference after boot time as its contents may change underneath it. At least after the complete boot is completed, the links to all the default sets will be removed.

Parameters
create:boolean

True if the database should be created

startParams:Properties

Configuration properties

Exceptions
StandardException:
Module cannot be started.
canSupportback to summary
public boolean canSupport(Properties startParams)

Implements org.apache.derby.iapi.services.monitor.ModuleSupportable.canSupport.

Doc from org.apache.derby.iapi.services.monitor.ModuleSupportable.canSupport.

See if this implementation can support any attributes that are listed in properties. This call may be made on a newly created instance before the boot() method has been called, or after the boot method has been called for a running module.

The module can check for attributes in the properties to see if it can fulfill the required behaviour. E.g. the raw store may define an attribute called RawStore.Recoverable. If a temporary raw store is required the property RawStore.recoverable=false would be added to the properties before calling bootServiceModule. If a raw store cannot support this attribute its canSupport method would return null. Also see the Monitor class's prologue to see how the identifier is used in looking up properties.
Actually a better way maybe to have properties of the form RawStore.Attributes.mandatory=recoverable,smallfootprint and RawStore.Attributes.requested=oltp,fast

Returns:boolean

true if this instance can be used, false otherwise.

closeback to summary
public void close()

Implements org.apache.derby.iapi.store.access.SortCostController.close.

Doc from org.apache.derby.iapi.store.access.SortCostController.close.

Close the controller.

Close the open controller. This method always succeeds, and never throws any exceptions. Callers must not use the StoreCostController after closing it; they are strongly advised to clear out the StoreCostController reference after closing.

createSortback to summary
public Sort createSort(TransactionController tran, int segment, Properties implParameters, DataValueDescriptor[] template, ColumnOrdering[] columnOrdering, SortObserver sortObserver, boolean alreadyInOrder, long estimatedRows, int estimatedRowSize) throws StandardException

Implements org.apache.derby.iapi.store.access.conglomerate.SortFactory.createSort.

Create a sort. This method could choose among different sort options, depending on the properties etc., but currently it always returns a merge sort.

Exceptions
StandardException:

Doc from org.apache.derby.iapi.store.access.conglomerate.SortFactory.createSort.

if the sort could not be opened for some reason, or if an error occurred in one of the lower level modules.

See Also
SortFactory#createSort
defaultPropertiesback to summary
public Properties defaultProperties()

Implements org.apache.derby.iapi.store.access.conglomerate.MethodFactory.defaultProperties.

There are no default properties for the external sort..

See Also
MethodFactory#defaultProperties
getMergeSortback to summary
protected MergeSort getMergeSort()

Returns merge sort implementation. Extending classes can overide this method to customize sorting.

Returns:MergeSort

MergeSort implementation

getMonitorback to summary
private static ModuleFactory getMonitor()

Must be private so that user code can't call this entry point.

getSortCostback to summary
public double getSortCost(DataValueDescriptor[] template, ColumnOrdering[] columnOrdering, boolean alreadyInOrder, long estimatedInputRows, long estimatedExportRows, int estimatedRowSize) throws StandardException

Implements org.apache.derby.iapi.store.access.SortCostController.getSortCost.

Short one line description of routine.

The sort algorithm is a N * log(N) algorithm. The following numbers on a PII, 400 MHZ machine, jdk117 with jit, insane.zip. This test is a simple "select * from table order by first_int_column. I then subtracted the time it takes to do "select * from table" from the result. number of rows elaspsed time in seconds -------------- ----------------------------- 1000 0.20 10000 10.5 100000 80.0 We assume that the formula for sort performance is of the form: performance = K * N * log(N). Solving the equation for the 1000 and 100000 case we come up with: performance = 1 + 0.08 N ln(n)

Note

Apparently, these measurements were done on a faster machine than was used for other performance measurements used by the optimizer. Experiments show that the 0.8 multiplier is off by a factor of 4 with respect to other measurements (such as the time it takes to scan a conglomerate). I am correcting the formula to use 0.32 rather than 0.08. - Jeff

RESOLVE (mikem) - this formula is very crude at the moment and will be refined later. known problems: 1) internal vs. external sort - we know that the performance of sort is discontinuous when we go from an internal to an external sort. A better model is probably a different set of contants for internal vs. external sort and some way to guess when this is going to happen. 2) current row size is never considered but is critical to performance. 3) estimatedExportRows is not used. This is a critical number to know if an internal vs. an external sort will happen.

Parameters
template:DataValueDescriptor[]

Doc from org.apache.derby.iapi.store.access.SortCostController.getSortCost.

A row which is prototypical for the sort. All rows inserted into the sort controller must have exactly the same number of columns as the template row. Every column in an inserted row must have the same type as the corresponding column in the template.

columnOrdering:ColumnOrdering[]

Doc from org.apache.derby.iapi.store.access.SortCostController.getSortCost.

An array which specifies which columns participate in ordering - see interface ColumnOrdering for details. The column referenced in the 0th columnOrdering object is compared first, then the 1st, etc.

alreadyInOrder:boolean

Doc from org.apache.derby.iapi.store.access.SortCostController.getSortCost.

Indicates that the rows inserted into the sort controller will already be in order. This is used to perform aggregation only.

estimatedInputRows:long

Doc from org.apache.derby.iapi.store.access.SortCostController.getSortCost.

The number of rows that the caller estimates will be inserted into the sort. This number must be >= 0.

estimatedExportRows:long

Doc from org.apache.derby.iapi.store.access.SortCostController.getSortCost.

The number of rows that the caller estimates will be exported by the sorter. For instance if the sort is doing duplicate elimination and all rows are expected to be duplicates then the estimatedExportRows would be 1. If no duplicate eliminate is to be done then estimatedExportRows would be the same as estimatedInputRows. This number must be >= 0.

estimatedRowSize:int

Doc from org.apache.derby.iapi.store.access.SortCostController.getSortCost.

The estimated average row size of the rows being sorted. This is the client portion of the rowsize, it should not attempt to calculate Store's overhead. -1 indicates that the caller has no idea (and the sorter will use 100 bytes in that case. Used by the sort to make good choices about in-memory vs. external sorting, and to size merge runs. The client is not expected to estimate the per column/ per row overhead of raw store, just to make a guess about the storage associated with each row (ie. reasonable estimates for some implementations would be 4 for int, 8 for long, 102 for char(100), 202 for varchar(200), a number out of hat for user types, ...).

Returns:double

The identifier to be used to open the conglomerate later.

Exceptions
StandardException:
Standard exception policy.
openSortCostControllerback to summary
public SortCostController openSortCostController() throws StandardException

Implements org.apache.derby.iapi.store.access.conglomerate.SortFactory.openSortCostController.

Return an open SortCostController.

Return an open SortCostController which can be used to ask about the estimated costs of SortController() operations.

Returns:SortCostController

The open SortCostController.

Exceptions
StandardException:
Standard exception policy.
See Also
SortCostController
primaryFormatback to summary
public UUID primaryFormat()

Implements org.apache.derby.iapi.store.access.conglomerate.MethodFactory.primaryFormat.

Doc from org.apache.derby.iapi.store.access.conglomerate.MethodFactory.primaryFormat.

Return the primary format that this access method supports. Although an access method may support more than one format, this is the usual one. the access manager will put the primary format in a hash table for fast access to the appropriate method.

See Also
MethodFactory#primaryFormat
primaryImplementationTypeback to summary
public String primaryImplementationType()

Implements org.apache.derby.iapi.store.access.conglomerate.MethodFactory.primaryImplementationType.

Doc from org.apache.derby.iapi.store.access.conglomerate.MethodFactory.primaryImplementationType.

Return the primary implementation type for this access method. Although an access method may implement more than one implementation type, this is the expected one. The access manager will put the primary implementation type in a hash table for fast access.

See Also
MethodFactory#primaryImplementationType
stopback to summary
public void stop()

Implements org.apache.derby.iapi.services.monitor.ModuleControl.stop.

Doc from org.apache.derby.iapi.services.monitor.ModuleControl.stop.

Stop the module. The module may be found via a findModule() method until some time after this method returns. Therefore the factory must be prepared to reject requests to it once it has been stopped. In addition other modules may cache a reference to the module and make requests of it after it has been stopped, these requests should be rejected as well.

supportsFormatback to summary
public boolean supportsFormat(UUID formatid)

Implements org.apache.derby.iapi.store.access.conglomerate.MethodFactory.supportsFormat.

Doc from org.apache.derby.iapi.store.access.conglomerate.MethodFactory.supportsFormat.

Return whether this access method supports the format supplied in the argument.

See Also
MethodFactory#supportsFormat
supportsImplementationback to summary
public boolean supportsImplementation(String implementationId)

Implements org.apache.derby.iapi.store.access.conglomerate.MethodFactory.supportsImplementation.

Doc from org.apache.derby.iapi.store.access.conglomerate.MethodFactory.supportsImplementation.

Return whether this access method implements the implementation type given in the argument string.

See Also
MethodFactory#supportsImplementation