t_sortcontroller.java

derby database source code.good for you.

/*

   Derby - Class org.apache.derbyTesting.unitTests.store.T_SortController

   Copyright 1997, 2005 The Apache Software Foundation or its licensors, as applicable.

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

      http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.

 */

package org.apache.derbyTesting.unitTests.store;

// impl imports are the preferred way to create unit tests.
import org.apache.derbyTesting.unitTests.harness.T_Generic;
import org.apache.derbyTesting.unitTests.harness.T_Fail;

import org.apache.derby.iapi.store.access.*;

import org.apache.derby.iapi.services.context.ContextService;

import org.apache.derby.iapi.services.monitor.Monitor;
import org.apache.derby.iapi.services.io.Storable;

import org.apache.derby.iapi.error.StandardException;

import org.apache.derby.iapi.types.DataValueDescriptor;

import org.apache.derby.iapi.reference.Property;

import org.apache.derby.iapi.services.i18n.MessageService;

import org.apache.derby.iapi.reference.SQLState;

import org.apache.derby.iapi.types.SQLInteger;

import java.util.Properties;
import java.util.Vector;
import java.util.StringTokenizer;
import java.io.File;

/**

  Unit test for sorting.

**/

public class T_SortController extends T_Generic
{
	private static final String testService = "sortTest";

	/** Set this to print out the rows that are inserted into
	 ** and returned from each sort. **/
	protected boolean verbose = false;

	public String getModuleToTestProtocolName() {
		return AccessFactory.MODULE;
	}

	private void setSortBufferSize(String buf_length) {
		Properties p = System.getProperties();
		p.put("derby.storage.sortBufferMax", buf_length);
		System.setProperties(p);
	}

	/*
	** Methods of T_SortController
	*/

	/**
		@exception T_Fail test has failed
	*/
	protected void runTests() throws T_Fail
	{
		int failcount = 0;

		// Get the AccessFactory to test.

		// don't automatic boot this service if it gets left around
		if (startParams == null) {
			startParams = new Properties();
		}
		startParams.put(Property.NO_AUTO_BOOT, Boolean.TRUE.toString());
		// remove the service directory to ensure a clean run
		startParams.put(Property.DELETE_ON_CREATE, Boolean.TRUE.toString());

		// see if we are testing encryption
		startParams = T_Util.setEncryptionParam(startParams);

		try {
			REPORT("(unitTestMain) Testing " + "sortTest with default sort buffer size 1024");
			AccessFactory store1024 = null;
			failcount = runEachTest(store1024, "1024");

			setSortBufferSize("4");
			REPORT("(unitTestMain) Testing " + "sortTest with minimum sort buffer size 4");
			AccessFactory store4 = null;
			failcount += runEachTest(store4, "4");
		}
		catch (StandardException e)
		{
			String  msg = e.getMessage();
			if (msg == null)
				msg = e.getClass().getName();
			REPORT("(unitTestMain) unexpected exception: " + msg);
			throw T_Fail.exceptionFail(e);
		}

		if (failcount != 0)
			throw T_Fail.testFailMsg("(unitTestMain)" + failcount + " cases failed.");

		REPORT("(unitTestMain) succeeded");
	}

	protected int runEachTest(AccessFactory store, String tail) throws T_Fail, StandardException {

		TransactionController tc = null;
		int failcount = 0;

		try {
			store = (AccessFactory) Monitor.createPersistentService(getModuleToTestProtocolName(), 
				testService + tail, startParams);
		} catch (StandardException mse) {
			throw T_Fail.exceptionFail(mse);
		}
		if (store == null) {
			throw T_Fail.testFailMsg(getModuleToTestProtocolName() + " service not started.");
		}

		tc = store.getTransaction(
                ContextService.getFactory().getCurrentContextManager());

		if (!sortExample(tc))
			failcount++;
		if (!sortBufferCoverage(tc))
			failcount++;
		if (!sortBoundaries(tc))
			failcount++;
		if (!sortAllDuplicates(tc))
			failcount++;
		if (!sortDescending(tc))
			failcount++;

		tc.commit();
		tc.destroy();

		return failcount;
	}

