#include "sql/join_optimizer/explain_access_path.h"
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <memory>
#include <new>
#include <regex>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
#include <openssl/sha.h>
#include "lex_string.h"
#include "mem_root_deque.h"
#include "my_base.h"
#include "my_dbug.h"
#include "my_sqlcommand.h"
#include "mysql/strings/dtoa.h"
#include "sha2.h"
#include "sql-common/json_dom.h"
#include "sql/current_thd.h"
#include "sql/field.h"
#include "sql/handler.h"
#include "sql/item.h"
#include "sql/item_cmpfunc.h"
#include "sql/item_subselect.h"
#include "sql/item_sum.h"
#include "sql/iterators/row_iterator.h"
#include "sql/join_optimizer/access_path.h"
#include "sql/join_optimizer/bit_utils.h"
#include "sql/join_optimizer/cost_model.h"
#include "sql/join_optimizer/materialize_path_parameters.h"
#include "sql/join_optimizer/print_utils.h"
#include "sql/join_optimizer/relational_expression.h"
#include "sql/join_type.h"
#include "sql/key.h"
#include "sql/key_spec.h"
#include "sql/mem_root_array.h"
#include "sql/olap.h"
#include "sql/opt_explain.h"
#include "sql/opt_explain_format.h"
#include "sql/opt_explain_traditional.h"
#include "sql/range_optimizer/group_index_skip_scan_plan.h"
#include "sql/range_optimizer/index_skip_scan_plan.h"
#include "sql/range_optimizer/internal.h"
#include "sql/range_optimizer/range_optimizer.h"
#include "sql/sql_array.h"
#include "sql/sql_class.h"
#include "sql/sql_cmd.h"
#include "sql/sql_const.h"
#include "sql/sql_executor.h"
#include "sql/sql_lex.h"
#include "sql/sql_list.h"
#include "sql/sql_opt_exec_shared.h"
#include "sql/sql_optimizer.h"
#include "sql/table.h"
#include "sql/temp_table_param.h"
#include "sql/window.h"
#include "sql_string.h"
#include "template_utils.h"

Classes
struct	ExplainChild
	This structure encapsulates the information needed to create a Json object for a child access path. More...

Functions
template<class T , class JsonObjectPtr , class... Args>
static bool	AddMemberToObject (const JsonObjectPtr &obj, const char *alias, Args &&...ctor_args)
	Convenience function to add a json field. More...

template<class T , class... Args>
static bool	AddElementToArray (const unique_ptr< Json_array > &array, Args &&...ctor_args)

static bool	PrintRanges (const QUICK_RANGE const ranges, unsigned num_ranges, const KEY_PART_INFO key_part, bool single_part_only, const unique_ptr< Json_array > &range_array, string ranges_out)

static unique_ptr< Json_object >	ExplainAccessPath (const AccessPath path, const AccessPath materialized_path, JOIN *join, bool is_root_of_join, unique_ptr< Json_object > root_obj)
	Convert the AccessPath into a Json object that represents the EXPLAIN output This Json object may in turn be used to output in whichever required format. More...

static unique_ptr< Json_object >	ExplainNoAccessPath (const THD::Query_plan *query_plan)

static unique_ptr< Json_object >	AssignParentPath (AccessPath table_path, const AccessPath materialized_path, unique_ptr< Json_object > materialized_obj, JOIN *join)
	AccessPath objects of type TEMPTABLE_AGGREGATE, MATERIALIZE, and MATERIALIZE_INFORMATION_SCHEMA_TABLE represent a materialized set of rows. More...

static double	GetJSONDouble (const Json_object obj, const char key)

static bool	IsCoveringIndexScan (const KEY &key, const TABLE &table)

static bool	AddTableInfoToObject (Json_object obj, const TABLE table)
	Add table name, schema name, and list of used columns for the specified table to the JSON object. More...

static bool	SetIndexInfoInObject (string str, const char json_index_access_type, const char prefix, const TABLE &table, const KEY &key, const char index_access_type, const string lookup_condition, const string ranges_text, unique_ptr< Json_array > range_arr, bool reverse, Item pushed_idx_cond, Json_object *obj)

string	JoinTypeToString (JoinType join_type)

string	HashJoinTypeToString (RelationalExpression::Type join_type, string *explain_json_value)

static bool	AddSubqueryPaths (const Item item_arg, const char source_text, vector< ExplainChild > *children)
	For each Item_subselect descendant of 'item_arg', add the corresponding root AccessPath object to 'children'. More...

