#include "sql/range_optimizer/index_skip_scan_plan.h"
#include <assert.h>
#include <float.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <memory>
#include "my_bitmap.h"
#include "my_dbug.h"
#include "my_inttypes.h"
#include "my_table_map.h"
#include "mysql/strings/m_ctype.h"
#include "sql/current_thd.h"
#include "sql/field.h"
#include "sql/handler.h"
#include "sql/item.h"
#include "sql/item_sum.h"
#include "sql/join_optimizer/access_path.h"
#include "sql/key.h"
#include "sql/key_spec.h"
#include "sql/opt_costmodel.h"
#include "sql/opt_hints.h"
#include "sql/opt_statistics.h"
#include "sql/opt_trace.h"
#include "sql/opt_trace_context.h"
#include "sql/range_optimizer/index_range_scan_plan.h"
#include "sql/range_optimizer/index_skip_scan.h"
#include "sql/range_optimizer/internal.h"
#include "sql/range_optimizer/path_helpers.h"
#include "sql/range_optimizer/range_opt_param.h"
#include "sql/range_optimizer/tree.h"
#include "sql/sql_bitmap.h"
#include "sql/sql_class.h"
#include "sql/sql_const.h"
#include "sql/sql_lex.h"
#include "sql/sql_optimizer.h"
#include "sql/sql_select.h"
#include "sql/table.h"
#include "sql_string.h"

Functions
void	trace_basic_info_index_skip_scan (THD thd, const AccessPath path, const RANGE_OPT_PARAM , Opt_trace_object trace_object)

static void	cost_skip_scan (TABLE table, uint key, uint distinct_key_parts, ha_rows quick_prefix_records, Cost_estimate cost_est, ha_rows records, Item where_cond, Opt_trace_object *trace_idx)
	Compute the cost of a IndexSkipScanIterator for a particular index. More...

static bool	find_skip_scans (THD thd, RANGE_OPT_PARAM param, SEL_TREE tree, enum_order order_direction, bool skip_records_in_range, bool find_all_skip_scans, Mem_root_array< IndexSkipScanParameters > *skip_scan_info_list)
	Collect all possible index skip scans and store them in the skip_scan_info_list. More...

static AccessPath *	make_skip_scan_path (RANGE_OPT_PARAM param, bool force_skip_scan, IndexSkipScanParameters skip_scan_info)
	Construct a new INDEX_SKIP_SCAN AccessPath from the IndexSkipScanParameters. More...

Mem_root_array< AccessPath * >	get_all_skip_scans (THD thd, RANGE_OPT_PARAM param, SEL_TREE *tree, enum_order order_direction, bool skip_records_in_range, bool force_skip_scan)
	Test if skip scan is applicable and if so, construct a new AccessPath for each candidate index skip scan. More...

AccessPath *	get_best_skip_scan (THD thd, RANGE_OPT_PARAM param, SEL_TREE *tree, enum_order order_direction, bool skip_records_in_range, bool force_skip_scan)
	Test if skip scan is applicable and if so, construct a new AccessPath. More...

static bool	setup_range_for_skip_scan (SEL_ARG range_sel_arg, RANGE_OPT_PARAM param, IndexSkipScanParameters *skip_scan_info)
	Set up ranges for index skip scan. More...

void	dbug_dump_index_skip_scan (int indent, bool verbose, const AccessPath *path)

Function Documentation

◆ cost_skip_scan()

void cost_skip_scan	(	TABLE *	table,
		uint	key,
		uint	distinct_key_parts,
		ha_rows	quick_prefix_records,
		Cost_estimate *	cost_est,
		ha_rows *	records,
		Item *	where_cond,
		Opt_trace_object *	trace_idx
	)

static

Compute the cost of a IndexSkipScanIterator for a particular index.

SYNOPSIS cost_skip_scan() table [in] The table being accessed key [in] The index used to access the table distinct_key_parts [in] Number of key_parts used to get distinct prefix quick_prefix_records [in] Number of records processed by prefix ranges cost_est [out] The cost to retrieve rows via this quick select records [out] The number of rows retrieved where_cond [in] WHERE condition trace_idx [in] optimizer_trace object

DESCRIPTION This method computes the access cost of an INDEX_SKIP_SCAN access path and the number of rows returned.

NOTES

To estimate the size of the groups to read, index statistics from rec_per_key is used. Each equality range decreases number of the groups to read. The total number of processed records from all the groups will be quick_prefix_records if there are equality ranges else it will be the entire table. Number of distinct group is calculated by dividing the number of processed record by the number keys in a group.

Number of processed records is calculated using following formula:

records = number_of_distinct_groups * records_per_group * filtering_effect

where filtering_effect is filtering effect of the range condition.

RETURN None

◆ dbug_dump_index_skip_scan()

void dbug_dump_index_skip_scan	(	int	indent,
		bool	verbose,
		const AccessPath *	path
	)

◆ find_skip_scans()

bool find_skip_scans	(	THD *	thd,
		RANGE_OPT_PARAM *	param,
		SEL_TREE *	tree,
		enum_order	order_direction,
		bool	skip_records_in_range,
		bool	find_all_skip_scans,
		Mem_root_array< IndexSkipScanParameters * > *	skip_scan_info_list
	)

