rowid_ordered_retrieval_plan.cc File Reference

#include "sql/range_optimizer/rowid_ordered_retrieval_plan.h"
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <utility>
#include "m_ctype.h"
#include "m_string.h"
#include "my_alloc.h"
#include "my_dbug.h"
#include "my_inttypes.h"
#include "sql/key.h"
#include "sql/key_spec.h"
#include "sql/mem_root_array.h"
#include "sql/opt_costmodel.h"
#include "sql/opt_hints.h"
#include "sql/opt_trace.h"
#include "sql/range_optimizer/index_range_scan.h"
#include "sql/range_optimizer/index_range_scan_plan.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/rowid_ordered_retrieval.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/table.h"
#include "sql_string.h"

Classes
struct	ROR_INTERSECT_INFO

Functions
static void	print_ror_scans_arr (TABLE *table, const char *msg, ROR_SCAN_INFO **start, ROR_SCAN_INFO **end)
void	trace_basic_info_rowid_intersection (THD *thd, const AccessPath *path, const RANGE_OPT_PARAM *param, Opt_trace_object *trace_object)
void	trace_basic_info_rowid_union (THD *thd, const AccessPath *path, const RANGE_OPT_PARAM *param, Opt_trace_object *trace_object)
static ROR_SCAN_INFO *	make_ror_scan (const RANGE_OPT_PARAM *param, int idx, SEL_ROOT *sel_root, const MY_BITMAP *needed_fields)
static bool	is_better_intersect_match (const ROR_SCAN_INFO *scan1, const ROR_SCAN_INFO *scan2)
	Compare two ROR_SCAN_INFO* by. More...
static void	find_intersect_order (ROR_SCAN_INFO **start, ROR_SCAN_INFO **end, const RANGE_OPT_PARAM *param, const MY_BITMAP *needed_fields)
	Sort indexes in an order that is likely to be a good index merge intersection order. More...
static ROR_INTERSECT_INFO *	ror_intersect_init (const RANGE_OPT_PARAM *param)
static void	ror_intersect_cpy (ROR_INTERSECT_INFO *dst, const ROR_INTERSECT_INFO *src)
static double	ror_scan_selectivity (const ROR_INTERSECT_INFO *info, const ROR_SCAN_INFO *scan)
static bool	ror_intersect_add (ROR_INTERSECT_INFO *info, const MY_BITMAP *needed_fields, ROR_SCAN_INFO *ror_scan, bool is_cpk_scan, Opt_trace_object *trace_costs, bool ignore_cost)
static AccessPath *	MakeAccessPath (ROR_SCAN_INFO *scan, TABLE *table, KEY_PART *used_key_part, bool reuse_handler, MEM_ROOT *mem_root)
AccessPath *	get_best_ror_intersect (THD *thd, const RANGE_OPT_PARAM *param, TABLE *table, bool index_merge_intersect_allowed, SEL_TREE *tree, const MY_BITMAP *needed_fields, double cost_est, bool force_index_merge_result, bool reuse_handler)
static int	find_max_used_key_length (const AccessPath *scan)
void	add_keys_and_lengths_rowid_intersection (const AccessPath *path, String *key_names, String *used_lengths)
void	add_keys_and_lengths_rowid_union (const AccessPath *path, String *key_names, String *used_lengths)
void	dbug_dump_rowid_intersection (int indent, bool verbose, const Mem_root_array< AccessPath * > &children)
void	dbug_dump_rowid_union (int indent, bool verbose, const Mem_root_array< AccessPath * > &children)

Function Documentation

add_keys_and_lengths_rowid_intersection()

void add_keys_and_lengths_rowid_intersection	(	const AccessPath *	path,
		String *	key_names,
		String *	used_lengths
	)

add_keys_and_lengths_rowid_union()

void add_keys_and_lengths_rowid_union	(	const AccessPath *	path,
		String *	key_names,
		String *	used_lengths
	)

dbug_dump_rowid_intersection()

