#include "sql/join_optimizer/derived_keys.h"
#include <assert.h>
#include <sys/types.h>
#include <algorithm>
#include <memory>
#include <optional>
#include <utility>
#include "my_base.h"
#include "my_inttypes.h"
#include "prealloced_array.h"
#include "sql/item.h"
#include "sql/item_cmpfunc.h"
#include "sql/item_func.h"
#include "sql/join_optimizer/access_path.h"
#include "sql/join_optimizer/optimizer_trace.h"
#include "sql/join_optimizer/overflow_bitset.h"
#include "sql/join_optimizer/walk_access_paths.h"
#include "sql/mem_root_array.h"
#include "sql/sql_array.h"
#include "sql/sql_optimizer.h"
#include "sql/table.h"
#include "template_utils.h"

Classes
struct	anonymous_namespace{derived_keys.cc}::GetDerivedKeyResult
	Result type for GetDerivedKey. More...

struct	anonymous_namespace{derived_keys.cc}::TableShareInfo
	The set of used keys for a TABLE_SHARE. More...

Namespaces
namespace	anonymous_namespace{derived_keys.cc}

Typedefs
using	KeyMap = MutableOverflowBitset

using	TableShareInfoCollection = Prealloced_array< TableShareInfo, kExpectedTableCount >
	The set of used keys, for each derived table. More...

Functions
static bool	AddKeyField (THD thd, const Query_block query_block, const Item_field field_item, Item equal_to)
	Add a field of a derived table to the set of fields for which we want to generate keys. More...

static bool	AddKeyFieldsFromEqual (THD thd, const Query_block query_block, const Item_func_eq *eq)
	Add any field from derived_tab.field=expression to the set of fields to generate keys for. More...

static bool	AddKeyFieldsFromMultiEqual (THD thd, const Query_block query_block, Item_multi_eq *equal)
	Add any field from derived_tab.field=expression to the set of fields to generate keys for. More...

bool	MakeDerivedKeys (THD thd, JOIN join)
	Collect the set fields of derived tables that are present in predicates like "derived_tab.field=function(other_tab.field)". More...

static std::optional< GetDerivedKeyResult >	GetDerivedKey (const AccessPath &path)
	Find the derived key used in 'path', if there is one. More...

TableShareInfo *	FindTableShareInfo (TableShareInfoCollection collection, const TABLE_SHARE share)
	Find 'share' in 'collection' if present. More...

static void	FindUsedDerivedKeys (THD thd, const Query_block &query_block, const AccessPath root_path, TableShareInfoCollection *share_info_collection)
	Find the set of keys that are in use in all derived Table_ref objects that belong to 'query_block'. More...

static void	FindUniqueAndHashKeys (THD thd, const Query_block &query_block, TableShareInfoCollection share_info_collection)
	Mark all unique and hash keys as is use. More...

static void	RemoveUnusedKeys (const Query_block &query_block, TableShareInfoCollection share_info_collection, const Table_ref table_ref)
	Remove any unused keys from derived table '*table_ref'. More...

static void	TraceDerivedKeys (THD thd, const Table_ref table_ref)
	Print the set of keys defined on derived table 'table_ref' to the optimizer trace for. More...

void	FinalizeDerivedKeys (THD thd, const Query_block &query_block, AccessPath root_path)
	Remove any unused keys on derived tables. More...

Variables
constexpr size_t	kExpectedTableCount {10}
	Joins of more than 10 tables are rare, so use this when sizing containers. More...

Typedef Documentation

◆ KeyMap

using KeyMap = MutableOverflowBitset

◆ TableShareInfoCollection

using TableShareInfoCollection = Prealloced_array<TableShareInfo, kExpectedTableCount>

The set of used keys, for each derived table.

Function Documentation

◆ AddKeyField()

static bool AddKeyField	(	THD *	thd,
		const Query_block *	query_block,
		const Item_field *	field_item,
		Item *	equal_to
	)

static

Add a field of a derived table to the set of fields for which we want to generate keys.

Parameters

thd	The current thread.
query_block	The current Query_block. Ignore 'field_item' if it belongs to another.
field_item	The field to add to the set.
equal_to	The expression that field_item is equal to. We may have to create separate keys for each pair of (equi-)joined tables. Therefore, we need this.

Returns: true if there was an error.

◆ AddKeyFieldsFromEqual()

static bool AddKeyFieldsFromEqual	(	THD *	thd,
		const Query_block *	query_block,
		const Item_func_eq *	eq
	)