	/**
	This test is more of an example, with lots of comments to
	explain what's going on.
	**/
	boolean sortExample(TransactionController tc)
		throws StandardException
	{
		REPORT("(sortExample)");

		// Create the rows to be sorted.
		T_AccessRow row[] = new T_AccessRow[4];
		row[0] = new T_AccessRow(18,  1,  2);
		row[1] = new T_AccessRow( 6,  1, 18);
		row[2] = new T_AccessRow(18,  1,  2);
		row[3] = new T_AccessRow( 8, 14,  3);

		// Decide on what kind of sort we want.  The properties
		// can select different sorting techniques and options.
		// But all sorts will result in the rows being in order.
		// We don't care which sort technique is used, so set
		// the properties to null.
		Properties implParameters = null;

		// Define the type of rows to be sorted by constructing
		// a template.  Any row with the correct column types
		// will do (the values in the template are never used,
		// just the types).  The first row to be inserted will
		// make a good template.
		T_AccessRow template = row[0];

		// Define the column ordering: sort on column 1
		// (the second column) ascending, then column 2
		// (the third column) ascending.
		ColumnOrdering order[] = new ColumnOrdering[2];
		order[0] = new T_ColumnOrderingImpl(1, true); // ascending
		order[1] = new T_ColumnOrderingImpl(2, true); // ascending

		// Tell the sort that the rows are not already in order.
		boolean alreadyInOrder = false;

		// Tell the sort that we're estimating that about 10
		// rows will be inserted into the sort.  This is just
		// a hint, the sort will still work if more rows or
		// fewer rows are inserted.  But if the guess is close
		// the sort will probably run faster.
		long estimatedRows = 10;

		// Tell the sort that we're estimating that the rows 
        // are about 24 bytes long (3 int columns).
		// This is just a hint, the sort will still work if rows of
		// less or greater size are inserted.  But if the guess is close
		// the sort will probably run faster.
		int estimatedRowSize = 12;

		// Create the sort.
		long sortid = tc.createSort(implParameters, template.getRowArray(),
			order, new T_DuplicateEliminator(template), alreadyInOrder, estimatedRows, 
            estimatedRowSize);

		// For the above sort, on the above input rows, we expect
		// the output rows to look like this:
		T_AccessRow expectedRow[] = new T_AccessRow[3];
		expectedRow[0] = new T_AccessRow(18,  1,  2);
		expectedRow[1] = new T_AccessRow( 6,  1, 18);
		expectedRow[2] = new T_AccessRow( 8, 14,  3);

		return testSort(tc, row, expectedRow, sortid);
	}