void dbug_dump_rowid_intersection	(	int	indent,
		bool	verbose,
		const Mem_root_array< AccessPath * > &	children
	)

dbug_dump_rowid_union()

void dbug_dump_rowid_union	(	int	indent,
		bool	verbose,
		const Mem_root_array< AccessPath * > &	children
	)

find_intersect_order()

static void find_intersect_order ( ROR_SCAN_INFO **  start, ROR_SCAN_INFO **  end, const RANGE_OPT_PARAM *  param, const MY_BITMAP *  needed_fields  )

static

Sort indexes in an order that is likely to be a good index merge intersection order.

After running this function, [start, ..., end-1] is ordered according to this strategy:

1) Minimize the number of indexes that must be used in the intersection. I.e., the index covering most fields not already covered by other indexes earlier in the sort order is picked first. 2) When multiple indexes cover equally many uncovered fields, the index with lowest E(Number of rows) is chosen.

Note that all permutations of index ordering are not tested, so this function may not find the optimal order.

Parameters

[in,out]	start	Pointer to the start of indexes that may be used in index merge intersection
	end	Pointer past the last index that may be used.
	param	Parameter from test_quick_select function.
	needed_fields	Bitmask of fields needed by the query.

find_max_used_key_length()

static int find_max_used_key_length ( const AccessPath *  scan )

static

get_best_ror_intersect()

AccessPath * get_best_ror_intersect	(	THD *	thd,
		const RANGE_OPT_PARAM *	param,
		TABLE *	table,
		bool	index_merge_intersect_allowed,
		SEL_TREE *	tree,
		const MY_BITMAP *	needed_fields,
		double	cost_est,
		bool	force_index_merge_result,
		bool	reuse_handler
	)

is_better_intersect_match()

static bool is_better_intersect_match ( const ROR_SCAN_INFO *  scan1, const ROR_SCAN_INFO *  scan2  )

static

Compare two ROR_SCAN_INFO* by.

1. Number of fields in this index that are not already covered by other indexes earlier in the intersect ordering: descending
2. E(Number of records): ascending

Parameters

scan1	first ror scan to compare
scan2	second ror scan to compare

Returns

true if scan1 > scan2, false otherwise

make_ror_scan()

static ROR_SCAN_INFO * make_ror_scan ( const RANGE_OPT_PARAM *  param, int  idx, SEL_ROOT *  sel_root, const MY_BITMAP *  needed_fields  )

static

MakeAccessPath()

static AccessPath * MakeAccessPath ( ROR_SCAN_INFO *  scan, TABLE *  table, KEY_PART *  used_key_part, bool  reuse_handler, MEM_ROOT *  mem_root  )

static

print_ror_scans_arr()

static void print_ror_scans_arr ( TABLE *  table, const char *  msg, ROR_SCAN_INFO **  start, ROR_SCAN_INFO **  end  )

static

ror_intersect_add()

static bool ror_intersect_add ( ROR_INTERSECT_INFO *  info, const MY_BITMAP *  needed_fields, ROR_SCAN_INFO *  ror_scan, bool  is_cpk_scan, Opt_trace_object *  trace_costs, bool  ignore_cost  )

static

ror_intersect_cpy()

static void ror_intersect_cpy ( ROR_INTERSECT_INFO *  dst, const ROR_INTERSECT_INFO *  src  )

static

ror_intersect_init()

static ROR_INTERSECT_INFO * ror_intersect_init ( const RANGE_OPT_PARAM *  param )

static

ror_scan_selectivity()

static double ror_scan_selectivity ( const ROR_INTERSECT_INFO *  info, const ROR_SCAN_INFO *  scan  )

static

key values tuple, used to store both min_range.key and max_range.key. This function is only called for equality ranges; open ranges (e.g. "min_value < X < max_value") cannot be used for rowid ordered retrieval, so in this function we know that min_range.key == max_range.key

trace_basic_info_rowid_intersection()

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

trace_basic_info_rowid_union()

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