org.apache.derby.iapi.store.access
Class BackingStoreHashtable

java.lang.Object
  extended by org.apache.derby.iapi.store.access.BackingStoreHashtable
Direct Known Subclasses:
BackingStoreHashTableFromScan

public class BackingStoreHashtable
extends java.lang.Object

A BackingStoreHashtable is a utility class which will store a set of rows into an in memory hash table, or overflow the hash table to a tempory on disk structure.

All rows must contain the same number of columns, and the column at position N of all the rows must have the same format id. If the BackingStoreHashtable needs to be overflowed to disk, then an arbitrary row will be chosen and used as a template for creating the underlying overflow container.

The hash table will be built logically as follows (actual implementation may differ). The important points are that the hash value is the standard java hash value on the row[key_column_numbers[0], if key_column_numbers.length is 1, or row[key_column_numbers[0, 1, ...]] if key_column_numbers.length > 1, and that duplicate detection is done by the standard java duplicate detection provided by java.util.Hashtable.

import java.util.Hashtable;

hash_table = new Hashtable();

Object[] row;
boolean  needsToClone = rowSource.needsToClone();

while((row = rowSource.getNextRowFromRowSource()) != null)
{
    if (needsToClone)
        row = clone_row_from_row(row);

    Object key = KeyHasher.buildHashKey(row, key_column_numbers);

    if ((duplicate_value = 
        hash_table.put(key, row)) != null)
    {
        Vector row_vec;

        // inserted a duplicate
        if ((duplicate_value instanceof vector))
        {
            row_vec = (Vector) duplicate_value;
        }
        else
        {
            // allocate vector to hold duplicates
            row_vec = new Vector(2);

            // insert original row into vector
            row_vec.addElement(duplicate_value);

            // put the vector as the data rather than the row
            hash_table.put(key, row_vec);
        }

        // insert new row into vector
        row_vec.addElement(row);
    }
}


Nested Class Summary
private  class BackingStoreHashtable.BackingStoreHashtableEnumeration
           
 
Field Summary
private static int ARRAY_LIST_SIZE
          The estimated number of bytes used by ArrayList(0)
private  java.util.Properties auxillary_runtimestats
           
private  DiskHashtable diskHashtable
           
private  java.util.HashMap hash_table
           
private  long inmemory_rowcnt
           
private  boolean keepAfterCommit
           
private  int[] key_column_numbers
           
private  long max_inmemory_rowcnt
           
private  long max_inmemory_size
           
private  boolean remove_duplicates
           
private  RowSource row_source
           
private  boolean skipNullKeyColumns
           
private  TransactionController tc
          Fields of the class
 
Constructor Summary
private BackingStoreHashtable()
          Constructors for This class:
  BackingStoreHashtable(TransactionController tc, RowSource row_source, int[] key_column_numbers, boolean remove_duplicates, long estimated_rowcnt, long max_inmemory_rowcnt, int initialCapacity, float loadFactor, boolean skipNullKeyColumns, boolean keepAfterCommit)
          Create the BackingStoreHashtable from a row source.
 
Method Summary
private  void add_row_to_hash_table(DataValueDescriptor[] row, boolean needsToClone)
          Do the work to add one row to the hash table.
private static DataValueDescriptor[] cloneRow(DataValueDescriptor[] old_row)
          Return a cloned copy of the row.
 void close()
          Close the BackingStoreHashtable.
private  void doSpaceAccounting(DataValueDescriptor[] row, boolean firstDuplicate)
           
 java.util.Enumeration elements()
          Return an Enumeration that can be used to scan entire table.
 java.lang.Object get(java.lang.Object key)
          get data associated with given key.
 void getAllRuntimeStats(java.util.Properties prop)
          Return runtime stats to caller by adding them to prop.
private  long getEstimatedMemUsage(DataValueDescriptor[] row)
          Take a row and return an estimate as to how much memory that row will consume.
private  DataValueDescriptor[] getNextRowFromRowSource()
          Call method to either get next row or next row with non-null key columns.
 boolean putRow(boolean needsToClone, DataValueDescriptor[] row)
          Put a row into the hash table.
 java.lang.Object remove(java.lang.Object key)
          remove a row from the hash table.
 void setAuxillaryRuntimeStats(java.util.Properties prop)
          Set the auxillary runtime stats.
(package private) static DataValueDescriptor[] shallowCloneRow(DataValueDescriptor[] old_row)
          Return a shallow cloned row
 int size()
          Return number of unique rows in the hash table.
private  boolean spillToDisk(DataValueDescriptor[] row)
          Determine whether a new row should be spilled to disk and, if so, do it.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

tc

private TransactionController tc
Fields of the class


hash_table

private java.util.HashMap hash_table

key_column_numbers

private int[] key_column_numbers

remove_duplicates

private boolean remove_duplicates

skipNullKeyColumns

private boolean skipNullKeyColumns

auxillary_runtimestats

private java.util.Properties auxillary_runtimestats

row_source

private RowSource row_source

max_inmemory_rowcnt

private long max_inmemory_rowcnt

inmemory_rowcnt

private long inmemory_rowcnt

max_inmemory_size

private long max_inmemory_size

keepAfterCommit

private boolean keepAfterCommit

ARRAY_LIST_SIZE

private static final int ARRAY_LIST_SIZE
The estimated number of bytes used by ArrayList(0)


diskHashtable

private DiskHashtable diskHashtable
Constructor Detail

BackingStoreHashtable

private BackingStoreHashtable()
Constructors for This class:


BackingStoreHashtable

public BackingStoreHashtable(TransactionController tc,
                             RowSource row_source,
                             int[] key_column_numbers,
                             boolean remove_duplicates,
                             long estimated_rowcnt,
                             long max_inmemory_rowcnt,
                             int initialCapacity,
                             float loadFactor,
                             boolean skipNullKeyColumns,
                             boolean keepAfterCommit)
                      throws StandardException
Create the BackingStoreHashtable from a row source.

This routine drains the RowSource. The performance characteristics depends on the number of rows inserted and the parameters to the constructor.

If the number of rows is <= "max_inmemory_rowcnt", then the rows are inserted into a java.util.HashMap. In this case no TransactionController is necessary, a "null" tc is valid.

If the number of rows is > "max_inmemory_rowcnt", then the rows will be all placed in some sort of Access temporary file on disk. This case requires a valid TransactionController.

Parameters:
tc - An open TransactionController to be used if the hash table needs to overflow to disk.
row_source - RowSource to read rows from.
key_column_numbers - The column numbers of the columns in the scan result row to be the key to the HashMap. "0" is the first column in the scan result row (which may be different than the first row in the table of the scan).
remove_duplicates - Should the HashMap automatically remove duplicates, or should it create the list of duplicates?
estimated_rowcnt - The estimated number of rows in the hash table. Pass in -1 if there is no estimate.
max_inmemory_rowcnt - The maximum number of rows to insert into the inmemory Hash table before overflowing to disk. Pass in -1 if there is no maximum.
initialCapacity - If not "-1" used to initialize the java HashMap
loadFactor - If not "-1" used to initialize the java HashMap
skipNullKeyColumns - Skip rows with a null key column, if true.
keepAfterCommit - If true the hash table is kept after a commit, if false the hash table is dropped on the next commit.
Throws:
StandardException - Standard exception policy.
Method Detail

getNextRowFromRowSource

private DataValueDescriptor[] getNextRowFromRowSource()
                                               throws StandardException
Call method to either get next row or next row with non-null key columns.

Throws:
StandardException - Standard exception policy.

cloneRow

private static DataValueDescriptor[] cloneRow(DataValueDescriptor[] old_row)
                                       throws StandardException
Return a cloned copy of the row.

Returns:
The cloned row row to use.
Throws:
StandardException - Standard exception policy.

shallowCloneRow

static DataValueDescriptor[] shallowCloneRow(DataValueDescriptor[] old_row)
                                      throws StandardException
Return a shallow cloned row

Returns:
The cloned row row to use.
Throws:
StandardException - Standard exception policy.

add_row_to_hash_table

private void add_row_to_hash_table(DataValueDescriptor[] row,
                                   boolean needsToClone)
                            throws StandardException
Do the work to add one row to the hash table.

Parameters:
row - Row to add to the hash table.
needsToClone - If the row needs to be cloned
Throws:
StandardException - Standard exception policy.

doSpaceAccounting

private void doSpaceAccounting(DataValueDescriptor[] row,
                               boolean firstDuplicate)

spillToDisk

private boolean spillToDisk(DataValueDescriptor[] row)
                     throws StandardException
Determine whether a new row should be spilled to disk and, if so, do it.

Parameters:
row -
Returns:
true if the row was spilled to disk, false if not
Throws:
StandardException - Standard exception policy.

getEstimatedMemUsage

private long getEstimatedMemUsage(DataValueDescriptor[] row)
Take a row and return an estimate as to how much memory that row will consume.

Parameters:
row - The row for which we want to know the memory usage.
Returns:
A guess as to how much memory the current row will use.

close

public void close()
           throws StandardException
Close the BackingStoreHashtable.

Perform any necessary cleanup after finishing with the hashtable. Will deallocate/dereference objects as necessary. If the table has gone to disk this will drop any on disk files used to support the hash table.

Throws:
StandardException - Standard exception policy.

elements

public java.util.Enumeration elements()
                               throws StandardException
Return an Enumeration that can be used to scan entire table.

RESOLVE - is it worth it to support this routine when we have a disk overflow hash table?

Returns:
The Enumeration.
Throws:
StandardException - Standard exception policy.

get

public java.lang.Object get(java.lang.Object key)
                     throws StandardException
get data associated with given key.

There are 2 different types of objects returned from this routine.

In both cases, the key value is either the object stored in row[key_column_numbers[0]], if key_column_numbers.length is 1, otherwise it is a KeyHasher containing the objects stored in row[key_column_numbers[0, 1, ...]]. For every qualifying unique row value an entry is placed into the hash table.

For row values with duplicates, the value of the data is a list of rows.

The caller will have to call "instanceof" on the data value object if duplicates are expected, to determine if the data value of the hash table entry is a row or is a list of rows.

The BackingStoreHashtable "owns" the objects returned from the get() routine. They remain valid until the next access to the BackingStoreHashtable. If the client needs to keep references to these objects, it should clone copies of the objects. A valid BackingStoreHashtable can place all rows into a disk based conglomerate, declare a row buffer and then reuse that row buffer for every get() call.

Parameters:
key - The key to hash on.
Returns:
The value to which the key is mapped in this hashtable; null if the key is not mapped to any value in this hashtable.
Throws:
StandardException - Standard exception policy.

getAllRuntimeStats

public void getAllRuntimeStats(java.util.Properties prop)
                        throws StandardException
Return runtime stats to caller by adding them to prop.

Parameters:
prop - The set of properties to append to.
Throws:
StandardException - Standard exception policy.

remove

public java.lang.Object remove(java.lang.Object key)
                        throws StandardException
remove a row from the hash table.

a remove of a duplicate removes the entire duplicate list.

Parameters:
key - The key of the row to remove.
Throws:
StandardException - Standard exception policy.

setAuxillaryRuntimeStats

public void setAuxillaryRuntimeStats(java.util.Properties prop)
                              throws StandardException
Set the auxillary runtime stats.

getRuntimeStats() will return both the auxillary stats and any BackingStoreHashtable() specific stats. Note that each call to setAuxillaryRuntimeStats() overwrites the Property set that was set previously.

Parameters:
prop - The set of properties to append from.
Throws:
StandardException - Standard exception policy.

putRow

public boolean putRow(boolean needsToClone,
                      DataValueDescriptor[] row)
               throws StandardException
Put a row into the hash table.

The in memory hash table will need to keep a reference to the row after the put call has returned. If "needsToClone" is true then the hash table will make a copy of the row and put that, else if "needsToClone" is false then the hash table will keep a reference to the row passed in and no copy will be made.

If rouine returns false, then no reference is kept to the duplicate row which was rejected (thus allowing caller to reuse the object).

Parameters:
needsToClone - does this routine have to make a copy of the row, in order to keep a reference to it after return?
row - The row to insert into the table.
Returns:
true if row was inserted into the hash table. Returns false if the BackingStoreHashtable is eliminating duplicates, and the row being inserted is a duplicate, or if we are skipping rows with 1 or more null key columns and we find a null key column.
Throws:
StandardException - Standard exception policy.

size

public int size()
         throws StandardException
Return number of unique rows in the hash table.

Returns:
The number of unique rows in the hash table.
Throws:
StandardException - Standard exception policy.

Built on Thu 2011-03-10 11:54:14+0000, from revision ???

Apache Derby V10.6 Internals - Copyright © 2004,2007 The Apache Software Foundation. All Rights Reserved.