static bool	GetAccessPathsFromSelectList (JOIN join, vector< ExplainChild > children)

static unique_ptr< Json_object >	ExplainMaterializeAccessPath (const AccessPath path, JOIN join, unique_ptr< Json_object > ret_obj, vector< ExplainChild > *children, bool explain_analyze)

static bool	ExplainIndexSkipScanAccessPath (Json_object obj, const AccessPath path, JOIN join, string description)

static bool	ExplainGroupIndexSkipScanAccessPath (Json_object obj, const AccessPath path, JOIN join, string description)

static bool	AddChildrenFromPushedCondition (const TABLE &table, vector< ExplainChild > *children)

static bool	AddChildrenToObject (Json_object obj, vector< ExplainChild > children, JOIN parent_join, bool parent_is_root_of_join, string alias)

static unique_ptr< Json_object >	ExplainQueryPlan (const AccessPath path, THD::Query_plan const query_plan, JOIN *join, bool is_root_of_join)

static bool	AddPathCosts (const AccessPath path, const AccessPath materialized_path, Json_object *obj, bool explain_analyze)
	Append the various costs. More...

static unique_ptr< Json_object >	SetObjectMembers (unique_ptr< Json_object > ret_obj, const AccessPath path, const AccessPath materialized_path, JOIN join, vector< ExplainChild > children)
	Given a json object, update it's appropriate json fields according to the input path. More...

std::string	PrintQueryPlan (THD ethd, const THD query_thd, Query_expression *unit)
	Print out an access path and all of its children (if any) in a tree. More...

std::string	PrintQueryPlan (int level, AccessPath path, JOIN join, bool is_root_of_join)
	For debugging purposes. More...

static string	GetForceSubplanToken (const Json_object *obj, const string &children_digest)

string	GetForceSubplanToken (AccessPath path, JOIN join)
	Generate a digest based on the subplan that the given access path represents. More...

Function Documentation

◆ AddChildrenFromPushedCondition()

static bool AddChildrenFromPushedCondition	(	const TABLE &	table,
		vector< ExplainChild > *	children
	)

static

◆ AddChildrenToObject()

static bool AddChildrenToObject	(	Json_object *	obj,
		vector< ExplainChild >	children,
		JOIN *	parent_join,
		bool	parent_is_root_of_join,
		string	alias
	)

static

◆ AddElementToArray()

template<class T , class... Args>

static bool AddElementToArray	(	const unique_ptr< Json_array > &	array,
		Args &&...	ctor_args
	)

static

◆ AddMemberToObject()

template<class T , class JsonObjectPtr , class... Args>

static bool AddMemberToObject	(	const JsonObjectPtr &	obj,
		const char *	alias,
		Args &&...	ctor_args
	)

static

Convenience function to add a json field.

◆ AddPathCosts()

static bool AddPathCosts	(	const AccessPath *	path,
		const AccessPath *	materialized_path,
		Json_object *	obj,
		bool	explain_analyze
	)

static

Append the various costs.

Parameters

path	the path that we add costs for.
materialized_path	the MATERIALIZE path for which 'path' is the table_path, or nullptr 'path' is not a table_path.
obj	the JSON object describing 'path'.
explain_analyze	true if we run an 'eaxplain analyze' command.

Returns: true iff there was an error.

◆ AddSubqueryPaths()

static bool AddSubqueryPaths	(	const Item *	item_arg,
		const char *	source_text,
		vector< ExplainChild > *	children
	)

static

For each Item_subselect descendant of 'item_arg', add the corresponding root AccessPath object to 'children'.

Parameters

[in]	item_arg	The root of the Item tree to examine.
[in]	source_text	A context description for the objects we add to 'children'.
[in,out]	children	TBD

Returns: 'true' if there was an error.

◆ AddTableInfoToObject()

static bool AddTableInfoToObject	(	Json_object *	obj,
		const TABLE *	table
	)

static

Add table name, schema name, and list of used columns for the specified table to the JSON object.

Add the table's alias if an alias was used.

Parameters

obj	The JSON object to be updated.
table	The table to fetch information from.

Return values

true	if either parameter is nullptr, or adding fields to the JSON object failed.
false	if all table information was added successfully.

◆ AssignParentPath()