static

Add any field from derived_tab.field=expression to the set of fields to generate keys for.

Parameters

thd	The current thread.
query_block	The current Query_block. Ignore fields belonging to other Query_block instances.
eq	The predicate to search for fields of derived tables.

Returns: true if there was an error.

◆ AddKeyFieldsFromMultiEqual()

static bool AddKeyFieldsFromMultiEqual	(	THD *	thd,
		const Query_block *	query_block,
		Item_multi_eq *	equal
	)

static

Add any field from derived_tab.field=expression to the set of fields to generate keys for.

Parameters

thd	The current thread.
query_block	The current Query_block. Ignore fields belonging to other Query_block instances.
equal	The predicate to search for fields of derived tables.

Returns: true if there was an error.

◆ FinalizeDerivedKeys()

void FinalizeDerivedKeys	(	THD *	thd,
		const Query_block &	query_block,
		AccessPath *	root_path
	)

Remove any unused keys on derived tables.

Update the key number in any AccessPath that uses a key that gets shifted to a lower number due to those removals.

Parameters

thd	The current thread.
query_block	The current Query_block.
root_path	The root path of 'query_block'.

◆ FindTableShareInfo()

TableShareInfo * FindTableShareInfo	(	TableShareInfoCollection *	collection,
		const TABLE_SHARE *	share
	)

Find 'share' in 'collection' if present.

Parameters

collection	The collection to search in.
share	The share to search for.

Returns: TableShareInfo for 'share' or nullptr if 'share' not found.

◆ FindUniqueAndHashKeys()

static void FindUniqueAndHashKeys	(	THD *	thd,
		const Query_block &	query_block,
		TableShareInfoCollection *	share_info_collection
	)

static

Mark all unique and hash keys as is use.

Parameters

thd	The current thread.
query_block	The current Query_block.
share_info_collection	The set of keys for derived tables that are in use.

◆ FindUsedDerivedKeys()

static void FindUsedDerivedKeys	(	THD *	thd,
		const Query_block &	query_block,
		const AccessPath *	root_path,
		TableShareInfoCollection *	share_info_collection
	)

static

Find the set of keys that are in use in all derived Table_ref objects that belong to 'query_block'.

Parameters

thd	The current thread.
query_block	The current Query_block.
root_path	The root path of 'query_block'.
share_info_collection	The set of keys for derived tables that are in use.

◆ GetDerivedKey()

static std::optional< GetDerivedKeyResult > GetDerivedKey ( const AccessPath & path )

static

Find the derived key used in 'path', if there is one.

◆ MakeDerivedKeys()

bool MakeDerivedKeys	(	THD *	thd,
		JOIN *	join
	)

Collect the set fields of derived tables that are present in predicates like "derived_tab.field=function(other_tab.field)".

Generate keys for every derived_tab+other_tab pair in that set.

Parameters

thd	The current thread.
join	The current join.

◆ RemoveUnusedKeys()

static void RemoveUnusedKeys	(	const Query_block &	query_block,
		TableShareInfoCollection *	share_info_collection,
		const Table_ref *	table_ref
	)

static

Remove any unused keys from derived table '*table_ref'.

Parameters

query_block	The current query block.
share_info_collection	The set of keys for derived tables that are in use.
table_ref	The derived table for which we remove the unused keys.

◆ TraceDerivedKeys()

static void TraceDerivedKeys	(	THD *	thd,
		const Table_ref *	table_ref
	)

static

Print the set of keys defined on derived table 'table_ref' to the optimizer trace for.

Variable Documentation

◆ kExpectedTableCount

constexpr size_t kExpectedTableCount {10}

constexpr

Joins of more than 10 tables are rare, so use this when sizing containers.

Classes

Namespaces

Typedefs

Functions

Variables

Typedef Documentation

◆ KeyMap

◆ TableShareInfoCollection

Function Documentation

◆ AddKeyField()

◆ AddKeyFieldsFromEqual()

◆ AddKeyFieldsFromMultiEqual()

◆ FinalizeDerivedKeys()

◆ FindTableShareInfo()

◆ FindUniqueAndHashKeys()

◆ FindUsedDerivedKeys()

◆ GetDerivedKey()

◆ MakeDerivedKeys()

◆ RemoveUnusedKeys()

◆ TraceDerivedKeys()

Variable Documentation

◆ kExpectedTableCount