static

Collect all possible index skip scans and store them in the skip_scan_info_list.

Parameters

	thd	Thread info
	param	Parameter from test_quick_select
	tree	Range tree generated by get_mm_tree
	order_direction	The sort order the range access method must be able to provide. Three-value logic: asc/desc/don't care
	skip_records_in_range	Same value as JOIN_TAB::skip_records_in_range()
	find_all_skip_scans	TRUE if every possible skip scan should be added to skip scan list, FALSE if the best skip scan should be added
[out]	skip_scan_info_list	List of index skip scans

Return values

true	on error, otherwise false.

◆ get_all_skip_scans()

Mem_root_array< AccessPath * > get_all_skip_scans	(	THD *	thd,
		RANGE_OPT_PARAM *	param,
		SEL_TREE *	tree,
		enum_order	order_direction,
		bool	skip_records_in_range,
		bool	force_skip_scan
	)

Test if skip scan is applicable and if so, construct a new AccessPath for each candidate index skip scan.

Parameters

thd	Thread info
param	Parameter from test_quick_select
tree	Range tree generated by get_mm_tree
order_direction	The sort order the range access method must be able to provide. Three-value logic: asc/desc/don't care
skip_records_in_range	Same value as JOIN_TAB::skip_records_in_range()
force_skip_scan	TRUE if skip scan is forced by optimizer hint

Return values

Mem_root_array of candidate INDEX_SKIP_SCAN AccessPaths.

◆ get_best_skip_scan()

AccessPath * get_best_skip_scan	(	THD *	thd,
		RANGE_OPT_PARAM *	param,
		SEL_TREE *	tree,
		enum_order	order_direction,
		bool	skip_records_in_range,
		bool	force_skip_scan
	)

Test if skip scan is applicable and if so, construct a new AccessPath.

DESCRIPTION Test whether a query can be computed via a IndexSkipScanIterator. The overall query form should look like this:

SELECT A_1,...,A_k, B_1,...,B_m, C FROM T WHERE EQ(A_1,...,A_k) AND RNG(C);

Queries computable via a IndexSkipScanIterator must satisfy the following conditions:

A) Table T has at least one compound index I of the form: I = <A_1,...,A_k, B_1,..., B_m, C ,[D_1,...,D_n]> Keyparts A and D may be empty, but B and C must be non-empty. B) Only one table referenced. C) Cannot have group by/select distinct D) Query must reference fields in the index only. E) The predicates on A_1...A_k must be equality predicates and they need to be constants. This includes the 'IN' operator. F) The query must be a conjunctive query. In other words, it is a AND of ORs: (COND1(kp1) OR COND2(kp1)) AND (COND1(kp2) OR ...) AND ... See get_sel_arg_for_keypart for details. G) There must be a range condition on C. H) Conditions on D columns are allowed. Conditions on D must be in conjunction with range condition on C.

NOTES If the current query satisfies the conditions above, and if (mem_root! = NULL), then the function constructs and returns a new AccessPath object, that is later used to construct a new IndexSkipScanIterator.

Parameters

thd	Thread info
param	Parameter from test_quick_select
tree	Range tree generated by get_mm_tree
order_direction	The sort order the range access method must be able to provide. Three-value logic: asc/desc/don't care
skip_records_in_range	Same value as JOIN_TAB::skip_records_in_range()
force_skip_scan	TRUE if skip scan is forced by optimizer hint

Return values

NULL,if skip index scan not applicable, otherwise index skip scan access path.

◆ make_skip_scan_path()

AccessPath * make_skip_scan_path	(	RANGE_OPT_PARAM *	param,
		bool	force_skip_scan,
		IndexSkipScanParameters *	skip_scan_info
	)

static

Construct a new INDEX_SKIP_SCAN AccessPath from the IndexSkipScanParameters.

Parameters

param	Parameter from test_quick_select
force_skip_scan	TRUE if skip scan is forced by optimizer hint
skip_scan_info	Parameters of index skip scan

Return values

INDEX_SKIP_SCAN AccessPath

◆ setup_range_for_skip_scan()

static bool setup_range_for_skip_scan	(	SEL_ARG *	range_sel_arg,
		RANGE_OPT_PARAM *	param,
		IndexSkipScanParameters *	skip_scan_info
	)

static

Set up ranges for index skip scan.

Set flags in skip scan info for null conditions and equality ranges based on the range condition
Alloc storage and set values of min/max range keys

Parameters

range_sel_arg	Range condition info
param	Parameter from test_quick_select
skip_scan_info	Info about a single index skip scan

Return values

true	on error, otherwise false

◆ trace_basic_info_index_skip_scan()

void trace_basic_info_index_skip_scan	(	THD *	thd,
		const AccessPath *	path,
		const RANGE_OPT_PARAM *	param,
		Opt_trace_object *	trace_object
	)

Functions

Function Documentation

◆ cost_skip_scan()

◆ dbug_dump_index_skip_scan()

◆ find_skip_scans()

◆ get_all_skip_scans()

◆ get_best_skip_scan()

◆ make_skip_scan_path()

◆ setup_range_for_skip_scan()

◆ trace_basic_info_index_skip_scan()