static unique_ptr< Json_object > AssignParentPath	(	AccessPath *	table_path,
		const AccessPath *	materialized_path,
		unique_ptr< Json_object >	materialized_obj,
		JOIN *	join
	)

static

AccessPath objects of type TEMPTABLE_AGGREGATE, MATERIALIZE, and MATERIALIZE_INFORMATION_SCHEMA_TABLE represent a materialized set of rows.

These materialized AccessPaths have a another path member (called table_path) that iterates over the materialized rows.

So codewise, table_path is a child of the materialized path, even if it is logically the parent, as it consumes the results from the materialized path. For that reason, we present table_path above the materialized path in 'explain' output (

See also: AddPathCost for details).

This function therefore sets the JSON object for the materialized path to be the leaf descendant of the table_path JSON object. (Note that in some cases table_path does not operate directly on materialized_path. Instead, table_path is the first in a chain of paths where the final path is typically a TABLE_SCAN of REF access path that the iterates over the materialized rows.)

Parameters

table_path	the head of the chain of paths that iterates over the materialized rows.
materialized_path	if (the leaf descendant of) table_path iterates over the rows from a MATERIALIZE path, then 'materialized_path' is that path. Otherwise it is nullptr.
materialized_obj	the JSON object describing the materialized path.
join	the JOIN to which 'table_path' belongs.

Returns: the JSON object describing table_path.

◆ ExplainAccessPath()

static unique_ptr< Json_object > ExplainAccessPath	(	const AccessPath *	path,
		const AccessPath *	materialized_path,
		JOIN *	join,
		bool	is_root_of_join,
		unique_ptr< Json_object >	root_obj
	)

static

Convert the AccessPath into a Json object that represents the EXPLAIN output This Json object may in turn be used to output in whichever required format.

Parameters

path	the path to describe.
materialized_path	if 'path' is the table_path of a MATERIALIZE path, then materialized_path is that path. Otherwise it is nullptr.
join	the JOIN to which 'path' belongs.
is_root_of_join	'true' if 'path' is the root path of a Query_expression that is not a union.
root_obj	The JSON object describing 'path', or nullptr if a new object should be allocated..

Returns: the root of the tree of JSON objects generated from 'path'. (In most cases a single object.)

◆ ExplainGroupIndexSkipScanAccessPath()

static bool ExplainGroupIndexSkipScanAccessPath	(	Json_object *	obj,
		const AccessPath *	path,
		JOIN *	join,
		string *	description
	)

static

◆ ExplainIndexSkipScanAccessPath()

static bool ExplainIndexSkipScanAccessPath	(	Json_object *	obj,
		const AccessPath *	path,
		JOIN *	join,
		string *	description
	)

static

◆ ExplainMaterializeAccessPath()

static unique_ptr< Json_object > ExplainMaterializeAccessPath	(	const AccessPath *	path,
		JOIN *	join,
		unique_ptr< Json_object >	ret_obj,
		vector< ExplainChild > *	children,
		bool	explain_analyze
	)

static

◆ ExplainNoAccessPath()

unique_ptr< Json_object > ExplainNoAccessPath ( const THD::Query_plan * query_plan )

static

◆ ExplainQueryPlan()

static unique_ptr< Json_object > ExplainQueryPlan	(	const AccessPath *	path,
		THD::Query_plan const *	query_plan,
		JOIN *	join,
		bool	is_root_of_join
	)

static

◆ GetAccessPathsFromSelectList()

static bool GetAccessPathsFromSelectList	(	JOIN *	join,
		vector< ExplainChild > *	children
	)

static

◆ GetForceSubplanToken() [1/2]

string GetForceSubplanToken	(	AccessPath *	path,
		JOIN *	join
	)

Generate a digest based on the subplan that the given access path represents.

