Bulk Loading and Sorting

• The Need for Bulk Loading
• Using the Merge Sorter
• Merge Sorting Overview
• The High-Speed Merge Sorter
• The High-Density Merge Sorter

The Need for Bulk Loading

    public synchronized static InfinityDB open(String fileName,
            boolean isWriteable, long cacheSizeLimitBytes) throws IOException;
    public synchronized static InfinityDB create(String fileName,
            boolean overWrite, long cacheSizeLimitBytes) throws IOException {

Using the Merge Sorter

For speed, do this:

	DiskBasedMergeSorterItemOutput sorter = new DiskBasedMergeSorterItemOutput(
		temporaryDirectoryFile, temporaryFileNamePrefix,
		long maxTemporarySpaceBytes);
	Cu cu = Cu.alloc();
	while (there are input Items) {
		// put Item in cu, then insert into the sorter
		sorter.insert(cu); // 'write' the Item into the sorter
	}
	// now retrieve Items
	ItemInput resultsItemInput = sorter.getResultsItemInput();
	while (resultsItemInput.readItem(cu)) { // read the sorted Items back
		// do something with Item in cu
		..
	}
	sorter.close(); // or do resultsItemInput.close();

To get a more disk-space efficient sort:

	// Use an InfinityDB or other large ItemSpace to store temporary data,
	// possibly a subspace of the target or other ItemSpace
	ItemSpace tempSpace = InfinityDB.create(temporaryFilePath, true);
	ItemSpaceBasedMergeSorterItemOutput sorter = new ItemSpaceBasedMergeSorterItemOutput(
		tempSpace, maxTemporarySpaceBytes);
	// and use as above for DiskBasedMergeSortItemOutput..

Merge Sorting Overview

The InfinityDB In-Memory Sorter

The High-Speed Merge Sorter

The ItemPacket encoding is extremely fast and easy to parse, but it is not as space efficient as the encoding of Items in InfinityDB, which does dynamic compression. As a result, the temporary space on disk may be from one to ten times as big as the final InfinityDB database. This can be confusing, and it may seem that data is being lost or the sorter is not working correctly. It is important to remember that the goal is not to have an index of a certain size, but instead to store a given number of Items. Thus comparisons with other DBMS's should take into account the amount of source data, not the final index size. The same is true of performance: high source data rate is the goal. For example, the example program com.infinitydb.examples.InfinityDBSortingBulkLoad inserts 10M Items of 20 bytes each, which should take at least 200MB, but in fact the database takes roughly 22MB. The Items are randomized in a way that shows good compression, but there are other randomizers there to experiment with.

If a very large InfinityDB is required and there is not enough temporary space, it can be built up iteratively with a sequence of 'incremental' merge sorts, each result sorting Item sequence simply being inserted into the growing InfinityDB. This can be efficient up to a point, but the performance of each iteration will be less and less because the time will be determined mostly by the InfinityDB size. It may be possible to avoid using an incremental merge sort until the end. Also, the more disk-efficient ItemSpaceMergeSorterItemOutput can be used when temporary space is getting scarce. If the input Items are not actually uniformly random, then performance may still be good. Sometimes only a small set of the blocks in the growing InfinityDB will be touched by the new data, and there will be few seeks. For example, a set of Items related to a single Entity will usually go in one block, or an entirely new Inversion will be created and it will create a new set of adjacent Items. (Inversion is just the optional InfinityDB 'Entity-Attribute-Value' class and concept corresponding to a relational index, but it is more flexible.)

The temporary file name paths look like this:

	temporaryDirectoryPath/temporaryFileNamePrefixInfinityDBSortMergeTemp_passNumber_batchNumber

	temporaryDirectoryPath/temporaryFileNamePrefixInfinityDBSortMergeTemp.lock

It is also possible to create a custom temporary file manager by extending DiskBasedMergeSorterTempFileManager and providing it to the merge sorter constructor.

The High-Density Merge Sorter

temporarySpacePrefix passNumber batchNumber Item

Previous Next