MySQL  8.0.27
Source Code Documentation
Sort_param Class Reference

There are several record formats for sorting: More...

#include <sort_param.h>

Public Types

enum  enum_sort_algorithm { FILESORT_ALG_NONE , FILESORT_ALG_STD_SORT , FILESORT_ALG_STD_STABLE }
 

Public Member Functions

void decide_addon_fields (Filesort *file_sort, const Mem_root_array< TABLE * > &tables, bool sort_positions)
 Decide whether we are to use addon fields (sort rows instead of sorting row IDs or not). More...
 
void clear_addon_fields ()
 Reset the decision made in decide_addon_fields(). More...
 
void init_for_filesort (Filesort *file_sort, Bounds_checked_array< st_sort_field > sf_array, uint sortlen, const Mem_root_array< TABLE * > &tables, ha_rows maxrows, bool remove_duplicates)
 Initialize this struct for filesort() usage. More...
 
void init_for_unittest (Bounds_checked_array< st_sort_field > sf_array)
 Initialize this struct for unit testing. More...
 
void try_to_pack_addons ()
 Enables the packing of addons if possible. More...
 
bool using_packed_addons () const
 Are we packing the "addon fields"? More...
 
bool using_varlen_keys () const
 Are we using varlen key fields? More...
 
bool using_json_keys () const
 Are we using any JSON key fields? More...
 
bool using_addon_fields () const
 Are we using "addon fields"? Note that decide_addon_fields() or init_for_filesort() must be called before checking this. More...
 
uint make_sortkey (Bounds_checked_array< uchar > dst, const Mem_root_array< TABLE * > &tables, size_t *longest_addons)
 Stores key fields in *dst. More...
 
uint make_sortkey (uchar *dst, size_t dst_len, const Mem_root_array< TABLE * > &tables)
 
ucharget_start_of_payload (uchar *p) const
 Skips the key part, and returns address of payload. More...
 
uint max_compare_length () const
 
void set_max_compare_length (uint len)
 
size_t get_record_length (uchar *p) const
 
uint max_record_length () const
 
void set_max_record_length (uint len)
 
void get_rec_and_res_len (uchar *record_start, uint *recl, uint *resl)
 Getter for record length and result length. More...
 
 Sort_param ()=default
 
 Sort_param (const Sort_param &)=delete
 
Sort_paramoperator= (const Sort_param &)=delete
 

Static Public Member Functions

static void store_varlen_key_length (uchar *p, uint sz)
 Stores the length of a variable-sized key. More...
 
static ucharget_start_of_payload (uint default_val, bool is_varlen, uchar *p)
 Skips the key part, and returns address of payload. More...
 

Public Attributes

uint sum_ref_length {0}
 
uint m_addon_length {0}
 
uint fixed_res_length {0}
 
uint max_rows_per_buffer {0}
 
ha_rows max_rows {0}
 
bool use_hash {false}
 
bool m_remove_duplicates
 Whether we want to remove duplicate rows. More...
 
ucharm_last_key_seen {nullptr}
 If we are removing duplicate rows and merging, contains a buffer where we can store the last key seen. More...
 
Bounds_checked_array< st_sort_fieldlocal_sortorder
 ORDER BY list with some precalculated info for filesort. More...
 
Addon_fieldsaddon_fields {nullptr}
 Descriptors for addon fields. More...
 
bool using_pq {false}
 
StringBuffer< STRING_BUFFER_USUAL_SIZEtmp_buffer
 
enum_sort_algorithm m_sort_algorithm {FILESORT_ALG_NONE}
 
Addon_fields_status m_addon_fields_status
 

Static Public Attributes

static const uint size_of_varlength_field = 4
 

Private Member Functions

int count_varlen_keys () const
 Counts number of varlen keys. More...
 
int count_json_keys () const
 Counts number of JSON keys. More...
 

Private Attributes

uint m_fixed_rec_length {0}
 Maximum length of a record, see above. More...
 
uint m_fixed_sort_length {0}
 Maximum number of bytes used for sorting. More...
 
uint m_packable_length {0}
 total length of fields which have a packable type More...
 
bool m_using_packed_addons {false}
 caches the value of using_packed_addons() More...
 
int m_num_varlen_keys {0}
 number of varlen keys More...
 
int m_num_json_keys {0}
 number of JSON keys More...
 

Detailed Description

There are several record formats for sorting:

    |<key a><key b>...    | ( <null row flag> | <rowid> | ) * num_tables
    / m_fixed_sort_length / (  0 or 1 bytes   | ref_len / )

or with "addon fields"

    |<key a><key b>...    |<null bits>|<field a><field b>...|
    / m_fixed_sort_length /        addon_length             /

The packed format for "addon fields"

    |<key a><key b>...    |<length>|<null bits>|<field a><field b>...|
    / m_fixed_sort_length /             addon_length                 /

