Classes
struct	KeySelectivityResult
	Return type for EstimateSelectivityFromIndexStatistics(). More...

Typedefs
using	EqualFieldArray = Bounds_checked_array< const Field *const >
	The set of fields that are equal in an equijoin predicate. More...

Functions
double	HistogramSelectivity (THD *thd, const Field &field)
	Return the selectivity of 'field' derived from a histogram, or -1.0 if there was no histogram. More...

double	KeyCap (THD *thd, const Field &field, uint key_no)
	Check if there is a unique index on key number 'key_no' of 'field'. More...

double	FindSelectivityCap (THD *thd, const Field &field)
	Check if there is a unique index on 'field'. More...

bool	HasEarlierPermutedPrefix (Bounds_checked_array< const KEY > keys, uint prefix_length)
	Check if any other key in 'keys' starts with the same 'prefix_length' fields as the last key. More...

KeySelectivityResult	EstimateSelectivityFromIndexStatistics (THD *thd, const Field &equal_field, const CompanionSet &companion_set, const TABLE &table, uint key_no)

double	EstimateEqualPredicateSelectivity (THD *thd, const EqualFieldArray &equal_fields, const CompanionSet &companion_set)
	Estimate the selectivity of (equi)joining a set of fields. More...

Typedef Documentation

◆ EqualFieldArray

using anonymous_namespace{estimate_selectivity.cc}::EqualFieldArray = typedef Bounds_checked_array<const Field *const>

The set of fields that are equal in an equijoin predicate.

Function Documentation

◆ EstimateEqualPredicateSelectivity()

double anonymous_namespace{estimate_selectivity.cc}::EstimateEqualPredicateSelectivity	(	THD *	thd,
		const EqualFieldArray &	equal_fields,
		const CompanionSet &	companion_set
	)

Estimate the selectivity of (equi)joining a set of fields.

Use cardinality information from indexes, if possible. Otherwise, use histograms, if available. Assumes equal distribution and zero correlation between pairs of fields, so if there are e.g. 100 records and 4 distinct values (A,B,C,D) for the field, it assumes 25% of the values will be A, 25% B, etc. (equal distribution), and thus, when joining a row from some other table against this one, 25% of the records will match (equal distribution, zero correlation).

If there are multiple indexes, we choose the one with the largest selectivity (least selective). There are two main reasons for this:

Databases generally tend to underestimate join cardinality (due to assuming uncorrelated relations); if we're wrong, it would better be towards overestimation to try to compensate.
Overestimating the number of rows generally leads to safer choices that are a little slower for few rows (e.g., hash join). Underestimating, however, leads to choices that can be catastrophic for many rows (e.g., nested loop against table scans). We should clearly prefer the least risky choice here.

Returns -1.0 if no index or no histogram was found. Lifted from Item_equal::get_filtering_effect.

Parameters

[in]	thd	The current thread.
[in]	equal_fields	The equijoined fields for which we calculate selectivity.
[in]	companion_set	The CompanionSet of the join.

Returns: The estimated selectivity of 'field' (or -1.0 if there was no suitable index or histogram).

◆ EstimateSelectivityFromIndexStatistics()

KeySelectivityResult anonymous_namespace{estimate_selectivity.cc}::EstimateSelectivityFromIndexStatistics	(	THD *	thd,
		const Field &	equal_field,
		const CompanionSet &	companion_set,
		const TABLE &	table,
		uint	key_no
	)

◆ FindSelectivityCap()

double anonymous_namespace{estimate_selectivity.cc}::FindSelectivityCap	(	THD *	thd,
		const Field &	field
	)

Check if there is a unique index on 'field'.

If so, use it to calculate an upper bound on the selectivity of field (i.e. 1/'number of rows in table'). If there is no such index, return 1.0.

◆ HasEarlierPermutedPrefix()

bool anonymous_namespace{estimate_selectivity.cc}::HasEarlierPermutedPrefix	(	Bounds_checked_array< const KEY >	keys,
		uint	prefix_length
	)

Check if any other key in 'keys' starts with the same 'prefix_length' fields as the last key.

Parameters

keys	The set of keys to examine.
prefix_length	The length of the key prefix to examine.

Returns: true if there is another key starting with the same prefix.

◆ HistogramSelectivity()

double anonymous_namespace{estimate_selectivity.cc}::HistogramSelectivity	(	THD *	thd,
		const Field &	field
	)

Return the selectivity of 'field' derived from a histogram, or -1.0 if there was no histogram.

◆ KeyCap()

double anonymous_namespace{estimate_selectivity.cc}::KeyCap	(	THD *	thd,
		const Field &	field,
		uint	key_no
	)

Check if there is a unique index on key number 'key_no' of 'field'.

If so, use it to calculate an upper bound on the selectivity of 'field' (i.e. 1/'number of rows in table') and return that. If there is no such index, return 1.0.

Classes

Typedefs

Functions