From: Tor Didriksen Date: December 2 2010 11:23am Subject: bzr commit into mysql-trunk-bugfixing branch (tor.didriksen:3253) List-Archive: http://lists.mysql.com/commits/125799 Message-Id: <20101202112316.7ED4E1646@atum07.norway.sun.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============8055274128866085612==" --===============8055274128866085612== MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Content-Disposition: inline #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 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) { --===============8055274128866085612== MIME-Version: 1.0 Content-Type: text/bzr-bundle; charset="us-ascii"; name="bzr/tor.didriksen@stripped" Content-Transfer-Encoding: 7bit Content-Disposition: inline # Bazaar merge directive format 2 (Bazaar 0.90) # revision_id: tor.didriksen@stripped\ # ci7ox8dqag2uv1sp # target_branch: file:///export/home/didrik/repo/next-mr-opt-team-\ # wl1393-merge/ # testament_sha1: bb7e0b5c9b4f39bf5426e48ca2fce71c99735778 # timestamp: 2010-12-02 12:23:16 +0100 # base_revision_id: tor.didriksen@stripped\ # xzyffh20fx9gttij # # Begin bundle IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWQNCK8IABnd/gFXQUwD5f/// f+f+IL////BgDF3z7NeM91sQAAATu88r11Q622Hbo27tkxzZ1sJJCAQFNhTzSabJoU8U9IaNAGgA AAPUGoyKemmFPUgA0Gj1GhoABo0BoGg9TQNqHGTJo0Bo0xGRoYhgTRpiDEaDCAAwSJEE9ST0009U 8m0mggYgaNNDIDQANNAAIokajRqYo9GpoMhphGmEDJ6gAAAAASRAIEyBpGmkYjRpTT1GRpmjTUaM mmgANqZL1iEGjZ0xuj297rv2bkjC3pgk2xuI38U6rEVQzn9P4/2g23TZ5euJ1ssZOjxQaDrGbuWc N1an4TL2VKJeyuumr7qYiBQSnhZ3k1h6wjndEo8otC1qziz2jfitpgtrriqUTLCQsCyEwkoMBr83 fzU1Jg+96l9xy8HGpyJxGphOAXwFlEwTYm022DaGw+3OgV34qx9+Az5orzuNh2O91OqvRKt2ub0O bsq87VgXYBW8oqzgxRo3lE0X/K6dptWA+GELWvhe1TqZE4sbpGB0c2VO11OoZgri41f7u7M29uBZ Xd0WlKpK0DLLo1GlGduLScEuc5jGzROel8HtgmswEEEqtNbfOuAGChzV0A8bAuWVYOxLCcwdFIa8 awRj9QuNncRANlGMGK2raVRYgkiIR910thIOBGEkt7EIgpuYyC2ZxqgHGxK4u0iDXgqk4+nDC6Qp lmeloND3+VzeXf4R9ekMqexcl4qTFvEXspnj/q6GG9BVgM2BmQGi+uDn9/VKaEmH29MFnZTtRU+T FQ4fGqtBU2COyGXFNEaWmMsdcI6LishwR0kYWk3wXuuIdZg1y03nhomyOs7Vgzm6DKCVhx+xwySI GtGl4lPhwAGsw9s7RyXNQNsiHbN9DwxReb6ObOiVePU9LRVo1aCtoM7JhighREKUpMZBQBtK/upD OTk5SHLllCW+YHRrNjmLLsOxCues0kcbRpYQ0pV9RgEr40XloSDYI7coowoNIUiAZCBpCYBXBYSw kiAscZgiRO4YJTByMKBAoDlG91jIZBSSqObBykZSS85BfbmgV91ILCts7PSE5POxHyo/jUAeAMyE v3/e5AxHB/E8Pl2KzLKJMc2AFTUx3FYoKJ2ArfvIEkCYkWHBwDUvcznd6/XwNuAX2WLDtpg5iBEd LcB0pGOrjsmuhOCoRJNf9MiiUqercRjV5h1EqT1JD3izMDJHG8obzlIXAyPyAMNbRgrDLpx1yxi9 NxMGdFGSSqgT1BzOR7EmlgASO07HUhqDGQwBkFTFtVOvYzRCI0eBbQjJr3vV8NCC7dOuCCxMc4FT qKQ/UWDwPI5nnMEcT2gEjobuxiWx82Kw2EOdN/GMSlN4BEdw8++RC8bAKKGDmmA87xlgVSjXkES+ s/iZIoYFSZqOMj6jRGYS/IxzvcV+zKGcZVlz2SeFiAubIpc6CJyLXl/gwTAqYBkXUDzMdRvNhkHa YTaR7hy4pnkVSyOQ56CtxI4I6Ft+2/cNk0WLuO3ahhjhcRNhKxRwZi6y+KGO/aXEz40veBy9SDhx MR9qdjacbtcM2g7xWx5mIcOhJ6jExsGW8jYaXHInJpmmNa7jbeBYRA0MyZ3EUd5lkqbt1ZYxydyQ TIXhOeBeehENF4hI6zLIkDpcdSepw4AbTMmYhPsMeZkW2HgAUN+GeJhDfCEoOzXJNMwKBQgR4Ut1 bio1SsAqlvgqF0YBa6EjWM85b7LAvNS87QDSphlSGOlc4sxE1IwoUkmhvByuBpkWpzxepusRJSDQ aG0xaZAzWehuKlZbkh3xXmYlscK3N20ylFKbwAajSSsgrNqCOKxhutGTizYnDVWPYOZJyW54rLM7 JToagwbKEKCBD4RRGAoaeMWLeALRC8i/3RQyJtNDb51f7uHDdWuQUjE36edRSYpN/yKNxBIFKZO/ jFeaqqKx2kYNpGjtPg07jiyilccJPddhxpuT9fjV3NBS8DUwhvb4YG+Dt1Zd9i1gYbILlCEPEFmC LY4KWTSauLBYpUQh3xm6t+kIm2Kg6MOlyM2BOiW/vGU1AOUYUD29n0numOb6BifbYlgtg2r/C9tB Ctp+LPiMMe45HwAOuqD7zjuOZ2aRhiqCWLAExcyO6OlMrygrWFb9+zVvw0Is2HO0v0Fp1rEXJt+P j3Z1Dmka+kifYOYo6HvJFd8SJuOvoFTq2/YfaTLvAwSoek97M+xelNpOcJQ7SI8qBGlYvVAouLjm etqjJnrLxcKnUX+LfcgsfwYJnrnHQ+wA5KLNvcQsTIheITGNoJpdu6EzCZlqZdgrQ7LWSYswshWH NezlyPBqBgB0fI89EJ0t6yMMMSReox0v2UwFuKs/kdppH5BC3JZaic0AGBIWG1yOHP4FbnG+Ou5z TCbPP3VI1j93GdVdqMOITJkqHUT9TDlPaVaJxmDN2nA7hx8xplx270uYqmTKrD5/fHQDQQ0PUY8O 0p7aHTkLAZQaRc3p674S50hUkKPkQ+etji8T0FOBulp1tTZmi8cuOw8wYdKs3Ru7/Dkw2+BdqsO4 28yI4h9KSoaCqxusMidRdbFK9HbiSNrZougQsuDF74zl3rHH4b4IOqe2uyFcS47WSgkXcC6yE+4B XifXIDHnZDqhZcZiNg41kEq6yrsnMTRk5u60UDcLzcM5vbpjADoZ1hUuORZNpLV4Mj9RjiGBQWn6 RvlaPQ0R5yCokx+i8d7c0swoLoAannOsrICGJ8WG2jITgLlS5OZFJWLtpgGFVMlsDCRJKGsSun8/ fAiUYdLNS7fvuhVaqIbTcWJATJXyq4AP5Slqc0xLpQuEghP6mCkJ+1T929LSpZ40rqQrCZIGZBlg LuEqOvFsQPeY7MfC3ZJoyJDsXZnTRj20DV3DNFKGdBmieRg8tFDSy4DMa5wJMuPae3WzP3dxCQWH wQ2/PuGZIPYMgtkkL85oYGPSlXPGZCslkEOEy5LdNQtHVbRGUZZKUgnmshBOSDPhlDl1wB8DFOsN lmwPIuVqVbbrjzggUxJaneVISlUPwy3Ek/0d6YBmdx2dmf/rhTzlwtDeGwn68G3d7Dm8lYiU3Isb Vj5kX1IulXaiWp/NSqg6m4gZADEJqJCthBRJzZONuk0o4AG7D77hqxXhS9Jctt0VgZhiYWYYhS0t j1fKL+bMMzO1lCMyuUAVmQ8BfHpJcboidmp81yeK9Bfs9L8vmpp8GKCEwviIToNjSHN0gjvSvkgW +jDU9l5q5Mo468wLEdYAxmCFiBrCjaRl0hlTjjxZyT9Q5t3ee9KxwmAlSzmO3GILnOjWeQLJqMkq 1QRbn0SQ3BzoxFgBHeRdZW0dgvlqZb4SMy5GHelkmBywFBGBKQISPVhQKCvT2aLTheK6Icd0lNFV aDo45WoWRk1VF3wwDVHJGlOFzi7hh2L62dwVRkJQYXAs6bXkfNspDjOME3CUzNNII/PO0ZwKLmmi V6aRgIL7QMNe6VMUhcpwdL08BV0QbVOIoWA0jF9GhiovChR0oXt0E3Mhc40Vpqtk36ElyI8zbbjG iGWaGYxrIgbks+V9O7akTauam651qUMtqm5Rp2qr7GSHBB0jBdRLmKDAVhG4G2WHRyxyYsNpma9M buxjHsrqhbY+lC/YDJETr2ue9Fdlr70sFTkUxUwc0kdk0HYc0mE/1cUFudlq1zEWQYb0skRNGHS/ MhwMMlsELE6gUaHWHm6oX914OimgVGzJoIb2kXD6nNSR5AGoB0PzfQZrkkTPkv+QuMp1JQIcs4TX lH1GM2MnnLQCqlBHGRvbJ2ShYrerJE2iJomtZurrJSd8ykqSJ2J7ZtLBEOgwGtL/i7kinChIAaEV 4QA= --===============8055274128866085612==--