Sorting
[Storage Structures]

Collaboration diagram for Sorting:

---

Detailed Description

The storage manager provides two tools for sorting, the class sort_stream_i and the method ss_m::sort_file.

The class sort_stream_i implements sorting of <key,elem> pairs with a simple interface. It is an adjunct of bulk-loading indexes. One inserts <key,elem> pairs into the stream, and then iterates over the stream with its sort_stream_i::get_next method to retrieve the pairs in order. The sort_stream_i uses temporary files as necessary to store the data stream.

The storage manager function ss_m::sort_file implements a polyphase merge-sort.

Both methods offer a variety of run-time options. The options are specified with different APIs:

• The sort_stream_i uses ssm_sort::key_info_t to describe keys and ssm_sort::sort_parm_t to describe behavior options.
• The ss_m::sort_file uses ssm_sort::sort_keys_t to describe keys and behavior options.

Note:

Historical note: The original implementation of the sort_file method used the same APIs (for specifying sort behavior and describing keys) as sort_stream_i, but that implementation for sort_file was inadequate for the needs of the projects using the storage manager at the time (viz user-defined key types, marshalling and unmarshalling, etc.). The new implementation is more general, but the sort_stream_i has not been rewritten to use the new options- and key- descriptor classes.

See sort_stream_i for details and sort_stream::cpp for an example of its use. The balance of this section describes the use of ss_m::sort_file and its application to bulk-loading.

Sort_file supports:

• sorting on one or more keys
• key types may be
  • fundamental (predefined) or user-defined
  • derived or embedded
• records being sorted may require marshalling when read from disk to memory and unmarshalling when written back to disk
• the result of the sort can be
  • a sorted copy of the input file
  • a file ready for bulk-loading an index to the original file

For all this generality, the sort uses callbacks to the server for such things as

• key comparisons
• key derivation
• object marshalling and unmarshalling
• producing the final form of keys for output, when the sort key is not the key to be loaded into the index (for example consider R-trees: a polygon is the index key, but the records are sorted on the polygon's Hilbert value)

Runs

The sort takes as many runs as required to read and sort the entire input file, while limiting the amount of memory used. The run size is given as an argument to sort_file.

The sort uses temporary files when the input file contains more records than can fit in one run (determined by the run size). These temporary files may be spread across multiple volumes, which is useful if the volumes reside on different spindles.

If the entire input file fits into the buffer pool pages of one run, much of the complexity of the sort is eliminated, because the copying of objects and metadata to scratch files is unnecessary, but for the general (polyphase) case, behavioral options describe how the writing to scratch files is handled, and these options depend on the kind of output desired (see Behavior and Results of Sort).

Callbacks

The sort has to call back to the server for

• marshalling a record (ssm_sort::MOF): When a record is first encountered in the input file, it may be marshalled to produce an in-memory version of the entire object (presumably byte-swapped, pointer-swizzled, etc.). This copy of the record (in the form of an object_t, which is a handle for the record or in-memory representation) is passed to the next callback function (ssm_sort::CSKF). If a marshal function is supplied it is called at least once on every record.

• creating or locating a key (ssm_sort::CSKF): This callback locates or derives a key for the object. Its result is an skey_t, which is a handle for the derived or embedded key. This function might have to allocate heap space for the derived keys, in which case sort_file has to deallocate such space, so this callback takes a factory_t for heap management.

• comparing two keys (ssm_sort::CF): The server provides this function to compare two byte streams of some given length each.

• unmarshalling an object (ssm_sort::UMOF): Before the object is written to the output file after the last run, it may be unmarshalled to produce an on-disk version of the object. The unmarshal function need not be called on every record. When the output is to be a bulk-loadable file for indexes, unmarshal is not needed. When the output is a copy of the input file, it is sometimes needed:
  • Case 1, Large object, not deep copy (large-object store will be transferred to the output file so carrying the object has no effect here) : No need to unmarshal; the large object was marshaled in the first place only for the purpose of locating or deriving a sort key.
  • Case 2, Large object with deep copy or small object
    • Case 2a, Carrying object : Call unmarshal function (UMOF), write its result to the output file.
    • Case 2b, Not carrying object : No need to unmarshal; pin the original object and copy it to the output file.

Behavior and Results of Sort

Behaviors that can be controlled are the following; these behaviors are determined by the contents of the sort_keys_t argument to sort_file:

• The kind of output the sort produces, which can be
  • a sorted copy of the input file (ssm_sort::sort_keys_t::set_for_file), or
  • a file suitable for bulk-loading an index (sort_keys_t::set_for_index), the format of which is:
    • header contains key in lexicographic format
    • body contains element
• whether the original file is to be retained or deleted by the sort (sort_keys_t::set_keep_orig), with variations on these choices
• how the key is to be located or derived (sort_keys_t::set_sortkey_fixed, sort_keys_t::set_sortkey_derived, and other attributes of sort_keys_t)
• whether the sort is to be stable (sort_keys_t::set_stable)
• whether the sort is ascending or descending (sort_keys_t::set_ascending)
• whether the sort is to eliminate duplicate nulls (sort_keys_t::set_null_unique)
• whether the sort is to eliminate all duplicates (sort_keys_t::set_unique)
• whether the sort is to call user-defined marshal and unmarshal functions to get/put the resulting data from/to disk

Many behavioral options depend on other options, as discussed below.

Result is Sorted Copy of Input File

Use ssm_sort::sort_keys_t::set_for_file to create a sorted copy of the input file.

Applicable key description data:

• number of keys : >= 1
• key access (for each key):
  • in header or body : a key or its source data may reside in either header or body of the original record
  • at fixed location (ssm_sort::sort_keys_t::set_sortkey_fixed): In all records this key is at the same location in the record (header or body). User may not provide a ssm_sort::CSKF for the key (it will not be used, so it is rejected).
    • aligned : By indicating that a key is adequately aligned in the original record for its key-comparison function (ssm_sort::CF) to operate on it, the sort function can avoid the work of copying to an aligned and contiguous buffer before calling the comparison function (ssm_sort::CF). (The sort function determines if the key resides entirely on one page; the user does not have to indicate this.) If the key is in lexicographic format in the original record (after marshalling, if marshalling is used), alignment is immaterial.
  • derived (ssm_sort::sort_keys_t::set_sortkey_derived) : User must provide a ssm_sort::CSKF callback function to derive the key. The source data may be in the header or body of the record. The ssm_sort::CSKF "knows" the key's offset from the header or body, or receives that information from an argument (key_cookie_t) passed to the callback function.
• lexicographic format: ssm_sort::sort_keys_t::is_lexico indicates that the key is in lexigographic format in the original record, so it can be compared in segments (if, say, it is spread across page boundaries) and its alignment is immaterial.

Applicable sort behavior options:

• marshalling : A callback marshal function (MOF) will be called to reformat records from which keys are created. This will be done before the ssm_sort::CSKF is called.
• ascending : sort in ascending or descending order
• stable : optionally ensure stable sort
• unique : eliminate records with duplicate keys
• null_unique : eliminate records with duplicate null keys
• keep_orig : optionally delete the original file
• carry_obj : optionally duplicate the entire object in the runs
• deep_copy : optionally copy the large objects

Result is Input to Bulk-Load

Applicable key description data:

• number of sort keys : only one-key sort is supported
• index key derivation: the index key may differ from the sort key, in which case the user provides a callback (ssm_sort::CSKF) function to produce the index key. It must be produced in lexigographic format.
• sort key access:
  • in header or body : a key or its source data may reside in either header or body of the original record
  • at fixed location (ssm_sort::sort_keys_t::set_sortkey_fixed): In all records the key is at the same location in the record (header or body). User may not provide a ssm_sort::CSKF for the key (it will not be used, so it is rejected).
    • aligned : By indicating that a key is adequately aligned in the original record for its key-comparison function (ssm_sort::CF) to operate on it, the sort function can avoid the work of copying to an aligned and contiguous buffer before calling the comparison function (ssm_sort::CF). (The sort function determines if the key resides entirely on one page; the user does not have to indicate this.) If the key is in lexicographic format in the original record (after marshalling, if marshalling is used), alignment is immaterial.
  • derived (ssm_sort::sort_keys_t::set_sortkey_derived) : User must provide a ssm_sort::CSKF callback function to derive the key. The source data may be in the header or body of the record. The ssm_sort::CSKF "knows" the key's offset from the header or body, or receives that information from an argument (key_cookie_t) passed to the callback function.
    • lexicographic format: if the key is in lexigographic format in the original record, it can be compared in segments (if, say, it is spread across page boundaries) and its alignment is immaterial. NOTE If it is not in lexicographic format, a ssm_sort::CSKF callback must put it in lexicographic format for the purpose of loading into a B+-Tree (should the sort key be used as the index key), so the sort key must therefore be derived in this case.

Applicable sort behavior options:

• marshalling : use callback marshal function (MOF) to reformat records from which keys are created
• ascending : sort in ascending or descending order
• stable : may not be set because it might violate RID order in the event of duplicates (the elements for the pairs with the same key are sorted on the element in the B+-Tree). If stability is needed, the key should be derived from two keys, or should be a concatenation of multiple keys (either suitable colocated in the object or derived) that would ensure the stability.
• unique : eliminate records with duplicate keys
• null_unique : eliminate records with duplicate null keys
• keep_orig : n/a
• carry_obj : n/a
• deep_copy : n/a

Keys

Sort keys may be located in the input records or derived from the input records. Index keys that are different from the sort key are derived.

When the output is to be a sorted copy of the input file, the keys do not appear in the output file except inasmuch as they are embedded in the original input records. The sort keys in this case may be derived from the record contents, in which case they truly do not appear in the output. Multiple keys may be used for the sort, and they may be a combination of fixed-location keys and derived keys. See Result is Sorted Copy of Input File.

When the output is to be a bulk-loadable file, its records takes the form header = key, body = element, and sort-file gives the caller no control over the elements' contents: they are the record-IDs of the original records. If something other than the record-ID is desired for bulk-loading an index, the output can be made to be a sorted copy of the original file, with a suitable unmarshal (UMOF) applied.

Only one sort key can be used in this case, but the index key can differ differ from the sort key. See Result is Input to Bulk-Load.

Classes
class	ssm_sort::key_cookie_t
	Input, output argument to CSKF, MOF, UMOF callbacks. More...
class	ssm_sort::factory_t
	A memory allocator (abstract base class) used by ss_m::sort_file and its adjuncts. More...
class	ssm_sort::key_location_t
	Descriptor for fixed-location keys. More...
class	ssm_sort::object_t
	Handle on a record in the buffer pool or in scratch memory. More...
class	ssm_sort::skey_t
	The result of a CSKF function. More...
struct	ssm_sort::generic_CSKF_cookie
	A cookie passed to generic_CSKF callback must point to one of these. More...
class	ssm_sort::sort_keys_t
	Parameter to control behavior of sort_file. More...
class	sort_stream_i
	Sorting tool. More...
Typedefs
typedef w_rc_t(*)	ssm_sort::CSKF (const rid_t &rid, const object_t &in_obj, key_cookie_t cookie, factory_t &f, skey_t *out)
	Create-Sort-Key Function.
typedef w_rc_t(*)	ssm_sort::MOF (const rid_t &rid, const object_t &obj_in, key_cookie_t cookie, object_t *obj_out)
	Marshal Object Function.
typedef w_rc_t(*)	ssm_sort::UMOF (const rid_t &rid, const object_t &obj_in, key_cookie_t cookie, object_t *obj_out)
	Un-marshal Object Function.
typedef int(*)	ssm_sort::CF (w_base_t::uint4_t length1, const void *key1, w_base_t::uint4_t length2, const void *key2)
	key Comparison Function
typedef w_rc_t(*)	ssm_sort::LEXFUNC (const void *source, smsize_t len, void *sink)
	Lexify key function.
Functions
static rc_t	ss_m::sort_file (const stid_t &fid, const stid_t &sorted_fid, int nvids, const vid_t *vid, sort_keys_t &kl, smsize_t min_rec_sz, int run_size, int temp_space)
	Sort a file.

---

Typedef Documentation

ssm_sort::CSKF

Create-Sort-Key Function.

Parameters:

[in]	rid	Record ID of the record containing the key.
[in]	in_obj	Handle (object_t) on the record whose key we need.
[in]	cookie	Describes the location and type of key in the source record.
[in]	f	Class for managing allocated space.
[out]	out	Result is written to this object_t.

This type of callback function fills in the skey_t out for a key in an object (record). It is called only when the object is first encountered in its run in a sort.

A set of predefined callbacks are provided, q.v.:

• sort_keys_t::noCSKF : vacuous - does nothing
• sort_keys_t::generic_CSKF : copies or lexifies a key based on its key_cookie_t argument.

See generic_CSKF_cookie for an example of a simple user-defined CSKF.

The skey_t out is pre-allocated and must be populated by this callback function. The factory_t f may be used for this allocation, or a user-defined factory_t may be used instead. Whatever factory is used to allocate the buffer to hold a key, that same factory must be placed in the skey_t via the placement-new constructor call. Examples are given in the description for skey_t.

This callback must not free any space for in_obj.

Definition at line 663 of file sort_s.h.

ssm_sort::MOF

Marshal Object Function.

Parameters:

[in]	rid	Record id of the source record to marshal
[in]	obj_in	Handle on the source record (object_t)
[in]	cookie	Describes location and type of key in the source record
[out]	obj_out	Result is to be written to this object_t.

The obj_out is already allocated; this function must populate it. The obj_out has no buffers or factory associated with it. The MOF must populate the obj_out from its own factory (it may use factory_t::cpp_vector, which uses the global heap, or it may use the factory from the obj_in, but ONLY if that factory is not factory_t::none. The obj_out object carries its factory along with it throughout the sort process.

This callback must not free any space for obj_in.

This type of callback is used

• when a record is first encountered in the input file
• if sort_keys_t::carry_obj() is true, it's also called when the object is read back from a temporary file.

A predefined callback is provided:

• ssm_sort::sort_keys_t::noMOF : vacuous - does nothing

The sort code checks for

 sort_keys_t::marshal_func() == sort_keys_t::noMOF

in which case, it does not call a marshal function at all. (This is less work than allocating the output object_t to call a vacuous function.)

Definition at line 707 of file sort_s.h.

ssm_sort::UMOF

Un-marshal Object Function.

Parameters:

[in]	rid	Record id of the source record to marshal
[in]	obj_in	Handle on the source record (object_t)
[in]	cookie	Describes location and type of key in the destination record
[out]	obj_out	Result is to be written to this object_t.

The obj_out is already allocated; this function must populate it. The obj_out has no buffers or factory associated with it. The MOF must populate the obj_out from its own factory (it may use factory_t::cpp_vector, which uses the global heap, or it may use the factory from the obj_in, but ONLY if that factory is not factory_t::none. The obj_out object carries its factory along with it throughout the sort process.

This callback must not free any space for obj_in.

This type of callback is used

• when an object is written to a temp file
• when the final object is written to the result file (if the output is a copy of the input file).

A predefined callback is provided:

• ssm_sort::sort_keys_t::noUMOF : vacuous - does nothing

The sort code checks for

 sort_keys_t::unmarshal_func() == sort_keys_t::noUMOF

in which case, it does not call a marshal function at all. (This is less work than allocating the output object_t to call a vacuous function.)

Definition at line 755 of file sort_s.h.

ssm_sort::CF

key Comparison Function

Parameters:

[in]	length1	Length of first key in bytes
[in]	key1	Pointer to start of first key
[in]	length2	Length of second key in bytes
[in]	key2	Pointer to start of second key

Return values:

int

Negative if key1 < key2, 0 if equal, Positive if key1 > key2

Used on every key comparison.

Note:

It is up to the server to determine if the keys are properly aligned for comparison as fundamental types. Alignment is determined by the combined behavior of the CSKF and MOF callbacks, as well as of the location of the keys in the original records.

Definition at line 778 of file sort_s.h.

ssm_sort::LEXFUNC

Lexify key function.

Parameters:

[in]	source	Pointer to start of key
[in]	len	Length of key
[out]	sink	Pointer to output buffer (preallocated, of length len)

This type of function is called by the generic_CSKF. It may be useful for user-defined CKSF callbacks. Its purpose is to reformat keys into lexicographic form so that simple string-type (byte-by-byte) comparisons yield the same results as typed comparisons would. An alternative to lexifying keys and using string comparisons is to use typed comparisons, however, that has its disadvantages, particularly for keys that might be spread across page boundaries or are not aligned.

Definition at line 801 of file sort_s.h.

---

Function Documentation

static rc_t ss_m::sort_file	(	const stid_t &	fid,
		const stid_t &	sorted_fid,
		int	nvids,
		const vid_t *	vid,
		sort_keys_t &	kl,
		smsize_t	min_rec_sz,
		int	run_size,
		int	temp_space
	)			[static, inherited]

Sort a file.

Parameters:

[in]	fid	File to sort.
[in]	sorted_fid	File to which to write the results.
[in]	nvids	Size of array vid.
[in]	vid	Array of IDs of scratch files created by the caller.
[in]	kl	See sort_keys_t.
[in]	min_rec_sz	Hint of minimum record size in input file.
[in]	run_size	Number of pages in buffer pool to use for a run.
[in]	temp_space	Number of pages to use for scratch space. (This limits the amount of memory used by the sort).

Before you call sort_file, you must create an output file sorted_fid into which sort_file will write the results.

The sort uses temporary files when the input file contains more records than can fit in one run (determined by run_size). These temporary files may be spread across multiple volumes, which is useful if the volumes reside on different spindles. The arguments nvids and vid are for indicating the volumes to use for these scratch files.

The caller can provide a clue in min_rec_size about the minimum record size of the input file, which can help the sort's efficiency.

The run_size indicates how many buffer-pool pages to use for each run. Since at all times one page is fixed for output, while the rest are for reading the input in runs, the real run size is run_size-1.

---