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 force_sort_rowids)
	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)
uchar *	get_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_param &	operator= (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 uchar *	get_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...
uchar *	m_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_field >	local_sortorder
	ORDER BY list with some precalculated info for filesort. More...
Addon_fields *	addon_fields {nullptr}
	Descriptors for addon fields. More...
bool	using_pq {false}
StringBuffer< STRING_BUFFER_USUAL_SIZE >	tmp_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

enum Sort_param::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	force_sort_rowids
	)

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_start	Pointer to record.
[out]	recl	Store record length here.
[out]	resl	Store 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_sort	sorting information which may be re-used on subsequent invocations of filesort()
	sf_array	initialization value for local_sortorder
	sortlen	length of sorted columns
	tables	tables to be sorted
	maxrows	HA_POS_ERROR or possible LIMIT value
	remove_duplicates	if 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]	dst	Where to store the result
	tables	Tables to get <rowid> from
[in,out]	longest_addons	The 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

Initial value:

{
      Addon_fields_status::unknown_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:

• sql/sort_param.h
• sql/filesort.cc