	/**
	This test covers specific code paths in the external sort's
	sort buffer.  It really should live closer to the sort buffer
	since the effectiveness of this test is very very implementation
	dependent.
	**/
	boolean sortBufferCoverage(TransactionController tc)
		throws StandardException
	{
		REPORT("(sortBufferCoverage)");

		// Create the rows to be sorted.  This sequence of values
		// will provoke both single and double rotations on insert
		// and both single and double rotations on removal.  Every
		// row has a duplicate so that we can test duplicate handling
		// in every tree position and through all manipulations.
		T_AccessRow row[] = new T_AccessRow[16];
		row[0] = new T_AccessRow(2, 0,  0); // first node
		row[1] = new T_AccessRow(2, 0,  0);

		row[2] = new T_AccessRow(4, 0,  0); // This makes the tree get higher [A7 case (i)]
		row[3] = new T_AccessRow(4, 0,  0);

		row[4] = new T_AccessRow(1, 0,  0); // This makes the tree more balanced [A7 case (ii)]
		row[5] = new T_AccessRow(1, 0,  0);

		row[6] = new T_AccessRow(7, 0,  0); // Tree getting higher again [A7 case (i)]
		row[7] = new T_AccessRow(7, 0,  0);

		row[8] = new T_AccessRow(8, 0,  0); // Tree getting out of balance [A7 case iii]
									  // Single rotation will fix	[A8]
		row[9] = new T_AccessRow(8, 0,  0);

		row[10] = new T_AccessRow(3, 0,  0); // Tree getting out of balance [A7 case iii]
									  // Double rotation will fix	[A9]
		row[11] = new T_AccessRow(3, 0,  0);

		row[12] = new T_AccessRow(5, 0,  0); // Tree more balanced [A7 case (ii)]
		row[13] = new T_AccessRow(5, 0,  0);

		row[14] = new T_AccessRow(6, 0,  0); // Tree getting higher again [A7 case (i)]
		row[15] = new T_AccessRow(6, 0,  0);

		// RESOLVE (nat) Should select the sort that being tested here.
		Properties implParameters = null;

		T_AccessRow template = row[0];

		// Sort on column 0 (the first column) ascending
		ColumnOrdering order[] = new ColumnOrdering[1];
		order[0] = new T_ColumnOrderingImpl(0, true); // ascending

		// The rows are not already in order.
		boolean alreadyInOrder = false;

		long estimatedRows = 20;
		int estimatedRowSize = 12;

		// Create the sort.
		long sortid = tc.createSort(implParameters, template.getRowArray(),
			order, new T_DummySortObserver(template), alreadyInOrder, estimatedRows,
            estimatedRowSize);

		// Rows should come out in order
		T_AccessRow expectedRow[] = new T_AccessRow[16];
		expectedRow[0] = new T_AccessRow(1, 0,  0);
		expectedRow[1] = new T_AccessRow(1, 0,  0);
		expectedRow[2] = new T_AccessRow(2, 0,  0);
		expectedRow[3] = new T_AccessRow(2, 0,  0);
		expectedRow[4] = new T_AccessRow(3, 0,  0);
		expectedRow[5] = new T_AccessRow(3, 0,  0);
		expectedRow[6] = new T_AccessRow(4, 0,  0);
		expectedRow[7] = new T_AccessRow(4, 0,  0);
		expectedRow[8] = new T_AccessRow(5, 0,  0);
		expectedRow[9] = new T_AccessRow(5, 0,  0);
		expectedRow[10] = new T_AccessRow(6, 0,  0);
		expectedRow[11] = new T_AccessRow(6, 0,  0);
		expectedRow[12] = new T_AccessRow(7, 0,  0);
		expectedRow[13] = new T_AccessRow(7, 0,  0);
		expectedRow[14] = new T_AccessRow(8, 0,  0);
		expectedRow[15] = new T_AccessRow(8, 0,  0);

		return testSort(tc, row, expectedRow, sortid);
	}


	/**
	Test a sorts with one or zero rows.
	**/
	boolean sortBoundaries(TransactionController tc)
		throws StandardException
	{
		int failcount = 0;
		long sortid;
		Properties implParameters;
		T_AccessRow template;
		ColumnOrdering order[];
		boolean alreadyInOrder;
		long estimatedRows;
		int estimatedRowSize;
		T_AccessRow input[];
		T_AccessRow expected[];

		/*
		** The following sort parameters are the same for
		** every sort tested in this method.
		*/

		implParameters = null;
		template = new T_AccessRow(1, 1, 1);
		order = new ColumnOrdering[1];
		order[0] = new T_ColumnOrderingImpl(0, true); // ascending
		estimatedRows = 10;
		estimatedRowSize = 12;

		/*
		** A no-row sort.
		*/

		REPORT("(sortBoundaries) Sorting no rows");

		input = new T_AccessRow[0];  // no rows in..
		expected = new T_AccessRow[0];  // .. ==> no rows out!
		alreadyInOrder = false;

		sortid = tc.createSort(implParameters, template.getRowArray(),
			order, new T_DummySortObserver(template), alreadyInOrder, estimatedRows, 
            estimatedRowSize);

		if (!testSort(tc, input, expected, sortid))
			failcount++;

		/*
		** A no-row already in order sort.
		*/

		REPORT("(sortBoundaries) Sorting no rows - \"already in order\"");

		input = new T_AccessRow[0];  // no rows in..
		expected = new T_AccessRow[0];  // .. ==> no rows out!
		alreadyInOrder = true;

		sortid = tc.createSort(implParameters, template.getRowArray(),
			order, new T_DummySortObserver(template), alreadyInOrder, estimatedRows, 
            estimatedRowSize);

		if (!testSort(tc, input, expected, sortid))
			failcount++;

		/*
		** A single-row sort.
		*/

		REPORT("(sortBoundaries) Sorting a single row");

		input = new T_AccessRow[1];
		input[0] = new T_AccessRow(99, 88, 77);
		expected = new T_AccessRow[1];
		expected[0] = new T_AccessRow(99, 88, 77);
		alreadyInOrder = false;

		sortid = tc.createSort(implParameters, template.getRowArray(),
			order, new T_DummySortObserver(template), alreadyInOrder, estimatedRows,
            estimatedRowSize);

		if (!testSort(tc, input, expected, sortid))
			failcount++;

		/*
		** A single-row already-in-order sort.
		*/

		REPORT("(sortBoundaries) Sorting a single row - \"already in order\"");

		input = new T_AccessRow[1];
		input[0] = new T_AccessRow(99, 88, 77);
		expected = new T_AccessRow[1];
		expected[0] = new T_AccessRow(99, 88, 77);
		alreadyInOrder = true;

		sortid = tc.createSort(implParameters, template.getRowArray(),
			order, new T_DummySortObserver(template), alreadyInOrder, estimatedRows, 
            estimatedRowSize);

		if (!testSort(tc, input, expected, sortid))
			failcount++;

		/*
		** A single-row sort, eliminating duplicates
		*/

		REPORT("(sortBoundaries) Sorting a single row - \"eliminate duplicates\"");

		input = new T_AccessRow[1];
		input[0] = new T_AccessRow(99, 88, 77);
		expected = new T_AccessRow[1];
		expected[0] = new T_AccessRow(99, 88, 77);
		alreadyInOrder = false;

		sortid = tc.createSort(implParameters, template.getRowArray(),
			order, new T_DuplicateEliminator(template), alreadyInOrder, estimatedRows, 
            estimatedRowSize);

		if (!testSort(tc, input, expected, sortid))
			failcount++;

		return failcount == 0;
	}

	/**
	Test a sort where all the rows are duplicates
	**/
	boolean sortAllDuplicates(TransactionController tc)
		throws StandardException
	{
		int failcount = 0;
		long sortid;
		Properties implParameters;
		T_AccessRow template;
		ColumnOrdering order[];
		boolean alreadyInOrder;
		long estimatedRows;
		int estimatedRowSize;
		T_AccessRow input[];
		T_AccessRow expected[];

		/*
		** The following sort parameters will be used in every
		** sort in this method.
		*/
		
		implParameters = null;
		template = new T_AccessRow(1, 1, 1);

		// Ordering first two columns, ascending
		order = new ColumnOrdering[2];
		order[0] = new T_ColumnOrderingImpl(0, true); // ascending
		order[1] = new T_ColumnOrderingImpl(1, true); // ascending

		alreadyInOrder = false;
		estimatedRows = 10;
		estimatedRowSize = 12;

		input = new T_AccessRow[5];
		input[0] = new T_AccessRow(1, 1, 1);
		input[1] = new T_AccessRow(1, 1, 1);
		input[2] = new T_AccessRow(1, 1, 1);
		input[3] = new T_AccessRow(1, 1, 1);
		input[4] = new T_AccessRow(1, 1, 1);

		/*
		** When doing no aggregation, we expect every duplicate
		** to come back out.
		*/