maria-developers team mailing list archive
-
maria-developers team
-
Mailing list archive
-
Message #03411
bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (igor:2750)
#At lp:maria based on revid:igor@xxxxxxxxxxxx-20091103182103-jnjuss2b4t72rz83
2750 Igor Babaev 2010-06-28
An implementation of index intersect via a modified Unique class.
This code is planned to be used for mwl#21.
modified:
include/my_tree.h
mysys/tree.c
sql/filesort.cc
sql/opt_range.cc
sql/opt_range.h
sql/sql_class.h
sql/sql_select.cc
sql/sql_sort.h
sql/uniques.cc
=== modified file 'include/my_tree.h'
--- a/include/my_tree.h 2008-05-29 15:33:33 +0000
+++ b/include/my_tree.h 2010-06-29 00:02:19 +0000
@@ -31,6 +31,7 @@ extern "C" {
#define tree_set_pointer(element,ptr) *((uchar **) (element+1))=((uchar*) (ptr))
#define TREE_NO_DUPS 1
+#define TREE_ONLY_DUPS 2
typedef enum { left_root_right, right_root_left } TREE_WALK;
typedef uint32 element_count;
=== modified file 'mysys/tree.c'
--- a/mysys/tree.c 2007-05-10 09:59:39 +0000
+++ b/mysys/tree.c 2010-06-29 00:02:19 +0000
@@ -221,6 +221,8 @@ TREE_ELEMENT *tree_insert(TREE *tree, vo
}
if (element == &tree->null_element)
{
+ if (tree->flag & TREE_ONLY_DUPS)
+ return((TREE_ELEMENT *) 1);
uint alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
tree->allocated+=alloc_size;
=== modified file 'sql/filesort.cc'
--- a/sql/filesort.cc 2009-09-03 14:05:38 +0000
+++ b/sql/filesort.cc 2010-06-29 00:02:19 +0000
@@ -50,10 +50,6 @@ static int write_keys(SORTPARAM *param,u
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);
@@ -143,6 +139,7 @@ ha_rows filesort(THD *thd, TABLE *table,
bzero((char*) ¶m,sizeof(param));
param.sort_length= sortlength(thd, sortorder, s_length, &multi_byte_charset);
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) &&
@@ -1212,7 +1209,13 @@ int merge_buffers(SORTPARAM *param, IO_C
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;
@@ -1258,16 +1261,20 @@ int merge_buffers(SORTPARAM *param, IO_C
*/
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
}
@@ -1283,27 +1290,42 @@ int merge_buffers(SORTPARAM *param, IO_C
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 */
@@ -1339,9 +1361,33 @@ int merge_buffers(SORTPARAM *param, IO_C
{
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
@@ -1363,12 +1409,17 @@ int merge_buffers(SORTPARAM *param, IO_C
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;
}
@@ -1389,7 +1440,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)
{
=== modified file 'sql/opt_range.cc'
--- a/sql/opt_range.cc 2009-10-30 00:36:35 +0000
+++ b/sql/opt_range.cc 2010-06-29 00:02:19 +0000
@@ -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(P
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);
@@ -1743,7 +1751,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
@@ -1778,6 +1786,63 @@ QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_M
DBUG_VOID_RETURN;
}
+QUICK_INDEX_INTERSECT_SELECT::QUICK_INDEX_INTERSECT_SELECT(THD *thd_param,
+ TABLE *table)
+ :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");
+ 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,
@@ -2555,6 +2620,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 merged 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.
@@ -2621,6 +2704,30 @@ 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;
+
+ /* 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) */
+
+ /*
+ 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
@@ -2899,6 +3006,7 @@ int SQL_SELECT::test_quick_select(THD *t
*/
TRP_RANGE *range_trp;
TRP_ROR_INTERSECT *rori_trp;
+ TRP_INDEX_INTERSECT *intersect_trp;
bool can_build_covering= FALSE;
remove_nonrange_trees(¶m, tree);
@@ -2938,6 +3046,18 @@ int SQL_SELECT::test_quick_select(THD *t
best_trp= rori_trp;
}
}
+#if 1
+#else
+ if (optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE))
+ {
+ if ((intersect_trp= get_best_index_intersect(¶m, tree,
+ best_read_time)))
+ {
+ best_trp= intersect_trp;
+ best_read_time= best_trp->read_cost;
+ }
+ }
+#endif
if (optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE))
{
@@ -4601,6 +4721,85 @@ TABLE_READ_PLAN *merge_same_index_scans(
DBUG_RETURN(trp);
}
+static
+TRP_INDEX_INTERSECT *get_best_index_intersect(PARAM *param, SEL_TREE *tree,
+ double read_time)
+{
+ uint i;
+ uint unique_calc_buff_size;
+ TRP_RANGE **cur_range;
+ TRP_RANGE **range_scans;
+ TRP_INDEX_INTERSECT *intersect_trp= NULL;
+ double intersect_cost= 0.0;
+ ha_rows scan_records= 0;
+ double selectivity= 1.0;
+ ha_rows table_records= param->table->file->stats.records;
+ uint n_index_scans= tree->index_scans_end - tree->index_scans;
+
+ DBUG_ENTER("get_best_index_intersect");
+
+ if (!n_index_scans)
+ DBUG_RETURN(NULL);
+
+ if (!(range_scans= (TRP_RANGE**)alloc_root(param->mem_root,
+ sizeof(TRP_RANGE *)*
+ n_index_scans)))
+ DBUG_RETURN(NULL);
+
+ for (i= 0, cur_range= range_scans; i < n_index_scans; i++)
+ {
+ struct st_index_scan_info *index_scan= tree->index_scans[i];
+ if ((*cur_range= new (param->mem_root) TRP_RANGE(index_scan->sel_arg,
+ index_scan->idx)))
+ {
+ TRP_RANGE *trp= *cur_range;
+ trp->records= index_scan->records;
+ trp->is_ror= FALSE;
+ trp->read_cost= get_index_only_read_time(param, index_scan->records,
+ index_scan->keynr);
+ scan_records+= trp->records;
+ selectivity*= (double) trp->records/table_records;
+ intersect_cost+= trp->read_cost;
+ cur_range++;
+ }
+ }
+
+ /* Add Unique operations cost */
+ unique_calc_buff_size=
+ Unique::get_cost_calc_buff_size((ulong)scan_records,
+ param->table->file->ref_length,
+ param->thd->variables.sortbuff_size);
+ if (param->imerge_cost_buff_size < unique_calc_buff_size)
+ {
+ if (!(param->imerge_cost_buff= (uint*)alloc_root(param->mem_root,
+ unique_calc_buff_size)))
+ DBUG_RETURN(NULL);
+ param->imerge_cost_buff_size= unique_calc_buff_size;
+ }
+
+ intersect_cost +=
+ Unique::get_use_cost(param->imerge_cost_buff, scan_records,
+ param->table->file->ref_length,
+ param->thd->variables.sortbuff_size);
+
+ intersect_cost += get_sweep_read_cost(param,
+ (ha_rows) (table_records*selectivity));
+
+ if (intersect_cost < read_time)
+ {
+ if ((intersect_trp= new (param->mem_root)TRP_INDEX_INTERSECT))
+ {
+ intersect_trp->read_cost= intersect_cost;
+ intersect_trp->records= (ha_rows) table_records*selectivity;
+ set_if_bigger(intersect_trp->records, 1);
+ intersect_trp->range_scans= range_scans;
+ intersect_trp->range_scans_end= cur_range;
+ read_time= intersect_cost;
+ }
+ }
+ DBUG_RETURN(intersect_trp);
+}
+
/*
Calculate cost of 'index only' scan for given index and number of records.
@@ -4638,27 +4837,8 @@ static double get_index_only_read_time(c
}
-typedef struct st_ror_scan_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 */
-
- /* Set of intervals over key fields that will be used for row retrieval. */
- SEL_ARG *sel_arg;
-
- /* 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) */
-
- /*
- 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 */
+typedef struct st_ror_scan_info : INDEX_SCAN_INFO
+{
} ROR_SCAN_INFO;
@@ -5518,6 +5698,14 @@ static TRP_RANGE *get_key_scans_params(P
"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++)
@@ -5526,6 +5714,7 @@ static TRP_RANGE *get_key_scans_params(P
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)
@@ -5535,6 +5724,17 @@ static TRP_RANGE *get_key_scans_params(P
(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->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++;
@@ -5629,6 +5829,34 @@ QUICK_SELECT_I *TRP_INDEX_MERGE::make_qu
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)
@@ -8893,6 +9121,18 @@ bool QUICK_INDEX_MERGE_SELECT::is_keys_u
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_RANGE_SELECT *quick;
@@ -9038,14 +9278,19 @@ 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)
{
List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects);
QUICK_RANGE_SELECT* cur_quick;
int result;
Unique *unique;
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. */
file->extra(HA_EXTRA_KEYREAD);
@@ -9053,6 +9298,7 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_
cur_quick_it.rewind();
cur_quick= cur_quick_it++;
+ bool first_quick= TRUE;
DBUG_ASSERT(cur_quick != 0);
/*
@@ -9064,13 +9310,20 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_
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)
DBUG_RETURN(1);
for (;;)
{
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)
@@ -9113,14 +9366,24 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_
*/
result= unique->get(head);
delete unique;
- doing_pk_scan= FALSE;
/* index_merge currently doesn't support "using index" at all */
file->extra(HA_EXTRA_NO_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);
}
+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);
+ doing_pk_scan= FALSE;
+ DBUG_RETURN(result);
+}
+
/*
Get next row for index_merge.
NOTES
@@ -9157,6 +9420,44 @@ 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);
+ 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 (doing_pk_scan)
+ DBUG_RETURN(pk_quick_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 */
+ if (pk_quick_select)
+ {
+ doing_pk_scan= TRUE;
+ if ((result= pk_quick_select->init()) ||
+ (result= pk_quick_select->reset()))
+ DBUG_RETURN(result);
+ DBUG_RETURN(pk_quick_select->get_next());
+ }
+ }
+
+ DBUG_RETURN(result);
+}
+
/*
Retrieve next record.
@@ -9887,6 +10188,28 @@ void QUICK_INDEX_MERGE_SELECT::add_info_
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("));
+ while ((quick= it++))
+ {
+ if (!first)
+ str->append(',');
+ else
+ first= FALSE;
+ quick->add_info_string(str);
+ }
+ if (pk_quick_select)
+ {
+ str->append(',');
+ pk_quick_select->add_info_string(str);
+ }
+ str->append(')');
+}
+
void QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
{
bool first= TRUE;
@@ -9911,6 +10234,7 @@ void QUICK_ROR_INTERSECT_SELECT::add_inf
str->append(')');
}
+
void QUICK_ROR_UNION_SELECT::add_info_string(String *str)
{
bool first= TRUE;
@@ -9940,8 +10264,12 @@ void QUICK_RANGE_SELECT::add_keys_and_le
used_lengths->append(buf, length);
}
-void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
- String *used_lengths)
+static
+void add_keys_and_lengths_of_index_scans(TABLE *head,
+ List<QUICK_RANGE_SELECT> quick_selects,
+ QUICK_RANGE_SELECT *pk_quick_select,
+ String *key_names,
+ String *used_lengths)
{
char buf[64];
uint length;
@@ -9975,6 +10303,20 @@ void QUICK_INDEX_MERGE_SELECT::add_keys_
}
}
+void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
+ String *used_lengths)
+{
+ add_keys_and_lengths_of_index_scans(head, quick_selects, pk_quick_select,
+ key_names, used_lengths);
+}
+
+void QUICK_INDEX_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
+ String *used_lengths)
+{
+ add_keys_and_lengths_of_index_scans(head, quick_selects, pk_quick_select,
+ key_names, used_lengths);
+}
+
void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
String *used_lengths)
{
@@ -12310,6 +12652,22 @@ void QUICK_INDEX_MERGE_SELECT::dbug_dump
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_RANGE_SELECT> it(quick_selects);
=== modified file 'sql/opt_range.h'
--- a/sql/opt_range.h 2009-09-02 08:40:18 +0000
+++ b/sql/opt_range.h 2010-06-29 00:02:19 +0000
@@ -195,12 +195,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 */
@@ -312,8 +313,16 @@ 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);
+
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;
@@ -463,6 +472,44 @@ public:
READ_RECORD read_record;
};
+class QUICK_INDEX_INTERSECT_SELECT : public QUICK_SELECT_I
+{
+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.
=== modified file 'sql/sql_class.h'
--- a/sql/sql_class.h 2009-09-15 10:46:35 +0000
+++ b/sql/sql_class.h 2010-06-29 00:02:19 +0000
@@ -2827,6 +2827,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,
@@ -2845,11 +2846,21 @@ class Unique :public Sql_alloc
uchar *record_pointers;
bool flush();
uint size;
+#if 0
+#else
+ uint full_size;
+ uint min_dupl_count;
+#endif
public:
ulong elements;
Unique(qsort_cmp2 comp_func, void *comp_func_fixed_arg,
+#if 0
uint size_arg, ulonglong max_in_memory_size_arg);
+#else
+ uint size_arg, ulonglong max_in_memory_size_arg,
+ uint min_dupl_count_arg= 0);
+#endif
~Unique();
ulong elements_in_tree() { return tree.elements_in_tree; }
inline bool unique_add(void *ptr)
@@ -2861,6 +2872,9 @@ public:
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);
static double get_use_cost(uint *buffer, uint nkeys, uint key_size,
ulonglong max_in_memory_size);
@@ -2877,6 +2891,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);
};
=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc 2009-10-26 11:38:17 +0000
+++ b/sql/sql_select.cc 2010-06-29 00:02:19 +0000
@@ -13333,7 +13333,8 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
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);
@@ -13682,6 +13683,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)
@@ -16405,6 +16407,7 @@ static void select_describe(JOIN *join,
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
@@ -16609,6 +16612,7 @@ static void select_describe(JOIN *join,
{
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 "));
=== modified file 'sql/sql_sort.h'
--- a/sql/sql_sort.h 2007-09-27 14:05:07 +0000
+++ b/sql/sql_sort.h 2010-06-29 00:02:19 +0000
@@ -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_CA
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);
+
=== modified file 'sql/uniques.cc'
--- a/sql/uniques.cc 2009-09-07 20:50:10 +0000
+++ b/sql/uniques.cc 2010-06-29 00:02:19 +0000
@@ -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, ele
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,26 @@ int unique_write_to_ptrs(uchar* key, ele
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;
+ }
+ 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);
@@ -276,7 +297,11 @@ double Unique::get_use_cost(uint *buffer
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);
+#if 1
result /= TIME_FOR_COMPARE_ROWID;
+#else
+ result /= TIME_FOR_COMPARE_ROWID * 10;
+#endif
DBUG_PRINT("info",("unique trees sizes: %u=%u*%lu + %lu", nkeys,
n_full_trees, n_full_trees?max_elements_in_tree:0,
@@ -327,7 +352,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 +385,7 @@ Unique::reset()
reinit_io_cache(&file, WRITE_CACHE, 0L, 0, 1);
}
elements= 0;
+ tree.flag= 0;
}
/*
@@ -576,14 +605,16 @@ 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;
+ (void) tree_walk(&tree, action,
this, left_root_right);
return 0;
}
@@ -614,7 +645,10 @@ 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;
+ sort_param.rec_length= sort_param.sort_length= sort_param.ref_length=
+ 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 +669,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:
