#At file:///export/home/didrik/repo/next-mr-opt-team-wl1393-merge/ based on revid:tor.didriksen@stripped
3253 Tor Didriksen 2010-12-02
more review comments
modified:
sql/bounded_queue.h
sql/filesort.cc
sql/filesort_utils.h
sql/sql_sort.h
sql/uniques.cc
unittest/gunit/bounded_queue-t.cc
=== modified file 'sql/bounded_queue.h'
--- a/sql/bounded_queue.h 2010-12-01 14:18:38 +0000
+++ b/sql/bounded_queue.h 2010-12-02 11:23:10 +0000
@@ -34,6 +34,9 @@ class Sort_param;
For each element, we call a user-supplied keymaker_function,
to generate a key of type Key_type for the element.
Instances of Key_type are compared with the user-supplied compare_function.
+
+ The underlying QUEUE implementation needs one extra element for replacing
+ the lowest/highest element when pushing into a full queue.
*/
template<typename Element_type, typename Key_type>
class Bounded_queue
=== modified file 'sql/filesort.cc'
--- a/sql/filesort.cc 2010-12-01 14:18:38 +0000
+++ b/sql/filesort.cc 2010-12-02 11:23:10 +0000
@@ -82,9 +82,9 @@ static bool check_if_pq_applicable(Sort_
ha_rows records, ulong memory_available);
-void Sort_param::init(uint sortlen, TABLE *table,
- ulong max_length_for_sort_data,
- ha_rows maxrows, bool sort_positions)
+void Sort_param::init_for_filesort(uint sortlen, TABLE *table,
+ ulong max_length_for_sort_data,
+ ha_rows maxrows, bool sort_positions)
{
sort_length= sortlen;
ref_length= table->file->ref_length;
@@ -194,9 +194,11 @@ ha_rows filesort(THD *thd, TABLE *table,
buffpek=0;
error= 1;
- param.init(sortlength(thd, sortorder, s_length, &multi_byte_charset),
- table,
- thd->variables.max_length_for_sort_data, max_rows, sort_positions);
+ param.init_for_filesort(sortlength(thd, sortorder, s_length,
+ &multi_byte_charset),
+ table,
+ thd->variables.max_length_for_sort_data,
+ max_rows, sort_positions);
/* filesort cannot handle zero-length records. */
DBUG_ASSERT(param.sort_length);
@@ -232,6 +234,7 @@ ha_rows filesort(THD *thd, TABLE *table,
&make_sortkey, ¶m, table_sort.sort_keys))
{
// If failed to init pq, fall back to merge-sort.
+ DBUG_PRINT("info", ("failed to allocate PQ, fallback to sort-merge"));
my_free(table_sort.sort_keys);
table_sort.sort_keys= NULL;
}
@@ -245,8 +248,8 @@ ha_rows filesort(THD *thd, TABLE *table,
while (memory_available >= min_sort_memory)
{
ulong keys= memory_available / (param.rec_length + sizeof(char*));
- param.num_keys_per_buffer= (uint) min(num_rows, keys);
- make_char_array(&table_sort, param.num_keys_per_buffer, param.rec_length);
+ param.max_keys_per_buffer= (uint) min(num_rows, keys);
+ make_char_array(&table_sort, param.max_keys_per_buffer, param.rec_length);
if (table_sort.sort_keys)
break;
ulong old_memory_available= memory_available;
@@ -308,7 +311,7 @@ ha_rows filesort(THD *thd, TABLE *table,
Use also the space previously used by string pointers in sort_buffer
for temporary key storage.
*/
- param.num_keys_per_buffer=((param.num_keys_per_buffer *
+ param.max_keys_per_buffer=((param.max_keys_per_buffer *
(param.rec_length + sizeof(char*))) /
param.rec_length - 1);
maxbuffer--; // Offset from 0
@@ -662,7 +665,7 @@ static ha_rows find_all_keys(Sort_param
}
else
{
- if (idx == param->num_keys_per_buffer)
+ if (idx == param->max_keys_per_buffer)
{
if (write_keys(param,sort_keys, idx, buffpek_pointers, tempfile))
DBUG_RETURN(HA_POS_ERROR);
@@ -1111,7 +1114,7 @@ static bool save_index(Sort_param *param
/**
Test whether priority queue is worth using to get top elements of an
- ordered result set. If it is then allocates buffer for required amount of
+ ordered result set. If it is, then allocates buffer for required amount of
records
@param param Sort parameters.
@@ -1147,11 +1150,7 @@ bool check_if_pq_applicable(Sort_param *
/*
How much Priority Queue sort is slower than qsort.
- For qsort we have an average case complexity of O(n*log(n)) comparisons.
- When using a priority queue, we have log(n) comparisons each time we
- push a new element. For PQ we also call qsort at the end.
- Measurements show that there is some extra overhead in QUEUE,
- so we set it to 3.0 rather than 2.0.
+ Measurements (see unit test) indicate that PQ is roughly 3 times slower.
*/
const double PQ_slowness= 3.0;
@@ -1170,7 +1169,7 @@ bool check_if_pq_applicable(Sort_param *
ulong num_available_keys=
memory_available / (param->rec_length + sizeof(char*));
// We need 1 extra record in the buffer, when using PQ.
- param->num_keys_per_buffer= (uint) param->max_rows + 1;
+ param->max_keys_per_buffer= (uint) param->max_rows + 1;
if (num_rows < num_available_keys)
{
@@ -1178,7 +1177,7 @@ bool check_if_pq_applicable(Sort_param *
if (param->max_rows < num_rows/PQ_slowness )
{
make_char_array(filesort_info,
- param->num_keys_per_buffer, param->rec_length);
+ param->max_keys_per_buffer, param->rec_length);
if (filesort_info->sort_keys)
DBUG_RETURN(true);
}
@@ -1189,10 +1188,10 @@ bool check_if_pq_applicable(Sort_param *
}
}
- if (param->num_keys_per_buffer < num_available_keys)
+ if (param->max_keys_per_buffer < num_available_keys)
{
make_char_array(filesort_info,
- param->num_keys_per_buffer, param->rec_length);
+ param->max_keys_per_buffer, param->rec_length);
if (filesort_info->sort_keys)
DBUG_RETURN(true);
}
@@ -1205,7 +1204,7 @@ bool check_if_pq_applicable(Sort_param *
num_available_keys= memory_available / row_length;
// Can we fit all the keys in memory?
- if (param->num_keys_per_buffer < num_available_keys)
+ if (param->max_keys_per_buffer < num_available_keys)
{
const double sort_merge_cost=
get_merge_many_buffs_cost_fast(num_rows,
@@ -1218,7 +1217,7 @@ bool check_if_pq_applicable(Sort_param *
cost of file lookup afterwards.
*/
const double pq_cost=
- (PQ_slowness * num_rows + param->num_keys_per_buffer) *
+ (PQ_slowness * num_rows + param->max_keys_per_buffer) *
log(param->max_rows + 1.0) / TIME_FOR_COMPARE_ROWID +
param->max_rows * table->file->scan_time();
@@ -1226,7 +1225,7 @@ bool check_if_pq_applicable(Sort_param *
DBUG_RETURN(false);
make_char_array(filesort_info,
- param->num_keys_per_buffer, param->rec_length);
+ param->max_keys_per_buffer, param->rec_length);
if (filesort_info->sort_keys)
{
// Make attached data to be references instead of fields.
@@ -1413,7 +1412,7 @@ int merge_buffers(Sort_param *param, IO_
res_length= param->res_length;
sort_length= param->sort_length;
offset= rec_length-res_length;
- maxcount= (ulong) (param->num_keys_per_buffer / ((uint) (Tb-Fb) +1));
+ maxcount= (ulong) (param->max_keys_per_buffer / ((uint) (Tb-Fb) +1));
to_start_filepos= my_b_tell(to_file);
strpos= (uchar*) sort_buffer;
org_max_rows=max_rows= param->max_rows;
@@ -1529,7 +1528,7 @@ int merge_buffers(Sort_param *param, IO_
}
buffpek= (BUFFPEK*) queue_top(&queue);
buffpek->base= sort_buffer;
- buffpek->max_keys= param->num_keys_per_buffer;
+ buffpek->max_keys= param->max_keys_per_buffer;
/*
As we know all entries in the buffer are unique, we only have to
=== modified file 'sql/filesort_utils.h'
--- a/sql/filesort_utils.h 2010-12-01 14:18:38 +0000
+++ b/sql/filesort_utils.h 2010-12-02 11:23:10 +0000
@@ -12,11 +12,13 @@
Calculates cost of merge sort by simulating call to merge_many_buff().
@retval
- computed cost of merge sort
+ Computed cost of merge sort in disk seeks.
@note
Declared here in order to be able to unit test it,
since library dependencies have not been sorted out yet.
+
+ See also comments get_merge_many_buffs_cost().
*/
#define FILESORT_UTILS_INCLUDED
=== modified file 'sql/sql_sort.h'
--- a/sql/sql_sort.h 2010-11-29 11:21:22 +0000
+++ b/sql/sql_sort.h 2010-12-02 11:23:10 +0000
@@ -73,22 +73,22 @@ struct BUFFPEK_COMPARE_CONTEXT
class Sort_param {
public:
- uint rec_length; /* Length of sorted records */
- uint sort_length; /* Length of sorted columns */
- uint ref_length; /* Length of record ref. */
- uint addon_length; /* Length of added packed fields */
- uint res_length; /* Length of records in final sorted file/buffer */
- uint num_keys_per_buffer; /* Max keys / buffer */
- ha_rows max_rows; /* Select limit, or HA_POS_ERROR if unlimited */
- ha_rows examined_rows; /* Number of examined rows */
- TABLE *sort_form; /* For quicker make_sortkey */
+ uint rec_length; // Length of sorted records.
+ uint sort_length; // Length of sorted columns.
+ uint ref_length; // Length of record ref.
+ uint addon_length; // Length of added packed fields.
+ uint res_length; // Length of records in final sorted file/buffer.
+ uint max_keys_per_buffer; // Max keys / buffer.
+ ha_rows max_rows; // Select limit, or HA_POS_ERROR if unlimited.
+ ha_rows examined_rows; // Number of examined rows.
+ TABLE *sort_form; // For quicker make_sortkey.
SORT_FIELD *local_sortorder;
SORT_FIELD *end;
- SORT_ADDON_FIELD *addon_field; /* Descriptors for companion fields */
+ SORT_ADDON_FIELD *addon_field; // Descriptors for companion fields.
uchar *unique_buff;
bool not_killable;
char* tmp_buffer;
- /* The fields below are used only by Unique class */
+ // The fields below are used only by Unique class.
qsort2_cmp compare;
BUFFPEK_COMPARE_CONTEXT cmp_context;
@@ -96,8 +96,9 @@ public:
{
memset(this, 0, sizeof(*this));
}
- void init(uint sortlen, TABLE *table, ulong max_length_for_sort_data,
- ha_rows maxrows, bool sort_positions);
+ void init_for_filesort(uint sortlen, TABLE *table,
+ ulong max_length_for_sort_data,
+ ha_rows maxrows, bool sort_positions);
};
=== modified file 'sql/uniques.cc'
--- a/sql/uniques.cc 2010-11-29 11:21:22 +0000
+++ b/sql/uniques.cc 2010-12-02 11:23:10 +0000
@@ -614,18 +614,17 @@ bool Unique::get(TABLE *table)
Sort_param sort_param;
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.num_keys_per_buffer=
+ sort_param.rec_length= sort_param.sort_length= sort_param.ref_length= size;
+ sort_param.max_keys_per_buffer=
(uint) (max_in_memory_size / sort_param.sort_length);
sort_param.not_killable=1;
- if (!(sort_buffer=(uchar*) my_malloc((sort_param.num_keys_per_buffer + 1) *
- sort_param.sort_length,
- MYF(0))))
+ if (!(sort_buffer=(uchar*) my_malloc((sort_param.max_keys_per_buffer + 1) *
+ sort_param.sort_length,
+ MYF(0))))
return 1;
- sort_param.unique_buff= sort_buffer+(sort_param.num_keys_per_buffer *
- sort_param.sort_length);
+ sort_param.unique_buff= sort_buffer+(sort_param.max_keys_per_buffer *
+ sort_param.sort_length);
sort_param.compare= (qsort2_cmp) buffpek_compare;
sort_param.cmp_context.key_compare= tree.compare;
=== modified file 'unittest/gunit/bounded_queue-t.cc'
--- a/unittest/gunit/bounded_queue-t.cc 2010-12-01 14:18:38 +0000
+++ b/unittest/gunit/bounded_queue-t.cc 2010-12-02 11:23:10 +0000
@@ -246,6 +246,7 @@ TEST_F(BoundedQueueTest, push_and_pop_ke
/*
Verifies that push and bounded size works, and that pop() gives sorted order.
+ Note that with max_at_top == true, we will pop() in reverse order.
*/
TEST_F(BoundedQueueTest, push_and_pop_keep_smallest)
{
Attachment: [text/bzr-bundle] bzr/tor.didriksen@oracle.com-20101202112310-ci7ox8dqag2uv1sp.bundle
| Thread |
|---|
| • bzr commit into mysql-trunk-bugfixing branch (tor.didriksen:3253) | Tor Didriksen | 2 Dec |