For packed addon fields, fields are not stored if the table is nullable and has its NULL bit set.

All the figures above are depicted for the case of fixed-size keys, with appropriate padding. Fixed-size keys can be compared/sorted using memcmp().

The packed (variable length) format for keys:

    |<keylen>|<varkey a><key b>...<hash>|<(null_row,rowid) * num_tables>  or <addons>   |
    / 4 bytes/   keylen bytes           / (0/1 + ref_len) * num_tables or addon_length /

Variable-size keys must be compared piece-by-piece, using type information about each individual key part,

See also
cmp_varlen_keys.

All the record formats consist of a (possibly composite) key, followed by a (possibly composite) payload. The key is used for sorting data. Once sorting is done, the payload is stored in some buffer, and read by some RowIterator.

<key>
Fields are fixed-size, specially encoded with Field::make_sort_key() so we can do byte-by-byte compare.
<length>
Contains the actual packed length (after packing) of everything after the sort keys. The size of the length field is 2 bytes, which should cover most use cases: addon data <= 65535 bytes. This is the same as max record size in MySQL.
<null bits>

One bit for each nullable table and field, indicating whether the table/field is NULL or not. May have size zero if no fields or rows are nullable. NULL bits for rows (on nullable tables), if any, always come before NULL bits for fields.

<field xx>
Are stored with field->pack(), and retrieved with field->unpack(). Addon fields within a record are stored consecutively, with no "holes" or padding. They will have zero size for NULL values.
<keylen>
Contains the actual packed length of all the keys. We may have an arbitrary mix of fixed and variable-sized keys.
<hash>
Optional 8 byte hash, used for GROUPing of JSON values.
<varkey>
Used for JSON and variable-length string values, the format is:
                |<null value>|<key length>|<sort key>        |
                / 1 byte     /   4 bytes  / key length bytes /
<null value>
0x00 for NULL. 0xff for NULL under DESC sort. 0x01 for NOT NULL.
<key length>
The length of the sort key, including the four bytes for the key length. Does not exist if the field is NULL.

Member Enumeration Documentation

◆ enum_sort_algorithm

Enumerator
FILESORT_ALG_NONE 
FILESORT_ALG_STD_SORT 
FILESORT_ALG_STD_STABLE 

Constructor & Destructor Documentation

◆ Sort_param() [1/2]

Sort_param::Sort_param ( )
default

◆ Sort_param() [2/2]

Sort_param::Sort_param ( const Sort_param )
delete

Member Function Documentation

◆ clear_addon_fields()

void Sort_param::clear_addon_fields ( )

Reset the decision made in decide_addon_fields().

Only used in exceptional circumstances (see NewWeedoutAccessPathForTables()).

◆ count_json_keys()

int Sort_param::count_json_keys ( ) const
private

Counts number of JSON keys.

◆ count_varlen_keys()

int Sort_param::count_varlen_keys ( ) const
inlineprivate

Counts number of varlen keys.

◆ decide_addon_fields()

void Sort_param::decide_addon_fields ( Filesort file_sort,
const Mem_root_array< TABLE * > &  tables,
bool  sort_positions 
)

Decide whether we are to use addon fields (sort rows instead of sorting row IDs or not).

See using_addon_fields().

Note that currently, this function must not be called from the Filesort constructor, as the read sets are not fully set up at that time (see filter_virtual_gcol_base_cols(), which runs very late in optimization). If we want to change this, we can probably have make_sortkey() check the read set at runtime, at the cost of slightly less precise estimation of packed row size.

◆ get_rec_and_res_len()

void Sort_param::get_rec_and_res_len ( uchar record_start,
uint recl,
uint resl 
)

Getter for record length and result length.

Parameters
record_startPointer to record.
[out]reclStore record length here.
[out]reslStore result length here.

◆ get_record_length()

size_t Sort_param::get_record_length ( uchar p) const
Returns
The actual size of a record (key + addons)

◆ get_start_of_payload() [1/2]

uchar* Sort_param::get_start_of_payload ( uchar p) const
inline

Skips the key part, and returns address of payload.

◆ get_start_of_payload() [2/2]

static uchar* Sort_param::get_start_of_payload ( uint  default_val,
bool  is_varlen,
uchar p 
)
inlinestatic

Skips the key part, and returns address of payload.

For SortBufferIterator, which does not have access to Sort_param.

◆ init_for_filesort()

void Sort_param::init_for_filesort ( Filesort file_sort,
Bounds_checked_array< st_sort_field sf_array,
uint  sortlen,
const Mem_root_array< TABLE * > &  tables,
ha_rows  maxrows,
bool  remove_duplicates 
)

Initialize this struct for filesort() usage.

See also
description of record layout above
Parameters
[in,out]file_sortsorting information which may be re-used on subsequent invocations of filesort()
sf_arrayinitialization value for local_sortorder
sortlenlength of sorted columns
tablestables to be sorted
maxrowsHA_POS_ERROR or possible LIMIT value
remove_duplicatesif true, items with duplicate keys will be removed

