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:
- 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 (subject to certain limitations - see Keys )
- 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)
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).
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.
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.
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
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
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. - Note:
- Keys that are located in the input records may not span pages. The complexity to do key-comparisons (in parts, across pages) is not implemented. To get around this, you may put the keys in the record headers or use marshalling to collect the keys from the records.
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
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.:
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.
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:
The sort code checks for
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.
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:
The sort code checks for
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.
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.
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.
Generated on Thu Dec 9 08:42:29 2010 for Shore Storage Manager by
1.4.7