This can be used by developers to force a given subplan, to investigate e.g. whether a given choice is actually faster in practice, force-apply a plan from the old join optimizer (or at least the types of subplans that are ever considered; e.g. aggregation through temporary tables are not) into the hypergraph join optimizer (to see how it's costed), or whether a given plan is even generated. If DEBUG contains force_subplan_0x<token>, subplans with the given token are unconditionally preferred over all others.

The token returned is “0x<digest>”, where <digest> is the first 64 bits of the SHA-256 sum of this string:

desc1,desc2,...,[child1_desc:]0xchild1,[child2_desc:]0xchild2,<more children>

where desc1, desc2, etc. are the description lines given by EXPLAIN, and 0xchild1 is the token for children. The normal way to generate such tokens is to use SET DEBUG='+d,subplan_tokens' and look at the EXPLAIN FORMAT=tree, but in a pinch, you can also write them by hand and use sha256sum or a similar tool.

Only the hypergraph join optimizer honors token preferences, but EXPLAIN FORMAT=tree shows computed tokens for both optimizers.

◆ GetForceSubplanToken() [2/2]

static string GetForceSubplanToken	(	const Json_object *	obj,
		const string &	children_digest
	)

static

◆ GetJSONDouble()

static double GetJSONDouble	(	const Json_object *	obj,
		const char *	key
	)

inlinestatic

◆ HashJoinTypeToString()

string HashJoinTypeToString	(	RelationalExpression::Type	join_type,
		string *	explain_json_value
	)

◆ IsCoveringIndexScan()

static bool IsCoveringIndexScan	(	const KEY &	key,
		const TABLE &	table
	)

static

◆ JoinTypeToString()

string JoinTypeToString ( JoinType join_type )

◆ PrintQueryPlan() [1/2]

std::string PrintQueryPlan	(	int	level,
		AccessPath *	path,
		JOIN *	join,
		bool	is_root_of_join
	)

For debugging purposes.

◆ PrintQueryPlan() [2/2]

std::string PrintQueryPlan	(	THD *	ethd,
		const THD *	query_thd,
		Query_expression *	unit
	)

Print out an access path and all of its children (if any) in a tree.

◆ PrintRanges()

static bool PrintRanges	(	const QUICK_RANGE const	ranges,
		unsigned	num_ranges,
		const KEY_PART_INFO *	key_part,
		bool	single_part_only,
		const unique_ptr< Json_array > &	range_array,
		string *	ranges_out
	)

static

◆ SetIndexInfoInObject()

static bool SetIndexInfoInObject	(	string *	str,
		const char *	json_index_access_type,
		const char *	prefix,
		const TABLE &	table,
		const KEY &	key,
		const char *	index_access_type,
		const string	lookup_condition,
		const string *	ranges_text,
		unique_ptr< Json_array >	range_arr,
		bool	reverse,
		Item *	pushed_idx_cond,
		Json_object *	obj
	)

static

◆ SetObjectMembers()

static unique_ptr< Json_object > SetObjectMembers	(	unique_ptr< Json_object >	ret_obj,
		const AccessPath *	path,
		const AccessPath *	materialized_path,
		JOIN *	join,
		vector< ExplainChild > *	children
	)

static

Given a json object, update it's appropriate json fields according to the input path.

Also update the 'children' with a flat list of direct children of the passed object. In most of cases, the returned object is same as the input object, but for some paths it can be different. So callers should use the returned object.

Note: This function has shown to consume excessive stack space, particularly in debug builds. Hence make sure this function does not directly or indirectly create any json children objects recursively. It may cause stack overflow. Hence json children are created only after this function returns in function ExplainAccessPath().

Parameters

ret_obj	The JSON object describing 'path'.
path	the path to describe.
materialized_path	if 'path' is the table_path of a MATERIALIZE path, then materialized_path is that path. Otherwise it is nullptr.
join	the JOIN to which 'path' belongs.
children	the paths that are the children of the path that the returned JSON object represents (i.e. the next paths to be explained).

Returns: either ret_obj or a new JSON object with ret_obj as a descendant.

Classes

Functions

Function Documentation

◆ AddChildrenFromPushedCondition()

◆ AddChildrenToObject()

◆ AddElementToArray()

◆ AddMemberToObject()

◆ AddPathCosts()

◆ AddSubqueryPaths()

◆ AddTableInfoToObject()

◆ AssignParentPath()

◆ ExplainAccessPath()

◆ ExplainGroupIndexSkipScanAccessPath()

◆ ExplainIndexSkipScanAccessPath()

◆ ExplainMaterializeAccessPath()

◆ ExplainNoAccessPath()

◆ ExplainQueryPlan()

◆ GetAccessPathsFromSelectList()

◆ GetForceSubplanToken() [1/2]

◆ GetForceSubplanToken() [2/2]

◆ GetJSONDouble()

◆ HashJoinTypeToString()

◆ IsCoveringIndexScan()

◆ JoinTypeToString()

◆ PrintQueryPlan() [1/2]

◆ PrintQueryPlan() [2/2]

◆ PrintRanges()

◆ SetIndexInfoInObject()

◆ SetObjectMembers()