◆ init_for_unittest()

void Sort_param::init_for_unittest ( Bounds_checked_array< st_sort_field sf_array)
inline

Initialize this struct for unit testing.

◆ make_sortkey() [1/2]

uint Sort_param::make_sortkey ( Bounds_checked_array< uchar dst,
const Mem_root_array< TABLE * > &  tables,
size_t *  longest_addons 
)

Stores key fields in *dst.

Then appends either *ref_pos (the <rowid>) or the "addon fields".

Parameters
[out]dstWhere to store the result
tablesTables to get <rowid> from
[in,out]longest_addonsThe longest addon field row (sum of all addon fields for any single given row) found.
Returns
Number of bytes stored, or UINT_MAX if the result could not provably fit within the destination buffer.

◆ make_sortkey() [2/2]

uint Sort_param::make_sortkey ( uchar dst,
size_t  dst_len,
const Mem_root_array< TABLE * > &  tables 
)
inline

◆ max_compare_length()

uint Sort_param::max_compare_length ( ) const
inline
Returns
The number of bytes used for sorting of fixed-size keys.

◆ max_record_length()

uint Sort_param::max_record_length ( ) const
inline
Returns
The maximum size of a record (key + addons)

◆ operator=()

Sort_param& Sort_param::operator= ( const Sort_param )
delete

◆ set_max_compare_length()

void Sort_param::set_max_compare_length ( uint  len)
inline

◆ set_max_record_length()

void Sort_param::set_max_record_length ( uint  len)
inline

◆ store_varlen_key_length()

static void Sort_param::store_varlen_key_length ( uchar p,
uint  sz 
)
inlinestatic

Stores the length of a variable-sized key.

◆ try_to_pack_addons()

void Sort_param::try_to_pack_addons ( )

Enables the packing of addons if possible.

◆ using_addon_fields()

bool Sort_param::using_addon_fields ( ) const
inline

Are we using "addon fields"? Note that decide_addon_fields() or init_for_filesort() must be called before checking this.

◆ using_json_keys()

bool Sort_param::using_json_keys ( ) const
inline

Are we using any JSON key fields?

◆ using_packed_addons()

bool Sort_param::using_packed_addons ( ) const
inline

Are we packing the "addon fields"?

◆ using_varlen_keys()

bool Sort_param::using_varlen_keys ( ) const
inline

Are we using varlen key fields?

Member Data Documentation

◆ addon_fields

Addon_fields* Sort_param::addon_fields {nullptr}

Descriptors for addon fields.

◆ fixed_res_length

uint Sort_param::fixed_res_length {0}

◆ local_sortorder

Bounds_checked_array<st_sort_field> Sort_param::local_sortorder

ORDER BY list with some precalculated info for filesort.

Array is created and owned by a Filesort instance.

◆ m_addon_fields_status

Addon_fields_status Sort_param::m_addon_fields_status

◆ m_addon_length

uint Sort_param::m_addon_length {0}

◆ m_fixed_rec_length

uint Sort_param::m_fixed_rec_length {0}
private

Maximum length of a record, see above.

◆ m_fixed_sort_length

uint Sort_param::m_fixed_sort_length {0}
private

Maximum number of bytes used for sorting.

◆ m_last_key_seen

uchar* Sort_param::m_last_key_seen {nullptr}

If we are removing duplicate rows and merging, contains a buffer where we can store the last key seen.

◆ m_num_json_keys

int Sort_param::m_num_json_keys {0}
private

number of JSON keys

◆ m_num_varlen_keys

int Sort_param::m_num_varlen_keys {0}
private

number of varlen keys

◆ m_packable_length

uint Sort_param::m_packable_length {0}
private

total length of fields which have a packable type

◆ m_remove_duplicates

bool Sort_param::m_remove_duplicates
Initial value:
{
false}

Whether we want to remove duplicate rows.

◆ m_sort_algorithm

enum_sort_algorithm Sort_param::m_sort_algorithm {FILESORT_ALG_NONE}

◆ m_using_packed_addons

bool Sort_param::m_using_packed_addons {false}
private

caches the value of using_packed_addons()

◆ max_rows

ha_rows Sort_param::max_rows {0}

◆ max_rows_per_buffer

uint Sort_param::max_rows_per_buffer {0}

◆ size_of_varlength_field

const uint Sort_param::size_of_varlength_field = 4
static

◆ sum_ref_length

uint Sort_param::sum_ref_length {0}

◆ tmp_buffer

StringBuffer<STRING_BUFFER_USUAL_SIZE> Sort_param::tmp_buffer

◆ use_hash

bool Sort_param::use_hash {false}

◆ using_pq

bool Sort_param::using_pq {false}

The documentation for this class was generated from the following files: