summaryrefslogtreecommitdiff
path: root/sql
diff options
context:
space:
mode:
Diffstat (limited to 'sql')
-rw-r--r--sql/filesort.cc114
-rw-r--r--sql/mysql_priv.h15
-rw-r--r--sql/mysqld.cc9
-rw-r--r--sql/opt_range.cc1147
-rw-r--r--sql/opt_range.h69
-rw-r--r--sql/sql_class.h27
-rw-r--r--sql/sql_select.cc15
-rw-r--r--sql/sql_sort.h6
-rw-r--r--sql/table.h2
-rw-r--r--sql/uniques.cc92
-rw-r--r--sql/unireg.h2
11 files changed, 1318 insertions, 180 deletions
diff --git a/sql/filesort.cc b/sql/filesort.cc
index 0e476d3d957..42ce33af1ca 100644
--- a/sql/filesort.cc
+++ b/sql/filesort.cc
@@ -50,10 +50,6 @@ static int write_keys(SORTPARAM *param,uchar * *sort_keys,
uint count, IO_CACHE *buffer_file, IO_CACHE *tempfile);
static void make_sortkey(SORTPARAM *param,uchar *to, uchar *ref_pos);
static void register_used_fields(SORTPARAM *param);
-static int merge_index(SORTPARAM *param,uchar *sort_buffer,
- BUFFPEK *buffpek,
- uint maxbuffer,IO_CACHE *tempfile,
- IO_CACHE *outfile);
static bool save_index(SORTPARAM *param,uchar **sort_keys, uint count,
FILESORT_INFO *table_sort);
static uint suffix_length(ulong string_length);
@@ -145,6 +141,7 @@ ha_rows filesort(THD *thd, TABLE *table, SORT_FIELD *sortorder, uint s_length,
/* filesort cannot handle zero-length records. */
DBUG_ASSERT(param.sort_length);
param.ref_length= table->file->ref_length;
+ param.min_dupl_count= 0;
param.addon_field= 0;
param.addon_length= 0;
if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) &&
@@ -1216,7 +1213,13 @@ int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
rec_length= param->rec_length;
res_length= param->res_length;
sort_length= param->sort_length;
- offset= rec_length-res_length;
+ element_count dupl_count;
+ uchar *src;
+ uint dupl_count_ofs= rec_length-sizeof(element_count);
+ uint min_dupl_count= param->min_dupl_count;
+ offset= rec_length-
+ (flag && min_dupl_count ? sizeof(dupl_count) : 0)-res_length;
+ uint wr_len= flag ? res_length : rec_length;
maxcount= (ulong) (param->keys/((uint) (Tb-Fb) +1));
to_start_filepos= my_b_tell(to_file);
strpos= sort_buffer;
@@ -1262,16 +1265,20 @@ int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
*/
buffpek= (BUFFPEK*) queue_top(&queue);
memcpy(param->unique_buff, buffpek->key, rec_length);
- if (my_b_write(to_file, (uchar*) buffpek->key, rec_length))
- {
- error=1; goto err; /* purecov: inspected */
- }
+ if (min_dupl_count)
+ memcpy(&dupl_count, param->unique_buff+dupl_count_ofs,
+ sizeof(dupl_count));
buffpek->key+= rec_length;
- buffpek->mem_count--;
- if (!--max_rows)
+ if (! --buffpek->mem_count)
{
- error= 0; /* purecov: inspected */
- goto end; /* purecov: inspected */
+ if (!(error= (int) read_to_buffer(from_file,buffpek,
+ rec_length)))
+ {
+ VOID(queue_remove(&queue,0));
+ reuse_freed_buff(&queue, buffpek, rec_length);
+ }
+ else if (error == -1)
+ goto err; /* purecov: inspected */
}
queue_replaced(&queue); // Top element has been used
}
@@ -1287,27 +1294,42 @@ int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
for (;;)
{
buffpek= (BUFFPEK*) queue_top(&queue);
+ src= buffpek->key;
if (cmp) // Remove duplicates
{
if (!(*cmp)(first_cmp_arg, &(param->unique_buff),
(uchar**) &buffpek->key))
- goto skip_duplicate;
- memcpy(param->unique_buff, (uchar*) buffpek->key, rec_length);
- }
- if (flag == 0)
- {
- if (my_b_write(to_file,(uchar*) buffpek->key, rec_length))
- {
- error=1; goto err; /* purecov: inspected */
+ {
+ if (min_dupl_count)
+ {
+ element_count cnt;
+ memcpy(&cnt, (uchar *) buffpek->key+dupl_count_ofs, sizeof(cnt));
+ dupl_count+= cnt;
+ }
+ goto skip_duplicate;
}
+ if (min_dupl_count)
+ {
+ memcpy(param->unique_buff+dupl_count_ofs, &dupl_count,
+ sizeof(dupl_count));
+ }
+ src= param->unique_buff;
}
- else
+
+ if (!flag || !min_dupl_count || dupl_count >= min_dupl_count)
{
- if (my_b_write(to_file, (uchar*) buffpek->key+offset, res_length))
+ if (my_b_write(to_file, src+(flag ? offset : 0), wr_len))
{
error=1; goto err; /* purecov: inspected */
}
}
+ if (cmp)
+ {
+ memcpy(param->unique_buff, (uchar*) buffpek->key, rec_length);
+ if (min_dupl_count)
+ memcpy(&dupl_count, param->unique_buff+dupl_count_ofs,
+ sizeof(dupl_count));
+ }
if (!--max_rows)
{
error= 0; /* purecov: inspected */
@@ -1343,9 +1365,33 @@ int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
{
if (!(*cmp)(first_cmp_arg, &(param->unique_buff), (uchar**) &buffpek->key))
{
- buffpek->key+= rec_length; // Remove duplicate
+ if (min_dupl_count)
+ {
+ element_count cnt;
+ memcpy(&cnt, (uchar *) buffpek->key+dupl_count_ofs, sizeof(cnt));
+ dupl_count+= cnt;
+ }
+ buffpek->key+= rec_length;
--buffpek->mem_count;
}
+
+ if (min_dupl_count)
+ memcpy(param->unique_buff+dupl_count_ofs, &dupl_count,
+ sizeof(dupl_count));
+
+ if (!flag || !min_dupl_count || dupl_count >= min_dupl_count)
+ {
+ src= param->unique_buff;
+ if (my_b_write(to_file, src+(flag ? offset : 0), wr_len))
+ {
+ error=1; goto err; /* purecov: inspected */
+ }
+ if (!--max_rows)
+ {
+ error= 0;
+ goto end;
+ }
+ }
}
do
@@ -1367,12 +1413,17 @@ int merge_buffers(SORTPARAM *param, IO_CACHE *from_file,
else
{
register uchar *end;
- strpos= buffpek->key+offset;
- for (end= strpos+buffpek->mem_count*rec_length ;
- strpos != end ;
- strpos+= rec_length)
- {
- if (my_b_write(to_file, strpos, res_length))
+ src= buffpek->key+offset;
+ for (end= src+buffpek->mem_count*rec_length ;
+ src != end ;
+ src+= rec_length)
+ {
+ if (flag && min_dupl_count &&
+ memcmp(&min_dupl_count, src+dupl_count_ofs,
+ sizeof(dupl_count_ofs))<0)
+ continue;
+
+ if (my_b_write(to_file, src, wr_len))
{
error=1; goto err;
}
@@ -1393,7 +1444,7 @@ err:
/* Do a merge to output-file (save only positions) */
-static int merge_index(SORTPARAM *param, uchar *sort_buffer,
+int merge_index(SORTPARAM *param, uchar *sort_buffer,
BUFFPEK *buffpek, uint maxbuffer,
IO_CACHE *tempfile, IO_CACHE *outfile)
{
@@ -1699,3 +1750,4 @@ void change_double_for_sort(double nr,uchar *to)
}
}
}
+
diff --git a/sql/mysql_priv.h b/sql/mysql_priv.h
index 7905a0f52e5..f8c36d87d52 100644
--- a/sql/mysql_priv.h
+++ b/sql/mysql_priv.h
@@ -338,7 +338,7 @@ protected:
Number of comparisons of table rowids equivalent to reading one row from a
table.
*/
-#define TIME_FOR_COMPARE_ROWID (TIME_FOR_COMPARE*2)
+#define TIME_FOR_COMPARE_ROWID (TIME_FOR_COMPARE*100)
/*
For sequential disk seeks the cost formula is:
@@ -542,12 +542,13 @@ protected:
#define OPTIMIZER_SWITCH_INDEX_MERGE_UNION 2
#define OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION 4
#define OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT 8
+#define OPTIMIZER_SWITCH_INDEX_MERGE_SORT_INTERSECT 16
#ifdef DBUG_OFF
-# define OPTIMIZER_SWITCH_LAST 16
-#else
-# define OPTIMIZER_SWITCH_TABLE_ELIMINATION 16
# define OPTIMIZER_SWITCH_LAST 32
+#else
+# define OPTIMIZER_SWITCH_TABLE_ELIMINATION 32
+# define OPTIMIZER_SWITCH_LAST 64
#endif
#ifdef DBUG_OFF
@@ -555,12 +556,14 @@ protected:
# define OPTIMIZER_SWITCH_DEFAULT (OPTIMIZER_SWITCH_INDEX_MERGE | \
OPTIMIZER_SWITCH_INDEX_MERGE_UNION | \
OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION | \
- OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT)
+ OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT | \
+ OPTIMIZER_SWITCH_INDEX_MERGE_SORT_INTERSECT)
#else
# define OPTIMIZER_SWITCH_DEFAULT (OPTIMIZER_SWITCH_INDEX_MERGE | \
OPTIMIZER_SWITCH_INDEX_MERGE_UNION | \
OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION | \
OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT | \
+ OPTIMIZER_SWITCH_INDEX_MERGE_SORT_INTERSECT | \
OPTIMIZER_SWITCH_TABLE_ELIMINATION)
#endif
@@ -2233,6 +2236,8 @@ ha_rows filesort(THD *thd, TABLE *form,struct st_sort_field *sortorder,
ha_rows max_rows, bool sort_positions,
ha_rows *examined_rows);
void filesort_free_buffers(TABLE *table, bool full);
+double get_merge_many_buffs_cost(uint *buffer, uint last_n_elems,
+ int elem_size);
void change_double_for_sort(double nr,uchar *to);
double my_double_round(double value, longlong dec, bool dec_unsigned,
bool truncate);
diff --git a/sql/mysqld.cc b/sql/mysqld.cc
index c3d58349ad5..9d662ea0174 100644
--- a/sql/mysqld.cc
+++ b/sql/mysqld.cc
@@ -338,7 +338,7 @@ TYPELIB sql_mode_typelib= { array_elements(sql_mode_names)-1,"",
static const char *optimizer_switch_names[]=
{
"index_merge","index_merge_union","index_merge_sort_union",
- "index_merge_intersection",
+ "index_merge_intersection","index_merge_sort_intersection",
#ifndef DBUG_OFF
"table_elimination",
#endif
@@ -352,6 +352,7 @@ static const unsigned int optimizer_switch_names_len[]=
sizeof("index_merge_union") - 1,
sizeof("index_merge_sort_union") - 1,
sizeof("index_merge_intersection") - 1,
+ sizeof("index_merge_sort_intersection") - 1,
#ifndef DBUG_OFF
sizeof("table_elimination") - 1,
#endif
@@ -431,7 +432,8 @@ static const char *sql_mode_str= "OFF";
/* Text representation for OPTIMIZER_SWITCH_DEFAULT */
static const char *optimizer_switch_str="index_merge=on,index_merge_union=on,"
"index_merge_sort_union=on,"
- "index_merge_intersection=on"
+ "index_merge_intersection=on,"
+ "index_merge_sort_intersection=on"
#ifndef DBUG_OFF
",table_elimination=on";
#else
@@ -7297,7 +7299,8 @@ thread is in the relay logs.",
0, GET_ULONG, OPT_ARG, MAX_TABLES+1, 0, MAX_TABLES+2, 0, 1, 0},
{"optimizer_switch", OPT_OPTIMIZER_SWITCH,
"optimizer_switch=option=val[,option=val...], where option={index_merge, "
- "index_merge_union, index_merge_sort_union, index_merge_intersection"
+ "index_merge_union, index_merge_sort_union, index_merge_intersection, "
+ "index_merge_sort_intersection"
#ifndef DBUG_OFF
", table_elimination"
#endif
diff --git a/sql/opt_range.cc b/sql/opt_range.cc
index 6ca9ff5e823..47d0b6a58a8 100644
--- a/sql/opt_range.cc
+++ b/sql/opt_range.cc
@@ -697,6 +697,9 @@ public:
key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
uint n_ror_scans; /* number of set bits in ror_scans_map */
+ struct st_index_scan_info **index_scans; /* list of index scans */
+ struct st_index_scan_info **index_scans_end; /* last index scan */
+
struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
/* Note that #records for each key scan is stored in table->quick_rows */
@@ -776,9 +779,11 @@ class TABLE_READ_PLAN;
class TRP_RANGE;
class TRP_ROR_INTERSECT;
class TRP_ROR_UNION;
+ class TRP_INDEX_INTERSECT;
class TRP_INDEX_MERGE;
class TRP_GROUP_MIN_MAX;
+struct st_index_scan_info;
struct st_ror_scan_info;
static SEL_TREE * get_mm_parts(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
@@ -804,6 +809,9 @@ static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
bool update_tbl_stats,
double read_time);
static
+TRP_INDEX_INTERSECT *get_best_index_intersect(PARAM *param, SEL_TREE *tree,
+ double read_time);
+static
TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
double read_time,
bool *are_all_covering);
@@ -1093,7 +1101,7 @@ int SEL_IMERGE::or_sel_tree_with_checks(RANGE_OPT_PARAM *param,
{
bool must_be_ored= sel_trees_must_be_ored(param, *or_tree, tree,
ored_keys);
- if (must_be_ored == is_first_check_pass)
+ if (must_be_ored || !is_first_check_pass)
{
result_keys.clear_all();
result= *or_tree;
@@ -1749,7 +1757,7 @@ int QUICK_INDEX_MERGE_SELECT::init()
int QUICK_INDEX_MERGE_SELECT::reset()
{
DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::reset");
- DBUG_RETURN(read_keys_and_merge());
+ DBUG_RETURN (read_keys_and_merge());
}
bool
@@ -1785,6 +1793,64 @@ QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
DBUG_VOID_RETURN;
}
+QUICK_INDEX_INTERSECT_SELECT::QUICK_INDEX_INTERSECT_SELECT(THD *thd_param,
+ TABLE *table)
+ :unique(NULL), pk_quick_select(NULL), thd(thd_param)
+{
+ DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::QUICK_INDEX_INTERSECT_SELECT");
+ index= MAX_KEY;
+ head= table;
+ bzero(&read_record, sizeof(read_record));
+ init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
+ DBUG_VOID_RETURN;
+}
+
+int QUICK_INDEX_INTERSECT_SELECT::init()
+{
+ DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::init");
+ DBUG_RETURN(0);
+}
+
+int QUICK_INDEX_INTERSECT_SELECT::reset()
+{
+ DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::reset");
+ DBUG_RETURN (read_keys_and_merge());
+}
+
+bool
+QUICK_INDEX_INTERSECT_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick_sel_range)
+{
+ /*
+ Save quick_select that does scan on clustered primary key as it will be
+ processed separately.
+ */
+ if (head->file->primary_key_is_clustered() &&
+ quick_sel_range->index == head->s->primary_key)
+ pk_quick_select= quick_sel_range;
+ else
+ return quick_selects.push_back(quick_sel_range);
+ return 0;
+}
+
+QUICK_INDEX_INTERSECT_SELECT::~QUICK_INDEX_INTERSECT_SELECT()
+{
+ List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
+ QUICK_RANGE_SELECT* quick;
+ DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::~QUICK_INDEX_INTERSECT_SELECT");
+ delete unique;
+ quick_it.rewind();
+ while ((quick= quick_it++))
+ quick->file= NULL;
+ quick_selects.delete_elements();
+ delete pk_quick_select;
+ /* It's ok to call the next two even if they are already deinitialized */
+ end_read_record(&read_record);
+ free_io_cache(head);
+ free_root(&alloc,MYF(0));
+ DBUG_VOID_RETURN;
+}
+
+
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(THD *thd_param,
TABLE *table,
@@ -2576,6 +2642,24 @@ public:
/*
+ Plan for QUICK_INDEX_INTERSECT_SELECT scan.
+ QUICK_INDEX_INTERSECT_SELECT always retrieves full rows, so retrieve_full_rows
+ is ignored by make_quick.
+*/
+
+class TRP_INDEX_INTERSECT : public TABLE_READ_PLAN
+{
+public:
+ TRP_INDEX_INTERSECT() {} /* Remove gcc warning */
+ virtual ~TRP_INDEX_INTERSECT() {} /* Remove gcc warning */
+ QUICK_SELECT_I *make_quick(PARAM *param, bool retrieve_full_rows,
+ MEM_ROOT *parent_alloc);
+ TRP_RANGE **range_scans; /* array of ptrs to plans of intersected scans */
+ TRP_RANGE **range_scans_end; /* end of the array */
+};
+
+
+/*
Plan for QUICK_INDEX_MERGE_SELECT scan.
QUICK_ROR_INTERSECT_SELECT always retrieves full rows, so retrieve_full_rows
is ignored by make_quick.
@@ -2642,6 +2726,35 @@ public:
};
+typedef struct st_index_scan_info
+{
+ uint idx; /* # of used key in param->keys */
+ uint keynr; /* # of used key in table */
+ uint range_count;
+ ha_rows records; /* estimate of # records this scan will return */
+
+ /* Set of intervals over key fields that will be used for row retrieval. */
+ SEL_ARG *sel_arg;
+
+ KEY *key_info;
+ uint used_key_parts;
+
+ MY_BITMAP used_fields;
+
+ /* Fields used in the query and covered by ROR scan. */
+ MY_BITMAP covered_fields;
+ uint used_fields_covered; /* # of set bits in covered_fields */
+ int key_rec_length; /* length of key record (including rowid) */
+
+ /*
+ Cost of reading all index records with values in sel_arg intervals set
+ (assuming there is no need to access full table records)
+ */
+ double index_read_cost;
+ uint first_uncovered_field; /* first unused bit in covered_fields */
+ uint key_components; /* # of parts in the key */
+} INDEX_SCAN_INFO;
+
/*
Fill param->needed_fields with bitmap of fields used in the query.
SYNOPSIS
@@ -2919,6 +3032,7 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
*/
TRP_RANGE *range_trp;
TRP_ROR_INTERSECT *rori_trp;
+ TRP_INDEX_INTERSECT *intersect_trp;
bool can_build_covering= FALSE;
remove_nonrange_trees(&param, tree);
@@ -2958,6 +3072,17 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
best_trp= rori_trp;
}
}
+ if (optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE) &&
+ optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE_SORT_INTERSECT))
+ {
+ if ((intersect_trp= get_best_index_intersect(&param, tree,
+ best_read_time)))
+ {
+ best_trp= intersect_trp;
+ best_read_time= best_trp->read_cost;
+
+ }
+ }
if (optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE))
{
@@ -4388,7 +4513,9 @@ TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge,
imerge_cost +=
Unique::get_use_cost(param->imerge_cost_buff, (uint)non_cpk_scan_records,
param->table->file->ref_length,
- param->thd->variables.sortbuff_size);
+ param->thd->variables.sortbuff_size,
+ TIME_FOR_COMPARE_ROWID,
+ FALSE, NULL);
DBUG_PRINT("info",("index_merge total cost: %g (wanted: less then %g)",
imerge_cost, read_time));
if (imerge_cost < read_time)
@@ -4621,27 +4748,680 @@ TABLE_READ_PLAN *merge_same_index_scans(PARAM *param, SEL_IMERGE *imerge,
DBUG_RETURN(trp);
}
-typedef struct st_ror_scan_info
+
+/*
+ This structure contains the info common for all steps of a partial
+ index intersection plan. Morever it contains also the info common
+ for index intersect plans. This info is filled in by the function
+ prepare_search_best just before searching for the best index
+ intersection plan.
+*/
+
+typedef struct st_common_index_intersection_info
+{
+ PARAM *param; /* context info for range optimizations */
+ uint key_size; /* size of a ROWID element stored in Unique object */
+ uint compare_factor; /* 1/compare - cost to compare two ROWIDs */
+ ulonglong max_memory_size; /* maximum space allowed for Unique objects */
+ ha_rows table_cardinality; /* estimate of the number of records in table */
+ double cutoff_cost; /* discard index intersects with greater costs */
+ INDEX_SCAN_INFO *cpk_scan; /* clustered primary key used in intersection */
+
+ bool in_memory; /* unique object for intersection is completely in memory */
+ /* estimate of the number of records filtered out from the first scan by
+ ranges for the clustered primary key scan (cpk_scan) */
+ ha_rows filtered_out_records;
+ double filter_cost; /* cost of checking the the cpk_scan rabhe conditions */
+
+ INDEX_SCAN_INFO **search_scans; /* scans possibly included in intersect */
+ uint n_search_scans; /* number of elements in search_scans */
+
+ bool best_uses_cpk; /* current best intersect uses clustered primary key */
+ double best_cost; /* cost of the current best index intersection */
+ /* estimate of the number of records in the current best intersection */
+ ha_rows best_records;
+ uint best_length; /* number of indexes in the current best intersection */
+ INDEX_SCAN_INFO **best_intersect; /* the current best index intersection */
+
+ uint *buff_elems; /* buffer to calculate cost of index intersection */
+
+} COMMON_INDEX_INTERSECTION_INFO;
+
+
+/*
+ This structure contains the info specific for one step of an index
+ intersection plan. The structure is filled in by the function
+ check_index_intersect_extension.
+*/
+
+typedef struct st_partial_index_intersection_info
{
- uint idx; /* # of used key in param->keys */
- uint keynr; /* # of used key in table */
- ha_rows records; /* estimate of # records this scan will return */
+ COMMON_INDEX_INTERSECTION_INFO *common_info; /* shared by index intersects */
+ uint length; /* number of index scans in the partial intersection */
+ ha_rows records; /* estimate of the number of records in intersection */
+ double cost; /* cost of the partial index intersection */
- /* Set of intervals over key fields that will be used for row retrieval. */
- SEL_ARG *sel_arg;
+ /* estimate of total number of records in all index scans of intersection */
+ ha_rows records_in_scans;
- /* Fields used in the query and covered by this ROR scan. */
- MY_BITMAP covered_fields;
- uint used_fields_covered; /* # of set bits in covered_fields */
- int key_rec_length; /* length of key record (including rowid) */
+ /* total cost of the scans of indexes from the partial index intersection */
+ double index_read_cost;
- /*
- Cost of reading all index records with values in sel_arg intervals set
- (assuming there is no need to access full table records)
- */
- double index_read_cost;
- uint first_uncovered_field; /* first unused bit in covered_fields */
- uint key_components; /* # of parts in the key */
+ bool with_cpk_filter; /* cpk filter is to be used for the first scan */
+ bool in_memory; /* uses unique object in memory */
+ double in_memory_cost; /* cost of using unique object in memory */
+
+ MY_BITMAP *intersect_fields; /* bitmap of fields used in intersection */
+} PARTIAL_INDEX_INTERSECTION_INFO;
+
+
+/* Check whether two indexes have the same first n components */
+
+static
+bool same_index_prefix(KEY *key1, KEY *key2, uint used_parts)
+{
+ KEY_PART_INFO *part1= key1->key_part;
+ KEY_PART_INFO *part2= key2->key_part;
+ for(uint i= 0; i < used_parts; i++, part1++, part2++)
+ {
+ if (part1->fieldnr != part2->fieldnr)
+ return FALSE;
+ }
+ return TRUE;
+}
+
+
+/* Create a bitmap for all fields of a table */
+
+static
+bool create_fields_bitmap(PARAM *param, MY_BITMAP *fields_bitmap)
+{
+ my_bitmap_map *bitmap_buf;
+
+ if (!(bitmap_buf= (my_bitmap_map *) alloc_root(param->mem_root,
+ param->fields_bitmap_size)))
+ return TRUE;
+ if (bitmap_init(fields_bitmap, bitmap_buf, param->table->s->fields, FALSE))
+ return TRUE;
+
+ return FALSE;
+}
+
+/* Compare two indexes scans for sort before search for the best intersection */
+
+static
+int cmp_intersect_index_scan(INDEX_SCAN_INFO **a, INDEX_SCAN_INFO **b)
+{
+ return (*a)->records < (*b)->records ?
+ -1 : (*a)->records == (*b)->records ? 0 : 1;
+}
+
+
+/*
+ Round up table cardinality read from statistics provided by engine.
+ This function should go away when mysql test will allow to handle
+ more or less easily in the test suites deviations of InnoDB
+ statistical data.
+*/
+
+static inline
+ha_rows get_table_cardinality_for_index_intersect(TABLE *table)
+{
+ if (table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT)
+ return table->file->stats.records;
+ else
+ {
+ ha_rows d;
+ double q;
+ for (q= table->file->stats.records, d= 1 ; q >= 10; q/= 10, d*= 10 ) ;
+ return (ha_rows) (round(q) * d);
+ }
+}
+
+
+/*
+ Prepare to search for the best index intersection
+
+ SYNOPSIS
+ prepare_search_best_index_intersect()
+ param common info about index ranges
+ tree tree of ranges for indexes than can be intersected
+ common OUT info needed for search to be filled by the function
+ init OUT info for an initial pseudo step of the intersection plans
+ cutoff_cost cut off cost of the interesting index intersection
+
+ NOTES
+ The function initializes all fields of the structure 'common' to be used
+ when searching for the best intersection plan. It also allocates
+ memory to store the most cheap index intersection.
+
+ RETURN
+ FALSE in the case of success
+ TRUE otherwise
+*/
+
+static
+bool prepare_search_best_index_intersect(PARAM *param,
+ SEL_TREE *tree,
+ COMMON_INDEX_INTERSECTION_INFO *common,
+ PARTIAL_INDEX_INTERSECTION_INFO *init,
+ double cutoff_cost)
+{
+ uint i;
+ double cost;
+ INDEX_SCAN_INFO **index_scan;
+ INDEX_SCAN_INFO **scan_ptr;
+ INDEX_SCAN_INFO *cpk_scan= NULL;
+ TABLE *table= param->table;
+ uint n_index_scans= tree->index_scans_end - tree->index_scans;
+
+ if (!n_index_scans)
+ return 1;
+
+ bzero(init, sizeof(PARTIAL_INDEX_INTERSECTION_INFO));
+ init->common_info= common;
+ init->cost= cutoff_cost+2*0.01;
+
+ common->param= param;
+ common->key_size= table->file->ref_length;
+ common->compare_factor= TIME_FOR_COMPARE_ROWID;
+ common->max_memory_size= param->thd->variables.sortbuff_size;
+ common->cutoff_cost= cutoff_cost;
+ common->cpk_scan= NULL;
+ common->filtered_out_records= 0;
+ common->table_cardinality=
+ get_table_cardinality_for_index_intersect(table);
+
+ if (n_index_scans <= 1)
+ return TRUE;
+
+ for (i=0, index_scan= tree->index_scans; i < n_index_scans; i++, index_scan++)
+ {
+ if ((*index_scan)->keynr == table->s->primary_key &&
+ table->file->primary_key_is_clustered())
+ {
+ common->cpk_scan= cpk_scan= *index_scan;
+ break;
+ }
+ }
+
+ i= n_index_scans - test(cpk_scan != NULL) + 1;
+
+ if (!(common->search_scans =
+ (INDEX_SCAN_INFO **) alloc_root (param->mem_root,
+ sizeof(INDEX_SCAN_INFO *) * i)))
+ return TRUE;
+ bzero(common->search_scans, sizeof(INDEX_SCAN_INFO *) * i);
+
+ INDEX_SCAN_INFO **selected_index_scans= common->search_scans;
+
+ for (i=0, index_scan= tree->index_scans; i < n_index_scans; i++, index_scan++)
+ {
+ uint used_key_parts= (*index_scan)->used_key_parts;
+ KEY *key_info= (*index_scan)->key_info;
+
+ if (*index_scan == cpk_scan)
+ continue;
+ if (cpk_scan && cpk_scan->used_key_parts == used_key_parts &&
+ same_index_prefix(cpk_scan->key_info, key_info, used_key_parts))
+ continue;
+
+ cost= table->file->keyread_time((*index_scan)->keynr,
+ (*index_scan)->range_count,
+ (*index_scan)->records);
+ if (cost >= cutoff_cost)
+ continue;
+
+ for (scan_ptr= selected_index_scans; *scan_ptr ; scan_ptr++)
+ {
+ if ((*scan_ptr)->used_key_parts == used_key_parts &&
+ same_index_prefix((*scan_ptr)->key_info, key_info, used_key_parts))
+ break;
+ }
+ if (!*scan_ptr || cost < (*scan_ptr)->index_read_cost)
+ {
+ (*index_scan)->index_read_cost= cost;
+ *scan_ptr= *index_scan;
+ }
+ }
+
+ ha_rows records_in_scans= 0;
+
+ for (scan_ptr=selected_index_scans, i= 0; *scan_ptr; scan_ptr++, i++)
+ {
+ if (create_fields_bitmap(param, &(*scan_ptr)->used_fields))
+ return TRUE;
+ records_in_scans+= (*scan_ptr)->records;
+ }
+
+ if (cpk_scan && create_fields_bitmap(param, &cpk_scan->used_fields))
+ return TRUE;
+
+ if (!(common->n_search_scans= i))
+ return TRUE;
+
+ common->best_uses_cpk= FALSE;
+ common->best_cost= cutoff_cost + 0.01;
+ common->best_length= 0;
+
+ if (!(common->best_intersect=
+ (INDEX_SCAN_INFO **) alloc_root (param->mem_root,
+ sizeof(INDEX_SCAN_INFO *) *
+ (i + test(cpk_scan != NULL)))))
+ return TRUE;
+
+ uint calc_cost_buff_size=
+ Unique::get_cost_calc_buff_size(records_in_scans,
+ common->key_size,
+ common->max_memory_size);
+ if (!(common->buff_elems= (uint *) alloc_root(param->mem_root,
+ calc_cost_buff_size)))
+ return TRUE;
+
+ my_qsort(selected_index_scans, i, sizeof(INDEX_SCAN_INFO *),
+ (qsort_cmp) cmp_intersect_index_scan);
+
+ return FALSE;
+}
+
+
+static inline
+void set_field_bitmap_for_index_prefix(MY_BITMAP *field_bitmap,
+ KEY_PART_INFO *key_part,
+ uint used_key_parts)
+{
+ bitmap_clear_all(field_bitmap);
+ for (KEY_PART_INFO *key_part_end= key_part+used_key_parts;
+ key_part < key_part_end; key_part++)
+ {
+ bitmap_set_bit(field_bitmap, key_part->fieldnr-1);
+ }
+}
+
+/*
+ Estimate the number of records selected by an extension a partial intersection
+
+ SYNOPSIS
+ records_in_index_intersect_extension()
+ curr partial intersection plan to be extended
+ ext_index_scan the evaluated extension of this partial plan
+
+ NOTES
+ The function figures out how many records can be expected if the
+ index scans from curr is intersected with ext_index_scan
+
+ RETURN
+ The expected number of rows in the extended index intersection
+*/
+
+static
+ha_rows records_in_index_intersect_extension(PARTIAL_INDEX_INTERSECTION_INFO *curr,
+ INDEX_SCAN_INFO *ext_index_scan)
+{
+ KEY *key_info= ext_index_scan->key_info;
+ KEY_PART_INFO* key_part= key_info->key_part;
+ KEY_PART_INFO* key_part_end= key_part+ext_index_scan->used_key_parts;
+ uint key_parts= key_info->key_parts;
+ MY_BITMAP *used_fields= &ext_index_scan->used_fields;
+
+ if (!curr->length)
+ {
+ set_field_bitmap_for_index_prefix(used_fields, key_part,
+ ext_index_scan->used_key_parts);
+ return ext_index_scan->records;
+ }
+ else
+ {
+ bool better_selectivity= FALSE;
+ ha_rows table_cardinality= curr->common_info->table_cardinality;
+ ha_rows records= curr->records;
+ bitmap_copy(used_fields, curr->intersect_fields);
+ records= (double) records / table_cardinality * ext_index_scan->records;
+ set_if_bigger(records, 1);
+ for (uint i= 0 ; key_part < key_part_end; i++, key_part++)
+ {
+ if (bitmap_is_set(used_fields, key_part->fieldnr-1))
+ {
+ ulong *rec_per_key= key_info->rec_per_key+i;
+ ulong f1= rec_per_key[0] ? rec_per_key[0] : 1;
+ ulong f2= i+1 < key_parts && rec_per_key[1] ? rec_per_key[1] : 1;
+ records= (double) records / f2 * f1;
+ }
+ else
+ {
+ better_selectivity= TRUE;
+ bitmap_set_bit(used_fields, key_part->fieldnr-1);
+ }
+ }
+ return !better_selectivity ? curr->records+1 :
+ !records ? 1 : records;
+ }
+}
+
+
+static inline
+double get_unique_intersect_cost(COMMON_INDEX_INTERSECTION_INFO *common,
+ uint length, ha_rows records_in_scans,
+ ha_rows filtered_out_records,
+ ha_rows last_index_records,
+ bool *in_memory,
+ double *in_memory_cost)
+{
+ double cost;
+ if (length > 1 && *in_memory)
+ {
+ ha_rows records_in_first_scan= common->search_scans[0]->records;
+ ha_rows elems_in_tree= records_in_first_scan-filtered_out_records;
+ *in_memory_cost+= Unique::get_search_cost(elems_in_tree,
+ common->compare_factor) *
+ last_index_records;
+ cost= *in_memory_cost;
+ }
+ else
+ {
+ ha_rows records_to_intersect= records_in_scans-filtered_out_records;
+ cost= Unique::get_use_cost(common->buff_elems,
+ records_to_intersect,
+ common->key_size,
+ common->max_memory_size,
+ common->compare_factor,
+ TRUE, in_memory);
+ if (*in_memory)
+ *in_memory_cost= cost;
+ }
+ return cost;
+}
+
+
+static inline
+double get_cpk_filter_cost(INDEX_SCAN_INFO *index_scan,
+ INDEX_SCAN_INFO *cpk_scan,
+ double compare_factor)
+{
+ return log((double) (cpk_scan->range_count+1)) / (compare_factor * M_LN2) *
+ index_scan->records;
+}
+
+
+/*
+ Check whether a patial index intersection plan can be extended
+
+ SYNOPSIS
+ check_index_intersect_extension()
+ curr partial intersection plan to be extended
+ ext_index_scan a possible extension of this plan to be checked
+ next OUT the structure to be filled for the extended plan
+
+ NOTES
+ The function checks whether it makes sense to extend the index
+ intersection plan adding the index ext_index_scan, and, if this
+ the case, the function fills in the structure fir the extended plan.
+
+ RETURN
+ TRUE if the given plan makes to extend
+ FALSE otherwise
+*/
+
+static
+bool check_index_intersect_extension(PARTIAL_INDEX_INTERSECTION_INFO *curr,
+ INDEX_SCAN_INFO *ext_index_scan,
+ PARTIAL_INDEX_INTERSECTION_INFO *next)
+{
+ ha_rows records;
+ ha_rows records2;
+ ha_rows records_in_scans;
+ double cost;
+ ha_rows filtered_out_records= 0;
+ ha_rows index_scan_records= ext_index_scan->records;
+ COMMON_INDEX_INTERSECTION_INFO *common_info= curr->common_info;
+ INDEX_SCAN_INFO *cpk_scan= common_info->cpk_scan;
+ double cutoff_cost= common_info->cutoff_cost;
+ uint compare_factor= common_info->compare_factor;
+ uint idx= curr->length;
+ bool with_cpk_filter= curr->with_cpk_filter;
+
+ if (with_cpk_filter)
+ filtered_out_records= common_info->filtered_out_records;
+
+ next->index_read_cost= curr->index_read_cost+ext_index_scan->index_read_cost;
+ if (next->index_read_cost > cutoff_cost)
+ return FALSE;
+
+ records_in_scans= curr->records_in_scans + index_scan_records;
+ if ((next->in_memory= curr->in_memory))
+ next->in_memory_cost= curr->in_memory_cost;
+
+ records= records_in_index_intersect_extension(curr, ext_index_scan);
+ if (idx && records > curr->records)
+ return FALSE;
+
+ next->records= records;
+ next->intersect_fields= &ext_index_scan->used_fields;
+
+ cost= get_unique_intersect_cost(common_info, idx+1, records_in_scans,
+ filtered_out_records, index_scan_records,
+ &next->in_memory, &next->in_memory_cost);
+
+ if (idx == 0 && cpk_scan)
+ {
+ next->length= 1;
+ records2= records_in_index_intersect_extension(next, cpk_scan);
+ next->length= 0;
+ if (records2 < records)
+ filtered_out_records= records-records2;
+
+ common_info->filter_cost= get_cpk_filter_cost(ext_index_scan, cpk_scan,
+ compare_factor);
+ common_info->filtered_out_records= filtered_out_records;
+ }
+
+ next->records_in_scans= records_in_scans;
+ next->with_cpk_filter= with_cpk_filter;
+
+ if (!with_cpk_filter && common_info->filtered_out_records)
+ {
+ double cost2;
+ bool in_memory_save= next->in_memory;
+ if (idx)
+ {
+ next->length= curr->length+1;
+ records2= records_in_index_intersect_extension(next, cpk_scan);
+ next->length= curr->length;
+ }
+ cost2= get_unique_intersect_cost(common_info, idx+1, records_in_scans,
+ filtered_out_records, index_scan_records,
+ &next->in_memory, &next->in_memory_cost);
+ cost2+= common_info->filter_cost;
+ if (cost2 < cost)
+ {
+ cost= cost2;
+ records= records2;
+ next->with_cpk_filter= TRUE;
+ *next->intersect_fields= cpk_scan->used_fields;
+ }
+ else
+ next->in_memory= in_memory_save;
+ }
+
+ cost+= next->index_read_cost;
+ if (cost >= cutoff_cost)
+ return FALSE;
+
+ next->records= records;
+
+ cost+= get_sweep_read_cost(common_info->param, records);
+
+ next->cost= cost;
+ next->length= curr->length+1;
+
+ return TRUE;
+}
+
+
+/*
+ Search for the cheapest extensions of range scans used to access a table
+
+ SYNOPSIS
+ find_index_intersect_best_extension()
+ curr partial intersection to evaluate all possible extension for
+
+ NOTES
+ The function tries to extend the partial plan curr in all possible ways
+ to look for a cheapest index intersection whose cost less than the
+ cut off value set in curr->common_info.cutoff_cost.
+*/
+
+static
+void find_index_intersect_best_extension(PARTIAL_INDEX_INTERSECTION_INFO *curr)
+{
+ PARTIAL_INDEX_INTERSECTION_INFO next;
+ COMMON_INDEX_INTERSECTION_INFO *common_info= curr->common_info;
+ INDEX_SCAN_INFO **index_scans= common_info->search_scans;
+ uint idx= curr->length;
+ INDEX_SCAN_INFO **rem_first_index_scan_ptr= &index_scans[idx];
+ double cost= curr->cost;
+
+ if (cost < common_info->best_cost)
+ {
+ common_info->best_cost= cost;
+ common_info->best_length= curr->length;
+ common_info->best_records= curr->records;
+ common_info->best_uses_cpk= curr->with_cpk_filter;
+ uint sz= sizeof(INDEX_SCAN_INFO *) * curr->length;
+ memcpy(common_info->best_intersect, common_info->search_scans, sz);
+ common_info->cutoff_cost= cost;
+ }
+
+ if (!(*rem_first_index_scan_ptr))
+ return;
+
+ next.common_info= common_info;
+
+ INDEX_SCAN_INFO *rem_first_index_scan= *rem_first_index_scan_ptr;
+ for (INDEX_SCAN_INFO **index_scan_ptr= rem_first_index_scan_ptr;
+ *index_scan_ptr; index_scan_ptr++)
+ {
+ *rem_first_index_scan_ptr= *index_scan_ptr;
+ *index_scan_ptr= rem_first_index_scan;
+ if (check_index_intersect_extension(curr, *rem_first_index_scan_ptr, &next))
+ find_index_intersect_best_extension(&next);
+ *index_scan_ptr= *rem_first_index_scan_ptr;
+ *rem_first_index_scan_ptr= rem_first_index_scan;
+ }
+}
+
+
+/*
+ Get the plan of the best intersection of range scans used to access a table
+
+ SYNOPSIS
+ get_best_index_intersect()
+ param common info about index ranges
+ tree tree of ranges for indexes than can be intersected
+ read_time cut off value for the evaluated plans
+
+ NOTES
+ The function looks for the cheapest index intersection of the range
+ scans to access a table. The info about the ranges for all indexes
+ is provided by the range optimizer and is passed through the
+ parameters param and tree. Any plan whose cost is greater than read_time
+ is rejected.
+ After the best index intersection is found the function constructs
+ the structure that manages the execution by the chosen plan.
+
+ RETURN
+ Pointer to the generated execution structure if a success,
+ 0 - otherwise.
+*/
+
+static
+TRP_INDEX_INTERSECT *get_best_index_intersect(PARAM *param, SEL_TREE *tree,
+ double read_time)
+{
+ uint i;
+ uint count;
+ TRP_RANGE **cur_range;
+ TRP_RANGE **range_scans;
+ INDEX_SCAN_INFO *index_scan;
+ COMMON_INDEX_INTERSECTION_INFO common;
+ PARTIAL_INDEX_INTERSECTION_INFO init;
+ TRP_INDEX_INTERSECT *intersect_trp= NULL;
+ TABLE *table= param->table;
+
+
+ DBUG_ENTER("get_best_index_intersect");
+
+ if (prepare_search_best_index_intersect(param, tree, &common, &init,
+ read_time))
+ DBUG_RETURN(NULL);
+
+ find_index_intersect_best_extension(&init);
+
+ if (common.best_length <= 1 && !common.best_uses_cpk)
+ DBUG_RETURN(NULL);
+
+ if (common.best_uses_cpk)
+ {
+ memmove((char *) (common.best_intersect+1), (char *) common.best_intersect,
+ sizeof(INDEX_SCAN_INFO *) * common.best_length);
+ common.best_intersect[0]= common.cpk_scan;
+ common.best_length++;
+ }
+
+ count= common.best_length;
+
+ if (!(range_scans= (TRP_RANGE**)alloc_root(param->mem_root,
+ sizeof(TRP_RANGE *)*
+ count)))
+ DBUG_RETURN(NULL);
+
+ for (i= 0, cur_range= range_scans; i < count; i++)
+ {
+ index_scan= common.best_intersect[i];
+ if ((*cur_range= new (param->mem_root) TRP_RANGE(index_scan->sel_arg,
+ index_scan->idx)))
+ {
+ TRP_RANGE *trp= *cur_range;
+ trp->read_cost= index_scan->index_read_cost;
+ trp->records= index_scan->records;
+ trp->is_ror= FALSE;
+ table->intersect_keys.set_bit(index_scan->keynr);
+ cur_range++;
+ }
+ }
+
+ count= tree->index_scans_end - tree->index_scans;
+ for (i= 0; i < count; i++)
+ {
+ index_scan= tree->index_scans[i];
+ if (!table->intersect_keys.is_set(index_scan->keynr))
+ {
+ for (uint j= 0; j < common.best_length; j++)
+ {
+ INDEX_SCAN_INFO *scan= common.best_intersect[j];
+ if (same_index_prefix(index_scan->key_info, scan->key_info,
+ scan->used_key_parts))
+ {
+ table->intersect_keys.set_bit(index_scan->keynr);
+ break;
+ }
+ }
+ }
+ }
+
+ if ((intersect_trp= new (param->mem_root)TRP_INDEX_INTERSECT))
+ {
+ intersect_trp->read_cost= common.best_cost;
+ intersect_trp->records= common.best_records;
+ intersect_trp->range_scans= range_scans;
+ intersect_trp->range_scans_end= cur_range;
+ }
+ DBUG_RETURN(intersect_trp);
+}
+
+
+typedef struct st_ror_scan_info : INDEX_SCAN_INFO
+{
} ROR_SCAN_INFO;
@@ -5313,7 +6093,7 @@ TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
/*
Get best covering ROR-intersection.
SYNOPSIS
- get_best_covering_ror_intersect()
+ get_best_ntersectcovering_ror_intersect()
param Parameter from test_quick_select function.
tree SEL_TREE with sets of intervals for different keys.
read_time Don't return table read plans with cost > read_time.
@@ -5500,6 +6280,14 @@ static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
"tree scans"););
tree->ror_scans_map.clear_all();
tree->n_ror_scans= 0;
+ tree->index_scans= 0;
+ if (!tree->keys_map.is_clear_all())
+ {
+ tree->index_scans=
+ (INDEX_SCAN_INFO **) alloc_root(param->mem_root,
+ sizeof(INDEX_SCAN_INFO *) * param->keys);
+ }
+ tree->index_scans_end= tree->index_scans;
for (idx= 0,key=tree->keys, end=key+param->keys;
key != end ;
key++,idx++)
@@ -5508,6 +6296,7 @@ static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
double found_read_time;
if (*key)
{
+ INDEX_SCAN_INFO *index_scan;
uint keynr= param->real_keynr[idx];
if ((*key)->type == SEL_ARG::MAYBE_KEY ||
(*key)->maybe_flag)
@@ -5517,6 +6306,19 @@ static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
(bool) param->table->covering_keys.is_set(keynr);
found_records= check_quick_select(param, idx, *key, update_tbl_stats);
+ if (found_records != HA_POS_ERROR && tree->index_scans &&
+ (index_scan= (INDEX_SCAN_INFO *)alloc_root(param->mem_root,
+ sizeof(INDEX_SCAN_INFO))))
+ {
+ index_scan->idx= idx;
+ index_scan->keynr= keynr;
+ index_scan->key_info= &param->table->key_info[keynr];
+ index_scan->used_key_parts= param->max_key_part+1;
+ index_scan->range_count= param->range_count;
+ index_scan->records= found_records;
+ index_scan->sel_arg= *key;
+ *tree->index_scans_end++= index_scan;
+ }
if (param->is_ror_scan)
{
tree->n_ror_scans++;
@@ -5611,6 +6413,35 @@ QUICK_SELECT_I *TRP_INDEX_MERGE::make_quick(PARAM *param,
return quick_imerge;
}
+
+QUICK_SELECT_I *TRP_INDEX_INTERSECT::make_quick(PARAM *param,
+ bool retrieve_full_rows,
+ MEM_ROOT *parent_alloc)
+{
+ QUICK_INDEX_INTERSECT_SELECT *quick_intersect;
+ QUICK_RANGE_SELECT *quick;
+ /* index_merge always retrieves full rows, ignore retrieve_full_rows */
+ if (!(quick_intersect= new QUICK_INDEX_INTERSECT_SELECT(param->thd, param->table)))
+ return NULL;
+
+ quick_intersect->records= records;
+ quick_intersect->read_time= read_cost;
+ for (TRP_RANGE **range_scan= range_scans; range_scan != range_scans_end;
+ range_scan++)
+ {
+ if (!(quick= (QUICK_RANGE_SELECT*)
+ ((*range_scan)->make_quick(param, FALSE, &quick_intersect->alloc)))||
+ quick_intersect->push_quick_back(quick))
+ {
+ delete quick;
+ delete quick_intersect;
+ return NULL;
+ }
+ }
+ return quick_intersect;
+}
+
+
QUICK_SELECT_I *TRP_ROR_INTERSECT::make_quick(PARAM *param,
bool retrieve_full_rows,
MEM_ROOT *parent_alloc)
@@ -9008,6 +9839,18 @@ bool QUICK_INDEX_MERGE_SELECT::is_keys_used(const MY_BITMAP *fields)
return 0;
}
+bool QUICK_INDEX_INTERSECT_SELECT::is_keys_used(const MY_BITMAP *fields)
+{
+ QUICK_RANGE_SELECT *quick;
+ List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
+ while ((quick= it++))
+ {
+ if (is_key_used(head, quick->index, fields))
+ return 1;
+ }
+ return 0;
+}
+
bool QUICK_ROR_INTERSECT_SELECT::is_keys_used(const MY_BITMAP *fields)
{
QUICK_SELECT_WITH_RECORD *qr;
@@ -9153,13 +9996,20 @@ err:
other error
*/
-int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
+int read_keys_and_merge_scans(THD *thd,
+ TABLE *head,
+ List<QUICK_RANGE_SELECT> quick_selects,
+ QUICK_RANGE_SELECT *pk_quick_select,
+ READ_RECORD *read_record,
+ bool intersection,
+ Unique **unique_ptr)
{
List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects);
QUICK_RANGE_SELECT* cur_quick;
int result;
+ Unique *unique= *unique_ptr;
handler *file= head->file;
- DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::read_keys_and_merge");
+ DBUG_ENTER("read_keys_and_merge");
/* We're going to just read rowids. */
if (!head->key_read)
@@ -9170,6 +10020,7 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
cur_quick_it.rewind();
cur_quick= cur_quick_it++;
+ bool first_quick= TRUE;
DBUG_ASSERT(cur_quick != 0);
/*
@@ -9187,9 +10038,11 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
unique= new Unique(refpos_order_cmp, (void *)file,
file->ref_length,
- thd->variables.sortbuff_size);
+ thd->variables.sortbuff_size,
+ intersection ? quick_selects.elements : 0);
if (!unique)
goto err;
+ *unique_ptr= unique;
}
else
unique->reset();
@@ -9201,6 +10054,12 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
{
while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
{
+ if (first_quick)
+ {
+ first_quick= FALSE;
+ if (intersection && unique->is_in_memory())
+ unique->close_for_expansion();
+ }
cur_quick->range_end();
cur_quick= cur_quick_it++;
if (!cur_quick)
@@ -9225,10 +10084,18 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
if (thd->killed)
goto err;
- /* skip row if it will be retrieved by clustered PK scan */
- if (pk_quick_select && pk_quick_select->row_in_ranges())
- continue;
-
+ if (intersection)
+ {
+ if (first_quick &&
+ pk_quick_select && !pk_quick_select->row_in_ranges())
+ continue;
+ }
+ else
+ {
+ /* skip row if it will be retrieved by clustered PK scan */
+ if (pk_quick_select && pk_quick_select->row_in_ranges())
+ continue;
+ }
cur_quick->file->position(cur_quick->record);
if (unique->unique_add((char*)cur_quick->file->ref))
goto err;
@@ -9240,12 +10107,11 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
sequence.
*/
result= unique->get(head);
- doing_pk_scan= FALSE;
/*
index_merge currently doesn't support "using index" at all
*/
head->disable_keyread();
- init_read_record(&read_record, thd, head, (SQL_SELECT*) 0, 1 , 1, TRUE);
+ init_read_record(read_record, thd, head, (SQL_SELECT*) 0, 1 , 1, TRUE);
DBUG_RETURN(result);
err:
@@ -9254,6 +10120,17 @@ err:
}
+int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
+
+{
+ int result;
+ DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::read_keys_and_merge");
+ result= read_keys_and_merge_scans(thd, head, quick_selects, pk_quick_select,
+ &read_record, FALSE, &unique);
+ doing_pk_scan= FALSE;
+ DBUG_RETURN(result);
+}
+
/*
Get next row for index_merge.
NOTES
@@ -9290,6 +10167,33 @@ int QUICK_INDEX_MERGE_SELECT::get_next()
DBUG_RETURN(result);
}
+int QUICK_INDEX_INTERSECT_SELECT::read_keys_and_merge()
+
+{
+ int result;
+ DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::read_keys_and_merge");
+ result= read_keys_and_merge_scans(thd, head, quick_selects, pk_quick_select,
+ &read_record, TRUE, &unique);
+ doing_pk_scan= FALSE;
+ DBUG_RETURN(result);
+}
+
+int QUICK_INDEX_INTERSECT_SELECT::get_next()
+{
+ int result;
+ DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::get_next");
+
+ if ((result= read_record.read_record(&read_record)) == -1)
+ {
+ result= HA_ERR_END_OF_FILE;
+ end_read_record(&read_record);
+ free_io_cache(head);
+ /* All rows from Unique have been retrieved, do a clustered PK scan */
+ }
+
+ DBUG_RETURN(result);
+}
+
/*
Retrieve next record.
@@ -9999,30 +10903,53 @@ bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range_arg)
}
-void QUICK_RANGE_SELECT::add_info_string(String *str)
+void QUICK_SELECT_I::add_key_name(String *str, bool *first)
{
KEY *key_info= head->key_info + index;
+
+ if (*first)
+ *first= FALSE;
+ else
+ str->append(',');
str->append(key_info->name);
}
+
+
+void QUICK_RANGE_SELECT::add_info_string(String *str)
+{
+ bool first= TRUE;
+
+ add_key_name(str, &first);
+}
void QUICK_INDEX_MERGE_SELECT::add_info_string(String *str)
{
QUICK_RANGE_SELECT *quick;
bool first= TRUE;
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
+
str->append(STRING_WITH_LEN("sort_union("));
while ((quick= it++))
{
- if (!first)
- str->append(',');
- else
- first= FALSE;
- quick->add_info_string(str);
+ quick->add_key_name(str, &first);
}
if (pk_quick_select)
+ pk_quick_select->add_key_name(str, &first);
+ str->append(')');
+}
+
+void QUICK_INDEX_INTERSECT_SELECT::add_info_string(String *str)
+{
+ QUICK_RANGE_SELECT *quick;
+ bool first= TRUE;
+ List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
+
+ str->append(STRING_WITH_LEN("sort_intersect("));
+ if (pk_quick_select)
+ pk_quick_select->add_key_name(str, &first);
+ while ((quick= it++))
{
- str->append(',');
- pk_quick_select->add_info_string(str);
+ quick->add_key_name(str, &first);
}
str->append(')');
}
@@ -10032,129 +10959,125 @@ void QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
bool first= TRUE;
QUICK_SELECT_WITH_RECORD *qr;
List_iterator_fast<QUICK_SELECT_WITH_RECORD> it(quick_selects);
+
str->append(STRING_WITH_LEN("intersect("));
while ((qr= it++))
{
- KEY *key_info= head->key_info + qr->quick->index;
- if (!first)
- str->append(',');
- else
- first= FALSE;
- str->append(key_info->name);
+ qr->quick->add_key_name(str, &first);
}
if (cpk_quick)
- {
- KEY *key_info= head->key_info + cpk_quick->index;
- str->append(',');
- str->append(key_info->name);
- }
+ cpk_quick->add_key_name(str, &first);
str->append(')');
}
+
void QUICK_ROR_UNION_SELECT::add_info_string(String *str)
{
- bool first= TRUE;
QUICK_SELECT_I *quick;
+ bool first= TRUE;
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
+
str->append(STRING_WITH_LEN("union("));
while ((quick= it++))
{
- if (!first)
- str->append(',');
- else
+ if (first)
first= FALSE;
+ else
+ str->append(',');
quick->add_info_string(str);
}
str->append(')');
}
-void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names,
- String *used_lengths)
+void QUICK_SELECT_I::add_key_and_length(String *key_names,
+ String *used_lengths,
+ bool *first)
{
char buf[64];
uint length;
KEY *key_info= head->key_info + index;
+
+ if (*first)
+ *first= FALSE;
+ else
+ {
+ key_names->append(',');
+ used_lengths->append(',');
+ }
key_names->append(key_info->name);
length= longlong2str(max_used_key_length, buf, 10) - buf;
used_lengths->append(buf, length);
}
+
+void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names,
+ String *used_lengths)
+{
+ bool first= TRUE;
+
+ add_key_and_length(key_names, used_lengths, &first);
+}
+
void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
String *used_lengths)
{
- char buf[64];
- uint length;
- bool first= TRUE;
QUICK_RANGE_SELECT *quick;
+ bool first= TRUE;
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
+
while ((quick= it++))
{
- if (first)
- first= FALSE;
- else
- {
- key_names->append(',');
- used_lengths->append(',');
- }
-
- KEY *key_info= head->key_info + quick->index;
- key_names->append(key_info->name);
- length= longlong2str(quick->max_used_key_length, buf, 10) - buf;
- used_lengths->append(buf, length);
+ quick->add_key_and_length(key_names, used_lengths, &first);
}
+
if (pk_quick_select)
+ pk_quick_select->add_key_and_length(key_names, used_lengths, &first);
+}
+
+
+void QUICK_INDEX_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
+ String *used_lengths)
+{
+ QUICK_RANGE_SELECT *quick;
+ bool first= TRUE;
+
+ List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
+
+ if (pk_quick_select)
+ pk_quick_select->add_key_and_length(key_names, used_lengths, &first);
+
+ while ((quick= it++))
{
- KEY *key_info= head->key_info + pk_quick_select->index;
- key_names->append(',');
- key_names->append(key_info->name);
- length= longlong2str(pk_quick_select->max_used_key_length, buf, 10) - buf;
- used_lengths->append(',');
- used_lengths->append(buf, length);
+ quick->add_key_and_length(key_names, used_lengths, &first);
}
}
void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
String *used_lengths)
{
- char buf[64];
- uint length;
- bool first= TRUE;
QUICK_SELECT_WITH_RECORD *qr;
+ bool first= TRUE;
+
List_iterator_fast<QUICK_SELECT_WITH_RECORD> it(quick_selects);
+
while ((qr= it++))
{
- KEY *key_info= head->key_info + qr->quick->index;
- if (first)
- first= FALSE;
- else
- {
- key_names->append(',');
- used_lengths->append(',');
- }
- key_names->append(key_info->name);
- length= longlong2str(qr->quick->max_used_key_length, buf, 10) - buf;
- used_lengths->append(buf, length);
+ qr->quick->add_key_and_length(key_names, used_lengths, &first);
}
-
if (cpk_quick)
- {
- KEY *key_info= head->key_info + cpk_quick->index;
- key_names->append(',');
- key_names->append(key_info->name);
- length= longlong2str(cpk_quick->max_used_key_length, buf, 10) - buf;
- used_lengths->append(',');
- used_lengths->append(buf, length);
- }
+ cpk_quick->add_key_and_length(key_names, used_lengths, &first);
}
void QUICK_ROR_UNION_SELECT::add_keys_and_lengths(String *key_names,
String *used_lengths)
{
- bool first= TRUE;
QUICK_SELECT_I *quick;
+ bool first= TRUE;
+
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
+
while ((quick= it++))
{
if (first)
@@ -12300,11 +13223,9 @@ void QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
void QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names,
String *used_lengths)
{
- char buf[64];
- uint length;
- key_names->append(index_info->name);
- length= longlong2str(max_used_key_length, buf, 10) - buf;
- used_lengths->append(buf, length);
+ bool first= TRUE;
+
+ add_key_and_length(key_names, used_lengths, &first);
}
@@ -12486,6 +13407,22 @@ void QUICK_INDEX_MERGE_SELECT::dbug_dump(int indent, bool verbose)
fprintf(DBUG_FILE, "%*s}\n", indent, "");
}
+void QUICK_INDEX_INTERSECT_SELECT::dbug_dump(int indent, bool verbose)
+{
+ List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
+ QUICK_RANGE_SELECT *quick;
+ fprintf(DBUG_FILE, "%*squick index_intersect select\n", indent, "");
+ fprintf(DBUG_FILE, "%*smerged scans {\n", indent, "");
+ while ((quick= it++))
+ quick->dbug_dump(indent+2, verbose);
+ if (pk_quick_select)
+ {
+ fprintf(DBUG_FILE, "%*sclustered PK quick:\n", indent, "");
+ pk_quick_select->dbug_dump(indent+2, verbose);
+ }
+ fprintf(DBUG_FILE, "%*s}\n", indent, "");
+}
+
void QUICK_ROR_INTERSECT_SELECT::dbug_dump(int indent, bool verbose)
{
List_iterator_fast<QUICK_SELECT_WITH_RECORD> it(quick_selects);
diff --git a/sql/opt_range.h b/sql/opt_range.h
index 1e3008d78aa..d894cfaf91d 100644
--- a/sql/opt_range.h
+++ b/sql/opt_range.h
@@ -274,12 +274,13 @@ public:
enum {
QS_TYPE_RANGE = 0,
- QS_TYPE_INDEX_MERGE = 1,
- QS_TYPE_RANGE_DESC = 2,
- QS_TYPE_FULLTEXT = 3,
- QS_TYPE_ROR_INTERSECT = 4,
- QS_TYPE_ROR_UNION = 5,
- QS_TYPE_GROUP_MIN_MAX = 6
+ QS_TYPE_INDEX_INTERSECT = 1,
+ QS_TYPE_INDEX_MERGE = 2,
+ QS_TYPE_RANGE_DESC = 3,
+ QS_TYPE_FULLTEXT = 4,
+ QS_TYPE_ROR_INTERSECT = 5,
+ QS_TYPE_ROR_UNION = 6,
+ QS_TYPE_GROUP_MIN_MAX = 7
};
/* Get type of this quick select - one of the QS_TYPE_* values */
@@ -305,6 +306,10 @@ public:
Save ROWID of last retrieved row in file->ref. This used in ROR-merging.
*/
virtual void save_last_pos(){};
+
+ void add_key_and_length(String *key_names,
+ String *used_lengths,
+ bool *first);
/*
Append comma-separated list of keys this quick select uses to key_names;
@@ -314,13 +319,15 @@ public:
virtual void add_keys_and_lengths(String *key_names,
String *used_lengths)=0;
+ void add_key_name(String *str, bool *first);
+
/*
Append text representation of quick select structure (what and how is
merged) to str. The result is added to "Extra" field in EXPLAIN output.
This function is implemented only by quick selects that merge other quick
selects output and/or can produce output suitable for merging.
*/
- virtual void add_info_string(String *str) {};
+ virtual void add_info_string(String *str) {}
/*
Return 1 if any index used by this quick select
uses field which is marked in passed bitmap.
@@ -393,8 +400,17 @@ protected:
friend QUICK_RANGE_SELECT *get_quick_select(PARAM*,uint idx,
SEL_ARG *key_tree,
MEM_ROOT *alloc);
+ friend
+ int read_keys_and_merge_scans(THD *thd, TABLE *head,
+ List<QUICK_RANGE_SELECT> quick_selects,
+ QUICK_RANGE_SELECT *pk_quick_select,
+ READ_RECORD *read_record,
+ bool intersection,
+ Unique **unique_ptr);
+
friend class QUICK_SELECT_DESC;
friend class QUICK_INDEX_MERGE_SELECT;
+ friend class QUICK_INDEX_INTERSECT_SELECT;
friend class QUICK_ROR_INTERSECT_SELECT;
friend class QUICK_GROUP_MIN_MAX_SELECT;
@@ -545,6 +561,45 @@ public:
READ_RECORD read_record;
};
+class QUICK_INDEX_INTERSECT_SELECT : public QUICK_SELECT_I
+{
+ Unique *unique;
+public:
+ QUICK_INDEX_INTERSECT_SELECT(THD *thd, TABLE *table);
+ ~QUICK_INDEX_INTERSECT_SELECT();
+
+ int init();
+ int reset(void);
+ int get_next();
+ bool reverse_sorted() { return false; }
+ bool unique_key_range() { return false; }
+ int get_type() { return QS_TYPE_INDEX_INTERSECT; }
+ void add_keys_and_lengths(String *key_names, String *used_lengths);
+ void add_info_string(String *str);
+ bool is_keys_used(const MY_BITMAP *fields);
+#ifndef DBUG_OFF
+ void dbug_dump(int indent, bool verbose);
+#endif
+
+ bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
+
+ /* range quick selects this index_merge read consists of */
+ List<QUICK_RANGE_SELECT> quick_selects;
+
+ /* quick select that uses clustered primary key (NULL if none) */
+ QUICK_RANGE_SELECT* pk_quick_select;
+
+ /* true if this select is currently doing a clustered PK scan */
+ bool doing_pk_scan;
+
+ MEM_ROOT alloc;
+ THD *thd;
+ int read_keys_and_merge();
+
+ /* used to get rows collected in Unique */
+ READ_RECORD read_record;
+};
+
/*
Rowid-Ordered Retrieval (ROR) index intersection quick select.
diff --git a/sql/sql_class.h b/sql/sql_class.h
index db0842e7547..6d51e972c85 100644
--- a/sql/sql_class.h
+++ b/sql/sql_class.h
@@ -2977,6 +2977,7 @@ class user_var_entry
DTCollation collation;
};
+
/*
Unique -- class for unique (removing of duplicates).
Puts all values to the TREE. If the tree becomes too big,
@@ -2993,27 +2994,42 @@ class Unique :public Sql_alloc
IO_CACHE file;
TREE tree;
uchar *record_pointers;
+ ulong filtered_out_elems;
bool flush();
uint size;
+ uint full_size;
+ uint min_dupl_count;
public:
ulong elements;
Unique(qsort_cmp2 comp_func, void *comp_func_fixed_arg,
- uint size_arg, ulonglong max_in_memory_size_arg);
+ uint size_arg, ulonglong max_in_memory_size_arg,
+ uint min_dupl_count_arg= 0);
~Unique();
ulong elements_in_tree() { return tree.elements_in_tree; }
inline bool unique_add(void *ptr)
{
DBUG_ENTER("unique_add");
DBUG_PRINT("info", ("tree %u - %lu", tree.elements_in_tree, max_elements));
- if (tree.elements_in_tree > max_elements && flush())
+ if (!(tree.flag & TREE_ONLY_DUPS) &&
+ tree.elements_in_tree >= max_elements && flush())
DBUG_RETURN(1);
DBUG_RETURN(!tree_insert(&tree, ptr, 0, tree.custom_arg));
}
+ bool is_in_memory() { return (my_b_tell(&file) == 0); }
+ void close_for_expansion() { tree.flag= TREE_ONLY_DUPS; }
+
bool get(TABLE *table);
+
+ inline static double get_search_cost(uint tree_elems, uint compare_factor)
+ {
+ return log((double) tree_elems) / (compare_factor * M_LN2);
+ }
+
static double get_use_cost(uint *buffer, uint nkeys, uint key_size,
- ulonglong max_in_memory_size);
+ ulonglong max_in_memory_size, uint compare_factor,
+ bool intersect_fl, bool *in_memory);
inline static int get_cost_calc_buff_size(ulong nkeys, uint key_size,
ulonglong max_in_memory_size)
{
@@ -3030,6 +3046,11 @@ public:
friend int unique_write_to_file(uchar* key, element_count count, Unique *unique);
friend int unique_write_to_ptrs(uchar* key, element_count count, Unique *unique);
+
+ friend int unique_write_to_file_with_count(uchar* key, element_count count,
+ Unique *unique);
+ friend int unique_intersect_write_to_ptrs(uchar* key, element_count count,
+ Unique *unique);
};
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 60bfa0dfcd6..288369eedba 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -2688,6 +2688,7 @@ make_join_statistics(JOIN *join, TABLE_LIST *tables_arg, COND *conds,
goto error;
}
table->quick_keys.clear_all();
+ table->intersect_keys.clear_all();
table->reginfo.join_tab=s;
table->reginfo.not_exists_optimize=0;
bzero((char*) table->const_key_parts, sizeof(key_part_map)*table->s->keys);
@@ -6373,8 +6374,10 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
used_tables|=current_map;
if (tab->type == JT_REF && tab->quick &&
- (uint) tab->ref.key == tab->quick->index &&
- tab->ref.key_length < tab->quick->max_used_key_length)
+ (((uint) tab->ref.key == tab->quick->index &&
+ tab->ref.key_length < tab->quick->max_used_key_length) ||
+ (!tab->table->intersect_keys.is_clear_all() &&
+ tab->table->intersect_keys.is_set(tab->ref.key))))
{
/* Range uses longer key; Use this instead of ref on key */
tab->type=JT_ALL;
@@ -10186,6 +10189,7 @@ create_tmp_table(THD *thd,TMP_TABLE_PARAM *param,List<Item> &fields,
table->quick_keys.init();
table->covering_keys.init();
table->merge_keys.init();
+ table->intersect_keys.init();
table->keys_in_use_for_query.init();
table->s= share;
@@ -13678,7 +13682,8 @@ test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit,
by clustered PK values.
*/
- if (quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE ||
+ if (quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE ||
+ quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_INTERSECT ||
quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION ||
quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT)
DBUG_RETURN(0);
@@ -14084,6 +14089,7 @@ check_reverse_order:
QUICK_SELECT_DESC *tmp;
int quick_type= select->quick->get_type();
if (quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE ||
+ quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_INTERSECT ||
quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT ||
quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION ||
quick_type == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX)
@@ -14256,6 +14262,7 @@ create_sort_index(THD *thd, JOIN *join, ORDER *order,
select->cleanup(); // filesort did select
tab->select= 0;
table->quick_keys.clear_all(); // as far as we cleanup select->quick
+ table->intersect_keys.clear_all();
table->sort.io_cache= tablesort_result_cache;
}
tab->select_cond=0;
@@ -16880,6 +16887,7 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
quick_type= tab->select->quick->get_type();
if ((quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE) ||
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) ||
+ (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) ||
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION))
tab->type = JT_INDEX_MERGE;
else
@@ -17092,6 +17100,7 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
{
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION ||
quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT ||
+ quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_INTERSECT ||
quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE)
{
extra.append(STRING_WITH_LEN("; Using "));
diff --git a/sql/sql_sort.h b/sql/sql_sort.h
index f54b085eeda..fc4117e2767 100644
--- a/sql/sql_sort.h
+++ b/sql/sql_sort.h
@@ -57,6 +57,7 @@ typedef struct st_sort_param {
uint addon_length; /* Length of added packed fields */
uint res_length; /* Length of records in final sorted file/buffer */
uint keys; /* Max keys / buffer */
+ element_count min_dupl_count;
ha_rows max_rows,examined_rows;
TABLE *sort_form; /* For quicker make_sortkey */
SORT_FIELD *local_sortorder;
@@ -80,4 +81,9 @@ int merge_buffers(SORTPARAM *param,IO_CACHE *from_file,
IO_CACHE *to_file, uchar *sort_buffer,
BUFFPEK *lastbuff,BUFFPEK *Fb,
BUFFPEK *Tb,int flag);
+int merge_index(SORTPARAM *param, uchar *sort_buffer,
+ BUFFPEK *buffpek, uint maxbuffer,
+ IO_CACHE *tempfile, IO_CACHE *outfile);
+
void reuse_freed_buff(QUEUE *queue, BUFFPEK *reuse, uint key_length);
+
diff --git a/sql/table.h b/sql/table.h
index 828d01f3783..25e90e33b5e 100644
--- a/sql/table.h
+++ b/sql/table.h
@@ -683,7 +683,7 @@ struct st_table {
needed by the query without reading the row.
*/
key_map covering_keys;
- key_map quick_keys, merge_keys;
+ key_map quick_keys, merge_keys,intersect_keys;
/*
A set of keys that can be used in the query that references this
table.
diff --git a/sql/uniques.cc b/sql/uniques.cc
index 3d1ea9243b9..141504df610 100644
--- a/sql/uniques.cc
+++ b/sql/uniques.cc
@@ -33,7 +33,6 @@
#include "mysql_priv.h"
#include "sql_sort.h"
-
int unique_write_to_file(uchar* key, element_count count, Unique *unique)
{
/*
@@ -45,6 +44,12 @@ int unique_write_to_file(uchar* key, element_count count, Unique *unique)
return my_b_write(&unique->file, key, unique->size) ? 1 : 0;
}
+int unique_write_to_file_with_count(uchar* key, element_count count, Unique *unique)
+{
+ return my_b_write(&unique->file, key, unique->size) ||
+ my_b_write(&unique->file, &count, sizeof(element_count)) ? 1 : 0;
+}
+
int unique_write_to_ptrs(uchar* key, element_count count, Unique *unique)
{
memcpy(unique->record_pointers, key, unique->size);
@@ -52,10 +57,28 @@ int unique_write_to_ptrs(uchar* key, element_count count, Unique *unique)
return 0;
}
+int unique_intersect_write_to_ptrs(uchar* key, element_count count, Unique *unique)
+{
+ if (count >= unique->min_dupl_count)
+ {
+ memcpy(unique->record_pointers, key, unique->size);
+ unique->record_pointers+=unique->size;
+ }
+ else
+ unique->filtered_out_elems++;
+ return 0;
+}
+
+
Unique::Unique(qsort_cmp2 comp_func, void * comp_func_fixed_arg,
- uint size_arg, ulonglong max_in_memory_size_arg)
+ uint size_arg, ulonglong max_in_memory_size_arg,
+ uint min_dupl_count_arg)
:max_in_memory_size(max_in_memory_size_arg), size(size_arg), elements(0)
{
+ min_dupl_count= min_dupl_count_arg;
+ full_size= size;
+ if (min_dupl_count_arg)
+ full_size+= sizeof(element_count);
my_b_clear(&file);
init_tree(&tree, (ulong) (max_in_memory_size / 16), 0, size, comp_func, 0,
NULL, comp_func_fixed_arg);
@@ -123,7 +146,8 @@ inline double log2_n_fact(double x)
*/
static double get_merge_buffers_cost(uint *buff_elems, uint elem_size,
- uint *first, uint *last)
+ uint *first, uint *last,
+ uint compare_factor)
{
uint total_buf_elems= 0;
for (uint *pbuf= first; pbuf <= last; pbuf++)
@@ -134,7 +158,7 @@ static double get_merge_buffers_cost(uint *buff_elems, uint elem_size,
/* Using log2(n)=log(n)/log(2) formula */
return 2*((double)total_buf_elems*elem_size) / IO_SIZE +
- total_buf_elems*log((double) n_buffers) / (TIME_FOR_COMPARE_ROWID * M_LN2);
+ total_buf_elems*log((double) n_buffers) / (compare_factor * M_LN2);
}
@@ -167,7 +191,8 @@ static double get_merge_buffers_cost(uint *buff_elems, uint elem_size,
static double get_merge_many_buffs_cost(uint *buffer,
uint maxbuffer, uint max_n_elems,
- uint last_n_elems, int elem_size)
+ uint last_n_elems, int elem_size,
+ uint compare_factor)
{
register int i;
double total_cost= 0.0;
@@ -194,19 +219,22 @@ static double get_merge_many_buffs_cost(uint *buffer,
{
total_cost+=get_merge_buffers_cost(buff_elems, elem_size,
buff_elems + i,
- buff_elems + i + MERGEBUFF-1);
+ buff_elems + i + MERGEBUFF-1,
+ compare_factor);
lastbuff++;
}
total_cost+=get_merge_buffers_cost(buff_elems, elem_size,
buff_elems + i,
- buff_elems + maxbuffer);
+ buff_elems + maxbuffer,
+ compare_factor);
maxbuffer= lastbuff;
}
}
/* Simulate final merge_buff call. */
total_cost += get_merge_buffers_cost(buff_elems, elem_size,
- buff_elems, buff_elems + maxbuffer);
+ buff_elems, buff_elems + maxbuffer,
+ compare_factor);
return total_cost;
}
@@ -221,7 +249,11 @@ static double get_merge_many_buffs_cost(uint *buffer,
to get # bytes needed.
nkeys #of elements in Unique
key_size size of each elements in bytes
- max_in_memory_size amount of memory Unique will be allowed to use
+ max_in_memory_size amount of memory Unique will be allowed to use
+ compare_factor used to calculate cost of one comparison
+ write_fl if the result must be saved written to disk
+ in_memory_elems OUT estimate of the number of elements in memory
+ if disk is not used
RETURN
Cost in disk seeks.
@@ -259,7 +291,9 @@ static double get_merge_many_buffs_cost(uint *buffer,
*/
double Unique::get_use_cost(uint *buffer, uint nkeys, uint key_size,
- ulonglong max_in_memory_size)
+ ulonglong max_in_memory_size,
+ uint compare_factor,
+ bool intersect_fl, bool *in_memory)
{
ulong max_elements_in_tree;
ulong last_tree_elems;
@@ -276,12 +310,15 @@ double Unique::get_use_cost(uint *buffer, uint nkeys, uint key_size,
result= 2*log2_n_fact(last_tree_elems + 1.0);
if (n_full_trees)
result+= n_full_trees * log2_n_fact(max_elements_in_tree + 1.0);
- result /= TIME_FOR_COMPARE_ROWID;
+ result /= compare_factor;
DBUG_PRINT("info",("unique trees sizes: %u=%u*%lu + %lu", nkeys,
n_full_trees, n_full_trees?max_elements_in_tree:0,
last_tree_elems));
+ if (in_memory)
+ *in_memory= !n_full_trees;
+
if (!n_full_trees)
return result;
@@ -295,12 +332,12 @@ double Unique::get_use_cost(uint *buffer, uint nkeys, uint key_size,
result += DISK_SEEK_BASE_COST * ceil(((double) key_size)*last_tree_elems / IO_SIZE);
/* Cost of merge */
+ if (intersect_fl)
+ key_size+= sizeof(element_count);
double merge_cost= get_merge_many_buffs_cost(buffer, n_full_trees,
max_elements_in_tree,
- last_tree_elems, key_size);
- if (merge_cost < 0.0)
- return merge_cost;
-
+ last_tree_elems, key_size,
+ compare_factor);
result += merge_cost;
/*
Add cost of reading the resulting sequence, assuming there were no
@@ -327,7 +364,10 @@ bool Unique::flush()
file_ptr.count=tree.elements_in_tree;
file_ptr.file_pos=my_b_tell(&file);
- if (tree_walk(&tree, (tree_walk_action) unique_write_to_file,
+ tree_walk_action action= min_dupl_count ?
+ (tree_walk_action) unique_write_to_file_with_count :
+ (tree_walk_action) unique_write_to_file;
+ if (tree_walk(&tree, action,
(void*) this, left_root_right) ||
insert_dynamic(&file_ptrs, (uchar*) &file_ptr))
return 1;
@@ -357,6 +397,7 @@ Unique::reset()
reinit_io_cache(&file, WRITE_CACHE, 0L, 0, 1);
}
elements= 0;
+ tree.flag= 0;
}
/*
@@ -576,15 +617,19 @@ bool Unique::get(TABLE *table)
{
SORTPARAM sort_param;
table->sort.found_records=elements+tree.elements_in_tree;
-
if (my_b_tell(&file) == 0)
{
/* Whole tree is in memory; Don't use disk if you don't need to */
if ((record_pointers=table->sort.record_pointers= (uchar*)
my_malloc(size * tree.elements_in_tree, MYF(0))))
{
- (void) tree_walk(&tree, (tree_walk_action) unique_write_to_ptrs,
+ tree_walk_action action= min_dupl_count ?
+ (tree_walk_action) unique_intersect_write_to_ptrs :
+ (tree_walk_action) unique_write_to_ptrs;
+ filtered_out_elems= 0;
+ (void) tree_walk(&tree, action,
this, left_root_right);
+ table->sort.found_records-= filtered_out_elems;
return 0;
}
}
@@ -614,7 +659,9 @@ bool Unique::get(TABLE *table)
sort_param.max_rows= elements;
sort_param.sort_form=table;
sort_param.rec_length= sort_param.sort_length= sort_param.ref_length=
- size;
+ full_size;
+ sort_param.min_dupl_count= min_dupl_count;
+ sort_param.res_length= 0;
sort_param.keys= (uint) (max_in_memory_size / sort_param.sort_length);
sort_param.not_killable=1;
@@ -635,8 +682,9 @@ bool Unique::get(TABLE *table)
if (flush_io_cache(&file) ||
reinit_io_cache(&file,READ_CACHE,0L,0,0))
goto err;
- if (merge_buffers(&sort_param, &file, outfile, sort_buffer, file_ptr,
- file_ptr, file_ptr+maxbuffer,0))
+ sort_param.res_length= sort_param.rec_length-
+ (min_dupl_count ? sizeof(min_dupl_count) : 0);
+ if (merge_index(&sort_param, sort_buffer, file_ptr, maxbuffer, &file, outfile))
goto err;
error=0;
err:
@@ -651,3 +699,5 @@ err:
outfile->end_of_file=save_pos;
return error;
}
+
+
diff --git a/sql/unireg.h b/sql/unireg.h
index 88a5ca5c12f..b3bf44173e7 100644
--- a/sql/unireg.h
+++ b/sql/unireg.h
@@ -89,7 +89,7 @@
#define MAX_SELECT_NESTING (sizeof(nesting_map)*8-1)
#define MAX_SORT_MEMORY (2048*1024-MALLOC_OVERHEAD)
-#define MIN_SORT_MEMORY (32*1024-MALLOC_OVERHEAD)
+#define MIN_SORT_MEMORY (1024-MALLOC_OVERHEAD)
/* Memory allocated when parsing a statement / saving a statement */
#define MEM_ROOT_BLOCK_SIZE 8192
View Lorry Controller Status